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 // Judy1Test() and JudyLGet() functions for Judy1 and JudyL.
19 // Compile with one of -DJUDY1 or -DJUDYL.
20
21 #if (! (defined(JUDY1) || defined(JUDYL)))
22 #error: One of -DJUDY1 or -DJUDYL must be specified.
23 #endif
24
25 #ifdef JUDY1
26 #include "Judy1.h"
27 #else
28 #include "JudyL.h"
29 #endif
30
31 #include "JudyPrivate1L.h"
32
33 #ifdef TRACEJPR // different macro name, for "retrieval" only.
34 #include "JudyPrintJP.c"
35 #endif
36
37
38 // ****************************************************************************
39 // J U D Y 1 T E S T
40 // J U D Y L G E T
41 //
42 // See the manual entry for details. Note support for "shortcut" entries to
43 // trees known to start with a JPM.
44
45 #ifdef JUDY1
46
47 #ifdef JUDYGETINLINE
j__udy1Test(Pvoid_t PArray,Word_t Index)48 FUNCTION int j__udy1Test
49 #else
50 FUNCTION int Judy1Test
51 #endif
52
53 #else // JUDYL
54
55 #ifdef JUDYGETINLINE
56 FUNCTION PPvoid_t j__udyLGet
57 #else
58 FUNCTION PPvoid_t JudyLGet
59 #endif
60
61 #endif // JUDYL
62 (
63 #ifdef JUDYGETINLINE
64 Pvoid_t PArray, // from which to retrieve.
65 Word_t Index // to retrieve.
66 #else
67 Pcvoid_t PArray, // from which to retrieve.
68 Word_t Index, // to retrieve.
69 PJError_t PJError // optional, for returning error info.
70 #endif
71 )
72 {
73 Pjp_t Pjp; // current JP while walking the tree.
74 Pjpm_t Pjpm; // for global accounting.
75 uint8_t Digit; // byte just decoded from Index.
76 Word_t Pop1; // leaf population (number of indexes).
77 Pjll_t Pjll; // pointer to LeafL.
78 DBGCODE(uint8_t ParentJPType;)
79
80 #ifndef JUDYGETINLINE
81
82 if (PArray == (Pcvoid_t) NULL) // empty array.
83 {
84 JUDY1CODE(return(0);)
85 JUDYLCODE(return((PPvoid_t) NULL);)
86 }
87
88 // ****************************************************************************
89 // PROCESS TOP LEVEL BRANCHES AND LEAF:
90
91 if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
92 {
93 Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
94 int posidx; // signed offset in leaf.
95
96 Pop1 = Pjlw[0] + 1;
97 posidx = j__udySearchLeafW(Pjlw + 1, Pop1, Index);
98
99 if (posidx >= 0)
100 {
101 JUDY1CODE(return(1);)
102 JUDYLCODE(return((PPvoid_t) (JL_LEAFWVALUEAREA(Pjlw, Pop1) + posidx));)
103 }
104 JUDY1CODE(return(0);)
105 JUDYLCODE(return((PPvoid_t) NULL);)
106 }
107
108 #endif // ! JUDYGETINLINE
109
110 Pjpm = P_JPM(PArray);
111 Pjp = &(Pjpm->jpm_JP); // top branch is below JPM.
112
113 // ****************************************************************************
114 // WALK THE JUDY TREE USING A STATE MACHINE:
115
116 ContinueWalk: // for going down one level; come here with Pjp set.
117
118 #ifdef TRACEJPR
119 JudyPrintJP(Pjp, "g", __LINE__);
120 #endif
121 switch (JU_JPTYPE(Pjp))
122 {
123
124 // Ensure the switch table starts at 0 for speed; otherwise more code is
125 // executed:
126
127 case 0: goto ReturnCorrupt; // save a little code.
128
129
130 // ****************************************************************************
131 // JPNULL*:
132 //
133 // Note: These are legitimate in a BranchU (only) and do not constitute a
134 // fault.
135
136 case cJU_JPNULL1:
137 case cJU_JPNULL2:
138 case cJU_JPNULL3:
139 #ifdef JU_64BIT
140 case cJU_JPNULL4:
141 case cJU_JPNULL5:
142 case cJU_JPNULL6:
143 case cJU_JPNULL7:
144 #endif
145 assert(ParentJPType >= cJU_JPBRANCH_U2);
146 assert(ParentJPType <= cJU_JPBRANCH_U);
147 JUDY1CODE(return(0);)
148 JUDYLCODE(return((PPvoid_t) NULL);)
149
150
151 // ****************************************************************************
152 // JPBRANCH_L*:
153 //
154 // Note: The use of JU_DCDNOTMATCHINDEX() in branches is not strictly
155 // required,since this can be done at leaf level, but it costs nothing to do it
156 // sooner, and it aborts an unnecessary traversal sooner.
157
158 case cJU_JPBRANCH_L2:
159
160 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
161 Digit = JU_DIGITATSTATE(Index, 2);
162 goto JudyBranchL;
163
164 case cJU_JPBRANCH_L3:
165
166 #ifdef JU_64BIT // otherwise its a no-op:
167 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
168 #endif
169 Digit = JU_DIGITATSTATE(Index, 3);
170 goto JudyBranchL;
171
172 #ifdef JU_64BIT
173 case cJU_JPBRANCH_L4:
174
175 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
176 Digit = JU_DIGITATSTATE(Index, 4);
177 goto JudyBranchL;
178
179 case cJU_JPBRANCH_L5:
180
181 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
182 Digit = JU_DIGITATSTATE(Index, 5);
183 goto JudyBranchL;
184
185 case cJU_JPBRANCH_L6:
186
187 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
188 Digit = JU_DIGITATSTATE(Index, 6);
189 goto JudyBranchL;
190
191 case cJU_JPBRANCH_L7:
192
193 // JU_DCDNOTMATCHINDEX() would be a no-op.
194 Digit = JU_DIGITATSTATE(Index, 7);
195 goto JudyBranchL;
196
197 #endif // JU_64BIT
198
199 case cJU_JPBRANCH_L:
200 {
201 Pjbl_t Pjbl;
202 int posidx;
203
204 Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
205
206 // Common code for all BranchLs; come here with Digit set:
207
208 JudyBranchL:
209 Pjbl = P_JBL(Pjp->jp_Addr);
210
211 posidx = 0;
212
213 do {
214 if (Pjbl->jbl_Expanse[posidx] == Digit)
215 { // found Digit; continue traversal:
216 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
217 Pjp = Pjbl->jbl_jp + posidx;
218 goto ContinueWalk;
219 }
220 } while (++posidx != Pjbl->jbl_NumJPs);
221
222 break;
223 }
224
225
226 // ****************************************************************************
227 // JPBRANCH_B*:
228
229 case cJU_JPBRANCH_B2:
230
231 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
232 Digit = JU_DIGITATSTATE(Index, 2);
233 goto JudyBranchB;
234
235 case cJU_JPBRANCH_B3:
236
237 #ifdef JU_64BIT // otherwise its a no-op:
238 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
239 #endif
240 Digit = JU_DIGITATSTATE(Index, 3);
241 goto JudyBranchB;
242
243
244 #ifdef JU_64BIT
245 case cJU_JPBRANCH_B4:
246
247 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
248 Digit = JU_DIGITATSTATE(Index, 4);
249 goto JudyBranchB;
250
251 case cJU_JPBRANCH_B5:
252
253 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
254 Digit = JU_DIGITATSTATE(Index, 5);
255 goto JudyBranchB;
256
257 case cJU_JPBRANCH_B6:
258
259 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
260 Digit = JU_DIGITATSTATE(Index, 6);
261 goto JudyBranchB;
262
263 case cJU_JPBRANCH_B7:
264
265 // JU_DCDNOTMATCHINDEX() would be a no-op.
266 Digit = JU_DIGITATSTATE(Index, 7);
267 goto JudyBranchB;
268
269 #endif // JU_64BIT
270
271 case cJU_JPBRANCH_B:
272 {
273 Pjbb_t Pjbb;
274 Word_t subexp; // in bitmap, 0..7.
275 BITMAPB_t BitMap; // for one subexpanse.
276 BITMAPB_t BitMask; // bit in BitMap for Indexs Digit.
277
278 Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
279
280 // Common code for all BranchBs; come here with Digit set:
281
282 JudyBranchB:
283 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
284 Pjbb = P_JBB(Pjp->jp_Addr);
285 subexp = Digit / cJU_BITSPERSUBEXPB;
286
287 BitMap = JU_JBB_BITMAP(Pjbb, subexp);
288 Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp));
289
290 BitMask = JU_BITPOSMASKB(Digit);
291
292 // No JP in subexpanse for Index => Index not found:
293
294 if (! (BitMap & BitMask)) break;
295
296 // Count JPs in the subexpanse below the one for Index:
297
298 Pjp += j__udyCountBitsB(BitMap & (BitMask - 1));
299
300 goto ContinueWalk;
301
302 } // case cJU_JPBRANCH_B*
303
304
305 // ****************************************************************************
306 // JPBRANCH_U*:
307 //
308 // Notice the reverse order of the cases, and falling through to the next case,
309 // for performance.
310
311 case cJU_JPBRANCH_U:
312
313 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
314 Pjp = JU_JBU_PJP(Pjp, Index, cJU_ROOTSTATE);
315
316 // If not a BranchU, traverse; otherwise fall into the next case, which makes
317 // this very fast code for a large Judy array (mainly BranchUs), especially
318 // when branches are already in the cache, such as for prev/next:
319
320 #ifndef JU_64BIT
321 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
322 #else
323 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U7) goto ContinueWalk;
324 #endif
325
326 #ifdef JU_64BIT
327 case cJU_JPBRANCH_U7:
328
329 // JU_DCDNOTMATCHINDEX() would be a no-op.
330 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
331 Pjp = JU_JBU_PJP(Pjp, Index, 7);
332
333 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U6) goto ContinueWalk;
334 // and fall through.
335
336 case cJU_JPBRANCH_U6:
337
338 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
339 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
340 Pjp = JU_JBU_PJP(Pjp, Index, 6);
341
342 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U5) goto ContinueWalk;
343 // and fall through.
344
345 case cJU_JPBRANCH_U5:
346
347 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
348 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
349 Pjp = JU_JBU_PJP(Pjp, Index, 5);
350
351 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U4) goto ContinueWalk;
352 // and fall through.
353
354 case cJU_JPBRANCH_U4:
355
356 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
357 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
358 Pjp = JU_JBU_PJP(Pjp, Index, 4);
359
360 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
361 // and fall through.
362
363 #endif // JU_64BIT
364
365 case cJU_JPBRANCH_U3:
366
367 #ifdef JU_64BIT // otherwise its a no-op:
368 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
369 #endif
370 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
371 Pjp = JU_JBU_PJP(Pjp, Index, 3);
372
373 if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U2) goto ContinueWalk;
374 // and fall through.
375
376 case cJU_JPBRANCH_U2:
377
378 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
379 DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
380 Pjp = JU_JBU_PJP(Pjp, Index, 2);
381
382 // Note: BranchU2 is a special case that must continue traversal to a leaf,
383 // immed, full, or null type:
384
385 goto ContinueWalk;
386
387
388 // ****************************************************************************
389 // JPLEAF*:
390 //
391 // Note: Here the calls of JU_DCDNOTMATCHINDEX() are necessary and check
392 // whether Index is out of the expanse of a narrow pointer.
393
394 #if (defined(JUDYL) || (! defined(JU_64BIT)))
395
396 case cJU_JPLEAF1:
397 {
398 int posidx; // signed offset in leaf.
399
400 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
401
402 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
403 Pjll = P_JLL(Pjp->jp_Addr);
404
405 if ((posidx = j__udySearchLeaf1(Pjll, Pop1, Index)) < 0) break;
406
407 JUDY1CODE(return(1);)
408 JUDYLCODE(return((PPvoid_t) (JL_LEAF1VALUEAREA(Pjll, Pop1) + posidx));)
409 }
410
411 #endif // (JUDYL || (! JU_64BIT))
412
413 case cJU_JPLEAF2:
414 {
415 int posidx; // signed offset in leaf.
416
417 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
418
419 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
420 Pjll = P_JLL(Pjp->jp_Addr);
421
422 if ((posidx = j__udySearchLeaf2(Pjll, Pop1, Index)) < 0) break;
423
424 JUDY1CODE(return(1);)
425 JUDYLCODE(return((PPvoid_t) (JL_LEAF2VALUEAREA(Pjll, Pop1) + posidx));)
426 }
427 case cJU_JPLEAF3:
428 {
429 int posidx; // signed offset in leaf.
430
431 #ifdef JU_64BIT // otherwise its a no-op:
432 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
433 #endif
434
435 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
436 Pjll = P_JLL(Pjp->jp_Addr);
437
438 if ((posidx = j__udySearchLeaf3(Pjll, Pop1, Index)) < 0) break;
439
440 JUDY1CODE(return(1);)
441 JUDYLCODE(return((PPvoid_t) (JL_LEAF3VALUEAREA(Pjll, Pop1) + posidx));)
442 }
443 #ifdef JU_64BIT
444 case cJU_JPLEAF4:
445 {
446 int posidx; // signed offset in leaf.
447
448 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
449
450 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
451 Pjll = P_JLL(Pjp->jp_Addr);
452
453 if ((posidx = j__udySearchLeaf4(Pjll, Pop1, Index)) < 0) break;
454
455 JUDY1CODE(return(1);)
456 JUDYLCODE(return((PPvoid_t) (JL_LEAF4VALUEAREA(Pjll, Pop1) + posidx));)
457 }
458 case cJU_JPLEAF5:
459 {
460 int posidx; // signed offset in leaf.
461
462 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
463
464 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
465 Pjll = P_JLL(Pjp->jp_Addr);
466
467 if ((posidx = j__udySearchLeaf5(Pjll, Pop1, Index)) < 0) break;
468
469 JUDY1CODE(return(1);)
470 JUDYLCODE(return((PPvoid_t) (JL_LEAF5VALUEAREA(Pjll, Pop1) + posidx));)
471 }
472
473 case cJU_JPLEAF6:
474 {
475 int posidx; // signed offset in leaf.
476
477 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
478
479 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
480 Pjll = P_JLL(Pjp->jp_Addr);
481
482 if ((posidx = j__udySearchLeaf6(Pjll, Pop1, Index)) < 0) break;
483
484 JUDY1CODE(return(1);)
485 JUDYLCODE(return((PPvoid_t) (JL_LEAF6VALUEAREA(Pjll, Pop1) + posidx));)
486 }
487 case cJU_JPLEAF7:
488 {
489 int posidx; // signed offset in leaf.
490
491 // JU_DCDNOTMATCHINDEX() would be a no-op.
492 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
493 Pjll = P_JLL(Pjp->jp_Addr);
494
495 if ((posidx = j__udySearchLeaf7(Pjll, Pop1, Index)) < 0) break;
496
497 JUDY1CODE(return(1);)
498 JUDYLCODE(return((PPvoid_t) (JL_LEAF7VALUEAREA(Pjll, Pop1) + posidx));)
499 }
500 #endif // JU_64BIT
501
502
503 // ****************************************************************************
504 // JPLEAF_B1:
505
506 case cJU_JPLEAF_B1:
507 {
508 Pjlb_t Pjlb;
509 #ifdef JUDYL
510 int posidx;
511 Word_t subexp; // in bitmap, 0..7.
512 BITMAPL_t BitMap; // for one subexpanse.
513 BITMAPL_t BitMask; // bit in BitMap for Indexs Digit.
514 Pjv_t Pjv;
515 #endif
516 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
517
518 Pjlb = P_JLB(Pjp->jp_Addr);
519
520 #ifdef JUDY1
521
522 // Simply check if Indexs bit is set in the bitmap:
523
524 if (JU_BITMAPTESTL(Pjlb, Index)) return(1);
525 break;
526
527 #else // JUDYL
528
529 // JudyL is much more complicated because of value area subarrays:
530
531 Digit = JU_DIGITATSTATE(Index, 1);
532 subexp = Digit / cJU_BITSPERSUBEXPL;
533 BitMap = JU_JLB_BITMAP(Pjlb, subexp);
534 BitMask = JU_BITPOSMASKL(Digit);
535
536 // No value in subexpanse for Index => Index not found:
537
538 if (! (BitMap & BitMask)) break;
539
540 // Count value areas in the subexpanse below the one for Index:
541
542 Pjv = P_JV(JL_JLB_PVALUE(Pjlb, subexp));
543 assert(Pjv != (Pjv_t) NULL);
544 posidx = j__udyCountBitsL(BitMap & (BitMask - 1));
545
546 return((PPvoid_t) (Pjv + posidx));
547
548 #endif // JUDYL
549
550 } // case cJU_JPLEAF_B1
551
552 #ifdef JUDY1
553
554 // ****************************************************************************
555 // JPFULLPOPU1:
556 //
557 // If the Index is in the expanse, it is necessarily valid (found).
558
559 case cJ1_JPFULLPOPU1:
560
561 if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
562 return(1);
563
564 #ifdef notdef // for future enhancements
565 #ifdef JU_64BIT
566
567 // Note: Need ? if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
568
569 case cJ1_JPFULLPOPU1m15:
570 if (Pjp->jp_1Index[14] == (uint8_t)Index) break;
571 case cJ1_JPFULLPOPU1m14:
572 if (Pjp->jp_1Index[13] == (uint8_t)Index) break;
573 case cJ1_JPFULLPOPU1m13:
574 if (Pjp->jp_1Index[12] == (uint8_t)Index) break;
575 case cJ1_JPFULLPOPU1m12:
576 if (Pjp->jp_1Index[11] == (uint8_t)Index) break;
577 case cJ1_JPFULLPOPU1m11:
578 if (Pjp->jp_1Index[10] == (uint8_t)Index) break;
579 case cJ1_JPFULLPOPU1m10:
580 if (Pjp->jp_1Index[9] == (uint8_t)Index) break;
581 case cJ1_JPFULLPOPU1m9:
582 if (Pjp->jp_1Index[8] == (uint8_t)Index) break;
583 case cJ1_JPFULLPOPU1m8:
584 if (Pjp->jp_1Index[7] == (uint8_t)Index) break;
585 #endif
586 case cJ1_JPFULLPOPU1m7:
587 if (Pjp->jp_1Index[6] == (uint8_t)Index) break;
588 case cJ1_JPFULLPOPU1m6:
589 if (Pjp->jp_1Index[5] == (uint8_t)Index) break;
590 case cJ1_JPFULLPOPU1m5:
591 if (Pjp->jp_1Index[4] == (uint8_t)Index) break;
592 case cJ1_JPFULLPOPU1m4:
593 if (Pjp->jp_1Index[3] == (uint8_t)Index) break;
594 case cJ1_JPFULLPOPU1m3:
595 if (Pjp->jp_1Index[2] == (uint8_t)Index) break;
596 case cJ1_JPFULLPOPU1m2:
597 if (Pjp->jp_1Index[1] == (uint8_t)Index) break;
598 case cJ1_JPFULLPOPU1m1:
599 if (Pjp->jp_1Index[0] == (uint8_t)Index) break;
600
601 return(1); // found, not in exclusion list
602
603 #endif // JUDY1
604 #endif // notdef
605
606 // ****************************************************************************
607 // JPIMMED*:
608 //
609 // Note that the contents of jp_DcdPopO are different for cJU_JPIMMED_*_01:
610
611 case cJU_JPIMMED_1_01:
612 case cJU_JPIMMED_2_01:
613 case cJU_JPIMMED_3_01:
614 #ifdef JU_64BIT
615 case cJU_JPIMMED_4_01:
616 case cJU_JPIMMED_5_01:
617 case cJU_JPIMMED_6_01:
618 case cJU_JPIMMED_7_01:
619 #endif
620 if (JU_JPDCDPOP0(Pjp) != JU_TRIMTODCDSIZE(Index)) break;
621
622 JUDY1CODE(return(1);)
623 JUDYLCODE(return((PPvoid_t) &(Pjp->jp_Addr));) // immediate value area.
624
625
626 // Macros to make code more readable and avoid dup errors
627
628 #ifdef JUDY1
629
630 #define CHECKINDEXNATIVE(LEAF_T, PJP, IDX, INDEX) \
631 if (((LEAF_T *)((PJP)->jp_1Index))[(IDX) - 1] == (LEAF_T)(INDEX)) \
632 return(1)
633
634 #define CHECKLEAFNONNAT(LFBTS, PJP, INDEX, IDX, COPY) \
635 { \
636 Word_t i_ndex; \
637 uint8_t *a_ddr; \
638 a_ddr = (PJP)->jp_1Index + (((IDX) - 1) * (LFBTS)); \
639 COPY(i_ndex, a_ddr); \
640 if (i_ndex == JU_LEASTBYTES((INDEX), (LFBTS))) \
641 return(1); \
642 }
643 #endif
644
645 #ifdef JUDYL
646
647 #define CHECKINDEXNATIVE(LEAF_T, PJP, IDX, INDEX) \
648 if (((LEAF_T *)((PJP)->jp_LIndex))[(IDX) - 1] == (LEAF_T)(INDEX)) \
649 return((PPvoid_t)(P_JV((PJP)->jp_Addr) + (IDX) - 1))
650
651 #define CHECKLEAFNONNAT(LFBTS, PJP, INDEX, IDX, COPY) \
652 { \
653 Word_t i_ndex; \
654 uint8_t *a_ddr; \
655 a_ddr = (PJP)->jp_LIndex + (((IDX) - 1) * (LFBTS)); \
656 COPY(i_ndex, a_ddr); \
657 if (i_ndex == JU_LEASTBYTES((INDEX), (LFBTS))) \
658 return((PPvoid_t)(P_JV((PJP)->jp_Addr) + (IDX) - 1)); \
659 }
660 #endif
661
662 #if (defined(JUDY1) && defined(JU_64BIT))
663 case cJ1_JPIMMED_1_15: CHECKINDEXNATIVE(uint8_t, Pjp, 15, Index);
664 case cJ1_JPIMMED_1_14: CHECKINDEXNATIVE(uint8_t, Pjp, 14, Index);
665 case cJ1_JPIMMED_1_13: CHECKINDEXNATIVE(uint8_t, Pjp, 13, Index);
666 case cJ1_JPIMMED_1_12: CHECKINDEXNATIVE(uint8_t, Pjp, 12, Index);
667 case cJ1_JPIMMED_1_11: CHECKINDEXNATIVE(uint8_t, Pjp, 11, Index);
668 case cJ1_JPIMMED_1_10: CHECKINDEXNATIVE(uint8_t, Pjp, 10, Index);
669 case cJ1_JPIMMED_1_09: CHECKINDEXNATIVE(uint8_t, Pjp, 9, Index);
670 case cJ1_JPIMMED_1_08: CHECKINDEXNATIVE(uint8_t, Pjp, 8, Index);
671 #endif
672 #if (defined(JUDY1) || defined(JU_64BIT))
673 case cJU_JPIMMED_1_07: CHECKINDEXNATIVE(uint8_t, Pjp, 7, Index);
674 case cJU_JPIMMED_1_06: CHECKINDEXNATIVE(uint8_t, Pjp, 6, Index);
675 case cJU_JPIMMED_1_05: CHECKINDEXNATIVE(uint8_t, Pjp, 5, Index);
676 case cJU_JPIMMED_1_04: CHECKINDEXNATIVE(uint8_t, Pjp, 4, Index);
677 #endif
678 case cJU_JPIMMED_1_03: CHECKINDEXNATIVE(uint8_t, Pjp, 3, Index);
679 case cJU_JPIMMED_1_02: CHECKINDEXNATIVE(uint8_t, Pjp, 2, Index);
680 CHECKINDEXNATIVE(uint8_t, Pjp, 1, Index);
681 break;
682
683 #if (defined(JUDY1) && defined(JU_64BIT))
684 case cJ1_JPIMMED_2_07: CHECKINDEXNATIVE(uint16_t, Pjp, 7, Index);
685 case cJ1_JPIMMED_2_06: CHECKINDEXNATIVE(uint16_t, Pjp, 6, Index);
686 case cJ1_JPIMMED_2_05: CHECKINDEXNATIVE(uint16_t, Pjp, 5, Index);
687 case cJ1_JPIMMED_2_04: CHECKINDEXNATIVE(uint16_t, Pjp, 4, Index);
688 #endif
689 #if (defined(JUDY1) || defined(JU_64BIT))
690 case cJU_JPIMMED_2_03: CHECKINDEXNATIVE(uint16_t, Pjp, 3, Index);
691 case cJU_JPIMMED_2_02: CHECKINDEXNATIVE(uint16_t, Pjp, 2, Index);
692 CHECKINDEXNATIVE(uint16_t, Pjp, 1, Index);
693 break;
694 #endif
695
696 #if (defined(JUDY1) && defined(JU_64BIT))
697 case cJ1_JPIMMED_3_05:
698 CHECKLEAFNONNAT(3, Pjp, Index, 5, JU_COPY3_PINDEX_TO_LONG);
699 case cJ1_JPIMMED_3_04:
700 CHECKLEAFNONNAT(3, Pjp, Index, 4, JU_COPY3_PINDEX_TO_LONG);
701 case cJ1_JPIMMED_3_03:
702 CHECKLEAFNONNAT(3, Pjp, Index, 3, JU_COPY3_PINDEX_TO_LONG);
703 #endif
704 #if (defined(JUDY1) || defined(JU_64BIT))
705 case cJU_JPIMMED_3_02:
706 CHECKLEAFNONNAT(3, Pjp, Index, 2, JU_COPY3_PINDEX_TO_LONG);
707 CHECKLEAFNONNAT(3, Pjp, Index, 1, JU_COPY3_PINDEX_TO_LONG);
708 break;
709 #endif
710
711 #if (defined(JUDY1) && defined(JU_64BIT))
712
713 case cJ1_JPIMMED_4_03: CHECKINDEXNATIVE(uint32_t, Pjp, 3, Index);
714 case cJ1_JPIMMED_4_02: CHECKINDEXNATIVE(uint32_t, Pjp, 2, Index);
715 CHECKINDEXNATIVE(uint32_t, Pjp, 1, Index);
716 break;
717
718 case cJ1_JPIMMED_5_03:
719 CHECKLEAFNONNAT(5, Pjp, Index, 3, JU_COPY5_PINDEX_TO_LONG);
720 case cJ1_JPIMMED_5_02:
721 CHECKLEAFNONNAT(5, Pjp, Index, 2, JU_COPY5_PINDEX_TO_LONG);
722 CHECKLEAFNONNAT(5, Pjp, Index, 1, JU_COPY5_PINDEX_TO_LONG);
723 break;
724
725 case cJ1_JPIMMED_6_02:
726 CHECKLEAFNONNAT(6, Pjp, Index, 2, JU_COPY6_PINDEX_TO_LONG);
727 CHECKLEAFNONNAT(6, Pjp, Index, 1, JU_COPY6_PINDEX_TO_LONG);
728 break;
729
730 case cJ1_JPIMMED_7_02:
731 CHECKLEAFNONNAT(7, Pjp, Index, 2, JU_COPY7_PINDEX_TO_LONG);
732 CHECKLEAFNONNAT(7, Pjp, Index, 1, JU_COPY7_PINDEX_TO_LONG);
733 break;
734
735 #endif // (JUDY1 && JU_64BIT)
736
737
738 // ****************************************************************************
739 // INVALID JP TYPE:
740
741 default:
742
743 ReturnCorrupt:
744
745 #ifdef JUDYGETINLINE // Pjpm is known to be non-null:
746 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
747 #else
748 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
749 #endif
750 JUDY1CODE(return(JERRI );)
751 JUDYLCODE(return(PPJERR);)
752
753 } // switch on JP type
754
755 JUDY1CODE(return(0);)
756 JUDYLCODE(return((PPvoid_t) NULL);)
757
758 } // Judy1Test() / JudyLGet()
759
760
761 #ifndef JUDYGETINLINE // only compile the following function once:
762 #ifdef DEBUG
763
764 // ****************************************************************************
765 // J U D Y C H E C K P O P
766 //
767 // Given a pointer to a Judy array, traverse the entire array to ensure
768 // population counts add up correctly. This can catch various coding errors.
769 //
770 // Since walking the entire tree is probably time-consuming, enable this
771 // function by setting env parameter $CHECKPOP to first call at which to start
772 // checking. Note: This function is called both from insert and delete code.
773 //
774 // Note: Even though this function does nothing useful for LEAFW leaves, its
775 // good practice to call it anyway, and cheap too.
776 //
777 // TBD: This is a debug-only check function similar to JudyCheckSorted(), but
778 // since it walks the tree it is Judy1/JudyL-specific and must live in a source
779 // file that is built both ways.
780 //
781 // TBD: As feared, enabling this code for every insert/delete makes Judy
782 // deathly slow, even for a small tree (10K indexes). Its not so bad if
783 // present but disabled (<1% slowdown measured). Still, should it be ifdefd
784 // other than DEBUG and/or called less often?
785 //
786 // TBD: Should this "population checker" be expanded to a comprehensive tree
787 // checker? It currently detects invalid LEAFW/JP types as well as inconsistent
788 // pop1s. Other possible checks, all based on essentially redundant data in
789 // the Judy tree, include:
790 //
791 // - Zero LS bits in jp_Addr field.
792 //
793 // - Correct Dcd bits.
794 //
795 // - Consistent JP types (always descending down the tree).
796 //
797 // - Sorted linear lists in BranchLs and leaves (using JudyCheckSorted(), but
798 // ideally that function is already called wherever appropriate after any
799 // linear list is modified).
800 //
801 // - Any others possible?
802
803 #include <stdlib.h> // for getenv() and atol().
804
805 static Word_t JudyCheckPopSM(Pjp_t Pjp, Word_t RootPop1);
806
JudyCheckPop(Pvoid_t PArray)807 FUNCTION void JudyCheckPop(
808 Pvoid_t PArray)
809 {
810 static bool_t checked = FALSE; // already checked env parameter.
811 static bool_t enabled = FALSE; // env parameter set.
812 static bool_t active = FALSE; // calls >= callsmin.
813 static Word_t callsmin; // start point from $CHECKPOP.
814 static Word_t calls = 0; // times called so far.
815
816
817 // CHECK FOR EXTERNAL ENABLING:
818
819 if (! checked) // only check once.
820 {
821 char * value; // for getenv().
822
823 checked = TRUE;
824
825 if ((value = getenv("CHECKPOP")) == (char *) NULL)
826 {
827 #ifdef notdef
828 // Take this out because nightly tests want to be flavor-independent; its not
829 // OK to emit special non-error output from the debug flavor:
830
831 (void) puts("JudyCheckPop() present but not enabled by "
832 "$CHECKPOP env parameter; set it to the number of "
833 "calls at which to begin checking");
834 #endif
835 return;
836 }
837
838 callsmin = atol(value); // note: non-number evaluates to 0.
839 enabled = TRUE;
840
841 (void) printf("JudyCheckPop() present and enabled; callsmin = "
842 "%lu\n", callsmin);
843 }
844 else if (! enabled) return;
845
846 // Previously or just now enabled; check if non-active or newly active:
847
848 if (! active)
849 {
850 if (++calls < callsmin) return;
851
852 (void) printf("JudyCheckPop() activated at call %lu\n", calls);
853 active = TRUE;
854 }
855
856 // IGNORE LEAFW AT TOP OF TREE:
857
858 if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
859 return;
860
861 // Check JPM pop0 against tree, recursively:
862 //
863 // Note: The traversal code in JudyCheckPopSM() is simplest when the case
864 // statement for each JP type compares the pop1 for that JP to its subtree (if
865 // any) after traversing the subtree (thats the hard part) and adding up
866 // actual pop1s. A top branchs JP in the JPM does not have room for a
867 // full-word pop1, so pass it in as a special case.
868
869 {
870 Pjpm_t Pjpm = P_JPM(PArray);
871 (void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1);
872 return;
873 }
874
875 } // JudyCheckPop()
876
877
878 // ****************************************************************************
879 // J U D Y C H E C K P O P S M
880 //
881 // Recursive state machine (subroutine) for JudyCheckPop(): Given a Pjp (other
882 // than JPNULL*; caller should shortcut) and the root population for top-level
883 // branches, check the subtrees actual pop1 against its nominal value, and
884 // return the total pop1 for the subtree.
885 //
886 // Note: Expect RootPop1 to be ignored at lower levels, so pass down 0, which
887 // should pop an assertion if this expectation is violated.
888
JudyCheckPopSM(Pjp_t Pjp,Word_t RootPop1)889 FUNCTION static Word_t JudyCheckPopSM(
890 Pjp_t Pjp, // top of subtree.
891 Word_t RootPop1) // whole array, for top-level branches only.
892 {
893 Word_t pop1_jp; // nominal population from the JP.
894 Word_t pop1 = 0; // actual population at this level.
895 Word_t offset; // in a branch.
896
897 #define PREPBRANCH(cPopBytes,Next) \
898 pop1_jp = JU_JPBRANCH_POP0(Pjp, cPopBytes) + 1; goto Next
899
900 assert((((Word_t) (Pjp->jp_Addr)) & 7) == 3);
901 switch (JU_JPTYPE(Pjp))
902 {
903
904 case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL);
905 case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL);
906 #ifdef JU_64BIT
907 case cJU_JPBRANCH_L4: PREPBRANCH(4, BranchL);
908 case cJU_JPBRANCH_L5: PREPBRANCH(5, BranchL);
909 case cJU_JPBRANCH_L6: PREPBRANCH(6, BranchL);
910 case cJU_JPBRANCH_L7: PREPBRANCH(7, BranchL);
911 #endif
912 case cJU_JPBRANCH_L: pop1_jp = RootPop1;
913 {
914 Pjbl_t Pjbl;
915 BranchL:
916 Pjbl = P_JBL(Pjp->jp_Addr);
917
918 for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset)
919 pop1 += JudyCheckPopSM((Pjbl->jbl_jp) + offset, 0);
920
921 assert(pop1_jp == pop1);
922 return(pop1);
923 }
924
925 case cJU_JPBRANCH_B2: PREPBRANCH(2, BranchB);
926 case cJU_JPBRANCH_B3: PREPBRANCH(3, BranchB);
927 #ifdef JU_64BIT
928 case cJU_JPBRANCH_B4: PREPBRANCH(4, BranchB);
929 case cJU_JPBRANCH_B5: PREPBRANCH(5, BranchB);
930 case cJU_JPBRANCH_B6: PREPBRANCH(6, BranchB);
931 case cJU_JPBRANCH_B7: PREPBRANCH(7, BranchB);
932 #endif
933 case cJU_JPBRANCH_B: pop1_jp = RootPop1;
934 {
935 Word_t subexp;
936 Word_t jpcount;
937 Pjbb_t Pjbb;
938 BranchB:
939 Pjbb = P_JBB(Pjp->jp_Addr);
940
941 for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
942 {
943 jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
944
945 for (offset = 0; offset < jpcount; ++offset)
946 {
947 pop1 += JudyCheckPopSM(P_JP(JU_JBB_PJP(Pjbb, subexp))
948 + offset, 0);
949 }
950 }
951
952 assert(pop1_jp == pop1);
953 return(pop1);
954 }
955
956 case cJU_JPBRANCH_U2: PREPBRANCH(2, BranchU);
957 case cJU_JPBRANCH_U3: PREPBRANCH(3, BranchU);
958 #ifdef JU_64BIT
959 case cJU_JPBRANCH_U4: PREPBRANCH(4, BranchU);
960 case cJU_JPBRANCH_U5: PREPBRANCH(5, BranchU);
961 case cJU_JPBRANCH_U6: PREPBRANCH(6, BranchU);
962 case cJU_JPBRANCH_U7: PREPBRANCH(7, BranchU);
963 #endif
964 case cJU_JPBRANCH_U: pop1_jp = RootPop1;
965 {
966 Pjbu_t Pjbu;
967 BranchU:
968 Pjbu = P_JBU(Pjp->jp_Addr);
969
970 for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
971 {
972 if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1)
973 && ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX))
974 {
975 continue; // skip null JP to save time.
976 }
977
978 pop1 += JudyCheckPopSM((Pjbu->jbu_jp) + offset, 0);
979 }
980
981 assert(pop1_jp == pop1);
982 return(pop1);
983 }
984
985
986 // -- Cases below here terminate and do not recurse. --
987 //
988 // For all of these cases except JPLEAF_B1, there is no way to check the JPs
989 // pop1 against the object itself; just return the pop1; but for linear leaves,
990 // a bounds check is possible.
991
992 #define CHECKLEAF(MaxPop1) \
993 pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
994 assert(pop1 >= 1); \
995 assert(pop1 <= (MaxPop1)); \
996 return(pop1)
997
998 #if (defined(JUDYL) || (! defined(JU_64BIT)))
999 case cJU_JPLEAF1: CHECKLEAF(cJU_LEAF1_MAXPOP1);
1000 #endif
1001 case cJU_JPLEAF2: CHECKLEAF(cJU_LEAF2_MAXPOP1);
1002 case cJU_JPLEAF3: CHECKLEAF(cJU_LEAF3_MAXPOP1);
1003 #ifdef JU_64BIT
1004 case cJU_JPLEAF4: CHECKLEAF(cJU_LEAF4_MAXPOP1);
1005 case cJU_JPLEAF5: CHECKLEAF(cJU_LEAF5_MAXPOP1);
1006 case cJU_JPLEAF6: CHECKLEAF(cJU_LEAF6_MAXPOP1);
1007 case cJU_JPLEAF7: CHECKLEAF(cJU_LEAF7_MAXPOP1);
1008 #endif
1009
1010 case cJU_JPLEAF_B1:
1011 {
1012 Word_t subexp;
1013 Pjlb_t Pjlb;
1014
1015 pop1_jp = JU_JPLEAF_POP0(Pjp) + 1;
1016
1017 Pjlb = P_JLB(Pjp->jp_Addr);
1018
1019 for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
1020 pop1 += j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
1021
1022 assert(pop1_jp == pop1);
1023 return(pop1);
1024 }
1025
1026 JUDY1CODE(case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0);)
1027
1028 case cJU_JPIMMED_1_01: return(1);
1029 case cJU_JPIMMED_2_01: return(1);
1030 case cJU_JPIMMED_3_01: return(1);
1031 #ifdef JU_64BIT
1032 case cJU_JPIMMED_4_01: return(1);
1033 case cJU_JPIMMED_5_01: return(1);
1034 case cJU_JPIMMED_6_01: return(1);
1035 case cJU_JPIMMED_7_01: return(1);
1036 #endif
1037
1038 case cJU_JPIMMED_1_02: return(2);
1039 case cJU_JPIMMED_1_03: return(3);
1040 #if (defined(JUDY1) || defined(JU_64BIT))
1041 case cJU_JPIMMED_1_04: return(4);
1042 case cJU_JPIMMED_1_05: return(5);
1043 case cJU_JPIMMED_1_06: return(6);
1044 case cJU_JPIMMED_1_07: return(7);
1045 #endif
1046 #if (defined(JUDY1) && defined(JU_64BIT))
1047 case cJ1_JPIMMED_1_08: return(8);
1048 case cJ1_JPIMMED_1_09: return(9);
1049 case cJ1_JPIMMED_1_10: return(10);
1050 case cJ1_JPIMMED_1_11: return(11);
1051 case cJ1_JPIMMED_1_12: return(12);
1052 case cJ1_JPIMMED_1_13: return(13);
1053 case cJ1_JPIMMED_1_14: return(14);
1054 case cJ1_JPIMMED_1_15: return(15);
1055 #endif
1056
1057 #if (defined(JUDY1) || defined(JU_64BIT))
1058 case cJU_JPIMMED_2_02: return(2);
1059 case cJU_JPIMMED_2_03: return(3);
1060 #endif
1061 #if (defined(JUDY1) && defined(JU_64BIT))
1062 case cJ1_JPIMMED_2_04: return(4);
1063 case cJ1_JPIMMED_2_05: return(5);
1064 case cJ1_JPIMMED_2_06: return(6);
1065 case cJ1_JPIMMED_2_07: return(7);
1066 #endif
1067
1068 #if (defined(JUDY1) || defined(JU_64BIT))
1069 case cJU_JPIMMED_3_02: return(2);
1070 #endif
1071 #if (defined(JUDY1) && defined(JU_64BIT))
1072 case cJ1_JPIMMED_3_03: return(3);
1073 case cJ1_JPIMMED_3_04: return(4);
1074 case cJ1_JPIMMED_3_05: return(5);
1075
1076 case cJ1_JPIMMED_4_02: return(2);
1077 case cJ1_JPIMMED_4_03: return(3);
1078 case cJ1_JPIMMED_5_02: return(2);
1079 case cJ1_JPIMMED_5_03: return(3);
1080 case cJ1_JPIMMED_6_02: return(2);
1081 case cJ1_JPIMMED_7_02: return(2);
1082 #endif
1083
1084 } // switch (JU_JPTYPE(Pjp))
1085
1086 assert(FALSE); // unrecognized JP type => corruption.
1087 return(0); // to make some compilers happy.
1088
1089 } // JudyCheckPopSM()
1090
1091 #endif // DEBUG
1092 #endif // ! JUDYGETINLINE
1093