pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/test/src/test_lfds700_hash_addonly_random_adds_fail.c

   1 /***** includes *****/
   2 #include "internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds700_hash_a_element
   8     hae;
   9
  10   lfds700_pal_uint_t
  11     datum,
  12     key;
  13 };
  14
  15 struct test_state
  16 {
  17   enum flag
  18     error_flag;
  19
  20   lfds700_pal_uint_t
  21     number_elements_per_thread;
  22
  23   struct lfds700_hash_a_state
  24     *has;
  25
  26   struct test_element
  27     *element_array;
  28 };
  29
  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 );
  34
  35
  36
  37
  38
  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 )
  41 {
  42   enum lfds700_misc_validity
  43     dvs = LFDS700_MISC_VALIDITY_VALID;
  44
  45   lfds700_pal_uint_t
  46     loop,
  47     number_elements_per_thread,
  48     number_elements_total,
  49     number_logical_processors,
  50     offset,
  51     temp,
  52     value;
  53
  54   struct lfds700_hash_a_element
  55     *hae;
  56
  57   struct lfds700_hash_a_state
  58     has;
  59
  60   struct lfds700_list_asu_element
  61     *lasue = NULL;
  62
  63   struct lfds700_btree_au_state
  64     *baus;
  65
  66   struct lfds700_misc_prng_state
  67     ps;
  68
  69   struct lfds700_misc_validation_info
  70     vi;
  71
  72   struct test_pal_logical_processor
  73     *lp;
  74
  75   struct util_thread_starter_state
  76     *tts;
  77
  78   struct test_element
  79     *element_array;
  80
  81   struct test_state
  82     *ts;
  83
  84   test_pal_thread_state_t
  85     *thread_handles;
  86
  87   assert( list_of_logical_processors != NULL );
  88   // TRD : memory_in_megabytes can be any value in its range
  89
  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
  99   */
 100
 101   internal_display_test_name( "Random adds and get (fail on existing key)" );
 102
 103   lfds700_misc_prng_init( &ps );
 104
 105   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 106
 107   baus = util_aligned_malloc( sizeof(struct lfds700_btree_au_state) * 1000, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 108
 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 );
 110
 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;
 113
 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 );
 116
 117   for( loop = 0 ; loop < number_elements_total ; loop++ )
 118   {
 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;
 122   }
 123
 124   for( loop = 0 ; loop < number_elements_total ; loop++ )
 125   {
 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;
 131   }
 132
 133   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
 134
 135   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 136   {
 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;
 141   }
 142
 143   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
 144
 145   util_thread_starter_new( &tts, number_logical_processors );
 146
 147   LFDS700_MISC_BARRIER_STORE;
 148
 149   lfds700_misc_force_store();
 150
 151   loop = 0;
 152
 153   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 154   {
 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 );
 157     loop++;
 158   }
 159
 160   util_thread_starter_run( tts );
 161
 162   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 163     test_pal_thread_wait( thread_handles[loop] );
 164
 165   util_thread_starter_delete( tts );
 166
 167   free( thread_handles );
 168
 169   LFDS700_MISC_BARRIER_LOAD;
 170
 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 );
 174
 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
 178   */
 179
 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;
 183     else
 184     {
 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;
 188     }
 189
 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;
 195
 196   // TRD : cleanup
 197   lfds700_hash_a_cleanup( &has, NULL );
 198
 199   util_aligned_free( baus );
 200
 201   free( ts );
 202
 203   util_aligned_free( element_array );
 204
 205   // TRD : print the test result
 206   internal_display_test_result( 1, "hash_a", dvs );
 207
 208   return;
 209 }
 210
 211
 212
 213
 214
 215 /****************************************************************************/
 216 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state )
 217 {
 218   enum lfds700_hash_a_insert_result
 219     apr;
 220
 221   lfds700_pal_uint_t
 222     index = 0;
 223
 224   struct test_state
 225     *ts;
 226
 227   struct lfds700_misc_prng_state
 228     ps;
 229
 230   struct util_thread_starter_thread_state
 231     *tsts;
 232
 233   LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 234
 235   assert( util_thread_starter_thread_state != NULL );
 236
 237   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 238   ts = (struct test_state *) tsts->thread_user_state;
 239
 240   lfds700_misc_prng_init( &ps );
 241
 242   util_thread_starter_ready_and_wait( tsts );
 243
 244   while( index < ts->number_elements_per_thread )
 245   {
 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 );
 249
 250     if( apr == LFDS700_HASH_A_PUT_RESULT_FAILURE_EXISTING_KEY )
 251       ts->error_flag = RAISED;
 252
 253     index++;
 254   }
 255
 256   LFDS700_MISC_BARRIER_STORE;
 257
 258   lfds700_misc_force_store();
 259
 260   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 261 }
 262
 263
 264
 265
 266
 267 /****************************************************************************/
 268 #pragma warning( disable : 4100 )
 269
 270 static int key_compare_function( void const *new_key, void const *existing_key )
 271 {
 272   int
 273     cr = 0;
 274
 275   // TRD : new_key can be NULL (i.e. 0)
 276   // TRD : existing_key can be NULL (i.e. 0)
 277
 278   if( (lfds700_pal_uint_t) new_key < (lfds700_pal_uint_t) existing_key )
 279     cr = -1;
 280
 281   if( (lfds700_pal_uint_t) new_key > (lfds700_pal_uint_t) existing_key )
 282     cr = 1;
 283
 284   return( cr );
 285 }
 286
 287 #pragma warning( default : 4100 )
 288
 289
 290
 291
 292
 293 /****************************************************************************/
 294 #pragma warning( disable : 4100 )
 295
 296 static void key_hash_function( void const *key, lfds700_pal_uint_t *hash )
 297 {
 298   // TRD : key can be NULL
 299   assert( hash != NULL );
 300
 301   *hash = 0;
 302
 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
 306   */
 307
 308   LFDS700_HASH_A_32BIT_HASH_FUNCTION( (void *) &key, sizeof(lfds700_pal_uint_t), *hash );
 309
 310   return;
 311 }
 312
 313 #pragma warning( default : 4100 )
 314