path: root/libnetdata/libjudy/src/JudyL/JudyLIns.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
// _________________

// @(#) $Revision: 4.116 $ $Source: /judy/src/JudyCommon/JudyIns.c $
//
// Judy1Set() and JudyLIns() functions for Judy1 and JudyL.
// Compile with one of -DJUDY1 or -DJUDYL.
//
// TBD:  Should some of the assertions here be converted to product code that
// returns JU_ERRNO_CORRUPT?

#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"

// Note:  Call JudyCheckPop() even before "already inserted" returns, to catch
// population errors; see fix in 4.84:

DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)
DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)

#ifdef TRACEJP
#include "JudyPrintJP.c"
#endif


// These are defined to generic values in JudyCommon/JudyPrivateTypes.h:
//
// TBD:  These should be exported from a header file, but perhaps not, as they
// are only used here, and exported from Judy*Decascade, which is a separate
// file for profiling reasons (to prevent inlining), but which potentially
// could be merged with this file, either in SoftCM or at compile-time.

#ifdef JUDY1
extern int j__udy1CreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
extern int j__udy1CreateBranchU(Pjp_t, Pvoid_t);

#ifndef JU_64BIT
extern int j__udy1Cascade1(Pjp_t, Pvoid_t);
#endif
extern int j__udy1Cascade2(Pjp_t, Pvoid_t);
extern int j__udy1Cascade3(Pjp_t, Pvoid_t);
#ifdef JU_64BIT
extern int j__udy1Cascade4(Pjp_t, Pvoid_t);
extern int j__udy1Cascade5(Pjp_t, Pvoid_t);
extern int j__udy1Cascade6(Pjp_t, Pvoid_t);
extern int j__udy1Cascade7(Pjp_t, Pvoid_t);
#endif
extern int j__udy1CascadeL(Pjp_t, Pvoid_t);

extern int j__udy1InsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);

#else // JUDYL

extern int j__udyLCreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
extern int j__udyLCreateBranchU(Pjp_t, Pvoid_t);

extern int j__udyLCascade1(Pjp_t, Pvoid_t);
extern int j__udyLCascade2(Pjp_t, Pvoid_t);
extern int j__udyLCascade3(Pjp_t, Pvoid_t);
#ifdef JU_64BIT
extern int j__udyLCascade4(Pjp_t, Pvoid_t);
extern int j__udyLCascade5(Pjp_t, Pvoid_t);
extern int j__udyLCascade6(Pjp_t, Pvoid_t);
extern int j__udyLCascade7(Pjp_t, Pvoid_t);
#endif
extern int j__udyLCascadeL(Pjp_t, Pvoid_t);

extern int j__udyLInsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);
#endif


// ****************************************************************************
// MACROS FOR COMMON CODE:
//
// Check if Index is an outlier to (that is, not a member of) this expanse:
//
// An outlier is an Index in-the-expanse of the slot containing the pointer,
// but not-in-the-expanse of the "narrow" pointer in that slot.  (This means
// the Dcd part of the Index differs from the equivalent part of jp_DcdPopO.)
// Therefore, the remedy is to put a cJU_JPBRANCH_L* between the narrow pointer
// and the object to which it points, and add the outlier Index as an Immediate
// in the cJU_JPBRANCH_L*.  The "trick" is placing the cJU_JPBRANCH_L* at a
// Level that is as low as possible.  This is determined by counting the digits
// in the existing narrow pointer that are the same as the digits in the new
// Index (see j__udyInsertBranch()).
//
// Note:  At some high Levels, cJU_DCDMASK() is all zeros => dead code; assume
// the compiler optimizes this out.

#define JU_CHECK_IF_OUTLIER(Pjp, Index, cLevel, Pjpm)                   \
        if (JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel))                    \
            return(j__udyInsertBranch(Pjp, Index, cLevel, Pjpm))

// Check if an Index is already in a leaf or immediate, after calling
// j__udySearchLeaf*() to set Offset:
//
// A non-negative Offset means the Index already exists, so return 0; otherwise
// complement Offset to proceed.

#ifdef JUDY1
#define Pjv ignore                                      // placeholder.
#define JU_CHECK_IF_EXISTS(Offset,ignore,Pjpm)  \
        {                                       \
            if ((Offset) >= 0) return(0);       \
            (Offset) = ~(Offset);               \
        }
#else
// For JudyL, also set the value area pointer in the Pjpm:

#define JU_CHECK_IF_EXISTS(Offset,Pjv,Pjpm)             \
        {                                               \
            if ((Offset) >= 0)                          \
            {                                           \
                (Pjpm)->jpm_PValue = (Pjv) + (Offset);  \
                return(0);                              \
            }                                           \
            (Offset) = ~(Offset);                       \
        }
#endif


// ****************************************************************************
// __ J U D Y   I N S   W A L K
//
// Walk the Judy tree to do a set/insert.  This is only called internally, and
// recursively.  Unlike Judy1Test() and JudyLGet(), the extra time required for
// recursion should be negligible compared with the total.
//
// Return -1 for error (details in JPM), 0 for Index already inserted, 1 for
// new Index inserted.

FUNCTION static int j__udyInsWalk(
        Pjp_t   Pjp,            // current JP to descend.
        Word_t  Index,          // to insert.
        Pjpm_t  Pjpm)           // for returning info to top Level.
{
        uint8_t digit;          // from Index, current offset into a branch.
        jp_t    newJP;          // for creating a new Immed JP.
        Word_t  exppop1;        // expanse (leaf) population.
        int     retcode;        // return codes:  -1, 0, 1.

#ifdef SUBEXPCOUNTS
// Pointer to BranchB/U subexpanse counter:
//
// Note:  Very important for performance reasons (avoids cache fills).

        PWord_t PSubExp = (PWord_t) NULL;
#endif

ContinueInsWalk:                // for modifying state without recursing.

#ifdef TRACEJP
        JudyPrintJP(Pjp, "i", __LINE__);
#endif

        switch (JU_JPTYPE(Pjp)) // entry:  Pjp, Index.
        {


// ****************************************************************************
// JPNULL*:
//
// Convert JP in place from current null type to cJU_JPIMMED_*_01 by
// calculating new JP type.

        case cJU_JPNULL1:
        case cJU_JPNULL2:
        case cJU_JPNULL3:
#ifdef JU_64BIT
        case cJU_JPNULL4:
        case cJU_JPNULL5:
        case cJU_JPNULL6:
        case cJU_JPNULL7:
#endif
            assert((Pjp->jp_Addr) == 0);
            JU_JPSETADT(Pjp, 0, Index, JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01 - cJU_JPNULL1);
#ifdef JUDYL
            // value area is first word of new Immed_01 JP:
            Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));
#endif
            return(1);


// ****************************************************************************
// JPBRANCH_L*:
//
// If the new Index is not an outlier to the branchs expanse, and the branch
// should not be converted to uncompressed, extract the digit and record the
// Immediate type to create for a new Immed JP, before going to common code.
//
// Note:  JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.

#define JU_BRANCH_OUTLIER(DIGIT,POP1,cLEVEL,PJP,INDEX,PJPM)  \
        JU_CHECK_IF_OUTLIER(PJP, INDEX, cLEVEL, PJPM);       \
        (DIGIT) = JU_DIGITATSTATE(INDEX, cLEVEL);            \
        (POP1)  = JU_JPBRANCH_POP0(PJP, cLEVEL)

        case cJU_JPBRANCH_L2:
            JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);
            goto JudyBranchL;

        case cJU_JPBRANCH_L3:
            JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);
            goto JudyBranchL;

#ifdef JU_64BIT
        case cJU_JPBRANCH_L4:
            JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);
            goto JudyBranchL;

        case cJU_JPBRANCH_L5:
            JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);
            goto JudyBranchL;

        case cJU_JPBRANCH_L6:
            JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);
            goto JudyBranchL;

        case cJU_JPBRANCH_L7:
            JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);
            goto JudyBranchL;
#endif

// Similar to common code above, but no outlier check is needed, and the Immed
// type depends on the word size:

        case cJU_JPBRANCH_L:
        {
            Pjbl_t PjblRaw;     // pointer to old linear branch.
            Pjbl_t Pjbl;
            Pjbu_t PjbuRaw;     // pointer to new uncompressed branch.
            Pjbu_t Pjbu;
            Word_t numJPs;      // number of JPs = populated expanses.
            int    offset;      // in branch.

            digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
            exppop1 = Pjpm->jpm_Pop0;

            // fall through:

// COMMON CODE FOR LINEAR BRANCHES:
//
// Come here with digit and exppop1 already set.

JudyBranchL:
            PjblRaw = (Pjbl_t) (Pjp->jp_Addr);
            Pjbl    = P_JBL(PjblRaw);

// If population under this branch greater than:

            if (exppop1 > JU_BRANCHL_MAX_POP)
                goto ConvertBranchLtoU;

            numJPs = Pjbl->jbl_NumJPs;

            if ((numJPs == 0) || (numJPs > cJU_BRANCHLMAXJPS))
            {
                JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
                return(-1);
            }

// Search for a match to the digit:

            offset = j__udySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse), numJPs,
                                       digit);

// If Index is found, offset is into an array of 1..cJU_BRANCHLMAXJPS JPs:

            if (offset >= 0)
            {
                Pjp = (Pjbl->jbl_jp) + offset;  // address of next JP.
                break;                          // continue walk.
            }

// Expanse is missing (not populated) for the passed Index, so insert an Immed
// -- if theres room:

            if (numJPs < cJU_BRANCHLMAXJPS)
            {
                offset = ~offset;       // insertion offset.

                JU_JPSETADT(&newJP, 0, Index,
                        JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01-cJU_JPBRANCH_L2);

                JU_INSERTINPLACE(Pjbl->jbl_Expanse, numJPs, offset, digit);
                JU_INSERTINPLACE(Pjbl->jbl_jp,      numJPs, offset, newJP);

                DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse),
                                        numJPs + 1, /* IndexSize = */ 1);)
                ++(Pjbl->jbl_NumJPs);
#ifdef JUDYL
                // value area is first word of new Immed 01 JP:
                Pjpm->jpm_PValue = (Pjv_t) ((Pjbl->jbl_jp) + offset);
#endif
                return(1);
            }


// MAXED OUT LINEAR BRANCH, CONVERT TO A BITMAP BRANCH, THEN INSERT:
//
// Copy the linear branch to a bitmap branch.
//
// TBD:  Consider renaming j__udyCreateBranchB() to j__udyConvertBranchLtoB().

            assert((numJPs) <= cJU_BRANCHLMAXJPS);

            if (j__udyCreateBranchB(Pjp, Pjbl->jbl_jp, Pjbl->jbl_Expanse,
                                    numJPs, Pjpm) == -1)
            {
                return(-1);
            }

// Convert jp_Type from linear branch to equivalent bitmap branch:

            Pjp->jp_Type += cJU_JPBRANCH_B - cJU_JPBRANCH_L;

            j__udyFreeJBL(PjblRaw, Pjpm);       // free old BranchL.

// Having changed branch types, now do the insert in the new branch type:

            goto ContinueInsWalk;


// OPPORTUNISTICALLY CONVERT FROM BRANCHL TO BRANCHU:
//
// Memory efficiency is no object because the branchs pop1 is large enough, so
// speed up array access.  Come here with PjblRaw set.  Note:  This is goto
// code because the previous block used to fall through into it as well, but no
// longer.

ConvertBranchLtoU:

// Allocate memory for an uncompressed branch:

            if ((PjbuRaw = j__udyAllocJBU(Pjpm)) == (Pjbu_t) NULL)
                return(-1);
            Pjbu = P_JBU(PjbuRaw);

// Set the proper NULL type for most of the uncompressed branchs JPs:

            JU_JPSETADT(&newJP, 0, 0, 
                    JU_JPTYPE(Pjp) - cJU_JPBRANCH_L2 + cJU_JPNULL1);

// Initialize:  Pre-set uncompressed branch to mostly JPNULL*s:

            for (numJPs = 0; numJPs < cJU_BRANCHUNUMJPS; ++numJPs)
                Pjbu->jbu_jp[numJPs] = newJP;

// Copy JPs from linear branch to uncompressed branch:

            {
#ifdef SUBEXPCOUNTS
                Word_t popmask = cJU_POP0MASK(JU_JPTYPE(Pjp))
                                             - cJU_JPBRANCH_L2 - 2;

                for (numJPs = 0; numJPs < cJU_NUMSUBEXPU; ++numJPs)
                    Pjbu->jbu_subPop1[numJPs] = 0;
#endif
                for (numJPs = 0; numJPs < Pjbl->jbl_NumJPs; ++numJPs)
                {
                    Pjp_t Pjp1           = &(Pjbl->jbl_jp[numJPs]);
                    offset               = Pjbl->jbl_Expanse[numJPs];
                    Pjbu->jbu_jp[offset] = *Pjp1;
#ifdef SUBEXPCOUNTS
                    Pjbu->jbu_subPop1[offset/cJU_NUMSUBEXPU] +=
                        JU_JPDCDPOP0(Pjp1) & popmask + 1;
#endif
                }
            }
            j__udyFreeJBL(PjblRaw, Pjpm);               // free old BranchL.

// Plug new values into parent JP:

            Pjp->jp_Addr  = (Word_t) PjbuRaw;
            Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_L;    // to BranchU.

// Save global population of last BranchU conversion:

            Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;
            goto ContinueInsWalk;

        } // case cJU_JPBRANCH_L.


// ****************************************************************************
// JPBRANCH_B*:
//
// If the new Index is not an outlier to the branchs expanse, extract the
// digit and record the Immediate type to create for a new Immed JP, before
// going to common code.
//
// Note:  JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.

        case cJU_JPBRANCH_B2:
            JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);
            goto JudyBranchB;

        case cJU_JPBRANCH_B3:
            JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);
            goto JudyBranchB;

#ifdef JU_64BIT
        case cJU_JPBRANCH_B4:
            JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);
            goto JudyBranchB;

        case cJU_JPBRANCH_B5:
            JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);
            goto JudyBranchB;

        case cJU_JPBRANCH_B6:
            JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);
            goto JudyBranchB;

        case cJU_JPBRANCH_B7:
            JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);
            goto JudyBranchB;
#endif

        case cJU_JPBRANCH_B:
        {
            Pjbb_t    Pjbb;             // pointer to bitmap branch.
            Pjbb_t    PjbbRaw;          // pointer to bitmap branch.
            Pjp_t     Pjp2Raw;          // 1 of N arrays of JPs.
            Pjp_t     Pjp2;             // 1 of N arrays of JPs.
            Word_t    subexp;           // 1 of N subexpanses in bitmap.
            BITMAPB_t bitmap;           // for one subexpanse.
            BITMAPB_t bitmask;          // bit set for Indexs digit.
            Word_t    numJPs;           // number of JPs = populated expanses.
            int       offset;           // in bitmap branch.

// Similar to common code above, but no outlier check is needed, and the Immed
// type depends on the word size:

            digit   = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
            exppop1 = Pjpm->jpm_Pop0;

            // fall through:


// COMMON CODE FOR BITMAP BRANCHES:
//
// Come here with digit and exppop1 already set.

JudyBranchB:

// If population increment is greater than..  (300):

            if ((Pjpm->jpm_Pop0 - Pjpm->jpm_LastUPop0) > JU_BTOU_POP_INCREMENT)
            {

// If total population of array is greater than..  (750):

                if (Pjpm->jpm_Pop0 > JU_BRANCHB_MAX_POP)
                {

// If population under the branch is greater than..  (135):

                    if (exppop1 > JU_BRANCHB_MIN_POP)
                    {
                        if (j__udyCreateBranchU(Pjp, Pjpm) == -1) return(-1);

// Save global population of last BranchU conversion:

                        Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;

                        goto ContinueInsWalk;
                    }
                }
            }

// CONTINUE TO USE BRANCHB:
//
// Get pointer to bitmap branch (JBB):

            PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);
            Pjbb    = P_JBB(PjbbRaw);

// Form the Int32 offset, and Bit offset values:
//
// 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
//              |SubExpanse |    Bit offset     |
//
// Get the 1 of 8 expanses from digit, Bits 5..7 = 1 of 8, and get the 32-bit
// word that may have a bit set:

            subexp = digit / cJU_BITSPERSUBEXPB;
            bitmap = JU_JBB_BITMAP(Pjbb, subexp);

            Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
            Pjp2    = P_JP(Pjp2Raw);

// Get the bit position that represents the desired expanse, and get the offset
// into the array of JPs for the JP that matches the bit.

            bitmask = JU_BITPOSMASKB(digit);
            offset  = j__udyCountBitsB(bitmap & (bitmask - 1));

// If JP is already in this expanse, get Pjp and continue the walk:

            if (bitmap & bitmask)
            {
#ifdef SUBEXPCOUNTS
                PSubExp = &(Pjbb->jbb_Counts[subexp]);  // ptr to subexp counts.
#endif
                Pjp =  Pjp2 + offset;
                break;                                  // continue walk.
            }


// ADD NEW EXPANSE FOR NEW INDEX:
//
// The new expanse always an cJU_JPIMMED_*_01 containing just the new Index, so
// finish setting up an Immed JP.

            JU_JPSETADT(&newJP, 0, Index, 
                JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01-cJU_JPBRANCH_B2);

// Get 1 of the 8 JP arrays and calculate number of JPs in subexpanse array:

            Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
            Pjp2    = P_JP(Pjp2Raw);
            numJPs  = j__udyCountBitsB(bitmap);

// Expand branch JP subarray in-place:

            if (JU_BRANCHBJPGROWINPLACE(numJPs))
            {
                assert(numJPs > 0);
                JU_INSERTINPLACE(Pjp2, numJPs, offset, newJP);
#ifdef JUDYL
                // value area is first word of new Immed 01 JP:
                Pjpm->jpm_PValue = (Pjv_t) (Pjp2 + offset);
#endif
            }

// No room, allocate a bigger bitmap branch JP subarray:

            else
            {
                Pjp_t PjpnewRaw;
                Pjp_t Pjpnew;

                if ((PjpnewRaw = j__udyAllocJBBJP(numJPs + 1, Pjpm)) == 0)
                    return(-1);
                Pjpnew = P_JP(PjpnewRaw);

// If there was an old JP array, then copy it, insert the new Immed JP, and
// free the old array:

                if (numJPs)
                {
                    JU_INSERTCOPY(Pjpnew, Pjp2, numJPs, offset, newJP);
                    j__udyFreeJBBJP(Pjp2Raw, numJPs, Pjpm);
#ifdef JUDYL
                    // value area is first word of new Immed 01 JP:
                    Pjpm->jpm_PValue = (Pjv_t) (Pjpnew + offset);
#endif
                }

// New JP subarray; point to cJU_JPIMMED_*_01 and place it:

                else
                {
                    assert(JU_JBB_PJP(Pjbb, subexp) == (Pjp_t) NULL);
                     Pjp = Pjpnew;
                    *Pjp = newJP;               // copy to new memory.
#ifdef JUDYL
                    // value area is first word of new Immed 01 JP:
                    Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));
#endif
                }

// Place new JP subarray in BranchB:

                JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw;

            } // else

// Set the new Indexs bit:

            JU_JBB_BITMAP(Pjbb, subexp) |= bitmask;

            return(1);

        } // case


// ****************************************************************************
// JPBRANCH_U*:
//
// Just drop through the JP for the correct digit.  If the JP turns out to be a
// JPNULL*, thats OK, the memory is already allocated, and the next walk
// simply places an Immed in it.
//
#ifdef SUBEXPCOUNTS
#define JU_GETSUBEXP(PSubExp,Pjbu,Digit) \
        (PSubExp) = &((Pjbu)->jbu_subPop1[(Digit) / cJU_NUMSUBEXPU])
#else
#define JU_GETSUBEXP(PSubExp,Pjbu,Digit)  // null.
#endif

#define JU_JBU_PJP_SUBEXP(Pjp,PSubExp,Index,Level)              \
        {                                                       \
            uint8_t digit = JU_DIGITATSTATE(Index, Level);      \
            Pjbu_t  P_jbu  = P_JBU((Pjp)->jp_Addr);             \
            (Pjp) = &(P_jbu->jbu_jp[digit]);                    \
            JU_GETSUBEXP(PSubExp, P_jbu, digit);                \
        }

        case cJU_JPBRANCH_U2:
            JU_CHECK_IF_OUTLIER(Pjp, Index, 2, Pjpm);
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 2);
            break;

#ifdef JU_64BIT
        case cJU_JPBRANCH_U3:
            JU_CHECK_IF_OUTLIER(Pjp, Index, 3, Pjpm);
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 3);
            break;

        case cJU_JPBRANCH_U4:
            JU_CHECK_IF_OUTLIER(Pjp, Index, 4, Pjpm);
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 4);
            break;

        case cJU_JPBRANCH_U5:
            JU_CHECK_IF_OUTLIER(Pjp, Index, 5, Pjpm);
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 5);
            break;

        case cJU_JPBRANCH_U6:
            JU_CHECK_IF_OUTLIER(Pjp, Index, 6, Pjpm);
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 6);
            break;

        case cJU_JPBRANCH_U7:
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 7);
#else
        case cJU_JPBRANCH_U3:
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 3);
#endif
            break;

        case cJU_JPBRANCH_U:
            JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, cJU_ROOTSTATE);
            break;


// ****************************************************************************
// JPLEAF*:
//
// COMMON CODE FRAGMENTS TO MINIMIZE REDUNDANCY BELOW:
//
// These are necessary to support performance by function and loop unrolling
// while avoiding huge amounts of nearly identical code.
//
// Prepare to handle a linear leaf:  Check for an outlier; set pop1 and pointer
// to leaf:

#ifdef JUDY1
#define JU_LEAFVALUE(Pjv)                       // null.
#define JU_LEAFPREPVALUE(Pjv, ValueArea)        // null.
#else
#define JU_LEAFVALUE(Pjv)                Pjv_t Pjv
#define JU_LEAFPREPVALUE(Pjv, ValueArea) (Pjv) = ValueArea(Pleaf, exppop1)
#endif

#define JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea)         \
        Pjll_t  PjllRaw;                                \
        Type    Pleaf;  /* specific type */             \
        int     offset;                                 \
        JU_LEAFVALUE(Pjv);                              \
                                                        \
        JU_CHECK_IF_OUTLIER(Pjp, Index, cIS, Pjpm);     \
                                                        \
        exppop1 = JU_JPLEAF_POP0(Pjp) + 1;              \
        assert(exppop1 <= (MaxPop1));                   \
        PjllRaw = (Pjll_t) (Pjp->jp_Addr);              \
        Pleaf   = (Type) P_JLL(PjllRaw);                \
        JU_LEAFPREPVALUE(Pjv, ValueArea)

// Add to, or grow, a linear leaf:  Find Index position; if the Index is
// absent, if theres room in the leaf, insert the Index [and value of 0] in
// place, otherwise grow the leaf:
//
// Note:  These insertions always take place with whole words, using
// JU_INSERTINPLACE() or JU_INSERTCOPY().

#ifdef JUDY1
#define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset)  // null.
#else
#define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset)         \
        JU_INSERTINPLACE(Pjv, ExpPop1, Offset, 0);      \
        Pjpm->jpm_PValue = (Pjv) + (Offset)
#endif

#ifdef JUDY1
#define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset)  // null.
#else
#define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset)               \
        {                                                               \
            Pjv_t Pjvnew = ValueArea(Pleafnew, (ExpPop1) + 1);          \
            JU_INSERTCOPY(Pjvnew, Pjv, ExpPop1, Offset, 0);             \
            Pjpm->jpm_PValue = (Pjvnew) + (Offset);                     \
        }
#endif

#define JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace,      \
                    InsertInPlace,InsertCopy,Alloc,Free)                \
                                                                        \
        offset = Search(Pleaf, exppop1, Index);                         \
        JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm);                          \
                                                                        \
        if (GrowInPlace(exppop1))       /* add to current leaf */       \
        {                                                               \
            InsertInPlace(Pleaf, exppop1, offset, Index);               \
            JU_LEAFGROWVALUEADD(Pjv, exppop1, offset);                  \
            DBGCODE(JudyCheckSorted((Pjll_t) Pleaf, exppop1 + 1, cIS);) \
            return(1);                                                  \
        }                                                               \
                                                                        \
        if (exppop1 < (MaxPop1))        /* grow to new leaf */          \
        {                                                               \
            Pjll_t PjllnewRaw;                                          \
            Type   Pleafnew;                                            \
            if ((PjllnewRaw = Alloc(exppop1 + 1, Pjpm)) == 0) return(-1); \
            Pleafnew = (Type) P_JLL(PjllnewRaw);                        \
            InsertCopy(Pleafnew, Pleaf, exppop1, offset, Index);        \
            JU_LEAFGROWVALUENEW(ValueArea, Pjv, exppop1, offset);       \
            DBGCODE(JudyCheckSorted((Pjll_t) Pleafnew, exppop1 + 1, cIS);) \
            Free(PjllRaw, exppop1, Pjpm);                               \
            (Pjp->jp_Addr) = (Word_t) PjllnewRaw;                       \
            return(1);                                                  \
        }                                                               \
        assert(exppop1 == (MaxPop1))

// Handle linear leaf overflow (cascade):  Splay or compress into smaller
// leaves:

#define JU_LEAFCASCADE(MaxPop1,Cascade,Free)            \
        if (Cascade(Pjp, Pjpm) == -1) return(-1);       \
        Free(PjllRaw, MaxPop1, Pjpm);                   \
        goto ContinueInsWalk

// Wrapper around all of the above:

#define JU_LEAFSET(cIS,Type,MaxPop1,Search,GrowInPlace,InsertInPlace,   \
                   InsertCopy,Cascade,Alloc,Free,ValueArea)             \
        {                                                               \
            JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea);                    \
            JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace,  \
                        InsertInPlace,InsertCopy,Alloc,Free);           \
            JU_LEAFCASCADE(MaxPop1,Cascade,Free);                       \
        }

// END OF MACROS; LEAFL CASES START HERE:
//
// 64-bit Judy1 does not have 1-byte leaves:

#if (defined(JUDYL) || (! defined(JU_64BIT)))

        case cJU_JPLEAF1:

            JU_LEAFSET(1, uint8_t *, cJU_LEAF1_MAXPOP1, j__udySearchLeaf1,
                       JU_LEAF1GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
                       j__udyCascade1, j__udyAllocJLL1, j__udyFreeJLL1,
                       JL_LEAF1VALUEAREA);

#endif // (JUDYL || ! JU_64BIT)

        case cJU_JPLEAF2:

            JU_LEAFSET(2, uint16_t *, cJU_LEAF2_MAXPOP1, j__udySearchLeaf2,
                       JU_LEAF2GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
                       j__udyCascade2, j__udyAllocJLL2, j__udyFreeJLL2,
                       JL_LEAF2VALUEAREA);

        case cJU_JPLEAF3:

            JU_LEAFSET(3, uint8_t *, cJU_LEAF3_MAXPOP1, j__udySearchLeaf3,
                       JU_LEAF3GROWINPLACE, JU_INSERTINPLACE3, JU_INSERTCOPY3,
                       j__udyCascade3, j__udyAllocJLL3, j__udyFreeJLL3,
                       JL_LEAF3VALUEAREA);

#ifdef JU_64BIT
        case cJU_JPLEAF4:

            JU_LEAFSET(4, uint32_t *, cJU_LEAF4_MAXPOP1, j__udySearchLeaf4,
                       JU_LEAF4GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
                       j__udyCascade4, j__udyAllocJLL4, j__udyFreeJLL4,
                       JL_LEAF4VALUEAREA);

        case cJU_JPLEAF5:

            JU_LEAFSET(5, uint8_t *, cJU_LEAF5_MAXPOP1, j__udySearchLeaf5,
                       JU_LEAF5GROWINPLACE, JU_INSERTINPLACE5, JU_INSERTCOPY5,
                       j__udyCascade5, j__udyAllocJLL5, j__udyFreeJLL5,
                       JL_LEAF5VALUEAREA);

        case cJU_JPLEAF6:

            JU_LEAFSET(6, uint8_t *, cJU_LEAF6_MAXPOP1, j__udySearchLeaf6,
                       JU_LEAF6GROWINPLACE, JU_INSERTINPLACE6, JU_INSERTCOPY6,
                       j__udyCascade6, j__udyAllocJLL6, j__udyFreeJLL6,
                       JL_LEAF6VALUEAREA);

        case cJU_JPLEAF7:

            JU_LEAFSET(7, uint8_t *, cJU_LEAF7_MAXPOP1, j__udySearchLeaf7,
                       JU_LEAF7GROWINPLACE, JU_INSERTINPLACE7, JU_INSERTCOPY7,
                       j__udyCascade7, j__udyAllocJLL7, j__udyFreeJLL7,
                       JL_LEAF7VALUEAREA);
#endif // JU_64BIT


// ****************************************************************************
// JPLEAF_B1:
//
// 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
//              |SubExpanse |    Bit offset     |
//
// Note:  For JudyL, values are stored in 8 subexpanses, each a linear word
// array of up to 32 values each.

        case cJU_JPLEAF_B1:
        {
#ifdef JUDYL
            Pjv_t     PjvRaw;           // pointer to value part of the leaf.
            Pjv_t     Pjv;              // pointer to value part of the leaf.
            Pjv_t     PjvnewRaw;        // new value area.
            Pjv_t     Pjvnew;           // new value area.
            Word_t    subexp;           // 1 of 8 subexpanses in bitmap.
            Pjlb_t    Pjlb;             // pointer to bitmap part of the leaf.
            BITMAPL_t bitmap;           // for one subexpanse.
            BITMAPL_t bitmask;          // bit set for Indexs digit.
            int       offset;           // of index in value area.
#endif

            JU_CHECK_IF_OUTLIER(Pjp, Index, 1, Pjpm);

#ifdef JUDY1

// If Index (bit) is already set, return now:

            if (JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index)) return(0);

// If bitmap is not full, set the new Indexs bit; otherwise convert to a Full:

            if ((exppop1 = JU_JPLEAF_POP0(Pjp) + 1)
              < cJU_JPFULLPOPU1_POP0)
            {
                JU_BITMAPSETL(P_JLB(Pjp->jp_Addr), Index);
            }
            else
            {
                j__udyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm);  // free LeafB1.
                Pjp->jp_Type = cJ1_JPFULLPOPU1;
                Pjp->jp_Addr = 0;
            }

#else // JUDYL

// This is very different from Judy1 because of the need to return a value area
// even for an existing Index, or manage the value area for a new Index, and
// because JudyL has no Full type:

// Get last byte to decode from Index, and pointer to bitmap leaf:

            digit = JU_DIGITATSTATE(Index, 1);
            Pjlb  = P_JLB(Pjp->jp_Addr);

// Prepare additional values:

            subexp  = digit / cJU_BITSPERSUBEXPL;       // which subexpanse.
            bitmap  = JU_JLB_BITMAP(Pjlb, subexp);      // subexps 32-bit map.
            PjvRaw  = JL_JLB_PVALUE(Pjlb, subexp);      // corresponding values.
            Pjv     = P_JV(PjvRaw);                     // corresponding values.
            bitmask = JU_BITPOSMASKL(digit);            // mask for Index.
            offset  = j__udyCountBitsL(bitmap & (bitmask - 1)); // of Index.

// If Index already exists, get value pointer and exit:

            if (bitmap & bitmask)
            {
                assert(Pjv);
                Pjpm->jpm_PValue = Pjv + offset;        // existing value.
                return(0);
            }

// Get the total bits set = expanse population of Value area:

            exppop1 = j__udyCountBitsL(bitmap);

// If the value area can grow in place, do it:

            if (JL_LEAFVGROWINPLACE(exppop1))
            {
                JU_INSERTINPLACE(Pjv, exppop1, offset, 0);
                JU_JLB_BITMAP(Pjlb, subexp) |= bitmask;  // set Indexs bit.
                Pjpm->jpm_PValue = Pjv + offset;          // new value area.
                return(1);
            }

// Increase size of value area:

            if ((PjvnewRaw = j__udyLAllocJV(exppop1 + 1, Pjpm))
             == (Pjv_t) NULL) return(-1);
            Pjvnew = P_JV(PjvnewRaw);

            if (exppop1)                // have existing value area.
            {
                assert(Pjv);
                JU_INSERTCOPY(Pjvnew, Pjv, exppop1, offset, 0);
                Pjpm->jpm_PValue = Pjvnew + offset;
                j__udyLFreeJV(PjvRaw, exppop1, Pjpm);   // free old values.
            }
            else                        // first index, new value area:
            {
                 Pjpm->jpm_PValue   = Pjvnew;
                *(Pjpm->jpm_PValue) = 0;
            }

// Set bit for new Index and place new leaf value area in bitmap:

            JU_JLB_BITMAP(Pjlb, subexp) |= bitmask;
            JL_JLB_PVALUE(Pjlb, subexp)  = PjvnewRaw;

#endif // JUDYL

            return(1);

        } // case


#ifdef JUDY1
// ****************************************************************************
// JPFULLPOPU1:
//
// If Index is not an outlier, then by definition its already set.

        case cJ1_JPFULLPOPU1:

            JU_CHECK_IF_OUTLIER(Pjp, Index, 1, Pjpm);
            return(0);
#endif


// ****************************************************************************
// JPIMMED*:
//
// This is some of the most complex code in Judy considering Judy1 versus JudyL
// and 32-bit versus 64-bit variations.  The following comments attempt to make
// this clearer.
//
// Of the 2 words in a JP, for immediate indexes Judy1 can use 2 words - 1 byte
// = 7 [15] bytes, but JudyL can only use 1 word - 1 byte = 3 [7] bytes because
// the other word is needed for a value area or a pointer to a value area.
//
// For both Judy1 and JudyL, cJU_JPIMMED_*_01 indexes are in word 2; otherwise
// for Judy1 only, a list of 2 or more indexes starts in word 1.  JudyL keeps
// the list in word 2 because word 1 is a pointer (to a LeafV, that is, a leaf
// containing only values).  Furthermore, cJU_JPIMMED_*_01 indexes are stored
// all-but-first-byte in jp_DcdPopO, not just the Index Sizes bytes.
//
// TBD:  This can be confusing because Doug didnt use data structures for it.
// Instead he often directly accesses Pjp for the first word and jp_DcdPopO for
// the second word.  It would be nice to use data structs, starting with
// jp_1Index and jp_LIndex where possible.
//
// Maximum Immed JP types for Judy1/JudyL, depending on Index Size (cIS):
//
//          32-bit  64-bit
//
//    bytes:  7/ 3   15/ 7   (Judy1/JudyL)
//
//    cIS
//    1_     07/03   15/07   (as in: cJ1_JPIMMED_1_07)
//    2_     03/01   07/03
//    3_     02/01   05/02
//    4_             03/01
//    5_             03/01
//    6_             02/01
//    7_             02/01
//
// State transitions while inserting an Index, matching the above table:
// (Yes, this is very terse...  Study it and it will make sense.)
// (Note, parts of this diagram are repeated below for quick reference.)
//
//      +-- reformat JP here for Judy1 only, from word-2 to word-1
//      |
//      |                  JUDY1 || JU_64BIT        JUDY1 && JU_64BIT
//      V
// 1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] Leaf1 (*)
// 2_01 =>                 [ 2_02 => 2_03 =>        [ 2_04..07 => ]] Leaf2
// 3_01 =>                 [ 3_02 =>                [ 3_03..05 => ]] Leaf3
// JU_64BIT only:
// 4_01 =>                                         [[ 4_02..03 => ]] Leaf4
// 5_01 =>                                         [[ 5_02..03 => ]] Leaf5
// 6_01 =>                                         [[ 6_02     => ]] Leaf6
// 7_01 =>                                         [[ 7_02     => ]] Leaf7
//
// (*) For Judy1 & 64-bit, go directly from cJU_JPIMMED_1_15 to a LeafB1; skip
//     Leaf1, as described in Judy1.h regarding cJ1_JPLEAF1.


// COMMON CODE FRAGMENTS TO MINIMIZE REDUNDANCY BELOW:
//
// These are necessary to support performance by function and loop unrolling
// while avoiding huge amounts of nearly identical code.
//
// The differences between Judy1 and JudyL with respect to value area handling
// are just too large for completely common code between them...  Oh well, some
// big ifdefs follow.  However, even in the following ifdefd code, use cJU_*,
// JU_*, and Judy*() instead of cJ1_* / cJL_*, J1_* / JL_*, and
// Judy1*()/JudyL*(), for minimum diffs.
//
// Handle growth of cJU_JPIMMED_*_01 to cJU_JPIMMED_*_02, for an even or odd
// Index Size (cIS), given oldIndex, Index, and Pjll in the context:
//
// Put oldIndex and Index in their proper order.  For odd indexes, must copy
// bytes.

#ifdef JUDY1

#define JU_IMMSET_01_COPY_EVEN(ignore1,ignore2) \
        if (oldIndex < Index) { Pjll[0] = oldIndex; Pjll[1] = Index;    } \
        else                  { Pjll[0] = Index;    Pjll[1] = oldIndex; }

#define JU_IMMSET_01_COPY_ODD(cIS,CopyWord)     \
        if (oldIndex < Index)                   \
        {                                       \
            CopyWord(Pjll + 0,     oldIndex);   \
            CopyWord(Pjll + (cIS), Index);      \
        }                                       \
        else                                    \
        {                                       \
            CopyWord(Pjll + 0,    Index);       \
            CopyWord(Pjll + (cIS), oldIndex);   \
        }

// The "real" *_01 Copy macro:
//
// Trim the high byte off Index, look for a match with the old Index, and if
// none, insert the new Index in the leaf in the correct place, given Pjp and
// Index in the context.
//
// Note:  A single immediate index lives in the jp_DcdPopO field, but two or
// more reside starting at Pjp->jp_1Index.

#define JU_IMMSET_01_COPY(cIS,LeafType,NewJPType,Copy,CopyWord) \
        {                                                       \
            LeafType Pjll;                                      \
            Word_t   oldIndex = JU_JPDCDPOP0(Pjp);              \
                                                                \
            Index = JU_TRIMTODCDSIZE(Index);                    \
            if (oldIndex == Index) return(0);                   \
                                                                \
            Pjll = (LeafType) (Pjp->jp_1Index);                 \
            Copy(cIS,CopyWord);                                 \
            DBGCODE(JudyCheckSorted(Pjll, 2, cIS);)             \
                                                                \
            Pjp->jp_Type = (NewJPType);                         \
            return(1);                                          \
        }

#else // JUDYL

// Variations to also handle value areas; see comments above:
//
// For JudyL, Pjv (start of value area) and oldValue are also in the context;
// leave Pjv set to the value area for Index.

#define JU_IMMSET_01_COPY_EVEN(cIS,CopyWord)    \
        if (oldIndex < Index)                   \
        {                                       \
            Pjll[0] = oldIndex;                 \
            Pjv [0] = oldValue;                 \
            Pjll[1] = Index;                    \
            ++Pjv;                              \
        }                                       \
        else                                    \
        {                                       \
            Pjll[0] = Index;                    \
            Pjll[1] = oldIndex;                 \
            Pjv [1] = oldValue;                 \
        }

#define JU_IMMSET_01_COPY_ODD(cIS,CopyWord)     \
        if (oldIndex < Index)                   \
        {                                       \
            CopyWord(Pjll + 0,     oldIndex);   \
            CopyWord(Pjll + (cIS), Index);      \
            Pjv[0] = oldValue;                  \
            ++Pjv;                              \
        }                                       \
        else                                    \
        {                                       \
            CopyWord(Pjll + 0,    Index);       \
            CopyWord(Pjll + (cIS), oldIndex);   \
            Pjv[1] = oldValue;                  \
        }

// The old value area is in the first word (*Pjp), and Pjv and Pjpm are also in
// the context.  Also, unlike Judy1, indexes remain in word 2 (jp_LIndex),
// meaning insert-in-place rather than copy.
//
// Return jpm_PValue pointing to Indexs value area.  If Index is new, allocate
// a 2-value-leaf and attach it to the JP.

#define JU_IMMSET_01_COPY(cIS,LeafType,NewJPType,Copy,CopyWord) \
        {                                                       \
            LeafType Pjll;                                      \
            Word_t   oldIndex = JU_JPDCDPOP0(Pjp);              \
            Word_t   oldValue;                                  \
            Pjv_t    PjvRaw;                                    \
            Pjv_t    Pjv;                                       \
                                                                \
            Index = JU_TRIMTODCDSIZE(Index);                    \
                                                                \
            if (oldIndex == Index)                              \
            {                                                   \
                Pjpm->jpm_PValue = (Pjv_t) Pjp;                 \
                return(0);                                      \
            }                                                   \
                                                                \
            if ((PjvRaw = j__udyLAllocJV(2, Pjpm)) == (Pjv_t) NULL) \
                return(-1);                                     \
            Pjv = P_JV(PjvRaw);                                 \
                                                                \
            oldValue       = Pjp->jp_Addr;                      \
            (Pjp->jp_Addr) = (Word_t) PjvRaw;                   \
            Pjll           = (LeafType) (Pjp->jp_LIndex);       \
                                                                \
            Copy(cIS,CopyWord);                                 \
            DBGCODE(JudyCheckSorted(Pjll, 2, cIS);)             \
                                                                \
            Pjp->jp_Type   = (NewJPType);                       \
            *Pjv             = 0;                               \
            Pjpm->jpm_PValue = Pjv;                             \
            return(1);                                          \
        }

// The following is a unique mix of JU_IMMSET_01() and JU_IMMSETCASCADE() for
// going from cJU_JPIMMED_*_01 directly to a cJU_JPLEAF* for JudyL:
//
// If Index is not already set, allocate a leaf, copy the old and new indexes
// into it, clear and return the new value area, and modify the current JP.
// Note that jp_DcdPop is set to a pop0 of 0 for now, and incremented later.


#define JU_IMMSET_01_CASCADE(cIS,LeafType,NewJPType,ValueArea,  \
                             Copy,CopyWord,Alloc)               \
        {                                                       \
            Word_t   D_P0;                                      \
            LeafType PjllRaw;                                   \
            LeafType Pjll;                                      \
            Word_t   oldIndex = JU_JPDCDPOP0(Pjp);              \
            Word_t   oldValue;                                  \
            Pjv_t    Pjv;                                       \
                                                                \
            Index = JU_TRIMTODCDSIZE(Index);                    \
                                                                \
            if (oldIndex == Index)                              \
            {                                                   \
                Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));   \
                return(0);                                      \
            }                                                   \
                                                                \
            if ((PjllRaw = (LeafType) Alloc(2, Pjpm)) == (LeafType) NULL) \
                return(-1);                                     \
            Pjll = (LeafType) P_JLL(PjllRaw);                   \
            Pjv  = ValueArea(Pjll, 2);                          \
                                                                \
            oldValue = Pjp->jp_Addr;                            \
                                                                \
            Copy(cIS,CopyWord);                                 \
            DBGCODE(JudyCheckSorted(Pjll, 2, cIS);)             \
                                                                \
            *Pjv = 0;                                           \
            Pjpm->jpm_PValue  = Pjv;                            \
            D_P0 = Index & cJU_DCDMASK(cIS); /* pop0 = 0 */     \
            JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType); \
                                                                \
            return(1);                                          \
        }

#endif // JUDYL

// Handle growth of cJU_JPIMMED_*_[02..15]:

#ifdef JUDY1

// Insert an Index into an immediate JP that has room for more, if the Index is
// not already present; given Pjp, Index, exppop1, Pjv, and Pjpm in the
// context:
//
// Note:  Use this only when the JP format doesnt change, that is, going from
// cJU_JPIMMED_X_0Y to cJU_JPIMMED_X_0Z, where X >= 2 and Y+1 = Z.
//
// Note:  Incrementing jp_Type is how to increase the Index population.

#define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \
        {                                                               \
            LeafType Pjll;                                              \
            int      offset;                                            \
                                                                        \
            exppop1 = JU_JPTYPE(Pjp) - (BaseJPType_02) + 2;             \
            offset  = Search((Pjll_t) (Pjp->jp_1Index), exppop1, Index); \
                                                                        \
            JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);                   \
                                                                        \
            Pjll = (LeafType) (Pjp->jp_1Index);                         \
            InsertInPlace(Pjll, exppop1, offset, Index);                \
            DBGCODE(JudyCheckSorted(Pjll, exppop1 + 1, cIS);)           \
            ++(Pjp->jp_Type);                                           \
            return(1);                                                  \
        }

// Insert an Index into an immediate JP that has no room for more:
//
// If the Index is not already present, do a cascade (to a leaf); given Pjp,
// Index, Pjv, and Pjpm in the context.


#define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType,                \
                         ignore,Search,InsertCopy,Alloc)                \
        {                                                               \
            Word_t   D_P0;                                              \
            Pjll_t PjllRaw;                                             \
            Pjll_t Pjll;                                                \
            int    offset;                                              \
                                                                        \
            offset = Search((Pjll_t) (Pjp->jp_1Index), (OldPop1), Index); \
            JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);                   \
                                                                        \
            if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0) return(-1); \
            Pjll = P_JLL(PjllRaw);                                      \
                                                                        \
            InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_1Index),    \
                       OldPop1, offset, Index);                         \
            DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);)         \
                                                                        \
            D_P0 = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1;          \
            JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType);         \
            return(1);                                                  \
        }

#else // JUDYL

// Variations to also handle value areas; see comments above:
//
// For JudyL, Pjv (start of value area) is also in the context.
//
// TBD:  This code makes a true but weak assumption that a JudyL 32-bit 2-index
// value area must be copied to a new 3-index value area.  AND it doesnt know
// anything about JudyL 64-bit cases (cJU_JPIMMED_1_0[3-7] only) where the
// value area can grow in place!  However, this should not break it, just slow
// it down.

#define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \
        {                                                                 \
            LeafType Pleaf;                                               \
            int      offset;                                              \
            Pjv_t    PjvRaw;                                              \
            Pjv_t    Pjv;                                                 \
            Pjv_t    PjvnewRaw;                                           \
            Pjv_t    Pjvnew;                                              \
                                                                          \
            exppop1 = JU_JPTYPE(Pjp) - (BaseJPType_02) + 2;               \
            offset  = Search((Pjll_t) (Pjp->jp_LIndex), exppop1, Index);  \
            PjvRaw  = (Pjv_t) (Pjp->jp_Addr);                             \
            Pjv     = P_JV(PjvRaw);                                       \
                                                                          \
            JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm);                        \
                                                                          \
            if ((PjvnewRaw = j__udyLAllocJV(exppop1 + 1, Pjpm))           \
             == (Pjv_t) NULL) return(-1);                                 \
            Pjvnew = P_JV(PjvnewRaw);                                     \
                                                                          \
            Pleaf = (LeafType) (Pjp->jp_LIndex);                          \
                                                                          \
            InsertInPlace(Pleaf, exppop1, offset, Index);                 \
            /* see TBD above about this: */                               \
            JU_INSERTCOPY(Pjvnew, Pjv, exppop1, offset, 0);               \
            DBGCODE(JudyCheckSorted(Pleaf, exppop1 + 1, cIS);)            \
            j__udyLFreeJV(PjvRaw, exppop1, Pjpm);                         \
            Pjp->jp_Addr     = (Word_t) PjvnewRaw;                        \
            Pjpm->jpm_PValue = Pjvnew + offset;                           \
                                                                          \
            ++(Pjp->jp_Type);                                             \
            return(1);                                                    \
        }

#define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType,                \
                         ValueArea,Search,InsertCopy,Alloc)             \
        {                                                               \
            Word_t   D_P0;                                      \
            Pjll_t PjllRaw;                                             \
            Pjll_t Pjll;                                                \
            int    offset;                                              \
            Pjv_t  PjvRaw;                                              \
            Pjv_t  Pjv;                                                 \
            Pjv_t  Pjvnew;                                              \
                                                                        \
            PjvRaw = (Pjv_t) (Pjp->jp_Addr);                            \
            Pjv    = P_JV(PjvRaw);                                      \
            offset = Search((Pjll_t) (Pjp->jp_LIndex), (OldPop1), Index); \
            JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm);                      \
                                                                        \
            if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0)            \
                return(-1);                                             \
            Pjll = P_JLL(PjllRaw);                                      \
            InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_LIndex),    \
                       OldPop1, offset, Index);                         \
            DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);)         \
                                                                        \
            Pjvnew = ValueArea(Pjll, (OldPop1) + 1);                    \
            JU_INSERTCOPY(Pjvnew, Pjv, OldPop1, offset, 0);             \
            j__udyLFreeJV(PjvRaw, (OldPop1), Pjpm);                     \
            Pjpm->jpm_PValue = Pjvnew + offset;                         \
                                                                        \
            D_P0 = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1;          \
            JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType);         \
            return(1);                                                  \
        }

#endif // JUDYL

// Common convenience/shorthand wrappers around JU_IMMSET_01_COPY() for
// even/odd index sizes:

#define JU_IMMSET_01(     cIS, LeafType, NewJPType) \
        JU_IMMSET_01_COPY(cIS, LeafType, NewJPType, JU_IMMSET_01_COPY_EVEN, \
                          ignore)

#define JU_IMMSET_01_ODD( cIS,            NewJPType, CopyWord) \
        JU_IMMSET_01_COPY(cIS, uint8_t *, NewJPType, JU_IMMSET_01_COPY_ODD, \
                          CopyWord)


// END OF MACROS; IMMED CASES START HERE:

// cJU_JPIMMED_*_01 cases:
//
// 1_01 always leads to 1_02:
//
// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)

        case cJU_JPIMMED_1_01: JU_IMMSET_01(1, uint8_t *, cJU_JPIMMED_1_02);

// 2_01 leads to 2_02, and 3_01 leads to 3_02, except for JudyL 32-bit, where
// they lead to a leaf:
//
// (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)
// (3_01 => [ 3_02 =>         [ 3_03..05 => ]] LeafL)

#if (defined(JUDY1) || defined(JU_64BIT))
        case cJU_JPIMMED_2_01: JU_IMMSET_01(2, uint16_t *, cJU_JPIMMED_2_02);
        case cJU_JPIMMED_3_01: JU_IMMSET_01_ODD (3, cJU_JPIMMED_3_02,
                                                 JU_COPY3_LONG_TO_PINDEX);
#else
        case cJU_JPIMMED_2_01:
            JU_IMMSET_01_CASCADE(2, uint16_t *, cJU_JPLEAF2, JL_LEAF2VALUEAREA,
                                 JU_IMMSET_01_COPY_EVEN, ignore,
                                 j__udyAllocJLL2);
        case cJU_JPIMMED_3_01:
            JU_IMMSET_01_CASCADE(3, uint8_t *,  cJU_JPLEAF3, JL_LEAF3VALUEAREA,
                                 JU_IMMSET_01_COPY_ODD,
                                 JU_COPY3_LONG_TO_PINDEX, j__udyAllocJLL3);
#endif

#ifdef JU_64BIT

// [4-7]_01 lead to [4-7]_02 for Judy1, and to leaves for JudyL:
//
// (4_01 => [[ 4_02..03 => ]] LeafL)
// (5_01 => [[ 5_02..03 => ]] LeafL)
// (6_01 => [[ 6_02 =>     ]] LeafL)
// (7_01 => [[ 7_02 =>     ]] LeafL)

#ifdef JUDY1
        case cJU_JPIMMED_4_01: JU_IMMSET_01(4, uint32_t *, cJ1_JPIMMED_4_02);
        case cJU_JPIMMED_5_01: JU_IMMSET_01_ODD(5, cJ1_JPIMMED_5_02,
                                                JU_COPY5_LONG_TO_PINDEX);
        case cJU_JPIMMED_6_01: JU_IMMSET_01_ODD(6, cJ1_JPIMMED_6_02,
                                                JU_COPY6_LONG_TO_PINDEX);
        case cJU_JPIMMED_7_01: JU_IMMSET_01_ODD(7, cJ1_JPIMMED_7_02,
                                                JU_COPY7_LONG_TO_PINDEX);
#else // JUDYL
        case cJU_JPIMMED_4_01:
            JU_IMMSET_01_CASCADE(4, uint32_t *, cJU_JPLEAF4, JL_LEAF4VALUEAREA,
                                 JU_IMMSET_01_COPY_EVEN, ignore,
                                 j__udyAllocJLL4);
        case cJU_JPIMMED_5_01:
            JU_IMMSET_01_CASCADE(5, uint8_t *, cJU_JPLEAF5, JL_LEAF5VALUEAREA,
                                 JU_IMMSET_01_COPY_ODD,
                                 JU_COPY5_LONG_TO_PINDEX, j__udyAllocJLL5);
        case cJU_JPIMMED_6_01:
            JU_IMMSET_01_CASCADE(6, uint8_t *, cJU_JPLEAF6, JL_LEAF6VALUEAREA,
                                 JU_IMMSET_01_COPY_ODD,
                                 JU_COPY6_LONG_TO_PINDEX, j__udyAllocJLL6);
        case cJU_JPIMMED_7_01:
            JU_IMMSET_01_CASCADE(7, uint8_t *, cJU_JPLEAF7, JL_LEAF7VALUEAREA,
                                 JU_IMMSET_01_COPY_ODD,
                                 JU_COPY7_LONG_TO_PINDEX, j__udyAllocJLL7);
#endif // JUDYL
#endif // JU_64BIT

// cJU_JPIMMED_1_* cases that can grow in place:
//
// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)

        case cJU_JPIMMED_1_02:
#if (defined(JUDY1) || defined(JU_64BIT))
        case cJU_JPIMMED_1_03:
        case cJU_JPIMMED_1_04:
        case cJU_JPIMMED_1_05:
        case cJU_JPIMMED_1_06:
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
        case cJU_JPIMMED_1_07:
        case cJ1_JPIMMED_1_08:
        case cJ1_JPIMMED_1_09:
        case cJ1_JPIMMED_1_10:
        case cJ1_JPIMMED_1_11:
        case cJ1_JPIMMED_1_12:
        case cJ1_JPIMMED_1_13:
        case cJ1_JPIMMED_1_14:
#endif
            JU_IMMSETINPLACE(1, uint8_t *, cJU_JPIMMED_1_02, j__udySearchLeaf1,
                             JU_INSERTINPLACE);

// cJU_JPIMMED_1_* cases that must cascade:
//
// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)

#if (defined(JUDYL) && (! defined(JU_64BIT)))
        case cJU_JPIMMED_1_03:
            JU_IMMSETCASCADE(1, 3, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,
                             j__udySearchLeaf1, JU_INSERTCOPY,
                             j__udyAllocJLL1);
#endif
#if (defined(JUDY1) && (! defined(JU_64BIT)))
        case cJU_JPIMMED_1_07:
            JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, ignore,
                             j__udySearchLeaf1, JU_INSERTCOPY,
                             j__udyAllocJLL1);

#endif
#if (defined(JUDYL) && defined(JU_64BIT))
        case cJU_JPIMMED_1_07:
            JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,
                             j__udySearchLeaf1, JU_INSERTCOPY,
                             j__udyAllocJLL1);

#endif
#if (defined(JUDY1) && defined(JU_64BIT))
// Special case, as described above, go directly from Immed to LeafB1:

        case cJ1_JPIMMED_1_15:
        {
            Word_t DcdP0;
            int    offset;
            Pjlb_t PjlbRaw;
            Pjlb_t Pjlb;

            offset = j__udySearchLeaf1((Pjll_t) Pjp->jp_1Index, 15, Index);

            JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);

// Create a bitmap leaf (special case for Judy1 64-bit only, see usage):  Set
// new Index in bitmap, copy an Immed1_15 to the bitmap, and set the parent JP
// EXCEPT jp_DcdPopO, leaving any followup to the caller:

            if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
                return(-1);
            Pjlb = P_JLB(PjlbRaw);

            JU_BITMAPSETL(Pjlb, Index);

            for (offset = 0; offset < 15; ++offset)
                JU_BITMAPSETL(Pjlb, Pjp->jp_1Index[offset]);

//          Set jp_DcdPopO including the current pop0; incremented later:
            DcdP0 = (Index & cJU_DCDMASK(1)) + 15 - 1;
            JU_JPSETADT(Pjp, (Word_t)PjlbRaw, DcdP0, cJU_JPLEAF_B1);

            return(1);
        }
#endif

// cJU_JPIMMED_[2..7]_[02..15] cases that grow in place or cascade:
//
// (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)

#if (defined(JUDY1) || defined(JU_64BIT))
        case cJU_JPIMMED_2_02:
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
        case cJU_JPIMMED_2_03:
        case cJ1_JPIMMED_2_04:
        case cJ1_JPIMMED_2_05:
        case cJ1_JPIMMED_2_06:
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
            JU_IMMSETINPLACE(2, uint16_t *, cJU_JPIMMED_2_02, j__udySearchLeaf2,
                             JU_INSERTINPLACE);
#endif

#undef OLDPOP1
#if ((defined(JUDY1) && (! defined(JU_64BIT))) || (defined(JUDYL) && defined(JU_64BIT)))
        case cJU_JPIMMED_2_03:
#define OLDPOP1 3
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
        case cJ1_JPIMMED_2_07:
#define OLDPOP1 7
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
            JU_IMMSETCASCADE(2, OLDPOP1, uint16_t *, cJU_JPLEAF2,
                             JL_LEAF2VALUEAREA, j__udySearchLeaf2,
                             JU_INSERTCOPY, j__udyAllocJLL2);
#endif

// (3_01 => [ 3_02 => [ 3_03..05 => ]] LeafL)

#if (defined(JUDY1) && defined(JU_64BIT))
        case cJU_JPIMMED_3_02:
        case cJ1_JPIMMED_3_03:
        case cJ1_JPIMMED_3_04:

            JU_IMMSETINPLACE(3, uint8_t *, cJU_JPIMMED_3_02, j__udySearchLeaf3,
                             JU_INSERTINPLACE3);
#endif

#undef OLDPOP1
#if ((defined(JUDY1) && (! defined(JU_64BIT))) || (defined(JUDYL) && defined(JU_64BIT)))
        case cJU_JPIMMED_3_02:
#define OLDPOP1 2
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
        case cJ1_JPIMMED_3_05:
#define OLDPOP1 5
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
            JU_IMMSETCASCADE(3, OLDPOP1, uint8_t *, cJU_JPLEAF3,
                             JL_LEAF3VALUEAREA, j__udySearchLeaf3,
                             JU_INSERTCOPY3, j__udyAllocJLL3);
#endif

#if (defined(JUDY1) && defined(JU_64BIT))

// (4_01 => [[ 4_02..03 => ]] LeafL)

        case cJ1_JPIMMED_4_02:

            JU_IMMSETINPLACE(4, uint32_t *, cJ1_JPIMMED_4_02, j__udySearchLeaf4,
                             JU_INSERTINPLACE);

        case cJ1_JPIMMED_4_03:

            JU_IMMSETCASCADE(4, 3, uint32_t *, cJU_JPLEAF4, ignore,
                             j__udySearchLeaf4, JU_INSERTCOPY,
                             j__udyAllocJLL4);

// (5_01 => [[ 5_02..03 => ]] LeafL)

        case cJ1_JPIMMED_5_02:

            JU_IMMSETINPLACE(5, uint8_t *, cJ1_JPIMMED_5_02, j__udySearchLeaf5,
                             JU_INSERTINPLACE5);

        case cJ1_JPIMMED_5_03:

            JU_IMMSETCASCADE(5, 3, uint8_t *, cJU_JPLEAF5, ignore,
                             j__udySearchLeaf5, JU_INSERTCOPY5,
                             j__udyAllocJLL5);

// (6_01 => [[ 6_02 => ]] LeafL)

        case cJ1_JPIMMED_6_02:

            JU_IMMSETCASCADE(6, 2, uint8_t *, cJU_JPLEAF6, ignore,
                             j__udySearchLeaf6, JU_INSERTCOPY6,
                             j__udyAllocJLL6);

// (7_01 => [[ 7_02 => ]] LeafL)

        case cJ1_JPIMMED_7_02:

            JU_IMMSETCASCADE(7, 2, uint8_t *, cJU_JPLEAF7, ignore,
                             j__udySearchLeaf7, JU_INSERTCOPY7,
                             j__udyAllocJLL7);

#endif // (JUDY1 && JU_64BIT)


// ****************************************************************************
// INVALID JP TYPE:

        default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);

        } // switch on JP type

        {

#ifdef SUBEXPCOUNTS

// This code might seem strange here.  However it saves some memory read time
// during insert (~70nS) because a pipelined processor does not need to "stall"
// waiting for the memory read to complete.  Hope the compiler is not too smart
// or dumb and moves the code down to where it looks like it belongs (below a
// few lines).

            Word_t SubExpCount = 0;     // current subexpanse counter.

            if (PSubExp != (PWord_t) NULL)      // only if BranchB/U.
                SubExpCount = PSubExp[0];
#endif

// PROCESS JP -- RECURSIVELY:
//
// For non-Immed JP types, if successful, post-increment the population count
// at this Level.

            retcode = j__udyInsWalk(Pjp, Index, Pjpm);

// Successful insert, increment JP and subexpanse count:

            if ((JU_JPTYPE(Pjp) < cJU_JPIMMED_1_01) && (retcode == 1))
            {
                jp_t   JP;
                Word_t DcdP0;
#ifdef SUBEXPCOUNTS

// Note:  Pjp must be a pointer to a BranchB/U:

                if (PSubExp != (PWord_t) NULL) PSubExp[0] = SubExpCount + 1;
#endif

                JP = *Pjp;
                DcdP0 = JU_JPDCDPOP0(Pjp) + 1;
                JU_JPSETADT(Pjp, JP.jp_Addr, DcdP0, JU_JPTYPE(&JP));
            }
        }
        return(retcode);

} // j__udyInsWalk()


// ****************************************************************************
// J U D Y   1   S E T
// J U D Y   L   I N S
//
// Main entry point.  See the manual entry for details.

#ifdef JUDY1
FUNCTION int Judy1Set
#else
FUNCTION PPvoid_t JudyLIns
#endif
        (
        PPvoid_t  PPArray,      // in which to insert.
        Word_t    Index,        // to insert.
        PJError_t PJError       // optional, for returning error info.
        )
{
#ifdef JUDY1
#define Pjv       ignore        // placeholders for macros.
#define Pjvnew    ignore
#else
        Pjv_t     Pjv;          // value area in old leaf.
        Pjv_t     Pjvnew;       // value area in new leaf.
#endif
        Pjpm_t    Pjpm;         // array-global info.
        int       offset;       // position in which to store new Index.
        Pjlw_t    Pjlw;


// CHECK FOR NULL POINTER (error by caller):

        if (PPArray == (PPvoid_t) NULL)
        {
            JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
            JUDY1CODE(return(JERRI );)
            JUDYLCODE(return(PPJERR);)
        }

        Pjlw = P_JLW(*PPArray); // first word of leaf.

// ****************************************************************************
// PROCESS TOP LEVEL "JRP" BRANCHES AND LEAVES:

// ****************************************************************************
// JRPNULL (EMPTY ARRAY):  BUILD A LEAFW WITH ONE INDEX:

// if a valid empty array (null pointer), so create an array of population == 1:

        if (Pjlw == (Pjlw_t)NULL)
        {
            Pjlw_t Pjlwnew;

            Pjlwnew = j__udyAllocJLW(1);
            JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)
            JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)

            Pjlwnew[0] = 1 - 1;         // pop0 = 0.
            Pjlwnew[1] = Index;

            *PPArray = (Pvoid_t) Pjlwnew;
            DBGCODE(JudyCheckPop(*PPArray);)

  JUDY1CODE(return(1); )
  JUDYLCODE(Pjlwnew[2] = 0; )           // value area.
  JUDYLCODE(return((PPvoid_t) (Pjlwnew + 2)); )

        }  // NULL JRP

// ****************************************************************************
// LEAFW, OTHER SIZE:

        if (JU_LEAFW_POP0(*PPArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
        {
            Pjlw_t Pjlwnew;
            Word_t pop1;

            Pjlw = P_JLW(*PPArray);             // first word of leaf.
            pop1 = Pjlw[0] + 1;

#ifdef JUDYL
            Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);
#endif
            offset = j__udySearchLeafW(Pjlw + 1, pop1, Index);

            if (offset >= 0)            // index is already valid:
            {
                DBGCODE(JudyCheckPop(*PPArray);)
                JUDY1CODE(return(0); )
                JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )
            }

            offset = ~offset;

// Insert index in cases where no new memory is needed:

            if (JU_LEAFWGROWINPLACE(pop1))
            {
                ++Pjlw[0];                      // increase population.

                JU_INSERTINPLACE(Pjlw + 1, pop1, offset, Index);
#ifdef JUDYL
                JU_INSERTINPLACE(Pjv, pop1, offset, 0);
#endif
                DBGCODE(JudyCheckPop(*PPArray);)
                DBGCODE(JudyCheckSorted(Pjlw + 1, pop1 + 1, cJU_ROOTSTATE);)

      JUDY1CODE(return(1); )
      JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )
            }

// Insert index into a new, larger leaf:

            if (pop1 < cJU_LEAFW_MAXPOP1)       // can grow to a larger leaf.
            {
                Pjlwnew = j__udyAllocJLW(pop1 + 1);
                JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)
                JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)

                Pjlwnew[0] = pop1;              // set pop0 in new leaf.

                JU_INSERTCOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, Index);
#ifdef JUDYL
                Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 + 1);
                JU_INSERTCOPY(Pjvnew, Pjv, pop1, offset, 0);
#endif
                DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 + 1, cJU_ROOTSTATE);)

                j__udyFreeJLW(Pjlw, pop1, NULL);

                *PPArray = (Pvoid_t) Pjlwnew;
                DBGCODE(JudyCheckPop(*PPArray);)

      JUDY1CODE(return(1); )
      JUDYLCODE(return((PPvoid_t) (Pjvnew + offset)); )
            }

            assert(pop1 == cJU_LEAFW_MAXPOP1);

// Leaf at max size => cannot insert new index, so cascade instead:
//
// Upon cascading from a LEAFW leaf to the first branch, must allocate and
// initialize a JPM.

            Pjpm = j__udyAllocJPM();
            JUDY1CODE(JU_CHECKALLOC(Pjpm_t, Pjpm, JERRI );)
            JUDYLCODE(JU_CHECKALLOC(Pjpm_t, Pjpm, PPJERR);)

            (Pjpm->jpm_Pop0)       = cJU_LEAFW_MAXPOP1 - 1;
            (Pjpm->jpm_JP.jp_Addr) = (Word_t) Pjlw;

            if (j__udyCascadeL(&(Pjpm->jpm_JP), Pjpm) == -1)
            {
                JU_COPY_ERRNO(PJError, Pjpm);
                JUDY1CODE(return(JERRI );)
                JUDYLCODE(return(PPJERR);)
            }

// Note:  No need to pass Pjpm for memory decrement; LEAFW memory is never
// counted in a JPM at all:

            j__udyFreeJLW(Pjlw, cJU_LEAFW_MAXPOP1, NULL);
            *PPArray = (Pvoid_t) Pjpm;

        } // JU_LEAFW

// ****************************************************************************
// BRANCH:

        {
            int retcode;  // really only needed for Judy1, but free for JudyL.

            Pjpm = P_JPM(*PPArray);
            retcode = j__udyInsWalk(&(Pjpm->jpm_JP), Index, Pjpm);

            if (retcode == -1)
            {
                JU_COPY_ERRNO(PJError, Pjpm);
                JUDY1CODE(return(JERRI );)
                JUDYLCODE(return(PPJERR);)
            }

            if (retcode ==  1) ++(Pjpm->jpm_Pop0);  // incr total array popu.

            assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)
                || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)
                || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));
            DBGCODE(JudyCheckPop(*PPArray);)

#ifdef JUDY1
            assert((retcode == 0) || (retcode == 1));
            return(retcode);            // == JU_RET_*_JPM().
#else
            assert(Pjpm->jpm_PValue != (Pjv_t) NULL);
            return((PPvoid_t) Pjpm->jpm_PValue);
#endif
        }
        /*NOTREACHED*/

} // Judy1Set() / JudyLIns()