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