diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLInsArray.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyL/JudyLInsArray.c | 1178 |
1 files changed, 1178 insertions, 0 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLInsArray.c b/libnetdata/libjudy/src/JudyL/JudyLInsArray.c new file mode 100644 index 0000000..f8e361f --- /dev/null +++ b/libnetdata/libjudy/src/JudyL/JudyLInsArray.c @@ -0,0 +1,1178 @@ +// 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 +// _________________ + +// TBD: It would probably be faster for the caller if the JudyL version took +// PIndex as an interleaved array of indexes and values rather than just +// indexes with a separate values array (PValue), especially considering +// indexes and values are copied here with for-loops anyway and not the +// equivalent of memcpy(). All code could be revised to simply count by two +// words for JudyL? Supports "streaming" the data to/from disk better later? +// In which case get rid of JU_ERRNO_NULLPVALUE, no longer needed, and simplify +// the API to this code. +// _________________ + +// @(#) $Revision: 4.21 $ $Source: /judy/src/JudyCommon/JudyInsArray.c $ +// +// Judy1SetArray() and JudyLInsArray() functions for Judy1 and JudyL. +// Compile with one of -DJUDY1 or -DJUDYL. + +#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" + +DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);) + + +// IMMED AND LEAF SIZE AND BRANCH TYPE ARRAYS: +// +// These support fast and easy lookup by level. + +static uint8_t immed_maxpop1[] = { + 0, + cJU_IMMED1_MAXPOP1, + cJU_IMMED2_MAXPOP1, + cJU_IMMED3_MAXPOP1, +#ifdef JU_64BIT + cJU_IMMED4_MAXPOP1, + cJU_IMMED5_MAXPOP1, + cJU_IMMED6_MAXPOP1, + cJU_IMMED7_MAXPOP1, +#endif + // note: There are no IMMEDs for whole words. +}; + +static uint8_t leaf_maxpop1[] = { + 0, +#if (defined(JUDYL) || (! defined(JU_64BIT))) + cJU_LEAF1_MAXPOP1, +#else + 0, // 64-bit Judy1 has no Leaf1. +#endif + cJU_LEAF2_MAXPOP1, + cJU_LEAF3_MAXPOP1, +#ifdef JU_64BIT + cJU_LEAF4_MAXPOP1, + cJU_LEAF5_MAXPOP1, + cJU_LEAF6_MAXPOP1, + cJU_LEAF7_MAXPOP1, +#endif + // note: Root-level leaves are handled differently. +}; + +static uint8_t branchL_JPtype[] = { + 0, + 0, + cJU_JPBRANCH_L2, + cJU_JPBRANCH_L3, +#ifdef JU_64BIT + cJU_JPBRANCH_L4, + cJU_JPBRANCH_L5, + cJU_JPBRANCH_L6, + cJU_JPBRANCH_L7, +#endif + cJU_JPBRANCH_L, +}; + +static uint8_t branchB_JPtype[] = { + 0, + 0, + cJU_JPBRANCH_B2, + cJU_JPBRANCH_B3, +#ifdef JU_64BIT + cJU_JPBRANCH_B4, + cJU_JPBRANCH_B5, + cJU_JPBRANCH_B6, + cJU_JPBRANCH_B7, +#endif + cJU_JPBRANCH_B, +}; + +static uint8_t branchU_JPtype[] = { + 0, + 0, + cJU_JPBRANCH_U2, + cJU_JPBRANCH_U3, +#ifdef JU_64BIT + cJU_JPBRANCH_U4, + cJU_JPBRANCH_U5, + cJU_JPBRANCH_U6, + cJU_JPBRANCH_U7, +#endif + cJU_JPBRANCH_U, +}; + +// Subexpanse masks are similer to JU_DCDMASK() but without the need to clear +// the first digits bits. Avoid doing variable shifts by precomputing a +// lookup array. + +static Word_t subexp_mask[] = { + 0, + ~cJU_POP0MASK(1), + ~cJU_POP0MASK(2), + ~cJU_POP0MASK(3), +#ifdef JU_64BIT + ~cJU_POP0MASK(4), + ~cJU_POP0MASK(5), + ~cJU_POP0MASK(6), + ~cJU_POP0MASK(7), +#endif +}; + + +// FUNCTION PROTOTYPES: + +static bool_t j__udyInsArray(Pjp_t PjpParent, int Level, PWord_t PPop1, + PWord_t PIndex, +#ifdef JUDYL + Pjv_t PValue, +#endif + Pjpm_t Pjpm); + + +// **************************************************************************** +// J U D Y 1 S E T A R R A Y +// J U D Y L I N S A R R A Y +// +// Main entry point. See the manual entry for external overview. +// +// TBD: Until thats written, note that the function returns 1 for success or +// JERRI for serious error, including insufficient memory to build whole array; +// use Judy*Count() to see how many were stored, the first N of the total +// Count. Also, since it takes Count == Pop1, it cannot handle a full array. +// Also, "sorted" means ascending without duplicates, otherwise you get the +// "unsorted" error. +// +// The purpose of these functions is to allow rapid construction of a large +// Judy array given a sorted list of indexes (and for JudyL, corresponding +// values). At least one customer saw this as useful, and probably it would +// also be useful as a sufficient workaround for fast(er) unload/reload to/from +// disk. +// +// This code is written recursively for simplicity, until/unless someone +// decides to make it faster and more complex. Hopefully recursion is fast +// enough simply because the function is so much faster than a series of +// Set/Ins calls. + +#ifdef JUDY1 +FUNCTION int Judy1SetArray +#else +FUNCTION int JudyLInsArray +#endif + ( + PPvoid_t PPArray, // in which to insert, initially empty. + Word_t Count, // number of indexes (and values) to insert. +const Word_t * const PIndex, // list of indexes to insert. +#ifdef JUDYL +const Word_t * const PValue, // list of corresponding values. +#endif + PJError_t PJError // optional, for returning error info. + ) +{ + Pjlw_t Pjlw; // new root-level leaf. + Pjlw_t Pjlwindex; // first index in root-level leaf. + int offset; // in PIndex. + + +// CHECK FOR NULL OR NON-NULL POINTER (error by caller): + + if (PPArray == (PPvoid_t) NULL) + { JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY); return(JERRI); } + + if (*PPArray != (Pvoid_t) NULL) + { JU_SET_ERRNO(PJError, JU_ERRNO_NONNULLPARRAY); return(JERRI); } + + if (PIndex == (PWord_t) NULL) + { JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX); return(JERRI); } + +#ifdef JUDYL + if (PValue == (PWord_t) NULL) + { JU_SET_ERRNO(PJError, JU_ERRNO_NULLPVALUE); return(JERRI); } +#endif + + +// HANDLE LARGE COUNT (= POP1) (typical case): +// +// Allocate and initialize a JPM, set the root pointer to point to it, and then +// build the tree underneath it. + +// Common code for unusual error handling when no JPM available: + + if (Count > cJU_LEAFW_MAXPOP1) // too big for root-level leaf. + { + Pjpm_t Pjpm; // new, to allocate. + +// Allocate JPM: + + Pjpm = j__udyAllocJPM(); + JU_CHECKALLOC(Pjpm_t, Pjpm, JERRI); + *PPArray = (Pvoid_t) Pjpm; + +// Set some JPM fields: + + (Pjpm->jpm_Pop0) = Count - 1; + // note: (Pjpm->jpm_TotalMemWords) is now initialized. + +// Build Judy tree: +// +// In case of error save the final Count, possibly modified, unless modified to +// 0, in which case free the JPM itself: + + if (! j__udyInsArray(&(Pjpm->jpm_JP), cJU_ROOTSTATE, &Count, + (PWord_t) PIndex, +#ifdef JUDYL + (Pjv_t) PValue, +#endif + Pjpm)) + { + JU_COPY_ERRNO(PJError, Pjpm); + + if (Count) // partial success, adjust pop0: + { + (Pjpm->jpm_Pop0) = Count - 1; + } + else // total failure, free JPM: + { + j__udyFreeJPM(Pjpm, (Pjpm_t) NULL); + *PPArray = (Pvoid_t) NULL; + } + + DBGCODE(JudyCheckPop(*PPArray);) + return(JERRI); + } + + DBGCODE(JudyCheckPop(*PPArray);) + return(1); + + } // large count + + +// HANDLE SMALL COUNT (= POP1): +// +// First ensure indexes are in sorted order: + + for (offset = 1; offset < Count; ++offset) + { + if (PIndex[offset - 1] >= PIndex[offset]) + { JU_SET_ERRNO(PJError, JU_ERRNO_UNSORTED); return(JERRI); } + } + + if (Count == 0) return(1); // *PPArray remains null. + + { + Pjlw = j__udyAllocJLW(Count + 1); + JU_CHECKALLOC(Pjlw_t, Pjlw, JERRI); + *PPArray = (Pvoid_t) Pjlw; + Pjlw[0] = Count - 1; // set pop0. + Pjlwindex = Pjlw + 1; + } + +// Copy whole-word indexes (and values) to the root-level leaf: + + JU_COPYMEM(Pjlwindex, PIndex, Count); +JUDYLCODE(JU_COPYMEM(JL_LEAFWVALUEAREA(Pjlw, Count), PValue, Count)); + + DBGCODE(JudyCheckPop(*PPArray);) + return(1); + +} // Judy1SetArray() / JudyLInsArray() + + +// **************************************************************************** +// __ J U D Y I N S A R R A Y +// +// Given: +// +// - a pointer to a JP +// +// - the JPs level in the tree, that is, the number of digits left to decode +// in the indexes under the JP (one less than the level of the JPM or branch +// in which the JP resides); cJU_ROOTSTATE on first entry (when JP is the one +// in the JPM), down to 1 for a Leaf1, LeafB1, or FullPop +// +// - a pointer to the number of indexes (and corresponding values) to store in +// this subtree, to modify in case of partial success +// +// - a list of indexes (and for JudyL, corresponding values) to store in this +// subtree +// +// - a JPM for tracking memory usage and returning errors +// +// Recursively build a subtree (immediate indexes, leaf, or branch with +// subtrees) and modify the JP accordingly. On the way down, build a BranchU +// (only) for any expanse with *PPop1 too high for a leaf; on the way out, +// convert the BranchU to a BranchL or BranchB if appropriate. Keep memory +// statistics in the JPM. +// +// Return TRUE for success, or FALSE with error information set in the JPM in +// case of error, in which case leave a partially constructed but healthy tree, +// and modify parent population counts on the way out. +// +// Note: Each call of this function makes all modifications to the PjpParent +// it receives; neither the parent nor child calls do this. + +FUNCTION static bool_t j__udyInsArray( + Pjp_t PjpParent, // parent JP in/under which to store. + int Level, // initial digits remaining to decode. + PWord_t PPop1, // number of indexes to store. + PWord_t PIndex, // list of indexes to store. +#ifdef JUDYL + Pjv_t PValue, // list of corresponding values. +#endif + Pjpm_t Pjpm) // for memory and errors. +{ + Pjp_t Pjp; // lower-level JP. + Word_t Pjbany; // any type of branch. + int levelsub; // actual, of Pjps node, <= Level. + Word_t pop1 = *PPop1; // fast local value. + Word_t pop1sub; // population of one subexpanse. + uint8_t JPtype; // current JP type. + uint8_t JPtype_null; // precomputed value for new branch. + jp_t JPnull; // precomputed for speed. + Pjbu_t PjbuRaw; // constructed BranchU. + Pjbu_t Pjbu; + int digit; // in BranchU. + Word_t digitmask; // for a digit in a BranchU. + Word_t digitshifted; // shifted to correct offset. + Word_t digitshincr; // increment for digitshifted. + int offset; // in PIndex, or a bitmap subexpanse. + int numJPs; // number non-null in a BranchU. + bool_t retval; // to return from this func. +JUDYLCODE(Pjv_t PjvRaw); // destination value area. +JUDYLCODE(Pjv_t Pjv); + + +// MACROS FOR COMMON CODE: +// +// Note: These use function and local parameters from the context. +// Note: Assume newly allocated memory is zeroed. + +// Indicate whether a sorted list of indexes in PIndex, based on the first and +// last indexes in the list using pop1, are in the same subexpanse between +// Level and L_evel: +// +// This can be confusing! Note that SAMESUBEXP(L) == TRUE means the indexes +// are the same through level L + 1, and it says nothing about level L and +// lower; they might be the same or they might differ. +// +// Note: In principle SAMESUBEXP needs a mask for the digits from Level, +// inclusive, to L_evel, exclusive. But in practice, since the indexes are all +// known to be identical above Level, it just uses a mask for the digits +// through L_evel + 1; see subexp_mask[]. + +#define SAMESUBEXP(L_evel) \ + (! ((PIndex[0] ^ PIndex[pop1 - 1]) & subexp_mask[L_evel])) + +// Set PjpParent to a null JP appropriate for the level of the node to which it +// points, which is 1 less than the level of the node in which the JP resides, +// which is by definition Level: +// +// Note: This can set the JPMs JP to an invalid jp_Type, but it doesnt +// matter because the JPM is deleted by the caller. + +#define SETJPNULL_PARENT \ + JU_JPSETADT(PjpParent, 0, 0, cJU_JPNULL1 + Level - 1); + +// Variation to set a specified JP (in a branch being built) to a precomputed +// null JP: + +#define SETJPNULL(Pjp) *(Pjp) = JPnull + +// Handle complete (as opposed to partial) memory allocation failure: Set the +// parent JP to an appropriate null type (to leave a consistent tree), zero the +// callers population count, and return FALSE: +// +// Note: At Level == cJU_ROOTSTATE this sets the JPMs JPs jp_Type to a bogus +// value, but it doesnt matter because the JPM should be deleted by the +// caller. + +#define NOMEM { SETJPNULL_PARENT; *PPop1 = 0; return(FALSE); } + +// Allocate a Leaf1-N and save the address in Pjll; in case of failure, NOMEM: + +#define ALLOCLEAF(AllocLeaf) \ + if ((PjllRaw = AllocLeaf(pop1, Pjpm)) == (Pjll_t) NULL) NOMEM; \ + Pjll = P_JLL(PjllRaw); + +// Copy indexes smaller than words (and values which are whole words) from +// given arrays to immediate indexes or a leaf: +// +// TBD: These macros overlap with some of the code in JudyCascade.c; do some +// merging? That file has functions while these are macros. + +#define COPYTOLEAF_EVEN_SUB(Pjll,LeafType) \ + { \ + LeafType * P_leaf = (LeafType *) (Pjll); \ + Word_t p_op1 = pop1; \ + PWord_t P_Index = PIndex; \ + \ + assert(pop1 > 0); \ + \ + do { *P_leaf++ = *P_Index++; /* truncates */\ + } while (--(p_op1)); \ + } + +#define COPYTOLEAF_ODD_SUB(cLevel,Pjll,Copy) \ + { \ + uint8_t * P_leaf = (uint8_t *) (Pjll); \ + Word_t p_op1 = pop1; \ + PWord_t P_Index = PIndex; \ + \ + assert(pop1 > 0); \ + \ + do { \ + Copy(P_leaf, *P_Index); \ + P_leaf += (cLevel); ++P_Index; \ + } while (--(p_op1)); \ + } + +#ifdef JUDY1 + +#define COPYTOLEAF_EVEN(Pjll,LeafType) COPYTOLEAF_EVEN_SUB(Pjll,LeafType) +#define COPYTOLEAF_ODD(cLevel,Pjll,Copy) COPYTOLEAF_ODD_SUB(cLevel,Pjll,Copy) + +#else // JUDYL adds copying of values: + +#define COPYTOLEAF_EVEN(Pjll,LeafType) \ + { \ + COPYTOLEAF_EVEN_SUB(Pjll,LeafType) \ + JU_COPYMEM(Pjv, PValue, pop1); \ + } + +#define COPYTOLEAF_ODD(cLevel,Pjll,Copy) \ + { \ + COPYTOLEAF_ODD_SUB( cLevel,Pjll,Copy) \ + JU_COPYMEM(Pjv, PValue, pop1); \ + } + +#endif + +// Set the JP type for an immediate index, where BaseJPType is JPIMMED_*_02: + +#define SETIMMTYPE(BaseJPType) (PjpParent->jp_Type) = (BaseJPType) + pop1 - 2 + +// Allocate and populate a Leaf1-N: +// +// Build MAKELEAF_EVEN() and MAKELEAF_ODD() using macros for common code. + +#define MAKELEAF_SUB1(AllocLeaf,ValueArea,LeafType) \ + ALLOCLEAF(AllocLeaf); \ + JUDYLCODE(Pjv = ValueArea(Pjll, pop1)) + + +#define MAKELEAF_SUB2(cLevel,JPType) \ +{ \ + Word_t D_cdP0; \ + assert(pop1 - 1 <= cJU_POP0MASK(cLevel)); \ + D_cdP0 = (*PIndex & cJU_DCDMASK(cLevel)) | (pop1 - 1); \ + JU_JPSETADT(PjpParent, (Word_t)PjllRaw, D_cdP0, JPType); \ +} + + +#define MAKELEAF_EVEN(cLevel,JPType,AllocLeaf,ValueArea,LeafType) \ + MAKELEAF_SUB1(AllocLeaf,ValueArea,LeafType); \ + COPYTOLEAF_EVEN(Pjll, LeafType); \ + MAKELEAF_SUB2(cLevel, JPType) + +#define MAKELEAF_ODD(cLevel,JPType,AllocLeaf,ValueArea,Copy) \ + MAKELEAF_SUB1(AllocLeaf,ValueArea,LeafType); \ + COPYTOLEAF_ODD(cLevel, Pjll, Copy); \ + MAKELEAF_SUB2(cLevel, JPType) + +// Ensure that the indexes to be stored in immediate indexes or a leaf are +// sorted: +// +// This check is pure overhead, but required in order to protect the Judy array +// against caller error, to avoid a later corruption or core dump from a +// seemingly valid Judy array. Do this check piecemeal at the leaf level while +// the indexes are already in the cache. Higher-level order-checking occurs +// while building branches. +// +// Note: Any sorting error in the expanse of a single immediate indexes JP or +// a leaf => save no indexes in that expanse. + +#define CHECKLEAFORDER \ + { \ + for (offset = 1; offset < pop1; ++offset) \ + { \ + if (PIndex[offset - 1] >= PIndex[offset]) \ + { \ + SETJPNULL_PARENT; \ + *PPop1 = 0; \ + JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED); \ + return(FALSE); \ + } \ + } \ + } + + +// ------ START OF CODE ------ + + assert( Level >= 1); + assert( Level <= cJU_ROOTSTATE); + assert((Level < cJU_ROOTSTATE) || (pop1 > cJU_LEAFW_MAXPOP1)); + + +// CHECK FOR TOP LEVEL: +// +// Special case: If at the top level (PjpParent is in the JPM), a top-level +// branch must be created, even if its a BranchL with just one JP. (The JPM +// cannot point to a leaf because the leaf would have to be a lower-level, +// higher-capacity leaf under a narrow pointer (otherwise a root-level leaf +// would suffice), and the JPMs JP cant handle a narrow pointer because the +// jp_DcdPopO field isnt big enough.) Otherwise continue to check for a pop1 +// small enough to support immediate indexes or a leaf before giving up and +// making a lower-level branch. + + if (Level == cJU_ROOTSTATE) + { + levelsub = cJU_ROOTSTATE; + goto BuildBranch2; + } + assert(Level < cJU_ROOTSTATE); + + +// SKIP JPIMMED_*_01: +// +// Immeds with pop1 == 1 should be handled in-line during branch construction. + + assert(pop1 > 1); + + +// BUILD JPIMMED_*_02+: +// +// The starting address of the indexes depends on Judy1 or JudyL; also, JudyL +// includes a pointer to a values-only leaf. + + if (pop1 <= immed_maxpop1[Level]) // note: always < root level. + { + JUDY1CODE(uint8_t * Pjll = (uint8_t *) (PjpParent->jp_1Index);) + JUDYLCODE(uint8_t * Pjll = (uint8_t *) (PjpParent->jp_LIndex);) + + CHECKLEAFORDER; // indexes to be stored are sorted. + +#ifdef JUDYL + if ((PjvRaw = j__udyLAllocJV(pop1, Pjpm)) == (Pjv_t) NULL) + NOMEM; + (PjpParent->jp_Addr) = (Word_t) PjvRaw; + Pjv = P_JV(PjvRaw); +#endif + + switch (Level) + { + case 1: COPYTOLEAF_EVEN(Pjll, uint8_t); + SETIMMTYPE(cJU_JPIMMED_1_02); + break; +#if (defined(JUDY1) || defined(JU_64BIT)) + case 2: COPYTOLEAF_EVEN(Pjll, uint16_t); + SETIMMTYPE(cJU_JPIMMED_2_02); + break; + case 3: COPYTOLEAF_ODD(3, Pjll, JU_COPY3_LONG_TO_PINDEX); + SETIMMTYPE(cJU_JPIMMED_3_02); + break; +#endif +#if (defined(JUDY1) && defined(JU_64BIT)) + case 4: COPYTOLEAF_EVEN(Pjll, uint32_t); + SETIMMTYPE(cJ1_JPIMMED_4_02); + break; + case 5: COPYTOLEAF_ODD(5, Pjll, JU_COPY5_LONG_TO_PINDEX); + SETIMMTYPE(cJ1_JPIMMED_5_02); + break; + case 6: COPYTOLEAF_ODD(6, Pjll, JU_COPY6_LONG_TO_PINDEX); + SETIMMTYPE(cJ1_JPIMMED_6_02); + break; + case 7: COPYTOLEAF_ODD(7, Pjll, JU_COPY7_LONG_TO_PINDEX); + SETIMMTYPE(cJ1_JPIMMED_7_02); + break; +#endif + default: assert(FALSE); // should be impossible. + } + + return(TRUE); // note: no children => no *PPop1 mods. + + } // JPIMMED_*_02+ + + +// BUILD JPLEAF*: +// +// This code is a little tricky. The method is: For each level starting at +// the present Level down through levelsub = 1, and then as a special case for +// LeafB1 and FullPop (which are also at levelsub = 1 but have different +// capacity, see later), check if pop1 fits in a leaf (using leaf_maxpop1[]) +// at that level. If so, except for Level == levelsub, check if all of the +// current indexes to be stored are in the same (narrow) subexpanse, that is, +// the digits from Level to levelsub + 1, inclusive, are identical between the +// first and last index in the (sorted) list (in PIndex). If this condition is +// satisfied at any level, build a leaf at that level (under a narrow pointer +// if Level > levelsub). +// +// Note: Doing the search in this order results in storing the indexes in +// "least compressed form." + + for (levelsub = Level; levelsub >= 1; --levelsub) + { + Pjll_t PjllRaw; + Pjll_t Pjll; + +// Check if pop1 is too large to fit in a leaf at levelsub; if so, try the next +// lower level: + + if (pop1 > leaf_maxpop1[levelsub]) continue; + +// If pop1 fits in a leaf at levelsub, but levelsub is lower than Level, must +// also check whether all the indexes in the expanse to store can in fact be +// placed under a narrow pointer; if not, a leaf cannot be used, at this or any +// lower level (levelsub): + + if ((levelsub < Level) && (! SAMESUBEXP(levelsub))) + goto BuildBranch; // cant use a narrow, need a branch. + +// Ensure valid pop1 and all indexes are in fact common through Level: + + assert(pop1 <= cJU_POP0MASK(Level) + 1); + assert(! ((PIndex[0] ^ PIndex[pop1 - 1]) & cJU_DCDMASK(Level))); + + CHECKLEAFORDER; // indexes to be stored are sorted. + +// Build correct type of leaf: +// +// Note: The jp_DcdPopO and jp_Type assignments in MAKELEAF_* happen correctly +// for the levelsub (not Level) of the new leaf, even if its under a narrow +// pointer. + + switch (levelsub) + { +#if (defined(JUDYL) || (! defined(JU_64BIT))) + case 1: MAKELEAF_EVEN(1, cJU_JPLEAF1, j__udyAllocJLL1, + JL_LEAF1VALUEAREA, uint8_t); + break; +#endif + case 2: MAKELEAF_EVEN(2, cJU_JPLEAF2, j__udyAllocJLL2, + JL_LEAF2VALUEAREA, uint16_t); + break; + case 3: MAKELEAF_ODD( 3, cJU_JPLEAF3, j__udyAllocJLL3, + JL_LEAF3VALUEAREA, JU_COPY3_LONG_TO_PINDEX); + break; +#ifdef JU_64BIT + case 4: MAKELEAF_EVEN(4, cJU_JPLEAF4, j__udyAllocJLL4, + JL_LEAF4VALUEAREA, uint32_t); + break; + case 5: MAKELEAF_ODD( 5, cJU_JPLEAF5, j__udyAllocJLL5, + JL_LEAF5VALUEAREA, JU_COPY5_LONG_TO_PINDEX); + break; + case 6: MAKELEAF_ODD( 6, cJU_JPLEAF6, j__udyAllocJLL6, + JL_LEAF6VALUEAREA, JU_COPY6_LONG_TO_PINDEX); + break; + case 7: MAKELEAF_ODD( 7, cJU_JPLEAF7, j__udyAllocJLL7, + JL_LEAF7VALUEAREA, JU_COPY7_LONG_TO_PINDEX); + break; +#endif + default: assert(FALSE); // should be impossible. + } + + return(TRUE); // note: no children => no *PPop1 mods. + + } // JPLEAF* + + +// BUILD JPLEAF_B1 OR JPFULLPOPU1: +// +// See above about JPLEAF*. If pop1 doesnt fit in any level of linear leaf, +// it might still fit in a LeafB1 or FullPop, perhaps under a narrow pointer. + + if ((Level == 1) || SAMESUBEXP(1)) // same until last digit. + { + Pjlb_t PjlbRaw; // for bitmap leaf. + Pjlb_t Pjlb; + + assert(pop1 <= cJU_JPFULLPOPU1_POP0 + 1); + CHECKLEAFORDER; // indexes to be stored are sorted. + +#ifdef JUDY1 + +// JPFULLPOPU1: + + if (pop1 == cJU_JPFULLPOPU1_POP0 + 1) + { + Word_t Addr = PjpParent->jp_Addr; + Word_t DcdP0 = (*PIndex & cJU_DCDMASK(1)) + | cJU_JPFULLPOPU1_POP0; + JU_JPSETADT(PjpParent, Addr, DcdP0, cJ1_JPFULLPOPU1); + + return(TRUE); + } +#endif + +// JPLEAF_B1: + + if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL) + NOMEM; + Pjlb = P_JLB(PjlbRaw); + + for (offset = 0; offset < pop1; ++offset) + JU_BITMAPSETL(Pjlb, PIndex[offset]); + + retval = TRUE; // default. + +#ifdef JUDYL + +// Build subexpanse values-only leaves (LeafVs) under LeafB1: + + for (offset = 0; offset < cJU_NUMSUBEXPL; ++offset) + { + if (! (pop1sub = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, offset)))) + continue; // skip empty subexpanse. + +// Allocate one LeafV = JP subarray; if out of memory, clear bitmaps for higher +// subexpanses and adjust *PPop1: + + if ((PjvRaw = j__udyLAllocJV(pop1sub, Pjpm)) + == (Pjv_t) NULL) + { + for (/* null */; offset < cJU_NUMSUBEXPL; ++offset) + { + *PPop1 -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, offset)); + JU_JLB_BITMAP(Pjlb, offset) = 0; + } + + retval = FALSE; + break; + } + +// Populate values-only leaf and save the pointer to it: + + Pjv = P_JV(PjvRaw); + JU_COPYMEM(Pjv, PValue, pop1sub); + JL_JLB_PVALUE(Pjlb, offset) = PjvRaw; // first-tier pointer. + PValue += pop1sub; + + } // for each subexpanse + +#endif // JUDYL + +// Attach new LeafB1 to parent JP; note use of *PPop1 possibly < pop1: + + JU_JPSETADT(PjpParent, (Word_t) PjlbRaw, + (*PIndex & cJU_DCDMASK(1)) | (*PPop1 - 1), cJU_JPLEAF_B1); + + return(retval); + + } // JPLEAF_B1 or JPFULLPOPU1 + + +// BUILD JPBRANCH_U*: +// +// Arriving at BuildBranch means Level < top level but the pop1 is too large +// for immediate indexes or a leaf, even under a narrow pointer, including a +// LeafB1 or FullPop at level 1. This implies SAMESUBEXP(1) == FALSE, that is, +// the indexes to be stored "branch" at level 2 or higher. + +BuildBranch: // come here directly if a leaf wont work. + + assert(Level >= 2); + assert(Level < cJU_ROOTSTATE); + assert(! SAMESUBEXP(1)); // sanity check, see above. + +// Determine the appropriate level for a new branch node; see if a narrow +// pointer can be used: +// +// This can be confusing. The branch is required at the lowest level L where +// the indexes to store are not in the same subexpanse at level L-1. Work down +// from Level to tree level 3, which is 1 above the lowest tree level = 2 at +// which a branch can be used. Theres no need to check SAMESUBEXP at level 2 +// because its known to be false at level 2-1 = 1. +// +// Note: Unlike for a leaf node, a narrow pointer is always used for a branch +// if possible, that is, maximum compression is always used, except at the top +// level of the tree, where a JPM cannot support a narrow pointer, meaning a +// top BranchL can have a single JP (fanout = 1); but that case jumps directly +// to BuildBranch2. +// +// Note: For 32-bit systems the only usable values for a narrow pointer are +// Level = 3 and levelsub = 2; 64-bit systems have many more choices; but +// hopefully this for-loop is fast enough even on a 32-bit system. +// +// TBD: If not fast enough, #ifdef JU_64BIT and handle the 32-bit case faster. + + for (levelsub = Level; levelsub >= 3; --levelsub) // see above. + if (! SAMESUBEXP(levelsub - 1)) // at limit of narrow pointer. + break; // put branch at levelsub. + +BuildBranch2: // come here directly for Level = levelsub = cJU_ROOTSTATE. + + assert(levelsub >= 2); + assert(levelsub <= Level); + +// Initially build a BranchU: +// +// Always start with a BranchU because the number of populated subexpanses is +// not yet known. Use digitmask, digitshifted, and digitshincr to avoid +// expensive variable shifts within JU_DIGITATSTATE within the loop. +// +// TBD: The use of digitmask, etc. results in more increment operations per +// loop, is there an even faster way? +// +// TBD: Would it pay to pre-count the populated JPs (subexpanses) and +// pre-compress the branch, that is, build a BranchL or BranchB immediately, +// also taking account of opportunistic uncompression rules? Probably not +// because at high levels of the tree there might be huge numbers of indexes +// (hence cache lines) to scan in the PIndex array to determine the fanout +// (number of JPs) needed. + + if ((PjbuRaw = j__udyAllocJBU(Pjpm)) == (Pjbu_t) NULL) NOMEM; + Pjbu = P_JBU(PjbuRaw); + + JPtype_null = cJU_JPNULL1 + levelsub - 2; // in new BranchU. + JU_JPSETADT(&JPnull, 0, 0, JPtype_null); + + Pjp = Pjbu->jbu_jp; // for convenience in loop. + numJPs = 0; // non-null in the BranchU. + digitmask = cJU_MASKATSTATE(levelsub); // see above. + digitshincr = 1UL << (cJU_BITSPERBYTE * (levelsub - 1)); + retval = TRUE; + +// Scan and populate JPs (subexpanses): +// +// Look for all indexes matching each digit in the BranchU (at the correct +// levelsub), and meanwhile notice any sorting error. Increment PIndex (and +// PValue) and reduce pop1 for each subexpanse handled successfully. + + for (digit = digitshifted = 0; + digit < cJU_BRANCHUNUMJPS; + ++digit, digitshifted += digitshincr, ++Pjp) + { + DBGCODE(Word_t pop1subprev;) + assert(pop1 != 0); // end of indexes is handled elsewhere. + +// Count indexes in digits subexpanse: + + for (pop1sub = 0; pop1sub < pop1; ++pop1sub) + if (digitshifted != (PIndex[pop1sub] & digitmask)) break; + +// Empty subexpanse (typical, performance path) or sorting error (rare): + + if (pop1sub == 0) + { + if (digitshifted < (PIndex[0] & digitmask)) + { SETJPNULL(Pjp); continue; } // empty subexpanse. + + assert(pop1 < *PPop1); // did save >= 1 index and decr pop1. + JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED); + goto AbandonBranch; + } + +// Non-empty subexpanse: +// +// First shortcut by handling pop1sub == 1 (JPIMMED_*_01) inline locally. + + if (pop1sub == 1) // note: can be at root level. + { + Word_t Addr = 0; + JUDYLCODE(Addr = (Word_t) (*PValue++);) + JU_JPSETADT(Pjp, Addr, *PIndex, cJU_JPIMMED_1_01 + levelsub -2); + + ++numJPs; + + if (--pop1) { ++PIndex; continue; } // more indexes to store. + + ++digit; ++Pjp; // skip JP just saved. + goto ClearBranch; // save time. + } + +// Recurse to populate one digits (subexpanses) JP; if successful, skip +// indexes (and values) just stored (performance path), except when expanse is +// completely stored: + + DBGCODE(pop1subprev = pop1sub;) + + if (j__udyInsArray(Pjp, levelsub - 1, &pop1sub, (PWord_t) PIndex, +#ifdef JUDYL + (Pjv_t) PValue, +#endif + Pjpm)) + { // complete success. + ++numJPs; + assert(pop1subprev == pop1sub); + assert(pop1 >= pop1sub); + + if ((pop1 -= pop1sub) != 0) // more indexes to store: + { + PIndex += pop1sub; // skip indexes just stored. + JUDYLCODE(PValue += pop1sub;) + continue; + } + // else leave PIndex in BranchUs expanse. + +// No more indexes to store in BranchUs expanse: + + ++digit; ++Pjp; // skip JP just saved. + goto ClearBranch; // save time. + } + +// Handle any error at a lower level of recursion: +// +// In case of partial success, pop1sub != 0, but it was reduced from the value +// passed to j__udyInsArray(); skip this JP later during ClearBranch. + + assert(pop1subprev > pop1sub); // check j__udyInsArray(). + assert(pop1 > pop1sub); // check j__udyInsArray(). + + if (pop1sub) // partial success. + { ++digit; ++Pjp; ++numJPs; } // skip JP just saved. + + pop1 -= pop1sub; // deduct saved indexes if any. + +// Same-level sorting error, or any lower-level error; abandon the rest of the +// branch: +// +// Arrive here with pop1 = remaining unsaved indexes (always non-zero). Adjust +// the *PPop1 value to record and return, modify retval, and use ClearBranch to +// finish up. + +AbandonBranch: + assert(pop1 != 0); // more to store, see above. + assert(pop1 <= *PPop1); // sanity check. + + *PPop1 -= pop1; // deduct unsaved indexes. + pop1 = 0; // to avoid error later. + retval = FALSE; + +// Error (rare), or end of indexes while traversing new BranchU (performance +// path); either way, mark the remaining JPs, if any, in the BranchU as nulls +// and exit the loop: +// +// Arrive here with digit and Pjp set to the first JP to set to null. + +ClearBranch: + for (/* null */; digit < cJU_BRANCHUNUMJPS; ++digit, ++Pjp) + SETJPNULL(Pjp); + break; // saves one more compare. + + } // for each digit + + +// FINISH JPBRANCH_U*: +// +// Arrive here with a BranchU built under Pjbu, numJPs set, and either: retval +// == TRUE and *PPop1 unmodified, or else retval == FALSE, *PPop1 set to the +// actual number of indexes saved (possibly 0 for complete failure at a lower +// level upon the first call of j__udyInsArray()), and the Judy error set in +// Pjpm. Either way, PIndex points to an index within the expanse just +// handled. + + Pjbany = (Word_t) PjbuRaw; // default = use this BranchU. + JPtype = branchU_JPtype[levelsub]; + +// Check for complete failure above: + + assert((! retval) || *PPop1); // sanity check. + + if ((! retval) && (*PPop1 == 0)) // nothing stored, full failure. + { + j__udyFreeJBU(PjbuRaw, Pjpm); + SETJPNULL_PARENT; + return(FALSE); + } + +// Complete or partial success so far; watch for sorting error after the +// maximum digit (255) in the BranchU, which is indicated by having more +// indexes to store in the BranchUs expanse: +// +// For example, if an index to store has a digit of 255 at levelsub, followed +// by an index with a digit of 254, the for-loop above runs out of digits +// without reducing pop1 to 0. + + if (pop1 != 0) + { + JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED); + *PPop1 -= pop1; // deduct unsaved indexes. + retval = FALSE; + } + assert(*PPop1 != 0); // branch (still) cannot be empty. + + +// OPTIONALLY COMPRESS JPBRANCH_U*: +// +// See if the BranchU should be compressed to a BranchL or BranchB; if so, do +// that and free the BranchU; otherwise just use the existing BranchU. Follow +// the same rules as in JudyIns.c (version 4.95): Only check local population +// (cJU_OPP_UNCOMP_POP0) for BranchL, and only check global memory efficiency +// (JU_OPP_UNCOMPRESS) for BranchB. TBD: Have the rules changed? +// +// Note: Because of differing order of operations, the latter compression +// might not result in the same set of branch nodes as a series of sequential +// insertions. +// +// Note: Allocating a BranchU only to sometimes convert it to a BranchL or +// BranchB is unfortunate, but attempting to work with a temporary BranchU on +// the stack and then allocate and keep it as a BranchU in many cases is worse +// in terms of error handling. + + +// COMPRESS JPBRANCH_U* TO JPBRANCH_L*: + + if (numJPs <= cJU_BRANCHLMAXJPS) // JPs fit in a BranchL. + { + Pjbl_t PjblRaw = (Pjbl_t) NULL; // new BranchL; init for cc. + Pjbl_t Pjbl; + + if ((*PPop1 > JU_BRANCHL_MAX_POP) // pop too high. + || ((PjblRaw = j__udyAllocJBL(Pjpm)) == (Pjbl_t) NULL)) + { // cant alloc BranchL. + goto SetParent; // just keep BranchU. + } + + Pjbl = P_JBL(PjblRaw); + +// Copy BranchU JPs to BranchL: + + (Pjbl->jbl_NumJPs) = numJPs; + offset = 0; + + for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit) + { + if ((((Pjbu->jbu_jp) + digit)->jp_Type) == JPtype_null) + continue; + + (Pjbl->jbl_Expanse[offset ]) = digit; + (Pjbl->jbl_jp [offset++]) = Pjbu->jbu_jp[digit]; + } + assert(offset == numJPs); // found same number. + +// Free the BranchU and prepare to use the new BranchL instead: + + j__udyFreeJBU(PjbuRaw, Pjpm); + + Pjbany = (Word_t) PjblRaw; + JPtype = branchL_JPtype[levelsub]; + + } // compress to BranchL + + +// COMPRESS JPBRANCH_U* TO JPBRANCH_B*: +// +// If unable to allocate the BranchB or any JP subarray, free all related +// memory and just keep the BranchU. +// +// Note: This use of JU_OPP_UNCOMPRESS is a bit conservative because the +// BranchU is already allocated while the (presumably smaller) BranchB is not, +// the opposite of how its used in single-insert code. + + else + { + Pjbb_t PjbbRaw = (Pjbb_t) NULL; // new BranchB; init for cc. + Pjbb_t Pjbb; + Pjp_t Pjp2; // in BranchU. + + if ((*PPop1 > JU_BRANCHB_MAX_POP) // pop too high. + || ((PjbbRaw = j__udyAllocJBB(Pjpm)) == (Pjbb_t) NULL)) + { // cant alloc BranchB. + goto SetParent; // just keep BranchU. + } + + Pjbb = P_JBB(PjbbRaw); + +// Set bits in bitmap for populated subexpanses: + + Pjp2 = Pjbu->jbu_jp; + + for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit) + if ((((Pjbu->jbu_jp) + digit)->jp_Type) != JPtype_null) + JU_BITMAPSETB(Pjbb, digit); + +// Copy non-null JPs to BranchB JP subarrays: + + for (offset = 0; offset < cJU_NUMSUBEXPB; ++offset) + { + Pjp_t PjparrayRaw; + Pjp_t Pjparray; + + if (! (numJPs = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, offset)))) + continue; // skip empty subexpanse. + +// If unable to allocate a JP subarray, free all BranchB memory so far and +// continue to use the BranchU: + + if ((PjparrayRaw = j__udyAllocJBBJP(numJPs, Pjpm)) + == (Pjp_t) NULL) + { + while (offset-- > 0) + { + if (JU_JBB_PJP(Pjbb, offset) == (Pjp_t) NULL) continue; + + j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, offset), + j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, offset)), + Pjpm); + } + j__udyFreeJBB(PjbbRaw, Pjpm); + goto SetParent; // keep BranchU. + } + +// Set one JP subarray pointer and copy the subexpanses JPs to the subarray: +// +// Scan the BranchU for non-null JPs until numJPs JPs are copied. + + JU_JBB_PJP(Pjbb, offset) = PjparrayRaw; + Pjparray = P_JP(PjparrayRaw); + + while (numJPs-- > 0) + { + while ((Pjp2->jp_Type) == JPtype_null) + { + ++Pjp2; + assert(Pjp2 < (Pjbu->jbu_jp) + cJU_BRANCHUNUMJPS); + } + *Pjparray++ = *Pjp2++; + } + } // for each subexpanse + +// Free the BranchU and prepare to use the new BranchB instead: + + j__udyFreeJBU(PjbuRaw, Pjpm); + + Pjbany = (Word_t) PjbbRaw; + JPtype = branchB_JPtype[levelsub]; + + } // compress to BranchB + + +// COMPLETE OR PARTIAL SUCCESS: +// +// Attach new branch (under Pjp, with JPtype) to parent JP; note use of *PPop1, +// possibly reduced due to partial failure. + +SetParent: + (PjpParent->jp_Addr) = Pjbany; + (PjpParent->jp_Type) = JPtype; + + if (Level < cJU_ROOTSTATE) // PjpParent not in JPM: + { + Word_t DcdP0 = (*PIndex & cJU_DCDMASK(levelsub)) | (*PPop1 - 1); + + JU_JPSETADT(PjpParent ,Pjbany, DcdP0, JPtype); + } + + return(retval); + +} // j__udyInsArray() |