Merging upstream version 1.45.3+dfsg.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 0 insertions, 1178 deletions

diff --git a/libnetdata/libjudy/src/JudyL/JudyLInsArray.c b/libnetdata/libjudy/src/JudyL/JudyLInsArray.c
deleted file mode 100644
index f8e361f27..000000000
--- a/libnetdata/libjudy/src/JudyL/JudyLInsArray.c
+++ /dev/null
@@ -1,1178 +0,0 @@
-// 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()