« back to all changes in this revision
Viewing changes to src/JudyCommon/JudyByCount.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
src/JudyCommon/JudyByCount.c
1
// Copyright (C) 2000 - 2002 Hewlett-Packard Company
2
//
3
// This program is free software; you can redistribute it and/or modify it
4
// under the term of the GNU Lesser General Public License as published by the
5
// Free Software Foundation; either version 2 of the License, or (at your
6
// option) any later version.
7
//
8
// This program is distributed in the hope that it will be useful, but WITHOUT
9
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
11
// for more details.
12
//
13
// You should have received a copy of the GNU Lesser General Public License
14
// along with this program; if not, write to the Free Software Foundation,
15
// Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
// _________________
17
18
// @(#) $Revision: 4.28 $ $Source: /judy/src/JudyCommon/JudyByCount.c $
19
//
20
// Judy*ByCount() function for Judy1 and JudyL.
21
// Compile with one of -DJUDY1 or -DJUDYL.
22
//
23
// Compile with -DNOSMARTJBB, -DNOSMARTJBU, and/or -DNOSMARTJLB to build a
24
// version with cache line optimizations deleted, for testing.
25
//
26
// Judy*ByCount() is a conceptual although not literal inverse of Judy*Count().
27
// Judy*Count() takes a pair of Indexes, and allows finding the ordinal of a
28
// given Index (that is, its position in the list of valid indexes from the
29
// beginning) as a degenerate case, because in general the count between two
30
// Indexes, inclusive, is not always just the difference in their ordinals.
31
// However, it suffices for Judy*ByCount() to simply be an ordinal-to-Index
32
// mapper.
33
//
34
// Note: Like Judy*Count(), this code must "count sideways" in branches, which
35
// can result in a lot of cache line fills. However, unlike Judy*Count(), this
36
// code does not receive a specific Index, hence digit, where to start in each
37
// branch, so it can't accurately calculate cache line fills required in each
38
// direction. The best it can do is an approximation based on the total
39
// population of the expanse (pop1 from Pjp) and the ordinal of the target
40
// Index (see SETOFFSET()) within the expanse.
41
//
42
// Compile with -DSMARTMETRICS to obtain global variables containing smart
43
// cache line metrics. Note: Don't turn this on simultaneously for this file
44
// and JudyCount.c because they export the same globals.
45
// ****************************************************************************
46
47
#if (! (JUDY1 || JUDYL))
48
Error: One of -DJUDY1 or -DJUDYL must be specified.
49
#endif
50
51
#ifdef JUDY1
52
#include "Judy1.h"
53
#else
54
#include "JudyL.h"
55
#endif
56
57
#include "JudyPrivate1L.h"
58
59
// These are imported from JudyCount.c:
60
//
61
// TBD: Should this be in common code? Exported from a header file?
62
63
#ifdef JUDY1
64
extern Word_t __Judy1JPPop1(const Pjp_t Pjp);
65
#define __JudyJPPop1 __Judy1JPPop1
66
#else
67
extern Word_t __JudyLJPPop1(const Pjp_t Pjp);
68
#define __JudyJPPop1 __JudyLJPPop1
69
#endif
70
71
// Avoid duplicate symbols since this file is multi-compiled:
72
73
#ifdef SMARTMETRICS
74
#ifdef JUDY1
75
Word_t jbb_upward = 0; // counts of directions taken:
76
Word_t jbb_downward = 0;
77
Word_t jbu_upward = 0;
78
Word_t jbu_downward = 0;
79
Word_t jlb_upward = 0;
80
Word_t jlb_downward = 0;
81
#else
82
extern Word_t jbb_upward;
83
extern Word_t jbb_downward;
84
extern Word_t jbu_upward;
85
extern Word_t jbu_downward;
86
extern Word_t jlb_upward;
87
extern Word_t jlb_downward;
88
#endif
89
#endif
90
91
92
// ****************************************************************************
93
// J U D Y 1 B Y C O U N T
94
// J U D Y L B Y C O U N T
95
//
96
// See the manual entry.
97
98
#ifdef JUDY1
99
FUNCTION int Judy1ByCount(
100
#else
101
FUNCTION PPvoid_t JudyLByCount(
102
#endif
103
Pcvoid_t PArray, // root pointer to first branch/leaf in SM.
104
const Word_t Count, // ordinal of Index to find, 1..MAX.
105
Word_t * PIndex, // to return found Index.
106
PJError_t PJError) // optional, for returning error info.
107
{
108
Word_t Count0; // Count, base-0, to match pop0.
109
Word_t JAPtype; // type part of PArray.
110
Word_t state; // current state in SM.
111
Word_t pop1; // of current branch or leaf, or of expanse.
112
Word_t pop1lower; // pop1 of expanses (JPs) below that for Count.
113
Word_t digit; // current word in branch.
114
Word_t jpcount; // JPs in a BranchB subexpanse.
115
long jpnum; // JP number in a branch (base 0).
116
long subexp; // for stepping through layer 1 (subexpanses).
117
int offset; // index ordinal within a leaf, base 0.
118
119
Pjp_t Pjp; // current JP in branch.
120
Pjll_t Pjll; // current Judy linear leaf.
121
122
123
// CHECK FOR EMPTY ARRAY OR NULL PINDEX:
124
125
if (PArray == (Pvoid_t) NULL) JU_RET_NOTFOUND;
126
127
if (PIndex == (PWord_t) NULL)
128
{
129
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
130
JUDY1CODE(return(JERRI );)
131
JUDYLCODE(return(PPJERR);)
132
}
133
134
// Convert Count to Count0; assume special case of Count = 0 maps to ~0, as
135
// desired, to represent the last index in a full array:
136
//
137
// Note: Think of Count0 as a reliable "number of Indexes below the target."
138
139
Count0 = Count - 1;
140
assert((Count || Count0 == ~0)); // ensure CPU is sane about 0 - 1.
141
pop1lower = 0;
142
143
144
// CHECK JAP TYPE:
145
//
146
// Use an if/then for speed rather than a switch, and put the most common cases
147
// first.
148
149
JAPtype = JAPTYPE(PArray);
150
151
if (JAPtype == cJU_JAPBRANCH)
152
{
153
Pjpm_t Pjpm = P_JPM(PArray);
154
155
if (Count0 > (Pjpm->jpm_Pop0)) JU_RET_NOTFOUND; // too high.
156
157
Pjp = &(Pjpm->jpm_JP);
158
pop1 = (Pjpm->jpm_Pop0) + 1;
159
160
goto SMByCount;
161
}
162
163
if (JAPtype == cJU_JAPLEAF)
164
{
165
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
166
167
if (Count0 > Pjlw[0]) JU_RET_NOTFOUND; // too high.
168
169
*PIndex = Pjlw[Count]; // Index, base 1.
170
171
JU_RET_FOUND_JAPLEAF(Pjlw, Pjlw[0] + 1, Count0);
172
}
173
174
#if (LOW_POP && JUDYL)
175
if (JAPtype == cJL_JAPLEAF_POPU1)
176
{
177
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
178
179
if (Count0) JU_RET_NOTFOUND; // wrong value.
180
181
*PIndex = Pjlw[0];
182
183
return((PPvoid_t) ((Pjlw) + 1));
184
}
185
186
if (JAPtype == cJL_JAPLEAF_POPU2)
187
{
188
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
189
190
if (Count0 > 1) JU_RET_NOTFOUND; // too high.
191
192
*PIndex = Pjlw[Count0]; // Index, base 0.
193
194
return((PPvoid_t) ((Pjlw) + 2 + Count0));
195
}
196
#endif // (LOW_POP && JUDYL)
197
198
JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1); return(JERRI );)
199
JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL); return(PPJERR);)
200
201
202
// COMMON CODE:
203
//
204
// Prepare to handle a root-level or lower-level branch: Save the current
205
// state, obtain the total population for the branch in a state-dependent way,
206
// and then branch to common code for multiple cases.
207
//
208
// For root-level branches, the state is always cJU_ROOTSTATE, and the array
209
// population must already be set in pop1; it is not available in jp_DcdPop0.
210
//
211
// Note: The total population is only needed in cases where the common code
212
// "counts down" instead of up to minimize cache line fills. However, it's
213
// available cheaply, and it's better to do it with a constant shift (constant
214
// state value) instead of a variable shift later "when needed".
215
216
#define PREPB_ROOT(Next) \
217
state = cJU_ROOTSTATE; \
218
goto Next
219
220
// Use PREPB_DCD() to first copy the Dcd bytes to *PIndex if there are any
221
// (only if state < cJU_ROOTSTATE - 1):
222
223
#define PREPB_DCD(Pjp,cState,Next) \
224
JU_SETDCD(*PIndex, (Pjp)->jp_DcdPop0, cState); \
225
PREPB((Pjp), cState, Next)
226
227
#define PREPB(Pjp,cState,Next) \
228
state = (cState); \
229
pop1 = JU_JPBRANCH_POP0((Pjp)->jp_DcdPop0, (cState)) + 1; \
230
goto Next
231
232
// Calculate whether the ordinal of an Index within a given expanse falls in
233
// the lower or upper half of the expanse's population, taking care with
234
// unsigned math and boundary conditions:
235
//
236
// Note: Assume the ordinal falls within the expanse's population, that is,
237
// 0 < (Count - Pop1lower) <= Pop1exp (assuming infinite math).
238
//
239
// Note: If the ordinal is the middle element, it doesn't matter whether
240
// LOWERHALF() is TRUE or FALSE.
241
242
#define LOWERHALF(Count0,Pop1lower,Pop1exp) \
243
(((Count0) - (Pop1lower)) < ((Pop1exp) / 2))
244
245
// Calculate the (signed) offset within a leaf to the desired ordinal (Count -
246
// Pop1lower; offset is one less), and optionally ensure it's in range:
247
248
#define SETOFFSET(Offset,Count0,Pop1lower,Pjp) \
249
(Offset) = (Count0) - (Pop1lower); \
250
assert((Offset) >= 0); \
251
assert((Offset) <= JU_JPLEAF_POP0((Pjp)->jp_DcdPop0))
252
253
// Variations for immediate indexes, with and without pop1-specific assertions:
254
255
#define SETOFFSET_IMM_CK(Offset,Count0,Pop1lower,cPop1) \
256
(Offset) = (Count0) - (Pop1lower); \
257
assert((Offset) >= 0); \
258
assert((Offset) < (cPop1))
259
260
#define SETOFFSET_IMM(Offset,Count0,Pop1lower) \
261
(Offset) = (Count0) - (Pop1lower)
262
263
264
// STATE MACHINE -- TRAVERSE TREE:
265
//
266
// In branches, look for the expanse (digit), if any, where the total pop1
267
// below or at that expanse would meet or exceed Count, meaning the Index must
268
// be in this expanse.
269
270
SMByCount: // return here for next branch/leaf.
271
272
switch (Pjp->jp_Type)
273
{
274
275
276
// ----------------------------------------------------------------------------
277
// LINEAR BRANCH; count populations in JPs in the JBL upwards until finding the
278
// expanse (digit) containing Count, and "recurse".
279
//
280
// Note: There are no null JPs in a JBL; watch out for pop1 == 0.
281
//
282
// Note: A JBL should always fit in one cache line => no need to count up
283
// versus down to save cache line fills.
284
//
285
// TBD: The previous is no longer true. Consider enhancing this code to count
286
// up/down, but it can wait for a later tuning phase. In the meantime, PREPB()
287
// sets pop1 for the whole array, but that value is not used here. 001215:
288
// Maybe it's true again?
289
290
case cJU_JPBRANCH_L2: PREPB_DCD(Pjp, 2, BranchL);
291
#ifndef JU_64BIT
292
case cJU_JPBRANCH_L3: PREPB( Pjp, 3, BranchL);
293
#else
294
case cJU_JPBRANCH_L3: PREPB_DCD(Pjp, 3, BranchL);
295
case cJU_JPBRANCH_L4: PREPB_DCD(Pjp, 4, BranchL);
296
case cJU_JPBRANCH_L5: PREPB_DCD(Pjp, 5, BranchL);
297
case cJU_JPBRANCH_L6: PREPB_DCD(Pjp, 6, BranchL);
298
case cJU_JPBRANCH_L7: PREPB( Pjp, 7, BranchL);
299
#endif
300
case cJU_JPBRANCH_L: PREPB_ROOT( BranchL);
301
{
302
Pjbl_t Pjbl;
303
304
// Common code (state-independent) for all cases of linear branches:
305
306
BranchL:
307
Pjbl = P_JBL(Pjp->jp_Addr);
308
309
for (jpnum = 0; jpnum < (Pjbl->jbl_NumJPs); ++jpnum)
310
{
311
if ((pop1 = __JudyJPPop1((Pjbl->jbl_jp) + jpnum))
312
== cJU_ALLONES)
313
{
314
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
315
JUDY1CODE(return(JERRI );)
316
JUDYLCODE(return(PPJERR);)
317
}
318
assert(pop1 != 0);
319
320
// Warning: pop1lower and pop1 are unsigned, so do not subtract 1 and compare
321
// >=, but instead use the following expression:
322
323
if (pop1lower + pop1 > Count0) // Index is in this expanse.
324
{
325
JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[jpnum], state);
326
Pjp = (Pjbl->jbl_jp) + jpnum;
327
goto SMByCount; // look under this expanse.
328
}
329
330
pop1lower += pop1; // add this JP's pop1.
331
}
332
333
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
334
JUDY1CODE(return(JERRI );)
335
JUDYLCODE(return(PPJERR);)
336
337
} // case cJU_JPBRANCH_L
338
339
340
// ----------------------------------------------------------------------------
341
// BITMAP BRANCH; count populations in JPs in the JBB upwards or downwards
342
// until finding the expanse (digit) containing Count, and "recurse".
343
//
344
// Note: There are no null JPs in a JBB; watch out for pop1 == 0.
345
346
case cJU_JPBRANCH_B2: PREPB_DCD(Pjp, 2, BranchB);
347
#ifndef JU_64BIT
348
case cJU_JPBRANCH_B3: PREPB( Pjp, 3, BranchB);
349
#else
350
case cJU_JPBRANCH_B3: PREPB_DCD(Pjp, 3, BranchB);
351
case cJU_JPBRANCH_B4: PREPB_DCD(Pjp, 4, BranchB);
352
case cJU_JPBRANCH_B5: PREPB_DCD(Pjp, 5, BranchB);
353
case cJU_JPBRANCH_B6: PREPB_DCD(Pjp, 6, BranchB);
354
case cJU_JPBRANCH_B7: PREPB( Pjp, 7, BranchB);
355
#endif
356
case cJU_JPBRANCH_B: PREPB_ROOT( BranchB);
357
{
358
Pjbb_t Pjbb;
359
360
// Common code (state-independent) for all cases of bitmap branches:
361
362
BranchB:
363
Pjbb = P_JBB(Pjp->jp_Addr);
364
365
// Shorthand for one subexpanse in a bitmap and for one JP in a bitmap branch:
366
//
367
// Note: BMPJP0 exists separately to support assertions.
368
369
#define BMPJP0(Subexp) (P_JP(JU_JBB_PJP(Pjbb, Subexp)))
370
#define BMPJP(Subexp,JPnum) (BMPJP0(Subexp) + (JPnum))
371
372
373
// Common code for descending through a JP:
374
//
375
// Determine the digit for the expanse and save it in *PIndex; then "recurse".
376
377
#define JBB_FOUNDEXPANSE \
378
{ \
379
JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb,subexp), jpnum); \
380
JU_SETDIGIT(*PIndex, digit, state); \
381
Pjp = BMPJP(subexp, jpnum); \
382
goto SMByCount; \
383
}
384
385
386
#ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
387
388
// FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1's
389
// in JPs upwards, or subtracting the pop1's in JPs downwards:
390
//
391
// See header comments about limitations of this for Judy*ByCount().
392
393
#endif
394
395
// COUNT UPWARD, adding each "below" JP's pop1:
396
397
#ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
398
399
if (LOWERHALF(Count0, pop1lower, pop1))
400
{
401
#endif
402
#ifdef SMARTMETRICS
403
++jbb_upward;
404
#endif
405
for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
406
{
407
if ((jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb,subexp)))
408
&& (BMPJP0(subexp) == (Pjp_t) NULL))
409
{
410
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // null ptr.
411
JUDY1CODE(return(JERRI );)
412
JUDYLCODE(return(PPJERR);)
413
}
414
415
// Note: An empty subexpanse (jpcount == 0) is handled "for free":
416
417
for (jpnum = 0; jpnum < jpcount; ++jpnum)
418
{
419
if ((pop1 = __JudyJPPop1(BMPJP(subexp, jpnum)))
420
== cJU_ALLONES)
421
{
422
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
423
JUDY1CODE(return(JERRI );)
424
JUDYLCODE(return(PPJERR);)
425
}
426
assert(pop1 != 0);
427
428
// Warning: pop1lower and pop1 are unsigned, see earlier comment:
429
430
if (pop1lower + pop1 > Count0)
431
JBB_FOUNDEXPANSE; // Index is in this expanse.
432
433
pop1lower += pop1; // add this JP's pop1.
434
}
435
}
436
#ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
437
}
438
439
440
// COUNT DOWNWARD, subtracting each "above" JP's pop1 from the whole expanse's
441
// pop1:
442
443
else
444
{
445
#ifdef SMARTMETRICS
446
++jbb_downward;
447
#endif
448
pop1lower += pop1; // add whole branch to start.
449
450
for (subexp = cJU_NUMSUBEXPB - 1; subexp >= 0; --subexp)
451
{
452
if ((jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)))
453
&& (BMPJP0(subexp) == (Pjp_t) NULL))
454
{
455
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // null ptr.
456
JUDY1CODE(return(JERRI );)
457
JUDYLCODE(return(PPJERR);)
458
}
459
460
// Note: An empty subexpanse (jpcount == 0) is handled "for free":
461
462
for (jpnum = jpcount - 1; jpnum >= 0; --jpnum)
463
{
464
if ((pop1 = __JudyJPPop1(BMPJP(subexp, jpnum)))
465
== cJU_ALLONES)
466
{
467
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
468
JUDY1CODE(return(JERRI );)
469
JUDYLCODE(return(PPJERR);)
470
}
471
assert(pop1 != 0);
472
473
// Warning: pop1lower and pop1 are unsigned, see earlier comment:
474
475
pop1lower -= pop1;
476
477
// Beware unsigned math problems:
478
479
if ((pop1lower == 0) || (pop1lower - 1 < Count0))
480
JBB_FOUNDEXPANSE; // Index is in this expanse.
481
}
482
}
483
}
484
#endif // NOSMARTJBB
485
486
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
487
JUDY1CODE(return(JERRI );)
488
JUDYLCODE(return(PPJERR);)
489
490
} // case cJU_JPBRANCH_B
491
492
493
// ----------------------------------------------------------------------------
494
// UNCOMPRESSED BRANCH; count populations in JPs in the JBU upwards or
495
// downwards until finding the expanse (digit) containing Count, and "recurse".
496
497
case cJU_JPBRANCH_U2: PREPB_DCD(Pjp, 2, BranchU);
498
#ifndef JU_64BIT
499
case cJU_JPBRANCH_U3: PREPB( Pjp, 3, BranchU);
500
#else
501
case cJU_JPBRANCH_U3: PREPB_DCD(Pjp, 3, BranchU);
502
case cJU_JPBRANCH_U4: PREPB_DCD(Pjp, 4, BranchU);
503
case cJU_JPBRANCH_U5: PREPB_DCD(Pjp, 5, BranchU);
504
case cJU_JPBRANCH_U6: PREPB_DCD(Pjp, 6, BranchU);
505
case cJU_JPBRANCH_U7: PREPB( Pjp, 7, BranchU);
506
#endif
507
case cJU_JPBRANCH_U: PREPB_ROOT( BranchU);
508
{
509
Pjbu_t Pjbu;
510
511
// Common code (state-independent) for all cases of uncompressed branches:
512
513
BranchU:
514
Pjbu = P_JBU(Pjp->jp_Addr);
515
516
// Common code for descending through a JP:
517
//
518
// Save the digit for the expanse in *PIndex, then "recurse".
519
520
#define JBU_FOUNDEXPANSE \
521
{ \
522
JU_SETDIGIT(*PIndex, jpnum, state); \
523
Pjp = (Pjbu->jbu_jp) + jpnum; \
524
goto SMByCount; \
525
}
526
527
528
#ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
529
530
// FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1's
531
// in JPs upwards, or subtracting the pop1's in JPs downwards:
532
//
533
// See header comments about limitations of this for Judy*ByCount().
534
535
#endif
536
537
// COUNT UPWARD, simply adding the pop1 of each JP:
538
539
#ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
540
541
if (LOWERHALF(Count0, pop1lower, pop1))
542
{
543
#endif
544
#ifdef SMARTMETRICS
545
++jbu_upward;
546
#endif
547
548
for (jpnum = 0; jpnum < cJU_BRANCHUNUMJPS; ++jpnum)
549
{
550
// shortcut, save a function call:
551
552
if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
553
continue;
554
555
if ((pop1 = __JudyJPPop1((Pjbu->jbu_jp) + jpnum))
556
== cJU_ALLONES)
557
{
558
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
559
JUDY1CODE(return(JERRI );)
560
JUDYLCODE(return(PPJERR);)
561
}
562
assert(pop1 != 0);
563
564
// Warning: pop1lower and pop1 are unsigned, see earlier comment:
565
566
if (pop1lower + pop1 > Count0)
567
JBU_FOUNDEXPANSE; // Index is in this expanse.
568
569
pop1lower += pop1; // add this JP's pop1.
570
}
571
#ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
572
}
573
574
575
// COUNT DOWNWARD, subtracting the pop1 of each JP above from the whole
576
// expanse's pop1:
577
578
else
579
{
580
#ifdef SMARTMETRICS
581
++jbu_downward;
582
#endif
583
pop1lower += pop1; // add whole branch to start.
584
585
for (jpnum = cJU_BRANCHUNUMJPS - 1; jpnum >= 0; --jpnum)
586
{
587
// shortcut, save a function call:
588
589
if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
590
continue;
591
592
if ((pop1 = __JudyJPPop1(Pjbu->jbu_jp + jpnum))
593
== cJU_ALLONES)
594
{
595
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
596
JUDY1CODE(return(JERRI );)
597
JUDYLCODE(return(PPJERR);)
598
}
599
assert(pop1 != 0);
600
601
// Warning: pop1lower and pop1 are unsigned, see earlier comment:
602
603
pop1lower -= pop1;
604
605
// Beware unsigned math problems:
606
607
if ((pop1lower == 0) || (pop1lower - 1 < Count0))
608
JBU_FOUNDEXPANSE; // Index is in this expanse.
609
}
610
}
611
#endif // NOSMARTJBU
612
613
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
614
JUDY1CODE(return(JERRI );)
615
JUDYLCODE(return(PPJERR);)
616
617
} // case cJU_JPBRANCH_U
618
619
// ----------------------------------------------------------------------------
620
// LINEAR LEAF:
621
//
622
// Return the Index at the proper ordinal (see SETOFFSET()) in the leaf. First
623
// copy Dcd bytes, if there are any (only if state < cJU_ROOTSTATE - 1), to
624
// *PIndex.
625
//
626
// Note: The preceding branch traversal code MIGHT set pop1 for this expanse
627
// (linear leaf) as a side-effect, but don't depend on that (for JUDYL, which
628
// is the only cases that need it anyway).
629
630
#define PREPL_DCD(cState) \
631
JU_SETDCD(*PIndex, Pjp->jp_DcdPop0, cState); \
632
PREPL
633
634
#ifdef JUDY1
635
#define PREPL_SETPOP1 // not needed in any cases.
636
#else
637
#define PREPL_SETPOP1 pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1
638
#endif
639
640
#define PREPL \
641
Pjll = P_JLL(Pjp->jp_Addr); \
642
PREPL_SETPOP1; \
643
SETOFFSET(offset, Count0, pop1lower, Pjp)
644
645
#if (JUDYL || ! JU_64BIT)
646
case cJU_JPLEAF1:
647
648
PREPL_DCD(1);
649
JU_SETDIGIT1(*PIndex, ((uint8_t *) Pjll)[offset]);
650
JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
651
#endif
652
653
case cJU_JPLEAF2:
654
655
PREPL_DCD(2);
656
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
657
| ((uint16_t *) Pjll)[offset];
658
JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
659
660
#ifndef JU_64BIT
661
case cJU_JPLEAF3:
662
{
663
Word_t lsb;
664
PREPL;
665
JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
666
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
667
JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
668
}
669
670
#else
671
case cJU_JPLEAF3:
672
{
673
Word_t lsb;
674
PREPL_DCD(3);
675
JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
676
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
677
JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
678
}
679
680
case cJU_JPLEAF4:
681
682
PREPL_DCD(4);
683
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
684
| ((uint32_t *) Pjll)[offset];
685
JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
686
687
case cJU_JPLEAF5:
688
{
689
Word_t lsb;
690
PREPL_DCD(5);
691
JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (5 * offset));
692
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
693
JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
694
}
695
696
case cJU_JPLEAF6:
697
{
698
Word_t lsb;
699
PREPL_DCD(6);
700
JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (6 * offset));
701
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
702
JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
703
}
704
705
case cJU_JPLEAF7:
706
{
707
Word_t lsb;
708
PREPL;
709
JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (7 * offset));
710
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
711
JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
712
}
713
#endif
714
715
716
// ----------------------------------------------------------------------------
717
// BITMAP LEAF:
718
//
719
// Return the Index at the proper ordinal (see SETOFFSET()) in the leaf by
720
// counting bits. First copy Dcd bytes (always present since state 1 <
721
// cJU_ROOTSTATE) to *PIndex.
722
//
723
// Note: The preceding branch traversal code MIGHT set pop1 for this expanse
724
// (bitmap leaf) as a side-effect, but don't depend on that.
725
726
case cJU_JPLEAF_B1:
727
{
728
Pjlb_t Pjlb;
729
730
JU_SETDCD(*PIndex, Pjp->jp_DcdPop0, 1);
731
Pjlb = P_JLB(Pjp->jp_Addr);
732
pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
733
734
// COUNT UPWARD, adding the pop1 of each subexpanse:
735
//
736
// The entire bitmap should fit in one cache line, but still try to save some
737
// CPU time by counting the fewest possible number of subexpanses from the
738
// bitmap.
739
//
740
// See header comments about limitations of this for Judy*ByCount().
741
742
#ifndef NOSMARTJLB // enable to turn off smart code for comparison purposes.
743
744
if (LOWERHALF(Count0, pop1lower, pop1))
745
{
746
#endif
747
#ifdef SMARTMETRICS
748
++jlb_upward;
749
#endif
750
for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
751
{
752
pop1 = __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
753
754
// Warning: pop1lower and pop1 are unsigned, see earlier comment:
755
756
if (pop1lower + pop1 > Count0)
757
goto LeafB1; // Index is in this subexpanse.
758
759
pop1lower += pop1; // add this subexpanse's pop1.
760
}
761
#ifndef NOSMARTJLB // enable to turn off smart code for comparison purposes.
762
}
763
764
765
// COUNT DOWNWARD, subtracting each "above" subexpanse's pop1 from the whole
766
// expanse's pop1:
767
768
else
769
{
770
#ifdef SMARTMETRICS
771
++jlb_downward;
772
#endif
773
pop1lower += pop1; // add whole leaf to start.
774
775
for (subexp = cJU_NUMSUBEXPL - 1; subexp >= 0; --subexp)
776
{
777
pop1lower -= __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
778
779
// Beware unsigned math problems:
780
781
if ((pop1lower == 0) || (pop1lower - 1 < Count0))
782
goto LeafB1; // Index is in this subexpanse.
783
}
784
}
785
#endif // NOSMARTJLB
786
787
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
788
JUDY1CODE(return(JERRI );)
789
JUDYLCODE(return(PPJERR);)
790
791
792
// RETURN INDEX FOUND:
793
//
794
// Come here with subexp set to the correct subexpanse, and pop1lower set to
795
// the sum for all lower expanses and subexpanses in the Judy tree. Calculate
796
// and save in *PIndex the digit corresponding to the ordinal in this
797
// subexpanse.
798
799
LeafB1:
800
SETOFFSET(offset, Count0, pop1lower, Pjp);
801
JU_BITMAPDIGITL(digit, subexp, JU_JLB_BITMAP(Pjlb, subexp), offset);
802
JU_SETDIGIT1(*PIndex, digit);
803
JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
804
// == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + offset))
805
806
} // case cJU_JPLEAF_B1
807
808
809
#ifdef JUDY1
810
// ----------------------------------------------------------------------------
811
// FULL POPULATION:
812
//
813
// Copy Dcd bytes (always present since state 1 < cJU_ROOTSTATE) to *PIndex,
814
// then set the appropriate digit for the ordinal (see SETOFFSET()) in the leaf
815
// as the LSB in *PIndex.
816
817
case cJ1_JPFULLPOPU1:
818
819
JU_SETDCD(*PIndex, Pjp->jp_DcdPop0, 1);
820
SETOFFSET(offset, Count0, pop1lower, Pjp);
821
assert(offset >= 0);
822
assert(offset <= cJU_JPFULLPOPU1_POP0);
823
JU_SETDIGIT1(*PIndex, offset);
824
JU_RET_FOUND_FULLPOPU1;
825
#endif
826
827
828
// ----------------------------------------------------------------------------
829
// IMMEDIATE:
830
//
831
// Locate the Index with the proper ordinal (see SETOFFSET()) in the Immediate,
832
// depending on leaf Index Size and pop1. Note: There are no Dcd bytes in an
833
// Immediate JP, but in a cJU_JPIMMED_*_01 JP, the field holds the least bytes
834
// of the immediate Index.
835
836
#define SET_01(cState) JU_SETDIGITS(*PIndex, Pjp->jp_DcdPop0, cState)
837
838
case cJU_JPIMMED_1_01: SET_01(1); goto Imm_01;
839
case cJU_JPIMMED_2_01: SET_01(2); goto Imm_01;
840
case cJU_JPIMMED_3_01: SET_01(3); goto Imm_01;
841
#ifdef JU_64BIT
842
case cJU_JPIMMED_4_01: SET_01(4); goto Imm_01;
843
case cJU_JPIMMED_5_01: SET_01(5); goto Imm_01;
844
case cJU_JPIMMED_6_01: SET_01(6); goto Imm_01;
845
case cJU_JPIMMED_7_01: SET_01(7); goto Imm_01;
846
#endif
847
848
Imm_01:
849
850
DBGCODE(SETOFFSET_IMM_CK(offset, Count0, pop1lower, 1);)
851
JU_RET_FOUND_IMM_01(Pjp);
852
853
// Shorthand for where to find start of Index bytes array:
854
855
#ifdef JUDY1
856
#define PJI (Pjp->jp_1Index)
857
#else
858
#define PJI (Pjp->jp_LIndex)
859
#endif
860
861
// Optional code to check the remaining ordinal (see SETOFFSET_IMM()) against
862
// the Index Size of the Immediate:
863
864
#ifndef DEBUG // simple placeholder:
865
#define IMM(cPop1,Next) \
866
goto Next
867
#else // extra pop1-specific checking:
868
#define IMM(cPop1,Next) \
869
SETOFFSET_IMM_CK(offset, Count0, pop1lower, cPop1); \
870
goto Next
871
#endif
872
873
case cJU_JPIMMED_1_02: IMM( 2, Imm1);
874
case cJU_JPIMMED_1_03: IMM( 3, Imm1);
875
#if (JUDY1 || JU_64BIT)
876
case cJU_JPIMMED_1_04: IMM( 4, Imm1);
877
case cJU_JPIMMED_1_05: IMM( 5, Imm1);
878
case cJU_JPIMMED_1_06: IMM( 6, Imm1);
879
case cJU_JPIMMED_1_07: IMM( 7, Imm1);
880
#endif
881
#if (JUDY1 && JU_64BIT)
882
case cJ1_JPIMMED_1_08: IMM( 8, Imm1);
883
case cJ1_JPIMMED_1_09: IMM( 9, Imm1);
884
case cJ1_JPIMMED_1_10: IMM(10, Imm1);
885
case cJ1_JPIMMED_1_11: IMM(11, Imm1);
886
case cJ1_JPIMMED_1_12: IMM(12, Imm1);
887
case cJ1_JPIMMED_1_13: IMM(13, Imm1);
888
case cJ1_JPIMMED_1_14: IMM(14, Imm1);
889
case cJ1_JPIMMED_1_15: IMM(15, Imm1);
890
#endif
891
892
Imm1: SETOFFSET_IMM(offset, Count0, pop1lower);
893
JU_SETDIGIT1(*PIndex, ((uint8_t *) PJI)[offset]);
894
JU_RET_FOUND_IMM(Pjp, offset);
895
896
#if (JUDY1 || JU_64BIT)
897
case cJU_JPIMMED_2_02: IMM(2, Imm2);
898
case cJU_JPIMMED_2_03: IMM(3, Imm2);
899
#endif
900
#if (JUDY1 && JU_64BIT)
901
case cJ1_JPIMMED_2_04: IMM(4, Imm2);
902
case cJ1_JPIMMED_2_05: IMM(5, Imm2);
903
case cJ1_JPIMMED_2_06: IMM(6, Imm2);
904
case cJ1_JPIMMED_2_07: IMM(7, Imm2);
905
#endif
906
907
#if (JUDY1 || JU_64BIT)
908
Imm2: SETOFFSET_IMM(offset, Count0, pop1lower);
909
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
910
| ((uint16_t *) PJI)[offset];
911
JU_RET_FOUND_IMM(Pjp, offset);
912
#endif
913
914
#if (JUDY1 || JU_64BIT)
915
case cJU_JPIMMED_3_02: IMM(2, Imm3);
916
#endif
917
#if (JUDY1 && JU_64BIT)
918
case cJ1_JPIMMED_3_03: IMM(3, Imm3);
919
case cJ1_JPIMMED_3_04: IMM(4, Imm3);
920
case cJ1_JPIMMED_3_05: IMM(5, Imm3);
921
#endif
922
923
#if (JUDY1 || JU_64BIT)
924
Imm3:
925
{
926
Word_t lsb;
927
SETOFFSET_IMM(offset, Count0, pop1lower);
928
JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (3 * offset));
929
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
930
JU_RET_FOUND_IMM(Pjp, offset);
931
}
932
#endif
933
934
#if (JUDY1 && JU_64BIT)
935
case cJ1_JPIMMED_4_02: IMM(2, Imm4);
936
case cJ1_JPIMMED_4_03: IMM(3, Imm4);
937
938
Imm4: SETOFFSET_IMM(offset, Count0, pop1lower);
939
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
940
| ((uint32_t *) PJI)[offset];
941
JU_RET_FOUND_IMM(Pjp, offset);
942
943
case cJ1_JPIMMED_5_02: IMM(2, Imm5);
944
case cJ1_JPIMMED_5_03: IMM(3, Imm5);
945
946
Imm5:
947
{
948
Word_t lsb;
949
SETOFFSET_IMM(offset, Count0, pop1lower);
950
JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (5 * offset));
951
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
952
JU_RET_FOUND_IMM(Pjp, offset);
953
}
954
955
case cJ1_JPIMMED_6_02: IMM(2, Imm6);
956
957
Imm6:
958
{
959
Word_t lsb;
960
SETOFFSET_IMM(offset, Count0, pop1lower);
961
JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (6 * offset));
962
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
963
JU_RET_FOUND_IMM(Pjp, offset);
964
}
965
966
case cJ1_JPIMMED_7_02: IMM(2, Imm7);
967
968
Imm7:
969
{
970
Word_t lsb;
971
SETOFFSET_IMM(offset, Count0, pop1lower);
972
JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (7 * offset));
973
*PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
974
JU_RET_FOUND_IMM(Pjp, offset);
975
}
976
#endif // (JUDY1 && JU_64BIT)
977
978
979
// ----------------------------------------------------------------------------
980
// UNEXPECTED JP TYPES:
981
982
default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
983
JUDY1CODE(return(JERRI );)
984
JUDYLCODE(return(PPJERR);)
985
986
} // SMByCount switch.
987
988
/*NOTREACHED*/
989
990
} // Judy1ByCount() / JudyLByCount()
Loggerhead is a web-based interface for Breezy
Version: 2.0.1