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

   1 /***** includes *****/
   2 #include "internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds700_list_aos_element
   8     laose;
   9
  10   lfds700_pal_uint_t
  11     element_number,
  12     thread_number;
  13 };
  14
  15 struct test_state
  16 {
  17   lfds700_pal_uint_t
  18     number_elements_per_thread;
  19
  20   struct lfds700_list_aos_state
  21     *laoss;
  22
  23   struct test_element
  24     *element_array;
  25 };
  26
  27 /***** private prototypes *****/
  28 static int new_ordered_compare_function( void const *value_new, void const *value_in_list );
  29 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_thread( void *util_thread_starter_thread_state );
  30
  31
  32
  33
  34
  35 /****************************************************************************/
  36 void test_lfds700_list_aos_new_ordered( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
  37 {
  38   enum lfds700_misc_validity
  39     dvs = LFDS700_MISC_VALIDITY_VALID;
  40
  41   lfds700_pal_uint_t
  42     loop,
  43     expected_element_number,
  44     number_elements_per_thread,
  45     number_elements_total,
  46     number_logical_processors,
  47     offset,
  48     temp;
  49
  50   struct lfds700_list_aos_element
  51     *laose = NULL;
  52
  53   struct lfds700_list_asu_element
  54     *lasue = NULL;
  55
  56   struct lfds700_list_aos_state
  57     laoss;
  58
  59   struct lfds700_misc_prng_state
  60     ps;
  61
  62   struct lfds700_misc_validation_info
  63     vi;
  64
  65   struct test_pal_logical_processor
  66     *lp;
  67
  68   struct test_element
  69     *element_array,
  70     *element;
  71
  72   struct test_state
  73     *ts;
  74
  75   struct util_thread_starter_state
  76     *tts;
  77
  78   test_pal_thread_state_t
  79     *thread_handles;
  80
  81   assert( list_of_logical_processors != NULL );
  82   // TRD : memory_in_megabytes can be any value in its range
  83
  84   /* TRD : run one thread per logical processor
  85            we have a single array of 10k elements per thread
  86            this is set to be randomly ordered (but with contigious numbers from 0 to n)
  87            we give 10k to each thread (a pointer into the array at the correct point)
  88            which then loops through that array
  89            calling lfds700_list_aos_insert_element_by_position( LFDS700_LIST_AOS_POSITION_ORDERED )
  90            verification should show list is sorted
  91   */
  92
  93   internal_display_test_name( "New ordered" );
  94
  95   lfds700_misc_prng_init( &ps );
  96
  97   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
  98
  99   lfds700_list_aos_init_valid_on_current_logical_core( &laoss, new_ordered_compare_function, LFDS700_LIST_AOS_INSERT_RESULT_FAILURE_EXISTING_KEY, NULL );
 100
 101   /* TRD : create randomly ordered number array with unique elements
 102
 103            unique isn't necessary - the list will sort anyway - but
 104            it permits slightly better validation
 105   */
 106
 107   number_elements_per_thread = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
 108
 109   // TRD : or the test takes a looooooong time...
 110   if( number_elements_per_thread > 10000 )
 111     number_elements_per_thread = 10000;
 112
 113   number_elements_total = number_elements_per_thread * number_logical_processors;
 114
 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     (element_array+loop)->element_number = loop;
 119
 120   for( loop = 0 ; loop < number_elements_total ; loop++ )
 121   {
 122     offset = LFDS700_MISC_PRNG_GENERATE( &ps );
 123     offset %= number_elements_total;
 124     temp = (element_array + offset)->element_number;
 125     (element_array + offset)->element_number = (element_array + loop)->element_number;
 126     (element_array + loop)->element_number = temp;
 127   }
 128
 129   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
 130
 131   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 132   {
 133     (ts+loop)->laoss = &laoss;
 134     (ts+loop)->element_array = element_array + (loop*number_elements_per_thread);
 135     (ts+loop)->number_elements_per_thread = number_elements_per_thread;
 136   }
 137
 138   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
 139
 140   util_thread_starter_new( &tts, number_logical_processors );
 141
 142   LFDS700_MISC_BARRIER_STORE;
 143
 144   lfds700_misc_force_store();
 145
 146   loop = 0;
 147
 148   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 149   {
 150     lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 151     util_thread_starter_start( tts, &thread_handles[loop], loop, lp, new_ordered_thread, ts+loop );
 152     loop++;
 153   }
 154
 155   util_thread_starter_run( tts );
 156
 157   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 158     test_pal_thread_wait( thread_handles[loop] );
 159
 160   util_thread_starter_delete( tts );
 161
 162   free( thread_handles );
 163
 164   free( ts );
 165
 166   /* TRD : validate the resultant list
 167            iterate over the list
 168            we expect to find the list is sorted,
 169            which means that element_number will
 170            increment from zero
 171   */
 172
 173   LFDS700_MISC_BARRIER_LOAD;
 174
 175   vi.min_elements = vi.max_elements = number_elements_total;
 176
 177   lfds700_list_aos_query( &laoss, LFDS700_LIST_AOS_QUERY_SINGLETHREADED_VALIDATE, &vi, &dvs );
 178
 179   if( dvs == LFDS700_MISC_VALIDITY_VALID )
 180   {
 181     expected_element_number = 0;
 182
 183     // TRD : traverse the list and check combined_data_array matches
 184     while( dvs == LFDS700_MISC_VALIDITY_VALID and LFDS700_LIST_AOS_GET_START_AND_THEN_NEXT(laoss, laose) )
 185     {
 186       element = LFDS700_LIST_AOS_GET_VALUE_FROM_ELEMENT( *laose );
 187
 188       if( element->element_number != expected_element_number++ )
 189         dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 190     }
 191   }
 192
 193   lfds700_list_aos_cleanup( &laoss, NULL );
 194
 195   util_aligned_free( element_array );
 196
 197   internal_display_test_result( 1, "list_aos", dvs );
 198
 199   return;
 200 }
 201
 202
 203
 204
 205
 206 /****************************************************************************/
 207 #pragma warning( disable : 4100 )
 208
 209 static int new_ordered_compare_function( void const *value_new, void const *value_in_list )
 210 {
 211   int
 212     cr = 0;
 213
 214   struct test_element
 215     *e1,
 216     *e2;
 217
 218   // TRD : value_new can be any value in its range
 219   // TRD : value_in_list can be any value in its range
 220
 221   e1 = (struct test_element *) value_new;
 222   e2 = (struct test_element *) value_in_list;
 223
 224   if( e1->element_number < e2->element_number )
 225     cr = -1;
 226
 227   if( e1->element_number > e2->element_number )
 228     cr = 1;
 229
 230   return( cr );
 231 }
 232
 233 #pragma warning( default : 4100 )
 234
 235
 236
 237
 238
 239 /****************************************************************************/
 240 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_thread( void *util_thread_starter_thread_state )
 241 {
 242   lfds700_pal_uint_t
 243     loop;
 244
 245   struct lfds700_misc_prng_state
 246     ps;
 247
 248   struct test_state
 249     *ts;
 250
 251   struct util_thread_starter_thread_state
 252     *tsts;
 253
 254   LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 255
 256   assert( util_thread_starter_thread_state != NULL );
 257
 258   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 259   ts = (struct test_state *) tsts->thread_user_state;
 260
 261   lfds700_misc_prng_init( &ps );
 262
 263   util_thread_starter_ready_and_wait( tsts );
 264
 265   for( loop = 0 ; loop < ts->number_elements_per_thread ; loop++ )
 266   {
 267     LFDS700_LIST_AOS_SET_KEY_IN_ELEMENT( (ts->element_array+loop)->laose, ts->element_array+loop );
 268     LFDS700_LIST_AOS_SET_VALUE_IN_ELEMENT( (ts->element_array+loop)->laose, ts->element_array+loop );
 269     lfds700_list_aos_insert( ts->laoss, &(ts->element_array+loop)->laose, NULL, &ps );
 270   }
 271
 272   LFDS700_MISC_BARRIER_STORE;
 273
 274   lfds700_misc_force_store();
 275
 276   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 277 }
 278