1 // @(#) $Revision: 4.15 $ $Source: /judy/test/manual/Judy1LHCheck.c $
2 // This program tests the accuracy of a Judy1 with a JudyL Array.
3 // -by-
4 // Douglas L. Baskins (8/2001) doug@sourcejudy.com
5
6 #include <stdlib.h> // calloc()
7 #include <unistd.h> // getopt()
8 #include <math.h> // pow()
9 #include <stdio.h> // printf()
10
11 #include <Judy.h>
12
13 // Compile:
14 // # cc -O Judy1LHCheck.c -lm -lJudy -o Judy1LHCheck
15
16 // Common macro to handle a failure
17 #define FAILURE(STR, UL) \
18 { \
19 printf( "Error: %s %lu, file='%s', 'function='%s', line %d\n", \
20 STR, (Word_t)(UL), __FILE__, __FUNCTI0N__, __LINE__); \
21 fprintf(stderr, "Error: %s %lu, file='%s', 'function='%s', line %d\n", \
22 STR, (Word_t)(UL), __FILE__, __FUNCTI0N__, __LINE__); \
23 exit(1); \
24 }
25
26 // Structure to keep track of times
27 typedef struct MEASUREMENTS_STRUCT
28 {
29 Word_t ms_delta;
30 }
31 ms_t, *Pms_t;
32
33 // Specify prototypes for each test routine
34 int
35 NextNumb(Word_t * PNumber, double *PDNumb, double DMult, Word_t MaxNumb);
36
37 Word_t TestJudyIns(void **J1, void **JL, void **JH, Word_t Seed, Word_t Elements);
38
39 Word_t TestJudyDup(void **J1, void **JL, void **JH, Word_t Seed, Word_t Elements);
40
41 int TestJudyDel(void **J1, void **JL, void **JH, Word_t Seed, Word_t Elements);
42
43 Word_t TestJudyGet(void *J1, void *JL, void *JH, Word_t Seed, Word_t Elements);
44
45 int TestJudyCount(void *J1, void *JL, Word_t LowIndex, Word_t Elements);
46
47 Word_t TestJudyNext(void *J1, void *JL, Word_t LowIndex, Word_t Elements);
48
49 int TestJudyPrev(void *J1, void *JL, Word_t HighIndex, Word_t Elements);
50
51 int
52 TestJudyNextEmpty(void *J1, void *JL, Word_t LowIndex, Word_t Elements);
53
54 int
55 TestJudyPrevEmpty(void *J1, void *JL, Word_t HighIndex, Word_t Elements);
56
57 Word_t MagicList[] =
58 {
59 0,0,0,0,0,0,0,0,0,0, // 0..9
60 0x27f, // 10
61 0x27f, // 11
62 0x27f, // 12
63 0x27f, // 13
64 0x27f, // 14
65 0x27f, // 15
66 0x1e71, // 16
67 0xdc0b, // 17
68 0xdc0b, // 18
69 0xdc0b, // 19
70 0xdc0b, // 20
71 0xc4fb, // 21
72 0xc4fb, // 22
73 0xc4fb, // 23
74 0x13aab, // 24
75 0x11ca3, // 25
76 0x11ca3, // 26
77 0x11ca3, // 27
78 0x13aab, // 28
79 0x11ca3, // 29
80 0xc4fb, // 30
81 0xc4fb, // 31
82 0x13aab, // 32
83 0x14e73, // 33
84 0x145d7, // 34
85 0x145f9, // 35 following tested with Seed=0xc1fc to 35Gig numbers
86 0x151ed, // 36 .. 41
87 0x151ed, // 37
88 0x151ed, // 38
89 0x151ed, // 39 fails at 549751488512 (549Gig)
90 0x151ed, // 40
91 0x146c3, // 41 .. 64
92 0x146c3, // 42
93 0x146c3, // 43
94 0x146c3, // 44
95 0x146c3, // 45
96 0x146c3, // 46
97 0x146c3, // 47
98 0x146c3, // 48
99 0x146c3, // 49
100 0x146c3, // 50
101 0x146c3, // 51
102 0x146c3, // 52
103 0x146c3, // 53
104 0x146c3, // 54
105 0x146c3, // 55
106 0x146c3, // 56
107 0x146c3, // 57
108 0x146c3, // 58
109 0x146c3, // 59
110 0x146c3, // 60
111 0x146c3, // 61
112 0x146c3, // 62
113 0x146c3, // 63
114 0x146c3 // 64
115 };
116
117 // Routine to "mirror" the input data word
118 static Word_t
Swizzle(Word_t word)119 Swizzle(Word_t word)
120 {
121 // BIT REVERSAL, Ron Gutman in Dr. Dobb's Journal, #316, Sept 2000, pp133-136
122 //
123
124 #ifdef __LP64__
125 word = ((word & 0x00000000ffffffff) << 32) |
126 ((word & 0xffffffff00000000) >> 32);
127 word = ((word & 0x0000ffff0000ffff) << 16) |
128 ((word & 0xffff0000ffff0000) >> 16);
129 word = ((word & 0x00ff00ff00ff00ff) << 8) |
130 ((word & 0xff00ff00ff00ff00) >> 8);
131 word = ((word & 0x0f0f0f0f0f0f0f0f) << 4) |
132 ((word & 0xf0f0f0f0f0f0f0f0) >> 4);
133 word = ((word & 0x3333333333333333) << 2) |
134 ((word & 0xcccccccccccccccc) >> 2);
135 word = ((word & 0x5555555555555555) << 1) |
136 ((word & 0xaaaaaaaaaaaaaaaa) >> 1);
137 #else // __LP64__
138 word = ((word & 0x0000ffff) << 16) | ((word & 0xffff0000) >> 16);
139 word = ((word & 0x00ff00ff) << 8) | ((word & 0xff00ff00) >> 8);
140 word = ((word & 0x0f0f0f0f) << 4) | ((word & 0xf0f0f0f0) >> 4);
141 word = ((word & 0x33333333) << 2) | ((word & 0xcccccccc) >> 2);
142 word = ((word & 0x55555555) << 1) | ((word & 0xaaaaaaaa) >> 1);
143 #endif // __LP64__
144
145 return(word);
146 }
147
148 Word_t dFlag = 1;
149 Word_t pFlag = 0;
150 Word_t CFlag = 0;
151 Word_t DFlag = 0;
152 Word_t SkipN = 0; // default == Random skip
153 Word_t nElms = 1000000; // Default = 1M
154 Word_t ErrorFlag = 0;
155 Word_t TotalIns = 0;
156 Word_t TotalPop = 0;
157 Word_t TotalDel = 0;
158
159 // Stuff for LFSR (pseudo random number generator)
160 Word_t RandomBit = ~0UL / 2 + 1;
161 Word_t BValue = sizeof(Word_t) * 8;
162 Word_t Magic;
163 Word_t StartSeed = 0xc1fc; // default beginning number
164 Word_t FirstSeed;
165
166 #undef __FUNCTI0N__
167 #define __FUNCTI0N__ "Random"
168
169 static Word_t // Placed here so INLINING compilers get to look at it.
Random(Word_t newseed)170 Random(Word_t newseed)
171 {
172 if (newseed & RandomBit)
173 {
174 newseed += newseed;
175 newseed ^= Magic;
176 }
177 else
178 {
179 newseed += newseed;
180 }
181 newseed &= RandomBit * 2 - 1;
182 if (newseed == FirstSeed)
183 {
184 printf("Passed (End of LFSR) Judy1, JudyL, JudyHS tests for %lu numbers with <= %ld bits\n", TotalPop, BValue);
185 exit(0);
186 }
187 return(newseed);
188 }
189
190 static Word_t // Placed here so INLINING compilers get to look at it.
GetNextIndex(Word_t Index)191 GetNextIndex(Word_t Index)
192 {
193 if (SkipN)
194 Index += SkipN;
195 else
196 Index = Random(Index);
197
198 return(Index);
199 }
200
201 #undef __FUNCTI0N__
202 #define __FUNCTI0N__ "main"
203
204 int
main(int argc,char * argv[])205 main(int argc, char *argv[])
206 {
207 // Names of Judy Arrays
208 void *J1 = NULL; // Judy1
209 void *JL = NULL; // JudyL
210 void *JH = NULL; // JudyHS
211
212 double Mult;
213 Pms_t Pms;
214 Word_t Seed;
215 Word_t PtsPdec = 10; // points per decade
216 Word_t Groups; // Number of measurement groups
217 Word_t grp;
218
219 int c;
220 extern char *optarg;
221
222 //////////////////////////////////////////////////////////////
223 // PARSE INPUT PARAMETERS
224 //////////////////////////////////////////////////////////////
225
226 while ((c = getopt(argc, argv, "n:S:P:b:L:B:pdDC")) != -1)
227 {
228 switch (c)
229 {
230 case 'n': // Number of elements
231 nElms = strtoul(optarg, NULL, 0); // Size of Linear Array
232 if (nElms == 0)
233 FAILURE("No tests: -n", nElms);
234
235 // Check if more than a trillion (64 bit only)
236 if ((double)nElms > 1e12)
237 FAILURE("Too many Indexes=", nElms);
238 break;
239
240 case 'S': // Step Size, 0 == Random
241 SkipN = strtoul(optarg, NULL, 0);
242 break;
243
244 case 'P': //
245 PtsPdec = strtoul(optarg, NULL, 0);
246 break;
247
248 case 'b': // May not work past 35 bits if changed
249 StartSeed = strtoul(optarg, NULL, 0);
250 break;
251
252 case 'B':
253 BValue = strtoul(optarg, NULL, 0);
254 if (
255 (BValue > (sizeof(Word_t) * 8))
256 ||
257 (MagicList[BValue] == 0)
258 )
259 {
260 ErrorFlag++;
261 printf("\nIllegal number of random bits of %lu !!!\n", BValue);
262 }
263 break;
264
265 case 'p': // Print test indexes
266 pFlag = 1;
267 break;
268
269 case 'd': // Delete indexes
270 dFlag = 0;
271 break;
272
273 case 'D': // Swizzle indexes
274 DFlag = 1;
275 break;
276
277 case 'C': // Skip counting test.
278 CFlag = 1;
279 break;
280
281 default:
282 ErrorFlag++;
283 break;
284 }
285 }
286
287 if (ErrorFlag)
288 {
289 printf("\n%s -n# -S# -B# -P# -b # -DRCpd\n\n", argv[0]);
290 printf("Where:\n");
291 printf("-n <#> number of indexes used in tests\n");
292 printf("-C skip JudyCount tests\n");
293 printf("-p print index set - for debug\n");
294 printf("-d do not call JudyDel/Unset\n");
295 printf("-D Swizzle data (mirror)\n");
296 printf("-S <#> index skip amount, 0 = random\n");
297 printf("-B <#> # bits-1 in random number generator\n");
298 printf("-P <#> number measurement points per decade\n");
299 printf("\n");
300
301 exit(1);
302 }
303 // Set number of Random bits in LFSR
304 RandomBit = 1UL << (BValue - 1);
305 Magic = MagicList[BValue];
306
307 if (nElms > ((RandomBit-2) * 2))
308 {
309 printf("# Number = -n%lu of Indexes reduced to max expanse of Random numbers\n", nElms);
310 nElms = ((RandomBit-2) * 2);
311 }
312
313 printf("\n%s -n%lu -S%lu -B%lu", argv[0], nElms, SkipN, BValue);
314
315 if (DFlag)
316 printf(" -D");
317 if (!dFlag)
318 printf(" -d");
319 if (pFlag)
320 printf(" -p");
321 if (CFlag)
322 printf(" -C");
323 printf("\n\n");
324
325 if (sizeof(Word_t) == 8)
326 printf("%s 64 Bit version\n", argv[0]);
327 else if (sizeof(Word_t) == 4)
328 printf("%s 32 Bit version\n", argv[0]);
329
330 //////////////////////////////////////////////////////////////
331 // CALCULATE NUMBER OF MEASUREMENT GROUPS
332 //////////////////////////////////////////////////////////////
333
334 // Calculate Multiplier for number of points per decade
335 Mult = pow(10.0, 1.0 / (double)PtsPdec);
336 {
337 double sum;
338 Word_t numb, prevnumb;
339
340 // Count number of measurements needed (10K max)
341 sum = numb = 1;
342 for (Groups = 2; Groups < 10000; Groups++)
343 if (NextNumb(&numb, &sum, Mult, nElms))
344 break;
345
346 // Get memory for measurements
347 Pms = (Pms_t) calloc(Groups, sizeof(ms_t));
348
349 // Now calculate number of Indexes for each measurement point
350 numb = sum = 1;
351 prevnumb = 0;
352 for (grp = 0; grp < Groups; grp++)
353 {
354 Pms[grp].ms_delta = numb - prevnumb;
355 prevnumb = numb;
356
357 NextNumb(&numb, &sum, Mult, nElms);
358 }
359 } // Groups = number of sizes
360
361 //////////////////////////////////////////////////////////////
362 // BEGIN TESTS AT EACH GROUP SIZE
363 //////////////////////////////////////////////////////////////
364
365 // Get the kicker to test the LFSR
366 FirstSeed = Seed = StartSeed & (RandomBit * 2 - 1);
367
368 printf("Total Pop Total Ins New Ins Total Del");
369 printf(" J1MU/I JLMU/I\n");
370
371 #ifdef testLFSR
372 {
373 Word_t Seed1 = Seed;
374
375 printf("Begin test of LSFR, BValue = %lu\n", BValue);
376 while(1)
377 {
378 Seed1 = GetNextIndex(Seed1);
379 TotalPop++;
380 if (TotalPop == 0) printf("BUG!!!\n");
381 }
382 exit(0);
383 }
384 #endif // testLFSR
385
386 for (grp = 0; grp < Groups; grp++)
387 {
388 Word_t LowIndex, HighIndex;
389 Word_t Delta;
390 Word_t NewSeed;
391
392 Delta = Pms[grp].ms_delta;
393
394 // Test JLI, J1S
395 NewSeed = TestJudyIns(&J1, &JL, &JH, Seed, Delta);
396
397 // Test JLG, J1T
398 LowIndex = TestJudyGet(J1, JL, JH, Seed, Delta);
399
400 // Test JLI, J1S -dup
401 LowIndex = TestJudyDup(&J1, &JL, &JH, Seed, Delta);
402
403 // Test JLC, J1C
404 if (!CFlag)
405 {
406 TestJudyCount(J1, JL, LowIndex, Delta);
407 }
408 // Test JLN, J1N
409 HighIndex = TestJudyNext(J1, JL, 0UL, TotalPop);
410
411 // Test JLP, J1P
412 TestJudyPrev(J1, JL, ~0UL, TotalPop);
413
414 // Test JLNE, J1NE
415 TestJudyNextEmpty(J1, JL, LowIndex, Delta);
416
417 // Test JLPE, J1PE
418 TestJudyPrevEmpty(J1, JL, HighIndex, Delta);
419
420 // Test JLD, J1U
421 if (dFlag)
422 {
423 TestJudyDel(&J1, &JL, &JH, Seed, Delta);
424 }
425
426 printf("%9lu %9lu %7lu %9lu", TotalPop, TotalIns, Delta, TotalDel);
427 {
428 Word_t Count1, CountL;
429
430 // Print the number of bytes used per Index
431 J1C(Count1, J1, 0, ~0);
432 printf(" %6.3f", (double)Judy1MemUsed(J1) / (double)Count1);
433 JLC(CountL, JL, 0, ~0);
434 printf(" %6.3f", (double)JudyLMemUsed(JL) / (double)CountL);
435 }
436 printf("\n");
437
438 // Advance Index number set
439 Seed = NewSeed;
440 }
441 {
442 Word_t Count1, CountL;
443 Word_t Bytes;
444
445 JLC(CountL, JL, 0, ~0);
446 J1C(Count1, J1, 0, ~0);
447
448 if (CountL != TotalPop)
449 FAILURE("JudyLCount wrong", CountL);
450
451 if (Count1 != TotalPop)
452 FAILURE("Judy1Count wrong", Count1);
453
454 if (TotalPop)
455 {
456 J1FA(Bytes, J1); // Free the Judy1 Array
457 printf("Judy1FreeArray = %6.3f Bytes/Index\n",
458 (double)Bytes / (double)Count1);
459
460 if (pFlag) { printf("J1FA: %8lu\tbytes = %lu\n", TotalPop, Bytes); }
461
462 JLFA(Bytes, JL); // Free the JudyL Array
463 printf("JudyLFreeArray = %6.3f Bytes/Index\n",
464 (double)Bytes / (double)CountL);
465
466 if (pFlag) { printf("JLFA: %8lu\tbytes = %lu\n", TotalPop, Bytes); }
467
468 JHSFA(Bytes, JH); // Free the JudyL Array
469 printf("JudyHSFreeArray = %6.3f Bytes/Index\n",
470 (double)Bytes / (double)TotalPop); // Count not available yet
471
472 if (pFlag) { printf("JHSFA: %8lu\tbytes = %lu\n", TotalPop, Bytes); }
473
474 TotalPop = 0;
475 }
476 }
477 printf("Passed Judy1, JudyL, JudyHS tests for %lu numbers with <= %ld bits\n", nElms, BValue);
478 exit(0);
479 }
480
481 #undef __FUNCTI0N__
482 #define __FUNCTI0N__ "TestJudyIns"
483
484 Word_t
TestJudyIns(void ** J1,void ** JL,void ** JH,Word_t Seed,Word_t Elements)485 TestJudyIns(void **J1, void **JL, void **JH, Word_t Seed, Word_t Elements)
486 {
487 Word_t TstIndex;
488 Word_t elm;
489 Word_t *PValue, *PValue1;
490 Word_t Seed1;
491 int Rcode;
492
493 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
494 {
495 Seed1 = GetNextIndex(Seed1);
496 if (Seed1 == 0)
497 FAILURE("This command not robust if Index == 0", elm);
498
499 if (DFlag)
500 TstIndex = Swizzle(Seed1);
501 else
502 TstIndex = Seed1;
503
504 if (pFlag) { printf("Ins: %8lu\t0x%lx\n", elm, TstIndex); }
505
506 // Judy1
507
508 J1S(Rcode, *J1, TstIndex);
509 if (Rcode == JERR)
510 FAILURE("Judy1Set failed at", elm);
511 if (Rcode == 0)
512 FAILURE("Judy1Set failed - DUP Index, population =", TotalPop);
513
514 #ifdef SKIPMACRO
515 Rcode = Judy1Test(*J1, TstIndex);
516 #else
517 J1T(Rcode, *J1, TstIndex);
518 #endif // SKIPMACRO
519 if (Rcode != 1)
520 FAILURE("Judy1Test failed - Index missing, population =", TotalPop);
521
522 J1S(Rcode, *J1, TstIndex);
523 if (Rcode != 0)
524 FAILURE("Judy1Set failed - Index missing, population =", TotalPop);
525
526 // JudyL
527 JLI(PValue, *JL, TstIndex);
528 if (PValue == PJERR)
529 FAILURE("JudyLIns failed at", elm);
530 if (*PValue == TstIndex)
531 FAILURE("JudyLIns failed - DUP Index, population =", TotalPop);
532
533 // Save Index in Value
534 *PValue = TstIndex;
535
536 #ifdef SKIPMACRO
537 PValue1 = (PWord_t)JudyLGet(*JL, TstIndex);
538 #else
539 JLG(PValue1, *JL, TstIndex);
540 #endif // SKIPMACRO
541 if (PValue != PValue1)
542 FAILURE("JudyLGet failed - Index missing, population =", TotalPop);
543
544 JLI(PValue1, *JL, TstIndex);
545 if (PValue != PValue1)
546 {
547 if (*PValue1 != TstIndex)
548 {
549 FAILURE("JudyLIns failed - Index missing, population =", TotalPop);
550 }
551 else
552 {
553 // not ready for this yet! printf("Index moved -- TotalPop = %lu\n", TotalPop);
554 }
555 }
556 // JudyHS
557 JHSI(PValue, *JH, (void *)(&TstIndex), sizeof(Word_t));
558 if (PValue == PJERR)
559 FAILURE("JudyHSIns failed at", elm);
560 if (*PValue == TstIndex)
561 FAILURE("JudyHSIns failed - DUP Index, population =", TotalPop);
562
563 // Save Index in Value
564 *PValue = TstIndex;
565
566 JHSG(PValue1, *JH, (void *)(&TstIndex), sizeof(Word_t));
567 if (PValue != PValue1)
568 FAILURE("JudyHSGet failed - Index missing, population =", TotalPop);
569
570 JHSI(PValue1, *JH, (void *)(&TstIndex), sizeof(Word_t));
571 if (PValue != PValue1)
572 {
573 if (*PValue1 != TstIndex)
574 {
575 FAILURE("JudyHSIns failed - Index missing, population =", TotalPop);
576 }
577 else
578 {
579 // not ready for this yet! printf("Index moved -- TotalPop = %lu\n", TotalPop);
580 }
581 }
582 TotalPop++;
583 TotalIns++;
584 }
585 return (Seed1); // New seed
586 }
587
588 #undef __FUNCTI0N__
589 #define __FUNCTI0N__ "TestJudyGet"
590
591 Word_t
TestJudyGet(void * J1,void * JL,void * JH,Word_t Seed,Word_t Elements)592 TestJudyGet(void *J1, void *JL, void *JH, Word_t Seed, Word_t Elements)
593 {
594 Word_t LowIndex = ~0UL;
595 Word_t TstIndex;
596 Word_t elm;
597 Word_t *PValue;
598 Word_t Seed1;
599 int Rcode;
600
601 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
602 {
603 Seed1 = GetNextIndex(Seed1);
604
605 if (DFlag)
606 TstIndex = Swizzle(Seed1);
607 else
608 TstIndex = Seed1;
609
610 if (TstIndex < LowIndex)
611 LowIndex = TstIndex;
612
613 #ifdef SKIPMACRO
614 Rcode = Judy1Test(J1, TstIndex);
615 #else
616 J1T(Rcode, J1, TstIndex);
617 #endif // SKIPMACRO
618 if (Rcode != 1)
619 FAILURE("Judy1Test Rcode != 1", Rcode);
620
621 #ifdef SKIPMACRO
622 PValue = (PWord_t)JudyLGet(JL, TstIndex);
623 #else
624 JLG(PValue, JL, TstIndex);
625 #endif // SKIPMACRO
626 if (PValue == (Word_t *) NULL)
627 FAILURE("JudyLGet ret PValue = NULL", 0L);
628 if (*PValue != TstIndex)
629 FAILURE("JudyLGet ret wrong Value at", elm);
630
631 JHSG(PValue, JH, (void *)(&TstIndex), sizeof(Word_t));
632 if (PValue == (Word_t *) NULL)
633 FAILURE("JudyHSGet ret PValue = NULL", 0L);
634 if (*PValue != TstIndex)
635 FAILURE("JudyHSGet ret wrong Value at", elm);
636 }
637
638 return(LowIndex);
639 }
640
641 #undef __FUNCTI0N__
642 #define __FUNCTI0N__ "TestJudyDup"
643
644 Word_t
TestJudyDup(void ** J1,void ** JL,void ** JH,Word_t Seed,Word_t Elements)645 TestJudyDup(void **J1, void **JL, void **JH, Word_t Seed, Word_t Elements)
646 {
647 Word_t LowIndex = ~0UL;
648 Word_t TstIndex;
649 Word_t elm;
650 Word_t *PValue;
651 Word_t Seed1;
652 int Rcode;
653
654 for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
655 {
656 Seed1 = GetNextIndex(Seed1);
657
658 if (DFlag)
659 TstIndex = Swizzle(Seed1);
660 else
661 TstIndex = Seed1;
662
663 if (TstIndex < LowIndex)
664 LowIndex = TstIndex;
665
666 J1S(Rcode, *J1, TstIndex);
667 if (Rcode != 0)
668 FAILURE("Judy1Set Rcode != 0", Rcode);
669
670 JLI(PValue, *JL, TstIndex);
671 if (PValue == (Word_t *) NULL)
672 FAILURE("JudyLIns ret PValue = NULL", 0L);
673 if (*PValue != TstIndex)
674 FAILURE("JudyLIns ret wrong Value at", elm);
675
676 JHSI(PValue, *JH, &TstIndex, sizeof(Word_t));
677 if (PValue == (Word_t *) NULL)
678 FAILURE("JudyHSIns ret PValue = NULL", 0L);
679 if (*PValue != TstIndex)
680 FAILURE("JudyHSIns ret wrong Value at", elm);
681 }
682
683 return(LowIndex);
684 }
685
686 #undef __FUNCTI0N__
687 #define __FUNCTI0N__ "TestJudyCount"
688
689 int
TestJudyCount(void * J1,void * JL,Word_t LowIndex,Word_t Elements)690 TestJudyCount(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
691 {
692 Word_t elm;
693 Word_t Count1, CountL;
694 Word_t TstIndex = LowIndex;
695 int Rcode;
696
697 TstIndex = LowIndex;
698 for (elm = 0; elm < Elements; elm++)
699 {
700 J1C(Count1, J1, LowIndex, TstIndex);
701 if (Count1 == JERR)
702 FAILURE("Judy1Count ret JERR", Count1);
703
704 if (Count1 != (elm + 1))
705 {
706 J1C(CountL, J1, 0, -1);
707 printf("J1C(%lu, J1, 0, -1)\n", CountL);
708
709 JLC(CountL, JL, 0, -1);
710 printf("JLC(%lu, JL, 0, -1)\n", CountL);
711
712 printf("LowIndex = 0x%lx, TstIndex = 0x%lx, diff = %lu\n", LowIndex,
713 TstIndex, TstIndex - LowIndex);
714 JLC(CountL, JL, LowIndex, TstIndex);
715 printf("CountL = %lu, Count1 = %lu, should be: elm + 1 = %lu\n", CountL, Count1, elm + 1);
716 FAILURE("J1C at", elm);
717 }
718
719 JLC(CountL, JL, LowIndex, TstIndex);
720 if (CountL == JERR)
721 FAILURE("JudyLCount ret JERR", CountL);
722
723 if (CountL != (elm + 1))
724 {
725 printf("CountL = %lu, elm +1 = %lu\n", CountL, elm + 1);
726 FAILURE("JLC at", elm);
727 }
728
729 J1N(Rcode, J1, TstIndex);
730 }
731 return(0);
732 }
733
734 #undef __FUNCTI0N__
735 #define __FUNCTI0N__ "TestJudyNext"
736
TestJudyNext(void * J1,void * JL,Word_t LowIndex,Word_t Elements)737 Word_t TestJudyNext(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
738 {
739 Word_t JLindex, J1index, JPindex = 0;
740 Word_t *PValue;
741 Word_t elm;
742 int Rcode;
743
744 // Get an Index low enough for Elements
745 J1index = JLindex = LowIndex;
746
747 JLF(PValue, JL, JLindex);
748 J1F(Rcode, J1, J1index);
749
750 for (elm = 0; elm < Elements; elm++)
751 {
752 if (PValue == NULL)
753 FAILURE("JudyLNext ret NULL PValue at", elm);
754 if (Rcode != 1)
755 FAILURE("Judy1Next Rcode != 1 =", Rcode);
756 if (JLindex != J1index)
757 FAILURE("JudyLNext & Judy1Next ret different PIndex at", elm);
758
759 JPindex = J1index; // save the last found index
760
761 JLN(PValue, JL, JLindex); // Get next one
762 J1N(Rcode, J1, J1index); // Get next one
763 }
764
765 if (PValue != NULL)
766 FAILURE("JudyLNext PValue != NULL", PValue);
767 if (Rcode != 0)
768 FAILURE("Judy1Next Rcode != 1 =", Rcode);
769
770 // perhaps a check should be done here -- if I knew what to expect.
771 return(JPindex); // return last one
772 }
773
774
775 #undef __FUNCTI0N__
776 #define __FUNCTI0N__ "TestJudyPrev"
777
778 int
TestJudyPrev(void * J1,void * JL,Word_t HighIndex,Word_t Elements)779 TestJudyPrev(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
780 {
781 Word_t JLindex, J1index;
782 Word_t *PValue;
783 Word_t elm;
784 int Rcode;
785
786 // Get an Index high enough for Elements
787 J1index = JLindex = HighIndex;
788
789 JLL(PValue, JL, JLindex);
790 J1L(Rcode, J1, J1index);
791
792 for (elm = 0; elm < Elements; elm++)
793 {
794 if (PValue == NULL)
795 FAILURE("JudyLPrev ret NULL PValue at", elm);
796 if (Rcode != 1)
797 FAILURE("Judy1Prev Rcode != 1 =", Rcode);
798 if (JLindex != J1index)
799 FAILURE("JudyLPrev & Judy1Prev ret different PIndex at", elm);
800
801 JLP(PValue, JL, JLindex); // Get previous one
802 J1P(Rcode, J1, J1index); // Get previous one
803 }
804 if (PValue != NULL)
805 FAILURE("JudyLPrev PValue != NULL", PValue);
806 if (Rcode != 0)
807 FAILURE("Judy1Prev Rcode != 1 =", Rcode);
808 // perhaps a check should be done here -- if I knew what to expect.
809 return(0);
810 }
811
812
813 #undef __FUNCTI0N__
814 #define __FUNCTI0N__ "TestJudyNextEmpty"
815
816 int
TestJudyNextEmpty(void * J1,void * JL,Word_t LowIndex,Word_t Elements)817 TestJudyNextEmpty(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
818 {
819 Word_t elm;
820 Word_t JLindex, J1index;
821 Word_t Seed1;
822 int Rcode1; // Return code
823 int RcodeL; // Return code
824
825 // Set 1st search to ..
826 Seed1 = LowIndex;
827 J1index = JLindex = Seed1;
828
829 for (elm = 0; elm < Elements; elm++)
830 {
831 Word_t *PValue;
832
833 if (pFlag) { printf("JNE: %8lu\t0x%lx\n", elm, JLindex); }
834
835 // Find next Empty Index, JLindex is modified by JLNE
836 JLNE(RcodeL, JL, JLindex); // Rcode = JudyLNextEmpty(JL, &JLindex, PJE0)
837
838 // Find next Empty Index, J1index is modified by J1NE
839 J1NE(Rcode1, J1, J1index); // Rcode = Judy1NextEmpty(J1, &J1index, PJE0)
840 if ((Rcode1 != 1) || (RcodeL != 1))
841 {
842 printf("RcodeL = %d, Rcode1 = %d, Index1 = 0x%lx, IndexL = 0x%lx\n",
843 RcodeL, Rcode1, J1index, JLindex);
844 FAILURE("Judy1NextEmpty Rcode != 1 =", Rcode1);
845 }
846
847 if (J1index != JLindex)
848 FAILURE("JLNE != J1NE returned index at", elm);
849 #ifdef SKIPMACRO
850 Rcode1 = Judy1Test(J1, J1index);
851 #else
852 J1T(Rcode1, J1, J1index);
853 #endif // SKIPMACRO
854 if (Rcode1 != 0)
855 FAILURE("J1NE returned non-empty Index =", J1index);
856
857 #ifdef SKIPMACRO
858 PValue = (PWord_t)JudyLGet(JL, JLindex);
859 #else
860 JLG(PValue, JL, JLindex);
861 #endif // SKIPMACRO
862 if (PValue != (Word_t *) NULL)
863 FAILURE("JLNE returned non-empty Index =", JLindex);
864
865 Seed1 = GetNextIndex(Seed1);
866 J1index = JLindex = Seed1;
867 }
868 return(0);
869 }
870
871
872 // Routine to JudyPrevEmpty routines
873
874 #undef __FUNCTI0N__
875 #define __FUNCTI0N__ "TestJudyPrevEmpty"
876
877 int
TestJudyPrevEmpty(void * J1,void * JL,Word_t HighIndex,Word_t Elements)878 TestJudyPrevEmpty(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
879 {
880 Word_t elm;
881 Word_t JLindex, J1index;
882 Word_t Seed1;
883 int Rcode1;
884 int RcodeL;
885
886 // Set 1st search to ..
887 Seed1 = HighIndex;
888 J1index = JLindex = Seed1;
889
890 for (elm = 0; elm < Elements; elm++)
891 {
892 Word_t *PValue;
893 Word_t JPIndex;
894
895 JPIndex = J1index;
896
897 if (pFlag) { printf("JPE: %8lu\t0x%lx\n", elm, JPIndex); }
898
899 J1PE(Rcode1, J1, J1index); // Rcode = Judy1PrevEmpty(J1, &J1index, PJE0)
900
901 // Find next Empty Index, JLindex is modified by JLPE
902 JLPE(RcodeL, JL, JLindex); // RcodeL = JudyLPrevEmpty(JL, &JLindex, PJE0)
903 if ((RcodeL != 1) || (Rcode1 != 1))
904 {
905 printf("RcodeL = %d, Rcode1 = %d, Index1 = 0x%lx, IndexL = 0x%lx\n",
906 RcodeL, Rcode1, J1index, JLindex);
907 FAILURE("Judy*PrevEmpty Rcode* != 1 =", RcodeL);
908 }
909
910 if (J1index != JLindex)
911 FAILURE("JLPE != J1PE returned index at", elm);
912
913 #ifdef SKIPMACRO
914 Rcode1 = Judy1Test(J1, J1index);
915 #else
916 J1T(Rcode1, J1, J1index);
917 #endif // SKIPMACRO
918 if (Rcode1 != 0)
919 FAILURE("J1PE returned non-empty Index =", J1index);
920
921 #ifdef SKIPMACRO
922 PValue = (PWord_t)JudyLGet(JL, JLindex);
923 #else
924 JLG(PValue, JL, JLindex);
925 #endif // SKIPMACRO
926 if (PValue != (Word_t *) NULL)
927 FAILURE("JLPE returned non-empty Index =", JLindex);
928
929 Seed1 = GetNextIndex(Seed1);
930 J1index = JLindex = Seed1;
931 }
932 return(0);
933 }
934
935 #undef __FUNCTI0N__
936 #define __FUNCTI0N__ "TestJudyDel"
937
938 int
TestJudyDel(void ** J1,void ** JL,void ** JH,Word_t Seed,Word_t Elements)939 TestJudyDel(void **J1, void **JL, void **JH, Word_t Seed, Word_t Elements)
940 {
941 Word_t TstIndex;
942 Word_t elm;
943 Word_t Seed1;
944 int Rcode;
945
946 // Only delete half of those inserted
947 for (Seed1 = Seed, elm = 0; elm < (Elements / 2); elm++)
948 {
949 Seed1 = GetNextIndex(Seed1);
950
951 if (DFlag)
952 TstIndex = Swizzle(Seed1);
953 else
954 TstIndex = Seed1;
955
956 if (pFlag) { printf("Del: %8lu\t0x%lx\n", elm, TstIndex); }
957
958 TotalDel++;
959
960 J1U(Rcode, *J1, TstIndex);
961 if (Rcode != 1)
962 FAILURE("Judy1Unset ret Rcode != 1", Rcode);
963
964 JLD(Rcode, *JL, TstIndex);
965 if (Rcode != 1)
966 FAILURE("JudyLDel ret Rcode != 1", Rcode);
967
968 JHSD(Rcode, *JH, (void *)(&TstIndex), sizeof(Word_t));
969 if (Rcode != 1)
970 FAILURE("JudyHSDel ret Rcode != 1", Rcode);
971
972 TotalPop--;
973 }
974 return(0);
975 }
976
977 // Routine to get next size of Indexes
978 int // return 1 if last number
NextNumb(Word_t * PNumber,double * PDNumb,double DMult,Word_t MaxNumb)979 NextNumb(Word_t * PNumber, // pointer to returned next number
980 double *PDNumb, // Temp double of above
981 double DMult, // Multiplier
982 Word_t MaxNumb) // Max number to return
983 {
984 Word_t num;
985
986 // Save prev number
987 Word_t PrevNumb = *PNumber;
988
989 // Verify integer number increased
990 for (num = 0; num < 1000; num++)
991 {
992 // Calc next number
993 *PDNumb *= DMult;
994
995 // Return it in integer format
996 *PNumber = (Word_t) (*PDNumb + 0.5);
997
998 if (*PNumber != PrevNumb)
999 break;
1000 }
1001
1002 // Verify it did exceed max ulong
1003 if ((*PDNumb + 0.5) > (double)(-1UL))
1004 {
1005 // It did, so return max number
1006 *PNumber = -1UL;
1007 return (1); // flag it
1008 }
1009
1010 // Verify it did not exceed max number
1011 if ((*PDNumb + 0.5) > (double)MaxNumb)
1012 {
1013 // it did, so return max
1014 *PNumber = MaxNumb;
1015 return(1); // flag it
1016 }
1017 return(0); // more available
1018 }
1019