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

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