]> pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/test/src/test_queue.c
Initial import (all versions, including the new 7.1.0)
[liblfds] / liblfds / liblfds6.1.0 / test / src / test_queue.c
1 #include "internal.h"
2
3
4
5
6
7 /****************************************************************************/
8 void test_lfds610_queue( void )
9 {
10   printf( "\n"
11           "Queue Tests\n"
12           "===========\n" );
13
14   queue_test_enqueuing();
15   queue_test_dequeuing();
16   queue_test_enqueuing_and_dequeuing();
17   queue_test_rapid_enqueuing_and_dequeuing();
18
19   return;
20 }
21
22
23
24
25
26 /****************************************************************************/
27 void queue_test_enqueuing( void )
28 {
29   unsigned int
30     loop,
31     cpu_count;
32
33   thread_state_t
34     *thread_handles;
35
36   struct lfds610_queue_state
37     *qs;
38
39   struct queue_test_enqueuing_state
40     *qtes;
41
42   lfds610_atom_t
43     user_data,
44     thread,
45     count,
46     *per_thread_counters;
47
48   struct lfds610_validation_info
49     vi = { 1000000, 1000000 };
50
51   enum lfds610_data_structure_validity
52     dvs[2];
53
54   /* TRD : create an empty queue with 1,000,000 elements in its freelist
55            then run one thread per CPU
56            where each thread busy-works, enqueuing elements (until there are no more elements)
57            each element's void pointer of user data is (thread number | element number)
58            where element_number is a thread-local counter starting at 0
59            where the thread_number occupies the top byte
60
61            when we're done, we check that all the elements are present
62            and increment on a per-thread basis
63   */
64
65   internal_display_test_name( "Enqueuing" );
66
67   cpu_count = abstraction_cpu_count();
68
69   lfds610_queue_new( &qs, 1000000 );
70
71   qtes = malloc( sizeof(struct queue_test_enqueuing_state) * cpu_count );
72
73   for( loop = 0 ; loop < cpu_count ; loop++ )
74   {
75     (qtes+loop)->qs = qs;
76     (qtes+loop)->counter = (lfds610_atom_t) loop << (sizeof(lfds610_atom_t)*8-8);
77   }
78
79   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
80
81   for( loop = 0 ; loop < cpu_count ; loop++ )
82     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_enqueuer, qtes+loop );
83
84   for( loop = 0 ; loop < cpu_count ; loop++ )
85     abstraction_thread_wait( thread_handles[loop] );
86
87   free( thread_handles );
88
89   free( qtes );
90
91   /* TRD : first, validate the queue
92
93            then dequeue
94            we expect to find element numbers increment on a per thread basis
95   */
96
97   lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, &vi, dvs );
98
99   per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
100
101   for( loop = 0 ; loop < cpu_count ; loop++ )
102     *(per_thread_counters+loop) = 0;
103
104   while( dvs[0] == LFDS610_VALIDITY_VALID and dvs[1] == LFDS610_VALIDITY_VALID and lfds610_queue_dequeue(qs, (void *) &user_data) )
105   {
106     thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
107     count = (user_data << 8) >> 8;
108
109     if( thread >= cpu_count )
110     {
111       dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
112       break;
113     }
114
115     if( count < per_thread_counters[thread] )
116       dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
117
118     if( count > per_thread_counters[thread] )
119       dvs[0] = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
120
121     if( count == per_thread_counters[thread] )
122       per_thread_counters[thread]++;
123   }
124
125   free( per_thread_counters );
126
127   lfds610_queue_delete( qs, NULL, NULL );
128
129   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
130
131   return;
132 }
133
134
135
136
137
138 /****************************************************************************/
139 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_enqueuer( void *queue_test_enqueuing_state )
140 {
141   struct queue_test_enqueuing_state
142     *qtes;
143
144   assert( queue_test_enqueuing_state != NULL );
145
146   qtes = (struct queue_test_enqueuing_state *) queue_test_enqueuing_state;
147
148   lfds610_queue_use( qtes->qs );
149
150   // TRD : top byte of counter is already our thread number
151   while( lfds610_queue_enqueue(qtes->qs, (void *) qtes->counter++) );
152
153   return( (thread_return_t) EXIT_SUCCESS );
154 }
155
156
157
158
159
160 /****************************************************************************/
161 void queue_test_dequeuing( void )
162 {
163   unsigned int
164     loop,
165     cpu_count;
166
167   thread_state_t
168     *thread_handles;
169
170   struct lfds610_queue_state
171     *qs;
172
173   struct queue_test_dequeuing_state
174     *qtds;
175
176   struct lfds610_validation_info
177     vi = { 0, 0 };
178
179   enum lfds610_data_structure_validity
180     dvs[2];
181
182   /* TRD : create a queue with 1,000,000 elements
183
184            use a single thread to enqueue every element
185            each elements user data is an incrementing counter
186
187            then run one thread per CPU
188            where each busy-works dequeuing
189
190            when an element is dequeued, we check (on a per-thread basis) the
191            value deqeued is greater than the element previously dequeued
192   */
193
194   internal_display_test_name( "Dequeuing" );
195
196   cpu_count = abstraction_cpu_count();
197
198   lfds610_queue_new( &qs, 1000000 );
199
200   for( loop = 0 ; loop < 1000000 ; loop++ )
201     lfds610_queue_enqueue( qs, (void *) (lfds610_atom_t) loop );
202
203   qtds = malloc( sizeof(struct queue_test_dequeuing_state) * cpu_count );
204
205   for( loop = 0 ; loop < cpu_count ; loop++ )
206   {
207     (qtds+loop)->qs = qs;
208     (qtds+loop)->error_flag = LOWERED;
209   }
210
211   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
212
213   for( loop = 0 ; loop < cpu_count ; loop++ )
214     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_dequeuer, qtds+loop );
215
216   for( loop = 0 ; loop < cpu_count ; loop++ )
217     abstraction_thread_wait( thread_handles[loop] );
218
219   free( thread_handles );
220
221   // TRD : check queue is empty
222   lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
223
224   // TRD : check for raised error flags
225   for( loop = 0 ; loop < cpu_count ; loop++ )
226     if( (qtds+loop)->error_flag == RAISED )
227       dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
228
229   free( qtds );
230
231   lfds610_queue_delete( qs, NULL, NULL );
232
233   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
234
235   return;
236 }
237
238
239
240
241
242 /****************************************************************************/
243 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_dequeuer( void *queue_test_dequeuing_state )
244 {
245   struct queue_test_dequeuing_state
246     *qtds;
247
248   lfds610_atom_t
249     *prev_user_data,
250     *user_data;
251
252   assert( queue_test_dequeuing_state != NULL );
253
254   qtds = (struct queue_test_dequeuing_state *) queue_test_dequeuing_state;
255
256   lfds610_queue_use( qtds->qs );
257
258   lfds610_queue_dequeue( qtds->qs, (void *) &prev_user_data );
259
260   while( lfds610_queue_dequeue(qtds->qs, (void *) &user_data) )
261   {
262     if( user_data <= prev_user_data )
263       qtds->error_flag = RAISED;
264
265     prev_user_data = user_data;
266   }
267
268   return( (thread_return_t) EXIT_SUCCESS );
269 }
270
271
272
273
274
275 /****************************************************************************/
276 void queue_test_enqueuing_and_dequeuing( void )
277 {
278   unsigned int
279     loop,
280     subloop,
281     cpu_count;
282
283   thread_state_t
284     *thread_handles;
285
286   struct lfds610_queue_state
287     *qs;
288
289   struct queue_test_enqueuing_and_dequeuing_state
290     *qteds;
291
292   struct lfds610_validation_info
293     vi = { 0, 0 };
294
295   enum lfds610_data_structure_validity
296     dvs[2];
297
298   internal_display_test_name( "Enqueuing and dequeuing (10 seconds)" );
299
300   cpu_count = abstraction_cpu_count();
301
302   lfds610_queue_new( &qs, cpu_count );
303
304   qteds = malloc( sizeof(struct queue_test_enqueuing_and_dequeuing_state) * cpu_count );
305
306   for( loop = 0 ; loop < cpu_count ; loop++ )
307   {
308     (qteds+loop)->qs = qs;
309     (qteds+loop)->thread_number = loop;
310     (qteds+loop)->counter = (lfds610_atom_t) loop << (sizeof(lfds610_atom_t)*8-8);
311     (qteds+loop)->cpu_count = cpu_count;
312     (qteds+loop)->error_flag = LOWERED;
313     (qteds+loop)->per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
314
315     for( subloop = 0 ; subloop < cpu_count ; subloop++ )
316       *((qteds+loop)->per_thread_counters+subloop) = 0;
317   }
318
319   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
320
321   for( loop = 0 ; loop < cpu_count ; loop++ )
322     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_enqueuer_and_dequeuer, qteds+loop );
323
324   for( loop = 0 ; loop < cpu_count ; loop++ )
325     abstraction_thread_wait( thread_handles[loop] );
326
327   free( thread_handles );
328
329   lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
330
331   for( loop = 0 ; loop < cpu_count ; loop++ )
332     if( (qteds+loop)->error_flag == RAISED )
333       dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
334
335   for( loop = 0 ; loop < cpu_count ; loop++ )
336     free( (qteds+loop)->per_thread_counters );
337
338   free( qteds );
339
340   lfds610_queue_delete( qs, NULL, NULL );
341
342   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
343
344   return;
345 }
346
347
348
349
350
351 /****************************************************************************/
352 thread_return_t CALLING_CONVENTION queue_test_internal_thread_enqueuer_and_dequeuer( void *queue_test_enqueuing_and_dequeuing_state )
353 {
354   struct queue_test_enqueuing_and_dequeuing_state
355     *qteds;
356
357   time_t
358     start_time;
359
360   lfds610_atom_t
361     thread,
362     count,
363     user_data;
364
365   assert( queue_test_enqueuing_and_dequeuing_state != NULL );
366
367   qteds = (struct queue_test_enqueuing_and_dequeuing_state *) queue_test_enqueuing_and_dequeuing_state;
368
369   lfds610_queue_use( qteds->qs );
370
371   time( &start_time );
372
373   while( time(NULL) < start_time + 10 )
374   {
375     lfds610_queue_enqueue( qteds->qs, (void *) (qteds->counter++) );
376     lfds610_queue_dequeue( qteds->qs, (void *) &user_data );
377
378     thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
379     count = (user_data << 8) >> 8;
380
381     if( thread >= qteds->cpu_count )
382       qteds->error_flag = RAISED;
383     else
384     {
385       if( count < qteds->per_thread_counters[thread] )
386         qteds->error_flag = RAISED;
387
388       if( count >= qteds->per_thread_counters[thread] )
389         qteds->per_thread_counters[thread] = count+1;
390     }
391   }
392
393   return( (thread_return_t) EXIT_SUCCESS );
394 }
395
396
397
398
399
400 /****************************************************************************/
401 void queue_test_rapid_enqueuing_and_dequeuing( void )
402 {
403   unsigned int
404     loop,
405     cpu_count;
406
407   thread_state_t
408     *thread_handles;
409
410   struct lfds610_queue_state
411     *qs;
412
413   struct queue_test_rapid_enqueuing_and_dequeuing_state
414     *qtreds;
415
416   struct lfds610_validation_info
417     vi = { 50000, 50000 };
418
419   lfds610_atom_t
420     user_data,
421     thread,
422     count,
423     *per_thread_counters;
424
425   enum lfds610_data_structure_validity
426     dvs[2];
427
428   internal_display_test_name( "Rapid enqueuing and dequeuing (10 seconds)" );
429
430   cpu_count = abstraction_cpu_count();
431
432   lfds610_queue_new( &qs, 100000 );
433
434   for( loop = 0 ; loop < 50000 ; loop++ )
435     lfds610_queue_enqueue( qs, NULL );
436
437   qtreds = malloc( sizeof(struct queue_test_rapid_enqueuing_and_dequeuing_state) * cpu_count );
438
439   for( loop = 0 ; loop < cpu_count ; loop++ )
440   {
441     (qtreds+loop)->qs = qs;
442     (qtreds+loop)->counter = (lfds610_atom_t) loop << (sizeof(lfds610_atom_t)*8-8);
443   }
444
445   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
446
447   for( loop = 0 ; loop < cpu_count ; loop++ )
448     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_rapid_enqueuer_and_dequeuer, qtreds+loop );
449
450   for( loop = 0 ; loop < cpu_count ; loop++ )
451     abstraction_thread_wait( thread_handles[loop] );
452
453   free( thread_handles );
454
455   lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
456
457   // TRD : now check results
458   per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
459
460   for( loop = 0 ; loop < cpu_count ; loop++ )
461     *(per_thread_counters+loop) = 0;
462
463   while( dvs[0] == LFDS610_VALIDITY_VALID and dvs[1] == LFDS610_VALIDITY_VALID and lfds610_queue_dequeue(qs, (void *) &user_data) )
464   {
465     thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
466     count = (user_data << 8) >> 8;
467
468     if( thread >= cpu_count )
469     {
470       dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
471       break;
472     }
473
474     if( per_thread_counters[thread] == 0 )
475       per_thread_counters[thread] = count;
476
477     if( count < per_thread_counters[thread] )
478       dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
479
480     if( count >= per_thread_counters[thread] )
481       per_thread_counters[thread] = count+1;
482   }
483
484   free( per_thread_counters );
485
486   free( qtreds );
487
488   lfds610_queue_delete( qs, NULL, NULL );
489
490   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
491
492   return;
493 }
494
495
496
497
498
499 /****************************************************************************/
500 thread_return_t CALLING_CONVENTION queue_test_internal_thread_rapid_enqueuer_and_dequeuer( void *queue_test_rapid_enqueuing_and_dequeuing_state )
501 {
502   struct queue_test_rapid_enqueuing_and_dequeuing_state
503     *qtreds;
504
505   time_t
506     start_time;
507
508   lfds610_atom_t
509     user_data;
510
511   assert( queue_test_rapid_enqueuing_and_dequeuing_state != NULL );
512
513   qtreds = (struct queue_test_rapid_enqueuing_and_dequeuing_state *) queue_test_rapid_enqueuing_and_dequeuing_state;
514
515   lfds610_queue_use( qtreds->qs );
516
517   time( &start_time );
518
519   while( time(NULL) < start_time + 10 )
520   {
521     lfds610_queue_enqueue( qtreds->qs, (void *) (qtreds->counter++) );
522     lfds610_queue_dequeue( qtreds->qs, (void *) &user_data );
523   }
524
525   return( (thread_return_t) EXIT_SUCCESS );
526 }
527