summaryrefslogtreecommitdiffstats
path: root/libnetdata/libjudy/src/JudyL/JudyLInsArray.c
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLInsArray.c')
-rw-r--r--libnetdata/libjudy/src/JudyL/JudyLInsArray.c1178
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()