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