path: root/libnetdata/libjudy/src/JudyL/JudyLInsArray.c

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