// 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()