7 struct lfds700_hash_a_element
17 number_elements_per_thread,
20 struct lfds700_hash_a_state
27 /***** private prototypes *****/
28 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state );
29 static int key_compare_function( void const *new_key, void const *existing_key );
30 static void key_hash_function( void const *key, lfds700_pal_uint_t *hash );
31 static int qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 );
37 /****************************************************************************/
38 void test_lfds700_hash_a_random_adds_overwrite_on_existing( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
40 enum lfds700_misc_validity
41 dvs = LFDS700_MISC_VALIDITY_VALID;
47 actual_sum_overwrite_existing_count,
48 expected_sum_overwrite_existing_count,
51 number_elements_per_thread,
52 number_elements_total,
53 number_logical_processors,
56 struct lfds700_hash_a_iterate
59 struct lfds700_hash_a_element
62 struct lfds700_hash_a_state
65 struct lfds700_list_asu_element
68 struct lfds700_btree_au_state
71 struct lfds700_misc_prng_state
74 struct lfds700_misc_validation_info
77 struct test_pal_logical_processor
80 struct util_thread_starter_state
89 test_pal_thread_state_t
96 assert( list_of_logical_processors != NULL );
97 // TRD : memory_in_megabytes can be any value in its range
99 /* TRD : we create a single hash_a
100 we generate n elements per thread
101 each element contains a key value, which is set to a random value
102 (we don't use value, so it's just set to 0)
103 the threads then run, putting
104 the threads count their number of overwrite hits
105 once the threads are done, then we
106 count the number of each key
107 from this we figure out the min/max element for hash_a validation, so we call validation
108 we check the sum of overwrites for each thread is what it should be
109 then using the hash_a get() we check all the elements we expect are present
110 and then we iterate over the hash_a
111 checking we see each key once
114 internal_display_test_name( "Random adds, get and iterate (overwrite on existing key)" );
116 lfds700_misc_prng_init( &ps );
118 lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
120 baus = util_aligned_malloc( sizeof(struct lfds700_btree_au_state) * 1000, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
122 lfds700_hash_a_init_valid_on_current_logical_core( &has, baus, 1000, key_compare_function, key_hash_function, LFDS700_HASH_A_EXISTING_KEY_OVERWRITE, NULL );
124 // TRD : we divide by 2 beccause we have to allocate a second array of this size later
125 number_elements_per_thread = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors ) / 2;
126 number_elements_total = number_elements_per_thread * number_logical_processors;
128 // TRD : created an ordered list of unique numbers
129 element_array = util_aligned_malloc( sizeof(struct test_element) * number_elements_total, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
131 for( loop = 0 ; loop < number_elements_total ; loop++ )
133 random_value = LFDS700_MISC_PRNG_GENERATE( &ps );
134 (element_array+loop)->key = (lfds700_pal_uint_t) floor( (number_elements_total/2) * ((double) random_value / (double) LFDS700_MISC_PRNG_MAX) );
137 ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
139 for( loop = 0 ; loop < number_logical_processors ; loop++ )
141 (ts+loop)->has = &has;
142 (ts+loop)->element_array = element_array + number_elements_per_thread*loop;
143 (ts+loop)->overwrite_count = 0;
144 (ts+loop)->number_elements_per_thread = number_elements_per_thread;
147 thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
149 util_thread_starter_new( &tts, number_logical_processors );
151 LFDS700_MISC_BARRIER_STORE;
153 lfds700_misc_force_store();
157 while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
159 lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
160 util_thread_starter_start( tts, &thread_handles[loop], loop, lp, thread_adding, ts+loop );
164 util_thread_starter_run( tts );
166 for( loop = 0 ; loop < number_logical_processors ; loop++ )
167 test_pal_thread_wait( thread_handles[loop] );
169 util_thread_starter_delete( tts );
171 free( thread_handles );
173 LFDS700_MISC_BARRIER_LOAD;
175 // TRD : now for validation
176 key_count_array = util_malloc_wrapper( sizeof(lfds700_pal_uint_t) * number_elements_total );
177 for( loop = 0 ; loop < number_elements_total ; loop++ )
178 *(key_count_array+loop) = 0;
180 for( loop = 0 ; loop < number_elements_total ; loop++ )
181 ( *(key_count_array + (element_array+loop)->key) )++;
183 vi.min_elements = number_elements_total;
185 for( loop = 0 ; loop < number_elements_total ; loop++ )
186 if( *(key_count_array+loop) == 0 )
189 vi.max_elements = vi.min_elements;
191 lfds700_hash_a_query( &has, LFDS700_HASH_A_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) &dvs );
193 expected_sum_overwrite_existing_count = 0;
195 for( loop = 0 ; loop < number_elements_total ; loop++ )
196 if( *(key_count_array+loop) != 0 )
197 expected_sum_overwrite_existing_count += *(key_count_array+loop) - 1;
199 actual_sum_overwrite_existing_count = 0;
201 for( loop = 0 ; loop < number_logical_processors ; loop++ )
202 actual_sum_overwrite_existing_count += (ts+loop)->overwrite_count;
204 if( expected_sum_overwrite_existing_count != actual_sum_overwrite_existing_count )
205 dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
207 // TRD : now loop over the expected array and check we can get() every element
208 for( loop = 0 ; loop < number_elements_total ; loop++ )
209 if( *(key_count_array+loop) > 0 )
211 rv = lfds700_hash_a_get_by_key( &has, (void *) loop, &hae );
214 dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
217 /* TRD : now iterate, checking we find every element and no others
218 to do this in a timely manner, we need to qsort() the key values
219 and use bsearch() to check for items in the array
222 for( loop = 0 ; loop < number_elements_total ; loop++ )
223 if( *(key_count_array+loop) != 0 )
224 *(key_count_array+loop) = loop;
226 *(key_count_array+loop) = 0;
228 qsort( key_count_array, number_elements_total, sizeof(lfds700_pal_uint_t), qsort_and_bsearch_key_compare_function );
230 lfds700_hash_a_iterate_init( &has, &hai );
232 while( dvs == LFDS700_MISC_VALIDITY_VALID and lfds700_hash_a_iterate(&hai, &hae) )
234 key = LFDS700_HASH_A_GET_KEY_FROM_ELEMENT( *hae );
236 key_pointer = bsearch( &key, key_count_array, number_elements_total, sizeof(lfds700_pal_uint_t), qsort_and_bsearch_key_compare_function );
238 if( key_pointer == NULL )
239 dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
243 lfds700_hash_a_cleanup( &has, NULL );
245 util_aligned_free( baus );
249 util_aligned_free( element_array );
251 free( key_count_array );
253 // TRD : print the test result
254 internal_display_test_result( 1, "hash_a", dvs );
263 /****************************************************************************/
264 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state )
266 enum lfds700_hash_a_insert_result
275 struct lfds700_misc_prng_state
278 struct util_thread_starter_thread_state
281 LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
283 assert( util_thread_starter_thread_state != NULL );
285 tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
286 ts = (struct test_state *) tsts->thread_user_state;
288 lfds700_misc_prng_init( &ps );
290 util_thread_starter_ready_and_wait( tsts );
292 while( index < ts->number_elements_per_thread )
294 LFDS700_HASH_A_SET_KEY_IN_ELEMENT( (ts->element_array+index)->hae, (ts->element_array+index)->key );
295 LFDS700_HASH_A_SET_VALUE_IN_ELEMENT( (ts->element_array+index)->hae, 0 );
296 apr = lfds700_hash_a_insert( ts->has, &(ts->element_array+index)->hae, NULL, &ps );
298 if( apr == LFDS700_HASH_A_PUT_RESULT_SUCCESS_OVERWRITE )
299 ts->overwrite_count++;
304 LFDS700_MISC_BARRIER_STORE;
306 lfds700_misc_force_store();
308 return( (test_pal_thread_return_t) EXIT_SUCCESS );
315 /****************************************************************************/
316 #pragma warning( disable : 4100 )
318 static int key_compare_function( void const *new_key, void const *existing_key )
323 // TRD : new_key can be NULL (i.e. 0)
324 // TRD : existing_key can be NULL (i.e. 0)
326 if( (lfds700_pal_uint_t) new_key < (lfds700_pal_uint_t) existing_key )
329 if( (lfds700_pal_uint_t) new_key > (lfds700_pal_uint_t) existing_key )
335 #pragma warning( default : 4100 )
341 /****************************************************************************/
342 #pragma warning( disable : 4100 )
344 static void key_hash_function( void const *key, lfds700_pal_uint_t *hash )
346 // TRD : key can be NULL
347 assert( hash != NULL );
351 /* TRD : this function iterates over the user data
352 and we are using the void pointer *as* key data
353 so here we need to pass in the addy of key
356 LFDS700_HASH_A_32BIT_HASH_FUNCTION( (void *) &key, sizeof(lfds700_pal_uint_t), *hash );
361 #pragma warning( default : 4100 )
367 /****************************************************************************/
368 static int qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 )
377 s1 = *(lfds700_pal_uint_t *) e1;
378 s2 = *(lfds700_pal_uint_t *) e2;