1 // @(#) $Revision: 4.20 $ $Source: /judy/test/manual/Judy1LTime.c $
2 //=======================================================================
3 // This program measures the performance of a Judy1 and JudyL Array.
4 // -by-
5 // Douglas L. Baskins (8/2001) doug@sourcejudy.com
6 //=======================================================================
7
8 #include <unistd.h> // sbrk()
9 #include <stdlib.h> // exit()
10 #include <stdio.h> // printf()
11 #include <math.h> // pow()
12 #include <sys/time.h> // gettimeofday()
13 #include <Judy.h> // for Judy macros J*()
14
15 #ifdef NOINLINE /* this is the 21st century? */
16 #define _INLINE_ static
17 #else
18 #define _INLINE_ inline
19 #endif
20
21
22 //=======================================================================
23 // C O M P I L E D:
24 //=======================================================================
25 //
26 // cc -static -O3 Judy1LTime.c -lJudy -lm
27 //
28 // the -static is for a little better performace on some platforms
29 //
30 // if optional high-resolution timers are desired:
31 //
32 // cc -static -O3 -DJU_LINUX_IA32 Judy1LTime.c -lJudy -lm
33 //
34 // and read below:
35 //
36 //=======================================================================
37 // T I M I N G M A C R O S
38 //=======================================================================
39 // if your machine is one of the supported types in the following header
40 // file then uncomment this corresponding to what the header file says.
41 // This will give very high timing resolution.
42 //
43 // #define JU_xxxxxxx 1 // read timeit.h
44 // #define JU_LINUX_IA32 1 // I.E. IA32 Linux
45 //
46 #include "timeit.h" // optional for high resolution times
47
48 double DeltaUSec; // Global for remembering delta times
49
50 #ifndef _TIMEIT_H
51
52 // Note: I have found some Linux systems (2.4.18-6mdk) have bugs in the
53 // gettimeofday() routine. Sometimes the difference of two consective calls
54 // returns a negative ~2840 microseconds instead of 0 or 1. If you use the
55 // above #include "timeit.h" and compile with timeit.c and use
56 // -DJU_LINUX_IA32, that problem will be eliminated. This is because for
57 // delta times less than .1 sec, the hardware free running timer is used
58 // instead of gettimeofday(). I have found the negative time problem
59 // appears about 40-50 times per second with numerous gettimeofday() calls.
60 // You should just ignore negative times output.
61
62 #define TIMER_vars(T) struct timeval __TVBeg_##T, __TVEnd_##T
63
64 #define STARTTm(T) gettimeofday(&__TVBeg_##T, NULL)
65
66 #define ENDTm(D,T) \
67 { \
68 gettimeofday(&__TVEnd_##T, NULL); \
69 (D) = (double)(__TVEnd_##T.tv_sec - __TVBeg_##T.tv_sec) * 1E6 + \
70 ((double)(__TVEnd_##T.tv_usec - __TVBeg_##T.tv_usec)); \
71 }
72
73 #endif // _TIMEIT_H
74
75 //=======================================================================
76 // M E M O R Y S I Z E M A C R O S
77 //=======================================================================
78 // Most mallocs have mallinfo()
79 // However, the size is an int, so just about worthless in 64 bit
80 // machines with more than 4Gb ram. But needed on 32 bit machines
81 // that have more than a 1Gbyte of memory, because malloc stops
82 // using sbrk() about at that time (runs out of heap -- use mmap()).
83
84 // un-define this if your malloc has mallinfo(); see above
85
86 #define NOMALLINFO 1
87
88 double DeltaMem;
89
90 #ifndef NOMALLINFO
91
92 #include <malloc.h> // mallinfo()
93
94 struct mallinfo malStart;
95
96 #define STARTmem malStart = mallinfo() /* works with some mallocs */
97 #define ENDmem \
98 { \
99 struct mallinfo malEnd = mallinfo(); \
100 /* strange little dance from signed to unsigned to double */ \
101 unsigned int _un_int = malEnd.arena - malStart.arena; \
102 DeltaMem = _un_int; /* to double */ \
103 }
104
105 #else // MALLINFO
106
107 // this usually works for machines with less than 1-2Gb RAM.
108 // (it does not include memory ACQUIRED by mmap())
109
110 char *malStart;
111
112 #define STARTmem (malStart = (char *)sbrk(0))
113 #define ENDmem \
114 { \
115 char *malEnd = (char *)sbrk(0); \
116 DeltaMem = malEnd - malStart; \
117 }
118
119 #endif // MALLINFO
120
121 //=======================================================================
122
123 // Common macro to handle a failure
124 #define FAILURE(STR, UL) \
125 { \
126 printf( "Error: %s %lu, file='%s', 'function='%s', line %d\n", \
127 STR, UL, __FILE__, __FUNCTI0N__, __LINE__); \
128 fprintf(stderr, "Error: %s %lu, file='%s', 'function='%s', line %d\n", \
129 STR, UL, __FILE__, __FUNCTI0N__, __LINE__); \
130 exit(1); \
131 }
132
133 // Interations without improvement
134 // Minimum of 2 loops, maximum of 1000000
135 #define MINLOOPS 2
136 #define MAXLOOPS 1000000
137
138 // Maximum or 10 loops with no improvement
139 #define ICNT 10
140
141 // Structure to keep track of times
142 typedef struct MEASUREMENTS_STRUCT
143 {
144 Word_t ms_delta;
145 }
146 ms_t , *Pms_t;
147
148 // Specify prototypes for each test routine
149 int NextNumb(Word_t *PNumber, double *PDNumb, double DMult,
150 Word_t MaxN);
151
152 Word_t TestJudyIns(void **J1, void **JL, Word_t Seed, Word_t Elems);
153
154 Word_t TestJudyDup(void **J1, void **JL, Word_t Seed, Word_t Elems);
155
156 int TestJudyDel(void **J1, void **JL, Word_t Seed, Word_t Elems);
157
158 Word_t TestJudyGet(void *J1, void *JL, Word_t Seed, Word_t Elems);
159
160 int TestJudyCount(void *J1, void *JL, Word_t LowIndex, Word_t Elems);
161
162 Word_t TestJudyNext(void *J1, void *JL, Word_t LowIndex, Word_t Elems);
163
164 int TestJudyPrev(void *J1, void *JL, Word_t HighIndex, Word_t Elems);
165
166 Word_t TestJudyNextEmpty(void *J1, void *JL, Word_t LowIndex,
167 Word_t Elems);
168
169 Word_t TestJudyPrevEmpty(void *J1, void *JL, Word_t HighIndex,
170 Word_t Elems);
171
172 //=======================================================================
173 // These are LFSF feedback taps for bitwidths of 10..64 sized numbers.
174 // Tested with Seed=0xc1fc to 35 billion numbers
175 //=======================================================================
176
177 Word_t StartSeed = 0xc1fc; // default beginning number
178 Word_t FirstSeed;
179
180 Word_t MagicList[] = {
181 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0..9
182 0x27f, // 10
183 0x27f, // 11
184 0x27f, // 12
185 0x27f, // 13
186 0x27f, // 14
187 0x27f, // 15
188 0x1e71, // 16
189 0xdc0b, // 17
190 0xdc0b, // 18
191 0xdc0b, // 19
192 0xdc0b, // 20
193 0xc4fb, // 21
194 0xc4fb, // 22
195 0xc4fb, // 23
196 0x13aab, // 24
197 0x11ca3, // 25
198 0x11ca3, // 26
199 0x11ca3, // 27
200 0x13aab, // 28
201 0x11ca3, // 29
202 0xc4fb, // 30
203 0xc4fb, // 31
204 0x13aab, // 32
205 0x14e73, // 33
206 0x145d7, // 34
207 0x145f9, // 35 following tested with Seed=0xc1fc to 35 billion numbers
208 0x151ed, // 36 .. 41
209 0x151ed, // 37
210 0x151ed, // 38
211 0x151ed, // 39
212 0x151ed, // 40
213 0x146c3, // 41 .. 64
214 0x146c3, // 42
215 0x146c3, // 43
216 0x146c3, // 44
217 0x146c3, // 45
218 0x146c3, // 46
219 0x146c3, // 47
220 0x146c3, // 48
221 0x146c3, // 49
222 0x146c3, // 50
223 0x146c3, // 51
224 0x146c3, // 52
225 0x146c3, // 53
226 0x146c3, // 54
227 0x146c3, // 55
228 0x146c3, // 56
229 0x146c3, // 57
230 0x146c3, // 58
231 0x146c3, // 59
232 0x146c3, // 60
233 0x146c3, // 61
234 0x146c3, // 62
235 0x146c3, // 63
236 0x146c3 // 64
237 };
238
239 // Routine to "mirror" the input data word
240 static Word_t
Swizzle(Word_t word)241 Swizzle(Word_t word)
242 {
243 // BIT REVERSAL, Ron Gutman in Dr. Dobb's Journal, #316, Sept 2000, pp133-136
244 //
245
246 #ifdef __LP64__
247 word = ((word & 0x00000000ffffffff) << 32) |
248 ((word & 0xffffffff00000000) >> 32);
249 word = ((word & 0x0000ffff0000ffff) << 16) |
250 ((word & 0xffff0000ffff0000) >> 16);
251 word = ((word & 0x00ff00ff00ff00ff) << 8) |
252 ((word & 0xff00ff00ff00ff00) >> 8);
253 word = ((word & 0x0f0f0f0f0f0f0f0f) << 4) |
254 ((word & 0xf0f0f0f0f0f0f0f0) >> 4);
255 word = ((word & 0x3333333333333333) << 2) |
256 ((word & 0xcccccccccccccccc) >> 2);
257 word = ((word & 0x5555555555555555) << 1) |
258 ((word & 0xaaaaaaaaaaaaaaaa) >> 1);
259 #else // not __LP64__
260 word = ((word & 0x0000ffff) << 16) | ((word & 0xffff0000) >> 16);
261 word = ((word & 0x00ff00ff) << 8) | ((word & 0xff00ff00) >> 8);
262 word = ((word & 0x0f0f0f0f) << 4) | ((word & 0xf0f0f0f0) >> 4);
263 word = ((word & 0x33333333) << 2) | ((word & 0xcccccccc) >> 2);
264 word = ((word & 0x55555555) << 1) | ((word & 0xaaaaaaaa) >> 1);
265 #endif // not __LP64__
266
267 return (word);
268 }
269
270 double DeltaUSec1 = 0.0; // Global for measuring delta times
271 double DeltaUSecL = 0.0; // Global for measuring delta times
272
273 Word_t J1Flag = 0; // time Judy1
274 Word_t JLFlag = 0; // time JudyL
275 Word_t dFlag = 0; // time Judy1Unset JudyLDel
276 Word_t vFlag = 0; // time Searching
277 Word_t CFlag = 0; // time Counting
278 Word_t IFlag = 0; // time duplicate inserts/sets
279 Word_t DFlag = 0; // bit reverse the data stream
280 Word_t lFlag = 0; // do not do multi-insert tests
281 Word_t aFlag = 0; // output active memory in array
282 Word_t SkipN = 0; // default == Random skip
283 Word_t TValues = 100000; // Maximum retrieve tests for timing
284 Word_t nElms = 1000000; // Max population of arrays
285 Word_t ErrorFlag = 0;
286 Word_t PtsPdec = 40; // measurement points per decade
287
288 // Stuff for LFSR (pseudo random number generator)
289 Word_t RandomBit = ~0UL / 2 + 1;
290 Word_t BValue = sizeof(Word_t) * 8;
291 Word_t Magic;
292
293 // for error routines -- notice misspelling, name conflicts with some compilers
294 #undef __FUNCTI0N__
295 #define __FUNCTI0N__ "Random"
296
297 _INLINE_ Word_t // so INLINING compilers get to look at it.
Random(Word_t newseed)298 Random(Word_t newseed)
299 {
300 if (newseed & RandomBit)
301 {
302 newseed += newseed;
303 newseed ^= Magic;
304 }
305 else
306 {
307 newseed += newseed;
308 }
309 newseed &= RandomBit * 2 - 1;
310 if (newseed == FirstSeed)
311 FAILURE("LFSR failed", newseed);
312 return (newseed);
313 }
314
315 _INLINE_ Word_t // so INLINING compilers get to look at it.
GetNextIndex(Word_t Index)316 GetNextIndex(Word_t Index)
317 {
318 if (SkipN)
319 Index += SkipN;
320 else
321 Index = Random(Index);
322
323 return (Index);
324 }
325
326 #undef __FUNCTI0N__
327 #define __FUNCTI0N__ "main"
328
329 int
main(int argc,char * argv[])330 main(int argc, char *argv[])
331 {
332 // Names of Judy Arrays
333 void *J1 = NULL; // Judy1
334 void *JL = NULL; // JudyL
335
336 TIMER_vars(tm1); // declare timer variables
337 Word_t Count1, CountL;
338 Word_t Bytes;
339
340 double Mult;
341 Pms_t Pms;
342 Word_t Seed;
343 Word_t PtsPdec = 40; // points per decade
344 Word_t Groups; // Number of measurement groups
345 Word_t grp;
346 Word_t Pop1;
347 Word_t Meas;
348 int Col;
349
350 int c;
351 extern char *optarg;
352
353 //============================================================
354 // PARSE INPUT PARAMETERS
355 //============================================================
356
357 while ((c = getopt(argc, argv, "n:S:T:P:b:B:dDC1LvIla")) != -1)
358 {
359 switch (c)
360 {
361 case 'n': // Max population of arrays
362 nElms = strtoul(optarg, NULL, 0); // Size of Linear Array
363 if (nElms == 0)
364 FAILURE("No tests: -n", nElms);
365
366 // Check if more than a trillion (64 bit only)
367 if ((double)nElms > 1e12)
368 FAILURE("Too many Indexes=", nElms);
369 break;
370
371 case 'S': // Step Size, 0 == Random
372 SkipN = strtoul(optarg, NULL, 0);
373 break;
374
375 case 'T': // Maximum retrieve tests for timing
376 TValues = strtoul(optarg, NULL, 0);
377 break;
378
379 case 'P': // measurement points per decade
380 PtsPdec = strtoul(optarg, NULL, 0);
381 break;
382
383 case 'b': // May not work past 35 bits if changed
384 StartSeed = strtoul(optarg, NULL, 0);
385 break;
386
387 case 'B': // expanse of data points (random only)
388 BValue = strtoul(optarg, NULL, 0);
389 if ((BValue > 64)
390 ||
391 (MagicList[BValue] == 0) || (BValue > (sizeof(Word_t) * 8)))
392 {
393 ErrorFlag++;
394 printf("\nIllegal number of random bits of %lu !!!\n",
395 BValue);
396 }
397 break;
398
399 case 'v':
400 vFlag = 1; // time Searching
401 break;
402
403 case '1': // time Judy1
404 J1Flag = 1;
405 break;
406
407 case 'L': // time JudyL
408 JLFlag = 1;
409 break;
410
411 case 'd': // time Judy1Unset JudyLDel
412 dFlag = 1;
413 break;
414
415 case 'D': // bit reverse the data stream
416 DFlag = 1;
417 break;
418
419 case 'C': // time Counting
420 CFlag = 1;
421 break;
422
423 case 'I': // time duplicate insert/set
424 IFlag = 1;
425 break;
426
427 case 'l': // do not loop in tests
428 lFlag = 1;
429 break;
430
431 case 'a': // output active memory in Judy array
432 aFlag = 1;
433 break;
434
435 default:
436 ErrorFlag++;
437 break;
438 }
439 }
440
441 if (ErrorFlag)
442 {
443 printf("\n%s -n# -P# -S# -B# -T# -b # -DCpdI\n\n", argv[0]);
444 printf("Where:\n");
445 printf("-n <#> number of indexes used in tests\n");
446 printf("-P <#> number measurement points per decade\n");
447 printf("-S <#> index skip amount, 0 = random\n");
448 printf("-B <#> # bits (10..%d) in random number generator\n",
449 (int)sizeof(Word_t) * 8);
450 printf("-L time JudyL\n");
451 printf("-1 time Judy1\n");
452 printf("-I time DUPLICATE Ins/Set times\n");
453 printf("-C time JudyCount tests\n");
454 printf("-v time Judy Search tests\n");
455 printf("-d time JudyDel/Unset instead of JudyFreeArray\n");
456 printf("-l do not loop on same Indexes\n");
457 printf("-T <#> max number indexes in read times - 0 == MAX\n");
458 printf("\n");
459
460 exit(1);
461 }
462
463 // If none, then both
464 if (!JLFlag && !J1Flag)
465 JLFlag = J1Flag = 1;
466
467 // Set number of Random bits in LFSR
468 RandomBit = 1UL << (BValue - 1);
469 Magic = MagicList[BValue];
470
471 if (nElms > ((RandomBit - 2) * 2))
472 {
473 printf
474 ("# Number = -n%lu of Indexes reduced to max expanse of Random numbers\n",
475 nElms);
476 nElms = ((RandomBit - 2) * 2);
477 }
478
479 printf("# TITLE %s -n%lu -S%lu -T%lu -B%lu -P%lu",
480 argv[0], nElms, SkipN, TValues, BValue, PtsPdec);
481 if (J1Flag)
482 printf(" -1");
483 if (JLFlag)
484 printf(" -L");
485 if (DFlag)
486 printf(" -D");
487 if (dFlag)
488 printf(" -d");
489 if (CFlag)
490 printf(" -C");
491 if (IFlag)
492 printf(" -I");
493 if (lFlag)
494 printf(" -l");
495 if (aFlag)
496 printf(" -a");
497 printf("\n");
498
499 if (sizeof(Word_t) == 8)
500 printf("#%s 64 Bit version\n", argv[0]);
501 else if (sizeof(Word_t) == 4)
502 printf("#%s 32 Bit version\n", argv[0]);
503
504 printf("# XLABEL Population\n");
505 printf("# YLABEL Microseconds / Index\n");
506
507 //============================================================
508 // CALCULATE NUMBER OF MEASUREMENT GROUPS
509 //============================================================
510
511 // Calculate Multiplier for number of points per decade
512 Mult = pow(10.0, 1.0 / (double)PtsPdec);
513 {
514 double sum;
515 Word_t numb, prevnumb;
516
517 // Count number of measurements needed (10K max)
518 sum = numb = 1;
519 for (Groups = 2; Groups < 10000; Groups++)
520 {
521 if (NextNumb(&numb, &sum, Mult, nElms)) break;
522 }
523
524 // Get memory for measurements
525 Pms = (Pms_t) calloc(Groups, sizeof(ms_t));
526
527 // Now calculate number of Indexes for each measurement point
528 numb = sum = 1;
529 prevnumb = 0;
530 for (grp = 0; grp < Groups; grp++)
531 {
532 Pms[grp].ms_delta = numb - prevnumb;
533 prevnumb = numb;
534
535 NextNumb(&numb, &sum, Mult, nElms);
536 }
537 } // Groups = number of sizes
538
539 //============================================================
540 // PRINT HEADER TO PERFORMANCE TIMERS
541 //============================================================
542
543 printf("# COLHEAD 1 Population\n");
544 printf("# COLHEAD 2 Measurments\n");
545 printf("# COLHEAD 3 J1S\n");
546 printf("# COLHEAD 4 JLI\n");
547 printf("# COLHEAD 5 J1T\n");
548 printf("# COLHEAD 6 JLG\n");
549
550 Col = 7;
551 if (IFlag)
552 {
553 printf("# COLHEAD %d J1S-dup\n", Col++);
554 printf("# COLHEAD %d JLI-dup\n", Col++);
555 }
556 if (CFlag)
557 {
558 printf("# COLHEAD %d J1C\n", Col++);
559 printf("# COLHEAD %d JLC\n", Col++);
560 }
561 if (vFlag)
562 {
563 printf("# COLHEAD %d J1N\n", Col++);
564 printf("# COLHEAD %d JLN\n", Col++);
565 printf("# COLHEAD %d J1P\n", Col++);
566 printf("# COLHEAD %d JLP\n", Col++);
567 printf("# COLHEAD %d J1NE\n", Col++);
568 printf("# COLHEAD %d JLNE\n", Col++);
569 printf("# COLHEAD %d J1PE\n", Col++);
570 printf("# COLHEAD %d JLPE\n", Col++);
571 }
572 if (dFlag)
573 {
574 printf("# COLHEAD %d J1U\n", Col++);
575 printf("# COLHEAD %d JLD\n", Col++);
576 }
577 printf("# COLHEAD %d J1MU/I\n", Col++);
578 printf("# COLHEAD %d JLMU/I\n", Col++);
579 if (aFlag)
580 {
581 printf("# COLHEAD %d J1MA/I\n", Col++);
582 printf("# COLHEAD %d JLMA/I\n", Col++);
583 }
584 printf("# COLHEAD %d HEAP/I\n", Col++);
585
586 printf("# %s\n", Judy1MallocSizes);
587 printf("# %s\n", JudyLMallocSizes);
588
589 printf("# Pop1 Measmts J1S JLI J1T JLG");
590
591 if (IFlag)
592 printf(" dupJ1S dupJLI");
593
594 if (CFlag)
595 printf(" J1C JLC");
596
597 if (vFlag)
598 printf(" J1N JLN J1P JLP J1NE JLNE J1PE JLPE");
599
600 if (dFlag)
601 printf(" J1U JLD");
602
603 printf(" J1MU/I JLMU/I");
604 if (aFlag)
605 {
606 printf(" J1MA/I JLMA/I");
607 }
608
609 printf(" HEAP/I");
610
611 printf("\n");
612
613 //============================================================
614 // BEGIN TESTS AT EACH GROUP SIZE
615 //============================================================
616
617 // Get the kicker to test the LFSR
618 FirstSeed = Seed = StartSeed & (RandomBit * 2 - 1);
619
620 STARTmem;
621 for (Pop1 = grp = 0; grp < Groups; grp++)
622 {
623 Word_t LowIndex, HighIndex;
624 Word_t Delta;
625 Word_t NewSeed;
626
627 Delta = Pms[grp].ms_delta;
628
629 // Test J1S, JLI
630 NewSeed = TestJudyIns(&J1, &JL, Seed, Delta);
631
632 // Accumulate the Total population of arrays
633 Pop1 += Delta;
634 Meas = Pop1;
635
636 // Only test the maximum of TValues if not zero
637 if (TValues)
638 Meas = (Pop1 < TValues) ? Pop1 : TValues;
639
640 printf("%10lu %9lu", Pop1, Meas);
641 printf(" %6.3f", DeltaUSec1);
642 printf(" %6.3f", DeltaUSecL);
643
644 // Test J1T, JLG
645
646 LowIndex = TestJudyGet(J1, JL, FirstSeed, Meas);
647 printf(" %6.3f", DeltaUSec1);
648 printf(" %6.3f", DeltaUSecL);
649
650 // Test J1T, JLI - duplicates
651
652 if (IFlag)
653 {
654 LowIndex = TestJudyDup(&J1, &JL, FirstSeed, Meas);
655 printf(" %6.3f", DeltaUSec1);
656 printf(" %6.3f", DeltaUSecL);
657 }
658 if (CFlag)
659 {
660 TestJudyCount(J1, JL, LowIndex, Meas);
661 printf(" %6.3f", DeltaUSec1);
662 printf(" %6.3f", DeltaUSecL);
663 }
664 if (vFlag)
665 {
666 // Test J1N, JLN
667 HighIndex = TestJudyNext(J1, JL, LowIndex, Meas);
668 printf(" %6.3f", DeltaUSec1);
669 printf(" %6.3f", DeltaUSecL);
670
671 // Test J1P, JLP
672 TestJudyPrev(J1, JL, HighIndex, Meas);
673 printf(" %6.3f", DeltaUSec1);
674 printf(" %6.3f", DeltaUSecL);
675
676 // Test J1NE, JLNE
677 TestJudyNextEmpty(J1, JL, LowIndex, Meas);
678 printf(" %6.3f", DeltaUSec1);
679 printf(" %6.3f", DeltaUSecL);
680
681 // Test J1PE, JLPE
682 TestJudyPrevEmpty(J1, JL, HighIndex, Meas);
683 printf(" %6.3f", DeltaUSec1);
684 printf(" %6.3f", DeltaUSecL);
685 }
686
687 // Test J1U, JLD
688 if (dFlag)
689 {
690 TestJudyDel(&J1, &JL, FirstSeed, Meas);
691 printf(" %6.3f", DeltaUSec1);
692 printf(" %6.3f", DeltaUSecL);
693
694 // Now put them back
695 TestJudyIns(&J1, &JL, FirstSeed, Meas);
696 }
697
698 // Advance Index number set
699 Seed = NewSeed;
700
701 // Print the number of bytes used per Index
702 printf(" %6.3f", (double)Judy1MemUsed(J1) / (double)Pop1);
703 printf(" %6.3f", (double)JudyLMemUsed(JL) / (double)Pop1);
704 if (aFlag)
705 {
706 printf(" %6.3f", (double)Judy1MemActive(J1) / (double)Pop1);
707 printf(" %6.3f", (double)JudyLMemActive(JL) / (double)Pop1);
708 }
709
710 ENDmem;
711 printf(" %6.3f", DeltaMem / (double)Pop1);
712 printf("\n");
713 fflush(NULL); // assure data gets to file in case malloc fail
714 }
715
716 JLC(CountL, JL, 0, -1); // get the counts
717 J1C(Count1, J1, 0, -1);
718
719 if (JLFlag && J1Flag)
720 {
721 if (CountL != Count1)
722 FAILURE("Judy1/LCount not equal", Count1);
723 }
724
725 if (Count1)
726 {
727 STARTTm(tm1);
728 J1FA(Bytes, J1); // Free the Judy1 Array
729 ENDTm(DeltaUSec1, tm1);
730 DeltaUSec1 /= (double)Count1;
731
732 printf("# Judy1FreeArray: %lu, %0.3f bytes/Index, %0.3f USec/Index\n",
733 Count1, (double)Bytes / (double)Count1, DeltaUSec1);
734 }
735
736 if (CountL)
737 {
738 STARTTm(tm1);
739 JLFA(Bytes, JL); // Free the JudyL Array
740 ENDTm(DeltaUSecL, tm1);
741 DeltaUSecL /= (double)CountL;
742
743 printf("# JudyLFreeArray: %lu, %0.3f bytes/Index, %0.3f USec/Index\n",
744 CountL, (double)Bytes / (double)CountL, DeltaUSecL);
745 }
746 exit(0);
747 }
748
749 #undef __FUNCTI0N__
750 #define __FUNCTI0N__ "TestJudyIns"
751
752 Word_t
TestJudyIns(void ** J1,void ** JL,Word_t Seed,Word_t Elements)753 TestJudyIns(void **J1, void **JL, Word_t Seed, Word_t Elements)
754 {
755 TIMER_vars(tm1); // declare timer variables
756 Word_t TstIndex;
757 Word_t elm;
758 Word_t *PValue;
759 Word_t Seed1 = 0;
760 int Rc;
761
762 double DDel;
763 Word_t icnt;
764 Word_t lp;
765 Word_t Loops;
766
767 if (Elements < 100)
768 Loops = (MAXLOOPS / Elements) + MINLOOPS;
769 else
770 Loops = 1;
771
772 if (lFlag)
773 Loops = 1;
774
775 // Judy1Set timings
776
777 if (J1Flag)
778 {
779 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
780 {
781 if (lp != 0)
782 {
783 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
784 {
785 Seed1 = GetNextIndex(Seed1);
786
787 if (DFlag)
788 TstIndex = Swizzle(Seed1);
789 else
790 TstIndex = Seed1;
791
792 J1U(Rc, *J1, TstIndex);
793 }
794 }
795
796 STARTTm(tm1);
797 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
798 {
799 Seed1 = GetNextIndex(Seed1);
800
801 if (DFlag)
802 TstIndex = Swizzle(Seed1);
803 else
804 TstIndex = Seed1;
805
806 J1S(Rc, *J1, TstIndex);
807 if (Rc == 0)
808 FAILURE("Judy1Set failed - DUP Index at", elm);
809 }
810 ENDTm(DeltaUSec1, tm1);
811
812 if (DDel > DeltaUSec1)
813 {
814 icnt = ICNT;
815 DDel = DeltaUSec1;
816 }
817 else
818 {
819 if (--icnt == 0)
820 break;
821 }
822 }
823 DeltaUSec1 = DDel / (double)Elements;
824 }
825
826 // JudyLIns timings
827
828 if (JLFlag)
829 {
830 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
831 {
832 if (lp != 0)
833 {
834 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
835 {
836 Seed1 = GetNextIndex(Seed1);
837
838 if (DFlag)
839 TstIndex = Swizzle(Seed1);
840 else
841 TstIndex = Seed1;
842
843 JLD(Rc, *JL, TstIndex);
844 }
845 }
846
847 STARTTm(tm1);
848 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
849 {
850 Seed1 = GetNextIndex(Seed1);
851
852 if (DFlag)
853 TstIndex = Swizzle(Seed1);
854 else
855 TstIndex = Seed1;
856
857 JLI(PValue, *JL, TstIndex);
858 if (*PValue == TstIndex)
859 FAILURE("JudyLIns failed - DUP Index", TstIndex);
860
861 *PValue = TstIndex; // save Index in Value
862 }
863 ENDTm(DeltaUSecL, tm1);
864 DeltaUSecL /= Elements;
865
866 if (DDel > DeltaUSecL)
867 {
868 icnt = ICNT;
869 DDel = DeltaUSecL;
870 }
871 else
872 {
873 if (--icnt == 0)
874 break;
875 }
876 }
877 }
878 return (Seed1); // New seed
879 }
880
881 #undef __FUNCTI0N__
882 #define __FUNCTI0N__ "TestJudyDup"
883
884 Word_t
TestJudyDup(void ** J1,void ** JL,Word_t Seed,Word_t Elements)885 TestJudyDup(void **J1, void **JL, Word_t Seed, Word_t Elements)
886 {
887 TIMER_vars(tm1); // declare timer variables
888 Word_t LowIndex = ~0UL;
889 Word_t TstIndex;
890 Word_t elm;
891 Word_t *PValue;
892 Word_t Seed1;
893 int Rc;
894
895 double DDel;
896 Word_t icnt;
897 Word_t lp;
898 Word_t Loops;
899
900 Loops = (MAXLOOPS / Elements) + MINLOOPS;
901
902 if (J1Flag)
903 {
904 LowIndex = ~0UL;
905 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
906 {
907 STARTTm(tm1);
908 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
909 {
910 Seed1 = GetNextIndex(Seed1);
911
912 if (DFlag)
913 TstIndex = Swizzle(Seed1);
914 else
915 TstIndex = Seed1;
916
917 if (TstIndex < LowIndex)
918 LowIndex = TstIndex;
919
920 J1S(Rc, *J1, TstIndex);
921 if (Rc != 0)
922 FAILURE("Judy1Test Rc != 0", (Word_t)Rc);
923 }
924 ENDTm(DeltaUSec1, tm1);
925
926 if (DDel > DeltaUSec1)
927 {
928 icnt = ICNT;
929 DDel = DeltaUSec1;
930 }
931 else
932 {
933 if (--icnt == 0)
934 break;
935 }
936 }
937 DeltaUSec1 = DDel / (double)Elements;
938 }
939
940 icnt = ICNT;
941
942 if (JLFlag)
943 {
944 LowIndex = ~0UL;
945 for (DDel = 1e40, lp = 0; lp < Loops; lp++)
946 {
947 STARTTm(tm1);
948 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
949 {
950 Seed1 = GetNextIndex(Seed1);
951
952 if (DFlag)
953 TstIndex = Swizzle(Seed1);
954 else
955 TstIndex = Seed1;
956
957 if (TstIndex < LowIndex)
958 LowIndex = TstIndex;
959
960 JLI(PValue, *JL, TstIndex);
961 if (PValue == (Word_t *)NULL)
962 FAILURE("JudyLGet ret PValue = NULL", 0L);
963 if (*PValue != TstIndex)
964 FAILURE("JudyLGet ret wrong Value at", elm);
965 }
966 ENDTm(DeltaUSecL, tm1);
967
968 if (DDel > DeltaUSecL)
969 {
970 icnt = ICNT;
971 DDel = DeltaUSecL;
972 }
973 else
974 {
975 if (--icnt == 0)
976 break;
977 }
978 }
979 DeltaUSecL = DDel / (double)Elements;
980 }
981
982 return (LowIndex);
983 }
984
985 #undef __FUNCTI0N__
986 #define __FUNCTI0N__ "TestJudyGet"
987
988 Word_t
TestJudyGet(void * J1,void * JL,Word_t Seed,Word_t Elements)989 TestJudyGet(void *J1, void *JL, Word_t Seed, Word_t Elements)
990 {
991 TIMER_vars(tm1); // declare timer variables
992 Word_t LowIndex = ~0UL;
993 Word_t TstIndex;
994 Word_t elm;
995 Word_t *PValue;
996 Word_t Seed1;
997 int Rc;
998
999 double DDel;
1000 Word_t icnt;
1001 Word_t lp;
1002 Word_t Loops;
1003
1004 Loops = (MAXLOOPS / Elements) + MINLOOPS;
1005
1006 if (J1Flag)
1007 {
1008 LowIndex = ~0UL;
1009 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1010 {
1011 STARTTm(tm1);
1012 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1013 {
1014 Seed1 = GetNextIndex(Seed1);
1015
1016 if (DFlag)
1017 TstIndex = Swizzle(Seed1);
1018 else
1019 TstIndex = Seed1;
1020
1021 if (TstIndex < LowIndex)
1022 LowIndex = TstIndex;
1023
1024 J1T(Rc, J1, TstIndex);
1025 if (Rc != 1)
1026 FAILURE("Judy1Test Rc != 1", (Word_t)Rc);
1027 }
1028 ENDTm(DeltaUSec1, tm1);
1029
1030 if (DDel > DeltaUSec1)
1031 {
1032 icnt = ICNT;
1033 DDel = DeltaUSec1;
1034 }
1035 else
1036 {
1037 if (--icnt == 0)
1038 break;
1039 }
1040 }
1041 DeltaUSec1 = DDel / (double)Elements;
1042 }
1043
1044 icnt = ICNT;
1045
1046 if (JLFlag)
1047 {
1048 LowIndex = ~0UL;
1049 for (DDel = 1e40, lp = 0; lp < Loops; lp++)
1050 {
1051 STARTTm(tm1);
1052 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1053 {
1054 Seed1 = GetNextIndex(Seed1);
1055
1056 if (DFlag)
1057 TstIndex = Swizzle(Seed1);
1058 else
1059 TstIndex = Seed1;
1060
1061 if (TstIndex < LowIndex)
1062 LowIndex = TstIndex;
1063
1064 JLG(PValue, JL, TstIndex);
1065 if (PValue == (Word_t *)NULL)
1066 FAILURE("JudyLGet ret PValue = NULL", 0L);
1067 if (*PValue != TstIndex)
1068 FAILURE("JudyLGet ret wrong Value at", elm);
1069 }
1070 ENDTm(DeltaUSecL, tm1);
1071
1072 if (DDel > DeltaUSecL)
1073 {
1074 icnt = ICNT;
1075 DDel = DeltaUSecL;
1076 }
1077 else
1078 {
1079 if (--icnt == 0)
1080 break;
1081 }
1082 }
1083 DeltaUSecL = DDel / (double)Elements;
1084 }
1085
1086 return (LowIndex);
1087 }
1088
1089 #undef __FUNCTI0N__
1090 #define __FUNCTI0N__ "TestJudyCount"
1091
1092 int
TestJudyCount(void * J1,void * JL,Word_t LowIndex,Word_t Elements)1093 TestJudyCount(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
1094 {
1095 TIMER_vars(tm1); // declare timer variables
1096 Word_t elm;
1097 Word_t Count1, CountL;
1098 Word_t TstIndex = LowIndex;
1099 int Rc;
1100
1101 double DDel;
1102 Word_t icnt;
1103 Word_t lp;
1104 Word_t Loops;
1105
1106 Loops = (MAXLOOPS / Elements) + MINLOOPS;
1107
1108 if (J1Flag)
1109 {
1110 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1111 {
1112 TstIndex = LowIndex;
1113 STARTTm(tm1);
1114 for (elm = 0; elm < Elements; elm++)
1115 {
1116 J1C(Count1, J1, LowIndex, TstIndex);
1117
1118 if (Count1 != (elm + 1))
1119 FAILURE("J1C at", elm);
1120
1121 J1N(Rc, J1, TstIndex);
1122 }
1123 ENDTm(DeltaUSec1, tm1);
1124
1125 if (DDel > DeltaUSec1)
1126 {
1127 icnt = ICNT;
1128 DDel = DeltaUSec1;
1129 }
1130 else
1131 {
1132 if (--icnt == 0)
1133 break;
1134 }
1135 }
1136 DeltaUSec1 = DDel / (double)Elements;
1137 }
1138
1139 if (JLFlag)
1140 {
1141 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1142 {
1143 TstIndex = LowIndex;
1144 STARTTm(tm1);
1145 for (elm = 0; elm < Elements; elm++)
1146 {
1147 Word_t *PValue;
1148
1149 JLC(CountL, JL, LowIndex, TstIndex);
1150
1151 if (CountL != (elm + 1))
1152 FAILURE("JLC at", elm);
1153
1154 JLN(PValue, JL, TstIndex);
1155 }
1156 ENDTm(DeltaUSecL, tm1);
1157
1158 if (DDel > DeltaUSecL)
1159 {
1160 icnt = ICNT;
1161 DDel = DeltaUSecL;
1162 }
1163 else
1164 {
1165 if (--icnt == 0)
1166 break;
1167 }
1168 }
1169 DeltaUSecL = DDel / (double)Elements;
1170 }
1171
1172 return (0);
1173 }
1174
1175 #undef __FUNCTI0N__
1176 #define __FUNCTI0N__ "TestJudyNext"
1177
1178 Word_t
TestJudyNext(void * J1,void * JL,Word_t LowIndex,Word_t Elements)1179 TestJudyNext(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
1180 {
1181 TIMER_vars(tm1); // declare timer variables
1182 Word_t elm;
1183
1184 double DDel;
1185 Word_t icnt;
1186 Word_t lp;
1187 Word_t Loops;
1188 Word_t Jindex;
1189
1190 Loops = (MAXLOOPS / Elements) + MINLOOPS;
1191
1192 if (J1Flag)
1193 {
1194 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1195 {
1196 int Rc;
1197 Jindex = LowIndex;
1198
1199 STARTTm(tm1);
1200 J1F(Rc, J1, Jindex);
1201
1202 for (elm = 0; elm < Elements; elm++)
1203 {
1204 if (Rc != 1)
1205 FAILURE("Judy1Next Rc != 1 =", (Word_t)Rc);
1206
1207 J1N(Rc, J1, Jindex); // Get next one
1208 }
1209 ENDTm(DeltaUSec1, tm1);
1210
1211 if (DDel > DeltaUSec1)
1212 {
1213 icnt = ICNT;
1214 DDel = DeltaUSec1;
1215 }
1216 else
1217 {
1218 if (--icnt == 0)
1219 break;
1220 }
1221 }
1222 DeltaUSec1 = DDel / (double)Elements;
1223 }
1224
1225 if (JLFlag)
1226 {
1227 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1228 {
1229 Word_t *PValue;
1230
1231 // Get an Index low enough for Elements
1232 Jindex = LowIndex;
1233
1234 STARTTm(tm1);
1235 JLF(PValue, JL, Jindex);
1236
1237 for (elm = 0; elm < Elements; elm++)
1238 {
1239 if (PValue == NULL)
1240 FAILURE("JudyLNext ret NULL PValue at", elm);
1241
1242 JLN(PValue, JL, Jindex); // Get next one
1243 }
1244 ENDTm(DeltaUSecL, tm1);
1245
1246 if (DDel > DeltaUSecL)
1247 {
1248 icnt = ICNT;
1249 DDel = DeltaUSecL;
1250 }
1251 else
1252 {
1253 if (--icnt == 0)
1254 break;
1255 }
1256 }
1257 DeltaUSecL = DDel / (double)Elements;
1258 }
1259
1260 // perhaps a check should be done here -- if I knew what to expect.
1261 return (Jindex); // return last one
1262 }
1263
1264 #undef __FUNCTI0N__
1265 #define __FUNCTI0N__ "TestJudyPrev"
1266
1267 int
TestJudyPrev(void * J1,void * JL,Word_t HighIndex,Word_t Elements)1268 TestJudyPrev(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
1269 {
1270 TIMER_vars(tm1); // declare timer variables
1271 Word_t elm;
1272
1273 double DDel;
1274 Word_t icnt;
1275 Word_t lp;
1276 Word_t Loops;
1277
1278 Loops = (MAXLOOPS / Elements) + MINLOOPS;
1279
1280 if (J1Flag)
1281 {
1282 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1283 {
1284 Word_t J1index = HighIndex;
1285 int Rc;
1286
1287 STARTTm(tm1);
1288 J1L(Rc, J1, J1index);
1289
1290 for (elm = 0; elm < Elements; elm++)
1291 {
1292 if (Rc != 1)
1293 FAILURE("Judy1Prev Rc != 1 =", (Word_t)Rc);
1294
1295 J1P(Rc, J1, J1index); // Get previous one
1296 }
1297 ENDTm(DeltaUSec1, tm1);
1298
1299 if (DDel > DeltaUSec1)
1300 {
1301 icnt = ICNT;
1302 DDel = DeltaUSec1;
1303 }
1304 else
1305 {
1306 if (--icnt == 0)
1307 break;
1308 }
1309 }
1310 DeltaUSec1 = DDel / (double)Elements;
1311 }
1312
1313 if (JLFlag)
1314 {
1315 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1316 {
1317 Word_t *PValue;
1318 Word_t JLindex = HighIndex;
1319
1320 STARTTm(tm1);
1321 JLL(PValue, JL, JLindex);
1322
1323 for (elm = 0; elm < Elements; elm++)
1324 {
1325 if (PValue == NULL)
1326 FAILURE("JudyLPrev ret NULL PValue at", elm);
1327
1328 JLP(PValue, JL, JLindex); // Get previous one
1329 }
1330 ENDTm(DeltaUSecL, tm1);
1331
1332 if (DDel > DeltaUSecL)
1333 {
1334 icnt = ICNT;
1335 DDel = DeltaUSecL;
1336 }
1337 else
1338 {
1339 if (--icnt == 0)
1340 break;
1341 }
1342 }
1343 DeltaUSecL = DDel / (double)Elements;
1344 }
1345
1346 // perhaps a check should be done here -- if I knew what to expect.
1347 return (0);
1348 }
1349
1350 #undef __FUNCTI0N__
1351 #define __FUNCTI0N__ "TestJudyNextEmpty"
1352
1353 // Returns number of consecutive Indexes
1354 Word_t
TestJudyNextEmpty(void * J1,void * JL,Word_t LowIndex,Word_t Elements)1355 TestJudyNextEmpty(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
1356 {
1357 TIMER_vars(tm1); // declare timer variables
1358 Word_t elm;
1359
1360 double DDel;
1361 Word_t icnt;
1362 Word_t lp;
1363 Word_t Loops;
1364 int Rc; // Return code
1365
1366 Loops = (MAXLOOPS / Elements) + MINLOOPS;
1367
1368 if (J1Flag)
1369 {
1370 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1371 {
1372 Word_t Seed1 = LowIndex;
1373
1374 STARTTm(tm1);
1375 for (elm = 0; elm < Elements; elm++)
1376 {
1377 Word_t J1index;
1378 J1index = Seed1;
1379
1380 // Find next Empty Index, J1index is modified by J1NE
1381 J1NE(Rc, J1, J1index); // Rc = Judy1NextEmpty(J1, &J1index,PJE0)
1382
1383 if (Rc != 1)
1384 FAILURE("Judy1NextEmpty Rcode != 1 =", (Word_t)Rc);
1385
1386 Seed1 = GetNextIndex(Seed1);
1387 }
1388 ENDTm(DeltaUSec1, tm1);
1389
1390 if (DDel > DeltaUSec1)
1391 {
1392 icnt = ICNT;
1393 DDel = DeltaUSec1;
1394 }
1395 else
1396 {
1397 if (--icnt == 0)
1398 break;
1399 }
1400 }
1401 DeltaUSec1 = DDel / (double)Elements;
1402 }
1403
1404 if (JLFlag)
1405 {
1406 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1407 {
1408 Word_t Seed1 = LowIndex;
1409
1410 STARTTm(tm1);
1411 for (elm = 0; elm < Elements; elm++)
1412 {
1413 Word_t JLindex;
1414 JLindex = Seed1;
1415
1416 // Find next Empty Index, JLindex is modified by JLNE
1417 JLNE(Rc, JL, JLindex); // Rc = JudyLNextEmpty(JL, &JLindex,PJE0)
1418
1419 if (Rc != 1)
1420 FAILURE("JudyLNextEmpty Rcode != 1 =", (Word_t)Rc);
1421
1422 Seed1 = GetNextIndex(Seed1);
1423 }
1424 ENDTm(DeltaUSecL, tm1);
1425
1426 if (DDel > DeltaUSecL)
1427 {
1428 icnt = ICNT;
1429 DDel = DeltaUSecL;
1430 }
1431 else
1432 {
1433 if (--icnt == 0)
1434 break;
1435 }
1436 }
1437 DeltaUSecL = DDel / (double)Elements;
1438 }
1439
1440 return (0);
1441 }
1442
1443 // Routine to time and test JudyPrevEmpty routines
1444
1445 #undef __FUNCTI0N__
1446 #define __FUNCTI0N__ "TestJudyPrevEmpty"
1447
1448 Word_t
TestJudyPrevEmpty(void * J1,void * JL,Word_t HighIndex,Word_t Elements)1449 TestJudyPrevEmpty(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
1450 {
1451 TIMER_vars(tm1); // declare timer variables
1452 Word_t elm;
1453
1454 double DDel;
1455 Word_t icnt;
1456 Word_t lp;
1457 Word_t Loops;
1458 int Rc;
1459
1460 Loops = (MAXLOOPS / Elements) + MINLOOPS;
1461
1462 if (J1Flag)
1463 {
1464 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1465 {
1466 Word_t Seed1 = HighIndex;
1467
1468 STARTTm(tm1);
1469 for (elm = 0; elm < Elements; elm++)
1470 {
1471 Word_t J1index;
1472 J1index = Seed1;
1473
1474 J1PE(Rc, J1, J1index); // Rc = Judy1PrevEmpty(J1, &J1index,PJE0)
1475
1476 if (Rc != 1)
1477 FAILURE("Judy1PrevEmpty Rc != 1 =", (Word_t)Rc);
1478
1479 Seed1 = GetNextIndex(Seed1);
1480 }
1481 ENDTm(DeltaUSec1, tm1);
1482
1483 if (DDel > DeltaUSec1)
1484 {
1485 icnt = ICNT;
1486 DDel = DeltaUSec1;
1487 }
1488 else
1489 {
1490 if (--icnt == 0)
1491 break;
1492 }
1493 }
1494 DeltaUSec1 = DDel / (double)Elements;
1495 }
1496
1497 if (JLFlag)
1498 {
1499 for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1500 {
1501 Word_t Seed1 = HighIndex;
1502
1503 STARTTm(tm1);
1504 for (elm = 0; elm < Elements; elm++)
1505 {
1506 Word_t JLindex;
1507 JLindex = Seed1;
1508
1509 // Find next Empty Index, JLindex is modified by JLPE
1510 JLPE(Rc, JL, JLindex); // Rc = JudyLPrevEmpty(JL, &JLindex,PJE0)
1511
1512 if (Rc != 1)
1513 FAILURE("JudyLPrevEmpty Rcode != 1 =", (Word_t)Rc);
1514
1515 Seed1 = GetNextIndex(Seed1);
1516 }
1517 ENDTm(DeltaUSecL, tm1);
1518
1519 if (DDel > DeltaUSecL)
1520 {
1521 icnt = ICNT;
1522 DDel = DeltaUSecL;
1523 }
1524 else
1525 {
1526 if (--icnt == 0)
1527 break;
1528 }
1529 }
1530 DeltaUSecL = DDel / (double)Elements;
1531 }
1532
1533 return (0);
1534 }
1535
1536 #undef __FUNCTI0N__
1537 #define __FUNCTI0N__ "TestJudyDel"
1538
1539 int
TestJudyDel(void ** J1,void ** JL,Word_t Seed,Word_t Elements)1540 TestJudyDel(void **J1, void **JL, Word_t Seed, Word_t Elements)
1541 {
1542 TIMER_vars(tm1); // declare timer variables
1543 Word_t TstIndex;
1544 Word_t elm;
1545 Word_t Seed1;
1546 int Rc;
1547
1548 if (J1Flag)
1549 {
1550 STARTTm(tm1);
1551 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1552 {
1553 Seed1 = GetNextIndex(Seed1);
1554
1555 if (DFlag)
1556 TstIndex = Swizzle(Seed1);
1557 else
1558 TstIndex = Seed1;
1559
1560 J1U(Rc, *J1, TstIndex);
1561 if (Rc != 1)
1562 FAILURE("Judy1Unset ret Rcode != 1", (Word_t)Rc);
1563 }
1564 ENDTm(DeltaUSec1, tm1);
1565 DeltaUSec1 /= Elements;
1566 }
1567
1568 STARTTm(tm1);
1569 if (JLFlag)
1570 {
1571 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1572 {
1573 Seed1 = GetNextIndex(Seed1);
1574
1575 if (DFlag)
1576 TstIndex = Swizzle(Seed1);
1577 else
1578 TstIndex = Seed1;
1579
1580 JLD(Rc, *JL, TstIndex);
1581 if (Rc != 1)
1582 FAILURE("JudyLDel ret Rcode != 1", (Word_t)Rc);
1583 }
1584 ENDTm(DeltaUSecL, tm1);
1585 DeltaUSecL /= Elements;
1586 }
1587 return (0);
1588 }
1589
1590 // Routine to get next size of Indexes
1591 int // return 1 if last number
NextNumb(Word_t * PNumber,double * PDNumb,double DMult,Word_t MaxNumb)1592 NextNumb(Word_t *PNumber, // pointer to returned next number
1593 double *PDNumb, // Temp double of above
1594 double DMult, // Multiplier
1595 Word_t MaxNumb) // Max number to return
1596 {
1597 // Save prev number
1598 double PrevPDNumb = *PDNumb;
1599 double DDiff;
1600
1601 // Calc next number >= 1.0 beyond previous
1602 do {
1603 *PDNumb *= DMult;
1604 DDiff = *PDNumb - PrevPDNumb;
1605
1606 } while (DDiff < 0.5);
1607
1608 // Return it in integer format
1609 if (DDiff < 100.0) *PNumber += (Word_t)(DDiff + 0.5);
1610 else *PNumber = *PDNumb + 0.5;
1611
1612 // Verify it did not exceed max number
1613 if (*PNumber >= MaxNumb)
1614 {
1615 // it did, so return max
1616 *PNumber = MaxNumb;
1617 return (1); // flag it
1618 }
1619 return (0); // more available
1620 }
1621