« back to all changes in this revision
Viewing changes to test/manual/Judy1LTime.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Troy Heber
- Date: 2005-03-22 06:55:53 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20050322065553-syjpkd48r4re18dn
Tags: 1.0.1-5
* Moving LGPL link in copyright back to LGPL-2.1
* Cleanup of debian/rules: removed explicit refs to 32-bit archs, removed
unnecessary nostrip, using --man dir to install man pages, moving from
dh_movefiles to dh_install.
- files added:
- AUTHORS
- autom4te.cache
- doc/man
- doc/man/man3
- src/JudyHS
- src/obj
- test/Centrino_1.3Mhz_Plots
- files removed:
- Makefile.multi
- make_includes
- test/manual
- files modified:
- COPYING
added
removed
test/manual/Judy1LTime.c
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
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.
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.
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
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
char 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
if (NextNumb(&numb, &sum, Mult, nElms))
521
break;
522
523
// Get memory for measurements
524
Pms = (Pms_t) calloc(Groups, sizeof(ms_t));
525
526
// Now calculate number of Indexes for each measurement point
527
numb = sum = 1;
528
prevnumb = 0;
529
for (grp = 0; grp < Groups; grp++)
530
{
531
Pms[grp].ms_delta = numb - prevnumb;
532
prevnumb = numb;
533
534
NextNumb(&numb, &sum, Mult, nElms);
535
}
536
} // Groups = number of sizes
537
538
//============================================================
539
// PRINT HEADER TO PERFORMANCE TIMERS
540
//============================================================
541
542
printf("# COLHEAD 1 Population\n");
543
printf("# COLHEAD 2 Measurments\n");
544
printf("# COLHEAD 3 J1S\n");
545
printf("# COLHEAD 4 JLI\n");
546
printf("# COLHEAD 5 J1T\n");
547
printf("# COLHEAD 6 JLG\n");
548
549
Col = 7;
550
if (IFlag)
551
{
552
printf("# COLHEAD %d J1S-dup\n", Col++);
553
printf("# COLHEAD %d JLI-dup\n", Col++);
554
}
555
if (CFlag)
556
{
557
printf("# COLHEAD %d J1C\n", Col++);
558
printf("# COLHEAD %d JLC\n", Col++);
559
}
560
if (vFlag)
561
{
562
printf("# COLHEAD %d J1N\n", Col++);
563
printf("# COLHEAD %d JLN\n", Col++);
564
printf("# COLHEAD %d J1P\n", Col++);
565
printf("# COLHEAD %d JLP\n", Col++);
566
printf("# COLHEAD %d J1NE\n", Col++);
567
printf("# COLHEAD %d JLNE\n", Col++);
568
printf("# COLHEAD %d J1PE\n", Col++);
569
printf("# COLHEAD %d JLPE\n", Col++);
570
}
571
if (dFlag)
572
{
573
printf("# COLHEAD %d J1U\n", Col++);
574
printf("# COLHEAD %d JLD\n", Col++);
575
}
576
printf("# COLHEAD %d J1MU/I\n", Col++);
577
printf("# COLHEAD %d JLMU/I\n", Col++);
578
if (aFlag)
579
{
580
printf("# COLHEAD %d J1MA/I\n", Col++);
581
printf("# COLHEAD %d JLMA/I\n", Col++);
582
}
583
printf("# COLHEAD %d HEAP/I\n", Col++);
584
585
printf("# %s\n", Judy1MallocSizes);
586
printf("# %s\n", JudyLMallocSizes);
587
588
printf("# Pop1 Measmts J1S JLI J1T JLG");
589
590
if (IFlag)
591
printf(" dupJ1S dupJLI");
592
593
if (CFlag)
594
printf(" J1C JLC");
595
596
if (vFlag)
597
printf(" J1N JLN J1P JLP J1NE JLNE J1PE JLPE");
598
599
if (dFlag)
600
printf(" J1U JLD");
601
602
printf(" J1MU/I JLMU/I");
603
if (aFlag)
604
{
605
printf(" J1MA/I JLMA/I");
606
}
607
608
printf(" HEAP/I");
609
610
printf("\n");
611
612
//============================================================
613
// BEGIN TESTS AT EACH GROUP SIZE
614
//============================================================
615
616
// Get the kicker to test the LFSR
617
FirstSeed = Seed = StartSeed & (RandomBit * 2 - 1);
618
619
STARTmem;
620
for (Pop1 = grp = 0; grp < Groups; grp++)
621
{
622
Word_t LowIndex, HighIndex;
623
Word_t Delta;
624
Word_t NewSeed;
625
626
Delta = Pms[grp].ms_delta;
627
628
// Test J1S, JLI
629
NewSeed = TestJudyIns(&J1, &JL, Seed, Delta);
630
631
// Accumulate the Total population of arrays
632
Pop1 += Delta;
633
Meas = Pop1;
634
635
// Only test the maximum of TValues if not zero
636
if (TValues)
637
Meas = (Pop1 < TValues) ? Pop1 : TValues;
638
639
printf("%10lu %9lu", Pop1, Meas);
640
printf(" %6.3f", DeltaUSec1);
641
printf(" %6.3f", DeltaUSecL);
642
643
// Test J1T, JLG
644
645
LowIndex = TestJudyGet(J1, JL, FirstSeed, Meas);
646
printf(" %6.3f", DeltaUSec1);
647
printf(" %6.3f", DeltaUSecL);
648
649
// Test J1T, JLI - duplicates
650
651
if (IFlag)
652
{
653
LowIndex = TestJudyDup(&J1, &JL, FirstSeed, Meas);
654
printf(" %6.3f", DeltaUSec1);
655
printf(" %6.3f", DeltaUSecL);
656
}
657
if (CFlag)
658
{
659
TestJudyCount(J1, JL, LowIndex, Meas);
660
printf(" %6.3f", DeltaUSec1);
661
printf(" %6.3f", DeltaUSecL);
662
}
663
if (vFlag)
664
{
665
// Test J1N, JLN
666
HighIndex = TestJudyNext(J1, JL, LowIndex, Meas);
667
printf(" %6.3f", DeltaUSec1);
668
printf(" %6.3f", DeltaUSecL);
669
670
// Test J1P, JLP
671
TestJudyPrev(J1, JL, HighIndex, Meas);
672
printf(" %6.3f", DeltaUSec1);
673
printf(" %6.3f", DeltaUSecL);
674
675
// Test J1NE, JLNE
676
TestJudyNextEmpty(J1, JL, LowIndex, Meas);
677
printf(" %6.3f", DeltaUSec1);
678
printf(" %6.3f", DeltaUSecL);
679
680
// Test J1PE, JLPE
681
TestJudyPrevEmpty(J1, JL, HighIndex, Meas);
682
printf(" %6.3f", DeltaUSec1);
683
printf(" %6.3f", DeltaUSecL);
684
}
685
686
// Test J1U, JLD
687
if (dFlag)
688
{
689
TestJudyDel(&J1, &JL, FirstSeed, Meas);
690
printf(" %6.3f", DeltaUSec1);
691
printf(" %6.3f", DeltaUSecL);
692
693
// Now put them back
694
TestJudyIns(&J1, &JL, FirstSeed, Meas);
695
}
696
697
// Advance Index number set
698
Seed = NewSeed;
699
700
// Print the number of bytes used per Index
701
printf(" %6.3f", (double)Judy1MemUsed(J1) / (double)Pop1);
702
printf(" %6.3f", (double)JudyLMemUsed(JL) / (double)Pop1);
703
if (aFlag)
704
{
705
printf(" %6.3f", (double)Judy1MemActive(J1) / (double)Pop1);
706
printf(" %6.3f", (double)JudyLMemActive(JL) / (double)Pop1);
707
}
708
709
ENDmem;
710
printf(" %6.3f", DeltaMem / (double)Pop1);
711
printf("\n");
712
fflush(NULL); // assure data gets to file in case malloc fail
713
}
714
715
JLC(CountL, JL, 0, -1); // get the counts
716
J1C(Count1, J1, 0, -1);
717
718
if (JLFlag && J1Flag)
719
{
720
if (CountL != Count1)
721
FAILURE("Judy1/LCount not equal", Count1);
722
}
723
724
if (Count1)
725
{
726
STARTTm(tm1);
727
J1FA(Bytes, J1); // Free the Judy1 Array
728
ENDTm(DeltaUSec1, tm1);
729
DeltaUSec1 /= (double)Count1;
730
731
printf("# Judy1FreeArray: %lu, %0.3f bytes/Index, %0.3f USec/Index\n",
732
Count1, (double)Bytes / (double)Count1, DeltaUSec1);
733
}
734
735
if (CountL)
736
{
737
STARTTm(tm1);
738
JLFA(Bytes, JL); // Free the JudyL Array
739
ENDTm(DeltaUSecL, tm1);
740
DeltaUSecL /= (double)CountL;
741
742
printf("# JudyLFreeArray: %lu, %0.3f bytes/Index, %0.3f USec/Index\n",
743
CountL, (double)Bytes / (double)CountL, DeltaUSecL);
744
}
745
exit(0);
746
}
747
748
#undef __FUNCTI0N__
749
#define __FUNCTI0N__ "TestJudyIns"
750
751
Word_t
752
TestJudyIns(void **J1, void **JL, Word_t Seed, Word_t Elements)
753
{
754
TIMER_vars(tm1); // declare timer variables
755
Word_t TstIndex;
756
Word_t elm;
757
Word_t *PValue;
758
Word_t Seed1 = 0;
759
int Rc;
760
761
double DDel;
762
Word_t icnt;
763
Word_t lp;
764
Word_t Loops;
765
766
if (Elements < 100)
767
Loops = (MAXLOOPS / Elements) + MINLOOPS;
768
else
769
Loops = 1;
770
771
if (lFlag)
772
Loops = 1;
773
774
// Judy1Set timings
775
776
if (J1Flag)
777
{
778
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
779
{
780
if (lp != 0)
781
{
782
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
783
{
784
Seed1 = GetNextIndex(Seed1);
785
786
if (DFlag)
787
TstIndex = Swizzle(Seed1);
788
else
789
TstIndex = Seed1;
790
791
J1U(Rc, *J1, TstIndex);
792
}
793
}
794
795
STARTTm(tm1);
796
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
797
{
798
Seed1 = GetNextIndex(Seed1);
799
800
if (DFlag)
801
TstIndex = Swizzle(Seed1);
802
else
803
TstIndex = Seed1;
804
805
J1S(Rc, *J1, TstIndex);
806
if (Rc == 0)
807
FAILURE("Judy1Set failed - DUP Index at", elm);
808
}
809
ENDTm(DeltaUSec1, tm1);
810
811
if (DDel > DeltaUSec1)
812
{
813
icnt = ICNT;
814
DDel = DeltaUSec1;
815
}
816
else
817
{
818
if (--icnt == 0)
819
break;
820
}
821
}
822
DeltaUSec1 = DDel / (double)Elements;
823
}
824
825
// JudyLIns timings
826
827
if (JLFlag)
828
{
829
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
830
{
831
if (lp != 0)
832
{
833
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
834
{
835
Seed1 = GetNextIndex(Seed1);
836
837
if (DFlag)
838
TstIndex = Swizzle(Seed1);
839
else
840
TstIndex = Seed1;
841
842
JLD(Rc, *JL, TstIndex);
843
}
844
}
845
846
STARTTm(tm1);
847
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
848
{
849
Seed1 = GetNextIndex(Seed1);
850
851
if (DFlag)
852
TstIndex = Swizzle(Seed1);
853
else
854
TstIndex = Seed1;
855
856
JLI(PValue, *JL, TstIndex);
857
if (*PValue == TstIndex)
858
FAILURE("JudyLIns failed - DUP Index", TstIndex);
859
860
*PValue = TstIndex; // save Index in Value
861
}
862
ENDTm(DeltaUSecL, tm1);
863
DeltaUSecL /= Elements;
864
865
if (DDel > DeltaUSecL)
866
{
867
icnt = ICNT;
868
DDel = DeltaUSecL;
869
}
870
else
871
{
872
if (--icnt == 0)
873
break;
874
}
875
}
876
}
877
return (Seed1); // New seed
878
}
879
880
#undef __FUNCTI0N__
881
#define __FUNCTI0N__ "TestJudyDup"
882
883
Word_t
884
TestJudyDup(void **J1, void **JL, Word_t Seed, Word_t Elements)
885
{
886
TIMER_vars(tm1); // declare timer variables
887
Word_t LowIndex = ~0UL;
888
Word_t TstIndex;
889
Word_t elm;
890
Word_t *PValue;
891
Word_t Seed1;
892
int Rc;
893
894
double DDel;
895
Word_t icnt;
896
Word_t lp;
897
Word_t Loops;
898
899
Loops = (MAXLOOPS / Elements) + MINLOOPS;
900
901
if (J1Flag)
902
{
903
LowIndex = ~0UL;
904
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
905
{
906
STARTTm(tm1);
907
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
908
{
909
Seed1 = GetNextIndex(Seed1);
910
911
if (DFlag)
912
TstIndex = Swizzle(Seed1);
913
else
914
TstIndex = Seed1;
915
916
if (TstIndex < LowIndex)
917
LowIndex = TstIndex;
918
919
J1S(Rc, *J1, TstIndex);
920
if (Rc != 0)
921
FAILURE("Judy1Test Rc != 0", (Word_t)Rc);
922
}
923
ENDTm(DeltaUSec1, tm1);
924
925
if (DDel > DeltaUSec1)
926
{
927
icnt = ICNT;
928
DDel = DeltaUSec1;
929
}
930
else
931
{
932
if (--icnt == 0)
933
break;
934
}
935
}
936
DeltaUSec1 = DDel / (double)Elements;
937
}
938
939
icnt = ICNT;
940
941
if (JLFlag)
942
{
943
LowIndex = ~0UL;
944
for (DDel = 1e40, lp = 0; lp < Loops; lp++)
945
{
946
STARTTm(tm1);
947
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
948
{
949
Seed1 = GetNextIndex(Seed1);
950
951
if (DFlag)
952
TstIndex = Swizzle(Seed1);
953
else
954
TstIndex = Seed1;
955
956
if (TstIndex < LowIndex)
957
LowIndex = TstIndex;
958
959
JLI(PValue, *JL, TstIndex);
960
if (PValue == (Word_t *)NULL)
961
FAILURE("JudyLGet ret PValue = NULL", 0L);
962
if (*PValue != TstIndex)
963
FAILURE("JudyLGet ret wrong Value at", elm);
964
}
965
ENDTm(DeltaUSecL, tm1);
966
967
if (DDel > DeltaUSecL)
968
{
969
icnt = ICNT;
970
DDel = DeltaUSecL;
971
}
972
else
973
{
974
if (--icnt == 0)
975
break;
976
}
977
}
978
DeltaUSecL = DDel / (double)Elements;
979
}
980
981
return (LowIndex);
982
}
983
984
#undef __FUNCTI0N__
985
#define __FUNCTI0N__ "TestJudyGet"
986
987
Word_t
988
TestJudyGet(void *J1, void *JL, Word_t Seed, Word_t Elements)
989
{
990
TIMER_vars(tm1); // declare timer variables
991
Word_t LowIndex = ~0UL;
992
Word_t TstIndex;
993
Word_t elm;
994
Word_t *PValue;
995
Word_t Seed1;
996
int Rc;
997
998
double DDel;
999
Word_t icnt;
1000
Word_t lp;
1001
Word_t Loops;
1002
1003
Loops = (MAXLOOPS / Elements) + MINLOOPS;
1004
1005
if (J1Flag)
1006
{
1007
LowIndex = ~0UL;
1008
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1009
{
1010
STARTTm(tm1);
1011
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1012
{
1013
Seed1 = GetNextIndex(Seed1);
1014
1015
if (DFlag)
1016
TstIndex = Swizzle(Seed1);
1017
else
1018
TstIndex = Seed1;
1019
1020
if (TstIndex < LowIndex)
1021
LowIndex = TstIndex;
1022
1023
J1T(Rc, J1, TstIndex);
1024
if (Rc != 1)
1025
FAILURE("Judy1Test Rc != 1", (Word_t)Rc);
1026
}
1027
ENDTm(DeltaUSec1, tm1);
1028
1029
if (DDel > DeltaUSec1)
1030
{
1031
icnt = ICNT;
1032
DDel = DeltaUSec1;
1033
}
1034
else
1035
{
1036
if (--icnt == 0)
1037
break;
1038
}
1039
}
1040
DeltaUSec1 = DDel / (double)Elements;
1041
}
1042
1043
icnt = ICNT;
1044
1045
if (JLFlag)
1046
{
1047
LowIndex = ~0UL;
1048
for (DDel = 1e40, lp = 0; lp < Loops; lp++)
1049
{
1050
STARTTm(tm1);
1051
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1052
{
1053
Seed1 = GetNextIndex(Seed1);
1054
1055
if (DFlag)
1056
TstIndex = Swizzle(Seed1);
1057
else
1058
TstIndex = Seed1;
1059
1060
if (TstIndex < LowIndex)
1061
LowIndex = TstIndex;
1062
1063
JLG(PValue, JL, TstIndex);
1064
if (PValue == (Word_t *)NULL)
1065
FAILURE("JudyLGet ret PValue = NULL", 0L);
1066
if (*PValue != TstIndex)
1067
FAILURE("JudyLGet ret wrong Value at", elm);
1068
}
1069
ENDTm(DeltaUSecL, tm1);
1070
1071
if (DDel > DeltaUSecL)
1072
{
1073
icnt = ICNT;
1074
DDel = DeltaUSecL;
1075
}
1076
else
1077
{
1078
if (--icnt == 0)
1079
break;
1080
}
1081
}
1082
DeltaUSecL = DDel / (double)Elements;
1083
}
1084
1085
return (LowIndex);
1086
}
1087
1088
#undef __FUNCTI0N__
1089
#define __FUNCTI0N__ "TestJudyCount"
1090
1091
int
1092
TestJudyCount(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
1093
{
1094
TIMER_vars(tm1); // declare timer variables
1095
Word_t elm;
1096
Word_t Count1, CountL;
1097
Word_t TstIndex = LowIndex;
1098
int Rc;
1099
1100
double DDel;
1101
Word_t icnt;
1102
Word_t lp;
1103
Word_t Loops;
1104
1105
Loops = (MAXLOOPS / Elements) + MINLOOPS;
1106
1107
if (J1Flag)
1108
{
1109
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1110
{
1111
TstIndex = LowIndex;
1112
STARTTm(tm1);
1113
for (elm = 0; elm < Elements; elm++)
1114
{
1115
J1C(Count1, J1, LowIndex, TstIndex);
1116
1117
if (Count1 != (elm + 1))
1118
FAILURE("J1C at", elm);
1119
1120
J1N(Rc, J1, TstIndex);
1121
}
1122
ENDTm(DeltaUSec1, tm1);
1123
1124
if (DDel > DeltaUSec1)
1125
{
1126
icnt = ICNT;
1127
DDel = DeltaUSec1;
1128
}
1129
else
1130
{
1131
if (--icnt == 0)
1132
break;
1133
}
1134
}
1135
DeltaUSec1 = DDel / (double)Elements;
1136
}
1137
1138
if (JLFlag)
1139
{
1140
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1141
{
1142
TstIndex = LowIndex;
1143
STARTTm(tm1);
1144
for (elm = 0; elm < Elements; elm++)
1145
{
1146
Word_t *PValue;
1147
1148
JLC(CountL, JL, LowIndex, TstIndex);
1149
1150
if (CountL != (elm + 1))
1151
FAILURE("JLC at", elm);
1152
1153
JLN(PValue, JL, TstIndex);
1154
}
1155
ENDTm(DeltaUSecL, tm1);
1156
1157
if (DDel > DeltaUSecL)
1158
{
1159
icnt = ICNT;
1160
DDel = DeltaUSecL;
1161
}
1162
else
1163
{
1164
if (--icnt == 0)
1165
break;
1166
}
1167
}
1168
DeltaUSecL = DDel / (double)Elements;
1169
}
1170
1171
return (0);
1172
}
1173
1174
#undef __FUNCTI0N__
1175
#define __FUNCTI0N__ "TestJudyNext"
1176
1177
Word_t
1178
TestJudyNext(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
1179
{
1180
TIMER_vars(tm1); // declare timer variables
1181
Word_t elm;
1182
1183
double DDel;
1184
Word_t icnt;
1185
Word_t lp;
1186
Word_t Loops;
1187
Word_t Jindex;
1188
1189
Loops = (MAXLOOPS / Elements) + MINLOOPS;
1190
1191
if (J1Flag)
1192
{
1193
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1194
{
1195
int Rc;
1196
Jindex = LowIndex;
1197
1198
STARTTm(tm1);
1199
J1F(Rc, J1, Jindex);
1200
1201
for (elm = 0; elm < Elements; elm++)
1202
{
1203
if (Rc != 1)
1204
FAILURE("Judy1Next Rc != 1 =", (Word_t)Rc);
1205
1206
J1N(Rc, J1, Jindex); // Get next one
1207
}
1208
ENDTm(DeltaUSec1, tm1);
1209
1210
if (DDel > DeltaUSec1)
1211
{
1212
icnt = ICNT;
1213
DDel = DeltaUSec1;
1214
}
1215
else
1216
{
1217
if (--icnt == 0)
1218
break;
1219
}
1220
}
1221
DeltaUSec1 = DDel / (double)Elements;
1222
}
1223
1224
if (JLFlag)
1225
{
1226
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1227
{
1228
Word_t *PValue;
1229
1230
// Get an Index low enough for Elements
1231
Jindex = LowIndex;
1232
1233
STARTTm(tm1);
1234
JLF(PValue, JL, Jindex);
1235
1236
for (elm = 0; elm < Elements; elm++)
1237
{
1238
if (PValue == NULL)
1239
FAILURE("JudyLNext ret NULL PValue at", elm);
1240
1241
JLN(PValue, JL, Jindex); // Get next one
1242
}
1243
ENDTm(DeltaUSecL, tm1);
1244
1245
if (DDel > DeltaUSecL)
1246
{
1247
icnt = ICNT;
1248
DDel = DeltaUSecL;
1249
}
1250
else
1251
{
1252
if (--icnt == 0)
1253
break;
1254
}
1255
}
1256
DeltaUSecL = DDel / (double)Elements;
1257
}
1258
1259
// perhaps a check should be done here -- if I knew what to expect.
1260
return (Jindex); // return last one
1261
}
1262
1263
#undef __FUNCTI0N__
1264
#define __FUNCTI0N__ "TestJudyPrev"
1265
1266
int
1267
TestJudyPrev(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
1268
{
1269
TIMER_vars(tm1); // declare timer variables
1270
Word_t elm;
1271
1272
double DDel;
1273
Word_t icnt;
1274
Word_t lp;
1275
Word_t Loops;
1276
1277
Loops = (MAXLOOPS / Elements) + MINLOOPS;
1278
1279
if (J1Flag)
1280
{
1281
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1282
{
1283
Word_t J1index = HighIndex;
1284
int Rc;
1285
1286
STARTTm(tm1);
1287
J1L(Rc, J1, J1index);
1288
1289
for (elm = 0; elm < Elements; elm++)
1290
{
1291
if (Rc != 1)
1292
FAILURE("Judy1Prev Rc != 1 =", (Word_t)Rc);
1293
1294
J1P(Rc, J1, J1index); // Get previous one
1295
}
1296
ENDTm(DeltaUSec1, tm1);
1297
1298
if (DDel > DeltaUSec1)
1299
{
1300
icnt = ICNT;
1301
DDel = DeltaUSec1;
1302
}
1303
else
1304
{
1305
if (--icnt == 0)
1306
break;
1307
}
1308
}
1309
DeltaUSec1 = DDel / (double)Elements;
1310
}
1311
1312
if (JLFlag)
1313
{
1314
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1315
{
1316
Word_t *PValue;
1317
Word_t JLindex = HighIndex;
1318
1319
STARTTm(tm1);
1320
JLL(PValue, JL, JLindex);
1321
1322
for (elm = 0; elm < Elements; elm++)
1323
{
1324
if (PValue == NULL)
1325
FAILURE("JudyLPrev ret NULL PValue at", elm);
1326
1327
JLP(PValue, JL, JLindex); // Get previous one
1328
}
1329
ENDTm(DeltaUSecL, tm1);
1330
1331
if (DDel > DeltaUSecL)
1332
{
1333
icnt = ICNT;
1334
DDel = DeltaUSecL;
1335
}
1336
else
1337
{
1338
if (--icnt == 0)
1339
break;
1340
}
1341
}
1342
DeltaUSecL = DDel / (double)Elements;
1343
}
1344
1345
// perhaps a check should be done here -- if I knew what to expect.
1346
return (0);
1347
}
1348
1349
#undef __FUNCTI0N__
1350
#define __FUNCTI0N__ "TestJudyNextEmpty"
1351
1352
// Returns number of consecutive Indexes
1353
Word_t
1354
TestJudyNextEmpty(void *J1, void *JL, Word_t LowIndex, Word_t Elements)
1355
{
1356
TIMER_vars(tm1); // declare timer variables
1357
Word_t elm;
1358
1359
double DDel;
1360
Word_t icnt;
1361
Word_t lp;
1362
Word_t Loops;
1363
int Rc; // Return code
1364
1365
Loops = (MAXLOOPS / Elements) + MINLOOPS;
1366
1367
if (J1Flag)
1368
{
1369
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1370
{
1371
Word_t Seed1 = LowIndex;
1372
1373
STARTTm(tm1);
1374
for (elm = 0; elm < Elements; elm++)
1375
{
1376
Word_t J1index;
1377
J1index = Seed1;
1378
1379
// Find next Empty Index, J1index is modified by J1NE
1380
J1NE(Rc, J1, J1index); // Rc = Judy1NextEmpty(J1, &J1index,PJE0)
1381
1382
if (Rc != 1)
1383
FAILURE("Judy1NextEmpty Rcode != 1 =", (Word_t)Rc);
1384
1385
Seed1 = GetNextIndex(Seed1);
1386
}
1387
ENDTm(DeltaUSec1, tm1);
1388
1389
if (DDel > DeltaUSec1)
1390
{
1391
icnt = ICNT;
1392
DDel = DeltaUSec1;
1393
}
1394
else
1395
{
1396
if (--icnt == 0)
1397
break;
1398
}
1399
}
1400
DeltaUSec1 = DDel / (double)Elements;
1401
}
1402
1403
if (JLFlag)
1404
{
1405
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1406
{
1407
Word_t Seed1 = LowIndex;
1408
1409
STARTTm(tm1);
1410
for (elm = 0; elm < Elements; elm++)
1411
{
1412
Word_t JLindex;
1413
JLindex = Seed1;
1414
1415
// Find next Empty Index, JLindex is modified by JLNE
1416
JLNE(Rc, JL, JLindex); // Rc = JudyLNextEmpty(JL, &JLindex,PJE0)
1417
1418
if (Rc != 1)
1419
FAILURE("JudyLNextEmpty Rcode != 1 =", (Word_t)Rc);
1420
1421
Seed1 = GetNextIndex(Seed1);
1422
}
1423
ENDTm(DeltaUSecL, tm1);
1424
1425
if (DDel > DeltaUSecL)
1426
{
1427
icnt = ICNT;
1428
DDel = DeltaUSecL;
1429
}
1430
else
1431
{
1432
if (--icnt == 0)
1433
break;
1434
}
1435
}
1436
DeltaUSecL = DDel / (double)Elements;
1437
}
1438
1439
return (0);
1440
}
1441
1442
// Routine to time and test JudyPrevEmpty routines
1443
1444
#undef __FUNCTI0N__
1445
#define __FUNCTI0N__ "TestJudyPrevEmpty"
1446
1447
Word_t
1448
TestJudyPrevEmpty(void *J1, void *JL, Word_t HighIndex, Word_t Elements)
1449
{
1450
TIMER_vars(tm1); // declare timer variables
1451
Word_t elm;
1452
1453
double DDel;
1454
Word_t icnt;
1455
Word_t lp;
1456
Word_t Loops;
1457
int Rc;
1458
1459
Loops = (MAXLOOPS / Elements) + MINLOOPS;
1460
1461
if (J1Flag)
1462
{
1463
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1464
{
1465
Word_t Seed1 = HighIndex;
1466
1467
STARTTm(tm1);
1468
for (elm = 0; elm < Elements; elm++)
1469
{
1470
Word_t J1index;
1471
J1index = Seed1;
1472
1473
J1PE(Rc, J1, J1index); // Rc = Judy1PrevEmpty(J1, &J1index,PJE0)
1474
1475
if (Rc != 1)
1476
FAILURE("Judy1PrevEmpty Rc != 1 =", (Word_t)Rc);
1477
1478
Seed1 = GetNextIndex(Seed1);
1479
}
1480
ENDTm(DeltaUSec1, tm1);
1481
1482
if (DDel > DeltaUSec1)
1483
{
1484
icnt = ICNT;
1485
DDel = DeltaUSec1;
1486
}
1487
else
1488
{
1489
if (--icnt == 0)
1490
break;
1491
}
1492
}
1493
DeltaUSec1 = DDel / (double)Elements;
1494
}
1495
1496
if (JLFlag)
1497
{
1498
for (DDel = 1e40, icnt = ICNT, lp = 0; lp < Loops; lp++)
1499
{
1500
Word_t Seed1 = HighIndex;
1501
1502
STARTTm(tm1);
1503
for (elm = 0; elm < Elements; elm++)
1504
{
1505
Word_t JLindex;
1506
JLindex = Seed1;
1507
1508
// Find next Empty Index, JLindex is modified by JLPE
1509
JLPE(Rc, JL, JLindex); // Rc = JudyLPrevEmpty(JL, &JLindex,PJE0)
1510
1511
if (Rc != 1)
1512
FAILURE("JudyLPrevEmpty Rcode != 1 =", (Word_t)Rc);
1513
1514
Seed1 = GetNextIndex(Seed1);
1515
}
1516
ENDTm(DeltaUSecL, tm1);
1517
1518
if (DDel > DeltaUSecL)
1519
{
1520
icnt = ICNT;
1521
DDel = DeltaUSecL;
1522
}
1523
else
1524
{
1525
if (--icnt == 0)
1526
break;
1527
}
1528
}
1529
DeltaUSecL = DDel / (double)Elements;
1530
}
1531
1532
return (0);
1533
}
1534
1535
#undef __FUNCTI0N__
1536
#define __FUNCTI0N__ "TestJudyDel"
1537
1538
int
1539
TestJudyDel(void **J1, void **JL, Word_t Seed, Word_t Elements)
1540
{
1541
TIMER_vars(tm1); // declare timer variables
1542
Word_t TstIndex;
1543
Word_t elm;
1544
Word_t Seed1;
1545
int Rc;
1546
1547
if (J1Flag)
1548
{
1549
STARTTm(tm1);
1550
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1551
{
1552
Seed1 = GetNextIndex(Seed1);
1553
1554
if (DFlag)
1555
TstIndex = Swizzle(Seed1);
1556
else
1557
TstIndex = Seed1;
1558
1559
J1U(Rc, *J1, TstIndex);
1560
if (Rc != 1)
1561
FAILURE("Judy1Unset ret Rcode != 1", (Word_t)Rc);
1562
}
1563
ENDTm(DeltaUSec1, tm1);
1564
DeltaUSec1 /= Elements;
1565
}
1566
1567
STARTTm(tm1);
1568
if (JLFlag)
1569
{
1570
for (Seed1 = Seed, elm = 0; elm < Elements; elm++)
1571
{
1572
Seed1 = GetNextIndex(Seed1);
1573
1574
if (DFlag)
1575
TstIndex = Swizzle(Seed1);
1576
else
1577
TstIndex = Seed1;
1578
1579
JLD(Rc, *JL, TstIndex);
1580
if (Rc != 1)
1581
FAILURE("JudyLDel ret Rcode != 1", (Word_t)Rc);
1582
}
1583
ENDTm(DeltaUSecL, tm1);
1584
DeltaUSecL /= Elements;
1585
}
1586
return (0);
1587
}
1588
1589
// Routine to get next size of Indexes
1590
int // return 1 if last number
1591
NextNumb(Word_t *PNumber, // pointer to returned next number
1592
double *PDNumb, // Temp double of above
1593
double DMult, // Multiplier
1594
Word_t MaxNumb) // Max number to return
1595
{
1596
Word_t num;
1597
1598
// Save prev number
1599
Word_t PrevNumb = *PNumber;
1600
1601
// Verify integer number increased
1602
for (num = 0; num < 1000; num++)
1603
{
1604
// Calc next number
1605
*PDNumb *= DMult;
1606
1607
// Return it in integer format
1608
*PNumber = (Word_t)(*PDNumb + 0.5);
1609
1610
if (*PNumber != PrevNumb)
1611
break;
1612
}
1613
1614
// Verify it did not exceed max number
1615
if ((*PDNumb + 0.5) > (double)MaxNumb)
1616
{
1617
// it did, so return max
1618
*PNumber = MaxNumb;
1619
return (1); // flag it
1620
}
1621
return (0); // more available
1622
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1