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