7 struct lfds700_hash_a_element
21 number_elements_per_thread;
23 struct lfds700_hash_a_state
30 /***** private prototypes *****/
31 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state );
32 static int key_compare_function( void const *new_key, void const *existing_key );
33 static void key_hash_function( void const *key, lfds700_pal_uint_t *hash );
39 /****************************************************************************/
40 void test_lfds700_hash_a_random_adds_fail_on_existing( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
42 enum lfds700_misc_validity
43 dvs = LFDS700_MISC_VALIDITY_VALID;
47 number_elements_per_thread,
48 number_elements_total,
49 number_logical_processors,
54 struct lfds700_hash_a_element
57 struct lfds700_hash_a_state
60 struct lfds700_list_asu_element
63 struct lfds700_btree_au_state
66 struct lfds700_misc_prng_state
69 struct lfds700_misc_validation_info
72 struct test_pal_logical_processor
75 struct util_thread_starter_state
84 test_pal_thread_state_t
87 assert( list_of_logical_processors != NULL );
88 // TRD : memory_in_megabytes can be any value in its range
90 /* TRD : we create a single hash_a
91 we generate 100k elements per thread (with one thread per logical processor) in an array
92 each element is unique
93 we randomly sort the elements
94 then each thread loops, adds those elements into the hash_a
95 we check that each datum inserts okay - failure will occur on non-unique data, i.e. two identical keys
96 we should have no failures
97 we then call the hash_a validation function
98 then using the hash_a get() we check all the elements we added are present
101 internal_display_test_name( "Random adds and get (fail on existing key)" );
103 lfds700_misc_prng_init( &ps );
105 lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
107 baus = util_aligned_malloc( sizeof(struct lfds700_btree_au_state) * 1000, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
109 lfds700_hash_a_init_valid_on_current_logical_core( &has, baus, 1000, key_compare_function, key_hash_function, LFDS700_HASH_A_EXISTING_KEY_FAIL, NULL );
111 number_elements_per_thread = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
112 number_elements_total = number_elements_per_thread * number_logical_processors;
114 // TRD : created an ordered list of unique numbers
115 element_array = util_aligned_malloc( sizeof(struct test_element) * number_elements_total, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
117 for( loop = 0 ; loop < number_elements_total ; loop++ )
119 (element_array+loop)->key = loop;
120 // TRD : + number_elements just to make it different to the key
121 (element_array+loop)->datum = loop + number_elements_total;
124 for( loop = 0 ; loop < number_elements_total ; loop++ )
126 offset = LFDS700_MISC_PRNG_GENERATE( &ps );
127 offset %= number_elements_total;
128 temp = (element_array + offset)->key;
129 (element_array + offset)->key = (element_array + loop)->key;
130 (element_array + loop)->key = temp;
133 ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
135 for( loop = 0 ; loop < number_logical_processors ; loop++ )
137 (ts+loop)->has = &has;
138 (ts+loop)->element_array = element_array + number_elements_per_thread*loop;
139 (ts+loop)->error_flag = LOWERED;
140 (ts+loop)->number_elements_per_thread = number_elements_per_thread;
143 thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
145 util_thread_starter_new( &tts, number_logical_processors );
147 LFDS700_MISC_BARRIER_STORE;
149 lfds700_misc_force_store();
153 while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
155 lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
156 util_thread_starter_start( tts, &thread_handles[loop], loop, lp, thread_adding, ts+loop );
160 util_thread_starter_run( tts );
162 for( loop = 0 ; loop < number_logical_processors ; loop++ )
163 test_pal_thread_wait( thread_handles[loop] );
165 util_thread_starter_delete( tts );
167 free( thread_handles );
169 LFDS700_MISC_BARRIER_LOAD;
171 // TRD : now for validation
172 vi.min_elements = vi.max_elements = number_elements_total;
173 lfds700_hash_a_query( &has, LFDS700_HASH_A_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) &dvs );
175 /* TRD : now we attempt to lfds700_hash_a_get_by_key() for every element in number_array
176 any failure to find is an error
177 we also check we've obtained the correct element
180 for( loop = 0 ; dvs == LFDS700_MISC_VALIDITY_VALID and loop < number_elements_total ; loop++ )
181 if( 0 == lfds700_hash_a_get_by_key(&has, (void *) (ts->element_array+loop)->key, &hae) )
182 dvs = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
185 value = (lfds700_pal_uint_t) LFDS700_HASH_A_GET_VALUE_FROM_ELEMENT( *hae );
186 if( (ts->element_array+loop)->datum != value )
187 dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
190 // TRD : just check error_flags weren't raised
191 if( dvs == LFDS700_MISC_VALIDITY_VALID )
192 for( loop = 0 ; loop < number_logical_processors ; loop++ )
193 if( (ts+loop)->error_flag == RAISED )
194 dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
197 lfds700_hash_a_cleanup( &has, NULL );
199 util_aligned_free( baus );
203 util_aligned_free( element_array );
205 // TRD : print the test result
206 internal_display_test_result( 1, "hash_a", dvs );
215 /****************************************************************************/
216 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state )
218 enum lfds700_hash_a_insert_result
227 struct lfds700_misc_prng_state
230 struct util_thread_starter_thread_state
233 LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
235 assert( util_thread_starter_thread_state != NULL );
237 tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
238 ts = (struct test_state *) tsts->thread_user_state;
240 lfds700_misc_prng_init( &ps );
242 util_thread_starter_ready_and_wait( tsts );
244 while( index < ts->number_elements_per_thread )
246 LFDS700_HASH_A_SET_KEY_IN_ELEMENT( (ts->element_array+index)->hae, (ts->element_array+index)->key );
247 LFDS700_HASH_A_SET_VALUE_IN_ELEMENT( (ts->element_array+index)->hae, (ts->element_array+index)->datum );
248 apr = lfds700_hash_a_insert( ts->has, &(ts->element_array+index)->hae, NULL, &ps );
250 if( apr == LFDS700_HASH_A_PUT_RESULT_FAILURE_EXISTING_KEY )
251 ts->error_flag = RAISED;
256 LFDS700_MISC_BARRIER_STORE;
258 lfds700_misc_force_store();
260 return( (test_pal_thread_return_t) EXIT_SUCCESS );
267 /****************************************************************************/
268 #pragma warning( disable : 4100 )
270 static int key_compare_function( void const *new_key, void const *existing_key )
275 // TRD : new_key can be NULL (i.e. 0)
276 // TRD : existing_key can be NULL (i.e. 0)
278 if( (lfds700_pal_uint_t) new_key < (lfds700_pal_uint_t) existing_key )
281 if( (lfds700_pal_uint_t) new_key > (lfds700_pal_uint_t) existing_key )
287 #pragma warning( default : 4100 )
293 /****************************************************************************/
294 #pragma warning( disable : 4100 )
296 static void key_hash_function( void const *key, lfds700_pal_uint_t *hash )
298 // TRD : key can be NULL
299 assert( hash != NULL );
303 /* TRD : this function iterates over the user data
304 and we are using the void pointer *as* key data
305 so here we need to pass in the addy of key
308 LFDS700_HASH_A_32BIT_HASH_FUNCTION( (void *) &key, sizeof(lfds700_pal_uint_t), *hash );
313 #pragma warning( default : 4100 )