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 // Judy*Count() function for Judy1 and JudyL.
19 // Compile with one of -DJUDY1 or -DJUDYL.
20 //
21 // Compile with -DNOSMARTJBB, -DNOSMARTJBU, and/or -DNOSMARTJLB to build a
22 // version with cache line optimizations deleted, for testing.
23 //
24 // Compile with -DSMARTMETRICS to obtain global variables containing smart
25 // cache line metrics. Note: Dont turn this on simultaneously for this file
26 // and JudyByCount.c because they export the same globals.
27 //
28 // Judy*Count() returns the "count of Indexes" (inclusive) between the two
29 // specified limits (Indexes). This code is remarkably fast. It traverses the
30 // "Judy array" data structure.
31 //
32 // This count code is the GENERIC untuned version (minimum code size). It
33 // might be possible to tuned to a specific architecture to be faster.
34 // However, in real applications, with a modern machine, it is expected that
35 // the instruction times will be swamped by cache line fills.
36 // ****************************************************************************
37
38 #if (! (defined(JUDY1) || defined(JUDYL)))
39 #error: One of -DJUDY1 or -DJUDYL must be specified.
40 #endif
41
42 #ifdef JUDY1
43 #include "Judy1.h"
44 #else
45 #include "JudyL.h"
46 #endif
47
48 #include "JudyPrivate1L.h"
49
50
51 // define a phoney that is for sure
52
53 #define cJU_LEAFW cJU_JPIMMED_CAP
54
55 // Avoid duplicate symbols since this file is multi-compiled:
56
57 #ifdef SMARTMETRICS
58 #ifdef JUDY1
59 Word_t jbb_upward = 0; // counts of directions taken:
60 Word_t jbb_downward = 0;
61 Word_t jbu_upward = 0;
62 Word_t jbu_downward = 0;
63 Word_t jlb_upward = 0;
64 Word_t jlb_downward = 0;
65 #else
66 extern Word_t jbb_upward;
67 extern Word_t jbb_downward;
68 extern Word_t jbu_upward;
69 extern Word_t jbu_downward;
70 extern Word_t jlb_upward;
71 extern Word_t jlb_downward;
72 #endif
73 #endif
74
75
76 // FORWARD DECLARATIONS (prototypes):
77
78 static Word_t j__udy1LCountSM(const Pjp_t Pjp, const Word_t Index,
79 const Pjpm_t Pjpm);
80
81 // Each of Judy1 and JudyL get their own private (static) version of this
82 // function:
83
84 static int j__udyCountLeafB1(const Pjll_t Pjll, const Word_t Pop1,
85 const Word_t Index);
86
87 // These functions are not static because they are exported to Judy*ByCount():
88 //
89 // TBD: Should be made static for performance reasons? And thus duplicated?
90 //
91 // Note: There really are two different functions, but for convenience they
92 // are referred to here with a generic name.
93
94 #ifdef JUDY1
95 #define j__udyJPPop1 j__udy1JPPop1
96 #else
97 #define j__udyJPPop1 j__udyLJPPop1
98 #endif
99
100 Word_t j__udyJPPop1(const Pjp_t Pjp);
101
102
103 // LOCAL ERROR HANDLING:
104 //
105 // The Judy*Count() functions are unusual because they return 0 instead of JERR
106 // for an error. In this source file, define C_JERR for clarity.
107
108 #define C_JERR 0
109
110
111 // ****************************************************************************
112 // J U D Y 1 C O U N T
113 // J U D Y L C O U N T
114 //
115 // See the manual entry for details.
116 //
117 // This code is written recursively, at least at first, because thats much
118 // simpler; hope its fast enough.
119
120 #ifdef JUDY1
Judy1Count(Pcvoid_t PArray,Word_t Index1,Word_t Index2,PJError_t PJError)121 FUNCTION Word_t Judy1Count
122 #else
123 FUNCTION Word_t JudyLCount
124 #endif
125 (
126 Pcvoid_t PArray, // JRP to first branch/leaf in SM.
127 Word_t Index1, // starting Index.
128 Word_t Index2, // ending Index.
129 PJError_t PJError // optional, for returning error info.
130 )
131 {
132 jpm_t fakejpm; // local temporary for small arrays.
133 Pjpm_t Pjpm; // top JPM or local temporary for error info.
134 jp_t fakejp; // constructed for calling j__udy1LCountSM().
135 Pjp_t Pjp; // JP to pass to j__udy1LCountSM().
136 Word_t pop1; // total for the array.
137 Word_t pop1above1; // indexes at or above Index1, inclusive.
138 Word_t pop1above2; // indexes at or above Index2, exclusive.
139 int retcode; // from Judy*First() calls.
140 JUDYLCODE(PPvoid_t PPvalue); // from JudyLFirst() calls.
141
142
143 // CHECK FOR SHORTCUTS:
144 //
145 // As documented, return C_JERR if the Judy array is empty or Index1 > Index2.
146
147 if ((PArray == (Pvoid_t) NULL) || (Index1 > Index2))
148 {
149 JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
150 return(C_JERR);
151 }
152
153 // If Index1 == Index2, simply check if the specified Index is set; pass
154 // through the return value from Judy1Test() or JudyLGet() with appropriate
155 // translations.
156
157 if (Index1 == Index2)
158 {
159 #ifdef JUDY1
160 retcode = Judy1Test(PArray, Index1, PJError);
161
162 if (retcode == JERRI) return(C_JERR); // pass through error.
163
164 if (retcode == 0)
165 {
166 JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
167 return(C_JERR);
168 }
169 #else
170 PPvalue = JudyLGet(PArray, Index1, PJError);
171
172 if (PPvalue == PPJERR) return(C_JERR); // pass through error.
173
174 if (PPvalue == (PPvoid_t) NULL) // Index is not set.
175 {
176 JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
177 return(C_JERR);
178 }
179 #endif
180 return(1); // single index is set.
181 }
182
183
184 // CHECK JRP TYPE:
185 //
186 // Use an if/then for speed rather than a switch, and put the most common cases
187 // first.
188 //
189 // Note: Since even cJU_LEAFW types require counting between two Indexes,
190 // prepare them here for common code below that calls j__udy1LCountSM(), rather
191 // than handling them even more specially here.
192
193 if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
194 {
195 Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
196 Pjpm = & fakejpm;
197 Pjp = & fakejp;
198 Pjp->jp_Addr = (Word_t) Pjlw;
199 Pjp->jp_Type = cJU_LEAFW;
200 Pjpm->jpm_Pop0 = Pjlw[0]; // from first word of leaf.
201 pop1 = Pjpm->jpm_Pop0 + 1;
202 }
203 else
204 {
205 Pjpm = P_JPM(PArray);
206 Pjp = &(Pjpm->jpm_JP);
207 pop1 = (Pjpm->jpm_Pop0) + 1; // note: can roll over to 0.
208
209 #if (defined(JUDY1) && (! defined(JU_64BIT)))
210 if (pop1 == 0) // rare special case of full array:
211 {
212 Word_t count = Index2 - Index1 + 1; // can roll over again.
213
214 if (count == 0)
215 {
216 JU_SET_ERRNO(PJError, JU_ERRNO_FULL);
217 return(C_JERR);
218 }
219 return(count);
220 }
221 #else
222 assert(pop1); // JudyL or 64-bit cannot create a full array!
223 #endif
224 }
225
226
227 // COUNT POP1 ABOVE INDEX1, INCLUSIVE:
228
229 assert(pop1); // just to be safe.
230
231 if (Index1 == 0) // shortcut, pop1above1 is entire population:
232 {
233 pop1above1 = pop1;
234 }
235 else // find first valid Index above Index1, if any:
236 {
237 #ifdef JUDY1
238 if ((retcode = Judy1First(PArray, & Index1, PJError)) == JERRI)
239 return(C_JERR); // pass through error.
240 #else
241 if ((PPvalue = JudyLFirst(PArray, & Index1, PJError)) == PPJERR)
242 return(C_JERR); // pass through error.
243
244 retcode = (PPvalue != (PPvoid_t) NULL); // found a next Index.
245 #endif
246
247 // If theres no Index at or above Index1, just return C_JERR (early exit):
248
249 if (retcode == 0)
250 {
251 JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
252 return(C_JERR);
253 }
254
255 // If a first/next Index was found, call the counting motor starting with that
256 // known valid Index, meaning the return should be positive, not C_JERR except
257 // in case of a real error:
258
259 if ((pop1above1 = j__udy1LCountSM(Pjp, Index1, Pjpm)) == C_JERR)
260 {
261 JU_COPY_ERRNO(PJError, Pjpm); // pass through error.
262 return(C_JERR);
263 }
264 }
265
266
267 // COUNT POP1 ABOVE INDEX2, EXCLUSIVE, AND RETURN THE DIFFERENCE:
268 //
269 // In principle, calculate the ordinal of each Index and take the difference,
270 // with caution about off-by-one errors due to the specified Indexes being set
271 // or unset. In practice:
272 //
273 // - The ordinals computed here are inverse ordinals, that is, the populations
274 // ABOVE the specified Indexes (Index1 inclusive, Index2 exclusive), so
275 // subtract pop1above2 from pop1above1, rather than vice-versa.
276 //
277 // - Index1s result already includes a count for Index1 and/or Index2 if
278 // either is set, so calculate pop1above2 exclusive of Index2.
279 //
280 // TBD: If Index1 and Index2 fall in the same expanse in the top-state
281 // branch(es), would it be faster to walk the SM only once, to their divergence
282 // point, before calling j__udy1LCountSM() or equivalent? Possibly a non-issue
283 // if a top-state pop1 becomes stored with each Judy1 array. Also, consider
284 // whether the first call of j__udy1LCountSM() fills the cache, for common tree
285 // branches, for the second call.
286 //
287 // As for pop1above1, look for shortcuts for special cases when pop1above2 is
288 // zero. Otherwise call the counting "motor".
289
290 assert(pop1above1); // just to be safe.
291
292 if (Index2++ == cJU_ALLONES) return(pop1above1); // Index2 at limit.
293
294 #ifdef JUDY1
295 if ((retcode = Judy1First(PArray, & Index2, PJError)) == JERRI)
296 return(C_JERR);
297 #else
298 if ((PPvalue = JudyLFirst(PArray, & Index2, PJError)) == PPJERR)
299 return(C_JERR);
300
301 retcode = (PPvalue != (PPvoid_t) NULL); // found a next Index.
302 #endif
303 if (retcode == 0) return(pop1above1); // no Index above Index2.
304
305 // Just as for Index1, j__udy1LCountSM() cannot return 0 (locally == C_JERR)
306 // except in case of a real error:
307
308 if ((pop1above2 = j__udy1LCountSM(Pjp, Index2, Pjpm)) == C_JERR)
309 {
310 JU_COPY_ERRNO(PJError, Pjpm); // pass through error.
311 return(C_JERR);
312 }
313
314 if (pop1above1 == pop1above2)
315 {
316 JU_SET_ERRNO(PJError, JU_ERRNO_NONE);
317 return(C_JERR);
318 }
319
320 return(pop1above1 - pop1above2);
321
322 } // Judy1Count() / JudyLCount()
323
324
325 // ****************************************************************************
326 // __ J U D Y 1 L C O U N T S M
327 //
328 // Given a pointer to a JP (with invalid jp_DcdPopO at cJU_ROOTSTATE), a known
329 // valid Index, and a Pjpm for returning error info, recursively visit a Judy
330 // array state machine (SM) and return the count of Indexes, including Index,
331 // through the end of the Judy array at this state or below. In case of error
332 // or a count of 0 (should never happen), return C_JERR with appropriate
333 // JU_ERRNO in the Pjpm.
334 //
335 // Note: This function is not told the current state because its encoded in
336 // the JP Type.
337 //
338 // Method: To minimize cache line fills, while studying each branch, if Index
339 // resides above the midpoint of the branch (which often consists of multiple
340 // cache lines), ADD the populations at or above Index; otherwise, SUBTRACT
341 // from the population of the WHOLE branch (available from the JP) the
342 // populations at or above Index. This is especially tricky for bitmap
343 // branches.
344 //
345 // Note: Unlike, say, the Ins and Del walk routines, this function returns the
346 // same type of returns as Judy*Count(), so it can use *_SET_ERRNO*() macros
347 // the same way.
348
j__udy1LCountSM(const Pjp_t Pjp,const Word_t Index,const Pjpm_t Pjpm)349 FUNCTION static Word_t j__udy1LCountSM(
350 const Pjp_t Pjp, // top of Judy (sub)SM.
351 const Word_t Index, // count at or above this Index.
352 const Pjpm_t Pjpm) // for returning error info.
353 {
354 Pjbl_t Pjbl; // Pjp->jp_Addr masked and cast to types:
355 Pjbb_t Pjbb;
356 Pjbu_t Pjbu;
357 Pjll_t Pjll; // a Judy lower-level linear leaf.
358
359 Word_t digit; // next digit to decode from Index.
360 long jpnum; // JP number in a branch (base 0).
361 int offset; // index ordinal within a leaf, base 0.
362 Word_t pop1; // total population of an expanse.
363 Word_t pop1above; // to return.
364
365 // Common code to check Decode bits in a JP against the equivalent portion of
366 // Index; XOR together, then mask bits of interest; must be all 0:
367 //
368 // Note: Why does this code only assert() compliance rather than actively
369 // checking for outliers? Its because Index is supposed to be valid, hence
370 // always match any Dcd bits traversed.
371 //
372 // Note: This assertion turns out to be always true for cState = 3 on 32-bit
373 // and 7 on 64-bit, but its harmless, probably removed by the compiler.
374
375 #define CHECKDCD(Pjp,cState) \
376 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cState))
377
378 // Common code to prepare to handle a root-level or lower-level branch:
379 // Extract a state-dependent digit from Index in a "constant" way, obtain the
380 // total population for the branch in a state-dependent way, and then branch to
381 // common code for multiple cases:
382 //
383 // For root-level branches, the state is always cJU_ROOTSTATE, and the
384 // population is received in Pjpm->jpm_Pop0.
385 //
386 // Note: The total population is only needed in cases where the common code
387 // "counts up" instead of down to minimize cache line fills. However, its
388 // available cheaply, and its better to do it with a constant shift (constant
389 // state value) instead of a variable shift later "when needed".
390
391 #define PREPB_ROOT(Pjp,Next) \
392 digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE); \
393 pop1 = (Pjpm->jpm_Pop0) + 1; \
394 goto Next
395
396 #define PREPB(Pjp,cState,Next) \
397 digit = JU_DIGITATSTATE(Index, cState); \
398 pop1 = JU_JPBRANCH_POP0(Pjp, (cState)) + 1; \
399 goto Next
400
401
402 // SWITCH ON JP TYPE:
403 //
404 // WARNING: For run-time efficiency the following cases replicate code with
405 // varying constants, rather than using common code with variable values!
406
407 switch (JU_JPTYPE(Pjp))
408 {
409
410
411 // ----------------------------------------------------------------------------
412 // ROOT-STATE LEAF that starts with a Pop0 word; just count within the leaf:
413
414 case cJU_LEAFW:
415 {
416 Pjlw_t Pjlw = P_JLW(Pjp->jp_Addr); // first word of leaf.
417
418 assert((Pjpm->jpm_Pop0) + 1 == Pjlw[0] + 1); // sent correctly.
419 offset = j__udySearchLeafW(Pjlw + 1, Pjpm->jpm_Pop0 + 1, Index);
420 assert(offset >= 0); // Index must exist.
421 assert(offset < (Pjpm->jpm_Pop0) + 1); // Index be in range.
422 return((Pjpm->jpm_Pop0) + 1 - offset); // INCLUSIVE of Index.
423 }
424
425 // ----------------------------------------------------------------------------
426 // LINEAR BRANCH; count populations in JPs in the JBL ABOVE the next digit in
427 // Index, and recurse for the next digit in Index:
428 //
429 // Note: There are no null JPs in a JBL; watch out for pop1 == 0.
430 //
431 // Note: A JBL should always fit in one cache line => no need to count up
432 // versus down to save cache line fills. (PREPB() sets pop1 for no reason.)
433
434 case cJU_JPBRANCH_L2: CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchL);
435 case cJU_JPBRANCH_L3: CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchL);
436
437 #ifdef JU_64BIT
438 case cJU_JPBRANCH_L4: CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchL);
439 case cJU_JPBRANCH_L5: CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchL);
440 case cJU_JPBRANCH_L6: CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchL);
441 case cJU_JPBRANCH_L7: CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchL);
442 #endif
443 case cJU_JPBRANCH_L: PREPB_ROOT(Pjp, BranchL);
444
445 // Common code (state-independent) for all cases of linear branches:
446
447 BranchL:
448
449 Pjbl = P_JBL(Pjp->jp_Addr);
450 jpnum = Pjbl->jbl_NumJPs; // above last JP.
451 pop1above = 0;
452
453 while (digit < (Pjbl->jbl_Expanse[--jpnum])) // still ABOVE digit.
454 {
455 if ((pop1 = j__udyJPPop1((Pjbl->jbl_jp) + jpnum)) == cJU_ALLONES)
456 {
457 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
458 return(C_JERR);
459 }
460
461 pop1above += pop1;
462 assert(jpnum > 0); // should find digit.
463 }
464
465 assert(digit == (Pjbl->jbl_Expanse[jpnum])); // should find digit.
466
467 pop1 = j__udy1LCountSM((Pjbl->jbl_jp) + jpnum, Index, Pjpm);
468 if (pop1 == C_JERR) return(C_JERR); // pass error up.
469
470 assert(pop1above + pop1);
471 return(pop1above + pop1);
472
473
474 // ----------------------------------------------------------------------------
475 // BITMAP BRANCH; count populations in JPs in the JBB ABOVE the next digit in
476 // Index, and recurse for the next digit in Index:
477 //
478 // Note: There are no null JPs in a JBB; watch out for pop1 == 0.
479
480 case cJU_JPBRANCH_B2: CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchB);
481 case cJU_JPBRANCH_B3: CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchB);
482 #ifdef JU_64BIT
483 case cJU_JPBRANCH_B4: CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchB);
484 case cJU_JPBRANCH_B5: CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchB);
485 case cJU_JPBRANCH_B6: CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchB);
486 case cJU_JPBRANCH_B7: CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchB);
487 #endif
488 case cJU_JPBRANCH_B: PREPB_ROOT(Pjp, BranchB);
489
490 // Common code (state-independent) for all cases of bitmap branches:
491
492 BranchB:
493 {
494 long subexp; // for stepping through layer 1 (subexpanses).
495 long findsub; // subexpanse containing Index (digit).
496 Word_t findbit; // bit representing Index (digit).
497 Word_t lowermask; // bits for indexes at or below Index.
498 Word_t jpcount; // JPs in a subexpanse.
499 Word_t clbelow; // cache lines below digits cache line.
500 Word_t clabove; // cache lines above digits cache line.
501
502 Pjbb = P_JBB(Pjp->jp_Addr);
503 findsub = digit / cJU_BITSPERSUBEXPB;
504 findbit = digit % cJU_BITSPERSUBEXPB;
505 lowermask = JU_MASKLOWERINC(JU_BITPOSMASKB(findbit));
506 clbelow = clabove = 0; // initial/default => always downward.
507
508 assert(JU_BITMAPTESTB(Pjbb, digit)); // digit must have a JP.
509 assert(findsub < cJU_NUMSUBEXPB); // falls in expected range.
510
511 // Shorthand for one subexpanse in a bitmap and for one JP in a bitmap branch:
512 //
513 // Note: BMPJP0 exists separately to support assertions.
514
515 #define BMPJP0(Subexp) (P_JP(JU_JBB_PJP(Pjbb, Subexp)))
516 #define BMPJP(Subexp,JPnum) (BMPJP0(Subexp) + (JPnum))
517
518 #ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
519
520 // FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1s
521 // in JPs above Indexs JP, or subtracting the pop1s in JPs below Indexs JP.
522 //
523 // This is tricky because, while each set bit in the bitmap represents a JP,
524 // the JPs are scattered over cJU_NUMSUBEXPB subexpanses, each of which can
525 // contain JPs packed into multiple cache lines, and this code must visit every
526 // JP either BELOW or ABOVE the JP for Index.
527 //
528 // Number of cache lines required to hold a linear list of the given number of
529 // JPs, assuming the first JP is at the start of a cache line or the JPs in
530 // jpcount fit wholly within a single cache line, which is ensured by
531 // JudyMalloc():
532
533 #define CLPERJPS(jpcount) \
534 ((((jpcount) * cJU_WORDSPERJP) + cJU_WORDSPERCL - 1) / cJU_WORDSPERCL)
535
536 // Count cache lines below/above for each subexpanse:
537
538 for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
539 {
540 jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
541
542 // When at the subexpanse containing Index (digit), add cache lines
543 // below/above appropriately, excluding the cache line containing the JP for
544 // Index itself:
545
546 if (subexp < findsub) clbelow += CLPERJPS(jpcount);
547 else if (subexp > findsub) clabove += CLPERJPS(jpcount);
548 else // (subexp == findsub)
549 {
550 Word_t clfind; // cache line containing Index (digit).
551
552 clfind = CLPERJPS(j__udyCountBitsB(
553 JU_JBB_BITMAP(Pjbb, subexp) & lowermask));
554
555 assert(clfind > 0); // digit itself should have 1 CL.
556 clbelow += clfind - 1;
557 clabove += CLPERJPS(jpcount) - clfind;
558 }
559 }
560 #endif // ! NOSMARTJBB
561
562 // Note: Its impossible to get through the following "if" without setting
563 // jpnum -- see some of the assertions below -- but gcc -Wall doesnt know
564 // this, so preset jpnum to make it happy:
565
566 jpnum = 0;
567
568
569 // COUNT POPULATION FOR A BITMAP BRANCH, in whichever direction should result
570 // in fewer cache line fills:
571 //
572 // Note: If the remainder of Index is zero, pop1above is the pop1 of the
573 // entire expanse and theres no point in recursing to lower levels; but this
574 // should be so rare that its not worth checking for;
575 // Judy1Count()/JudyLCount() never even calls the motor for Index == 0 (all
576 // bytes).
577
578
579 // COUNT UPWARD, subtracting each "below or at" JPs pop1 from the whole
580 // expanses pop1:
581 //
582 // Note: If this causes clbelow + 1 cache line fills including JPs cache
583 // line, thats OK; at worst this is the same as clabove.
584
585 if (clbelow < clabove)
586 {
587 #ifdef SMARTMETRICS
588 ++jbb_upward;
589 #endif
590 pop1above = pop1; // subtract JPs at/below Index.
591
592 // Count JPs for which to accrue pop1s in this subexpanse:
593 //
594 // TBD: If JU_JBB_BITMAP is cJU_FULLBITMAPB, dont bother counting.
595
596 for (subexp = 0; subexp <= findsub; ++subexp)
597 {
598 jpcount = j__udyCountBitsB((subexp < findsub) ?
599 JU_JBB_BITMAP(Pjbb, subexp) :
600 JU_JBB_BITMAP(Pjbb, subexp) & lowermask);
601
602 // should always find findbit:
603 assert((subexp < findsub) || jpcount);
604
605 // Subtract pop1s from JPs BELOW OR AT Index (digit):
606 //
607 // Note: The pop1 for Indexs JP itself is partially added back later at a
608 // lower state.
609 //
610 // Note: An empty subexpanse (jpcount == 0) is handled "for free".
611 //
612 // Note: Must be null JP subexp pointer in empty subexpanse and non-empty in
613 // non-empty subexpanse:
614
615 assert( jpcount || (BMPJP0(subexp) == (Pjp_t) NULL));
616 assert((! jpcount) || (BMPJP0(subexp) != (Pjp_t) NULL));
617
618 for (jpnum = 0; jpnum < jpcount; ++jpnum)
619 {
620 if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum)))
621 == cJU_ALLONES)
622 {
623 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
624 return(C_JERR);
625 }
626
627 pop1above -= pop1;
628 }
629
630 jpnum = jpcount - 1; // make correct for digit.
631 }
632 }
633
634 // COUNT DOWNWARD, adding each "above" JPs pop1:
635
636 else
637 {
638 long jpcountbf; // below findbit, inclusive.
639 #ifdef SMARTMETRICS
640 ++jbb_downward;
641 #endif
642 pop1above = 0; // add JPs above Index.
643 jpcountbf = 0; // until subexp == findsub.
644
645 // Count JPs for which to accrue pop1s in this subexpanse:
646 //
647 // This is more complicated than counting upward because the scan of digits
648 // subexpanse must count ALL JPs, to know where to START counting down, and
649 // ALSO note the offset of digits JP to know where to STOP counting down.
650
651 for (subexp = cJU_NUMSUBEXPB - 1; subexp >= findsub; --subexp)
652 {
653 jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
654
655 // should always find findbit:
656 assert((subexp > findsub) || jpcount);
657
658 if (! jpcount) continue; // empty subexpanse, save time.
659
660 // Count JPs below digit, inclusive:
661
662 if (subexp == findsub)
663 {
664 jpcountbf = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)
665 & lowermask);
666 }
667
668 // should always find findbit:
669 assert((subexp > findsub) || jpcountbf);
670 assert(jpcount >= jpcountbf); // proper relationship.
671
672 // Add pop1s from JPs ABOVE Index (digit):
673
674 // no null JP subexp pointers:
675 assert(BMPJP0(subexp) != (Pjp_t) NULL);
676
677 for (jpnum = jpcount - 1; jpnum >= jpcountbf; --jpnum)
678 {
679 if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum)))
680 == cJU_ALLONES)
681 {
682 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
683 return(C_JERR);
684 }
685
686 pop1above += pop1;
687 }
688 // jpnum is now correct for digit.
689 }
690 } // else.
691
692 // Return the net population ABOVE the digits JP at this state (in this JBB)
693 // plus the population AT OR ABOVE Index in the SM under the digits JP:
694
695 pop1 = j__udy1LCountSM(BMPJP(findsub, jpnum), Index, Pjpm);
696 if (pop1 == C_JERR) return(C_JERR); // pass error up.
697
698 assert(pop1above + pop1);
699 return(pop1above + pop1);
700
701 } // case.
702
703
704 // ----------------------------------------------------------------------------
705 // UNCOMPRESSED BRANCH; count populations in JPs in the JBU ABOVE the next
706 // digit in Index, and recurse for the next digit in Index:
707 //
708 // Note: If the remainder of Index is zero, pop1above is the pop1 of the
709 // entire expanse and theres no point in recursing to lower levels; but this
710 // should be so rare that its not worth checking for;
711 // Judy1Count()/JudyLCount() never even calls the motor for Index == 0 (all
712 // bytes).
713
714 case cJU_JPBRANCH_U2: CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchU);
715 case cJU_JPBRANCH_U3: CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchU);
716 #ifdef JU_64BIT
717 case cJU_JPBRANCH_U4: CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchU);
718 case cJU_JPBRANCH_U5: CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchU);
719 case cJU_JPBRANCH_U6: CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchU);
720 case cJU_JPBRANCH_U7: CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchU);
721 #endif
722 case cJU_JPBRANCH_U: PREPB_ROOT(Pjp, BranchU);
723
724 // Common code (state-independent) for all cases of uncompressed branches:
725
726 BranchU:
727 Pjbu = P_JBU(Pjp->jp_Addr);
728
729 #ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
730
731 // FIGURE OUT WHICH WAY CAUSES FEWER CACHE LINE FILLS; adding the JPs above
732 // Indexs JP, or subtracting the JPs below Indexs JP.
733 //
734 // COUNT UPWARD, subtracting the pop1 of each JP BELOW OR AT Index, from the
735 // whole expanses pop1:
736
737 if (digit < (cJU_BRANCHUNUMJPS / 2))
738 {
739 pop1above = pop1; // subtract JPs below Index.
740 #ifdef SMARTMETRICS
741 ++jbu_upward;
742 #endif
743 for (jpnum = 0; jpnum <= digit; ++jpnum)
744 {
745 if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
746 continue; // shortcut, save a function call.
747
748 if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum))
749 == cJU_ALLONES)
750 {
751 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
752 return(C_JERR);
753 }
754
755 pop1above -= pop1;
756 }
757 }
758
759 // COUNT DOWNWARD, simply adding the pop1 of each JP ABOVE Index:
760
761 else
762 #endif // NOSMARTJBU
763 {
764 assert(digit < cJU_BRANCHUNUMJPS);
765 #ifdef SMARTMETRICS
766 ++jbu_downward;
767 #endif
768 pop1above = 0; // add JPs above Index.
769
770 for (jpnum = cJU_BRANCHUNUMJPS - 1; jpnum > digit; --jpnum)
771 {
772 if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
773 continue; // shortcut, save a function call.
774
775 if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum))
776 == cJU_ALLONES)
777 {
778 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
779 return(C_JERR);
780 }
781
782 pop1above += pop1;
783 }
784 }
785
786 if ((pop1 = j__udy1LCountSM(Pjbu->jbu_jp + digit, Index, Pjpm))
787 == C_JERR) return(C_JERR); // pass error up.
788
789 assert(pop1above + pop1);
790 return(pop1above + pop1);
791
792
793 // ----------------------------------------------------------------------------
794 // LEAF COUNT MACROS:
795 //
796 // LEAF*ABOVE() are common code for different JP types (linear leaves, bitmap
797 // leaves, and immediates) and different leaf Index Sizes, which result in
798 // calling different leaf search functions. Linear leaves get the leaf address
799 // from jp_Addr and the Population from jp_DcdPopO, while immediates use Pjp
800 // itself as the leaf address and get Population from jp_Type.
801
802 #define LEAFLABOVE(Func) \
803 Pjll = P_JLL(Pjp->jp_Addr); \
804 pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
805 LEAFABOVE(Func, Pjll, pop1)
806
807 #define LEAFB1ABOVE(Func) LEAFLABOVE(Func) // different Func, otherwise same.
808
809 #ifdef JUDY1
810 #define IMMABOVE(Func,Pop1) \
811 Pjll = (Pjll_t) Pjp; \
812 LEAFABOVE(Func, Pjll, Pop1)
813 #else
814 // Note: For JudyL immediates with >= 2 Indexes, the index bytes are in a
815 // different place than for Judy1:
816
817 #define IMMABOVE(Func,Pop1) \
818 LEAFABOVE(Func, (Pjll_t) (Pjp->jp_LIndex), Pop1)
819 #endif
820
821 // For all leaf types, the population AT OR ABOVE is the total pop1 less the
822 // offset of Index; and Index should always be found:
823
824 #define LEAFABOVE(Func,Pjll,Pop1) \
825 offset = Func(Pjll, Pop1, Index); \
826 assert(offset >= 0); \
827 assert(offset < (Pop1)); \
828 return((Pop1) - offset)
829
830 // IMMABOVE_01 handles the special case of an immediate JP with 1 index, which
831 // the search functions arent used for anyway:
832 //
833 // The target Index should be the one in this Immediate, in which case the
834 // count above (inclusive) is always 1.
835
836 #define IMMABOVE_01 \
837 assert((JU_JPDCDPOP0(Pjp)) == JU_TRIMTODCDSIZE(Index)); \
838 return(1)
839
840
841 // ----------------------------------------------------------------------------
842 // LINEAR LEAF; search the leaf for Index; size is computed from jp_Type:
843
844 #if (defined(JUDYL) || (! defined(JU_64BIT)))
845 case cJU_JPLEAF1: LEAFLABOVE(j__udySearchLeaf1);
846 #endif
847 case cJU_JPLEAF2: LEAFLABOVE(j__udySearchLeaf2);
848 case cJU_JPLEAF3: LEAFLABOVE(j__udySearchLeaf3);
849
850 #ifdef JU_64BIT
851 case cJU_JPLEAF4: LEAFLABOVE(j__udySearchLeaf4);
852 case cJU_JPLEAF5: LEAFLABOVE(j__udySearchLeaf5);
853 case cJU_JPLEAF6: LEAFLABOVE(j__udySearchLeaf6);
854 case cJU_JPLEAF7: LEAFLABOVE(j__udySearchLeaf7);
855 #endif
856
857
858 // ----------------------------------------------------------------------------
859 // BITMAP LEAF; search the leaf for Index:
860 //
861 // Since the bitmap describes Indexes digitally rather than linearly, this is
862 // not really a search, but just a count.
863
864 case cJU_JPLEAF_B1: LEAFB1ABOVE(j__udyCountLeafB1);
865
866
867 #ifdef JUDY1
868 // ----------------------------------------------------------------------------
869 // FULL POPULATION:
870 //
871 // Return the count of Indexes AT OR ABOVE Index, which is the total population
872 // of the expanse (a constant) less the value of the undecoded digit remaining
873 // in Index (its base-0 offset in the expanse), which yields an inclusive count
874 // above.
875 //
876 // TBD: This only supports a 1-byte full expanse. Should this extract a
877 // stored value for pop0 and possibly more LSBs of Index, to handle larger full
878 // expanses?
879
880 case cJ1_JPFULLPOPU1:
881 return(cJU_JPFULLPOPU1_POP0 + 1 - JU_DIGITATSTATE(Index, 1));
882 #endif
883
884
885 // ----------------------------------------------------------------------------
886 // IMMEDIATE:
887
888 case cJU_JPIMMED_1_01: IMMABOVE_01;
889 case cJU_JPIMMED_2_01: IMMABOVE_01;
890 case cJU_JPIMMED_3_01: IMMABOVE_01;
891 #ifdef JU_64BIT
892 case cJU_JPIMMED_4_01: IMMABOVE_01;
893 case cJU_JPIMMED_5_01: IMMABOVE_01;
894 case cJU_JPIMMED_6_01: IMMABOVE_01;
895 case cJU_JPIMMED_7_01: IMMABOVE_01;
896 #endif
897
898 case cJU_JPIMMED_1_02: IMMABOVE(j__udySearchLeaf1, 2);
899 case cJU_JPIMMED_1_03: IMMABOVE(j__udySearchLeaf1, 3);
900 #if (defined(JUDY1) || defined(JU_64BIT))
901 case cJU_JPIMMED_1_04: IMMABOVE(j__udySearchLeaf1, 4);
902 case cJU_JPIMMED_1_05: IMMABOVE(j__udySearchLeaf1, 5);
903 case cJU_JPIMMED_1_06: IMMABOVE(j__udySearchLeaf1, 6);
904 case cJU_JPIMMED_1_07: IMMABOVE(j__udySearchLeaf1, 7);
905 #endif
906 #if (defined(JUDY1) && defined(JU_64BIT))
907 case cJ1_JPIMMED_1_08: IMMABOVE(j__udySearchLeaf1, 8);
908 case cJ1_JPIMMED_1_09: IMMABOVE(j__udySearchLeaf1, 9);
909 case cJ1_JPIMMED_1_10: IMMABOVE(j__udySearchLeaf1, 10);
910 case cJ1_JPIMMED_1_11: IMMABOVE(j__udySearchLeaf1, 11);
911 case cJ1_JPIMMED_1_12: IMMABOVE(j__udySearchLeaf1, 12);
912 case cJ1_JPIMMED_1_13: IMMABOVE(j__udySearchLeaf1, 13);
913 case cJ1_JPIMMED_1_14: IMMABOVE(j__udySearchLeaf1, 14);
914 case cJ1_JPIMMED_1_15: IMMABOVE(j__udySearchLeaf1, 15);
915 #endif
916
917 #if (defined(JUDY1) || defined(JU_64BIT))
918 case cJU_JPIMMED_2_02: IMMABOVE(j__udySearchLeaf2, 2);
919 case cJU_JPIMMED_2_03: IMMABOVE(j__udySearchLeaf2, 3);
920 #endif
921 #if (defined(JUDY1) && defined(JU_64BIT))
922 case cJ1_JPIMMED_2_04: IMMABOVE(j__udySearchLeaf2, 4);
923 case cJ1_JPIMMED_2_05: IMMABOVE(j__udySearchLeaf2, 5);
924 case cJ1_JPIMMED_2_06: IMMABOVE(j__udySearchLeaf2, 6);
925 case cJ1_JPIMMED_2_07: IMMABOVE(j__udySearchLeaf2, 7);
926 #endif
927
928 #if (defined(JUDY1) || defined(JU_64BIT))
929 case cJU_JPIMMED_3_02: IMMABOVE(j__udySearchLeaf3, 2);
930 #endif
931 #if (defined(JUDY1) && defined(JU_64BIT))
932 case cJ1_JPIMMED_3_03: IMMABOVE(j__udySearchLeaf3, 3);
933 case cJ1_JPIMMED_3_04: IMMABOVE(j__udySearchLeaf3, 4);
934 case cJ1_JPIMMED_3_05: IMMABOVE(j__udySearchLeaf3, 5);
935
936 case cJ1_JPIMMED_4_02: IMMABOVE(j__udySearchLeaf4, 2);
937 case cJ1_JPIMMED_4_03: IMMABOVE(j__udySearchLeaf4, 3);
938
939 case cJ1_JPIMMED_5_02: IMMABOVE(j__udySearchLeaf5, 2);
940 case cJ1_JPIMMED_5_03: IMMABOVE(j__udySearchLeaf5, 3);
941
942 case cJ1_JPIMMED_6_02: IMMABOVE(j__udySearchLeaf6, 2);
943
944 case cJ1_JPIMMED_7_02: IMMABOVE(j__udySearchLeaf7, 2);
945 #endif
946
947
948 // ----------------------------------------------------------------------------
949 // OTHER CASES:
950
951 default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(C_JERR);
952
953 } // switch on JP type
954
955 /*NOTREACHED*/
956
957 } // j__udy1LCountSM()
958
959
960 // ****************************************************************************
961 // J U D Y C O U N T L E A F B 1
962 //
963 // This is a private analog of the j__udySearchLeaf*() functions for counting
964 // in bitmap 1-byte leaves. Since a bitmap leaf describes Indexes digitally
965 // rather than linearly, this is not really a search, but just a count of the
966 // valid Indexes == set bits below or including Index, which should be valid.
967 // Return the "offset" (really the ordinal), 0 .. Pop1 - 1, of Index in Pjll;
968 // if Indexs bit is not set (which should never happen, so this is DEBUG-mode
969 // only), return the 1s-complement equivalent (== negative offset minus 1).
970 //
971 // Note: The source code for this function looks identical for both Judy1 and
972 // JudyL, but the JU_JLB_BITMAP macro varies.
973 //
974 // Note: For simpler calling, the first arg is of type Pjll_t but then cast to
975 // Pjlb_t.
976
j__udyCountLeafB1(const Pjll_t Pjll,const Word_t Pop1,const Word_t Index)977 FUNCTION static int j__udyCountLeafB1(
978 const Pjll_t Pjll, // bitmap leaf, as Pjll_t for consistency.
979 const Word_t Pop1, // Population of whole leaf.
980 const Word_t Index) // to which to count.
981 {
982 Pjlb_t Pjlb = (Pjlb_t) Pjll; // to proper type.
983 Word_t digit = Index & cJU_MASKATSTATE(1);
984 Word_t findsub = digit / cJU_BITSPERSUBEXPL;
985 Word_t findbit = digit % cJU_BITSPERSUBEXPL;
986 int count; // in leaf through Index.
987 long subexp; // for stepping through subexpanses.
988
989
990 // COUNT UPWARD:
991 //
992 // The entire bitmap should fit in one cache line, but still try to save some
993 // CPU time by counting the fewest possible number of subexpanses from the
994 // bitmap.
995
996 #ifndef NOSMARTJLB // enable to turn off smart code for comparison purposes.
997
998 if (findsub < (cJU_NUMSUBEXPL / 2))
999 {
1000 #ifdef SMARTMETRICS
1001 ++jlb_upward;
1002 #endif
1003 count = 0;
1004
1005 for (subexp = 0; subexp < findsub; ++subexp)
1006 {
1007 count += ((JU_JLB_BITMAP(Pjlb, subexp) == cJU_FULLBITMAPL) ?
1008 cJU_BITSPERSUBEXPL :
1009 j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp)));
1010 }
1011
1012 // This count includes findbit, which should be set, resulting in a base-1
1013 // offset:
1014
1015 count += j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, findsub)
1016 & JU_MASKLOWERINC(JU_BITPOSMASKL(findbit)));
1017
1018 DBGCODE(if (! JU_BITMAPTESTL(Pjlb, digit)) return(~count);)
1019 assert(count >= 1);
1020 return(count - 1); // convert to base-0 offset.
1021 }
1022 #endif // NOSMARTJLB
1023
1024
1025 // COUNT DOWNWARD:
1026 //
1027 // Count the valid Indexes above or at Index, and subtract from Pop1.
1028
1029 #ifdef SMARTMETRICS
1030 ++jlb_downward;
1031 #endif
1032 count = Pop1; // base-1 for now.
1033
1034 for (subexp = cJU_NUMSUBEXPL - 1; subexp > findsub; --subexp)
1035 {
1036 count -= ((JU_JLB_BITMAP(Pjlb, subexp) == cJU_FULLBITMAPL) ?
1037 cJU_BITSPERSUBEXPL :
1038 j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp)));
1039 }
1040
1041 // This count includes findbit, which should be set, resulting in a base-0
1042 // offset:
1043
1044 count -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, findsub)
1045 & JU_MASKHIGHERINC(JU_BITPOSMASKL(findbit)));
1046
1047 DBGCODE(if (! JU_BITMAPTESTL(Pjlb, digit)) return(~count);)
1048 assert(count >= 0); // should find Index itself.
1049 return(count); // is already a base-0 offset.
1050
1051 } // j__udyCountLeafB1()
1052
1053
1054 // ****************************************************************************
1055 // J U D Y J P P O P 1
1056 //
1057 // This function takes any type of JP other than a root-level JP (cJU_LEAFW* or
1058 // cJU_JPBRANCH* with no number suffix) and extracts the Pop1 from it. In some
1059 // sense this is a wrapper around the JU_JP*_POP0 macros. Why write it as a
1060 // function instead of a complex macro containing a trinary? (See version
1061 // Judy1.h version 4.17.) We think its cheaper to call a function containing
1062 // a switch statement with "constant" cases than to do the variable
1063 // calculations in a trinary.
1064 //
1065 // For invalid JP Types return cJU_ALLONES. Note that this is an impossibly
1066 // high Pop1 for any JP below a top level branch.
1067
j__udyJPPop1(const Pjp_t Pjp)1068 FUNCTION Word_t j__udyJPPop1(
1069 const Pjp_t Pjp) // JP to count.
1070 {
1071 switch (JU_JPTYPE(Pjp))
1072 {
1073 #ifdef notdef // caller should shortcut and not even call with these:
1074
1075 case cJU_JPNULL1:
1076 case cJU_JPNULL2:
1077 case cJU_JPNULL3: return(0);
1078 #ifdef JU_64BIT
1079 case cJU_JPNULL4:
1080 case cJU_JPNULL5:
1081 case cJU_JPNULL6:
1082 case cJU_JPNULL7: return(0);
1083 #endif
1084 #endif // notdef
1085
1086 case cJU_JPBRANCH_L2:
1087 case cJU_JPBRANCH_B2:
1088 case cJU_JPBRANCH_U2: return(JU_JPBRANCH_POP0(Pjp,2) + 1);
1089
1090 case cJU_JPBRANCH_L3:
1091 case cJU_JPBRANCH_B3:
1092 case cJU_JPBRANCH_U3: return(JU_JPBRANCH_POP0(Pjp,3) + 1);
1093
1094 #ifdef JU_64BIT
1095 case cJU_JPBRANCH_L4:
1096 case cJU_JPBRANCH_B4:
1097 case cJU_JPBRANCH_U4: return(JU_JPBRANCH_POP0(Pjp,4) + 1);
1098
1099 case cJU_JPBRANCH_L5:
1100 case cJU_JPBRANCH_B5:
1101 case cJU_JPBRANCH_U5: return(JU_JPBRANCH_POP0(Pjp,5) + 1);
1102
1103 case cJU_JPBRANCH_L6:
1104 case cJU_JPBRANCH_B6:
1105 case cJU_JPBRANCH_U6: return(JU_JPBRANCH_POP0(Pjp,6) + 1);
1106
1107 case cJU_JPBRANCH_L7:
1108 case cJU_JPBRANCH_B7:
1109 case cJU_JPBRANCH_U7: return(JU_JPBRANCH_POP0(Pjp,7) + 1);
1110 #endif
1111
1112 #if (defined(JUDYL) || (! defined(JU_64BIT)))
1113 case cJU_JPLEAF1:
1114 #endif
1115 case cJU_JPLEAF2:
1116 case cJU_JPLEAF3:
1117 #ifdef JU_64BIT
1118 case cJU_JPLEAF4:
1119 case cJU_JPLEAF5:
1120 case cJU_JPLEAF6:
1121 case cJU_JPLEAF7:
1122 #endif
1123 case cJU_JPLEAF_B1: return(JU_JPLEAF_POP0(Pjp) + 1);
1124
1125 #ifdef JUDY1
1126 case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0 + 1);
1127 #endif
1128
1129 case cJU_JPIMMED_1_01:
1130 case cJU_JPIMMED_2_01:
1131 case cJU_JPIMMED_3_01: return(1);
1132 #ifdef JU_64BIT
1133 case cJU_JPIMMED_4_01:
1134 case cJU_JPIMMED_5_01:
1135 case cJU_JPIMMED_6_01:
1136 case cJU_JPIMMED_7_01: return(1);
1137 #endif
1138
1139 case cJU_JPIMMED_1_02: return(2);
1140 case cJU_JPIMMED_1_03: return(3);
1141 #if (defined(JUDY1) || defined(JU_64BIT))
1142 case cJU_JPIMMED_1_04: return(4);
1143 case cJU_JPIMMED_1_05: return(5);
1144 case cJU_JPIMMED_1_06: return(6);
1145 case cJU_JPIMMED_1_07: return(7);
1146 #endif
1147 #if (defined(JUDY1) && defined(JU_64BIT))
1148 case cJ1_JPIMMED_1_08: return(8);
1149 case cJ1_JPIMMED_1_09: return(9);
1150 case cJ1_JPIMMED_1_10: return(10);
1151 case cJ1_JPIMMED_1_11: return(11);
1152 case cJ1_JPIMMED_1_12: return(12);
1153 case cJ1_JPIMMED_1_13: return(13);
1154 case cJ1_JPIMMED_1_14: return(14);
1155 case cJ1_JPIMMED_1_15: return(15);
1156 #endif
1157
1158 #if (defined(JUDY1) || defined(JU_64BIT))
1159 case cJU_JPIMMED_2_02: return(2);
1160 case cJU_JPIMMED_2_03: return(3);
1161 #endif
1162 #if (defined(JUDY1) && defined(JU_64BIT))
1163 case cJ1_JPIMMED_2_04: return(4);
1164 case cJ1_JPIMMED_2_05: return(5);
1165 case cJ1_JPIMMED_2_06: return(6);
1166 case cJ1_JPIMMED_2_07: return(7);
1167 #endif
1168
1169 #if (defined(JUDY1) || defined(JU_64BIT))
1170 case cJU_JPIMMED_3_02: return(2);
1171 #endif
1172 #if (defined(JUDY1) && defined(JU_64BIT))
1173 case cJ1_JPIMMED_3_03: return(3);
1174 case cJ1_JPIMMED_3_04: return(4);
1175 case cJ1_JPIMMED_3_05: return(5);
1176
1177 case cJ1_JPIMMED_4_02: return(2);
1178 case cJ1_JPIMMED_4_03: return(3);
1179
1180 case cJ1_JPIMMED_5_02: return(2);
1181 case cJ1_JPIMMED_5_03: return(3);
1182
1183 case cJ1_JPIMMED_6_02: return(2);
1184
1185 case cJ1_JPIMMED_7_02: return(2);
1186 #endif
1187
1188 default: return(cJU_ALLONES);
1189 }
1190
1191 /*NOTREACHED*/
1192
1193 } // j__udyJPPop1()
1194