« back to all changes in this revision
Viewing changes to test/manual/Judy1LCheck.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Theodore Y. Ts'o
- Date: 2004-01-17 00:04:53 UTC
- Revision ID: james.westby@ubuntu.com-20040117000453-d5sj6uoon2v1g4gf
Tags: upstream-0.0.4
Import upstream version 0.0.4
- files added:
- doc
- doc/ext
- doc/int
- make_includes
- src
- src/Judy1
- src/JudyCommon
- src/JudyL
- src/JudySL
- src/apps
- src/apps/demo
- test
- test/manual
- tool
added
removed
test/manual/Judy1LCheck.c
1
// @(#) $Revision: 4.15 $ $Source: /judy/test/manual/Judy1LCheck.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
#ifndef JU_WIN_IA32
7
#include <unistd.h> // unavailable on Win32, and no getopt().
8
#endif
9
10
#include <stdlib.h> // calloc()
11
#include <math.h> // pow()
12
#include <stdio.h> // printf()
13
14
#include <Judy.h>
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, UL, __FILE__, __FUNCTI0N__, __LINE__); \
21
fprintf(stderr, "Error: %s %lu, file='%s', 'function='%s', line %d\n", \
22
STR, 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, Word_t Seed, Word_t Elements);
38
39
Word_t TestJudyDup(void **J1, void **JL, Word_t Seed, Word_t Elements);
40
41
int TestJudyDel(void **J1, void **JL, Word_t Seed, Word_t Elements);
42
43
Word_t TestJudyGet(void *J1, void *JL, 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
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
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.
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("End of LFSR, Total Population = %lu\n", TotalPop);
185
exit(0);
186
}
187
return(newseed);
188
}
189
190
static Word_t // Placed here so INLINING compilers get to look at it.
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
205
main(int argc, char *argv[])
206
{
207
// Names of Judy Arrays
208
void *J1 = NULL; // Judy1
209
void *JL = NULL; // JudyL
210
211
double Mult;
212
Pms_t Pms;
213
Word_t Seed;
214
Word_t PtsPdec = 10; // points per decade
215
Word_t Groups; // Number of measurement groups
216
Word_t grp;
217
218
char c;
219
extern char *optarg;
220
221
//////////////////////////////////////////////////////////////
222
// PARSE INPUT PARAMETERS
223
//////////////////////////////////////////////////////////////
224
225
while ((c = getopt(argc, argv, "n:S:P:b:L:B:pdDC")) != -1)
226
{
227
switch (c)
228
{
229
case 'n': // Number of elements
230
nElms = strtoul(optarg, NULL, 0); // Size of Linear Array
231
if (nElms == 0)
232
FAILURE("No tests: -n", nElms);
233
234
// Check if more than a trillion (64 bit only)
235
if ((double)nElms > 1e12)
236
FAILURE("Too many Indexes=", nElms);
237
break;
238
239
case 'S': // Step Size, 0 == Random
240
SkipN = strtoul(optarg, NULL, 0);
241
break;
242
243
case 'P': //
244
PtsPdec = strtoul(optarg, NULL, 0);
245
break;
246
247
case 'b': // May not work past 35 bits if changed
248
StartSeed = strtoul(optarg, NULL, 0);
249
break;
250
251
case 'B':
252
BValue = strtoul(optarg, NULL, 0);
253
if (
254
(BValue > (sizeof(Word_t) * 8))
255
||
256
(MagicList[BValue] == 0)
257
)
258
{
259
ErrorFlag++;
260
printf("\nIllegal number of random bits of %lu !!!\n", BValue);
261
}
262
break;
263
264
case 'p': // Print test indexes
265
pFlag = 1;
266
break;
267
268
case 'd': // Delete indexes
269
dFlag = 0;
270
break;
271
272
case 'D': // Swizzle indexes
273
DFlag = 1;
274
break;
275
276
case 'C': // Skip counting test.
277
CFlag = 1;
278
break;
279
280
default:
281
ErrorFlag++;
282
break;
283
}
284
}
285
286
if (ErrorFlag)
287
{
288
printf("\n%s -n# -S# -B# -P# -b # -DRCpd\n\n", argv[0]);
289
printf("Where:\n");
290
printf("-n <#> number of indexes used in tests\n");
291
printf("-C skip JudyCount tests\n");
292
printf("-p print index set - for debug\n");
293
printf("-d do not call JudyDel/Unset\n");
294
printf("-D Swizzle data (mirror)\n");
295
printf("-S <#> index skip amount, 0 = random\n");
296
printf("-B <#> # bits-1 in random number generator\n");
297
printf("-P <#> number measurement points per decade\n");
298
printf("\n");
299
300
exit(1);
301
}
302
// Set number of Random bits in LFSR
303
RandomBit = 1UL << (BValue - 1);
304
Magic = MagicList[BValue];
305
306
if (nElms > ((RandomBit-2) * 2))
307
{
308
printf("# Number = -n%lu of Indexes reduced to max expanse of Random numbers\n", nElms);
309
nElms = ((RandomBit-2) * 2);
310
}
311
312
printf("\n%s -n%lu -S%lu -B%lu", argv[0], nElms, SkipN, BValue);
313
314
if (DFlag)
315
printf(" -D");
316
if (!dFlag)
317
printf(" -d");
318
if (pFlag)
319
printf(" -p");
320
if (CFlag)
321
printf(" -C");
322
printf("\n\n");
323
324
if (sizeof(Word_t) == 8)
325
printf("%s 64 Bit version\n", argv[0]);
326
else if (sizeof(Word_t) == 4)
327
printf("%s 32 Bit version\n", argv[0]);
328
329
//////////////////////////////////////////////////////////////
330
// CALCULATE NUMBER OF MEASUREMENT GROUPS
331
//////////////////////////////////////////////////////////////
332
333
// Calculate Multiplier for number of points per decade
334
Mult = pow(10.0, 1.0 / (double)PtsPdec);
335
{
336
double sum;
337
Word_t numb, prevnumb;
338
339
// Count number of measurements needed (10K max)
340
sum = numb = 1;
341
for (Groups = 2; Groups < 10000; Groups++)
342
if (NextNumb(&numb, &sum, Mult, nElms))
343
break;
344
345
// Get memory for measurements
346
Pms = (Pms_t) calloc(Groups, sizeof(ms_t));
347
348
// Now calculate number of Indexes for each measurement point
349
numb = sum = 1;
350
prevnumb = 0;
351
for (grp = 0; grp < Groups; grp++)
352
{
353
Pms[grp].ms_delta = numb - prevnumb;
354
prevnumb = numb;
355
356
NextNumb(&numb, &sum, Mult, nElms);
357
}
358
} // Groups = number of sizes
359
360
//////////////////////////////////////////////////////////////
361
// BEGIN TESTS AT EACH GROUP SIZE
362
//////////////////////////////////////////////////////////////
363
364
// Get the kicker to test the LFSR
365
FirstSeed = Seed = StartSeed & (RandomBit * 2 - 1);
366
367
printf("Total Pop Total Ins New Ins Total Del");
368
printf(" J1MU/I JLMU/I\n");
369
370
#ifdef testLFSR
371
{
372
Word_t Seed1 = Seed;
373
374
while(1)
375
{
376
Seed1 = GetNextIndex(Seed1);
377
TotalPop++;
378
if (TotalPop > 40000000000) printf("Total = %lu\n", TotalPop), exit(1);
379
}
380
}
381
#endif // testLFSR
382
383
for (grp = 0; grp < Groups; grp++)
384
{
385
Word_t LowIndex, HighIndex;
386
Word_t Delta;
387
Word_t NewSeed;
388
389
Delta = Pms[grp].ms_delta;
390
391
// Test JLI, J1S
392
NewSeed = TestJudyIns(&J1, &JL, Seed, Delta);
393
394
// Test JLG, J1T
395
LowIndex = TestJudyGet(J1, JL, Seed, Delta);
396
397
// Test JLI, J1S -dup
398
LowIndex = TestJudyDup(&J1, &JL, Seed, Delta);
399
400
// Test JLC, J1C
401
if (!CFlag)
402
{
403
TestJudyCount(J1, JL, LowIndex, Delta);
404
}
405
// Test JLN, J1N
406
HighIndex = TestJudyNext(J1, JL, LowIndex, Delta);
407
408
// Test JLP, J1P
409
TestJudyPrev(J1, JL, HighIndex, Delta);
410
411
// Test JLNE, J1NE
412
TestJudyNextEmpty(J1, JL, LowIndex, Delta);
413
414
// Test JLPE, J1PE
415
TestJudyPrevEmpty(J1, JL, HighIndex, Delta);
416
417
// Test JLD, J1U
418
if (dFlag)
419
{
420
TestJudyDel(&J1, &JL, Seed, Delta);
421
}
422
423
printf("%9lu %9lu %7lu %9lu", TotalPop, TotalIns, Delta, TotalDel);
424
{
425
Word_t Count1, CountL;
426
427
// Print the number of bytes used per Index
428
J1C(Count1, J1, 0, ~0);
429
printf(" %6.3f", (double)Judy1MemUsed(J1) / (double)Count1);
430
JLC(CountL, JL, 0, ~0);
431
printf(" %6.3f", (double)JudyLMemUsed(JL) / (double)CountL);
432
}
433
printf("\n");
434
435
// Advance Index number set
436
Seed = NewSeed;
437
}
438
{
439
Word_t Count1, CountL;
440
Word_t Bytes;
441
442
JLC(CountL, JL, 0, ~0);
443
J1C(Count1, J1, 0, ~0);
444
445
if (CountL != TotalPop)
446
FAILURE("JudyLCount wrong", CountL);
447
448
if (Count1 != TotalPop)
449
FAILURE("Judy1Count wrong", Count1);
450
451
if (TotalPop)
452
{
453
J1FA(Bytes, J1); // Free the Judy1 Array
454
printf("Judy1FreeArray = %6.3f Bytes/Index\n",
455
(double)Bytes / (double)Count1);
456
457
if (pFlag) { printf("J1FA: %8lu\tbytes = %lu\n", TotalPop, Bytes); }
458
459
JLFA(Bytes, JL); // Free the JudyL Array
460
printf("JudyLFreeArray = %6.3f Bytes/Index\n",
461
(double)Bytes / (double)CountL);
462
463
if (pFlag) { printf("JLFA: %8lu\tbytes = %lu\n", TotalPop, Bytes); }
464
465
TotalPop = 0;
466
}
467
}
468
printf("Passed JudyL and Judy1 tests\n");
469
exit(0);
470
}
471
472
#undef __FUNCTI0N__
473
#define __FUNCTI0N__ "TestJudyIns"
474
475
Word_t
476
TestJudyIns(void **J1, void **JL, Word_t Seed, Word_t Elements)
477
{
478
Word_t TstIndex;
479
Word_t elm;
480
Word_t *PValue, *PValue1;
481
Word_t Seed1;
482
int Rcode;
483
484
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
485
{
486
Seed1 = GetNextIndex(Seed1);
487
if (Seed1 == 0)
488
FAILURE("This command not robust if Index == 0", elm);
489
490
if (DFlag)
491
TstIndex = Swizzle(Seed1);
492
else
493
TstIndex = Seed1;
494
495
if (pFlag) { printf("Ins: %8lu\t0x%lx\n", elm, TstIndex); }
496
497
J1S(Rcode, *J1, TstIndex);
498
if (Rcode == JERR)
499
FAILURE("Judy1Set failed at", elm);
500
if (Rcode == 0)
501
FAILURE("Judy1Set failed - DUP Index, population =", TotalPop);
502
503
J1T(Rcode, *J1, TstIndex);
504
if (Rcode != 1)
505
FAILURE("Judy1Test failed - Index missing, population =", TotalPop);
506
507
J1S(Rcode, *J1, TstIndex);
508
if (Rcode != 0)
509
FAILURE("Judy1Set failed - Index missing, population =", TotalPop);
510
511
JLI(PValue, *JL, TstIndex);
512
if (PValue == PJERR)
513
FAILURE("JudyLIns failed at", elm);
514
if (*PValue == TstIndex)
515
FAILURE("JudyLIns failed - DUP Index, population =", TotalPop);
516
517
// Save Index in Value
518
*PValue = TstIndex;
519
520
JLG(PValue1, *JL, TstIndex);
521
if (PValue != PValue1)
522
FAILURE("JudyLGet failed - Index missing, population =", TotalPop);
523
524
JLI(PValue1, *JL, TstIndex);
525
if (PValue != PValue1)
526
{
527
if (*PValue1 != TstIndex)
528
{
529
FAILURE("JudyLIns failed - Index missing, population =", TotalPop);
530
}
531
else
532
{
533
// not ready for this yet! printf("Index moved -- TotalPop = %lu\n", TotalPop);
534
}
535
}
536
TotalPop++;
537
TotalIns++;
538
}
539
return (Seed1); // New seed
540
}
541
542
#undef __FUNCTI0N__
543
#define __FUNCTI0N__ "TestJudyGet"
544
545
Word_t
546
TestJudyGet(void *J1, void *JL, Word_t Seed, Word_t Elements)
547
{
548
Word_t LowIndex = ~0UL;
549
Word_t TstIndex;
550
Word_t elm;
551
Word_t *PValue;
552
Word_t Seed1;
553
int Rcode;
554
555
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
556
{
557
Seed1 = GetNextIndex(Seed1);
558
559
if (DFlag)
560
TstIndex = Swizzle(Seed1);
561
else
562
TstIndex = Seed1;
563
564
if (TstIndex < LowIndex)
565
LowIndex = TstIndex;
566
567
J1T(Rcode, J1, TstIndex);
568
if (Rcode != 1)
569
FAILURE("Judy1Test Rcode != 1", (Word_t) Rcode);
570
571
JLG(PValue, JL, TstIndex);
572
if (PValue == (Word_t *) NULL)
573
FAILURE("JudyLGet ret PValue = NULL", 0L);
574
if (*PValue != TstIndex)
575
FAILURE("JudyLGet ret wrong Value at", elm);
576
}
577
578
return(LowIndex);
579
}
580
581
#undef __FUNCTI0N__
582
#define __FUNCTI0N__ "TestJudyDup"
583
584
Word_t
585
TestJudyDup(void **J1, void **JL, Word_t Seed, Word_t Elements)
586
{
587
Word_t LowIndex = ~0UL;
588
Word_t TstIndex;
589
Word_t elm;
590
Word_t *PValue;
591
Word_t Seed1;
592
int Rcode;
593
594
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
595
{
596
Seed1 = GetNextIndex(Seed1);
597
598
if (DFlag)
599
TstIndex = Swizzle(Seed1);
600
else
601
TstIndex = Seed1;
602
603
if (TstIndex < LowIndex)
604
LowIndex = TstIndex;
605
606
J1S(Rcode, *J1, TstIndex);
607
if (Rcode != 0)
608
FAILURE("Judy1Set Rcode != 0", (Word_t) Rcode);
609
610
JLI(PValue, *JL, TstIndex);
611
if (PValue == (Word_t *) NULL)
612
FAILURE("JudyLIns ret PValue = NULL", 0L);
613
if (*PValue != TstIndex)
614
FAILURE("JudyLIns ret wrong Value at", elm);
615
}
616
617
return(LowIndex);
618
}
619
620
#undef __FUNCTI0N__
621
#define __FUNCTI0N__ "TestJudyCount"
622
623
int
624
TestJudyCount(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
625
{
626
Word_t elm;
627
Word_t Count1, CountL;
628
Word_t TstIndex = LowIndex;
629
int Rcode;
630
631
TstIndex = LowIndex;
632
for (elm = 0; elm < Elements; elm++)
633
{
634
J1C(Count1, J1, LowIndex, TstIndex);
635
if (Count1 == JERR)
636
FAILURE("Judy1Count ret JERR", (Word_t) Count1);
637
638
if (Count1 != (elm + 1))
639
{
640
J1C(CountL, J1, 0, -1);
641
printf("J1C(%lu, J1, 0, -1)\n", CountL);
642
643
JLC(CountL, JL, 0, -1);
644
printf("JLC(%lu, JL, 0, -1)\n", CountL);
645
646
printf("LowIndex = 0x%lx, TstIndex = 0x%lx, diff = %lu\n", LowIndex,
647
TstIndex, TstIndex - LowIndex);
648
JLC(CountL, JL, LowIndex, TstIndex);
649
printf("CountL = %lu, Count1 = %lu, should be: elm + 1 = %lu\n", CountL, Count1, elm + 1);
650
FAILURE("J1C at", elm);
651
}
652
653
JLC(CountL, JL, LowIndex, TstIndex);
654
if (CountL == JERR)
655
FAILURE("JudyLCount ret JERR", (Word_t) CountL);
656
657
if (CountL != (elm + 1)) FAILURE("JLC at", elm);
658
659
J1N(Rcode, J1, TstIndex);
660
}
661
return(0);
662
}
663
664
#undef __FUNCTI0N__
665
#define __FUNCTI0N__ "TestJudyNext"
666
667
Word_t TestJudyNext(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
668
{
669
Word_t JLindex, J1index;
670
Word_t *PValue;
671
Word_t elm;
672
int Rcode;
673
674
// Get an Index low enough for Elements
675
J1index = JLindex = LowIndex;
676
677
JLF(PValue, JL, JLindex);
678
J1F(Rcode, J1, J1index);
679
680
for (elm = 0; elm < Elements; elm++)
681
{
682
if (PValue == NULL)
683
FAILURE("JudyLNext ret NULL PValue at", elm);
684
if (Rcode != 1)
685
FAILURE("Judy1Next Rcode != 1 =", (Word_t) Rcode);
686
if (JLindex != J1index)
687
FAILURE("Judy1Next & Judy1Next ret different PIndex at", elm);
688
689
JLN(PValue, JL, JLindex); // Get next one
690
J1N(Rcode, J1, J1index); // Get next one
691
}
692
// perhaps a check should be done here -- if I knew what to expect.
693
return(JLindex); // return last one
694
}
695
696
697
#undef __FUNCTI0N__
698
#define __FUNCTI0N__ "TestJudyPrev"
699
700
int
701
TestJudyPrev(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
702
{
703
Word_t JLindex, J1index;
704
Word_t *PValue;
705
Word_t elm;
706
int Rcode;
707
708
// Get an Index high enough for Elements
709
J1index = JLindex = HighIndex;
710
711
JLL(PValue, JL, JLindex);
712
J1L(Rcode, J1, J1index);
713
714
for (elm = 0; elm < Elements; elm++)
715
{
716
if (PValue == NULL)
717
FAILURE("JudyLPrev ret NULL PValue at", elm);
718
if (Rcode != 1)
719
FAILURE("Judy1Prev Rcode != 1 =", (Word_t) Rcode);
720
if (JLindex != J1index)
721
FAILURE("Judy1Prev & Judy1Prev ret different PIndex at", elm);
722
723
JLP(PValue, JL, JLindex); // Get previous one
724
J1P(Rcode, J1, J1index); // Get previous one
725
}
726
// perhaps a check should be done here -- if I knew what to expect.
727
return(0);
728
}
729
730
731
#undef __FUNCTI0N__
732
#define __FUNCTI0N__ "TestJudyNextEmpty"
733
734
int
735
TestJudyNextEmpty(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
736
{
737
Word_t elm;
738
Word_t JLindex, J1index;
739
Word_t Seed1;
740
int Rcode; // Return code
741
742
// Set 1st search to ..
743
Seed1 = LowIndex;
744
J1index = JLindex = Seed1;
745
746
for (elm = 0; elm < Elements; elm++)
747
{
748
Word_t *PValue;
749
750
// Find next Empty Index, JLindex is modified by JLNE
751
JLNE(Rcode, JL, JLindex); // Rcode = JudyLNextEmpty(JL, &JLindex, PJE0)
752
if (Rcode != 1)
753
FAILURE("JudyLNextEmpty Rcode != 1 =", (Word_t) Rcode);
754
755
if (pFlag) { printf("JNE: %8lu\t0x%lx\n", elm, JLindex); }
756
757
// Find next Empty Index, J1index is modified by J1NE
758
J1NE(Rcode, J1, J1index); // Rcode = Judy1NextEmpty(J1, &J1index, PJE0)
759
if (Rcode != 1)
760
FAILURE("Judy1NextEmpty Rcode != 1 =", (Word_t) Rcode);
761
762
if (J1index != JLindex)
763
FAILURE("JLNE != J1NE returned index at", elm);
764
765
J1T(Rcode, J1, J1index);
766
if (Rcode != 0)
767
FAILURE("J1NE returned non-empty Index =", J1index);
768
769
JLG(PValue, JL, JLindex);
770
if (PValue != (Word_t *) NULL)
771
FAILURE("JLNE returned non-empty Index =", JLindex);
772
773
Seed1 = GetNextIndex(Seed1);
774
J1index = JLindex = Seed1;
775
}
776
return(0);
777
}
778
779
780
// Routine to JudyPrevEmpty routines
781
782
#undef __FUNCTI0N__
783
#define __FUNCTI0N__ "TestJudyPrevEmpty"
784
785
int
786
TestJudyPrevEmpty(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
787
{
788
Word_t elm;
789
Word_t JLindex, J1index;
790
Word_t Seed1;
791
int Rcode;
792
793
// Set 1st search to ..
794
Seed1 = HighIndex;
795
J1index = JLindex = Seed1;
796
797
for (elm = 0; elm < Elements; elm++)
798
{
799
Word_t *PValue;
800
801
J1PE(Rcode, J1, J1index); // Rcode = Judy1PrevEmpty(J1, &J1index, PJE0)
802
if (Rcode != 1)
803
FAILURE("Judy1PrevEmpty Rcode != 1 =", (Word_t) Rcode);
804
805
if (pFlag) { printf("JPE: %8lu\t0x%lx\n", elm, J1index); }
806
807
// Find next Empty Index, JLindex is modified by JLPE
808
JLPE(Rcode, JL, JLindex); // Rcode = JudyLPrevEmpty(JL, &JLindex, PJE0)
809
if (Rcode != 1)
810
FAILURE("JudyLPrevEmpty Rcode != 1 =", (Word_t) Rcode);
811
812
if (J1index != JLindex)
813
FAILURE("JLPE != J1PE returned index at", elm);
814
815
J1T(Rcode, J1, J1index);
816
if (Rcode != 0)
817
FAILURE("J1PE returned non-empty Index =", J1index);
818
819
JLG(PValue, JL, JLindex);
820
if (PValue != (Word_t *) NULL)
821
FAILURE("JLPE returned non-empty Index =", JLindex);
822
823
Seed1 = GetNextIndex(Seed1);
824
J1index = JLindex = Seed1;
825
}
826
return(0);
827
}
828
829
#undef __FUNCTI0N__
830
#define __FUNCTI0N__ "TestJudyDel"
831
832
int
833
TestJudyDel(void **J1, void **JL, Word_t Seed, Word_t Elements)
834
{
835
Word_t TstIndex;
836
Word_t elm;
837
Word_t Seed1;
838
int Rcode;
839
840
// Only delete half of thoes inserted
841
for (Seed1 = Seed, elm = 0; elm < (Elements / 2); elm++)
842
{
843
Seed1 = GetNextIndex(Seed1);
844
845
if (DFlag)
846
TstIndex = Swizzle(Seed1);
847
else
848
TstIndex = Seed1;
849
850
if (pFlag) { printf("Del: %8lu\t0x%lx\n", elm, TstIndex); }
851
852
TotalDel++;
853
854
J1U(Rcode, *J1, TstIndex);
855
if (Rcode != 1)
856
FAILURE("Judy1Unset ret Rcode != 1", (Word_t) Rcode);
857
858
JLD(Rcode, *JL, TstIndex);
859
if (Rcode != 1)
860
FAILURE("JudyLDel ret Rcode != 1", (Word_t) Rcode);
861
862
TotalPop--;
863
}
864
return(0);
865
}
866
867
// Routine to get next size of Indexes
868
int // return 1 if last number
869
NextNumb(Word_t * PNumber, // pointer to returned next number
870
double *PDNumb, // Temp double of above
871
double DMult, // Multiplier
872
Word_t MaxNumb) // Max number to return
873
{
874
Word_t num;
875
876
// Save prev number
877
Word_t PrevNumb = *PNumber;
878
879
// Verify integer number increased
880
for (num = 0; num < 1000; num++)
881
{
882
// Calc next number
883
*PDNumb *= DMult;
884
885
// Return it in integer format
886
*PNumber = (Word_t) (*PDNumb + 0.5);
887
888
if (*PNumber != PrevNumb)
889
break;
890
}
891
892
// Verify it did exceed max ulong
893
if ((*PDNumb + 0.5) > (double)(-1UL))
894
{
895
// It did, so return max number
896
*PNumber = -1UL;
897
return (1); // flag it
898
}
899
900
// Verify it did not exceed max number
901
if ((*PDNumb + 0.5) > (double)MaxNumb)
902
{
903
// it did, so return max
904
*PNumber = MaxNumb;
905
return(1); // flag it
906
}
907
return(0); // more available
908
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1