1 // Copyright (C) 2000 - 2002 Hewlett-Packard Company
2 //
3 // This program is free software; you can redistribute it and/or modify it
4 // under the term of the GNU Lesser General Public License as published by the
5 // Free Software Foundation; either version 2 of the License, or (at your
6 // option) any later version.
7 //
8 // This program is distributed in the hope that it will be useful, but WITHOUT
9 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
11 // for more details.
12 //
13 // You should have received a copy of the GNU Lesser General Public License
14 // along with this program; if not, write to the Free Software Foundation,
15 // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 // _________________
17
18 // Judy*PrevEmpty() and Judy*NextEmpty() functions for Judy1 and JudyL.
19 // Compile with one of -DJUDY1 or -DJUDYL.
20 //
21 // Compile with -DJUDYNEXT for the Judy*NextEmpty() function; otherwise
22 // defaults to Judy*PrevEmpty().
23 //
24 // Compile with -DTRACEJPSE to trace JP traversals.
25 //
26 // This file is separate from JudyPrevNext.c because it differs too greatly for
27 // ifdefs. This might be a bit surprising, but there are two reasons:
28 //
29 // - First, down in the details, searching for an empty index (SearchEmpty) is
30 // remarkably asymmetric with searching for a valid index (SearchValid),
31 // mainly with respect to: No return of a value area for JudyL; partially-
32 // full versus totally-full JPs; and handling of narrow pointers.
33 //
34 // - Second, we chose to implement SearchEmpty without a backtrack stack or
35 // backtrack engine, partly as an experiment, and partly because we think
36 // restarting from the top of the tree is less likely for SearchEmpty than
37 // for SearchValid, because empty indexes are more likely than valid indexes.
38 //
39 // A word about naming: A prior version of this feature (see 4.13) was named
40 // Judy*Free(), but there were concerns about that being read as a verb rather
41 // than an adjective. After prolonged debate and based on user input, we
42 // changed "Free" to "Empty".
43
44 #if (! (defined(JUDY1) || defined(JUDYL)))
45 #error: One of -DJUDY1 or -DJUDYL must be specified.
46 #endif
47
48 #ifndef JUDYNEXT
49 #ifndef JUDYPREV
50 #define JUDYPREV 1 // neither set => use default.
51 #endif
52 #endif
53
54 #ifdef JUDY1
55 #include "Judy1.h"
56 #else
57 #include "JudyL.h"
58 #endif
59
60 #include "JudyPrivate1L.h"
61
62 #ifdef TRACEJPSE
63 #include "JudyPrintJP.c"
64 #endif
65
66
67 // ****************************************************************************
68 // J U D Y 1 P R E V E M P T Y
69 // J U D Y 1 N E X T E M P T Y
70 // J U D Y L P R E V E M P T Y
71 // J U D Y L N E X T E M P T Y
72 //
73 // See the manual entry for the API.
74 //
75 // OVERVIEW OF Judy*PrevEmpty() / Judy*NextEmpty():
76 //
77 // See also for comparison the equivalent comments in JudyPrevNext.c.
78 //
79 // Take the callers *PIndex and subtract/add 1, but watch out for
80 // underflow/overflow, which means "no previous/next empty index found." Use a
81 // reentrant switch statement (state machine, see SMGetRestart and
82 // SMGetContinue) to decode Index, starting with the JRP (PArray), through a
83 // JPM and branches, if any, down to an immediate or a leaf. Look for Index in
84 // that immediate or leaf, and if not found (invalid index), return success
85 // (Index is empty).
86 //
87 // This search can result in a dead end where taking a different path is
88 // required. There are four kinds of dead ends:
89 //
90 // BRANCH PRIMARY dead end: Encountering a fully-populated JP for the
91 // appropriate digit in Index. Search sideways in the branch for the
92 // previous/next absent/null/non-full JP, and if one is found, set Index to the
93 // highest/lowest index possible in that JPs expanse. Then if the JP is an
94 // absent or null JP, return success; otherwise for a non-full JP, traverse
95 // through the partially populated JP.
96 //
97 // BRANCH SECONDARY dead end: Reaching the end of a branch during a sideways
98 // search after a branch primary dead end. Set Index to the lowest/highest
99 // index possible in the whole branchs expanse (one higher/lower than the
100 // previous/next branchs expanse), then restart at the top of the tree, which
101 // includes pre-decrementing/incrementing Index (again) and watching for
102 // underflow/overflow (again).
103 //
104 // LEAF PRIMARY dead end: Finding a valid (non-empty) index in an immediate or
105 // leaf matching Index. Search sideways in the immediate/leaf for the
106 // previous/next empty index; if found, set *PIndex to match and return success.
107 //
108 // LEAF SECONDARY dead end: Reaching the end of an immediate or leaf during a
109 // sideways search after a leaf primary dead end. Just as for a branch
110 // secondary dead end, restart at the top of the tree with Index set to the
111 // lowest/highest index possible in the whole immediate/leafs expanse.
112 // TBD: If leaf secondary dead end occurs, could shortcut and treat it as a
113 // branch primary dead end; but this would require remembering the parent
114 // branchs type and offset (a "one-deep stack"), and also wrestling with
115 // narrow pointers, at least for leaves (but not for immediates).
116 //
117 // Note some ASYMMETRIES between SearchValid and SearchEmpty:
118 //
119 // - The SearchValid code, upon descending through a narrow pointer, if Index
120 // is outside the expanse of the subsidiary node (effectively a secondary
121 // dead end), must decide whether to backtrack or findlimit. But the
122 // SearchEmpty code simply returns success (Index is empty).
123 //
124 // - Similarly, the SearchValid code, upon finding no previous/next index in
125 // the expanse of a narrow pointer (again, a secondary dead end), can simply
126 // start to backtrack at the parent JP. But the SearchEmpty code would have
127 // to first determine whether or not the parent JPs narrow expanse contains
128 // a previous/next empty index outside the subexpanse. Rather than keeping a
129 // parent state stack and backtracking this way, upon a secondary dead end,
130 // the SearchEmpty code simply restarts at the top of the tree, whether or
131 // not a narrow pointer is involved. Again, see the equivalent comments in
132 // JudyPrevNext.c for comparison.
133 //
134 // This function is written iteratively for speed, rather than recursively.
135 //
136 // TBD: Wed like to enhance this function to make successive searches faster.
137 // This would require saving some previous state, including the previous Index
138 // returned, and in which leaf it was found. If the next call is for the same
139 // Index and the array has not been modified, start at the same leaf. This
140 // should be much easier to implement since this is iterative rather than
141 // recursive code.
142
143 #ifdef JUDY1
144 #ifdef JUDYPREV
Judy1PrevEmpty(Pcvoid_t PArray,Word_t * PIndex,PJError_t PJError)145 FUNCTION int Judy1PrevEmpty
146 #else
147 FUNCTION int Judy1NextEmpty
148 #endif
149 #else
150 #ifdef JUDYPREV
151 FUNCTION int JudyLPrevEmpty
152 #else
153 FUNCTION int JudyLNextEmpty
154 #endif
155 #endif
156 (
157 Pcvoid_t PArray, // Judy array to search.
158 Word_t * PIndex, // starting point and result.
159 PJError_t PJError // optional, for returning error info.
160 )
161 {
162 Word_t Index; // fast copy, in a register.
163 Pjp_t Pjp; // current JP.
164 Pjbl_t Pjbl; // Pjp->jp_Addr masked and cast to types:
165 Pjbb_t Pjbb;
166 Pjbu_t Pjbu;
167 Pjlb_t Pjlb;
168 PWord_t Pword; // alternate name for use by GET* macros.
169
170 Word_t digit; // next digit to decode from Index.
171 Word_t digits; // current state in SM = digits left to decode.
172 Word_t pop0; // in a leaf.
173 Word_t pop0mask; // precalculated to avoid variable shifts.
174 long offset; // within a branch or leaf (can be large).
175 int subexp; // subexpanse in a bitmap branch.
176 BITMAPB_t bitposmaskB; // bit in bitmap for bitmap branch.
177 BITMAPL_t bitposmaskL; // bit in bitmap for bitmap leaf.
178 Word_t possfullJP1; // JP types for possibly full subexpanses:
179 Word_t possfullJP2;
180 Word_t possfullJP3;
181
182
183 // ----------------------------------------------------------------------------
184 // M A C R O S
185 //
186 // These are intended to make the code a bit more readable and less redundant.
187
188
189 // CHECK FOR NULL JP:
190 //
191 // TBD: In principle this can be reduced (here and in other *.c files) to just
192 // the latter clause since no Type should ever be below cJU_JPNULL1, but in
193 // fact some root pointer types can be lower, so for safety do both checks.
194
195 #define JPNULL(Type) (((Type) >= cJU_JPNULL1) && ((Type) <= cJU_JPNULLMAX))
196
197
198 // CHECK FOR A FULL JP:
199 //
200 // Given a JP, indicate if it is fully populated. Use digits, pop0mask, and
201 // possfullJP1..3 in the context.
202 //
203 // This is a difficult problem because it requires checking the Pop0 bits for
204 // all-ones, but the number of bytes depends on the JP type, which is not
205 // directly related to the parent branchs type or level -- the JPs child
206 // could be under a narrow pointer (hence not full). The simple answer
207 // requires switching on or otherwise calculating the JP type, which could be
208 // slow. Instead, in SMPREPB* precalculate pop0mask and also record in
209 // possfullJP1..3 the child JP (branch) types that could possibly be full (one
210 // level down), and use them here. For level-2 branches (with digits == 2),
211 // the test for a full child depends on Judy1/JudyL.
212 //
213 // Note: This cannot be applied to the JP in a JPM because it doesnt have
214 // enough pop0 digits.
215 //
216 // TBD: JPFULL_BRANCH diligently checks for BranchL or BranchB, where neither
217 // of those can ever be full as it turns out. Could just check for a BranchU
218 // at the right level. Also, pop0mask might be overkill, its not used much,
219 // so perhaps just call cJU_POP0MASK(digits - 1) here?
220 //
221 // First, JPFULL_BRANCH checks for a full expanse for a JP whose child can be a
222 // branch, that is, a JP in a branch at level 3 or higher:
223
224 #define JPFULL_BRANCH(Pjp) \
225 ((((JU_JPDCDPOP0(Pjp) ^ cJU_ALLONES) & pop0mask) == 0) \
226 && ((JU_JPTYPE(Pjp) == possfullJP1) \
227 || (JU_JPTYPE(Pjp) == possfullJP2) \
228 || (JU_JPTYPE(Pjp) == possfullJP3)))
229
230 #ifdef JUDY1
231 #define JPFULL(Pjp) \
232 ((digits == 2) ? \
233 (JU_JPTYPE(Pjp) == cJ1_JPFULLPOPU1) : JPFULL_BRANCH(Pjp))
234 #else
235 #define JPFULL(Pjp) \
236 ((digits == 2) ? \
237 (JU_JPTYPE(Pjp) == cJU_JPLEAF_B1) \
238 && (((JU_JPDCDPOP0(Pjp) & cJU_POP0MASK(1)) == cJU_POP0MASK(1))) : \
239 JPFULL_BRANCH(Pjp))
240 #endif
241
242
243 // RETURN SUCCESS:
244 //
245 // This hides the need to set *PIndex back to the local value of Index -- use a
246 // local value for faster operation. Note that the callers *PIndex is ALWAYS
247 // modified upon success, at least decremented/incremented.
248
249 #define RET_SUCCESS { *PIndex = Index; return(1); }
250
251
252 // RETURN A CORRUPTION:
253
254 #define RET_CORRUPT { JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); return(JERRI); }
255
256
257 // SEARCH A BITMAP BRANCH:
258 //
259 // This is a weak analog of j__udySearchLeaf*() for bitmap branches. Return
260 // the actual or next-left position, base 0, of Digit in a BITMAPB_t bitmap
261 // (subexpanse of a full bitmap), also given a Bitposmask for Digit. The
262 // position is the offset within the set bits.
263 //
264 // Unlike j__udySearchLeaf*(), the offset is not returned bit-complemented if
265 // Digits bit is unset, because the caller can check the bitmap themselves to
266 // determine that. Also, if Digits bit is unset, the returned offset is to
267 // the next-left JP or index (including -1), not to the "ideal" position for
268 // the index = next-right JP or index.
269 //
270 // Shortcut and skip calling j__udyCountBitsB() if the bitmap is full, in which
271 // case (Digit % cJU_BITSPERSUBEXPB) itself is the base-0 offset.
272
273 #define SEARCHBITMAPB(Bitmap,Digit,Bitposmask) \
274 (((Bitmap) == cJU_FULLBITMAPB) ? (Digit % cJU_BITSPERSUBEXPB) : \
275 j__udyCountBitsB((Bitmap) & JU_MASKLOWERINC(Bitposmask)) - 1)
276
277 #ifdef JUDYPREV
278 // Equivalent to search for the highest offset in Bitmap, that is, one less
279 // than the number of bits set:
280
281 #define SEARCHBITMAPMAXB(Bitmap) \
282 (((Bitmap) == cJU_FULLBITMAPB) ? cJU_BITSPERSUBEXPB - 1 : \
283 j__udyCountBitsB(Bitmap) - 1)
284 #endif
285
286
287 // CHECK DECODE BYTES:
288 //
289 // Check Decode bytes in a JP against the equivalent portion of Index. If they
290 // dont match, Index is outside the subexpanse of a narrow pointer, hence is
291 // empty.
292
293 #define CHECKDCD(cDigits) \
294 if (JU_DCDNOTMATCHINDEX(Index, Pjp, cDigits)) RET_SUCCESS
295
296
297 // REVISE REMAINDER OF INDEX:
298 //
299 // Put one digit in place in Index and clear/set the lower digits, if any, so
300 // the resulting Index is at the start/end of an expanse, or just clear/set the
301 // least digits.
302 //
303 // Actually, to make simple use of JU_LEASTBYTESMASK, first clear/set all least
304 // digits of Index including the digit to be overridden, then set the value of
305 // that one digit. If Digits == 1 the first operation is redundant, but either
306 // very fast or even removed by the optimizer.
307
308 #define CLEARLEASTDIGITS(Digits) Index &= ~JU_LEASTBYTESMASK(Digits)
309 #define SETLEASTDIGITS( Digits) Index |= JU_LEASTBYTESMASK(Digits)
310
311 #define CLEARLEASTDIGITS_D(Digit,Digits) \
312 { \
313 CLEARLEASTDIGITS(Digits); \
314 JU_SETDIGIT(Index, Digit, Digits); \
315 }
316
317 #define SETLEASTDIGITS_D(Digit,Digits) \
318 { \
319 SETLEASTDIGITS(Digits); \
320 JU_SETDIGIT(Index, Digit, Digits); \
321 }
322
323
324 // SET REMAINDER OF INDEX AND THEN RETURN OR CONTINUE:
325
326 #define SET_AND_RETURN(OpLeastDigits,Digit,Digits) \
327 { \
328 OpLeastDigits(Digit, Digits); \
329 RET_SUCCESS; \
330 }
331
332 #define SET_AND_CONTINUE(OpLeastDigits,Digit,Digits) \
333 { \
334 OpLeastDigits(Digit, Digits); \
335 goto SMGetContinue; \
336 }
337
338
339 // PREPARE TO HANDLE A LEAFW OR JP BRANCH IN THE STATE MACHINE:
340 //
341 // Extract a state-dependent digit from Index in a "constant" way, then jump to
342 // common code for multiple cases.
343 //
344 // TBD: Should this macro do more, such as preparing variable-shift masks for
345 // use in CLEARLEASTDIGITS and SETLEASTDIGITS?
346
347 #define SMPREPB(cDigits,Next,PossFullJP1,PossFullJP2,PossFullJP3) \
348 digits = (cDigits); \
349 digit = JU_DIGITATSTATE(Index, cDigits); \
350 pop0mask = cJU_POP0MASK((cDigits) - 1); /* for branchs JPs */ \
351 possfullJP1 = (PossFullJP1); \
352 possfullJP2 = (PossFullJP2); \
353 possfullJP3 = (PossFullJP3); \
354 goto Next
355
356 // Variations for specific-level branches and for shorthands:
357 //
358 // Note: SMPREPB2 need not initialize possfullJP* because JPFULL does not use
359 // them for digits == 2, but gcc -Wall isnt quite smart enough to see this, so
360 // waste a bit of time and space to get rid of the warning:
361
362 #define SMPREPB2(Next) \
363 digits = 2; \
364 digit = JU_DIGITATSTATE(Index, 2); \
365 pop0mask = cJU_POP0MASK(1); /* for branchs JPs */ \
366 possfullJP1 = possfullJP2 = possfullJP3 = 0; \
367 goto Next
368
369 #define SMPREPB3(Next) SMPREPB(3, Next, cJU_JPBRANCH_L2, \
370 cJU_JPBRANCH_B2, \
371 cJU_JPBRANCH_U2)
372 #ifndef JU_64BIT
373 #define SMPREPBL(Next) SMPREPB(cJU_ROOTSTATE, Next, cJU_JPBRANCH_L3, \
374 cJU_JPBRANCH_B3, \
375 cJU_JPBRANCH_U3)
376 #else
377 #define SMPREPB4(Next) SMPREPB(4, Next, cJU_JPBRANCH_L3, \
378 cJU_JPBRANCH_B3, \
379 cJU_JPBRANCH_U3)
380 #define SMPREPB5(Next) SMPREPB(5, Next, cJU_JPBRANCH_L4, \
381 cJU_JPBRANCH_B4, \
382 cJU_JPBRANCH_U4)
383 #define SMPREPB6(Next) SMPREPB(6, Next, cJU_JPBRANCH_L5, \
384 cJU_JPBRANCH_B5, \
385 cJU_JPBRANCH_U5)
386 #define SMPREPB7(Next) SMPREPB(7, Next, cJU_JPBRANCH_L6, \
387 cJU_JPBRANCH_B6, \
388 cJU_JPBRANCH_U6)
389 #define SMPREPBL(Next) SMPREPB(cJU_ROOTSTATE, Next, cJU_JPBRANCH_L7, \
390 cJU_JPBRANCH_B7, \
391 cJU_JPBRANCH_U7)
392 #endif
393
394
395 // RESTART AFTER SECONDARY DEAD END:
396 //
397 // Set Index to the first/last index in the branch or leaf subexpanse and start
398 // over at the top of the tree.
399
400 #ifdef JUDYPREV
401 #define SMRESTART(Digits) { CLEARLEASTDIGITS(Digits); goto SMGetRestart; }
402 #else
403 #define SMRESTART(Digits) { SETLEASTDIGITS( Digits); goto SMGetRestart; }
404 #endif
405
406
407 // CHECK EDGE OF LEAFS EXPANSE:
408 //
409 // Given the LSBs of the lowest/highest valid index in a leaf (or equivalently
410 // in an immediate JP), the level (index size) of the leaf, and the full index
411 // to return (as Index in the context) already set to the full index matching
412 // the lowest/highest one, determine if there is an empty index in the leafs
413 // expanse below/above the lowest/highest index, which is true if the
414 // lowest/highest index is not at the "edge" of the leafs expanse based on its
415 // LSBs. If so, return Index decremented/incremented; otherwise restart at the
416 // top of the tree.
417 //
418 // Note: In many cases Index is already at the right spot and calling
419 // SMRESTART instead of just going directly to SMGetRestart is a bit of
420 // overkill.
421 //
422 // Note: Variable shift occurs if Digits is not a constant.
423
424 #ifdef JUDYPREV
425 #define LEAF_EDGE(MinIndex,Digits) \
426 { \
427 if (MinIndex) { --Index; RET_SUCCESS; } \
428 SMRESTART(Digits); \
429 }
430 #else
431 #define LEAF_EDGE(MaxIndex,Digits) \
432 { \
433 if ((MaxIndex) != JU_LEASTBYTES(cJU_ALLONES, Digits)) \
434 { ++Index; RET_SUCCESS; } \
435 SMRESTART(Digits); \
436 }
437 #endif
438
439 // Same as above except Index is not already set to match the lowest/highest
440 // index, so do that before decrementing/incrementing it:
441
442 #ifdef JUDYPREV
443 #define LEAF_EDGE_SET(MinIndex,Digits) \
444 { \
445 if (MinIndex) \
446 { JU_SETDIGITS(Index, MinIndex, Digits); --Index; RET_SUCCESS; } \
447 SMRESTART(Digits); \
448 }
449 #else
450 #define LEAF_EDGE_SET(MaxIndex,Digits) \
451 { \
452 if ((MaxIndex) != JU_LEASTBYTES(cJU_ALLONES, Digits)) \
453 { JU_SETDIGITS(Index, MaxIndex, Digits); ++Index; RET_SUCCESS; } \
454 SMRESTART(Digits); \
455 }
456 #endif
457
458
459 // FIND A HOLE (EMPTY INDEX) IN AN IMMEDIATE OR LEAF:
460 //
461 // Given an index location in a leaf (or equivalently an immediate JP) known to
462 // contain a usable hole (an empty index less/greater than Index), and the LSBs
463 // of a minimum/maximum index to locate, find the previous/next empty index and
464 // return it.
465 //
466 // Note: "Even" index sizes (1,2,4[,8] bytes) have corresponding native C
467 // types; "odd" index sizes dont, but they are not represented here because
468 // they are handled completely differently; see elsewhere.
469
470 #ifdef JUDYPREV
471
472 #define LEAF_HOLE_EVEN(cDigits,Pjll,IndexLSB) \
473 { \
474 while (*(Pjll) > (IndexLSB)) --(Pjll); /* too high */ \
475 if (*(Pjll) < (IndexLSB)) RET_SUCCESS /* Index is empty */ \
476 while (*(--(Pjll)) == --(IndexLSB)) /* null, find a hole */;\
477 JU_SETDIGITS(Index, IndexLSB, cDigits); \
478 RET_SUCCESS; \
479 }
480 #else
481 #define LEAF_HOLE_EVEN(cDigits,Pjll,IndexLSB) \
482 { \
483 while (*(Pjll) < (IndexLSB)) ++(Pjll); /* too low */ \
484 if (*(Pjll) > (IndexLSB)) RET_SUCCESS /* Index is empty */ \
485 while (*(++(Pjll)) == ++(IndexLSB)) /* null, find a hole */;\
486 JU_SETDIGITS(Index, IndexLSB, cDigits); \
487 RET_SUCCESS; \
488 }
489 #endif
490
491
492 // SEARCH FOR AN EMPTY INDEX IN AN IMMEDIATE OR LEAF:
493 //
494 // Given a pointer to the first index in a leaf (or equivalently an immediate
495 // JP), the population of the leaf, and a first empty Index to find (inclusive,
496 // as Index in the context), where Index is known to fall within the expanse of
497 // the leaf to search, efficiently find the previous/next empty index in the
498 // leaf, if any. For simplicity the following overview is stated in terms of
499 // Judy*NextEmpty() only, but the same concepts apply symmetrically for
500 // Judy*PrevEmpty(). Also, in each case the comparisons are for the LSBs of
501 // Index and leaf indexes, according to the leafs level.
502 //
503 // 1. If Index is GREATER than the last (highest) index in the leaf
504 // (maxindex), return success, Index is empty. (Remember, Index is known
505 // to be in the leafs expanse.)
506 //
507 // 2. If Index is EQUAL to maxindex: If maxindex is not at the edge of the
508 // leafs expanse, increment Index and return success, there is an empty
509 // Index one higher than any in the leaf; otherwise restart with Index
510 // reset to the upper edge of the leafs expanse. Note: This might cause
511 // an extra cache line fill, but this is OK for repeatedly-called search
512 // code, and it saves CPU time.
513 //
514 // 3. If Index is LESS than maxindex, check for "dense to end of leaf":
515 // Subtract Index from maxindex, and back up that many slots in the leaf.
516 // If the resulting offset is not before the start of the leaf then compare
517 // the index at this offset (baseindex) with Index:
518 //
519 // 3a. If GREATER, the leaf must be corrupt, since indexes are sorted and
520 // there are no duplicates.
521 //
522 // 3b. If EQUAL, the leaf is "dense" from Index to maxindex, meaning there is
523 // no reason to search it. "Slide right" to the high end of the leaf
524 // (modify Index to maxindex) and continue with step 2 above.
525 //
526 // 3c. If LESS, continue with step 4.
527 //
528 // 4. If the offset based on maxindex minus Index falls BEFORE the start of
529 // the leaf, or if, per 3c above, baseindex is LESS than Index, the leaf is
530 // guaranteed "not dense to the end" and a usable empty Index must exist.
531 // This supports a more efficient search loop. Start at the FIRST index in
532 // the leaf, or one BEYOND baseindex, respectively, and search the leaf as
533 // follows, comparing each current index (currindex) with Index:
534 //
535 // 4a. If LESS, keep going to next index. Note: This is certain to terminate
536 // because maxindex is known to be greater than Index, hence the loop can
537 // be small and fast.
538 //
539 // 4b. If EQUAL, loop and increment Index until finding currindex greater than
540 // Index, and return success with the modified Index.
541 //
542 // 4c. If GREATER, return success, Index (unmodified) is empty.
543 //
544 // Note: These are macros rather than functions for speed.
545
546 #ifdef JUDYPREV
547
548 #define JSLE_EVEN(Addr,Pop0,cDigits,LeafType) \
549 { \
550 LeafType * PjllLSB = (LeafType *) (Addr); \
551 LeafType IndexLSB = Index; /* auto-masking */ \
552 \
553 /* Index before or at start of leaf: */ \
554 \
555 if (*PjllLSB >= IndexLSB) /* no need to search */ \
556 { \
557 if (*PjllLSB > IndexLSB) RET_SUCCESS; /* Index empty */ \
558 LEAF_EDGE(*PjllLSB, cDigits); \
559 } \
560 \
561 /* Index in or after leaf: */ \
562 \
563 offset = IndexLSB - *PjllLSB; /* tentative offset */ \
564 if (offset <= (Pop0)) /* can check density */ \
565 { \
566 PjllLSB += offset; /* move to slot */ \
567 \
568 if (*PjllLSB <= IndexLSB) /* dense or corrupt */ \
569 { \
570 if (*PjllLSB == IndexLSB) /* dense, check edge */ \
571 LEAF_EDGE_SET(PjllLSB[-offset], cDigits); \
572 RET_CORRUPT; \
573 } \
574 --PjllLSB; /* not dense, start at previous */ \
575 } \
576 else PjllLSB = ((LeafType *) (Addr)) + (Pop0); /* start at max */ \
577 \
578 LEAF_HOLE_EVEN(cDigits, PjllLSB, IndexLSB); \
579 }
580
581 // JSLE_ODD is completely different from JSLE_EVEN because its important to
582 // minimize copying odd indexes to compare them (see 4.14). Furthermore, a
583 // very complex version (4.17, but abandoned before fully debugged) that
584 // avoided calling j__udySearchLeaf*() ran twice as fast as 4.14, but still
585 // half as fast as SearchValid. Doug suggested that to minimize complexity and
586 // share common code we should use j__udySearchLeaf*() for the initial search
587 // to establish if Index is empty, which should be common. If Index is valid
588 // in a leaf or immediate indexes, odds are good that an empty Index is nearby,
589 // so for simplicity just use a *COPY* function to linearly search the
590 // remainder.
591 //
592 // TBD: Pathological case? Average performance should be good, but worst-case
593 // might suffer. When Search says the initial Index is valid, so a linear
594 // copy-and-compare is begun, if the caller builds fairly large leaves with
595 // dense clusters AND frequently does a SearchEmpty at one end of such a
596 // cluster, performance wont be very good. Might a dense-check help? This
597 // means checking offset against the index at offset, and then against the
598 // first/last index in the leaf. We doubt the pathological case will appear
599 // much in real applications because they will probably alternate SearchValid
600 // and SearchEmpty calls.
601
602 #define JSLE_ODD(cDigits,Pjll,Pop0,Search,Copy) \
603 { \
604 Word_t IndexLSB; /* least bytes only */ \
605 Word_t IndexFound; /* in leaf */ \
606 \
607 if ((offset = Search(Pjll, (Pop0) + 1, Index)) < 0) \
608 RET_SUCCESS; /* Index is empty */ \
609 \
610 IndexLSB = JU_LEASTBYTES(Index, cDigits); \
611 offset *= (cDigits); \
612 \
613 while ((offset -= (cDigits)) >= 0) \
614 { /* skip until empty or start */ \
615 Copy(IndexFound, ((uint8_t *) (Pjll)) + offset); \
616 if (IndexFound != (--IndexLSB)) /* found an empty */ \
617 { JU_SETDIGITS(Index, IndexLSB, cDigits); RET_SUCCESS; }\
618 } \
619 LEAF_EDGE_SET(IndexLSB, cDigits); \
620 }
621
622 #else // JUDYNEXT
623
624 #define JSLE_EVEN(Addr,Pop0,cDigits,LeafType) \
625 { \
626 LeafType * PjllLSB = ((LeafType *) (Addr)) + (Pop0); \
627 LeafType IndexLSB = Index; /* auto-masking */ \
628 \
629 /* Index at or after end of leaf: */ \
630 \
631 if (*PjllLSB <= IndexLSB) /* no need to search */ \
632 { \
633 if (*PjllLSB < IndexLSB) RET_SUCCESS; /* Index empty */\
634 LEAF_EDGE(*PjllLSB, cDigits); \
635 } \
636 \
637 /* Index before or in leaf: */ \
638 \
639 offset = *PjllLSB - IndexLSB; /* tentative offset */ \
640 if (offset <= (Pop0)) /* can check density */ \
641 { \
642 PjllLSB -= offset; /* move to slot */ \
643 \
644 if (*PjllLSB >= IndexLSB) /* dense or corrupt */ \
645 { \
646 if (*PjllLSB == IndexLSB) /* dense, check edge */ \
647 LEAF_EDGE_SET(PjllLSB[offset], cDigits); \
648 RET_CORRUPT; \
649 } \
650 ++PjllLSB; /* not dense, start at next */ \
651 } \
652 else PjllLSB = (LeafType *) (Addr); /* start at minimum */ \
653 \
654 LEAF_HOLE_EVEN(cDigits, PjllLSB, IndexLSB); \
655 }
656
657 #define JSLE_ODD(cDigits,Pjll,Pop0,Search,Copy) \
658 { \
659 Word_t IndexLSB; /* least bytes only */ \
660 Word_t IndexFound; /* in leaf */ \
661 int offsetmax; /* in bytes */ \
662 \
663 if ((offset = Search(Pjll, (Pop0) + 1, Index)) < 0) \
664 RET_SUCCESS; /* Index is empty */ \
665 \
666 IndexLSB = JU_LEASTBYTES(Index, cDigits); \
667 offset *= (cDigits); \
668 offsetmax = (Pop0) * (cDigits); /* single multiply */ \
669 \
670 while ((offset += (cDigits)) <= offsetmax) \
671 { /* skip until empty or end */ \
672 Copy(IndexFound, ((uint8_t *) (Pjll)) + offset); \
673 if (IndexFound != (++IndexLSB)) /* found an empty */ \
674 { JU_SETDIGITS(Index, IndexLSB, cDigits); RET_SUCCESS; } \
675 } \
676 LEAF_EDGE_SET(IndexLSB, cDigits); \
677 }
678
679 #endif // JUDYNEXT
680
681 // Note: Immediate indexes never fill a single index group, so for odd index
682 // sizes, save time by calling JSLE_ODD_IMM instead of JSLE_ODD.
683
684 #define j__udySearchLeafEmpty1(Addr,Pop0) \
685 JSLE_EVEN(Addr, Pop0, 1, uint8_t)
686
687 #define j__udySearchLeafEmpty2(Addr,Pop0) \
688 JSLE_EVEN(Addr, Pop0, 2, uint16_t)
689
690 #define j__udySearchLeafEmpty3(Addr,Pop0) \
691 JSLE_ODD(3, Addr, Pop0, j__udySearchLeaf3, JU_COPY3_PINDEX_TO_LONG)
692
693 #ifndef JU_64BIT
694
695 #define j__udySearchLeafEmptyL(Addr,Pop0) \
696 JSLE_EVEN(Addr, Pop0, 4, Word_t)
697
698 #else
699
700 #define j__udySearchLeafEmpty4(Addr,Pop0) \
701 JSLE_EVEN(Addr, Pop0, 4, uint32_t)
702
703 #define j__udySearchLeafEmpty5(Addr,Pop0) \
704 JSLE_ODD(5, Addr, Pop0, j__udySearchLeaf5, JU_COPY5_PINDEX_TO_LONG)
705
706 #define j__udySearchLeafEmpty6(Addr,Pop0) \
707 JSLE_ODD(6, Addr, Pop0, j__udySearchLeaf6, JU_COPY6_PINDEX_TO_LONG)
708
709 #define j__udySearchLeafEmpty7(Addr,Pop0) \
710 JSLE_ODD(7, Addr, Pop0, j__udySearchLeaf7, JU_COPY7_PINDEX_TO_LONG)
711
712 #define j__udySearchLeafEmptyL(Addr,Pop0) \
713 JSLE_EVEN(Addr, Pop0, 8, Word_t)
714
715 #endif // JU_64BIT
716
717
718 // ----------------------------------------------------------------------------
719 // START OF CODE:
720 //
721 // CHECK FOR SHORTCUTS:
722 //
723 // Error out if PIndex is null.
724
725 if (PIndex == (PWord_t) NULL)
726 {
727 JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
728 return(JERRI);
729 }
730
731 Index = *PIndex; // fast local copy.
732
733 // Set and pre-decrement/increment Index, watching for underflow/overflow:
734 //
735 // An out-of-bounds Index means failure: No previous/next empty index.
736
737 SMGetRestart: // return here with revised Index.
738
739 #ifdef JUDYPREV
740 if (Index-- == 0) return(0);
741 #else
742 if (++Index == 0) return(0);
743 #endif
744
745 // An empty array with an in-bounds (not underflowed/overflowed) Index means
746 // success:
747 //
748 // Note: This check is redundant after restarting at SMGetRestart, but should
749 // take insignificant time.
750
751 if (PArray == (Pvoid_t) NULL) RET_SUCCESS;
752
753 // ----------------------------------------------------------------------------
754 // ROOT-LEVEL LEAF that starts with a Pop0 word; just look within the leaf:
755 //
756 // If Index is not in the leaf, return success; otherwise return the first
757 // empty Index, if any, below/above where it would belong.
758
759 if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
760 {
761 Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
762 pop0 = Pjlw[0];
763
764 #ifdef JUDY1
765 if (pop0 == 0) // special case.
766 {
767 #ifdef JUDYPREV
768 if ((Index != Pjlw[1]) || (Index-- != 0)) RET_SUCCESS;
769 #else
770 if ((Index != Pjlw[1]) || (++Index != 0)) RET_SUCCESS;
771 #endif
772 return(0); // no previous/next empty index.
773 }
774 #endif // JUDY1
775
776 j__udySearchLeafEmptyL(Pjlw + 1, pop0);
777
778 // No return -- thanks ALAN
779
780 }
781 else
782
783 // ----------------------------------------------------------------------------
784 // HANDLE JRP Branch:
785 //
786 // For JRP branches, traverse the JPM; handle LEAFW
787 // directly; but look for the most common cases first.
788
789 {
790 Pjpm_t Pjpm = P_JPM(PArray);
791 Pjp = &(Pjpm->jpm_JP);
792
793 // goto SMGetContinue;
794 }
795
796
797 // ============================================================================
798 // STATE MACHINE -- GET INDEX:
799 //
800 // Search for Index (already decremented/incremented so as to be an inclusive
801 // search). If not found (empty index), return success. Otherwise do a
802 // previous/next search, and if successful modify Index to the empty index
803 // found. See function header comments.
804 //
805 // ENTRY: Pjp points to next JP to interpret, whose Decode bytes have not yet
806 // been checked.
807 //
808 // Note: Check Decode bytes at the start of each loop, not after looking up a
809 // new JP, so its easy to do constant shifts/masks.
810 //
811 // EXIT: Return, or branch to SMGetRestart with modified Index, or branch to
812 // SMGetContinue with a modified Pjp, as described elsewhere.
813 //
814 // WARNING: For run-time efficiency the following cases replicate code with
815 // varying constants, rather than using common code with variable values!
816
817 SMGetContinue: // return here for next branch/leaf.
818
819 #ifdef TRACEJPSE
820 JudyPrintJP(Pjp, "sf", __LINE__);
821 #endif
822
823 switch (JU_JPTYPE(Pjp))
824 {
825
826
827 // ----------------------------------------------------------------------------
828 // LINEAR BRANCH:
829 //
830 // Check Decode bytes, if any, in the current JP, then search for a JP for the
831 // next digit in Index.
832
833 case cJU_JPBRANCH_L2: CHECKDCD(2); SMPREPB2(SMBranchL);
834 case cJU_JPBRANCH_L3: CHECKDCD(3); SMPREPB3(SMBranchL);
835 #ifdef JU_64BIT
836 case cJU_JPBRANCH_L4: CHECKDCD(4); SMPREPB4(SMBranchL);
837 case cJU_JPBRANCH_L5: CHECKDCD(5); SMPREPB5(SMBranchL);
838 case cJU_JPBRANCH_L6: CHECKDCD(6); SMPREPB6(SMBranchL);
839 case cJU_JPBRANCH_L7: CHECKDCD(7); SMPREPB7(SMBranchL);
840 #endif
841 case cJU_JPBRANCH_L: SMPREPBL(SMBranchL);
842
843 // Common code (state-independent) for all cases of linear branches:
844
845 SMBranchL:
846 Pjbl = P_JBL(Pjp->jp_Addr);
847
848 // First, check if Indexs expanse (digit) is below/above the first/last
849 // populated expanse in the BranchL, in which case Index is empty; otherwise
850 // find the offset of the lowest/highest populated expanse at or above/below
851 // digit, if any:
852 //
853 // Note: The for-loop is guaranteed to exit eventually because the first/last
854 // expanse is known to be a terminator.
855 //
856 // Note: Cannot use j__udySearchLeaf*Empty1() here because it only applies to
857 // leaves and does not know about partial versus full JPs, unlike the use of
858 // j__udySearchLeaf1() for BranchLs in SearchValid code. Also, since linear
859 // leaf expanse lists are small, dont waste time calling j__udySearchLeaf1(),
860 // just scan the expanse list.
861
862 #ifdef JUDYPREV
863 if ((Pjbl->jbl_Expanse[0]) > digit) RET_SUCCESS;
864
865 for (offset = (Pjbl->jbl_NumJPs) - 1; /* null */; --offset)
866 #else
867 if ((Pjbl->jbl_Expanse[(Pjbl->jbl_NumJPs) - 1]) < digit)
868 RET_SUCCESS;
869
870 for (offset = 0; /* null */; ++offset)
871 #endif
872 {
873
874 // Too low/high, keep going; or too high/low, meaning the loop passed a hole
875 // and the initial Index is empty:
876
877 #ifdef JUDYPREV
878 if ((Pjbl->jbl_Expanse[offset]) > digit) continue;
879 if ((Pjbl->jbl_Expanse[offset]) < digit) RET_SUCCESS;
880 #else
881 if ((Pjbl->jbl_Expanse[offset]) < digit) continue;
882 if ((Pjbl->jbl_Expanse[offset]) > digit) RET_SUCCESS;
883 #endif
884
885 // Found expanse matching digit; if its not full, traverse through it:
886
887 if (! JPFULL((Pjbl->jbl_jp) + offset))
888 {
889 Pjp = (Pjbl->jbl_jp) + offset;
890 goto SMGetContinue;
891 }
892
893 // Common code: While searching for a lower/higher hole or a non-full JP, upon
894 // finding a lower/higher hole, adjust Index using the revised digit and
895 // return; or upon finding a consecutive lower/higher expanse, if the expanses
896 // JP is non-full, modify Index and traverse through the JP:
897
898 #define BRANCHL_CHECK(OpIncDec,OpLeastDigits,Digit,Digits) \
899 { \
900 if ((Pjbl->jbl_Expanse[offset]) != OpIncDec digit) \
901 SET_AND_RETURN(OpLeastDigits, Digit, Digits); \
902 \
903 if (! JPFULL((Pjbl->jbl_jp) + offset)) \
904 { \
905 Pjp = (Pjbl->jbl_jp) + offset; \
906 SET_AND_CONTINUE(OpLeastDigits, Digit, Digits); \
907 } \
908 }
909
910 // BranchL primary dead end: Expanse matching Index/digit is full (rare except
911 // for dense/sequential indexes):
912 //
913 // Search for a lower/higher hole, a non-full JP, or the end of the expanse
914 // list, while decrementing/incrementing digit.
915
916 #ifdef JUDYPREV
917 while (--offset >= 0)
918 BRANCHL_CHECK(--, SETLEASTDIGITS_D, digit, digits)
919 #else
920 while (++offset < Pjbl->jbl_NumJPs)
921 BRANCHL_CHECK(++, CLEARLEASTDIGITS_D, digit, digits)
922 #endif
923
924 // Passed end of BranchL expanse list after finding a matching but full
925 // expanse:
926 //
927 // Digit now matches the lowest/highest expanse, which is a full expanse; if
928 // digit is at the end of BranchLs expanse (no hole before/after), break out
929 // of the loop; otherwise modify Index to the next lower/higher digit and
930 // return success:
931
932 #ifdef JUDYPREV
933 if (digit == 0) break;
934 --digit; SET_AND_RETURN(SETLEASTDIGITS_D, digit, digits);
935 #else
936 if (digit == JU_LEASTBYTES(cJU_ALLONES, 1)) break;
937 ++digit; SET_AND_RETURN(CLEARLEASTDIGITS_D, digit, digits);
938 #endif
939 } // for-loop
940
941 // BranchL secondary dead end, no non-full previous/next JP:
942
943 SMRESTART(digits);
944
945
946 // ----------------------------------------------------------------------------
947 // BITMAP BRANCH:
948 //
949 // Check Decode bytes, if any, in the current JP, then search for a JP for the
950 // next digit in Index.
951
952 case cJU_JPBRANCH_B2: CHECKDCD(2); SMPREPB2(SMBranchB);
953 case cJU_JPBRANCH_B3: CHECKDCD(3); SMPREPB3(SMBranchB);
954 #ifdef JU_64BIT
955 case cJU_JPBRANCH_B4: CHECKDCD(4); SMPREPB4(SMBranchB);
956 case cJU_JPBRANCH_B5: CHECKDCD(5); SMPREPB5(SMBranchB);
957 case cJU_JPBRANCH_B6: CHECKDCD(6); SMPREPB6(SMBranchB);
958 case cJU_JPBRANCH_B7: CHECKDCD(7); SMPREPB7(SMBranchB);
959 #endif
960 case cJU_JPBRANCH_B: SMPREPBL(SMBranchB);
961
962 // Common code (state-independent) for all cases of bitmap branches:
963
964 SMBranchB:
965 Pjbb = P_JBB(Pjp->jp_Addr);
966
967 // Locate the digits JP in the subexpanse list, if present:
968
969 subexp = digit / cJU_BITSPERSUBEXPB;
970 assert(subexp < cJU_NUMSUBEXPB); // falls in expected range.
971 bitposmaskB = JU_BITPOSMASKB(digit);
972
973 // Absent JP = no JP matches current digit in Index:
974
975 // if (! JU_BITMAPTESTB(Pjbb, digit)) // slower.
976 if (! (JU_JBB_BITMAP(Pjbb, subexp) & bitposmaskB)) // faster.
977 RET_SUCCESS;
978
979 // Non-full JP matches current digit in Index:
980 //
981 // Iterate to the subsidiary non-full JP.
982
983 offset = SEARCHBITMAPB(JU_JBB_BITMAP(Pjbb, subexp), digit,
984 bitposmaskB);
985 // not negative since at least one bit is set:
986 assert(offset >= 0);
987 assert(offset < (int) cJU_BITSPERSUBEXPB);
988
989 // Watch for null JP subarray pointer with non-null bitmap (a corruption):
990
991 if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp)))
992 == (Pjp_t) NULL) RET_CORRUPT;
993
994 Pjp += offset;
995 if (! JPFULL(Pjp)) goto SMGetContinue;
996
997 // BranchB primary dead end:
998 //
999 // Upon hitting a full JP in a BranchB for the next digit in Index, search
1000 // sideways for a previous/next absent JP (unset bit) or non-full JP (set bit
1001 // with non-full JP); first in the current bitmap subexpanse, then in
1002 // lower/higher subexpanses. Upon entry, Pjp points to a known-unusable JP,
1003 // ready to decrement/increment.
1004 //
1005 // Note: The preceding code is separate from this loop because Index does not
1006 // need revising (see SET_AND_*()) if the initial index is an empty index.
1007 //
1008 // TBD: For speed, shift bitposmaskB instead of using JU_BITMAPTESTB or
1009 // JU_BITPOSMASKB, but this shift has knowledge of bit order that really should
1010 // be encapsulated in a header file.
1011
1012 #define BRANCHB_CHECKBIT(OpLeastDigits) \
1013 if (! (JU_JBB_BITMAP(Pjbb, subexp) & bitposmaskB)) /* absent JP */ \
1014 SET_AND_RETURN(OpLeastDigits, digit, digits)
1015
1016 #define BRANCHB_CHECKJPFULL(OpLeastDigits) \
1017 if (! JPFULL(Pjp)) \
1018 SET_AND_CONTINUE(OpLeastDigits, digit, digits)
1019
1020 #define BRANCHB_STARTSUBEXP(OpLeastDigits) \
1021 if (! JU_JBB_BITMAP(Pjbb, subexp)) /* empty subexpanse, shortcut */ \
1022 SET_AND_RETURN(OpLeastDigits, digit, digits) \
1023 if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL) RET_CORRUPT
1024
1025 #ifdef JUDYPREV
1026
1027 --digit; // skip initial digit.
1028 bitposmaskB >>= 1; // see TBD above.
1029
1030 BranchBNextSubexp: // return here to check next bitmap subexpanse.
1031
1032 while (bitposmaskB) // more bits to check in subexp.
1033 {
1034 BRANCHB_CHECKBIT(SETLEASTDIGITS_D);
1035 --Pjp; // previous in subarray.
1036 BRANCHB_CHECKJPFULL(SETLEASTDIGITS_D);
1037 assert(digit >= 0);
1038 --digit;
1039 bitposmaskB >>= 1;
1040 }
1041
1042 if (subexp-- > 0) // more subexpanses.
1043 {
1044 BRANCHB_STARTSUBEXP(SETLEASTDIGITS_D);
1045 Pjp += SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp)) + 1;
1046 bitposmaskB = (1U << (cJU_BITSPERSUBEXPB - 1));
1047 goto BranchBNextSubexp;
1048 }
1049
1050 #else // JUDYNEXT
1051
1052 ++digit; // skip initial digit.
1053 bitposmaskB <<= 1; // note: BITMAPB_t.
1054
1055 BranchBNextSubexp: // return here to check next bitmap subexpanse.
1056
1057 while (bitposmaskB) // more bits to check in subexp.
1058 {
1059 BRANCHB_CHECKBIT(CLEARLEASTDIGITS_D);
1060 ++Pjp; // previous in subarray.
1061 BRANCHB_CHECKJPFULL(CLEARLEASTDIGITS_D);
1062 assert(digit < cJU_SUBEXPPERSTATE);
1063 ++digit;
1064 bitposmaskB <<= 1; // note: BITMAPB_t.
1065 }
1066
1067 if (++subexp < cJU_NUMSUBEXPB) // more subexpanses.
1068 {
1069 BRANCHB_STARTSUBEXP(CLEARLEASTDIGITS_D);
1070 --Pjp; // pre-decrement.
1071 bitposmaskB = 1;
1072 goto BranchBNextSubexp;
1073 }
1074
1075 #endif // JUDYNEXT
1076
1077 // BranchB secondary dead end, no non-full previous/next JP:
1078
1079 SMRESTART(digits);
1080
1081
1082 // ----------------------------------------------------------------------------
1083 // UNCOMPRESSED BRANCH:
1084 //
1085 // Check Decode bytes, if any, in the current JP, then search for a JP for the
1086 // next digit in Index.
1087
1088 case cJU_JPBRANCH_U2: CHECKDCD(2); SMPREPB2(SMBranchU);
1089 case cJU_JPBRANCH_U3: CHECKDCD(3); SMPREPB3(SMBranchU);
1090 #ifdef JU_64BIT
1091 case cJU_JPBRANCH_U4: CHECKDCD(4); SMPREPB4(SMBranchU);
1092 case cJU_JPBRANCH_U5: CHECKDCD(5); SMPREPB5(SMBranchU);
1093 case cJU_JPBRANCH_U6: CHECKDCD(6); SMPREPB6(SMBranchU);
1094 case cJU_JPBRANCH_U7: CHECKDCD(7); SMPREPB7(SMBranchU);
1095 #endif
1096 case cJU_JPBRANCH_U: SMPREPBL(SMBranchU);
1097
1098 // Common code (state-independent) for all cases of uncompressed branches:
1099
1100 SMBranchU:
1101 Pjbu = P_JBU(Pjp->jp_Addr);
1102 Pjp = (Pjbu->jbu_jp) + digit;
1103
1104 // Absent JP = null JP for current digit in Index:
1105
1106 if (JPNULL(JU_JPTYPE(Pjp))) RET_SUCCESS;
1107
1108 // Non-full JP matches current digit in Index:
1109 //
1110 // Iterate to the subsidiary JP.
1111
1112 if (! JPFULL(Pjp)) goto SMGetContinue;
1113
1114 // BranchU primary dead end:
1115 //
1116 // Upon hitting a full JP in a BranchU for the next digit in Index, search
1117 // sideways for a previous/next null or non-full JP. BRANCHU_CHECKJP() is
1118 // shorthand for common code.
1119 //
1120 // Note: The preceding code is separate from this loop because Index does not
1121 // need revising (see SET_AND_*()) if the initial index is an empty index.
1122
1123 #define BRANCHU_CHECKJP(OpIncDec,OpLeastDigits) \
1124 { \
1125 OpIncDec Pjp; \
1126 \
1127 if (JPNULL(JU_JPTYPE(Pjp))) \
1128 SET_AND_RETURN(OpLeastDigits, digit, digits) \
1129 \
1130 if (! JPFULL(Pjp)) \
1131 SET_AND_CONTINUE(OpLeastDigits, digit, digits) \
1132 }
1133
1134 #ifdef JUDYPREV
1135 while (digit-- > 0)
1136 BRANCHU_CHECKJP(--, SETLEASTDIGITS_D);
1137 #else
1138 while (++digit < cJU_BRANCHUNUMJPS)
1139 BRANCHU_CHECKJP(++, CLEARLEASTDIGITS_D);
1140 #endif
1141
1142 // BranchU secondary dead end, no non-full previous/next JP:
1143
1144 SMRESTART(digits);
1145
1146
1147 // ----------------------------------------------------------------------------
1148 // LINEAR LEAF:
1149 //
1150 // Check Decode bytes, if any, in the current JP, then search the leaf for the
1151 // previous/next empty index starting at Index. Primary leaf dead end is
1152 // hidden within j__udySearchLeaf*Empty*(). In case of secondary leaf dead
1153 // end, restart at the top of the tree.
1154 //
1155 // Note: Pword is the name known to GET*; think of it as Pjlw.
1156
1157 #define SMLEAFL(cDigits,Func) \
1158 Pword = (PWord_t) P_JLW(Pjp->jp_Addr); \
1159 pop0 = JU_JPLEAF_POP0(Pjp); \
1160 Func(Pword, pop0)
1161
1162 #if (defined(JUDYL) || (! defined(JU_64BIT)))
1163 case cJU_JPLEAF1: CHECKDCD(1); SMLEAFL(1, j__udySearchLeafEmpty1);
1164 #endif
1165 case cJU_JPLEAF2: CHECKDCD(2); SMLEAFL(2, j__udySearchLeafEmpty2);
1166 case cJU_JPLEAF3: CHECKDCD(3); SMLEAFL(3, j__udySearchLeafEmpty3);
1167
1168 #ifdef JU_64BIT
1169 case cJU_JPLEAF4: CHECKDCD(4); SMLEAFL(4, j__udySearchLeafEmpty4);
1170 case cJU_JPLEAF5: CHECKDCD(5); SMLEAFL(5, j__udySearchLeafEmpty5);
1171 case cJU_JPLEAF6: CHECKDCD(6); SMLEAFL(6, j__udySearchLeafEmpty6);
1172 case cJU_JPLEAF7: CHECKDCD(7); SMLEAFL(7, j__udySearchLeafEmpty7);
1173 #endif
1174
1175
1176 // ----------------------------------------------------------------------------
1177 // BITMAP LEAF:
1178 //
1179 // Check Decode bytes, if any, in the current JP, then search the leaf for the
1180 // previous/next empty index starting at Index.
1181
1182 case cJU_JPLEAF_B1:
1183
1184 CHECKDCD(1);
1185
1186 Pjlb = P_JLB(Pjp->jp_Addr);
1187 digit = JU_DIGITATSTATE(Index, 1);
1188 subexp = digit / cJU_BITSPERSUBEXPL;
1189 bitposmaskL = JU_BITPOSMASKL(digit);
1190 assert(subexp < cJU_NUMSUBEXPL); // falls in expected range.
1191
1192 // Absent index = no index matches current digit in Index:
1193
1194 // if (! JU_BITMAPTESTL(Pjlb, digit)) // slower.
1195 if (! (JU_JLB_BITMAP(Pjlb, subexp) & bitposmaskL)) // faster.
1196 RET_SUCCESS;
1197
1198 // LeafB1 primary dead end:
1199 //
1200 // Upon hitting a valid (non-empty) index in a LeafB1 for the last digit in
1201 // Index, search sideways for a previous/next absent index, first in the
1202 // current bitmap subexpanse, then in lower/higher subexpanses.
1203 // LEAFB1_CHECKBIT() is shorthand for common code to handle one bit in one
1204 // bitmap subexpanse.
1205 //
1206 // Note: The preceding code is separate from this loop because Index does not
1207 // need revising (see SET_AND_*()) if the initial index is an empty index.
1208 //
1209 // TBD: For speed, shift bitposmaskL instead of using JU_BITMAPTESTL or
1210 // JU_BITPOSMASKL, but this shift has knowledge of bit order that really should
1211 // be encapsulated in a header file.
1212
1213 #define LEAFB1_CHECKBIT(OpLeastDigits) \
1214 if (! (JU_JLB_BITMAP(Pjlb, subexp) & bitposmaskL)) \
1215 SET_AND_RETURN(OpLeastDigits, digit, 1)
1216
1217 #define LEAFB1_STARTSUBEXP(OpLeastDigits) \
1218 if (! JU_JLB_BITMAP(Pjlb, subexp)) /* empty subexp */ \
1219 SET_AND_RETURN(OpLeastDigits, digit, 1)
1220
1221 #ifdef JUDYPREV
1222
1223 --digit; // skip initial digit.
1224 bitposmaskL >>= 1; // see TBD above.
1225
1226 LeafB1NextSubexp: // return here to check next bitmap subexpanse.
1227
1228 while (bitposmaskL) // more bits to check in subexp.
1229 {
1230 LEAFB1_CHECKBIT(SETLEASTDIGITS_D);
1231 assert(digit >= 0);
1232 --digit;
1233 bitposmaskL >>= 1;
1234 }
1235
1236 if (subexp-- > 0) // more subexpanses.
1237 {
1238 LEAFB1_STARTSUBEXP(SETLEASTDIGITS_D);
1239 bitposmaskL = ((Word_t)1U << (cJU_BITSPERSUBEXPL - 1));
1240 goto LeafB1NextSubexp;
1241 }
1242
1243 #else // JUDYNEXT
1244
1245 ++digit; // skip initial digit.
1246 bitposmaskL <<= 1; // note: BITMAPL_t.
1247
1248 LeafB1NextSubexp: // return here to check next bitmap subexpanse.
1249
1250 while (bitposmaskL) // more bits to check in subexp.
1251 {
1252 LEAFB1_CHECKBIT(CLEARLEASTDIGITS_D);
1253 assert(digit < cJU_SUBEXPPERSTATE);
1254 ++digit;
1255 bitposmaskL <<= 1; // note: BITMAPL_t.
1256 }
1257
1258 if (++subexp < cJU_NUMSUBEXPL) // more subexpanses.
1259 {
1260 LEAFB1_STARTSUBEXP(CLEARLEASTDIGITS_D);
1261 bitposmaskL = 1;
1262 goto LeafB1NextSubexp;
1263 }
1264
1265 #endif // JUDYNEXT
1266
1267 // LeafB1 secondary dead end, no empty index:
1268
1269 SMRESTART(1);
1270
1271
1272 #ifdef JUDY1
1273 // ----------------------------------------------------------------------------
1274 // FULL POPULATION:
1275 //
1276 // If the Decode bytes do not match, Index is empty (without modification);
1277 // otherwise restart.
1278
1279 case cJ1_JPFULLPOPU1:
1280
1281 CHECKDCD(1);
1282 SMRESTART(1);
1283 #endif
1284
1285
1286 // ----------------------------------------------------------------------------
1287 // IMMEDIATE:
1288 //
1289 // Pop1 = 1 Immediate JPs:
1290 //
1291 // If Index is not in the immediate JP, return success; otherwise check if
1292 // there is an empty index below/above the immediate JPs index, and if so,
1293 // return success with modified Index, else restart.
1294 //
1295 // Note: Doug says its fast enough to calculate the index size (digits) in
1296 // the following; no need to set it separately for each case.
1297
1298 case cJU_JPIMMED_1_01:
1299 case cJU_JPIMMED_2_01:
1300 case cJU_JPIMMED_3_01:
1301 #ifdef JU_64BIT
1302 case cJU_JPIMMED_4_01:
1303 case cJU_JPIMMED_5_01:
1304 case cJU_JPIMMED_6_01:
1305 case cJU_JPIMMED_7_01:
1306 #endif
1307 if (JU_JPDCDPOP0(Pjp) != JU_TRIMTODCDSIZE(Index)) RET_SUCCESS;
1308 digits = JU_JPTYPE(Pjp) - cJU_JPIMMED_1_01 + 1;
1309 LEAF_EDGE(JU_LEASTBYTES(JU_JPDCDPOP0(Pjp), digits), digits);
1310
1311 // Immediate JPs with Pop1 > 1:
1312
1313 #define IMM_MULTI(Func,BaseJPType) \
1314 JUDY1CODE(Pword = (PWord_t) (Pjp->jp_1Index);) \
1315 JUDYLCODE(Pword = (PWord_t) (Pjp->jp_LIndex);) \
1316 Func(Pword, JU_JPTYPE(Pjp) - (BaseJPType) + 1)
1317
1318 case cJU_JPIMMED_1_02:
1319 case cJU_JPIMMED_1_03:
1320 #if (defined(JUDY1) || defined(JU_64BIT))
1321 case cJU_JPIMMED_1_04:
1322 case cJU_JPIMMED_1_05:
1323 case cJU_JPIMMED_1_06:
1324 case cJU_JPIMMED_1_07:
1325 #endif
1326 #if (defined(JUDY1) && defined(JU_64BIT))
1327 case cJ1_JPIMMED_1_08:
1328 case cJ1_JPIMMED_1_09:
1329 case cJ1_JPIMMED_1_10:
1330 case cJ1_JPIMMED_1_11:
1331 case cJ1_JPIMMED_1_12:
1332 case cJ1_JPIMMED_1_13:
1333 case cJ1_JPIMMED_1_14:
1334 case cJ1_JPIMMED_1_15:
1335 #endif
1336 IMM_MULTI(j__udySearchLeafEmpty1, cJU_JPIMMED_1_02);
1337
1338 #if (defined(JUDY1) || defined(JU_64BIT))
1339 case cJU_JPIMMED_2_02:
1340 case cJU_JPIMMED_2_03:
1341 #endif
1342 #if (defined(JUDY1) && defined(JU_64BIT))
1343 case cJ1_JPIMMED_2_04:
1344 case cJ1_JPIMMED_2_05:
1345 case cJ1_JPIMMED_2_06:
1346 case cJ1_JPIMMED_2_07:
1347 #endif
1348 #if (defined(JUDY1) || defined(JU_64BIT))
1349 IMM_MULTI(j__udySearchLeafEmpty2, cJU_JPIMMED_2_02);
1350 #endif
1351
1352 #if (defined(JUDY1) || defined(JU_64BIT))
1353 case cJU_JPIMMED_3_02:
1354 #endif
1355 #if (defined(JUDY1) && defined(JU_64BIT))
1356 case cJ1_JPIMMED_3_03:
1357 case cJ1_JPIMMED_3_04:
1358 case cJ1_JPIMMED_3_05:
1359 #endif
1360 #if (defined(JUDY1) || defined(JU_64BIT))
1361 IMM_MULTI(j__udySearchLeafEmpty3, cJU_JPIMMED_3_02);
1362 #endif
1363
1364 #if (defined(JUDY1) && defined(JU_64BIT))
1365 case cJ1_JPIMMED_4_02:
1366 case cJ1_JPIMMED_4_03:
1367 IMM_MULTI(j__udySearchLeafEmpty4, cJ1_JPIMMED_4_02);
1368
1369 case cJ1_JPIMMED_5_02:
1370 case cJ1_JPIMMED_5_03:
1371 IMM_MULTI(j__udySearchLeafEmpty5, cJ1_JPIMMED_5_02);
1372
1373 case cJ1_JPIMMED_6_02:
1374 IMM_MULTI(j__udySearchLeafEmpty6, cJ1_JPIMMED_6_02);
1375
1376 case cJ1_JPIMMED_7_02:
1377 IMM_MULTI(j__udySearchLeafEmpty7, cJ1_JPIMMED_7_02);
1378 #endif
1379
1380
1381 // ----------------------------------------------------------------------------
1382 // INVALID JP TYPE:
1383
1384 default: RET_CORRUPT;
1385
1386 } // SMGet switch.
1387
1388 } // Judy1PrevEmpty() / Judy1NextEmpty() / JudyLPrevEmpty() / JudyLNextEmpty()
1389