summaryrefslogtreecommitdiffstats
path: root/libnetdata/libjudy/src/JudyL/JudyLByCount.c
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLByCount.c')
-rw-r--r--libnetdata/libjudy/src/JudyL/JudyLByCount.c954
1 files changed, 954 insertions, 0 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLByCount.c b/libnetdata/libjudy/src/JudyL/JudyLByCount.c
new file mode 100644
index 0000000..c5a0047
--- /dev/null
+++ b/libnetdata/libjudy/src/JudyL/JudyLByCount.c
@@ -0,0 +1,954 @@
+// 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.28 $ $Source: /judy/src/JudyCommon/JudyByCount.c $
+//
+// Judy*ByCount() function for Judy1 and JudyL.
+// Compile with one of -DJUDY1 or -DJUDYL.
+//
+// Compile with -DNOSMARTJBB, -DNOSMARTJBU, and/or -DNOSMARTJLB to build a
+// version with cache line optimizations deleted, for testing.
+//
+// Judy*ByCount() is a conceptual although not literal inverse of Judy*Count().
+// Judy*Count() takes a pair of Indexes, and allows finding the ordinal of a
+// given Index (that is, its position in the list of valid indexes from the
+// beginning) as a degenerate case, because in general the count between two
+// Indexes, inclusive, is not always just the difference in their ordinals.
+// However, it suffices for Judy*ByCount() to simply be an ordinal-to-Index
+// mapper.
+//
+// Note: Like Judy*Count(), this code must "count sideways" in branches, which
+// can result in a lot of cache line fills. However, unlike Judy*Count(), this
+// code does not receive a specific Index, hence digit, where to start in each
+// branch, so it cant accurately calculate cache line fills required in each
+// direction. The best it can do is an approximation based on the total
+// population of the expanse (pop1 from Pjp) and the ordinal of the target
+// Index (see SETOFFSET()) within the expanse.
+//
+// Compile with -DSMARTMETRICS to obtain global variables containing smart
+// cache line metrics. Note: Dont turn this on simultaneously for this file
+// and JudyCount.c because they export the same globals.
+// ****************************************************************************
+
+#if (! (defined(JUDY1) || defined(JUDYL)))
+#error: One of -DJUDY1 or -DJUDYL must be specified.
+#endif
+
+#ifdef JUDY1
+#include "Judy1.h"
+#else
+#include "JudyL.h"
+#endif
+
+#include "JudyPrivate1L.h"
+
+// These are imported from JudyCount.c:
+//
+// TBD: Should this be in common code? Exported from a header file?
+
+#ifdef JUDY1
+extern Word_t j__udy1JPPop1(const Pjp_t Pjp);
+#define j__udyJPPop1 j__udy1JPPop1
+#else
+extern Word_t j__udyLJPPop1(const Pjp_t Pjp);
+#define j__udyJPPop1 j__udyLJPPop1
+#endif
+
+// Avoid duplicate symbols since this file is multi-compiled:
+
+#ifdef SMARTMETRICS
+#ifdef JUDY1
+Word_t jbb_upward = 0; // counts of directions taken:
+Word_t jbb_downward = 0;
+Word_t jbu_upward = 0;
+Word_t jbu_downward = 0;
+Word_t jlb_upward = 0;
+Word_t jlb_downward = 0;
+#else
+extern Word_t jbb_upward;
+extern Word_t jbb_downward;
+extern Word_t jbu_upward;
+extern Word_t jbu_downward;
+extern Word_t jlb_upward;
+extern Word_t jlb_downward;
+#endif
+#endif
+
+
+// ****************************************************************************
+// J U D Y 1 B Y C O U N T
+// J U D Y L B Y C O U N T
+//
+// See the manual entry.
+
+#ifdef JUDY1
+FUNCTION int Judy1ByCount
+#else
+FUNCTION PPvoid_t JudyLByCount
+#endif
+ (
+ Pcvoid_t PArray, // root pointer to first branch/leaf in SM.
+ Word_t Count, // ordinal of Index to find, 1..MAX.
+ Word_t * PIndex, // to return found Index.
+ PJError_t PJError // optional, for returning error info.
+ )
+{
+ Word_t Count0; // Count, base-0, to match pop0.
+ Word_t state; // current state in SM.
+ Word_t pop1; // of current branch or leaf, or of expanse.
+ Word_t pop1lower; // pop1 of expanses (JPs) below that for Count.
+ Word_t digit; // current word in branch.
+ Word_t jpcount; // JPs in a BranchB subexpanse.
+ long jpnum; // JP number in a branch (base 0).
+ long subexp; // for stepping through layer 1 (subexpanses).
+ int offset; // index ordinal within a leaf, base 0.
+
+ Pjp_t Pjp; // current JP in branch.
+ Pjll_t Pjll; // current Judy linear leaf.
+
+
+// CHECK FOR EMPTY ARRAY OR NULL PINDEX:
+
+ if (PArray == (Pvoid_t) NULL) JU_RET_NOTFOUND;
+
+ if (PIndex == (PWord_t) NULL)
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+
+// Convert Count to Count0; assume special case of Count = 0 maps to ~0, as
+// desired, to represent the last index in a full array:
+//
+// Note: Think of Count0 as a reliable "number of Indexes below the target."
+
+ Count0 = Count - 1;
+ assert((Count || Count0 == ~0)); // ensure CPU is sane about 0 - 1.
+ pop1lower = 0;
+
+ if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
+ {
+ Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
+
+ if (Count0 > Pjlw[0]) JU_RET_NOTFOUND; // too high.
+
+ *PIndex = Pjlw[Count]; // Index, base 1.
+
+ JU_RET_FOUND_LEAFW(Pjlw, Pjlw[0] + 1, Count0);
+ }
+ else
+ {
+ Pjpm_t Pjpm = P_JPM(PArray);
+
+ if (Count0 > (Pjpm->jpm_Pop0)) JU_RET_NOTFOUND; // too high.
+
+ Pjp = &(Pjpm->jpm_JP);
+ pop1 = (Pjpm->jpm_Pop0) + 1;
+
+// goto SMByCount;
+ }
+
+// COMMON CODE:
+//
+// Prepare to handle a root-level or lower-level branch: Save the current
+// state, obtain the total population for the branch in a state-dependent way,
+// and then branch to common code for multiple cases.
+//
+// For root-level branches, the state is always cJU_ROOTSTATE, and the array
+// population must already be set in pop1; it is not available in jp_DcdPopO.
+//
+// Note: The total population is only needed in cases where the common code
+// "counts down" instead of up to minimize cache line fills. However, its
+// available cheaply, and its better to do it with a constant shift (constant
+// state value) instead of a variable shift later "when needed".
+
+#define PREPB_ROOT(Next) \
+ state = cJU_ROOTSTATE; \
+ goto Next
+
+// Use PREPB_DCD() to first copy the Dcd bytes to *PIndex if there are any
+// (only if state < cJU_ROOTSTATE - 1):
+
+#define PREPB_DCD(Pjp,cState,Next) \
+ JU_SETDCD(*PIndex, Pjp, cState); \
+ PREPB((Pjp), cState, Next)
+
+#define PREPB(Pjp,cState,Next) \
+ state = (cState); \
+ pop1 = JU_JPBRANCH_POP0(Pjp, (cState)) + 1; \
+ goto Next
+
+// Calculate whether the ordinal of an Index within a given expanse falls in
+// the lower or upper half of the expanses population, taking care with
+// unsigned math and boundary conditions:
+//
+// Note: Assume the ordinal falls within the expanses population, that is,
+// 0 < (Count - Pop1lower) <= Pop1exp (assuming infinite math).
+//
+// Note: If the ordinal is the middle element, it doesnt matter whether
+// LOWERHALF() is TRUE or FALSE.
+
+#define LOWERHALF(Count0,Pop1lower,Pop1exp) \
+ (((Count0) - (Pop1lower)) < ((Pop1exp) / 2))
+
+// Calculate the (signed) offset within a leaf to the desired ordinal (Count -
+// Pop1lower; offset is one less), and optionally ensure its in range:
+
+#define SETOFFSET(Offset,Count0,Pop1lower,Pjp) \
+ (Offset) = (Count0) - (Pop1lower); \
+ assert((Offset) >= 0); \
+ assert((Offset) <= JU_JPLEAF_POP0(Pjp))
+
+// Variations for immediate indexes, with and without pop1-specific assertions:
+
+#define SETOFFSET_IMM_CK(Offset,Count0,Pop1lower,cPop1) \
+ (Offset) = (Count0) - (Pop1lower); \
+ assert((Offset) >= 0); \
+ assert((Offset) < (cPop1))
+
+#define SETOFFSET_IMM(Offset,Count0,Pop1lower) \
+ (Offset) = (Count0) - (Pop1lower)
+
+
+// STATE MACHINE -- TRAVERSE TREE:
+//
+// In branches, look for the expanse (digit), if any, where the total pop1
+// below or at that expanse would meet or exceed Count, meaning the Index must
+// be in this expanse.
+
+SMByCount: // return here for next branch/leaf.
+
+ switch (JU_JPTYPE(Pjp))
+ {
+
+
+// ----------------------------------------------------------------------------
+// LINEAR BRANCH; count populations in JPs in the JBL upwards until finding the
+// expanse (digit) containing Count, and "recurse".
+//
+// Note: There are no null JPs in a JBL; watch out for pop1 == 0.
+//
+// Note: A JBL should always fit in one cache line => no need to count up
+// versus down to save cache line fills.
+//
+// TBD: The previous is no longer true. Consider enhancing this code to count
+// up/down, but it can wait for a later tuning phase. In the meantime, PREPB()
+// sets pop1 for the whole array, but that value is not used here. 001215:
+// Maybe its true again?
+
+ case cJU_JPBRANCH_L2: PREPB_DCD(Pjp, 2, BranchL);
+#ifndef JU_64BIT
+ case cJU_JPBRANCH_L3: PREPB( Pjp, 3, BranchL);
+#else
+ case cJU_JPBRANCH_L3: PREPB_DCD(Pjp, 3, BranchL);
+ case cJU_JPBRANCH_L4: PREPB_DCD(Pjp, 4, BranchL);
+ case cJU_JPBRANCH_L5: PREPB_DCD(Pjp, 5, BranchL);
+ case cJU_JPBRANCH_L6: PREPB_DCD(Pjp, 6, BranchL);
+ case cJU_JPBRANCH_L7: PREPB( Pjp, 7, BranchL);
+#endif
+ case cJU_JPBRANCH_L: PREPB_ROOT( BranchL);
+ {
+ Pjbl_t Pjbl;
+
+// Common code (state-independent) for all cases of linear branches:
+
+BranchL:
+ Pjbl = P_JBL(Pjp->jp_Addr);
+
+ for (jpnum = 0; jpnum < (Pjbl->jbl_NumJPs); ++jpnum)
+ {
+ if ((pop1 = j__udyJPPop1((Pjbl->jbl_jp) + jpnum))
+ == cJU_ALLONES)
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+ assert(pop1 != 0);
+
+// Warning: pop1lower and pop1 are unsigned, so do not subtract 1 and compare
+// >=, but instead use the following expression:
+
+ if (pop1lower + pop1 > Count0) // Index is in this expanse.
+ {
+ JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[jpnum], state);
+ Pjp = (Pjbl->jbl_jp) + jpnum;
+ goto SMByCount; // look under this expanse.
+ }
+
+ pop1lower += pop1; // add this JPs pop1.
+ }
+
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+
+ } // case cJU_JPBRANCH_L
+
+
+// ----------------------------------------------------------------------------
+// BITMAP BRANCH; count populations in JPs in the JBB upwards or downwards
+// until finding the expanse (digit) containing Count, and "recurse".
+//
+// Note: There are no null JPs in a JBB; watch out for pop1 == 0.
+
+ case cJU_JPBRANCH_B2: PREPB_DCD(Pjp, 2, BranchB);
+#ifndef JU_64BIT
+ case cJU_JPBRANCH_B3: PREPB( Pjp, 3, BranchB);
+#else
+ case cJU_JPBRANCH_B3: PREPB_DCD(Pjp, 3, BranchB);
+ case cJU_JPBRANCH_B4: PREPB_DCD(Pjp, 4, BranchB);
+ case cJU_JPBRANCH_B5: PREPB_DCD(Pjp, 5, BranchB);
+ case cJU_JPBRANCH_B6: PREPB_DCD(Pjp, 6, BranchB);
+ case cJU_JPBRANCH_B7: PREPB( Pjp, 7, BranchB);
+#endif
+ case cJU_JPBRANCH_B: PREPB_ROOT( BranchB);
+ {
+ Pjbb_t Pjbb;
+
+// Common code (state-independent) for all cases of bitmap branches:
+
+BranchB:
+ Pjbb = P_JBB(Pjp->jp_Addr);
+
+// Shorthand for one subexpanse in a bitmap and for one JP in a bitmap branch:
+//
+// Note: BMPJP0 exists separately to support assertions.
+
+#define BMPJP0(Subexp) (P_JP(JU_JBB_PJP(Pjbb, Subexp)))
+#define BMPJP(Subexp,JPnum) (BMPJP0(Subexp) + (JPnum))
+
+
+// Common code for descending through a JP:
+//
+// Determine the digit for the expanse and save it in *PIndex; then "recurse".
+
+#define JBB_FOUNDEXPANSE \
+ { \
+ JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb,subexp), jpnum); \
+ JU_SETDIGIT(*PIndex, digit, state); \
+ Pjp = BMPJP(subexp, jpnum); \
+ goto SMByCount; \
+ }
+
+
+#ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
+
+// FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1s
+// in JPs upwards, or subtracting the pop1s in JPs downwards:
+//
+// See header comments about limitations of this for Judy*ByCount().
+
+#endif
+
+// COUNT UPWARD, adding each "below" JPs pop1:
+
+#ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
+
+ if (LOWERHALF(Count0, pop1lower, pop1))
+ {
+#endif
+#ifdef SMARTMETRICS
+ ++jbb_upward;
+#endif
+ for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
+ {
+ if ((jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb,subexp)))
+ && (BMPJP0(subexp) == (Pjp_t) NULL))
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // null ptr.
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+
+// Note: An empty subexpanse (jpcount == 0) is handled "for free":
+
+ for (jpnum = 0; jpnum < jpcount; ++jpnum)
+ {
+ if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum)))
+ == cJU_ALLONES)
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+ assert(pop1 != 0);
+
+// Warning: pop1lower and pop1 are unsigned, see earlier comment:
+
+ if (pop1lower + pop1 > Count0)
+ JBB_FOUNDEXPANSE; // Index is in this expanse.
+
+ pop1lower += pop1; // add this JPs pop1.
+ }
+ }
+#ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes.
+ }
+
+
+// COUNT DOWNWARD, subtracting each "above" JPs pop1 from the whole expanses
+// pop1:
+
+ else
+ {
+#ifdef SMARTMETRICS
+ ++jbb_downward;
+#endif
+ pop1lower += pop1; // add whole branch to start.
+
+ for (subexp = cJU_NUMSUBEXPB - 1; subexp >= 0; --subexp)
+ {
+ if ((jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)))
+ && (BMPJP0(subexp) == (Pjp_t) NULL))
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // null ptr.
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+
+// Note: An empty subexpanse (jpcount == 0) is handled "for free":
+
+ for (jpnum = jpcount - 1; jpnum >= 0; --jpnum)
+ {
+ if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum)))
+ == cJU_ALLONES)
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+ assert(pop1 != 0);
+
+// Warning: pop1lower and pop1 are unsigned, see earlier comment:
+
+ pop1lower -= pop1;
+
+// Beware unsigned math problems:
+
+ if ((pop1lower == 0) || (pop1lower - 1 < Count0))
+ JBB_FOUNDEXPANSE; // Index is in this expanse.
+ }
+ }
+ }
+#endif // NOSMARTJBB
+
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+
+ } // case cJU_JPBRANCH_B
+
+
+// ----------------------------------------------------------------------------
+// UNCOMPRESSED BRANCH; count populations in JPs in the JBU upwards or
+// downwards until finding the expanse (digit) containing Count, and "recurse".
+
+ case cJU_JPBRANCH_U2: PREPB_DCD(Pjp, 2, BranchU);
+#ifndef JU_64BIT
+ case cJU_JPBRANCH_U3: PREPB( Pjp, 3, BranchU);
+#else
+ case cJU_JPBRANCH_U3: PREPB_DCD(Pjp, 3, BranchU);
+ case cJU_JPBRANCH_U4: PREPB_DCD(Pjp, 4, BranchU);
+ case cJU_JPBRANCH_U5: PREPB_DCD(Pjp, 5, BranchU);
+ case cJU_JPBRANCH_U6: PREPB_DCD(Pjp, 6, BranchU);
+ case cJU_JPBRANCH_U7: PREPB( Pjp, 7, BranchU);
+#endif
+ case cJU_JPBRANCH_U: PREPB_ROOT( BranchU);
+ {
+ Pjbu_t Pjbu;
+
+// Common code (state-independent) for all cases of uncompressed branches:
+
+BranchU:
+ Pjbu = P_JBU(Pjp->jp_Addr);
+
+// Common code for descending through a JP:
+//
+// Save the digit for the expanse in *PIndex, then "recurse".
+
+#define JBU_FOUNDEXPANSE \
+ { \
+ JU_SETDIGIT(*PIndex, jpnum, state); \
+ Pjp = (Pjbu->jbu_jp) + jpnum; \
+ goto SMByCount; \
+ }
+
+
+#ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
+
+// FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1s
+// in JPs upwards, or subtracting the pop1s in JPs downwards:
+//
+// See header comments about limitations of this for Judy*ByCount().
+
+#endif
+
+// COUNT UPWARD, simply adding the pop1 of each JP:
+
+#ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
+
+ if (LOWERHALF(Count0, pop1lower, pop1))
+ {
+#endif
+#ifdef SMARTMETRICS
+ ++jbu_upward;
+#endif
+
+ for (jpnum = 0; jpnum < cJU_BRANCHUNUMJPS; ++jpnum)
+ {
+ // shortcut, save a function call:
+
+ if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
+ continue;
+
+ if ((pop1 = j__udyJPPop1((Pjbu->jbu_jp) + jpnum))
+ == cJU_ALLONES)
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+ assert(pop1 != 0);
+
+// Warning: pop1lower and pop1 are unsigned, see earlier comment:
+
+ if (pop1lower + pop1 > Count0)
+ JBU_FOUNDEXPANSE; // Index is in this expanse.
+
+ pop1lower += pop1; // add this JPs pop1.
+ }
+#ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes.
+ }
+
+
+// COUNT DOWNWARD, subtracting the pop1 of each JP above from the whole
+// expanses pop1:
+
+ else
+ {
+#ifdef SMARTMETRICS
+ ++jbu_downward;
+#endif
+ pop1lower += pop1; // add whole branch to start.
+
+ for (jpnum = cJU_BRANCHUNUMJPS - 1; jpnum >= 0; --jpnum)
+ {
+ // shortcut, save a function call:
+
+ if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX)
+ continue;
+
+ if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum))
+ == cJU_ALLONES)
+ {
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+ }
+ assert(pop1 != 0);
+
+// Warning: pop1lower and pop1 are unsigned, see earlier comment:
+
+ pop1lower -= pop1;
+
+// Beware unsigned math problems:
+
+ if ((pop1lower == 0) || (pop1lower - 1 < Count0))
+ JBU_FOUNDEXPANSE; // Index is in this expanse.
+ }
+ }
+#endif // NOSMARTJBU
+
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+
+ } // case cJU_JPBRANCH_U
+
+// ----------------------------------------------------------------------------
+// LINEAR LEAF:
+//
+// Return the Index at the proper ordinal (see SETOFFSET()) in the leaf. First
+// copy Dcd bytes, if there are any (only if state < cJU_ROOTSTATE - 1), to
+// *PIndex.
+//
+// Note: The preceding branch traversal code MIGHT set pop1 for this expanse
+// (linear leaf) as a side-effect, but dont depend on that (for JUDYL, which
+// is the only cases that need it anyway).
+
+#define PREPL_DCD(cState) \
+ JU_SETDCD(*PIndex, Pjp, cState); \
+ PREPL
+
+#ifdef JUDY1
+#define PREPL_SETPOP1 // not needed in any cases.
+#else
+#define PREPL_SETPOP1 pop1 = JU_JPLEAF_POP0(Pjp) + 1
+#endif
+
+#define PREPL \
+ Pjll = P_JLL(Pjp->jp_Addr); \
+ PREPL_SETPOP1; \
+ SETOFFSET(offset, Count0, pop1lower, Pjp)
+
+#if (defined(JUDYL) || (! defined(JU_64BIT)))
+ case cJU_JPLEAF1:
+
+ PREPL_DCD(1);
+ JU_SETDIGIT1(*PIndex, ((uint8_t *) Pjll)[offset]);
+ JU_RET_FOUND_LEAF1(Pjll, pop1, offset);
+#endif
+
+ case cJU_JPLEAF2:
+
+ PREPL_DCD(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;
+ PREPL;
+ 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;
+ PREPL_DCD(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:
+
+ PREPL_DCD(4);
+ *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
+ | ((uint32_t *) Pjll)[offset];
+ JU_RET_FOUND_LEAF4(Pjll, pop1, offset);
+
+ case cJU_JPLEAF5:
+ {
+ Word_t lsb;
+ PREPL_DCD(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;
+ PREPL_DCD(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;
+ PREPL;
+ 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:
+//
+// Return the Index at the proper ordinal (see SETOFFSET()) in the leaf by
+// counting bits. First copy Dcd bytes (always present since state 1 <
+// cJU_ROOTSTATE) to *PIndex.
+//
+// Note: The preceding branch traversal code MIGHT set pop1 for this expanse
+// (bitmap leaf) as a side-effect, but dont depend on that.
+
+ case cJU_JPLEAF_B1:
+ {
+ Pjlb_t Pjlb;
+
+ JU_SETDCD(*PIndex, Pjp, 1);
+ Pjlb = P_JLB(Pjp->jp_Addr);
+ pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+
+// COUNT UPWARD, adding the pop1 of each subexpanse:
+//
+// The entire bitmap should fit in one cache line, but still try to save some
+// CPU time by counting the fewest possible number of subexpanses from the
+// bitmap.
+//
+// See header comments about limitations of this for Judy*ByCount().
+
+#ifndef NOSMARTJLB // enable to turn off smart code for comparison purposes.
+
+ if (LOWERHALF(Count0, pop1lower, pop1))
+ {
+#endif
+#ifdef SMARTMETRICS
+ ++jlb_upward;
+#endif
+ for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
+ {
+ pop1 = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
+
+// Warning: pop1lower and pop1 are unsigned, see earlier comment:
+
+ if (pop1lower + pop1 > Count0)
+ goto LeafB1; // Index is in this subexpanse.
+
+ pop1lower += pop1; // add this subexpanses pop1.
+ }
+#ifndef NOSMARTJLB // enable to turn off smart code for comparison purposes.
+ }
+
+
+// COUNT DOWNWARD, subtracting each "above" subexpanses pop1 from the whole
+// expanses pop1:
+
+ else
+ {
+#ifdef SMARTMETRICS
+ ++jlb_downward;
+#endif
+ pop1lower += pop1; // add whole leaf to start.
+
+ for (subexp = cJU_NUMSUBEXPL - 1; subexp >= 0; --subexp)
+ {
+ pop1lower -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
+
+// Beware unsigned math problems:
+
+ if ((pop1lower == 0) || (pop1lower - 1 < Count0))
+ goto LeafB1; // Index is in this subexpanse.
+ }
+ }
+#endif // NOSMARTJLB
+
+ JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); // should never get here.
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+
+
+// RETURN INDEX FOUND:
+//
+// Come here with subexp set to the correct subexpanse, and pop1lower set to
+// the sum for all lower expanses and subexpanses in the Judy tree. Calculate
+// and save in *PIndex the digit corresponding to the ordinal in this
+// subexpanse.
+
+LeafB1:
+ SETOFFSET(offset, Count0, pop1lower, Pjp);
+ 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 (always present since state 1 < cJU_ROOTSTATE) to *PIndex,
+// then set the appropriate digit for the ordinal (see SETOFFSET()) in the leaf
+// as the LSB in *PIndex.
+
+ case cJ1_JPFULLPOPU1:
+
+ JU_SETDCD(*PIndex, Pjp, 1);
+ SETOFFSET(offset, Count0, pop1lower, Pjp);
+ assert(offset >= 0);
+ assert(offset <= cJU_JPFULLPOPU1_POP0);
+ JU_SETDIGIT1(*PIndex, offset);
+ JU_RET_FOUND_FULLPOPU1;
+#endif
+
+
+// ----------------------------------------------------------------------------
+// IMMEDIATE:
+//
+// Locate the Index with the proper ordinal (see SETOFFSET()) in the Immediate,
+// 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.
+
+#define SET_01(cState) JU_SETDIGITS(*PIndex, JU_JPDCDPOP0(Pjp), cState)
+
+ case cJU_JPIMMED_1_01: SET_01(1); goto Imm_01;
+ case cJU_JPIMMED_2_01: SET_01(2); goto Imm_01;
+ case cJU_JPIMMED_3_01: SET_01(3); goto Imm_01;
+#ifdef JU_64BIT
+ case cJU_JPIMMED_4_01: SET_01(4); goto Imm_01;
+ case cJU_JPIMMED_5_01: SET_01(5); goto Imm_01;
+ case cJU_JPIMMED_6_01: SET_01(6); goto Imm_01;
+ case cJU_JPIMMED_7_01: SET_01(7); goto Imm_01;
+#endif
+
+Imm_01:
+
+ DBGCODE(SETOFFSET_IMM_CK(offset, Count0, pop1lower, 1);)
+ 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
+
+// Optional code to check the remaining ordinal (see SETOFFSET_IMM()) against
+// the Index Size of the Immediate:
+
+#ifndef DEBUG // simple placeholder:
+#define IMM(cPop1,Next) \
+ goto Next
+#else // extra pop1-specific checking:
+#define IMM(cPop1,Next) \
+ SETOFFSET_IMM_CK(offset, Count0, pop1lower, cPop1); \
+ goto Next
+#endif
+
+ case cJU_JPIMMED_1_02: IMM( 2, Imm1);
+ case cJU_JPIMMED_1_03: IMM( 3, Imm1);
+#if (defined(JUDY1) || defined(JU_64BIT))
+ case cJU_JPIMMED_1_04: IMM( 4, Imm1);
+ case cJU_JPIMMED_1_05: IMM( 5, Imm1);
+ case cJU_JPIMMED_1_06: IMM( 6, Imm1);
+ case cJU_JPIMMED_1_07: IMM( 7, Imm1);
+#endif
+#if (defined(JUDY1) && defined(JU_64BIT))
+ case cJ1_JPIMMED_1_08: IMM( 8, Imm1);
+ case cJ1_JPIMMED_1_09: IMM( 9, Imm1);
+ case cJ1_JPIMMED_1_10: IMM(10, Imm1);
+ case cJ1_JPIMMED_1_11: IMM(11, Imm1);
+ case cJ1_JPIMMED_1_12: IMM(12, Imm1);
+ case cJ1_JPIMMED_1_13: IMM(13, Imm1);
+ case cJ1_JPIMMED_1_14: IMM(14, Imm1);
+ case cJ1_JPIMMED_1_15: IMM(15, Imm1);
+#endif
+
+Imm1: SETOFFSET_IMM(offset, Count0, pop1lower);
+ JU_SETDIGIT1(*PIndex, ((uint8_t *) PJI)[offset]);
+ JU_RET_FOUND_IMM(Pjp, offset);
+
+#if (defined(JUDY1) || defined(JU_64BIT))
+ case cJU_JPIMMED_2_02: IMM(2, Imm2);
+ case cJU_JPIMMED_2_03: IMM(3, Imm2);
+#endif
+#if (defined(JUDY1) && defined(JU_64BIT))
+ case cJ1_JPIMMED_2_04: IMM(4, Imm2);
+ case cJ1_JPIMMED_2_05: IMM(5, Imm2);
+ case cJ1_JPIMMED_2_06: IMM(6, Imm2);
+ case cJ1_JPIMMED_2_07: IMM(7, Imm2);
+#endif
+
+#if (defined(JUDY1) || defined(JU_64BIT))
+Imm2: SETOFFSET_IMM(offset, Count0, pop1lower);
+ *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: IMM(2, Imm3);
+#endif
+#if (defined(JUDY1) && defined(JU_64BIT))
+ case cJ1_JPIMMED_3_03: IMM(3, Imm3);
+ case cJ1_JPIMMED_3_04: IMM(4, Imm3);
+ case cJ1_JPIMMED_3_05: IMM(5, Imm3);
+#endif
+
+#if (defined(JUDY1) || defined(JU_64BIT))
+Imm3:
+ {
+ Word_t lsb;
+ SETOFFSET_IMM(offset, Count0, pop1lower);
+ 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: IMM(2, Imm4);
+ case cJ1_JPIMMED_4_03: IMM(3, Imm4);
+
+Imm4: SETOFFSET_IMM(offset, Count0, pop1lower);
+ *PIndex = (*PIndex & (~JU_LEASTBYTESMASK(4)))
+ | ((uint32_t *) PJI)[offset];
+ JU_RET_FOUND_IMM(Pjp, offset);
+
+ case cJ1_JPIMMED_5_02: IMM(2, Imm5);
+ case cJ1_JPIMMED_5_03: IMM(3, Imm5);
+
+Imm5:
+ {
+ Word_t lsb;
+ SETOFFSET_IMM(offset, Count0, pop1lower);
+ 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: IMM(2, Imm6);
+
+Imm6:
+ {
+ Word_t lsb;
+ SETOFFSET_IMM(offset, Count0, pop1lower);
+ 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: IMM(2, Imm7);
+
+Imm7:
+ {
+ Word_t lsb;
+ SETOFFSET_IMM(offset, Count0, pop1lower);
+ 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)
+
+
+// ----------------------------------------------------------------------------
+// UNEXPECTED JP TYPES:
+
+ default: JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+ JUDY1CODE(return(JERRI );)
+ JUDYLCODE(return(PPJERR);)
+
+ } // SMByCount switch.
+
+ /*NOTREACHED*/
+
+} // Judy1ByCount() / JudyLByCount()