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.54 $ $Source: /judy/src/JudyCommon/JudyPrevNext.c $
19 //
20 // Judy*Prev() and Judy*Next() functions for Judy1 and JudyL.
21 // Compile with one of -DJUDY1 or -DJUDYL.
22 //
23 // Compile with -DJUDYNEXT for the Judy*Next() function; otherwise defaults to
24 // Judy*Prev().
25
26 #if (! (defined(JUDY1) || defined(JUDYL)))
27 #error: One of -DJUDY1 or -DJUDYL must be specified.
28 #endif
29
30 #ifndef JUDYNEXT
31 #ifndef JUDYPREV
32 #define JUDYPREV 1 // neither set => use default.
33 #endif
34 #endif
35
36 #ifdef JUDY1
37 #include "Judy1.h"
38 #else
39 #include "JudyL.h"
40 #endif
41
42 #include "JudyPrivate1L.h"
43
44
45 // ****************************************************************************
46 // J U D Y 1 P R E V
47 // J U D Y 1 N E X T
48 // J U D Y L P R E V
49 // J U D Y L N E X T
50 //
51 // See the manual entry for the API.
52 //
53 // OVERVIEW OF Judy*Prev():
54 //
55 // Use a reentrant switch statement (state machine, SM1 = "get") to decode the
56 // callers *PIndex-1, starting with the (PArray), through branches, if
57 // any, down to an immediate or a leaf. Look for *PIndex-1 in that leaf, and
58 // if found, return it.
59 //
60 // A dead end is either a branch that does not contain a JP for the appropriate
61 // digit in *PIndex-1, or a leaf that does not contain the undecoded digits of
62 // *PIndex-1. Upon reaching a dead end, backtrack through the leaf/branches
63 // that were just traversed, using a list (history) of parent JPs that is built
64 // while going forward in SM1Get. Start with the current leaf or branch. In a
65 // backtracked leaf, look for an Index less than *PIndex-1. In each
66 // backtracked branch, look "sideways" for the next JP, if any, lower than the
67 // one for the digit (from *PIndex-1) that was previously decoded. While
68 // backtracking, if a leaf has no previous Index or a branch has no lower JP,
69 // go to its parent branch in turn. Upon reaching the JRP, return failure, "no
70 // previous Index". The backtrack process is sufficiently different from
71 // SM1Get to merit its own separate reentrant switch statement (SM2 =
72 // "backtrack").
73 //
74 // While backtracking, upon finding a lower JP in a branch, there is certain to
75 // be a "prev" Index under that JP (unless the Judy array is corrupt).
76 // Traverse forward again, this time taking the last (highest, right-most) JP
77 // in each branch, and the last (highest) Index upon reaching an immediate or a
78 // leaf. This traversal is sufficiently different from SM1Get and SM2Backtrack
79 // to merit its own separate reentrant switch statement (SM3 = "findlimit").
80 //
81 // "Decode" bytes in JPs complicate this process a little. In SM1Get, when a
82 // JP is a narrow pointer, that is, when states are skipped (so the skipped
83 // digits are stored in jp_DcdPopO), compare the relevant digits to the same
84 // digits in *PIndex-1. If they are EQUAL, proceed in SM1Get as before. If
85 // jp_DcdPopOs digits are GREATER, treat the JP as a dead end and proceed in
86 // SM2Backtrack. If jp_DcdPopOs digits are LESS, treat the JP as if it had
87 // just been found during a backtrack and proceed directly in SM3Findlimit.
88 //
89 // Note that Decode bytes can be ignored in SM3Findlimit; they dont matter.
90 // Also note that in practice the Decode bytes are routinely compared with
91 // *PIndex-1 because thats simpler and no slower than first testing for
92 // narrowness.
93 //
94 // Decode bytes also make it unnecessary to construct the Index to return (the
95 // revised *PIndex) during the search. This step is deferred until finding an
96 // Index during backtrack or findlimit, before returning it. The first digit
97 // of *PIndex is derived (saved) based on which JP is used in a JRP branch.
98 // The remaining digits are obtained from the jp_DcdPopO field in the JP (if
99 // any) above the immediate or leaf containing the found (prev) Index, plus the
100 // remaining digit(s) in the immediate or leaf itself. In the case of a LEAFW,
101 // the Index to return is found directly in the leaf.
102 //
103 // Note: Theoretically, as described above, upon reaching a dead end, SM1Get
104 // passes control to SM2Backtrack to look sideways, even in a leaf. Actually
105 // its a little more efficient for the SM1Get leaf cases to shortcut this and
106 // take care of the sideways searches themselves. Hence the history list only
107 // contains branch JPs, and SM2Backtrack only handles branches. In fact, even
108 // the branch handling cases in SM1Get do some shortcutting (sideways
109 // searching) to avoid pushing history and calling SM2Backtrack unnecessarily.
110 //
111 // Upon reaching an Index to return after backtracking, *PIndex must be
112 // modified to the found Index. In principle this could be done by building
113 // the Index from a saved rootdigit (in the top branch) plus the Dcd bytes from
114 // the parent JP plus the appropriate Index bytes from the leaf. However,
115 // Immediates are difficult because their parent JPs lack one (last) digit. So
116 // instead just build the *PIndex to return "top down" while backtracking and
117 // findlimiting.
118 //
119 // This function is written iteratively for speed, rather than recursively.
120 //
121 // CAVEATS:
122 //
123 // Why use a backtrack list (history stack), since it has finite size? The
124 // size is small for Judy on both 32-bit and 64-bit systems, and a list (really
125 // just an array) is fast to maintain and use. Other alternatives include
126 // doing a lookahead (lookaside) in each branch while traversing forward
127 // (decoding), and restarting from the top upon a dead end.
128 //
129 // A lookahead means noting the last branch traversed which contained a
130 // non-null JP lower than the one specified by a digit in *PIndex-1, and
131 // returning to that point for SM3Findlimit. This seems like a good idea, and
132 // should be pretty cheap for linear and bitmap branches, but it could result
133 // in up to 31 unnecessary additional cache line fills (in extreme cases) for
134 // every uncompressed branch traversed. We have considered means of attaching
135 // to or hiding within an uncompressed branch (in null JPs) a "cache line map"
136 // or other structure, such as an offset to the next non-null JP, that would
137 // speed this up, but it seems unnecessary merely to avoid having a
138 // finite-length list (array). (If JudySL is ever made "native", the finite
139 // list length will be an issue.)
140 //
141 // Restarting at the top of the Judy array after a dead end requires a careful
142 // modification of *PIndex-1 to decrement the digit for the parent branch and
143 // set the remaining lower digits to all 1s. This must be repeated each time a
144 // parent branch contains another dead end, so even though it should all happen
145 // in cache, the CPU time can be excessive. (For JudySL or an equivalent
146 // "infinitely deep" Judy array, consider a hybrid of a large, finite,
147 // "circular" list and a restart-at-top when the list is backtracked to
148 // exhaustion.)
149 //
150 // Why search for *PIndex-1 instead of *PIndex during SM1Get? In rare
151 // instances this prevents an unnecessary decode down the wrong path followed
152 // by a backtrack; its pretty cheap to set up initially; and it means the
153 // SM1Get machine can simply return if/when it finds that Index.
154 //
155 // TBD: Wed like to enhance this function to make successive searches faster.
156 // This would require saving some previous state, including the previous Index
157 // returned, and in which leaf it was found. If the next call is for the same
158 // Index and the array has not been modified, start at the same leaf. This
159 // should be much easier to implement since this is iterative rather than
160 // recursive code.
161 //
162 // VARIATIONS FOR Judy*Next():
163 //
164 // The Judy*Next() code is nearly a perfect mirror of the Judy*Prev() code.
165 // See the Judy*Prev() overview comments, and mentally switch the following:
166 //
167 // - "*PIndex-1" => "*PIndex+1"
168 // - "less than" => "greater than"
169 // - "lower" => "higher"
170 // - "lowest" => "highest"
171 // - "next-left" => "next-right"
172 // - "right-most" => "left-most"
173 //
174 // Note: SM3Findlimit could be called SM3Findmax/SM3Findmin, but a common name
175 // for both Prev and Next means many fewer ifdefs in this code.
176 //
177 // TBD: Currently this code traverses a JP whether its expanse is partially or
178 // completely full (populated). For Judy1 (only), since there is no value area
179 // needed, consider shortcutting to a "success" return upon encountering a full
180 // JP in SM1Get (or even SM3Findlimit?) A full JP looks like this:
181 //
182 // (((JU_JPDCDPOP0(Pjp) ^ cJU_ALLONES) & cJU_POP0MASK(cLevel)) == 0)
183
184 #ifdef JUDY1
185 #ifdef JUDYPREV
Judy1Prev(Pcvoid_t PArray,Word_t * PIndex,PJError_t PJError)186 FUNCTION int Judy1Prev
187 #else
188 FUNCTION int Judy1Next
189 #endif
190 #else
191 #ifdef JUDYPREV
192 FUNCTION PPvoid_t JudyLPrev
193 #else
194 FUNCTION PPvoid_t JudyLNext
195 #endif
196 #endif
197 (
198 Pcvoid_t PArray, // Judy array to search.
199 Word_t * PIndex, // starting point and result.
200 PJError_t PJError // optional, for returning error info.
201 )
202 {
203 Pjp_t Pjp, Pjp2; // current JPs.
204 Pjbl_t Pjbl; // Pjp->jp_Addr masked and cast to types:
205 Pjbb_t Pjbb;
206 Pjbu_t Pjbu;
207
208 // Note: The following initialization is not strictly required but it makes
209 // gcc -Wall happy because there is an "impossible" path from Immed handling to
210 // SM1LeafLImm code that looks like Pjll might be used before set:
211
212 Pjll_t Pjll = (Pjll_t) NULL;
213 Word_t state; // current state in SM.
214 Word_t digit; // next digit to decode from Index.
215
216 // Note: The following initialization is not strictly required but it makes
217 // gcc -Wall happy because there is an "impossible" path from Immed handling to
218 // SM1LeafLImm code (for JudyL & JudyPrev only) that looks like pop1 might be
219 // used before set:
220
221 #if (defined(JUDYL) && defined(JUDYPREV))
222 Word_t pop1 = 0; // in a leaf.
223 #else
224 Word_t pop1; // in a leaf.
225 #endif
226 int offset; // linear branch/leaf, from j__udySearchLeaf*().
227 int subexp; // subexpanse in a bitmap branch.
228 Word_t bitposmask; // bit in bitmap for Index.
229
230 // History for SM2Backtrack:
231 //
232 // For a given histnum, APjphist[histnum] is a parent JP that points to a
233 // branch, and Aoffhist[histnum] is the offset of the NEXT JP in the branch to
234 // which the parent JP points. The meaning of Aoffhist[histnum] depends on the
235 // type of branch to which the parent JP points:
236 //
237 // Linear: Offset of the next JP in the JP list.
238 //
239 // Bitmap: Which subexpanse, plus the offset of the next JP in the
240 // subexpanses JP list (to avoid bit-counting again), plus for Judy*Next(),
241 // hidden one byte to the left, which digit, because Judy*Next() also needs
242 // this.
243 //
244 // Uncompressed: Digit, which is actually the offset of the JP in the branch.
245 //
246 // Note: Only branch JPs are stored in APjphist[] because, as explained
247 // earlier, SM1Get shortcuts sideways searches in leaves (and even in branches
248 // in some cases), so SM2Backtrack only handles branches.
249
250 #define HISTNUMMAX cJU_ROOTSTATE // maximum branches traversable.
251 Pjp_t APjphist[HISTNUMMAX]; // list of branch JPs traversed.
252 int Aoffhist[HISTNUMMAX]; // list of next JP offsets; see above.
253 int histnum = 0; // number of JPs now in list.
254
255
256 // ----------------------------------------------------------------------------
257 // M A C R O S
258 //
259 // These are intended to make the code a bit more readable and less redundant.
260
261
262 // "PUSH" AND "POP" Pjp AND offset ON HISTORY STACKS:
263 //
264 // Note: Ensure a corrupt Judy array does not overflow *hist[]. Meanwhile,
265 // underflowing *hist[] simply means theres no more room to backtrack =>
266 // "no previous/next Index".
267
268 #define HISTPUSH(Pjp,Offset) \
269 APjphist[histnum] = (Pjp); \
270 Aoffhist[histnum] = (Offset); \
271 \
272 if (++histnum >= HISTNUMMAX) \
273 { \
274 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT) \
275 JUDY1CODE(return(JERRI );) \
276 JUDYLCODE(return(PPJERR);) \
277 }
278
279 #define HISTPOP(Pjp,Offset) \
280 if ((histnum--) < 1) JU_RET_NOTFOUND; \
281 (Pjp) = APjphist[histnum]; \
282 (Offset) = Aoffhist[histnum]
283
284 // How to pack/unpack Aoffhist[] values for bitmap branches:
285
286 #ifdef JUDYPREV
287
288 #define HISTPUSHBOFF(Subexp,Offset,Digit) \
289 (((Subexp) * cJU_BITSPERSUBEXPB) | (Offset))
290
291 #define HISTPOPBOFF(Subexp,Offset,Digit) \
292 (Subexp) = (Offset) / cJU_BITSPERSUBEXPB; \
293 (Offset) %= cJU_BITSPERSUBEXPB
294 #else
295
296 #define HISTPUSHBOFF(Subexp,Offset,Digit) \
297 (((Digit) << cJU_BITSPERBYTE) \
298 | ((Subexp) * cJU_BITSPERSUBEXPB) | (Offset))
299
300 #define HISTPOPBOFF(Subexp,Offset,Digit) \
301 (Digit) = (Offset) >> cJU_BITSPERBYTE; \
302 (Subexp) = ((Offset) & JU_LEASTBYTESMASK(1)) / cJU_BITSPERSUBEXPB; \
303 (Offset) %= cJU_BITSPERSUBEXPB
304 #endif
305
306
307 // CHECK FOR NULL JP:
308
309 #define JPNULL(Type) (((Type) >= cJU_JPNULL1) && ((Type) <= cJU_JPNULLMAX))
310
311
312 // SEARCH A BITMAP:
313 //
314 // This is a weak analog of j__udySearchLeaf*() for bitmaps. Return the actual
315 // or next-left position, base 0, of Digit in the single uint32_t bitmap, also
316 // given a Bitposmask for Digit.
317 //
318 // Unlike j__udySearchLeaf*(), the offset is not returned bit-complemented if
319 // Digits bit is unset, because the caller can check the bitmap themselves to
320 // determine that. Also, if Digits bit is unset, the returned offset is to
321 // the next-left JP (including -1), not to the "ideal" position for the Index =
322 // next-right JP.
323 //
324 // Shortcut and skip calling j__udyCountBits*() if the bitmap is full, in which
325 // case (Digit % cJU_BITSPERSUBEXP*) itself is the base-0 offset.
326 //
327 // TBD for Judy*Next(): Should this return next-right instead of next-left?
328 // That is, +1 from current value? Maybe not, if Digits bit IS set, +1 would
329 // be wrong.
330
331 #define SEARCHBITMAPB(Bitmap,Digit,Bitposmask) \
332 (((Bitmap) == cJU_FULLBITMAPB) ? (Digit % cJU_BITSPERSUBEXPB) : \
333 j__udyCountBitsB((Bitmap) & JU_MASKLOWERINC(Bitposmask)) - 1)
334
335 #define SEARCHBITMAPL(Bitmap,Digit,Bitposmask) \
336 (((Bitmap) == cJU_FULLBITMAPL) ? (Digit % cJU_BITSPERSUBEXPL) : \
337 j__udyCountBitsL((Bitmap) & JU_MASKLOWERINC(Bitposmask)) - 1)
338
339 #ifdef JUDYPREV
340 // Equivalent to search for the highest offset in Bitmap:
341
342 #define SEARCHBITMAPMAXB(Bitmap) \
343 (((Bitmap) == cJU_FULLBITMAPB) ? cJU_BITSPERSUBEXPB - 1 : \
344 j__udyCountBitsB(Bitmap) - 1)
345
346 #define SEARCHBITMAPMAXL(Bitmap) \
347 (((Bitmap) == cJU_FULLBITMAPL) ? cJU_BITSPERSUBEXPL - 1 : \
348 j__udyCountBitsL(Bitmap) - 1)
349 #endif
350
351
352 // CHECK DECODE BYTES:
353 //
354 // Check Decode bytes in a JP against the equivalent portion of *PIndex. If
355 // *PIndex is lower (for Judy*Prev()) or higher (for Judy*Next()), this JP is a
356 // dead end (the same as if it had been absent in a linear or bitmap branch or
357 // null in an uncompressed branch), enter SM2Backtrack; otherwise enter
358 // SM3Findlimit to find the highest/lowest Index under this JP, as if the code
359 // had already backtracked to this JP.
360
361 #ifdef JUDYPREV
362 #define CDcmp__ <
363 #else
364 #define CDcmp__ >
365 #endif
366
367 #define CHECKDCD(cState) \
368 if (JU_DCDNOTMATCHINDEX(*PIndex, Pjp, cState)) \
369 { \
370 if ((*PIndex & cJU_DCDMASK(cState)) \
371 CDcmp__(JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(cState))) \
372 { \
373 goto SM2Backtrack; \
374 } \
375 goto SM3Findlimit; \
376 }
377
378
379 // PREPARE TO HANDLE A LEAFW OR JRP BRANCH IN SM1:
380 //
381 // Extract a state-dependent digit from Index in a "constant" way, then jump to
382 // common code for multiple cases.
383
384 #define SM1PREPB(cState,Next) \
385 state = (cState); \
386 digit = JU_DIGITATSTATE(*PIndex, cState); \
387 goto Next
388
389
390 // PREPARE TO HANDLE A LEAFW OR JRP BRANCH IN SM3:
391 //
392 // Optionally save Dcd bytes into *PIndex, then save state and jump to common
393 // code for multiple cases.
394
395 #define SM3PREPB_DCD(cState,Next) \
396 JU_SETDCD(*PIndex, Pjp, cState); \
397 SM3PREPB(cState,Next)
398
399 #define SM3PREPB(cState,Next) state = (cState); goto Next
400
401
402 // ----------------------------------------------------------------------------
403 // CHECK FOR SHORTCUTS:
404 //
405 // Error out if PIndex is null. Execute JU_RET_NOTFOUND if the Judy array is
406 // empty or *PIndex is already the minimum/maximum Index possible.
407 //
408 // Note: As documented, in case of failure *PIndex may be modified.
409
410 if (PIndex == (PWord_t) NULL)
411 {
412 JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
413 JUDY1CODE(return(JERRI );)
414 JUDYLCODE(return(PPJERR);)
415 }
416
417 #ifdef JUDYPREV
418 if ((PArray == (Pvoid_t) NULL) || ((*PIndex)-- == 0))
419 #else
420 if ((PArray == (Pvoid_t) NULL) || ((*PIndex)++ == cJU_ALLONES))
421 #endif
422 JU_RET_NOTFOUND;
423
424
425 // HANDLE JRP:
426 //
427 // Before even entering SM1Get, check the JRP type. For JRP branches, traverse
428 // the JPM; handle LEAFW leaves directly; but look for the most common cases
429 // first.
430
431 // ROOT-STATE LEAF that starts with a Pop0 word; just look within the leaf:
432 //
433 // If *PIndex is in the leaf, return it; otherwise return the Index, if any,
434 // below where it would belong.
435
436 if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
437 {
438 Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
439 pop1 = Pjlw[0] + 1;
440
441 if ((offset = j__udySearchLeafW(Pjlw + 1, pop1, *PIndex))
442 >= 0) // Index is present.
443 {
444 assert(offset < pop1); // in expected range.
445 JU_RET_FOUND_LEAFW(Pjlw, pop1, offset); // *PIndex is set.
446 }
447
448 #ifdef JUDYPREV
449 if ((offset = ~offset) == 0) // no next-left Index.
450 #else
451 if ((offset = ~offset) >= pop1) // no next-right Index.
452 #endif
453 JU_RET_NOTFOUND;
454
455 assert(offset <= pop1); // valid result.
456
457 #ifdef JUDYPREV
458 *PIndex = Pjlw[offset--]; // next-left Index, base 1.
459 #else
460 *PIndex = Pjlw[offset + 1]; // next-right Index, base 1.
461 #endif
462 JU_RET_FOUND_LEAFW(Pjlw, pop1, offset); // base 0.
463
464 }
465 else // JRP BRANCH
466 {
467 Pjpm_t Pjpm = P_JPM(PArray);
468 Pjp = &(Pjpm->jpm_JP);
469
470 // goto SM1Get;
471 }
472
473 // ============================================================================
474 // STATE MACHINE 1 -- GET INDEX:
475 //
476 // Search for *PIndex (already decremented/incremented so as to be inclusive).
477 // If found, return it. Otherwise in theory hand off to SM2Backtrack or
478 // SM3Findlimit, but in practice "shortcut" by first sideways searching the
479 // current branch or leaf upon hitting a dead end. During sideways search,
480 // modify *PIndex to a new path taken.
481 //
482 // ENTRY: Pjp points to next JP to interpret, whose Decode bytes have not yet
483 // been checked. This JP is not yet listed in history.
484 //
485 // Note: Check Decode bytes at the start of each loop, not after looking up a
486 // new JP, so its easy to do constant shifts/masks, although this requires
487 // cautious handling of Pjp, offset, and *hist[] for correct entry to
488 // SM2Backtrack.
489 //
490 // EXIT: Return, or branch to SM2Backtrack or SM3Findlimit with correct
491 // interface, as described elsewhere.
492 //
493 // WARNING: For run-time efficiency the following cases replicate code with
494 // varying constants, rather than using common code with variable values!
495
496 SM1Get: // return here for next branch/leaf.
497
498 switch (JU_JPTYPE(Pjp))
499 {
500
501
502 // ----------------------------------------------------------------------------
503 // LINEAR BRANCH:
504 //
505 // Check Decode bytes, if any, in the current JP, then search for a JP for the
506 // next digit in *PIndex.
507
508 case cJU_JPBRANCH_L2: CHECKDCD(2); SM1PREPB(2, SM1BranchL);
509 case cJU_JPBRANCH_L3: CHECKDCD(3); SM1PREPB(3, SM1BranchL);
510 #ifdef JU_64BIT
511 case cJU_JPBRANCH_L4: CHECKDCD(4); SM1PREPB(4, SM1BranchL);
512 case cJU_JPBRANCH_L5: CHECKDCD(5); SM1PREPB(5, SM1BranchL);
513 case cJU_JPBRANCH_L6: CHECKDCD(6); SM1PREPB(6, SM1BranchL);
514 case cJU_JPBRANCH_L7: CHECKDCD(7); SM1PREPB(7, SM1BranchL);
515 #endif
516 case cJU_JPBRANCH_L: SM1PREPB(cJU_ROOTSTATE, SM1BranchL);
517
518 // Common code (state-independent) for all cases of linear branches:
519
520 SM1BranchL:
521 Pjbl = P_JBL(Pjp->jp_Addr);
522
523 // Found JP matching current digit in *PIndex; record parent JP and the next
524 // JPs offset, and iterate to the next JP:
525
526 if ((offset = j__udySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse),
527 Pjbl->jbl_NumJPs, digit)) >= 0)
528 {
529 HISTPUSH(Pjp, offset);
530 Pjp = (Pjbl->jbl_jp) + offset;
531 goto SM1Get;
532 }
533
534 // Dead end, no JP in BranchL for next digit in *PIndex:
535 //
536 // Get the ideal location of digits JP, and if theres no next-left/right JP
537 // in the BranchL, shortcut and start backtracking one level up; ignore the
538 // current Pjp because it points to a BranchL with no next-left/right JP.
539
540 #ifdef JUDYPREV
541 if ((offset = (~offset) - 1) < 0) // no next-left JP in BranchL.
542 #else
543 if ((offset = (~offset)) >= Pjbl->jbl_NumJPs) // no next-right.
544 #endif
545 goto SM2Backtrack;
546
547 // Theres a next-left/right JP in the current BranchL; save its digit in
548 // *PIndex and shortcut to SM3Findlimit:
549
550 JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
551 Pjp = (Pjbl->jbl_jp) + offset;
552 goto SM3Findlimit;
553
554
555 // ----------------------------------------------------------------------------
556 // BITMAP BRANCH:
557 //
558 // Check Decode bytes, if any, in the current JP, then look for a JP for the
559 // next digit in *PIndex.
560
561 case cJU_JPBRANCH_B2: CHECKDCD(2); SM1PREPB(2, SM1BranchB);
562 case cJU_JPBRANCH_B3: CHECKDCD(3); SM1PREPB(3, SM1BranchB);
563 #ifdef JU_64BIT
564 case cJU_JPBRANCH_B4: CHECKDCD(4); SM1PREPB(4, SM1BranchB);
565 case cJU_JPBRANCH_B5: CHECKDCD(5); SM1PREPB(5, SM1BranchB);
566 case cJU_JPBRANCH_B6: CHECKDCD(6); SM1PREPB(6, SM1BranchB);
567 case cJU_JPBRANCH_B7: CHECKDCD(7); SM1PREPB(7, SM1BranchB);
568 #endif
569 case cJU_JPBRANCH_B: SM1PREPB(cJU_ROOTSTATE, SM1BranchB);
570
571 // Common code (state-independent) for all cases of bitmap branches:
572
573 SM1BranchB:
574 Pjbb = P_JBB(Pjp->jp_Addr);
575
576 // Locate the digits JP in the subexpanse list, if present, otherwise the
577 // offset of the next-left JP, if any:
578
579 subexp = digit / cJU_BITSPERSUBEXPB;
580 assert(subexp < cJU_NUMSUBEXPB); // falls in expected range.
581 bitposmask = JU_BITPOSMASKB(digit);
582 offset = SEARCHBITMAPB(JU_JBB_BITMAP(Pjbb, subexp), digit,
583 bitposmask);
584 // right range:
585 assert((offset >= -1) && (offset < (int) cJU_BITSPERSUBEXPB));
586
587 // Found JP matching current digit in *PIndex:
588 //
589 // Record the parent JP and the next JPs offset; and iterate to the next JP.
590
591 // if (JU_BITMAPTESTB(Pjbb, digit)) // slower.
592 if (JU_JBB_BITMAP(Pjbb, subexp) & bitposmask) // faster.
593 {
594 // not negative since at least one bit is set:
595 assert(offset >= 0);
596
597 HISTPUSH(Pjp, HISTPUSHBOFF(subexp, offset, digit));
598
599 if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
600 {
601 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
602 JUDY1CODE(return(JERRI );)
603 JUDYLCODE(return(PPJERR);)
604 }
605
606 Pjp += offset;
607 goto SM1Get; // iterate to next JP.
608 }
609
610 // Dead end, no JP in BranchB for next digit in *PIndex:
611 //
612 // If theres a next-left/right JP in the current BranchB, shortcut to
613 // SM3Findlimit. Note: offset is already set to the correct value for the
614 // next-left/right JP.
615
616 #ifdef JUDYPREV
617 if (offset >= 0) // next-left JP is in this subexpanse.
618 goto SM1BranchBFindlimit;
619
620 while (--subexp >= 0) // search next-left subexpanses.
621 #else
622 if (JU_JBB_BITMAP(Pjbb, subexp) & JU_MASKHIGHEREXC(bitposmask))
623 {
624 ++offset; // next-left => next-right.
625 goto SM1BranchBFindlimit;
626 }
627
628 while (++subexp < cJU_NUMSUBEXPB) // search next-right subexps.
629 #endif
630 {
631 if (! JU_JBB_PJP(Pjbb, subexp)) continue; // empty subexpanse.
632
633 #ifdef JUDYPREV
634 offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
635 // expected range:
636 assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
637 #else
638 offset = 0;
639 #endif
640
641 // Save the next-left/right JPs digit in *PIndex:
642
643 SM1BranchBFindlimit:
644 JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp),
645 offset);
646 JU_SETDIGIT(*PIndex, digit, state);
647
648 if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
649 {
650 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
651 JUDY1CODE(return(JERRI );)
652 JUDYLCODE(return(PPJERR);)
653 }
654
655 Pjp += offset;
656 goto SM3Findlimit;
657 }
658
659 // Theres no next-left/right JP in the BranchB:
660 //
661 // Shortcut and start backtracking one level up; ignore the current Pjp because
662 // it points to a BranchB with no next-left/right JP.
663
664 goto SM2Backtrack;
665
666
667 // ----------------------------------------------------------------------------
668 // UNCOMPRESSED BRANCH:
669 //
670 // Check Decode bytes, if any, in the current JP, then look for a JP for the
671 // next digit in *PIndex.
672
673 case cJU_JPBRANCH_U2: CHECKDCD(2); SM1PREPB(2, SM1BranchU);
674 case cJU_JPBRANCH_U3: CHECKDCD(3); SM1PREPB(3, SM1BranchU);
675 #ifdef JU_64BIT
676 case cJU_JPBRANCH_U4: CHECKDCD(4); SM1PREPB(4, SM1BranchU);
677 case cJU_JPBRANCH_U5: CHECKDCD(5); SM1PREPB(5, SM1BranchU);
678 case cJU_JPBRANCH_U6: CHECKDCD(6); SM1PREPB(6, SM1BranchU);
679 case cJU_JPBRANCH_U7: CHECKDCD(7); SM1PREPB(7, SM1BranchU);
680 #endif
681 case cJU_JPBRANCH_U: SM1PREPB(cJU_ROOTSTATE, SM1BranchU);
682
683 // Common code (state-independent) for all cases of uncompressed branches:
684
685 SM1BranchU:
686 Pjbu = P_JBU(Pjp->jp_Addr);
687 Pjp2 = (Pjbu->jbu_jp) + digit;
688
689 // Found JP matching current digit in *PIndex:
690 //
691 // Record the parent JP and the next JPs digit, and iterate to the next JP.
692 //
693 // TBD: Instead of this, just goto SM1Get, and add cJU_JPNULL* cases to the
694 // SM1Get state machine? Then backtrack? However, it means you cant detect
695 // an inappropriate cJU_JPNULL*, when it occurs in other than a BranchU, and
696 // return JU_RET_CORRUPT.
697
698 if (! JPNULL(JU_JPTYPE(Pjp2))) // digit has a JP.
699 {
700 HISTPUSH(Pjp, digit);
701 Pjp = Pjp2;
702 goto SM1Get;
703 }
704
705 // Dead end, no JP in BranchU for next digit in *PIndex:
706 //
707 // Search for a next-left/right JP in the current BranchU, and if one is found,
708 // save its digit in *PIndex and shortcut to SM3Findlimit:
709
710 #ifdef JUDYPREV
711 while (digit >= 1)
712 {
713 Pjp = (Pjbu->jbu_jp) + (--digit);
714 #else
715 while (digit < cJU_BRANCHUNUMJPS - 1)
716 {
717 Pjp = (Pjbu->jbu_jp) + (++digit);
718 #endif
719 if (JPNULL(JU_JPTYPE(Pjp))) continue;
720
721 JU_SETDIGIT(*PIndex, digit, state);
722 goto SM3Findlimit;
723 }
724
725 // Theres no next-left/right JP in the BranchU:
726 //
727 // Shortcut and start backtracking one level up; ignore the current Pjp because
728 // it points to a BranchU with no next-left/right JP.
729
730 goto SM2Backtrack;
731
732
733 // ----------------------------------------------------------------------------
734 // LINEAR LEAF:
735 //
736 // Check Decode bytes, if any, in the current JP, then search the leaf for
737 // *PIndex.
738
739 #define SM1LEAFL(Func) \
740 Pjll = P_JLL(Pjp->jp_Addr); \
741 pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
742 offset = Func(Pjll, pop1, *PIndex); \
743 goto SM1LeafLImm
744
745 #if (defined(JUDYL) || (! defined(JU_64BIT)))
746 case cJU_JPLEAF1: CHECKDCD(1); SM1LEAFL(j__udySearchLeaf1);
747 #endif
748 case cJU_JPLEAF2: CHECKDCD(2); SM1LEAFL(j__udySearchLeaf2);
749 case cJU_JPLEAF3: CHECKDCD(3); SM1LEAFL(j__udySearchLeaf3);
750
751 #ifdef JU_64BIT
752 case cJU_JPLEAF4: CHECKDCD(4); SM1LEAFL(j__udySearchLeaf4);
753 case cJU_JPLEAF5: CHECKDCD(5); SM1LEAFL(j__udySearchLeaf5);
754 case cJU_JPLEAF6: CHECKDCD(6); SM1LEAFL(j__udySearchLeaf6);
755 case cJU_JPLEAF7: CHECKDCD(7); SM1LEAFL(j__udySearchLeaf7);
756 #endif
757
758 // Common code (state-independent) for all cases of linear leaves and
759 // immediates:
760
761 SM1LeafLImm:
762 if (offset >= 0) // *PIndex is in LeafL / Immed.
763 #ifdef JUDY1
764 JU_RET_FOUND;
765 #else
766 { // JudyL is trickier...
767 switch (JU_JPTYPE(Pjp))
768 {
769 #if (defined(JUDYL) || (! defined(JU_64BIT)))
770 case cJU_JPLEAF1: JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
771 #endif
772 case cJU_JPLEAF2: JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
773 case cJU_JPLEAF3: JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
774 #ifdef JU_64BIT
775 case cJU_JPLEAF4: JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
776 case cJU_JPLEAF5: JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
777 case cJU_JPLEAF6: JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
778 case cJU_JPLEAF7: JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
779 #endif
780
781 case cJU_JPIMMED_1_01:
782 case cJU_JPIMMED_2_01:
783 case cJU_JPIMMED_3_01:
784 #ifdef JU_64BIT
785 case cJU_JPIMMED_4_01:
786 case cJU_JPIMMED_5_01:
787 case cJU_JPIMMED_6_01:
788 case cJU_JPIMMED_7_01:
789 #endif
790 JU_RET_FOUND_IMM_01(Pjp);
791
792 case cJU_JPIMMED_1_02:
793 case cJU_JPIMMED_1_03:
794 #ifdef JU_64BIT
795 case cJU_JPIMMED_1_04:
796 case cJU_JPIMMED_1_05:
797 case cJU_JPIMMED_1_06:
798 case cJU_JPIMMED_1_07:
799 case cJU_JPIMMED_2_02:
800 case cJU_JPIMMED_2_03:
801 case cJU_JPIMMED_3_02:
802 #endif
803 JU_RET_FOUND_IMM(Pjp, offset);
804 }
805
806 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // impossible?
807 JUDY1CODE(return(JERRI );)
808 JUDYLCODE(return(PPJERR);)
809
810 } // found *PIndex
811
812 #endif // JUDYL
813
814 // Dead end, no Index in LeafL / Immed for remaining digit(s) in *PIndex:
815 //
816 // Get the ideal location of Index, and if theres no next-left/right Index in
817 // the LeafL / Immed, shortcut and start backtracking one level up; ignore the
818 // current Pjp because it points to a LeafL / Immed with no next-left/right
819 // Index.
820
821 #ifdef JUDYPREV
822 if ((offset = (~offset) - 1) < 0) // no next-left Index.
823 #else
824 if ((offset = (~offset)) >= pop1) // no next-right Index.
825 #endif
826 goto SM2Backtrack;
827
828 // Theres a next-left/right Index in the current LeafL / Immed; shortcut by
829 // copying its digit(s) to *PIndex and returning it.
830 //
831 // Unfortunately this is pretty hairy, especially avoiding endian issues.
832 //
833 // The cJU_JPLEAF* cases are very similar to same-index-size cJU_JPIMMED* cases
834 // for *_02 and above, but must return differently, at least for JudyL, so
835 // spell them out separately here at the cost of a little redundant code for
836 // Judy1.
837
838 switch (JU_JPTYPE(Pjp))
839 {
840 #if (defined(JUDYL) || (! defined(JU_64BIT)))
841 case cJU_JPLEAF1:
842
843 JU_SETDIGIT1(*PIndex, ((uint8_t *) Pjll)[offset]);
844 JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
845 #endif
846
847 case cJU_JPLEAF2:
848
849 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
850 | ((uint16_t *) Pjll)[offset];
851 JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
852
853 case cJU_JPLEAF3:
854 {
855 Word_t lsb;
856 JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
857 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
858 JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
859 }
860
861 #ifdef JU_64BIT
862 case cJU_JPLEAF4:
863
864 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
865 | ((uint32_t *) Pjll)[offset];
866 JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
867
868 case cJU_JPLEAF5:
869 {
870 Word_t lsb;
871 JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (5 * offset));
872 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
873 JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
874 }
875
876 case cJU_JPLEAF6:
877 {
878 Word_t lsb;
879 JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (6 * offset));
880 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
881 JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
882 }
883
884 case cJU_JPLEAF7:
885 {
886 Word_t lsb;
887 JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (7 * offset));
888 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
889 JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
890 }
891
892 #endif // JU_64BIT
893
894 #define SET_01(cState) JU_SETDIGITS(*PIndex, JU_JPDCDPOP0(Pjp), cState)
895
896 case cJU_JPIMMED_1_01: SET_01(1); goto SM1Imm_01;
897 case cJU_JPIMMED_2_01: SET_01(2); goto SM1Imm_01;
898 case cJU_JPIMMED_3_01: SET_01(3); goto SM1Imm_01;
899 #ifdef JU_64BIT
900 case cJU_JPIMMED_4_01: SET_01(4); goto SM1Imm_01;
901 case cJU_JPIMMED_5_01: SET_01(5); goto SM1Imm_01;
902 case cJU_JPIMMED_6_01: SET_01(6); goto SM1Imm_01;
903 case cJU_JPIMMED_7_01: SET_01(7); goto SM1Imm_01;
904 #endif
905 SM1Imm_01: JU_RET_FOUND_IMM_01(Pjp);
906
907 // Shorthand for where to find start of Index bytes array:
908
909 #ifdef JUDY1
910 #define PJI (Pjp->jp_1Index)
911 #else
912 #define PJI (Pjp->jp_LIndex)
913 #endif
914
915 case cJU_JPIMMED_1_02:
916 case cJU_JPIMMED_1_03:
917 #if (defined(JUDY1) || defined(JU_64BIT))
918 case cJU_JPIMMED_1_04:
919 case cJU_JPIMMED_1_05:
920 case cJU_JPIMMED_1_06:
921 case cJU_JPIMMED_1_07:
922 #endif
923 #if (defined(JUDY1) && defined(JU_64BIT))
924 case cJ1_JPIMMED_1_08:
925 case cJ1_JPIMMED_1_09:
926 case cJ1_JPIMMED_1_10:
927 case cJ1_JPIMMED_1_11:
928 case cJ1_JPIMMED_1_12:
929 case cJ1_JPIMMED_1_13:
930 case cJ1_JPIMMED_1_14:
931 case cJ1_JPIMMED_1_15:
932 #endif
933 JU_SETDIGIT1(*PIndex, ((uint8_t *) PJI)[offset]);
934 JU_RET_FOUND_IMM(Pjp, offset);
935
936 #if (defined(JUDY1) || defined(JU_64BIT))
937 case cJU_JPIMMED_2_02:
938 case cJU_JPIMMED_2_03:
939 #endif
940 #if (defined(JUDY1) && defined(JU_64BIT))
941 case cJ1_JPIMMED_2_04:
942 case cJ1_JPIMMED_2_05:
943 case cJ1_JPIMMED_2_06:
944 case cJ1_JPIMMED_2_07:
945 #endif
946 #if (defined(JUDY1) || defined(JU_64BIT))
947 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
948 | ((uint16_t *) PJI)[offset];
949 JU_RET_FOUND_IMM(Pjp, offset);
950 #endif
951
952 #if (defined(JUDY1) || defined(JU_64BIT))
953 case cJU_JPIMMED_3_02:
954 #endif
955 #if (defined(JUDY1) && defined(JU_64BIT))
956 case cJ1_JPIMMED_3_03:
957 case cJ1_JPIMMED_3_04:
958 case cJ1_JPIMMED_3_05:
959 #endif
960 #if (defined(JUDY1) || defined(JU_64BIT))
961 {
962 Word_t lsb;
963 JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (3 * offset));
964 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
965 JU_RET_FOUND_IMM(Pjp, offset);
966 }
967 #endif
968
969 #if (defined(JUDY1) && defined(JU_64BIT))
970 case cJ1_JPIMMED_4_02:
971 case cJ1_JPIMMED_4_03:
972
973 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
974 | ((uint32_t *) PJI)[offset];
975 JU_RET_FOUND_IMM(Pjp, offset);
976
977 case cJ1_JPIMMED_5_02:
978 case cJ1_JPIMMED_5_03:
979 {
980 Word_t lsb;
981 JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (5 * offset));
982 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
983 JU_RET_FOUND_IMM(Pjp, offset);
984 }
985
986 case cJ1_JPIMMED_6_02:
987 {
988 Word_t lsb;
989 JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (6 * offset));
990 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
991 JU_RET_FOUND_IMM(Pjp, offset);
992 }
993
994 case cJ1_JPIMMED_7_02:
995 {
996 Word_t lsb;
997 JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (7 * offset));
998 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
999 JU_RET_FOUND_IMM(Pjp, offset);
1000 }
1001
1002 #endif // (JUDY1 && JU_64BIT)
1003
1004 } // switch for not-found *PIndex
1005
1006 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // impossible?
1007 JUDY1CODE(return(JERRI );)
1008 JUDYLCODE(return(PPJERR);)
1009
1010
1011 // ----------------------------------------------------------------------------
1012 // BITMAP LEAF:
1013 //
1014 // Check Decode bytes, if any, in the current JP, then look in the leaf for
1015 // *PIndex.
1016
1017 case cJU_JPLEAF_B1:
1018 {
1019 Pjlb_t Pjlb;
1020 CHECKDCD(1);
1021
1022 Pjlb = P_JLB(Pjp->jp_Addr);
1023 digit = JU_DIGITATSTATE(*PIndex, 1);
1024 subexp = JU_SUBEXPL(digit);
1025 bitposmask = JU_BITPOSMASKL(digit);
1026 assert(subexp < cJU_NUMSUBEXPL); // falls in expected range.
1027
1028 // *PIndex exists in LeafB1:
1029
1030 // if (JU_BITMAPTESTL(Pjlb, digit)) // slower.
1031 if (JU_JLB_BITMAP(Pjlb, subexp) & bitposmask) // faster.
1032 {
1033 #ifdef JUDYL // needs offset at this point:
1034 offset = SEARCHBITMAPL(JU_JLB_BITMAP(Pjlb, subexp), digit, bitposmask);
1035 #endif
1036 JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
1037 // == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + (offset)));
1038 }
1039
1040 // Dead end, no Index in LeafB1 for remaining digit in *PIndex:
1041 //
1042 // If theres a next-left/right Index in the current LeafB1, which for
1043 // Judy*Next() is true if any bits are set for higher Indexes, shortcut by
1044 // returning it. Note: For Judy*Prev(), offset is set here to the correct
1045 // value for the next-left JP.
1046
1047 offset = SEARCHBITMAPL(JU_JLB_BITMAP(Pjlb, subexp), digit,
1048 bitposmask);
1049 // right range:
1050 assert((offset >= -1) && (offset < (int) cJU_BITSPERSUBEXPL));
1051
1052 #ifdef JUDYPREV
1053 if (offset >= 0) // next-left JP is in this subexpanse.
1054 goto SM1LeafB1Findlimit;
1055
1056 while (--subexp >= 0) // search next-left subexpanses.
1057 #else
1058 if (JU_JLB_BITMAP(Pjlb, subexp) & JU_MASKHIGHEREXC(bitposmask))
1059 {
1060 ++offset; // next-left => next-right.
1061 goto SM1LeafB1Findlimit;
1062 }
1063
1064 while (++subexp < cJU_NUMSUBEXPL) // search next-right subexps.
1065 #endif
1066 {
1067 if (! JU_JLB_BITMAP(Pjlb, subexp)) continue; // empty subexp.
1068
1069 #ifdef JUDYPREV
1070 offset = SEARCHBITMAPMAXL(JU_JLB_BITMAP(Pjlb, subexp));
1071 // expected range:
1072 assert((offset >= 0) && (offset < (int) cJU_BITSPERSUBEXPL));
1073 #else
1074 offset = 0;
1075 #endif
1076
1077 // Save the next-left/right Indexess digit in *PIndex:
1078
1079 SM1LeafB1Findlimit:
1080 JU_BITMAPDIGITL(digit, subexp, JU_JLB_BITMAP(Pjlb, subexp), offset);
1081 JU_SETDIGIT1(*PIndex, digit);
1082 JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
1083 // == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + (offset)));
1084 }
1085
1086 // Theres no next-left/right Index in the LeafB1:
1087 //
1088 // Shortcut and start backtracking one level up; ignore the current Pjp because
1089 // it points to a LeafB1 with no next-left/right Index.
1090
1091 goto SM2Backtrack;
1092
1093 } // case cJU_JPLEAF_B1
1094
1095 #ifdef JUDY1
1096 // ----------------------------------------------------------------------------
1097 // FULL POPULATION:
1098 //
1099 // If the Decode bytes match, *PIndex is found (without modification).
1100
1101 case cJ1_JPFULLPOPU1:
1102
1103 CHECKDCD(1);
1104 JU_RET_FOUND_FULLPOPU1;
1105 #endif
1106
1107
1108 // ----------------------------------------------------------------------------
1109 // IMMEDIATE:
1110
1111 #ifdef JUDYPREV
1112 #define SM1IMM_SETPOP1(cPop1)
1113 #else
1114 #define SM1IMM_SETPOP1(cPop1) pop1 = (cPop1)
1115 #endif
1116
1117 #define SM1IMM(Func,cPop1) \
1118 SM1IMM_SETPOP1(cPop1); \
1119 offset = Func((Pjll_t) (PJI), cPop1, *PIndex); \
1120 goto SM1LeafLImm
1121
1122 // Special case for Pop1 = 1 Immediate JPs:
1123 //
1124 // If *PIndex is in the immediate, offset is 0, otherwise the binary NOT of the
1125 // offset where it belongs, 0 or 1, same as from the search functions.
1126
1127 #ifdef JUDYPREV
1128 #define SM1IMM_01_SETPOP1
1129 #else
1130 #define SM1IMM_01_SETPOP1 pop1 = 1
1131 #endif
1132
1133 #define SM1IMM_01 \
1134 SM1IMM_01_SETPOP1; \
1135 offset = ((JU_JPDCDPOP0(Pjp) < JU_TRIMTODCDSIZE(*PIndex)) ? ~1 : \
1136 (JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(*PIndex)) ? 0 : \
1137 ~0); \
1138 goto SM1LeafLImm
1139
1140 case cJU_JPIMMED_1_01:
1141 case cJU_JPIMMED_2_01:
1142 case cJU_JPIMMED_3_01:
1143 #ifdef JU_64BIT
1144 case cJU_JPIMMED_4_01:
1145 case cJU_JPIMMED_5_01:
1146 case cJU_JPIMMED_6_01:
1147 case cJU_JPIMMED_7_01:
1148 #endif
1149 SM1IMM_01;
1150
1151 // TBD: Doug says it would be OK to have fewer calls and calculate arg 2, here
1152 // and in Judy*Count() also.
1153
1154 case cJU_JPIMMED_1_02: SM1IMM(j__udySearchLeaf1, 2);
1155 case cJU_JPIMMED_1_03: SM1IMM(j__udySearchLeaf1, 3);
1156 #if (defined(JUDY1) || defined(JU_64BIT))
1157 case cJU_JPIMMED_1_04: SM1IMM(j__udySearchLeaf1, 4);
1158 case cJU_JPIMMED_1_05: SM1IMM(j__udySearchLeaf1, 5);
1159 case cJU_JPIMMED_1_06: SM1IMM(j__udySearchLeaf1, 6);
1160 case cJU_JPIMMED_1_07: SM1IMM(j__udySearchLeaf1, 7);
1161 #endif
1162 #if (defined(JUDY1) && defined(JU_64BIT))
1163 case cJ1_JPIMMED_1_08: SM1IMM(j__udySearchLeaf1, 8);
1164 case cJ1_JPIMMED_1_09: SM1IMM(j__udySearchLeaf1, 9);
1165 case cJ1_JPIMMED_1_10: SM1IMM(j__udySearchLeaf1, 10);
1166 case cJ1_JPIMMED_1_11: SM1IMM(j__udySearchLeaf1, 11);
1167 case cJ1_JPIMMED_1_12: SM1IMM(j__udySearchLeaf1, 12);
1168 case cJ1_JPIMMED_1_13: SM1IMM(j__udySearchLeaf1, 13);
1169 case cJ1_JPIMMED_1_14: SM1IMM(j__udySearchLeaf1, 14);
1170 case cJ1_JPIMMED_1_15: SM1IMM(j__udySearchLeaf1, 15);
1171 #endif
1172
1173 #if (defined(JUDY1) || defined(JU_64BIT))
1174 case cJU_JPIMMED_2_02: SM1IMM(j__udySearchLeaf2, 2);
1175 case cJU_JPIMMED_2_03: SM1IMM(j__udySearchLeaf2, 3);
1176 #endif
1177 #if (defined(JUDY1) && defined(JU_64BIT))
1178 case cJ1_JPIMMED_2_04: SM1IMM(j__udySearchLeaf2, 4);
1179 case cJ1_JPIMMED_2_05: SM1IMM(j__udySearchLeaf2, 5);
1180 case cJ1_JPIMMED_2_06: SM1IMM(j__udySearchLeaf2, 6);
1181 case cJ1_JPIMMED_2_07: SM1IMM(j__udySearchLeaf2, 7);
1182 #endif
1183
1184 #if (defined(JUDY1) || defined(JU_64BIT))
1185 case cJU_JPIMMED_3_02: SM1IMM(j__udySearchLeaf3, 2);
1186 #endif
1187 #if (defined(JUDY1) && defined(JU_64BIT))
1188 case cJ1_JPIMMED_3_03: SM1IMM(j__udySearchLeaf3, 3);
1189 case cJ1_JPIMMED_3_04: SM1IMM(j__udySearchLeaf3, 4);
1190 case cJ1_JPIMMED_3_05: SM1IMM(j__udySearchLeaf3, 5);
1191
1192 case cJ1_JPIMMED_4_02: SM1IMM(j__udySearchLeaf4, 2);
1193 case cJ1_JPIMMED_4_03: SM1IMM(j__udySearchLeaf4, 3);
1194
1195 case cJ1_JPIMMED_5_02: SM1IMM(j__udySearchLeaf5, 2);
1196 case cJ1_JPIMMED_5_03: SM1IMM(j__udySearchLeaf5, 3);
1197
1198 case cJ1_JPIMMED_6_02: SM1IMM(j__udySearchLeaf6, 2);
1199
1200 case cJ1_JPIMMED_7_02: SM1IMM(j__udySearchLeaf7, 2);
1201 #endif
1202
1203
1204 // ----------------------------------------------------------------------------
1205 // INVALID JP TYPE:
1206
1207 default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1208 JUDY1CODE(return(JERRI );)
1209 JUDYLCODE(return(PPJERR);)
1210
1211 } // SM1Get switch.
1212
1213 /*NOTREACHED*/
1214
1215
1216 // ============================================================================
1217 // STATE MACHINE 2 -- BACKTRACK BRANCH TO PREVIOUS JP:
1218 //
1219 // Look for the next-left/right JP in a branch, backing up the history list as
1220 // necessary. Upon finding a next-left/right JP, modify the corresponding
1221 // digit in *PIndex before passing control to SM3Findlimit.
1222 //
1223 // Note: As described earlier, only branch JPs are expected here; other types
1224 // fall into the default case.
1225 //
1226 // Note: If a found JP contains needed Dcd bytes, thats OK, theyre copied to
1227 // *PIndex in SM3Findlimit.
1228 //
1229 // TBD: This code has a lot in common with similar code in the shortcut cases
1230 // in SM1Get. Can combine this code somehow?
1231 //
1232 // ENTRY: List, possibly empty, of JPs and offsets in APjphist[] and
1233 // Aoffhist[]; see earlier comments.
1234 //
1235 // EXIT: Execute JU_RET_NOTFOUND if no previous/next JP; otherwise jump to
1236 // SM3Findlimit to resume a new but different downward search.
1237
1238 SM2Backtrack: // come or return here for first/next sideways search.
1239
1240 HISTPOP(Pjp, offset);
1241
1242 switch (JU_JPTYPE(Pjp))
1243 {
1244
1245
1246 // ----------------------------------------------------------------------------
1247 // LINEAR BRANCH:
1248
1249 case cJU_JPBRANCH_L2: state = 2; goto SM2BranchL;
1250 case cJU_JPBRANCH_L3: state = 3; goto SM2BranchL;
1251 #ifdef JU_64BIT
1252 case cJU_JPBRANCH_L4: state = 4; goto SM2BranchL;
1253 case cJU_JPBRANCH_L5: state = 5; goto SM2BranchL;
1254 case cJU_JPBRANCH_L6: state = 6; goto SM2BranchL;
1255 case cJU_JPBRANCH_L7: state = 7; goto SM2BranchL;
1256 #endif
1257 case cJU_JPBRANCH_L: state = cJU_ROOTSTATE; goto SM2BranchL;
1258
1259 SM2BranchL:
1260 #ifdef JUDYPREV
1261 if (--offset < 0) goto SM2Backtrack; // no next-left JP in BranchL.
1262 #endif
1263 Pjbl = P_JBL(Pjp->jp_Addr);
1264 #ifdef JUDYNEXT
1265 if (++offset >= (Pjbl->jbl_NumJPs)) goto SM2Backtrack;
1266 // no next-right JP in BranchL.
1267 #endif
1268
1269 // Theres a next-left/right JP in the current BranchL; save its digit in
1270 // *PIndex and continue with SM3Findlimit:
1271
1272 JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
1273 Pjp = (Pjbl->jbl_jp) + offset;
1274 goto SM3Findlimit;
1275
1276
1277 // ----------------------------------------------------------------------------
1278 // BITMAP BRANCH:
1279
1280 case cJU_JPBRANCH_B2: state = 2; goto SM2BranchB;
1281 case cJU_JPBRANCH_B3: state = 3; goto SM2BranchB;
1282 #ifdef JU_64BIT
1283 case cJU_JPBRANCH_B4: state = 4; goto SM2BranchB;
1284 case cJU_JPBRANCH_B5: state = 5; goto SM2BranchB;
1285 case cJU_JPBRANCH_B6: state = 6; goto SM2BranchB;
1286 case cJU_JPBRANCH_B7: state = 7; goto SM2BranchB;
1287 #endif
1288 case cJU_JPBRANCH_B: state = cJU_ROOTSTATE; goto SM2BranchB;
1289
1290 SM2BranchB:
1291 Pjbb = P_JBB(Pjp->jp_Addr);
1292 HISTPOPBOFF(subexp, offset, digit); // unpack values.
1293
1294 // If theres a next-left/right JP in the current BranchB, which for
1295 // Judy*Next() is true if any bits are set for higher Indexes, continue to
1296 // SM3Findlimit:
1297 //
1298 // Note: offset is set to the JP previously traversed; go one to the
1299 // left/right.
1300
1301 #ifdef JUDYPREV
1302 if (offset > 0) // next-left JP is in this subexpanse.
1303 {
1304 --offset;
1305 goto SM2BranchBFindlimit;
1306 }
1307
1308 while (--subexp >= 0) // search next-left subexpanses.
1309 #else
1310 if (JU_JBB_BITMAP(Pjbb, subexp)
1311 & JU_MASKHIGHEREXC(JU_BITPOSMASKB(digit)))
1312 {
1313 ++offset; // next-left => next-right.
1314 goto SM2BranchBFindlimit;
1315 }
1316
1317 while (++subexp < cJU_NUMSUBEXPB) // search next-right subexps.
1318 #endif
1319 {
1320 if (! JU_JBB_PJP(Pjbb, subexp)) continue; // empty subexpanse.
1321
1322 #ifdef JUDYPREV
1323 offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
1324 // expected range:
1325 assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
1326 #else
1327 offset = 0;
1328 #endif
1329
1330 // Save the next-left/right JPs digit in *PIndex:
1331
1332 SM2BranchBFindlimit:
1333 JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp),
1334 offset);
1335 JU_SETDIGIT(*PIndex, digit, state);
1336
1337 if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
1338 {
1339 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1340 JUDY1CODE(return(JERRI );)
1341 JUDYLCODE(return(PPJERR);)
1342 }
1343
1344 Pjp += offset;
1345 goto SM3Findlimit;
1346 }
1347
1348 // Theres no next-left/right JP in the BranchB:
1349
1350 goto SM2Backtrack;
1351
1352
1353 // ----------------------------------------------------------------------------
1354 // UNCOMPRESSED BRANCH:
1355
1356 case cJU_JPBRANCH_U2: state = 2; goto SM2BranchU;
1357 case cJU_JPBRANCH_U3: state = 3; goto SM2BranchU;
1358 #ifdef JU_64BIT
1359 case cJU_JPBRANCH_U4: state = 4; goto SM2BranchU;
1360 case cJU_JPBRANCH_U5: state = 5; goto SM2BranchU;
1361 case cJU_JPBRANCH_U6: state = 6; goto SM2BranchU;
1362 case cJU_JPBRANCH_U7: state = 7; goto SM2BranchU;
1363 #endif
1364 case cJU_JPBRANCH_U: state = cJU_ROOTSTATE; goto SM2BranchU;
1365
1366 SM2BranchU:
1367
1368 // Search for a next-left/right JP in the current BranchU, and if one is found,
1369 // save its digit in *PIndex and continue to SM3Findlimit:
1370
1371 Pjbu = P_JBU(Pjp->jp_Addr);
1372 digit = offset;
1373
1374 #ifdef JUDYPREV
1375 while (digit >= 1)
1376 {
1377 Pjp = (Pjbu->jbu_jp) + (--digit);
1378 #else
1379 while (digit < cJU_BRANCHUNUMJPS - 1)
1380 {
1381 Pjp = (Pjbu->jbu_jp) + (++digit);
1382 #endif
1383 if (JPNULL(JU_JPTYPE(Pjp))) continue;
1384
1385 JU_SETDIGIT(*PIndex, digit, state);
1386 goto SM3Findlimit;
1387 }
1388
1389 // Theres no next-left/right JP in the BranchU:
1390
1391 goto SM2Backtrack;
1392
1393
1394 // ----------------------------------------------------------------------------
1395 // INVALID JP TYPE:
1396
1397 default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1398 JUDY1CODE(return(JERRI );)
1399 JUDYLCODE(return(PPJERR);)
1400
1401 } // SM2Backtrack switch.
1402
1403 /*NOTREACHED*/
1404
1405
1406 // ============================================================================
1407 // STATE MACHINE 3 -- FIND LIMIT JP/INDEX:
1408 //
1409 // Look for the highest/lowest (right/left-most) JP in each branch and the
1410 // highest/lowest Index in a leaf or immediate, and return it. While
1411 // traversing, modify appropriate digit(s) in *PIndex to reflect the path
1412 // taken, including Dcd bytes in each JP (which could hold critical missing
1413 // digits for skipped branches).
1414 //
1415 // ENTRY: Pjp set to a JP under which to find max/min JPs (if a branch JP) or
1416 // a max/min Index and return (if a leaf or immediate JP).
1417 //
1418 // EXIT: Execute JU_RET_FOUND* upon reaching a leaf or immediate. Should be
1419 // impossible to fail, unless the Judy array is corrupt.
1420
1421 SM3Findlimit: // come or return here for first/next branch/leaf.
1422
1423 switch (JU_JPTYPE(Pjp))
1424 {
1425 // ----------------------------------------------------------------------------
1426 // LINEAR BRANCH:
1427 //
1428 // Simply use the highest/lowest (right/left-most) JP in the BranchL, but first
1429 // copy the Dcd bytes to *PIndex if there are any (only if state <
1430 // cJU_ROOTSTATE - 1).
1431
1432 case cJU_JPBRANCH_L2: SM3PREPB_DCD(2, SM3BranchL);
1433 #ifndef JU_64BIT
1434 case cJU_JPBRANCH_L3: SM3PREPB( 3, SM3BranchL);
1435 #else
1436 case cJU_JPBRANCH_L3: SM3PREPB_DCD(3, SM3BranchL);
1437 case cJU_JPBRANCH_L4: SM3PREPB_DCD(4, SM3BranchL);
1438 case cJU_JPBRANCH_L5: SM3PREPB_DCD(5, SM3BranchL);
1439 case cJU_JPBRANCH_L6: SM3PREPB_DCD(6, SM3BranchL);
1440 case cJU_JPBRANCH_L7: SM3PREPB( 7, SM3BranchL);
1441 #endif
1442 case cJU_JPBRANCH_L: SM3PREPB( cJU_ROOTSTATE, SM3BranchL);
1443
1444 SM3BranchL:
1445 Pjbl = P_JBL(Pjp->jp_Addr);
1446
1447 #ifdef JUDYPREV
1448 if ((offset = (Pjbl->jbl_NumJPs) - 1) < 0)
1449 #else
1450 offset = 0; if ((Pjbl->jbl_NumJPs) == 0)
1451 #endif
1452 {
1453 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1454 JUDY1CODE(return(JERRI );)
1455 JUDYLCODE(return(PPJERR);)
1456 }
1457
1458 JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
1459 Pjp = (Pjbl->jbl_jp) + offset;
1460 goto SM3Findlimit;
1461
1462
1463 // ----------------------------------------------------------------------------
1464 // BITMAP BRANCH:
1465 //
1466 // Look for the highest/lowest (right/left-most) non-null subexpanse, then use
1467 // the highest/lowest JP in that subexpanse, but first copy Dcd bytes, if there
1468 // are any (only if state < cJU_ROOTSTATE - 1), to *PIndex.
1469
1470 case cJU_JPBRANCH_B2: SM3PREPB_DCD(2, SM3BranchB);
1471 #ifndef JU_64BIT
1472 case cJU_JPBRANCH_B3: SM3PREPB( 3, SM3BranchB);
1473 #else
1474 case cJU_JPBRANCH_B3: SM3PREPB_DCD(3, SM3BranchB);
1475 case cJU_JPBRANCH_B4: SM3PREPB_DCD(4, SM3BranchB);
1476 case cJU_JPBRANCH_B5: SM3PREPB_DCD(5, SM3BranchB);
1477 case cJU_JPBRANCH_B6: SM3PREPB_DCD(6, SM3BranchB);
1478 case cJU_JPBRANCH_B7: SM3PREPB( 7, SM3BranchB);
1479 #endif
1480 case cJU_JPBRANCH_B: SM3PREPB( cJU_ROOTSTATE, SM3BranchB);
1481
1482 SM3BranchB:
1483 Pjbb = P_JBB(Pjp->jp_Addr);
1484 #ifdef JUDYPREV
1485 subexp = cJU_NUMSUBEXPB;
1486
1487 while (! (JU_JBB_BITMAP(Pjbb, --subexp))) // find non-empty subexp.
1488 {
1489 if (subexp <= 0) // wholly empty bitmap.
1490 {
1491 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1492 JUDY1CODE(return(JERRI );)
1493 JUDYLCODE(return(PPJERR);)
1494 }
1495 }
1496
1497 offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
1498 // expected range:
1499 assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
1500 #else
1501 subexp = -1;
1502
1503 while (! (JU_JBB_BITMAP(Pjbb, ++subexp))) // find non-empty subexp.
1504 {
1505 if (subexp >= cJU_NUMSUBEXPB - 1) // didnt find one.
1506 {
1507 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1508 JUDY1CODE(return(JERRI );)
1509 JUDYLCODE(return(PPJERR);)
1510 }
1511 }
1512
1513 offset = 0;
1514 #endif
1515
1516 JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp), offset);
1517 JU_SETDIGIT(*PIndex, digit, state);
1518
1519 if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
1520 {
1521 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1522 JUDY1CODE(return(JERRI );)
1523 JUDYLCODE(return(PPJERR);)
1524 }
1525
1526 Pjp += offset;
1527 goto SM3Findlimit;
1528
1529
1530 // ----------------------------------------------------------------------------
1531 // UNCOMPRESSED BRANCH:
1532 //
1533 // Look for the highest/lowest (right/left-most) non-null JP, and use it, but
1534 // first copy Dcd bytes to *PIndex if there are any (only if state <
1535 // cJU_ROOTSTATE - 1).
1536
1537 case cJU_JPBRANCH_U2: SM3PREPB_DCD(2, SM3BranchU);
1538 #ifndef JU_64BIT
1539 case cJU_JPBRANCH_U3: SM3PREPB( 3, SM3BranchU);
1540 #else
1541 case cJU_JPBRANCH_U3: SM3PREPB_DCD(3, SM3BranchU);
1542 case cJU_JPBRANCH_U4: SM3PREPB_DCD(4, SM3BranchU);
1543 case cJU_JPBRANCH_U5: SM3PREPB_DCD(5, SM3BranchU);
1544 case cJU_JPBRANCH_U6: SM3PREPB_DCD(6, SM3BranchU);
1545 case cJU_JPBRANCH_U7: SM3PREPB( 7, SM3BranchU);
1546 #endif
1547 case cJU_JPBRANCH_U: SM3PREPB( cJU_ROOTSTATE, SM3BranchU);
1548
1549 SM3BranchU:
1550 Pjbu = P_JBU(Pjp->jp_Addr);
1551 #ifdef JUDYPREV
1552 digit = cJU_BRANCHUNUMJPS;
1553
1554 while (digit >= 1)
1555 {
1556 Pjp = (Pjbu->jbu_jp) + (--digit);
1557 #else
1558
1559 for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit)
1560 {
1561 Pjp = (Pjbu->jbu_jp) + digit;
1562 #endif
1563 if (JPNULL(JU_JPTYPE(Pjp))) continue;
1564
1565 JU_SETDIGIT(*PIndex, digit, state);
1566 goto SM3Findlimit;
1567 }
1568
1569 // No non-null JPs in BranchU:
1570
1571 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1572 JUDY1CODE(return(JERRI );)
1573 JUDYLCODE(return(PPJERR);)
1574
1575
1576 // ----------------------------------------------------------------------------
1577 // LINEAR LEAF:
1578 //
1579 // Simply use the highest/lowest (right/left-most) Index in the LeafL, but the
1580 // details vary depending on leaf Index Size. First copy Dcd bytes, if there
1581 // are any (only if state < cJU_ROOTSTATE - 1), to *PIndex.
1582
1583 #define SM3LEAFLDCD(cState) \
1584 JU_SETDCD(*PIndex, Pjp, cState); \
1585 SM3LEAFLNODCD
1586
1587 #ifdef JUDY1
1588 #define SM3LEAFL_SETPOP1 // not needed in any cases.
1589 #else
1590 #define SM3LEAFL_SETPOP1 pop1 = JU_JPLEAF_POP0(Pjp) + 1
1591 #endif
1592
1593 #ifdef JUDYPREV
1594 #define SM3LEAFLNODCD \
1595 Pjll = P_JLL(Pjp->jp_Addr); \
1596 SM3LEAFL_SETPOP1; \
1597 offset = JU_JPLEAF_POP0(Pjp); assert(offset >= 0)
1598 #else
1599 #define SM3LEAFLNODCD \
1600 Pjll = P_JLL(Pjp->jp_Addr); \
1601 SM3LEAFL_SETPOP1; \
1602 offset = 0; assert(JU_JPLEAF_POP0(Pjp) >= 0);
1603 #endif
1604
1605 #if (defined(JUDYL) || (! defined(JU_64BIT)))
1606 case cJU_JPLEAF1:
1607
1608 SM3LEAFLDCD(1);
1609 JU_SETDIGIT1(*PIndex, ((uint8_t *) Pjll)[offset]);
1610 JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
1611 #endif
1612
1613 case cJU_JPLEAF2:
1614
1615 SM3LEAFLDCD(2);
1616 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
1617 | ((uint16_t *) Pjll)[offset];
1618 JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
1619
1620 #ifndef JU_64BIT
1621 case cJU_JPLEAF3:
1622 {
1623 Word_t lsb;
1624 SM3LEAFLNODCD;
1625 JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
1626 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
1627 JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
1628 }
1629
1630 #else
1631 case cJU_JPLEAF3:
1632 {
1633 Word_t lsb;
1634 SM3LEAFLDCD(3);
1635 JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
1636 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
1637 JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
1638 }
1639
1640 case cJU_JPLEAF4:
1641
1642 SM3LEAFLDCD(4);
1643 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
1644 | ((uint32_t *) Pjll)[offset];
1645 JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
1646
1647 case cJU_JPLEAF5:
1648 {
1649 Word_t lsb;
1650 SM3LEAFLDCD(5);
1651 JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (5 * offset));
1652 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
1653 JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
1654 }
1655
1656 case cJU_JPLEAF6:
1657 {
1658 Word_t lsb;
1659 SM3LEAFLDCD(6);
1660 JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (6 * offset));
1661 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
1662 JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
1663 }
1664
1665 case cJU_JPLEAF7:
1666 {
1667 Word_t lsb;
1668 SM3LEAFLNODCD;
1669 JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (7 * offset));
1670 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
1671 JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
1672 }
1673 #endif
1674
1675
1676 // ----------------------------------------------------------------------------
1677 // BITMAP LEAF:
1678 //
1679 // Look for the highest/lowest (right/left-most) non-null subexpanse, then use
1680 // the highest/lowest Index in that subexpanse, but first copy Dcd bytes
1681 // (always present since state 1 < cJU_ROOTSTATE) to *PIndex.
1682
1683 case cJU_JPLEAF_B1:
1684 {
1685 Pjlb_t Pjlb;
1686
1687 JU_SETDCD(*PIndex, Pjp, 1);
1688
1689 Pjlb = P_JLB(Pjp->jp_Addr);
1690 #ifdef JUDYPREV
1691 subexp = cJU_NUMSUBEXPL;
1692
1693 while (! JU_JLB_BITMAP(Pjlb, --subexp)) // find non-empty subexp.
1694 {
1695 if (subexp <= 0) // wholly empty bitmap.
1696 {
1697 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1698 JUDY1CODE(return(JERRI );)
1699 JUDYLCODE(return(PPJERR);)
1700 }
1701 }
1702
1703 // TBD: Might it be faster to just use a variant of BITMAPDIGIT*() that yields
1704 // the digit for the right-most Index with a bit set?
1705
1706 offset = SEARCHBITMAPMAXL(JU_JLB_BITMAP(Pjlb, subexp));
1707 // expected range:
1708 assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPL));
1709 #else
1710 subexp = -1;
1711
1712 while (! JU_JLB_BITMAP(Pjlb, ++subexp)) // find non-empty subexp.
1713 {
1714 if (subexp >= cJU_NUMSUBEXPL - 1) // didnt find one.
1715 {
1716 JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1717 JUDY1CODE(return(JERRI );)
1718 JUDYLCODE(return(PPJERR);)
1719 }
1720 }
1721
1722 offset = 0;
1723 #endif
1724
1725 JU_BITMAPDIGITL(digit, subexp, JU_JLB_BITMAP(Pjlb, subexp), offset);
1726 JU_SETDIGIT1(*PIndex, digit);
1727 JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
1728 // == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + (offset)));
1729
1730 } // case cJU_JPLEAF_B1
1731
1732 #ifdef JUDY1
1733 // ----------------------------------------------------------------------------
1734 // FULL POPULATION:
1735 //
1736 // Copy Dcd bytes to *PIndex (always present since state 1 < cJU_ROOTSTATE),
1737 // then set the highest/lowest possible digit as the LSB in *PIndex.
1738
1739 case cJ1_JPFULLPOPU1:
1740
1741 JU_SETDCD( *PIndex, Pjp, 1);
1742 #ifdef JUDYPREV
1743 JU_SETDIGIT1(*PIndex, cJU_BITSPERBITMAP - 1);
1744 #else
1745 JU_SETDIGIT1(*PIndex, 0);
1746 #endif
1747 JU_RET_FOUND_FULLPOPU1;
1748 #endif // JUDY1
1749
1750
1751 // ----------------------------------------------------------------------------
1752 // IMMEDIATE:
1753 //
1754 // Simply use the highest/lowest (right/left-most) Index in the Imm, but the
1755 // details vary depending on leaf Index Size and pop1. Note: There are no Dcd
1756 // bytes in an Immediate JP, but in a cJU_JPIMMED_*_01 JP, the field holds the
1757 // least bytes of the immediate Index.
1758
1759 case cJU_JPIMMED_1_01: SET_01(1); goto SM3Imm_01;
1760 case cJU_JPIMMED_2_01: SET_01(2); goto SM3Imm_01;
1761 case cJU_JPIMMED_3_01: SET_01(3); goto SM3Imm_01;
1762 #ifdef JU_64BIT
1763 case cJU_JPIMMED_4_01: SET_01(4); goto SM3Imm_01;
1764 case cJU_JPIMMED_5_01: SET_01(5); goto SM3Imm_01;
1765 case cJU_JPIMMED_6_01: SET_01(6); goto SM3Imm_01;
1766 case cJU_JPIMMED_7_01: SET_01(7); goto SM3Imm_01;
1767 #endif
1768 SM3Imm_01: JU_RET_FOUND_IMM_01(Pjp);
1769
1770 #ifdef JUDYPREV
1771 #define SM3IMM_OFFSET(cPop1) (cPop1) - 1 // highest.
1772 #else
1773 #define SM3IMM_OFFSET(cPop1) 0 // lowest.
1774 #endif
1775
1776 #define SM3IMM(cPop1,Next) \
1777 offset = SM3IMM_OFFSET(cPop1); \
1778 goto Next
1779
1780 case cJU_JPIMMED_1_02: SM3IMM( 2, SM3Imm1);
1781 case cJU_JPIMMED_1_03: SM3IMM( 3, SM3Imm1);
1782 #if (defined(JUDY1) || defined(JU_64BIT))
1783 case cJU_JPIMMED_1_04: SM3IMM( 4, SM3Imm1);
1784 case cJU_JPIMMED_1_05: SM3IMM( 5, SM3Imm1);
1785 case cJU_JPIMMED_1_06: SM3IMM( 6, SM3Imm1);
1786 case cJU_JPIMMED_1_07: SM3IMM( 7, SM3Imm1);
1787 #endif
1788 #if (defined(JUDY1) && defined(JU_64BIT))
1789 case cJ1_JPIMMED_1_08: SM3IMM( 8, SM3Imm1);
1790 case cJ1_JPIMMED_1_09: SM3IMM( 9, SM3Imm1);
1791 case cJ1_JPIMMED_1_10: SM3IMM(10, SM3Imm1);
1792 case cJ1_JPIMMED_1_11: SM3IMM(11, SM3Imm1);
1793 case cJ1_JPIMMED_1_12: SM3IMM(12, SM3Imm1);
1794 case cJ1_JPIMMED_1_13: SM3IMM(13, SM3Imm1);
1795 case cJ1_JPIMMED_1_14: SM3IMM(14, SM3Imm1);
1796 case cJ1_JPIMMED_1_15: SM3IMM(15, SM3Imm1);
1797 #endif
1798
1799 SM3Imm1: JU_SETDIGIT1(*PIndex, ((uint8_t *) PJI)[offset]);
1800 JU_RET_FOUND_IMM(Pjp, offset);
1801
1802 #if (defined(JUDY1) || defined(JU_64BIT))
1803 case cJU_JPIMMED_2_02: SM3IMM(2, SM3Imm2);
1804 case cJU_JPIMMED_2_03: SM3IMM(3, SM3Imm2);
1805 #endif
1806 #if (defined(JUDY1) && defined(JU_64BIT))
1807 case cJ1_JPIMMED_2_04: SM3IMM(4, SM3Imm2);
1808 case cJ1_JPIMMED_2_05: SM3IMM(5, SM3Imm2);
1809 case cJ1_JPIMMED_2_06: SM3IMM(6, SM3Imm2);
1810 case cJ1_JPIMMED_2_07: SM3IMM(7, SM3Imm2);
1811 #endif
1812
1813 #if (defined(JUDY1) || defined(JU_64BIT))
1814 SM3Imm2: *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
1815 | ((uint16_t *) PJI)[offset];
1816 JU_RET_FOUND_IMM(Pjp, offset);
1817 #endif
1818
1819 #if (defined(JUDY1) || defined(JU_64BIT))
1820 case cJU_JPIMMED_3_02: SM3IMM(2, SM3Imm3);
1821 #endif
1822 #if (defined(JUDY1) && defined(JU_64BIT))
1823 case cJ1_JPIMMED_3_03: SM3IMM(3, SM3Imm3);
1824 case cJ1_JPIMMED_3_04: SM3IMM(4, SM3Imm3);
1825 case cJ1_JPIMMED_3_05: SM3IMM(5, SM3Imm3);
1826 #endif
1827
1828 #if (defined(JUDY1) || defined(JU_64BIT))
1829 SM3Imm3:
1830 {
1831 Word_t lsb;
1832 JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (3 * offset));
1833 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
1834 JU_RET_FOUND_IMM(Pjp, offset);
1835 }
1836 #endif
1837
1838 #if (defined(JUDY1) && defined(JU_64BIT))
1839 case cJ1_JPIMMED_4_02: SM3IMM(2, SM3Imm4);
1840 case cJ1_JPIMMED_4_03: SM3IMM(3, SM3Imm4);
1841
1842 SM3Imm4: *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
1843 | ((uint32_t *) PJI)[offset];
1844 JU_RET_FOUND_IMM(Pjp, offset);
1845
1846 case cJ1_JPIMMED_5_02: SM3IMM(2, SM3Imm5);
1847 case cJ1_JPIMMED_5_03: SM3IMM(3, SM3Imm5);
1848
1849 SM3Imm5:
1850 {
1851 Word_t lsb;
1852 JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (5 * offset));
1853 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
1854 JU_RET_FOUND_IMM(Pjp, offset);
1855 }
1856
1857 case cJ1_JPIMMED_6_02: SM3IMM(2, SM3Imm6);
1858
1859 SM3Imm6:
1860 {
1861 Word_t lsb;
1862 JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (6 * offset));
1863 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
1864 JU_RET_FOUND_IMM(Pjp, offset);
1865 }
1866
1867 case cJ1_JPIMMED_7_02: SM3IMM(2, SM3Imm7);
1868
1869 SM3Imm7:
1870 {
1871 Word_t lsb;
1872 JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (7 * offset));
1873 *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
1874 JU_RET_FOUND_IMM(Pjp, offset);
1875 }
1876 #endif // (JUDY1 && JU_64BIT)
1877
1878
1879 // ----------------------------------------------------------------------------
1880 // OTHER CASES:
1881
1882 default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
1883 JUDY1CODE(return(JERRI );)
1884 JUDYLCODE(return(PPJERR);)
1885
1886 } // SM3Findlimit switch.
1887
1888 /*NOTREACHED*/
1889
1890 } // Judy1Prev() / Judy1Next() / JudyLPrev() / JudyLNext()
1891