pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/test/src/test_slist.c

   1 #include "internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 void test_lfds610_slist( void )
   9 {
  10   printf( "\n"
  11           "SList Tests\n"
  12           "===========\n" );
  13
  14   test_slist_new_delete_get();
  15   test_slist_get_set_user_data();
  16   test_slist_delete_all_elements();
  17
  18   return;
  19 }
  20
  21
  22
  23
  24
  25 /****************************************************************************/
  26 void test_slist_new_delete_get( void )
  27 {
  28   unsigned int
  29     loop,
  30     cpu_count;
  31
  32   struct lfds610_slist_state
  33     *ss;
  34
  35   struct lfds610_slist_element
  36     *se = NULL;
  37
  38   struct slist_test_state
  39     *sts;
  40
  41   thread_state_t
  42     *thread_handles;
  43
  44   size_t
  45     total_create_count = 0,
  46     total_delete_count = 0,
  47     element_count = 0;
  48
  49   enum lfds610_data_structure_validity
  50     dvs = LFDS610_VALIDITY_VALID;
  51
  52   /* TRD : two threads per CPU
  53            first simply alternates between new_head() and new_next() (next on element created by head)
  54            second calls get_next, if NULL, then calls get_head, and deletes the element
  55            both threads keep count of created and deleted
  56            validate is to reconcile created, deleted and remaining in list
  57   */
  58
  59   internal_display_test_name( "New head/next, delete and get next" );
  60
  61   cpu_count = abstraction_cpu_count();
  62
  63   lfds610_slist_new( &ss, NULL, NULL );
  64
  65   sts = malloc( sizeof(struct slist_test_state) * cpu_count * 2 );
  66
  67   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
  68   {
  69     (sts+loop)->ss = ss;
  70     (sts+loop)->create_count = 0;
  71     (sts+loop)->delete_count = 0;
  72   }
  73
  74   thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
  75
  76   for( loop = 0 ; loop < cpu_count ; loop++ )
  77   {
  78     abstraction_thread_start( &thread_handles[loop], loop, slist_test_internal_thread_new_delete_get_new_head_and_next, sts+loop );
  79     abstraction_thread_start( &thread_handles[loop+cpu_count], loop, slist_test_internal_thread_new_delete_get_delete_and_get, sts+loop+cpu_count );
  80   }
  81
  82   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
  83     abstraction_thread_wait( thread_handles[loop] );
  84
  85   free( thread_handles );
  86
  87   // TRD : now validate
  88   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
  89   {
  90     total_create_count += (sts+loop)->create_count;
  91     total_delete_count += (sts+loop)->delete_count;
  92   }
  93
  94   while( NULL != lfds610_slist_get_head_and_then_next(ss, &se) )
  95     element_count++;
  96
  97   if( total_create_count - total_delete_count - element_count != 0 )
  98     dvs = LFDS610_VALIDITY_INVALID_TEST_DATA;
  99
 100   free( sts );
 101
 102   lfds610_slist_delete( ss );
 103
 104   internal_display_test_result( 1, "slist", dvs );
 105
 106   return;
 107 }
 108
 109
 110
 111
 112
 113 /****************************************************************************/
 114 thread_return_t CALLING_CONVENTION slist_test_internal_thread_new_delete_get_new_head_and_next( void *slist_test_state )
 115 {
 116   struct slist_test_state
 117     *sts;
 118
 119   time_t
 120     start_time;
 121
 122   struct lfds610_slist_element
 123     *se = NULL;
 124
 125   assert( slist_test_state != NULL );
 126
 127   sts = (struct slist_test_state *) slist_test_state;
 128
 129   lfds610_slist_use( sts->ss );
 130
 131   time( &start_time );
 132
 133   while( time(NULL) < start_time + 1 )
 134   {
 135     if( sts->create_count % 2 == 0 )
 136       se = lfds610_slist_new_head( sts->ss, NULL );
 137     else
 138       lfds610_slist_new_next( se, NULL );
 139
 140     sts->create_count++;
 141   }
 142
 143   return( (thread_return_t) EXIT_SUCCESS );
 144 }
 145
 146
 147
 148
 149
 150 /****************************************************************************/
 151 thread_return_t CALLING_CONVENTION slist_test_internal_thread_new_delete_get_delete_and_get( void *slist_test_state )
 152 {
 153   struct slist_test_state
 154     *sts;
 155
 156   time_t
 157     start_time;
 158
 159   struct lfds610_slist_element
 160     *se = NULL;
 161
 162   assert( slist_test_state != NULL );
 163
 164   sts = (struct slist_test_state *) slist_test_state;
 165
 166   lfds610_slist_use( sts->ss );
 167
 168   time( &start_time );
 169
 170   while( time(NULL) < start_time + 1 )
 171   {
 172     if( se == NULL )
 173       lfds610_slist_get_head( sts->ss, &se );
 174     else
 175       lfds610_slist_get_next( se, &se );
 176
 177     if( se != NULL )
 178     {
 179       if( 1 == lfds610_slist_logically_delete_element(sts->ss, se) )
 180         sts->delete_count++;
 181     }
 182   }
 183
 184   return( (thread_return_t) EXIT_SUCCESS );
 185 }
 186
 187
 188
 189
 190
 191 /****************************************************************************/
 192 void test_slist_get_set_user_data( void )
 193 {
 194   unsigned int
 195     loop,
 196     cpu_count;
 197
 198   struct lfds610_slist_state
 199     *ss;
 200
 201   struct lfds610_slist_element
 202     *se = NULL;
 203
 204   struct slist_test_state
 205     *sts;
 206
 207   thread_state_t
 208     *thread_handles;
 209
 210   lfds610_atom_t
 211     thread_and_count,
 212     thread,
 213     count,
 214     *per_thread_counters,
 215     *per_thread_drop_flags;
 216
 217   enum lfds610_data_structure_validity
 218     dvs = LFDS610_VALIDITY_VALID;
 219
 220   /* TRD : create a list of (cpu_count*10) elements, user data 0
 221            one thread per CPU
 222            each thread loops, setting user_data to ((thread_number << (sizeof(lfds610_atom_t)*8-8)) | count)
 223            validation is to scan list, count on a per thread basis should go down only once
 224   */
 225
 226   internal_display_test_name( "Get and set user data" );
 227
 228   cpu_count = abstraction_cpu_count();
 229
 230   lfds610_slist_new( &ss, NULL, NULL );
 231
 232   for( loop = 0 ; loop < cpu_count * 10 ; loop++ )
 233     lfds610_slist_new_head( ss, NULL );
 234
 235   sts = malloc( sizeof(struct slist_test_state) * cpu_count );
 236
 237   for( loop = 0 ; loop < cpu_count ; loop++ )
 238   {
 239     (sts+loop)->ss = ss;
 240     (sts+loop)->thread_and_count = (lfds610_atom_t) loop << (sizeof(lfds610_atom_t)*8-8);
 241   }
 242
 243   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
 244
 245   for( loop = 0 ; loop < cpu_count ; loop++ )
 246     abstraction_thread_start( &thread_handles[loop], loop, slist_test_internal_thread_get_set_user_data, sts+loop );
 247
 248   for( loop = 0 ; loop < cpu_count ; loop++ )
 249     abstraction_thread_wait( thread_handles[loop] );
 250
 251   free( thread_handles );
 252
 253   // now validate
 254   per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
 255   per_thread_drop_flags = malloc( sizeof(lfds610_atom_t) * cpu_count );
 256
 257   for( loop = 0 ; loop < cpu_count ; loop++ )
 258   {
 259     *(per_thread_counters+loop) = 0;
 260     *(per_thread_drop_flags+loop) = 0;
 261   }
 262
 263   while( dvs == LFDS610_VALIDITY_VALID and NULL != lfds610_slist_get_head_and_then_next(ss, &se) )
 264   {
 265     lfds610_slist_get_user_data_from_element( se, (void **) &thread_and_count );
 266
 267     thread = thread_and_count >> (sizeof(lfds610_atom_t)*8-8);
 268     count = (thread_and_count << 8) >> 8;
 269
 270     if( thread >= cpu_count )
 271     {
 272       dvs = LFDS610_VALIDITY_INVALID_TEST_DATA;
 273       break;
 274     }
 275
 276     if( per_thread_counters[thread] == 0 )
 277     {
 278       per_thread_counters[thread] = count;
 279       continue;
 280     }
 281
 282     per_thread_counters[thread]++;
 283
 284     if( count < per_thread_counters[thread] and per_thread_drop_flags[thread] == 1 )
 285     {
 286       dvs = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 287       break;
 288     }
 289
 290     if( count < per_thread_counters[thread] and per_thread_drop_flags[thread] == 0 )
 291     {
 292       per_thread_drop_flags[thread] = 1;
 293       per_thread_counters[thread] = count;
 294       continue;
 295     }
 296
 297     if( count < per_thread_counters[thread] )
 298       dvs = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 299
 300     if( count >= per_thread_counters[thread] )
 301       per_thread_counters[thread] = count;
 302   }
 303
 304   free( per_thread_drop_flags );
 305   free( per_thread_counters );
 306
 307   free( sts );
 308
 309   lfds610_slist_delete( ss );
 310
 311   internal_display_test_result( 1, "slist", dvs );
 312
 313   return;
 314 }
 315
 316
 317
 318
 319
 320 /****************************************************************************/
 321 thread_return_t CALLING_CONVENTION slist_test_internal_thread_get_set_user_data( void *slist_test_state )
 322 {
 323   struct slist_test_state
 324     *sts;
 325
 326   time_t
 327     start_time;
 328
 329   struct lfds610_slist_element
 330     *se = NULL;
 331
 332   assert( slist_test_state != NULL );
 333
 334   sts = (struct slist_test_state *) slist_test_state;
 335
 336   lfds610_slist_use( sts->ss );
 337
 338   time( &start_time );
 339
 340   while( time(NULL) < start_time + 1 )
 341   {
 342     if( se == NULL )
 343       lfds610_slist_get_head( sts->ss, &se );
 344
 345     lfds610_slist_set_user_data_in_element( se, (void *) sts->thread_and_count++ );
 346
 347     lfds610_slist_get_next( se, &se );
 348   }
 349
 350   return( (thread_return_t) EXIT_SUCCESS );
 351 }
 352
 353
 354
 355
 356
 357 /****************************************************************************/
 358 void test_slist_delete_all_elements( void )
 359 {
 360   struct lfds610_slist_state
 361     *ss;
 362
 363   struct lfds610_slist_element
 364     *se = NULL;
 365
 366   size_t
 367     element_count = 0;
 368
 369   unsigned int
 370     loop;
 371
 372   enum lfds610_data_structure_validity
 373     dvs = LFDS610_VALIDITY_VALID;
 374
 375   /* TRD : this test creates a list of 100,000 elements
 376            then simply calls delete_all_elements()
 377            we then count the number of elements remaining
 378            should be zero :-)
 379   */
 380
 381   internal_display_test_name( "Delete all elements" );
 382
 383   lfds610_slist_new( &ss, NULL, NULL );
 384
 385   for( loop = 0 ; loop < 1000000 ; loop++ )
 386     lfds610_slist_new_head( ss, NULL );
 387
 388   lfds610_slist_single_threaded_physically_delete_all_elements( ss );
 389
 390   while( NULL != lfds610_slist_get_head_and_then_next(ss, &se) )
 391     element_count++;
 392
 393   if( element_count != 0 )
 394     dvs = LFDS610_VALIDITY_INVALID_TEST_DATA;
 395
 396   lfds610_slist_delete( ss );
 397
 398   internal_display_test_result( 1, "slist", dvs );
 399
 400   return;
 401 }
 402