summaryrefslogtreecommitdiffstats
path: root/libnetdata/libjudy/src/JudyL/JudyLNext.c
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLNext.c')
-rw-r--r--libnetdata/libjudy/src/JudyL/JudyLNext.c1890
1 files changed, 0 insertions, 1890 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLNext.c b/libnetdata/libjudy/src/JudyL/JudyLNext.c
deleted file mode 100644
index 4bcdccf10..000000000
--- a/libnetdata/libjudy/src/JudyL/JudyLNext.c
+++ /dev/null
@@ -1,1890 +0,0 @@
-// Copyright (C) 2000 - 2002 Hewlett-Packard Company
-//
-// This program is free software; you can redistribute it and/or modify it
-// under the term of the GNU Lesser General Public License as published by the
-// Free Software Foundation; either version 2 of the License, or (at your
-// option) any later version.
-//
-// This program is distributed in the hope that it will be useful, but WITHOUT
-// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
-// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
-// for more details.
-//
-// You should have received a copy of the GNU Lesser General Public License
-// along with this program; if not, write to the Free Software Foundation,
-// Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-// _________________
-
-// @(#) $Revision: 4.54 $ $Source: /judy/src/JudyCommon/JudyPrevNext.c $
-//
-// Judy*Prev() and Judy*Next() functions for Judy1 and JudyL.
-// Compile with one of -DJUDY1 or -DJUDYL.
-//
-// Compile with -DJUDYNEXT for the Judy*Next() function; otherwise defaults to
-// Judy*Prev().
-
-#if (! (defined(JUDY1) || defined(JUDYL)))
-#error: One of -DJUDY1 or -DJUDYL must be specified.
-#endif
-
-#ifndef JUDYNEXT
-#ifndef JUDYPREV
-#define JUDYPREV 1 // neither set => use default.
-#endif
-#endif
-
-#ifdef JUDY1
-#include "Judy1.h"
-#else
-#include "JudyL.h"
-#endif
-
-#include "JudyPrivate1L.h"
-
-
-// ****************************************************************************
-// J U D Y 1 P R E V
-// J U D Y 1 N E X T
-// J U D Y L P R E V
-// J U D Y L N E X T
-//
-// See the manual entry for the API.
-//
-// OVERVIEW OF Judy*Prev():
-//
-// Use a reentrant switch statement (state machine, SM1 = "get") to decode the
-// callers *PIndex-1, starting with the (PArray), through branches, if
-// any, down to an immediate or a leaf. Look for *PIndex-1 in that leaf, and
-// if found, return it.
-//
-// A dead end is either a branch that does not contain a JP for the appropriate
-// digit in *PIndex-1, or a leaf that does not contain the undecoded digits of
-// *PIndex-1. Upon reaching a dead end, backtrack through the leaf/branches
-// that were just traversed, using a list (history) of parent JPs that is built
-// while going forward in SM1Get. Start with the current leaf or branch. In a
-// backtracked leaf, look for an Index less than *PIndex-1. In each
-// backtracked branch, look "sideways" for the next JP, if any, lower than the
-// one for the digit (from *PIndex-1) that was previously decoded. While
-// backtracking, if a leaf has no previous Index or a branch has no lower JP,
-// go to its parent branch in turn. Upon reaching the JRP, return failure, "no
-// previous Index". The backtrack process is sufficiently different from
-// SM1Get to merit its own separate reentrant switch statement (SM2 =
-// "backtrack").
-//
-// While backtracking, upon finding a lower JP in a branch, there is certain to
-// be a "prev" Index under that JP (unless the Judy array is corrupt).
-// Traverse forward again, this time taking the last (highest, right-most) JP
-// in each branch, and the last (highest) Index upon reaching an immediate or a
-// leaf. This traversal is sufficiently different from SM1Get and SM2Backtrack
-// to merit its own separate reentrant switch statement (SM3 = "findlimit").
-//
-// "Decode" bytes in JPs complicate this process a little. In SM1Get, when a
-// JP is a narrow pointer, that is, when states are skipped (so the skipped
-// digits are stored in jp_DcdPopO), compare the relevant digits to the same
-// digits in *PIndex-1. If they are EQUAL, proceed in SM1Get as before. If
-// jp_DcdPopOs digits are GREATER, treat the JP as a dead end and proceed in
-// SM2Backtrack. If jp_DcdPopOs digits are LESS, treat the JP as if it had
-// just been found during a backtrack and proceed directly in SM3Findlimit.
-//
-// Note that Decode bytes can be ignored in SM3Findlimit; they dont matter.
-// Also note that in practice the Decode bytes are routinely compared with
-// *PIndex-1 because thats simpler and no slower than first testing for
-// narrowness.
-//
-// Decode bytes also make it unnecessary to construct the Index to return (the
-// revised *PIndex) during the search. This step is deferred until finding an
-// Index during backtrack or findlimit, before returning it. The first digit
-// of *PIndex is derived (saved) based on which JP is used in a JRP branch.
-// The remaining digits are obtained from the jp_DcdPopO field in the JP (if
-// any) above the immediate or leaf containing the found (prev) Index, plus the
-// remaining digit(s) in the immediate or leaf itself. In the case of a LEAFW,
-// the Index to return is found directly in the leaf.
-//
-// Note: Theoretically, as described above, upon reaching a dead end, SM1Get
-// passes control to SM2Backtrack to look sideways, even in a leaf. Actually
-// its a little more efficient for the SM1Get leaf cases to shortcut this and
-// take care of the sideways searches themselves. Hence the history list only
-// contains branch JPs, and SM2Backtrack only handles branches. In fact, even
-// the branch handling cases in SM1Get do some shortcutting (sideways
-// searching) to avoid pushing history and calling SM2Backtrack unnecessarily.
-//
-// Upon reaching an Index to return after backtracking, *PIndex must be
-// modified to the found Index. In principle this could be done by building
-// the Index from a saved rootdigit (in the top branch) plus the Dcd bytes from
-// the parent JP plus the appropriate Index bytes from the leaf. However,
-// Immediates are difficult because their parent JPs lack one (last) digit. So
-// instead just build the *PIndex to return "top down" while backtracking and
-// findlimiting.
-//
-// This function is written iteratively for speed, rather than recursively.
-//
-// CAVEATS:
-//
-// Why use a backtrack list (history stack), since it has finite size? The
-// size is small for Judy on both 32-bit and 64-bit systems, and a list (really
-// just an array) is fast to maintain and use. Other alternatives include
-// doing a lookahead (lookaside) in each branch while traversing forward
-// (decoding), and restarting from the top upon a dead end.
-//
-// A lookahead means noting the last branch traversed which contained a
-// non-null JP lower than the one specified by a digit in *PIndex-1, and
-// returning to that point for SM3Findlimit. This seems like a good idea, and
-// should be pretty cheap for linear and bitmap branches, but it could result
-// in up to 31 unnecessary additional cache line fills (in extreme cases) for
-// every uncompressed branch traversed. We have considered means of attaching
-// to or hiding within an uncompressed branch (in null JPs) a "cache line map"
-// or other structure, such as an offset to the next non-null JP, that would
-// speed this up, but it seems unnecessary merely to avoid having a
-// finite-length list (array). (If JudySL is ever made "native", the finite
-// list length will be an issue.)
-//
-// Restarting at the top of the Judy array after a dead end requires a careful
-// modification of *PIndex-1 to decrement the digit for the parent branch and
-// set the remaining lower digits to all 1s. This must be repeated each time a
-// parent branch contains another dead end, so even though it should all happen
-// in cache, the CPU time can be excessive. (For JudySL or an equivalent
-// "infinitely deep" Judy array, consider a hybrid of a large, finite,
-// "circular" list and a restart-at-top when the list is backtracked to
-// exhaustion.)
-//
-// Why search for *PIndex-1 instead of *PIndex during SM1Get? In rare
-// instances this prevents an unnecessary decode down the wrong path followed
-// by a backtrack; its pretty cheap to set up initially; and it means the
-// SM1Get machine can simply return if/when it finds that Index.
-//
-// TBD: Wed like to enhance this function to make successive searches faster.
-// This would require saving some previous state, including the previous Index
-// returned, and in which leaf it was found. If the next call is for the same
-// Index and the array has not been modified, start at the same leaf. This
-// should be much easier to implement since this is iterative rather than
-// recursive code.
-//
-// VARIATIONS FOR Judy*Next():
-//
-// The Judy*Next() code is nearly a perfect mirror of the Judy*Prev() code.
-// See the Judy*Prev() overview comments, and mentally switch the following:
-//
-// - "*PIndex-1" => "*PIndex+1"
-// - "less than" => "greater than"
-// - "lower" => "higher"
-// - "lowest" => "highest"
-// - "next-left" => "next-right"
-// - "right-most" => "left-most"
-//
-// Note: SM3Findlimit could be called SM3Findmax/SM3Findmin, but a common name
-// for both Prev and Next means many fewer ifdefs in this code.
-//
-// TBD: Currently this code traverses a JP whether its expanse is partially or
-// completely full (populated). For Judy1 (only), since there is no value area
-// needed, consider shortcutting to a "success" return upon encountering a full
-// JP in SM1Get (or even SM3Findlimit?) A full JP looks like this:
-//
-// (((JU_JPDCDPOP0(Pjp) ^ cJU_ALLONES) & cJU_POP0MASK(cLevel)) == 0)
-
-#ifdef JUDY1
-#ifdef JUDYPREV
-FUNCTION int Judy1Prev
-#else
-FUNCTION int Judy1Next
-#endif
-#else
-#ifdef JUDYPREV
-FUNCTION PPvoid_t JudyLPrev
-#else
-FUNCTION PPvoid_t JudyLNext
-#endif
-#endif
- (
- Pcvoid_t PArray, // Judy array to search.
- Word_t * PIndex, // starting point and result.
- PJError_t PJError // optional, for returning error info.
- )
-{
- Pjp_t Pjp, Pjp2; // current JPs.
- Pjbl_t Pjbl; // Pjp->jp_Addr masked and cast to types:
- Pjbb_t Pjbb;
- Pjbu_t Pjbu;
-
-// Note: The following initialization is not strictly required but it makes
-// gcc -Wall happy because there is an "impossible" path from Immed handling to
-// SM1LeafLImm code that looks like Pjll might be used before set:
-
- Pjll_t Pjll = (Pjll_t) NULL;
- Word_t state; // current state in SM.
- Word_t digit; // next digit to decode from Index.
-
-// Note: The following initialization is not strictly required but it makes
-// gcc -Wall happy because there is an "impossible" path from Immed handling to
-// SM1LeafLImm code (for JudyL & JudyPrev only) that looks like pop1 might be
-// used before set:
-
-#if (defined(JUDYL) && defined(JUDYPREV))
- Word_t pop1 = 0; // in a leaf.
-#else
- Word_t pop1; // in a leaf.
-#endif
- int offset; // linear branch/leaf, from j__udySearchLeaf*().
- int subexp; // subexpanse in a bitmap branch.
- Word_t bitposmask; // bit in bitmap for Index.
-
-// History for SM2Backtrack:
-//
-// For a given histnum, APjphist[histnum] is a parent JP that points to a
-// branch, and Aoffhist[histnum] is the offset of the NEXT JP in the branch to
-// which the parent JP points. The meaning of Aoffhist[histnum] depends on the
-// type of branch to which the parent JP points:
-//
-// Linear: Offset of the next JP in the JP list.
-//
-// Bitmap: Which subexpanse, plus the offset of the next JP in the
-// subexpanses JP list (to avoid bit-counting again), plus for Judy*Next(),
-// hidden one byte to the left, which digit, because Judy*Next() also needs
-// this.
-//
-// Uncompressed: Digit, which is actually the offset of the JP in the branch.
-//
-// Note: Only branch JPs are stored in APjphist[] because, as explained
-// earlier, SM1Get shortcuts sideways searches in leaves (and even in branches
-// in some cases), so SM2Backtrack only handles branches.
-
-#define HISTNUMMAX cJU_ROOTSTATE // maximum branches traversable.
- Pjp_t APjphist[HISTNUMMAX]; // list of branch JPs traversed.
- int Aoffhist[HISTNUMMAX]; // list of next JP offsets; see above.
- int histnum = 0; // number of JPs now in list.
-
-
-// ----------------------------------------------------------------------------
-// M A C R O S
-//
-// These are intended to make the code a bit more readable and less redundant.
-
-
-// "PUSH" AND "POP" Pjp AND offset ON HISTORY STACKS:
-//
-// Note: Ensure a corrupt Judy array does not overflow *hist[]. Meanwhile,
-// underflowing *hist[] simply means theres no more room to backtrack =>
-// "no previous/next Index".
-
-#define HISTPUSH(Pjp,Offset) \
- APjphist[histnum] = (Pjp); \
- Aoffhist[histnum] = (Offset); \
- \
- if (++histnum >= HISTNUMMAX) \
- { \
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT) \
- JUDY1CODE(return(JERRI );) \
- JUDYLCODE(return(PPJERR);) \
- }
-
-#define HISTPOP(Pjp,Offset) \
- if ((histnum--) < 1) JU_RET_NOTFOUND; \
- (Pjp) = APjphist[histnum]; \
- (Offset) = Aoffhist[histnum]
-
-// How to pack/unpack Aoffhist[] values for bitmap branches:
-
-#ifdef JUDYPREV
-
-#define HISTPUSHBOFF(Subexp,Offset,Digit) \
- (((Subexp) * cJU_BITSPERSUBEXPB) | (Offset))
-
-#define HISTPOPBOFF(Subexp,Offset,Digit) \
- (Subexp) = (Offset) / cJU_BITSPERSUBEXPB; \
- (Offset) %= cJU_BITSPERSUBEXPB
-#else
-
-#define HISTPUSHBOFF(Subexp,Offset,Digit) \
- (((Digit) << cJU_BITSPERBYTE) \
- | ((Subexp) * cJU_BITSPERSUBEXPB) | (Offset))
-
-#define HISTPOPBOFF(Subexp,Offset,Digit) \
- (Digit) = (Offset) >> cJU_BITSPERBYTE; \
- (Subexp) = ((Offset) & JU_LEASTBYTESMASK(1)) / cJU_BITSPERSUBEXPB; \
- (Offset) %= cJU_BITSPERSUBEXPB
-#endif
-
-
-// CHECK FOR NULL JP:
-
-#define JPNULL(Type) (((Type) >= cJU_JPNULL1) && ((Type) <= cJU_JPNULLMAX))
-
-
-// SEARCH A BITMAP:
-//
-// This is a weak analog of j__udySearchLeaf*() for bitmaps. Return the actual
-// or next-left position, base 0, of Digit in the single uint32_t bitmap, also
-// given a Bitposmask for Digit.
-//
-// Unlike j__udySearchLeaf*(), the offset is not returned bit-complemented if
-// Digits bit is unset, because the caller can check the bitmap themselves to
-// determine that. Also, if Digits bit is unset, the returned offset is to
-// the next-left JP (including -1), not to the "ideal" position for the Index =
-// next-right JP.
-//
-// Shortcut and skip calling j__udyCountBits*() if the bitmap is full, in which
-// case (Digit % cJU_BITSPERSUBEXP*) itself is the base-0 offset.
-//
-// TBD for Judy*Next(): Should this return next-right instead of next-left?
-// That is, +1 from current value? Maybe not, if Digits bit IS set, +1 would
-// be wrong.
-
-#define SEARCHBITMAPB(Bitmap,Digit,Bitposmask) \
- (((Bitmap) == cJU_FULLBITMAPB) ? (Digit % cJU_BITSPERSUBEXPB) : \
- j__udyCountBitsB((Bitmap) & JU_MASKLOWERINC(Bitposmask)) - 1)
-
-#define SEARCHBITMAPL(Bitmap,Digit,Bitposmask) \
- (((Bitmap) == cJU_FULLBITMAPL) ? (Digit % cJU_BITSPERSUBEXPL) : \
- j__udyCountBitsL((Bitmap) & JU_MASKLOWERINC(Bitposmask)) - 1)
-
-#ifdef JUDYPREV
-// Equivalent to search for the highest offset in Bitmap:
-
-#define SEARCHBITMAPMAXB(Bitmap) \
- (((Bitmap) == cJU_FULLBITMAPB) ? cJU_BITSPERSUBEXPB - 1 : \
- j__udyCountBitsB(Bitmap) - 1)
-
-#define SEARCHBITMAPMAXL(Bitmap) \
- (((Bitmap) == cJU_FULLBITMAPL) ? cJU_BITSPERSUBEXPL - 1 : \
- j__udyCountBitsL(Bitmap) - 1)
-#endif
-
-
-// CHECK DECODE BYTES:
-//
-// Check Decode bytes in a JP against the equivalent portion of *PIndex. If
-// *PIndex is lower (for Judy*Prev()) or higher (for Judy*Next()), this JP is a
-// dead end (the same as if it had been absent in a linear or bitmap branch or
-// null in an uncompressed branch), enter SM2Backtrack; otherwise enter
-// SM3Findlimit to find the highest/lowest Index under this JP, as if the code
-// had already backtracked to this JP.
-
-#ifdef JUDYPREV
-#define CDcmp__ <
-#else
-#define CDcmp__ >
-#endif
-
-#define CHECKDCD(cState) \
- if (JU_DCDNOTMATCHINDEX(*PIndex, Pjp, cState)) \
- { \
- if ((*PIndex & cJU_DCDMASK(cState)) \
- CDcmp__(JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(cState))) \
- { \
- goto SM2Backtrack; \
- } \
- goto SM3Findlimit; \
- }
-
-
-// PREPARE TO HANDLE A LEAFW OR JRP BRANCH IN SM1:
-//
-// Extract a state-dependent digit from Index in a "constant" way, then jump to
-// common code for multiple cases.
-
-#define SM1PREPB(cState,Next) \
- state = (cState); \
- digit = JU_DIGITATSTATE(*PIndex, cState); \
- goto Next
-
-
-// PREPARE TO HANDLE A LEAFW OR JRP BRANCH IN SM3:
-//
-// Optionally save Dcd bytes into *PIndex, then save state and jump to common
-// code for multiple cases.
-
-#define SM3PREPB_DCD(cState,Next) \
- JU_SETDCD(*PIndex, Pjp, cState); \
- SM3PREPB(cState,Next)
-
-#define SM3PREPB(cState,Next) state = (cState); goto Next
-
-
-// ----------------------------------------------------------------------------
-// CHECK FOR SHORTCUTS:
-//
-// Error out if PIndex is null. Execute JU_RET_NOTFOUND if the Judy array is
-// empty or *PIndex is already the minimum/maximum Index possible.
-//
-// Note: As documented, in case of failure *PIndex may be modified.
-
- if (PIndex == (PWord_t) NULL)
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
-
-#ifdef JUDYPREV
- if ((PArray == (Pvoid_t) NULL) || ((*PIndex)-- == 0))
-#else
- if ((PArray == (Pvoid_t) NULL) || ((*PIndex)++ == cJU_ALLONES))
-#endif
- JU_RET_NOTFOUND;
-
-
-// HANDLE JRP:
-//
-// Before even entering SM1Get, check the JRP type. For JRP branches, traverse
-// the JPM; handle LEAFW leaves directly; but look for the most common cases
-// first.
-
-// ROOT-STATE LEAF that starts with a Pop0 word; just look within the leaf:
-//
-// If *PIndex is in the leaf, return it; otherwise return the Index, if any,
-// below where it would belong.
-
- if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
- {
- Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
- pop1 = Pjlw[0] + 1;
-
- if ((offset = j__udySearchLeafW(Pjlw + 1, pop1, *PIndex))
- >= 0) // Index is present.
- {
- assert(offset < pop1); // in expected range.
- JU_RET_FOUND_LEAFW(Pjlw, pop1, offset); // *PIndex is set.
- }
-
-#ifdef JUDYPREV
- if ((offset = ~offset) == 0) // no next-left Index.
-#else
- if ((offset = ~offset) >= pop1) // no next-right Index.
-#endif
- JU_RET_NOTFOUND;
-
- assert(offset <= pop1); // valid result.
-
-#ifdef JUDYPREV
- *PIndex = Pjlw[offset--]; // next-left Index, base 1.
-#else
- *PIndex = Pjlw[offset + 1]; // next-right Index, base 1.
-#endif
- JU_RET_FOUND_LEAFW(Pjlw, pop1, offset); // base 0.
-
- }
- else // JRP BRANCH
- {
- Pjpm_t Pjpm = P_JPM(PArray);
- Pjp = &(Pjpm->jpm_JP);
-
-// goto SM1Get;
- }
-
-// ============================================================================
-// STATE MACHINE 1 -- GET INDEX:
-//
-// Search for *PIndex (already decremented/incremented so as to be inclusive).
-// If found, return it. Otherwise in theory hand off to SM2Backtrack or
-// SM3Findlimit, but in practice "shortcut" by first sideways searching the
-// current branch or leaf upon hitting a dead end. During sideways search,
-// modify *PIndex to a new path taken.
-//
-// ENTRY: Pjp points to next JP to interpret, whose Decode bytes have not yet
-// been checked. This JP is not yet listed in history.
-//
-// Note: Check Decode bytes at the start of each loop, not after looking up a
-// new JP, so its easy to do constant shifts/masks, although this requires
-// cautious handling of Pjp, offset, and *hist[] for correct entry to
-// SM2Backtrack.
-//
-// EXIT: Return, or branch to SM2Backtrack or SM3Findlimit with correct
-// interface, as described elsewhere.
-//
-// WARNING: For run-time efficiency the following cases replicate code with
-// varying constants, rather than using common code with variable values!
-
-SM1Get: // return here for next branch/leaf.
-
- switch (JU_JPTYPE(Pjp))
- {
-
-
-// ----------------------------------------------------------------------------
-// LINEAR BRANCH:
-//
-// Check Decode bytes, if any, in the current JP, then search for a JP for the
-// next digit in *PIndex.
-
- case cJU_JPBRANCH_L2: CHECKDCD(2); SM1PREPB(2, SM1BranchL);
- case cJU_JPBRANCH_L3: CHECKDCD(3); SM1PREPB(3, SM1BranchL);
-#ifdef JU_64BIT
- case cJU_JPBRANCH_L4: CHECKDCD(4); SM1PREPB(4, SM1BranchL);
- case cJU_JPBRANCH_L5: CHECKDCD(5); SM1PREPB(5, SM1BranchL);
- case cJU_JPBRANCH_L6: CHECKDCD(6); SM1PREPB(6, SM1BranchL);
- case cJU_JPBRANCH_L7: CHECKDCD(7); SM1PREPB(7, SM1BranchL);
-#endif
- case cJU_JPBRANCH_L: SM1PREPB(cJU_ROOTSTATE, SM1BranchL);
-
-// Common code (state-independent) for all cases of linear branches:
-
-SM1BranchL:
- Pjbl = P_JBL(Pjp->jp_Addr);
-
-// Found JP matching current digit in *PIndex; record parent JP and the next
-// JPs offset, and iterate to the next JP:
-
- if ((offset = j__udySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse),
- Pjbl->jbl_NumJPs, digit)) >= 0)
- {
- HISTPUSH(Pjp, offset);
- Pjp = (Pjbl->jbl_jp) + offset;
- goto SM1Get;
- }
-
-// Dead end, no JP in BranchL for next digit in *PIndex:
-//
-// Get the ideal location of digits JP, and if theres no next-left/right JP
-// in the BranchL, shortcut and start backtracking one level up; ignore the
-// current Pjp because it points to a BranchL with no next-left/right JP.
-
-#ifdef JUDYPREV
- if ((offset = (~offset) - 1) < 0) // no next-left JP in BranchL.
-#else
- if ((offset = (~offset)) >= Pjbl->jbl_NumJPs) // no next-right.
-#endif
- goto SM2Backtrack;
-
-// Theres a next-left/right JP in the current BranchL; save its digit in
-// *PIndex and shortcut to SM3Findlimit:
-
- JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
- Pjp = (Pjbl->jbl_jp) + offset;
- goto SM3Findlimit;
-
-
-// ----------------------------------------------------------------------------
-// BITMAP BRANCH:
-//
-// Check Decode bytes, if any, in the current JP, then look for a JP for the
-// next digit in *PIndex.
-
- case cJU_JPBRANCH_B2: CHECKDCD(2); SM1PREPB(2, SM1BranchB);
- case cJU_JPBRANCH_B3: CHECKDCD(3); SM1PREPB(3, SM1BranchB);
-#ifdef JU_64BIT
- case cJU_JPBRANCH_B4: CHECKDCD(4); SM1PREPB(4, SM1BranchB);
- case cJU_JPBRANCH_B5: CHECKDCD(5); SM1PREPB(5, SM1BranchB);
- case cJU_JPBRANCH_B6: CHECKDCD(6); SM1PREPB(6, SM1BranchB);
- case cJU_JPBRANCH_B7: CHECKDCD(7); SM1PREPB(7, SM1BranchB);
-#endif
- case cJU_JPBRANCH_B: SM1PREPB(cJU_ROOTSTATE, SM1BranchB);
-
-// Common code (state-independent) for all cases of bitmap branches:
-
-SM1BranchB:
- Pjbb = P_JBB(Pjp->jp_Addr);
-
-// Locate the digits JP in the subexpanse list, if present, otherwise the
-// offset of the next-left JP, if any:
-
- subexp = digit / cJU_BITSPERSUBEXPB;
- assert(subexp < cJU_NUMSUBEXPB); // falls in expected range.
- bitposmask = JU_BITPOSMASKB(digit);
- offset = SEARCHBITMAPB(JU_JBB_BITMAP(Pjbb, subexp), digit,
- bitposmask);
- // right range:
- assert((offset >= -1) && (offset < (int) cJU_BITSPERSUBEXPB));
-
-// Found JP matching current digit in *PIndex:
-//
-// Record the parent JP and the next JPs offset; and iterate to the next JP.
-
-// if (JU_BITMAPTESTB(Pjbb, digit)) // slower.
- if (JU_JBB_BITMAP(Pjbb, subexp) & bitposmask) // faster.
- {
- // not negative since at least one bit is set:
- assert(offset >= 0);
-
- HISTPUSH(Pjp, HISTPUSHBOFF(subexp, offset, digit));
-
- if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
-
- Pjp += offset;
- goto SM1Get; // iterate to next JP.
- }
-
-// Dead end, no JP in BranchB for next digit in *PIndex:
-//
-// If theres a next-left/right JP in the current BranchB, shortcut to
-// SM3Findlimit. Note: offset is already set to the correct value for the
-// next-left/right JP.
-
-#ifdef JUDYPREV
- if (offset >= 0) // next-left JP is in this subexpanse.
- goto SM1BranchBFindlimit;
-
- while (--subexp >= 0) // search next-left subexpanses.
-#else
- if (JU_JBB_BITMAP(Pjbb, subexp) & JU_MASKHIGHEREXC(bitposmask))
- {
- ++offset; // next-left => next-right.
- goto SM1BranchBFindlimit;
- }
-
- while (++subexp < cJU_NUMSUBEXPB) // search next-right subexps.
-#endif
- {
- if (! JU_JBB_PJP(Pjbb, subexp)) continue; // empty subexpanse.
-
-#ifdef JUDYPREV
- offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
- // expected range:
- assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
-#else
- offset = 0;
-#endif
-
-// Save the next-left/right JPs digit in *PIndex:
-
-SM1BranchBFindlimit:
- JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp),
- offset);
- JU_SETDIGIT(*PIndex, digit, state);
-
- if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
-
- Pjp += offset;
- goto SM3Findlimit;
- }
-
-// Theres no next-left/right JP in the BranchB:
-//
-// Shortcut and start backtracking one level up; ignore the current Pjp because
-// it points to a BranchB with no next-left/right JP.
-
- goto SM2Backtrack;
-
-
-// ----------------------------------------------------------------------------
-// UNCOMPRESSED BRANCH:
-//
-// Check Decode bytes, if any, in the current JP, then look for a JP for the
-// next digit in *PIndex.
-
- case cJU_JPBRANCH_U2: CHECKDCD(2); SM1PREPB(2, SM1BranchU);
- case cJU_JPBRANCH_U3: CHECKDCD(3); SM1PREPB(3, SM1BranchU);
-#ifdef JU_64BIT
- case cJU_JPBRANCH_U4: CHECKDCD(4); SM1PREPB(4, SM1BranchU);
- case cJU_JPBRANCH_U5: CHECKDCD(5); SM1PREPB(5, SM1BranchU);
- case cJU_JPBRANCH_U6: CHECKDCD(6); SM1PREPB(6, SM1BranchU);
- case cJU_JPBRANCH_U7: CHECKDCD(7); SM1PREPB(7, SM1BranchU);
-#endif
- case cJU_JPBRANCH_U: SM1PREPB(cJU_ROOTSTATE, SM1BranchU);
-
-// Common code (state-independent) for all cases of uncompressed branches:
-
-SM1BranchU:
- Pjbu = P_JBU(Pjp->jp_Addr);
- Pjp2 = (Pjbu->jbu_jp) + digit;
-
-// Found JP matching current digit in *PIndex:
-//
-// Record the parent JP and the next JPs digit, and iterate to the next JP.
-//
-// TBD: Instead of this, just goto SM1Get, and add cJU_JPNULL* cases to the
-// SM1Get state machine? Then backtrack? However, it means you cant detect
-// an inappropriate cJU_JPNULL*, when it occurs in other than a BranchU, and
-// return JU_RET_CORRUPT.
-
- if (! JPNULL(JU_JPTYPE(Pjp2))) // digit has a JP.
- {
- HISTPUSH(Pjp, digit);
- Pjp = Pjp2;
- goto SM1Get;
- }
-
-// Dead end, no JP in BranchU for next digit in *PIndex:
-//
-// Search for a next-left/right JP in the current BranchU, and if one is found,
-// save its digit in *PIndex and shortcut to SM3Findlimit:
-
-#ifdef JUDYPREV
- while (digit >= 1)
- {
- Pjp = (Pjbu->jbu_jp) + (--digit);
-#else
- while (digit < cJU_BRANCHUNUMJPS - 1)
- {
- Pjp = (Pjbu->jbu_jp) + (++digit);
-#endif
- if (JPNULL(JU_JPTYPE(Pjp))) continue;
-
- JU_SETDIGIT(*PIndex, digit, state);
- goto SM3Findlimit;
- }
-
-// Theres no next-left/right JP in the BranchU:
-//
-// Shortcut and start backtracking one level up; ignore the current Pjp because
-// it points to a BranchU with no next-left/right JP.
-
- goto SM2Backtrack;
-
-
-// ----------------------------------------------------------------------------
-// LINEAR LEAF:
-//
-// Check Decode bytes, if any, in the current JP, then search the leaf for
-// *PIndex.
-
-#define SM1LEAFL(Func) \
- Pjll = P_JLL(Pjp->jp_Addr); \
- pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
- offset = Func(Pjll, pop1, *PIndex); \
- goto SM1LeafLImm
-
-#if (defined(JUDYL) || (! defined(JU_64BIT)))
- case cJU_JPLEAF1: CHECKDCD(1); SM1LEAFL(j__udySearchLeaf1);
-#endif
- case cJU_JPLEAF2: CHECKDCD(2); SM1LEAFL(j__udySearchLeaf2);
- case cJU_JPLEAF3: CHECKDCD(3); SM1LEAFL(j__udySearchLeaf3);
-
-#ifdef JU_64BIT
- case cJU_JPLEAF4: CHECKDCD(4); SM1LEAFL(j__udySearchLeaf4);
- case cJU_JPLEAF5: CHECKDCD(5); SM1LEAFL(j__udySearchLeaf5);
- case cJU_JPLEAF6: CHECKDCD(6); SM1LEAFL(j__udySearchLeaf6);
- case cJU_JPLEAF7: CHECKDCD(7); SM1LEAFL(j__udySearchLeaf7);
-#endif
-
-// Common code (state-independent) for all cases of linear leaves and
-// immediates:
-
-SM1LeafLImm:
- if (offset >= 0) // *PIndex is in LeafL / Immed.
-#ifdef JUDY1
- JU_RET_FOUND;
-#else
- { // JudyL is trickier...
- switch (JU_JPTYPE(Pjp))
- {
-#if (defined(JUDYL) || (! defined(JU_64BIT)))
- case cJU_JPLEAF1: JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
-#endif
- case cJU_JPLEAF2: JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
- case cJU_JPLEAF3: JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
-#ifdef JU_64BIT
- case cJU_JPLEAF4: JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
- case cJU_JPLEAF5: JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
- case cJU_JPLEAF6: JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
- case cJU_JPLEAF7: JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
-#endif
-
- case cJU_JPIMMED_1_01:
- case cJU_JPIMMED_2_01:
- case cJU_JPIMMED_3_01:
-#ifdef JU_64BIT
- case cJU_JPIMMED_4_01:
- case cJU_JPIMMED_5_01:
- case cJU_JPIMMED_6_01:
- case cJU_JPIMMED_7_01:
-#endif
- JU_RET_FOUND_IMM_01(Pjp);
-
- case cJU_JPIMMED_1_02:
- case cJU_JPIMMED_1_03:
-#ifdef JU_64BIT
- case cJU_JPIMMED_1_04:
- case cJU_JPIMMED_1_05:
- case cJU_JPIMMED_1_06:
- case cJU_JPIMMED_1_07:
- case cJU_JPIMMED_2_02:
- case cJU_JPIMMED_2_03:
- case cJU_JPIMMED_3_02:
-#endif
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // impossible?
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
-
- } // found *PIndex
-
-#endif // JUDYL
-
-// Dead end, no Index in LeafL / Immed for remaining digit(s) in *PIndex:
-//
-// Get the ideal location of Index, and if theres no next-left/right Index in
-// the LeafL / Immed, shortcut and start backtracking one level up; ignore the
-// current Pjp because it points to a LeafL / Immed with no next-left/right
-// Index.
-
-#ifdef JUDYPREV
- if ((offset = (~offset) - 1) < 0) // no next-left Index.
-#else
- if ((offset = (~offset)) >= pop1) // no next-right Index.
-#endif
- goto SM2Backtrack;
-
-// Theres a next-left/right Index in the current LeafL / Immed; shortcut by
-// copying its digit(s) to *PIndex and returning it.
-//
-// Unfortunately this is pretty hairy, especially avoiding endian issues.
-//
-// The cJU_JPLEAF* cases are very similar to same-index-size cJU_JPIMMED* cases
-// for *_02 and above, but must return differently, at least for JudyL, so
-// spell them out separately here at the cost of a little redundant code for
-// Judy1.
-
- switch (JU_JPTYPE(Pjp))
- {
-#if (defined(JUDYL) || (! defined(JU_64BIT)))
- case cJU_JPLEAF1:
-
- JU_SETDIGIT1(*PIndex, ((uint8_t *) Pjll)[offset]);
- JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
-#endif
-
- case cJU_JPLEAF2:
-
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
- | ((uint16_t *) Pjll)[offset];
- JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
-
- case cJU_JPLEAF3:
- {
- Word_t lsb;
- JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
- JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
- }
-
-#ifdef JU_64BIT
- case cJU_JPLEAF4:
-
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
- | ((uint32_t *) Pjll)[offset];
- JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
-
- case cJU_JPLEAF5:
- {
- Word_t lsb;
- JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (5 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
- JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
- }
-
- case cJU_JPLEAF6:
- {
- Word_t lsb;
- JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (6 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
- JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
- }
-
- case cJU_JPLEAF7:
- {
- Word_t lsb;
- JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (7 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
- JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
- }
-
-#endif // JU_64BIT
-
-#define SET_01(cState) JU_SETDIGITS(*PIndex, JU_JPDCDPOP0(Pjp), cState)
-
- case cJU_JPIMMED_1_01: SET_01(1); goto SM1Imm_01;
- case cJU_JPIMMED_2_01: SET_01(2); goto SM1Imm_01;
- case cJU_JPIMMED_3_01: SET_01(3); goto SM1Imm_01;
-#ifdef JU_64BIT
- case cJU_JPIMMED_4_01: SET_01(4); goto SM1Imm_01;
- case cJU_JPIMMED_5_01: SET_01(5); goto SM1Imm_01;
- case cJU_JPIMMED_6_01: SET_01(6); goto SM1Imm_01;
- case cJU_JPIMMED_7_01: SET_01(7); goto SM1Imm_01;
-#endif
-SM1Imm_01: JU_RET_FOUND_IMM_01(Pjp);
-
-// Shorthand for where to find start of Index bytes array:
-
-#ifdef JUDY1
-#define PJI (Pjp->jp_1Index)
-#else
-#define PJI (Pjp->jp_LIndex)
-#endif
-
- case cJU_JPIMMED_1_02:
- case cJU_JPIMMED_1_03:
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_1_04:
- case cJU_JPIMMED_1_05:
- case cJU_JPIMMED_1_06:
- case cJU_JPIMMED_1_07:
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_1_08:
- case cJ1_JPIMMED_1_09:
- case cJ1_JPIMMED_1_10:
- case cJ1_JPIMMED_1_11:
- case cJ1_JPIMMED_1_12:
- case cJ1_JPIMMED_1_13:
- case cJ1_JPIMMED_1_14:
- case cJ1_JPIMMED_1_15:
-#endif
- JU_SETDIGIT1(*PIndex, ((uint8_t *) PJI)[offset]);
- JU_RET_FOUND_IMM(Pjp, offset);
-
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_2_02:
- case cJU_JPIMMED_2_03:
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_2_04:
- case cJ1_JPIMMED_2_05:
- case cJ1_JPIMMED_2_06:
- case cJ1_JPIMMED_2_07:
-#endif
-#if (defined(JUDY1) || defined(JU_64BIT))
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
- | ((uint16_t *) PJI)[offset];
- JU_RET_FOUND_IMM(Pjp, offset);
-#endif
-
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_3_02:
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_3_03:
- case cJ1_JPIMMED_3_04:
- case cJ1_JPIMMED_3_05:
-#endif
-#if (defined(JUDY1) || defined(JU_64BIT))
- {
- Word_t lsb;
- JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (3 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-#endif
-
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_4_02:
- case cJ1_JPIMMED_4_03:
-
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
- | ((uint32_t *) PJI)[offset];
- JU_RET_FOUND_IMM(Pjp, offset);
-
- case cJ1_JPIMMED_5_02:
- case cJ1_JPIMMED_5_03:
- {
- Word_t lsb;
- JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (5 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-
- case cJ1_JPIMMED_6_02:
- {
- Word_t lsb;
- JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (6 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-
- case cJ1_JPIMMED_7_02:
- {
- Word_t lsb;
- JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (7 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-
-#endif // (JUDY1 && JU_64BIT)
-
- } // switch for not-found *PIndex
-
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // impossible?
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
-
-
-// ----------------------------------------------------------------------------
-// BITMAP LEAF:
-//
-// Check Decode bytes, if any, in the current JP, then look in the leaf for
-// *PIndex.
-
- case cJU_JPLEAF_B1:
- {
- Pjlb_t Pjlb;
- CHECKDCD(1);
-
- Pjlb = P_JLB(Pjp->jp_Addr);
- digit = JU_DIGITATSTATE(*PIndex, 1);
- subexp = JU_SUBEXPL(digit);
- bitposmask = JU_BITPOSMASKL(digit);
- assert(subexp < cJU_NUMSUBEXPL); // falls in expected range.
-
-// *PIndex exists in LeafB1:
-
-// if (JU_BITMAPTESTL(Pjlb, digit)) // slower.
- if (JU_JLB_BITMAP(Pjlb, subexp) & bitposmask) // faster.
- {
-#ifdef JUDYL // needs offset at this point:
- offset = SEARCHBITMAPL(JU_JLB_BITMAP(Pjlb, subexp), digit, bitposmask);
-#endif
- JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
-// == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + (offset)));
- }
-
-// Dead end, no Index in LeafB1 for remaining digit in *PIndex:
-//
-// If theres a next-left/right Index in the current LeafB1, which for
-// Judy*Next() is true if any bits are set for higher Indexes, shortcut by
-// returning it. Note: For Judy*Prev(), offset is set here to the correct
-// value for the next-left JP.
-
- offset = SEARCHBITMAPL(JU_JLB_BITMAP(Pjlb, subexp), digit,
- bitposmask);
- // right range:
- assert((offset >= -1) && (offset < (int) cJU_BITSPERSUBEXPL));
-
-#ifdef JUDYPREV
- if (offset >= 0) // next-left JP is in this subexpanse.
- goto SM1LeafB1Findlimit;
-
- while (--subexp >= 0) // search next-left subexpanses.
-#else
- if (JU_JLB_BITMAP(Pjlb, subexp) & JU_MASKHIGHEREXC(bitposmask))
- {
- ++offset; // next-left => next-right.
- goto SM1LeafB1Findlimit;
- }
-
- while (++subexp < cJU_NUMSUBEXPL) // search next-right subexps.
-#endif
- {
- if (! JU_JLB_BITMAP(Pjlb, subexp)) continue; // empty subexp.
-
-#ifdef JUDYPREV
- offset = SEARCHBITMAPMAXL(JU_JLB_BITMAP(Pjlb, subexp));
- // expected range:
- assert((offset >= 0) && (offset < (int) cJU_BITSPERSUBEXPL));
-#else
- offset = 0;
-#endif
-
-// Save the next-left/right Indexess digit in *PIndex:
-
-SM1LeafB1Findlimit:
- JU_BITMAPDIGITL(digit, subexp, JU_JLB_BITMAP(Pjlb, subexp), offset);
- JU_SETDIGIT1(*PIndex, digit);
- JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
-// == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + (offset)));
- }
-
-// Theres no next-left/right Index in the LeafB1:
-//
-// Shortcut and start backtracking one level up; ignore the current Pjp because
-// it points to a LeafB1 with no next-left/right Index.
-
- goto SM2Backtrack;
-
- } // case cJU_JPLEAF_B1
-
-#ifdef JUDY1
-// ----------------------------------------------------------------------------
-// FULL POPULATION:
-//
-// If the Decode bytes match, *PIndex is found (without modification).
-
- case cJ1_JPFULLPOPU1:
-
- CHECKDCD(1);
- JU_RET_FOUND_FULLPOPU1;
-#endif
-
-
-// ----------------------------------------------------------------------------
-// IMMEDIATE:
-
-#ifdef JUDYPREV
-#define SM1IMM_SETPOP1(cPop1)
-#else
-#define SM1IMM_SETPOP1(cPop1) pop1 = (cPop1)
-#endif
-
-#define SM1IMM(Func,cPop1) \
- SM1IMM_SETPOP1(cPop1); \
- offset = Func((Pjll_t) (PJI), cPop1, *PIndex); \
- goto SM1LeafLImm
-
-// Special case for Pop1 = 1 Immediate JPs:
-//
-// If *PIndex is in the immediate, offset is 0, otherwise the binary NOT of the
-// offset where it belongs, 0 or 1, same as from the search functions.
-
-#ifdef JUDYPREV
-#define SM1IMM_01_SETPOP1
-#else
-#define SM1IMM_01_SETPOP1 pop1 = 1
-#endif
-
-#define SM1IMM_01 \
- SM1IMM_01_SETPOP1; \
- offset = ((JU_JPDCDPOP0(Pjp) < JU_TRIMTODCDSIZE(*PIndex)) ? ~1 : \
- (JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(*PIndex)) ? 0 : \
- ~0); \
- goto SM1LeafLImm
-
- case cJU_JPIMMED_1_01:
- case cJU_JPIMMED_2_01:
- case cJU_JPIMMED_3_01:
-#ifdef JU_64BIT
- case cJU_JPIMMED_4_01:
- case cJU_JPIMMED_5_01:
- case cJU_JPIMMED_6_01:
- case cJU_JPIMMED_7_01:
-#endif
- SM1IMM_01;
-
-// TBD: Doug says it would be OK to have fewer calls and calculate arg 2, here
-// and in Judy*Count() also.
-
- case cJU_JPIMMED_1_02: SM1IMM(j__udySearchLeaf1, 2);
- case cJU_JPIMMED_1_03: SM1IMM(j__udySearchLeaf1, 3);
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_1_04: SM1IMM(j__udySearchLeaf1, 4);
- case cJU_JPIMMED_1_05: SM1IMM(j__udySearchLeaf1, 5);
- case cJU_JPIMMED_1_06: SM1IMM(j__udySearchLeaf1, 6);
- case cJU_JPIMMED_1_07: SM1IMM(j__udySearchLeaf1, 7);
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_1_08: SM1IMM(j__udySearchLeaf1, 8);
- case cJ1_JPIMMED_1_09: SM1IMM(j__udySearchLeaf1, 9);
- case cJ1_JPIMMED_1_10: SM1IMM(j__udySearchLeaf1, 10);
- case cJ1_JPIMMED_1_11: SM1IMM(j__udySearchLeaf1, 11);
- case cJ1_JPIMMED_1_12: SM1IMM(j__udySearchLeaf1, 12);
- case cJ1_JPIMMED_1_13: SM1IMM(j__udySearchLeaf1, 13);
- case cJ1_JPIMMED_1_14: SM1IMM(j__udySearchLeaf1, 14);
- case cJ1_JPIMMED_1_15: SM1IMM(j__udySearchLeaf1, 15);
-#endif
-
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_2_02: SM1IMM(j__udySearchLeaf2, 2);
- case cJU_JPIMMED_2_03: SM1IMM(j__udySearchLeaf2, 3);
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_2_04: SM1IMM(j__udySearchLeaf2, 4);
- case cJ1_JPIMMED_2_05: SM1IMM(j__udySearchLeaf2, 5);
- case cJ1_JPIMMED_2_06: SM1IMM(j__udySearchLeaf2, 6);
- case cJ1_JPIMMED_2_07: SM1IMM(j__udySearchLeaf2, 7);
-#endif
-
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_3_02: SM1IMM(j__udySearchLeaf3, 2);
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_3_03: SM1IMM(j__udySearchLeaf3, 3);
- case cJ1_JPIMMED_3_04: SM1IMM(j__udySearchLeaf3, 4);
- case cJ1_JPIMMED_3_05: SM1IMM(j__udySearchLeaf3, 5);
-
- case cJ1_JPIMMED_4_02: SM1IMM(j__udySearchLeaf4, 2);
- case cJ1_JPIMMED_4_03: SM1IMM(j__udySearchLeaf4, 3);
-
- case cJ1_JPIMMED_5_02: SM1IMM(j__udySearchLeaf5, 2);
- case cJ1_JPIMMED_5_03: SM1IMM(j__udySearchLeaf5, 3);
-
- case cJ1_JPIMMED_6_02: SM1IMM(j__udySearchLeaf6, 2);
-
- case cJ1_JPIMMED_7_02: SM1IMM(j__udySearchLeaf7, 2);
-#endif
-
-
-// ----------------------------------------------------------------------------
-// INVALID JP TYPE:
-
- default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
-
- } // SM1Get switch.
-
- /*NOTREACHED*/
-
-
-// ============================================================================
-// STATE MACHINE 2 -- BACKTRACK BRANCH TO PREVIOUS JP:
-//
-// Look for the next-left/right JP in a branch, backing up the history list as
-// necessary. Upon finding a next-left/right JP, modify the corresponding
-// digit in *PIndex before passing control to SM3Findlimit.
-//
-// Note: As described earlier, only branch JPs are expected here; other types
-// fall into the default case.
-//
-// Note: If a found JP contains needed Dcd bytes, thats OK, theyre copied to
-// *PIndex in SM3Findlimit.
-//
-// TBD: This code has a lot in common with similar code in the shortcut cases
-// in SM1Get. Can combine this code somehow?
-//
-// ENTRY: List, possibly empty, of JPs and offsets in APjphist[] and
-// Aoffhist[]; see earlier comments.
-//
-// EXIT: Execute JU_RET_NOTFOUND if no previous/next JP; otherwise jump to
-// SM3Findlimit to resume a new but different downward search.
-
-SM2Backtrack: // come or return here for first/next sideways search.
-
- HISTPOP(Pjp, offset);
-
- switch (JU_JPTYPE(Pjp))
- {
-
-
-// ----------------------------------------------------------------------------
-// LINEAR BRANCH:
-
- case cJU_JPBRANCH_L2: state = 2; goto SM2BranchL;
- case cJU_JPBRANCH_L3: state = 3; goto SM2BranchL;
-#ifdef JU_64BIT
- case cJU_JPBRANCH_L4: state = 4; goto SM2BranchL;
- case cJU_JPBRANCH_L5: state = 5; goto SM2BranchL;
- case cJU_JPBRANCH_L6: state = 6; goto SM2BranchL;
- case cJU_JPBRANCH_L7: state = 7; goto SM2BranchL;
-#endif
- case cJU_JPBRANCH_L: state = cJU_ROOTSTATE; goto SM2BranchL;
-
-SM2BranchL:
-#ifdef JUDYPREV
- if (--offset < 0) goto SM2Backtrack; // no next-left JP in BranchL.
-#endif
- Pjbl = P_JBL(Pjp->jp_Addr);
-#ifdef JUDYNEXT
- if (++offset >= (Pjbl->jbl_NumJPs)) goto SM2Backtrack;
- // no next-right JP in BranchL.
-#endif
-
-// Theres a next-left/right JP in the current BranchL; save its digit in
-// *PIndex and continue with SM3Findlimit:
-
- JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
- Pjp = (Pjbl->jbl_jp) + offset;
- goto SM3Findlimit;
-
-
-// ----------------------------------------------------------------------------
-// BITMAP BRANCH:
-
- case cJU_JPBRANCH_B2: state = 2; goto SM2BranchB;
- case cJU_JPBRANCH_B3: state = 3; goto SM2BranchB;
-#ifdef JU_64BIT
- case cJU_JPBRANCH_B4: state = 4; goto SM2BranchB;
- case cJU_JPBRANCH_B5: state = 5; goto SM2BranchB;
- case cJU_JPBRANCH_B6: state = 6; goto SM2BranchB;
- case cJU_JPBRANCH_B7: state = 7; goto SM2BranchB;
-#endif
- case cJU_JPBRANCH_B: state = cJU_ROOTSTATE; goto SM2BranchB;
-
-SM2BranchB:
- Pjbb = P_JBB(Pjp->jp_Addr);
- HISTPOPBOFF(subexp, offset, digit); // unpack values.
-
-// If theres a next-left/right JP in the current BranchB, which for
-// Judy*Next() is true if any bits are set for higher Indexes, continue to
-// SM3Findlimit:
-//
-// Note: offset is set to the JP previously traversed; go one to the
-// left/right.
-
-#ifdef JUDYPREV
- if (offset > 0) // next-left JP is in this subexpanse.
- {
- --offset;
- goto SM2BranchBFindlimit;
- }
-
- while (--subexp >= 0) // search next-left subexpanses.
-#else
- if (JU_JBB_BITMAP(Pjbb, subexp)
- & JU_MASKHIGHEREXC(JU_BITPOSMASKB(digit)))
- {
- ++offset; // next-left => next-right.
- goto SM2BranchBFindlimit;
- }
-
- while (++subexp < cJU_NUMSUBEXPB) // search next-right subexps.
-#endif
- {
- if (! JU_JBB_PJP(Pjbb, subexp)) continue; // empty subexpanse.
-
-#ifdef JUDYPREV
- offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
- // expected range:
- assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
-#else
- offset = 0;
-#endif
-
-// Save the next-left/right JPs digit in *PIndex:
-
-SM2BranchBFindlimit:
- JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp),
- offset);
- JU_SETDIGIT(*PIndex, digit, state);
-
- if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
-
- Pjp += offset;
- goto SM3Findlimit;
- }
-
-// Theres no next-left/right JP in the BranchB:
-
- goto SM2Backtrack;
-
-
-// ----------------------------------------------------------------------------
-// UNCOMPRESSED BRANCH:
-
- case cJU_JPBRANCH_U2: state = 2; goto SM2BranchU;
- case cJU_JPBRANCH_U3: state = 3; goto SM2BranchU;
-#ifdef JU_64BIT
- case cJU_JPBRANCH_U4: state = 4; goto SM2BranchU;
- case cJU_JPBRANCH_U5: state = 5; goto SM2BranchU;
- case cJU_JPBRANCH_U6: state = 6; goto SM2BranchU;
- case cJU_JPBRANCH_U7: state = 7; goto SM2BranchU;
-#endif
- case cJU_JPBRANCH_U: state = cJU_ROOTSTATE; goto SM2BranchU;
-
-SM2BranchU:
-
-// Search for a next-left/right JP in the current BranchU, and if one is found,
-// save its digit in *PIndex and continue to SM3Findlimit:
-
- Pjbu = P_JBU(Pjp->jp_Addr);
- digit = offset;
-
-#ifdef JUDYPREV
- while (digit >= 1)
- {
- Pjp = (Pjbu->jbu_jp) + (--digit);
-#else
- while (digit < cJU_BRANCHUNUMJPS - 1)
- {
- Pjp = (Pjbu->jbu_jp) + (++digit);
-#endif
- if (JPNULL(JU_JPTYPE(Pjp))) continue;
-
- JU_SETDIGIT(*PIndex, digit, state);
- goto SM3Findlimit;
- }
-
-// Theres no next-left/right JP in the BranchU:
-
- goto SM2Backtrack;
-
-
-// ----------------------------------------------------------------------------
-// INVALID JP TYPE:
-
- default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
-
- } // SM2Backtrack switch.
-
- /*NOTREACHED*/
-
-
-// ============================================================================
-// STATE MACHINE 3 -- FIND LIMIT JP/INDEX:
-//
-// Look for the highest/lowest (right/left-most) JP in each branch and the
-// highest/lowest Index in a leaf or immediate, and return it. While
-// traversing, modify appropriate digit(s) in *PIndex to reflect the path
-// taken, including Dcd bytes in each JP (which could hold critical missing
-// digits for skipped branches).
-//
-// ENTRY: Pjp set to a JP under which to find max/min JPs (if a branch JP) or
-// a max/min Index and return (if a leaf or immediate JP).
-//
-// EXIT: Execute JU_RET_FOUND* upon reaching a leaf or immediate. Should be
-// impossible to fail, unless the Judy array is corrupt.
-
-SM3Findlimit: // come or return here for first/next branch/leaf.
-
- switch (JU_JPTYPE(Pjp))
- {
-// ----------------------------------------------------------------------------
-// LINEAR BRANCH:
-//
-// Simply use the highest/lowest (right/left-most) JP in the BranchL, but first
-// copy the Dcd bytes to *PIndex if there are any (only if state <
-// cJU_ROOTSTATE - 1).
-
- case cJU_JPBRANCH_L2: SM3PREPB_DCD(2, SM3BranchL);
-#ifndef JU_64BIT
- case cJU_JPBRANCH_L3: SM3PREPB( 3, SM3BranchL);
-#else
- case cJU_JPBRANCH_L3: SM3PREPB_DCD(3, SM3BranchL);
- case cJU_JPBRANCH_L4: SM3PREPB_DCD(4, SM3BranchL);
- case cJU_JPBRANCH_L5: SM3PREPB_DCD(5, SM3BranchL);
- case cJU_JPBRANCH_L6: SM3PREPB_DCD(6, SM3BranchL);
- case cJU_JPBRANCH_L7: SM3PREPB( 7, SM3BranchL);
-#endif
- case cJU_JPBRANCH_L: SM3PREPB( cJU_ROOTSTATE, SM3BranchL);
-
-SM3BranchL:
- Pjbl = P_JBL(Pjp->jp_Addr);
-
-#ifdef JUDYPREV
- if ((offset = (Pjbl->jbl_NumJPs) - 1) < 0)
-#else
- offset = 0; if ((Pjbl->jbl_NumJPs) == 0)
-#endif
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
-
- JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
- Pjp = (Pjbl->jbl_jp) + offset;
- goto SM3Findlimit;
-
-
-// ----------------------------------------------------------------------------
-// BITMAP BRANCH:
-//
-// Look for the highest/lowest (right/left-most) non-null subexpanse, then use
-// the highest/lowest JP in that subexpanse, but first copy Dcd bytes, if there
-// are any (only if state < cJU_ROOTSTATE - 1), to *PIndex.
-
- case cJU_JPBRANCH_B2: SM3PREPB_DCD(2, SM3BranchB);
-#ifndef JU_64BIT
- case cJU_JPBRANCH_B3: SM3PREPB( 3, SM3BranchB);
-#else
- case cJU_JPBRANCH_B3: SM3PREPB_DCD(3, SM3BranchB);
- case cJU_JPBRANCH_B4: SM3PREPB_DCD(4, SM3BranchB);
- case cJU_JPBRANCH_B5: SM3PREPB_DCD(5, SM3BranchB);
- case cJU_JPBRANCH_B6: SM3PREPB_DCD(6, SM3BranchB);
- case cJU_JPBRANCH_B7: SM3PREPB( 7, SM3BranchB);
-#endif
- case cJU_JPBRANCH_B: SM3PREPB( cJU_ROOTSTATE, SM3BranchB);
-
-SM3BranchB:
- Pjbb = P_JBB(Pjp->jp_Addr);
-#ifdef JUDYPREV
- subexp = cJU_NUMSUBEXPB;
-
- while (! (JU_JBB_BITMAP(Pjbb, --subexp))) // find non-empty subexp.
- {
- if (subexp <= 0) // wholly empty bitmap.
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
- }
-
- offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
- // expected range:
- assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
-#else
- subexp = -1;
-
- while (! (JU_JBB_BITMAP(Pjbb, ++subexp))) // find non-empty subexp.
- {
- if (subexp >= cJU_NUMSUBEXPB - 1) // didnt find one.
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
- }
-
- offset = 0;
-#endif
-
- JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp), offset);
- JU_SETDIGIT(*PIndex, digit, state);
-
- if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
-
- Pjp += offset;
- goto SM3Findlimit;
-
-
-// ----------------------------------------------------------------------------
-// UNCOMPRESSED BRANCH:
-//
-// Look for the highest/lowest (right/left-most) non-null JP, and use it, but
-// first copy Dcd bytes to *PIndex if there are any (only if state <
-// cJU_ROOTSTATE - 1).
-
- case cJU_JPBRANCH_U2: SM3PREPB_DCD(2, SM3BranchU);
-#ifndef JU_64BIT
- case cJU_JPBRANCH_U3: SM3PREPB( 3, SM3BranchU);
-#else
- case cJU_JPBRANCH_U3: SM3PREPB_DCD(3, SM3BranchU);
- case cJU_JPBRANCH_U4: SM3PREPB_DCD(4, SM3BranchU);
- case cJU_JPBRANCH_U5: SM3PREPB_DCD(5, SM3BranchU);
- case cJU_JPBRANCH_U6: SM3PREPB_DCD(6, SM3BranchU);
- case cJU_JPBRANCH_U7: SM3PREPB( 7, SM3BranchU);
-#endif
- case cJU_JPBRANCH_U: SM3PREPB( cJU_ROOTSTATE, SM3BranchU);
-
-SM3BranchU:
- Pjbu = P_JBU(Pjp->jp_Addr);
-#ifdef JUDYPREV
- digit = cJU_BRANCHUNUMJPS;
-
- while (digit >= 1)
- {
- Pjp = (Pjbu->jbu_jp) + (--digit);
-#else
-
- for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit)
- {
- Pjp = (Pjbu->jbu_jp) + digit;
-#endif
- if (JPNULL(JU_JPTYPE(Pjp))) continue;
-
- JU_SETDIGIT(*PIndex, digit, state);
- goto SM3Findlimit;
- }
-
-// No non-null JPs in BranchU:
-
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
-
-
-// ----------------------------------------------------------------------------
-// LINEAR LEAF:
-//
-// Simply use the highest/lowest (right/left-most) Index in the LeafL, but the
-// details vary depending on leaf Index Size. First copy Dcd bytes, if there
-// are any (only if state < cJU_ROOTSTATE - 1), to *PIndex.
-
-#define SM3LEAFLDCD(cState) \
- JU_SETDCD(*PIndex, Pjp, cState); \
- SM3LEAFLNODCD
-
-#ifdef JUDY1
-#define SM3LEAFL_SETPOP1 // not needed in any cases.
-#else
-#define SM3LEAFL_SETPOP1 pop1 = JU_JPLEAF_POP0(Pjp) + 1
-#endif
-
-#ifdef JUDYPREV
-#define SM3LEAFLNODCD \
- Pjll = P_JLL(Pjp->jp_Addr); \
- SM3LEAFL_SETPOP1; \
- offset = JU_JPLEAF_POP0(Pjp); assert(offset >= 0)
-#else
-#define SM3LEAFLNODCD \
- Pjll = P_JLL(Pjp->jp_Addr); \
- SM3LEAFL_SETPOP1; \
- offset = 0; assert(JU_JPLEAF_POP0(Pjp) >= 0);
-#endif
-
-#if (defined(JUDYL) || (! defined(JU_64BIT)))
- case cJU_JPLEAF1:
-
- SM3LEAFLDCD(1);
- JU_SETDIGIT1(*PIndex, ((uint8_t *) Pjll)[offset]);
- JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
-#endif
-
- case cJU_JPLEAF2:
-
- SM3LEAFLDCD(2);
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
- | ((uint16_t *) Pjll)[offset];
- JU_RET_FOUND_LEAF2(Pjll, pop1, offset);
-
-#ifndef JU_64BIT
- case cJU_JPLEAF3:
- {
- Word_t lsb;
- SM3LEAFLNODCD;
- JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
- JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
- }
-
-#else
- case cJU_JPLEAF3:
- {
- Word_t lsb;
- SM3LEAFLDCD(3);
- JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (3 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
- JU_RET_FOUND_LEAF3(Pjll, pop1, offset);
- }
-
- case cJU_JPLEAF4:
-
- SM3LEAFLDCD(4);
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
- | ((uint32_t *) Pjll)[offset];
- JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
-
- case cJU_JPLEAF5:
- {
- Word_t lsb;
- SM3LEAFLDCD(5);
- JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (5 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
- JU_RET_FOUND_LEAF5(Pjll, pop1, offset);
- }
-
- case cJU_JPLEAF6:
- {
- Word_t lsb;
- SM3LEAFLDCD(6);
- JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (6 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
- JU_RET_FOUND_LEAF6(Pjll, pop1, offset);
- }
-
- case cJU_JPLEAF7:
- {
- Word_t lsb;
- SM3LEAFLNODCD;
- JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) Pjll) + (7 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
- JU_RET_FOUND_LEAF7(Pjll, pop1, offset);
- }
-#endif
-
-
-// ----------------------------------------------------------------------------
-// BITMAP LEAF:
-//
-// Look for the highest/lowest (right/left-most) non-null subexpanse, then use
-// the highest/lowest Index in that subexpanse, but first copy Dcd bytes
-// (always present since state 1 < cJU_ROOTSTATE) to *PIndex.
-
- case cJU_JPLEAF_B1:
- {
- Pjlb_t Pjlb;
-
- JU_SETDCD(*PIndex, Pjp, 1);
-
- Pjlb = P_JLB(Pjp->jp_Addr);
-#ifdef JUDYPREV
- subexp = cJU_NUMSUBEXPL;
-
- while (! JU_JLB_BITMAP(Pjlb, --subexp)) // find non-empty subexp.
- {
- if (subexp <= 0) // wholly empty bitmap.
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
- }
-
-// TBD: Might it be faster to just use a variant of BITMAPDIGIT*() that yields
-// the digit for the right-most Index with a bit set?
-
- offset = SEARCHBITMAPMAXL(JU_JLB_BITMAP(Pjlb, subexp));
- // expected range:
- assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPL));
-#else
- subexp = -1;
-
- while (! JU_JLB_BITMAP(Pjlb, ++subexp)) // find non-empty subexp.
- {
- if (subexp >= cJU_NUMSUBEXPL - 1) // didnt find one.
- {
- JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
- }
- }
-
- offset = 0;
-#endif
-
- JU_BITMAPDIGITL(digit, subexp, JU_JLB_BITMAP(Pjlb, subexp), offset);
- JU_SETDIGIT1(*PIndex, digit);
- JU_RET_FOUND_LEAF_B1(Pjlb, subexp, offset);
-// == return((PPvoid_t) (P_JV(JL_JLB_PVALUE(Pjlb, subexp)) + (offset)));
-
- } // case cJU_JPLEAF_B1
-
-#ifdef JUDY1
-// ----------------------------------------------------------------------------
-// FULL POPULATION:
-//
-// Copy Dcd bytes to *PIndex (always present since state 1 < cJU_ROOTSTATE),
-// then set the highest/lowest possible digit as the LSB in *PIndex.
-
- case cJ1_JPFULLPOPU1:
-
- JU_SETDCD( *PIndex, Pjp, 1);
-#ifdef JUDYPREV
- JU_SETDIGIT1(*PIndex, cJU_BITSPERBITMAP - 1);
-#else
- JU_SETDIGIT1(*PIndex, 0);
-#endif
- JU_RET_FOUND_FULLPOPU1;
-#endif // JUDY1
-
-
-// ----------------------------------------------------------------------------
-// IMMEDIATE:
-//
-// Simply use the highest/lowest (right/left-most) Index in the Imm, but the
-// details vary depending on leaf Index Size and pop1. Note: There are no Dcd
-// bytes in an Immediate JP, but in a cJU_JPIMMED_*_01 JP, the field holds the
-// least bytes of the immediate Index.
-
- case cJU_JPIMMED_1_01: SET_01(1); goto SM3Imm_01;
- case cJU_JPIMMED_2_01: SET_01(2); goto SM3Imm_01;
- case cJU_JPIMMED_3_01: SET_01(3); goto SM3Imm_01;
-#ifdef JU_64BIT
- case cJU_JPIMMED_4_01: SET_01(4); goto SM3Imm_01;
- case cJU_JPIMMED_5_01: SET_01(5); goto SM3Imm_01;
- case cJU_JPIMMED_6_01: SET_01(6); goto SM3Imm_01;
- case cJU_JPIMMED_7_01: SET_01(7); goto SM3Imm_01;
-#endif
-SM3Imm_01: JU_RET_FOUND_IMM_01(Pjp);
-
-#ifdef JUDYPREV
-#define SM3IMM_OFFSET(cPop1) (cPop1) - 1 // highest.
-#else
-#define SM3IMM_OFFSET(cPop1) 0 // lowest.
-#endif
-
-#define SM3IMM(cPop1,Next) \
- offset = SM3IMM_OFFSET(cPop1); \
- goto Next
-
- case cJU_JPIMMED_1_02: SM3IMM( 2, SM3Imm1);
- case cJU_JPIMMED_1_03: SM3IMM( 3, SM3Imm1);
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_1_04: SM3IMM( 4, SM3Imm1);
- case cJU_JPIMMED_1_05: SM3IMM( 5, SM3Imm1);
- case cJU_JPIMMED_1_06: SM3IMM( 6, SM3Imm1);
- case cJU_JPIMMED_1_07: SM3IMM( 7, SM3Imm1);
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_1_08: SM3IMM( 8, SM3Imm1);
- case cJ1_JPIMMED_1_09: SM3IMM( 9, SM3Imm1);
- case cJ1_JPIMMED_1_10: SM3IMM(10, SM3Imm1);
- case cJ1_JPIMMED_1_11: SM3IMM(11, SM3Imm1);
- case cJ1_JPIMMED_1_12: SM3IMM(12, SM3Imm1);
- case cJ1_JPIMMED_1_13: SM3IMM(13, SM3Imm1);
- case cJ1_JPIMMED_1_14: SM3IMM(14, SM3Imm1);
- case cJ1_JPIMMED_1_15: SM3IMM(15, SM3Imm1);
-#endif
-
-SM3Imm1: JU_SETDIGIT1(*PIndex, ((uint8_t *) PJI)[offset]);
- JU_RET_FOUND_IMM(Pjp, offset);
-
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_2_02: SM3IMM(2, SM3Imm2);
- case cJU_JPIMMED_2_03: SM3IMM(3, SM3Imm2);
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_2_04: SM3IMM(4, SM3Imm2);
- case cJ1_JPIMMED_2_05: SM3IMM(5, SM3Imm2);
- case cJ1_JPIMMED_2_06: SM3IMM(6, SM3Imm2);
- case cJ1_JPIMMED_2_07: SM3IMM(7, SM3Imm2);
-#endif
-
-#if (defined(JUDY1) || defined(JU_64BIT))
-SM3Imm2: *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(2)))
- | ((uint16_t *) PJI)[offset];
- JU_RET_FOUND_IMM(Pjp, offset);
-#endif
-
-#if (defined(JUDY1) || defined(JU_64BIT))
- case cJU_JPIMMED_3_02: SM3IMM(2, SM3Imm3);
-#endif
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_3_03: SM3IMM(3, SM3Imm3);
- case cJ1_JPIMMED_3_04: SM3IMM(4, SM3Imm3);
- case cJ1_JPIMMED_3_05: SM3IMM(5, SM3Imm3);
-#endif
-
-#if (defined(JUDY1) || defined(JU_64BIT))
-SM3Imm3:
- {
- Word_t lsb;
- JU_COPY3_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (3 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(3))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-#endif
-
-#if (defined(JUDY1) && defined(JU_64BIT))
- case cJ1_JPIMMED_4_02: SM3IMM(2, SM3Imm4);
- case cJ1_JPIMMED_4_03: SM3IMM(3, SM3Imm4);
-
-SM3Imm4: *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
- | ((uint32_t *) PJI)[offset];
- JU_RET_FOUND_IMM(Pjp, offset);
-
- case cJ1_JPIMMED_5_02: SM3IMM(2, SM3Imm5);
- case cJ1_JPIMMED_5_03: SM3IMM(3, SM3Imm5);
-
-SM3Imm5:
- {
- Word_t lsb;
- JU_COPY5_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (5 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(5))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-
- case cJ1_JPIMMED_6_02: SM3IMM(2, SM3Imm6);
-
-SM3Imm6:
- {
- Word_t lsb;
- JU_COPY6_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (6 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(6))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-
- case cJ1_JPIMMED_7_02: SM3IMM(2, SM3Imm7);
-
-SM3Imm7:
- {
- Word_t lsb;
- JU_COPY7_PINDEX_TO_LONG(lsb, ((uint8_t *) PJI) + (7 * offset));
- *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(7))) | lsb;
- JU_RET_FOUND_IMM(Pjp, offset);
- }
-#endif // (JUDY1 && JU_64BIT)
-
-
-// ----------------------------------------------------------------------------
-// OTHER CASES:
-
- default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
- JUDY1CODE(return(JERRI );)
- JUDYLCODE(return(PPJERR);)
-
- } // SM3Findlimit switch.
-
- /*NOTREACHED*/
-
-} // Judy1Prev() / Judy1Next() / JudyLPrev() / JudyLNext()