Adding upstream version 1.44.3.upstream/1.44.3upstream

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

1 files changed, 1094 insertions, 0 deletions

diff --git a/libnetdata/libjudy/src/JudyL/JudyLGet.c b/libnetdata/libjudy/src/JudyL/JudyLGet.c
new file mode 100644
index 00000000..0bb9971c
--- /dev/null
+++ b/libnetdata/libjudy/src/JudyL/JudyLGet.c
@@ -0,0 +1,1094 @@
+// 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.43 $ $Source: /judy/src/JudyCommon/JudyGet.c $
+//
+// Judy1Test() and JudyLGet() 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"
+
+#ifdef TRACEJPR                 // different macro name, for "retrieval" only.
+#include "JudyPrintJP.c"
+#endif
+
+
+// ****************************************************************************
+// J U D Y   1   T E S T
+// J U D Y   L   G E T
+//
+// See the manual entry for details.  Note support for "shortcut" entries to
+// trees known to start with a JPM.
+
+#ifdef JUDY1
+
+#ifdef JUDYGETINLINE
+FUNCTION int j__udy1Test
+#else
+FUNCTION int Judy1Test
+#endif
+
+#else  // JUDYL
+
+#ifdef JUDYGETINLINE
+FUNCTION PPvoid_t j__udyLGet
+#else
+FUNCTION PPvoid_t JudyLGet
+#endif
+
+#endif // JUDYL
+        (
+#ifdef JUDYGETINLINE
+        Pvoid_t   PArray,       // from which to retrieve.
+        Word_t    Index         // to retrieve.
+#else
+        Pcvoid_t  PArray,       // from which to retrieve.
+        Word_t    Index,        // to retrieve.
+        PJError_t PJError       // optional, for returning error info.
+#endif
+        )
+{
+        Pjp_t     Pjp;          // current JP while walking the tree.
+        Pjpm_t    Pjpm;         // for global accounting.
+        uint8_t   Digit;        // byte just decoded from Index.
+        Word_t    Pop1;         // leaf population (number of indexes).
+        Pjll_t    Pjll;         // pointer to LeafL.
+        DBGCODE(uint8_t ParentJPType;)
+
+#ifndef JUDYGETINLINE
+
+        if (PArray == (Pcvoid_t) NULL)  // empty array.
+        {
+  JUDY1CODE(return(0);)
+  JUDYLCODE(return((PPvoid_t) NULL);)
+        }
+
+// ****************************************************************************
+// PROCESS TOP LEVEL BRANCHES AND LEAF:
+
+        if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
+        {
+            Pjlw_t Pjlw = P_JLW(PArray);        // first word of leaf.
+            int    posidx;                      // signed offset in leaf.
+
+            Pop1   = Pjlw[0] + 1;
+            posidx = j__udySearchLeafW(Pjlw + 1, Pop1, Index);
+
+            if (posidx >= 0)
+            {
+      JUDY1CODE(return(1);)
+      JUDYLCODE(return((PPvoid_t) (JL_LEAFWVALUEAREA(Pjlw, Pop1) + posidx));)
+            }
+  JUDY1CODE(return(0);)
+  JUDYLCODE(return((PPvoid_t) NULL);)
+        }
+
+#endif // ! JUDYGETINLINE
+
+        Pjpm = P_JPM(PArray);
+        Pjp = &(Pjpm->jpm_JP);  // top branch is below JPM.
+
+// ****************************************************************************
+// WALK THE JUDY TREE USING A STATE MACHINE:
+
+ContinueWalk:           // for going down one level; come here with Pjp set.
+
+#ifdef TRACEJPR
+        JudyPrintJP(Pjp, "g", __LINE__);
+#endif
+        switch (JU_JPTYPE(Pjp))
+        {
+
+// Ensure the switch table starts at 0 for speed; otherwise more code is
+// executed:
+
+        case 0: goto ReturnCorrupt;     // save a little code.
+
+
+// ****************************************************************************
+// JPNULL*:
+//
+// Note:  These are legitimate in a BranchU (only) and do not constitute a
+// fault.
+
+        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(ParentJPType >= cJU_JPBRANCH_U2);
+            assert(ParentJPType <= cJU_JPBRANCH_U);
+      JUDY1CODE(return(0);)
+      JUDYLCODE(return((PPvoid_t) NULL);)
+
+
+// ****************************************************************************
+// JPBRANCH_L*:
+//
+// Note:  The use of JU_DCDNOTMATCHINDEX() in branches is not strictly
+// required,since this can be done at leaf level, but it costs nothing to do it
+// sooner, and it aborts an unnecessary traversal sooner.
+
+        case cJU_JPBRANCH_L2:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
+            Digit = JU_DIGITATSTATE(Index, 2);
+            goto JudyBranchL;
+
+        case cJU_JPBRANCH_L3:
+
+#ifdef JU_64BIT // otherwise its a no-op:
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
+#endif
+            Digit = JU_DIGITATSTATE(Index, 3);
+            goto JudyBranchL;
+
+#ifdef JU_64BIT
+        case cJU_JPBRANCH_L4:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
+            Digit = JU_DIGITATSTATE(Index, 4);
+            goto JudyBranchL;
+
+        case cJU_JPBRANCH_L5:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
+            Digit = JU_DIGITATSTATE(Index, 5);
+            goto JudyBranchL;
+
+        case cJU_JPBRANCH_L6:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
+            Digit = JU_DIGITATSTATE(Index, 6);
+            goto JudyBranchL;
+
+        case cJU_JPBRANCH_L7:
+
+            // JU_DCDNOTMATCHINDEX() would be a no-op.
+            Digit = JU_DIGITATSTATE(Index, 7);
+            goto JudyBranchL;
+
+#endif // JU_64BIT
+
+        case cJU_JPBRANCH_L:
+        {
+            Pjbl_t Pjbl;
+            int    posidx;
+
+            Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
+
+// Common code for all BranchLs; come here with Digit set:
+
+JudyBranchL:
+            Pjbl = P_JBL(Pjp->jp_Addr);
+
+            posidx = 0;
+
+            do {
+                if (Pjbl->jbl_Expanse[posidx] == Digit)
+                {                       // found Digit; continue traversal:
+                    DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+                    Pjp = Pjbl->jbl_jp + posidx;
+                    goto ContinueWalk;
+                }
+            } while (++posidx != Pjbl->jbl_NumJPs);
+
+            break;
+        }
+
+
+// ****************************************************************************
+// JPBRANCH_B*:
+
+        case cJU_JPBRANCH_B2:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
+            Digit = JU_DIGITATSTATE(Index, 2);
+            goto JudyBranchB;
+
+        case cJU_JPBRANCH_B3:
+
+#ifdef JU_64BIT // otherwise its a no-op:
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
+#endif
+            Digit = JU_DIGITATSTATE(Index, 3);
+            goto JudyBranchB;
+
+
+#ifdef JU_64BIT
+        case cJU_JPBRANCH_B4:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
+            Digit = JU_DIGITATSTATE(Index, 4);
+            goto JudyBranchB;
+
+        case cJU_JPBRANCH_B5:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
+            Digit = JU_DIGITATSTATE(Index, 5);
+            goto JudyBranchB;
+
+        case cJU_JPBRANCH_B6:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
+            Digit = JU_DIGITATSTATE(Index, 6);
+            goto JudyBranchB;
+
+        case cJU_JPBRANCH_B7:
+
+            // JU_DCDNOTMATCHINDEX() would be a no-op.
+            Digit = JU_DIGITATSTATE(Index, 7);
+            goto JudyBranchB;
+
+#endif // JU_64BIT
+
+        case cJU_JPBRANCH_B:
+        {
+            Pjbb_t    Pjbb;
+            Word_t    subexp;   // in bitmap, 0..7.
+            BITMAPB_t BitMap;   // for one subexpanse.
+            BITMAPB_t BitMask;  // bit in BitMap for Indexs Digit.
+
+            Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
+
+// Common code for all BranchBs; come here with Digit set:
+
+JudyBranchB:
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjbb   = P_JBB(Pjp->jp_Addr);
+            subexp = Digit / cJU_BITSPERSUBEXPB;
+
+            BitMap = JU_JBB_BITMAP(Pjbb, subexp);
+            Pjp    = P_JP(JU_JBB_PJP(Pjbb, subexp));
+
+            BitMask = JU_BITPOSMASKB(Digit);
+
+// No JP in subexpanse for Index => Index not found:
+
+            if (! (BitMap & BitMask)) break;
+
+// Count JPs in the subexpanse below the one for Index:
+
+            Pjp += j__udyCountBitsB(BitMap & (BitMask - 1));
+
+            goto ContinueWalk;
+
+        } // case cJU_JPBRANCH_B*
+
+
+// ****************************************************************************
+// JPBRANCH_U*:
+//
+// Notice the reverse order of the cases, and falling through to the next case,
+// for performance.
+
+        case cJU_JPBRANCH_U:
+
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, cJU_ROOTSTATE);
+
+// If not a BranchU, traverse; otherwise fall into the next case, which makes
+// this very fast code for a large Judy array (mainly BranchUs), especially
+// when branches are already in the cache, such as for prev/next:
+
+#ifndef JU_64BIT
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
+#else
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U7) goto ContinueWalk;
+#endif
+
+#ifdef JU_64BIT
+        case cJU_JPBRANCH_U7:
+
+            // JU_DCDNOTMATCHINDEX() would be a no-op.
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, 7);
+
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U6) goto ContinueWalk;
+            // and fall through.
+
+        case cJU_JPBRANCH_U6:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, 6);
+
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U5) goto ContinueWalk;
+            // and fall through.
+
+        case cJU_JPBRANCH_U5:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, 5);
+
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U4) goto ContinueWalk;
+            // and fall through.
+
+        case cJU_JPBRANCH_U4:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, 4);
+
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
+            // and fall through.
+
+#endif // JU_64BIT
+
+        case cJU_JPBRANCH_U3:
+
+#ifdef JU_64BIT // otherwise its a no-op:
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
+#endif
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, 3);
+
+            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U2) goto ContinueWalk;
+            // and fall through.
+
+        case cJU_JPBRANCH_U2:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
+            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
+            Pjp = JU_JBU_PJP(Pjp, Index, 2);
+
+// Note:  BranchU2 is a special case that must continue traversal to a leaf,
+// immed, full, or null type:
+
+            goto ContinueWalk;
+
+
+// ****************************************************************************
+// JPLEAF*:
+//
+// Note:  Here the calls of JU_DCDNOTMATCHINDEX() are necessary and check
+// whether Index is out of the expanse of a narrow pointer.
+
+#if (defined(JUDYL) || (! defined(JU_64BIT)))
+
+        case cJU_JPLEAF1:
+        {
+            int posidx;         // signed offset in leaf.
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
+
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf1(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF1VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+
+#endif // (JUDYL || (! JU_64BIT))
+
+        case cJU_JPLEAF2:
+        {
+            int posidx;         // signed offset in leaf.
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
+
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf2(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF2VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+        case cJU_JPLEAF3:
+        {
+            int posidx;         // signed offset in leaf.
+
+#ifdef JU_64BIT // otherwise its a no-op:
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
+#endif
+
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf3(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF3VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+#ifdef JU_64BIT
+        case cJU_JPLEAF4:
+        {
+            int posidx;         // signed offset in leaf.
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
+
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf4(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF4VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+        case cJU_JPLEAF5:
+        {
+            int posidx;         // signed offset in leaf.
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
+
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf5(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF5VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+
+        case cJU_JPLEAF6:
+        {
+            int posidx;         // signed offset in leaf.
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
+
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf6(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF6VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+        case cJU_JPLEAF7:
+        {
+            int posidx;         // signed offset in leaf.
+
+            // JU_DCDNOTMATCHINDEX() would be a no-op.
+            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
+            Pjll = P_JLL(Pjp->jp_Addr);
+
+            if ((posidx = j__udySearchLeaf7(Pjll, Pop1, Index)) < 0) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) (JL_LEAF7VALUEAREA(Pjll, Pop1) + posidx));)
+        }
+#endif // JU_64BIT
+
+
+// ****************************************************************************
+// JPLEAF_B1:
+
+        case cJU_JPLEAF_B1:
+        {
+            Pjlb_t    Pjlb;
+#ifdef JUDYL
+            int       posidx;
+            Word_t    subexp;   // in bitmap, 0..7.
+            BITMAPL_t BitMap;   // for one subexpanse.
+            BITMAPL_t BitMask;  // bit in BitMap for Indexs Digit.
+            Pjv_t     Pjv;
+#endif
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
+
+            Pjlb = P_JLB(Pjp->jp_Addr);
+
+#ifdef JUDY1
+
+// Simply check if Indexs bit is set in the bitmap:
+
+            if (JU_BITMAPTESTL(Pjlb, Index)) return(1);
+            break;
+
+#else // JUDYL
+
+// JudyL is much more complicated because of value area subarrays:
+
+            Digit   = JU_DIGITATSTATE(Index, 1);
+            subexp  = Digit / cJU_BITSPERSUBEXPL;
+            BitMap  = JU_JLB_BITMAP(Pjlb, subexp);
+            BitMask = JU_BITPOSMASKL(Digit);
+
+// No value in subexpanse for Index => Index not found:
+
+            if (! (BitMap & BitMask)) break;
+
+// Count value areas in the subexpanse below the one for Index:
+
+            Pjv = P_JV(JL_JLB_PVALUE(Pjlb, subexp));
+            assert(Pjv != (Pjv_t) NULL);
+            posidx = j__udyCountBitsL(BitMap & (BitMask - 1));
+
+            return((PPvoid_t) (Pjv + posidx));
+
+#endif // JUDYL
+
+        } // case cJU_JPLEAF_B1
+
+#ifdef JUDY1
+
+// ****************************************************************************
+// JPFULLPOPU1:
+//
+// If the Index is in the expanse, it is necessarily valid (found).
+
+        case cJ1_JPFULLPOPU1:
+
+            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
+            return(1);
+
+#ifdef notdef // for future enhancements
+#ifdef JU_64BIT
+
+// Note: Need ? if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
+
+        case cJ1_JPFULLPOPU1m15:
+            if (Pjp->jp_1Index[14] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m14:
+            if (Pjp->jp_1Index[13] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m13:
+            if (Pjp->jp_1Index[12] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m12:
+            if (Pjp->jp_1Index[11] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m11:
+            if (Pjp->jp_1Index[10] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m10:
+            if (Pjp->jp_1Index[9] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m9:
+            if (Pjp->jp_1Index[8] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m8:
+            if (Pjp->jp_1Index[7] == (uint8_t)Index) break;
+#endif
+        case cJ1_JPFULLPOPU1m7:
+            if (Pjp->jp_1Index[6] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m6:
+            if (Pjp->jp_1Index[5] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m5:
+            if (Pjp->jp_1Index[4] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m4:
+            if (Pjp->jp_1Index[3] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m3:
+            if (Pjp->jp_1Index[2] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m2:
+            if (Pjp->jp_1Index[1] == (uint8_t)Index) break;
+        case cJ1_JPFULLPOPU1m1:
+            if (Pjp->jp_1Index[0] == (uint8_t)Index) break;
+
+            return(1);  // found, not in exclusion list
+
+#endif // JUDY1
+#endif //  notdef
+
+// ****************************************************************************
+// JPIMMED*:
+//
+// Note that the contents of jp_DcdPopO are different for cJU_JPIMMED_*_01:
+
+        case cJU_JPIMMED_1_01:
+        case cJU_JPIMMED_2_01:
+        case cJU_JPIMMED_3_01:
+#ifdef JU_64BIT
+        case cJU_JPIMMED_4_01:
+        case cJU_JPIMMED_5_01:
+        case cJU_JPIMMED_6_01:
+        case cJU_JPIMMED_7_01:
+#endif
+            if (JU_JPDCDPOP0(Pjp) != JU_TRIMTODCDSIZE(Index)) break;
+
+  JUDY1CODE(return(1);)
+  JUDYLCODE(return((PPvoid_t) &(Pjp->jp_Addr));)  // immediate value area.
+
+
+//   Macros to make code more readable and avoid dup errors
+
+#ifdef JUDY1
+
+#define CHECKINDEXNATIVE(LEAF_T, PJP, IDX, INDEX)                       \
+if (((LEAF_T *)((PJP)->jp_1Index))[(IDX) - 1] == (LEAF_T)(INDEX))       \
+    return(1)
+
+#define CHECKLEAFNONNAT(LFBTS, PJP, INDEX, IDX, COPY)                   \
+{                                                                       \
+    Word_t   i_ndex;                                                    \
+    uint8_t *a_ddr;                                                     \
+    a_ddr  = (PJP)->jp_1Index + (((IDX) - 1) * (LFBTS));                \
+    COPY(i_ndex, a_ddr);                                                \
+    if (i_ndex == JU_LEASTBYTES((INDEX), (LFBTS)))                      \
+        return(1);                                                      \
+}
+#endif
+
+#ifdef JUDYL
+
+#define CHECKINDEXNATIVE(LEAF_T, PJP, IDX, INDEX)                       \
+if (((LEAF_T *)((PJP)->jp_LIndex))[(IDX) - 1] == (LEAF_T)(INDEX))       \
+        return((PPvoid_t)(P_JV((PJP)->jp_Addr) + (IDX) - 1))
+
+#define CHECKLEAFNONNAT(LFBTS, PJP, INDEX, IDX, COPY)                   \
+{                                                                       \
+    Word_t   i_ndex;                                                    \
+    uint8_t *a_ddr;                                                     \
+    a_ddr  = (PJP)->jp_LIndex + (((IDX) - 1) * (LFBTS));                \
+    COPY(i_ndex, a_ddr);                                                \
+    if (i_ndex == JU_LEASTBYTES((INDEX), (LFBTS)))                      \
+        return((PPvoid_t)(P_JV((PJP)->jp_Addr) + (IDX) - 1));           \
+}
+#endif
+
+#if (defined(JUDY1) && defined(JU_64BIT))
+        case cJ1_JPIMMED_1_15: CHECKINDEXNATIVE(uint8_t, Pjp, 15, Index);
+        case cJ1_JPIMMED_1_14: CHECKINDEXNATIVE(uint8_t, Pjp, 14, Index);
+        case cJ1_JPIMMED_1_13: CHECKINDEXNATIVE(uint8_t, Pjp, 13, Index);
+        case cJ1_JPIMMED_1_12: CHECKINDEXNATIVE(uint8_t, Pjp, 12, Index);
+        case cJ1_JPIMMED_1_11: CHECKINDEXNATIVE(uint8_t, Pjp, 11, Index);
+        case cJ1_JPIMMED_1_10: CHECKINDEXNATIVE(uint8_t, Pjp, 10, Index);
+        case cJ1_JPIMMED_1_09: CHECKINDEXNATIVE(uint8_t, Pjp,  9, Index);
+        case cJ1_JPIMMED_1_08: CHECKINDEXNATIVE(uint8_t, Pjp,  8, Index);
+#endif
+#if (defined(JUDY1) || defined(JU_64BIT))
+        case cJU_JPIMMED_1_07: CHECKINDEXNATIVE(uint8_t, Pjp,  7, Index);
+        case cJU_JPIMMED_1_06: CHECKINDEXNATIVE(uint8_t, Pjp,  6, Index);
+        case cJU_JPIMMED_1_05: CHECKINDEXNATIVE(uint8_t, Pjp,  5, Index);
+        case cJU_JPIMMED_1_04: CHECKINDEXNATIVE(uint8_t, Pjp,  4, Index);
+#endif
+        case cJU_JPIMMED_1_03: CHECKINDEXNATIVE(uint8_t, Pjp,  3, Index);
+        case cJU_JPIMMED_1_02: CHECKINDEXNATIVE(uint8_t, Pjp,  2, Index);
+                               CHECKINDEXNATIVE(uint8_t, Pjp,  1, Index);
+        break;
+
+#if (defined(JUDY1) && defined(JU_64BIT))
+        case cJ1_JPIMMED_2_07: CHECKINDEXNATIVE(uint16_t, Pjp, 7, Index);
+        case cJ1_JPIMMED_2_06: CHECKINDEXNATIVE(uint16_t, Pjp, 6, Index);
+        case cJ1_JPIMMED_2_05: CHECKINDEXNATIVE(uint16_t, Pjp, 5, Index);
+        case cJ1_JPIMMED_2_04: CHECKINDEXNATIVE(uint16_t, Pjp, 4, Index);
+#endif
+#if (defined(JUDY1) || defined(JU_64BIT))
+        case cJU_JPIMMED_2_03: CHECKINDEXNATIVE(uint16_t, Pjp, 3, Index);
+        case cJU_JPIMMED_2_02: CHECKINDEXNATIVE(uint16_t, Pjp, 2, Index);
+                               CHECKINDEXNATIVE(uint16_t, Pjp, 1, Index);
+        break;
+#endif
+
+#if (defined(JUDY1) && defined(JU_64BIT))
+        case cJ1_JPIMMED_3_05: 
+            CHECKLEAFNONNAT(3, Pjp, Index, 5, JU_COPY3_PINDEX_TO_LONG);
+        case cJ1_JPIMMED_3_04:
+            CHECKLEAFNONNAT(3, Pjp, Index, 4, JU_COPY3_PINDEX_TO_LONG);
+        case cJ1_JPIMMED_3_03:
+            CHECKLEAFNONNAT(3, Pjp, Index, 3, JU_COPY3_PINDEX_TO_LONG);
+#endif
+#if (defined(JUDY1) || defined(JU_64BIT))
+        case cJU_JPIMMED_3_02:
+            CHECKLEAFNONNAT(3, Pjp, Index, 2, JU_COPY3_PINDEX_TO_LONG);
+            CHECKLEAFNONNAT(3, Pjp, Index, 1, JU_COPY3_PINDEX_TO_LONG);
+            break;
+#endif
+
+#if (defined(JUDY1) && defined(JU_64BIT))
+
+        case cJ1_JPIMMED_4_03: CHECKINDEXNATIVE(uint32_t, Pjp, 3, Index);
+        case cJ1_JPIMMED_4_02: CHECKINDEXNATIVE(uint32_t, Pjp, 2, Index);
+                               CHECKINDEXNATIVE(uint32_t, Pjp, 1, Index);
+            break;
+
+        case cJ1_JPIMMED_5_03:
+            CHECKLEAFNONNAT(5, Pjp, Index, 3, JU_COPY5_PINDEX_TO_LONG);
+        case cJ1_JPIMMED_5_02:
+            CHECKLEAFNONNAT(5, Pjp, Index, 2, JU_COPY5_PINDEX_TO_LONG);
+            CHECKLEAFNONNAT(5, Pjp, Index, 1, JU_COPY5_PINDEX_TO_LONG);
+            break;
+
+        case cJ1_JPIMMED_6_02:
+            CHECKLEAFNONNAT(6, Pjp, Index, 2, JU_COPY6_PINDEX_TO_LONG);
+            CHECKLEAFNONNAT(6, Pjp, Index, 1, JU_COPY6_PINDEX_TO_LONG);
+            break;
+
+        case cJ1_JPIMMED_7_02:
+            CHECKLEAFNONNAT(7, Pjp, Index, 2, JU_COPY7_PINDEX_TO_LONG);
+            CHECKLEAFNONNAT(7, Pjp, Index, 1, JU_COPY7_PINDEX_TO_LONG);
+            break;
+
+#endif // (JUDY1 && JU_64BIT)
+
+
+// ****************************************************************************
+// INVALID JP TYPE:
+
+        default:
+
+ReturnCorrupt:
+
+#ifdef JUDYGETINLINE    // Pjpm is known to be non-null:
+            JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
+#else
+            JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
+#endif
+            JUDY1CODE(return(JERRI );)
+            JUDYLCODE(return(PPJERR);)
+
+        } // switch on JP type
+
+JUDY1CODE(return(0);)
+JUDYLCODE(return((PPvoid_t) NULL);)
+
+} // Judy1Test() / JudyLGet()
+
+
+#ifndef JUDYGETINLINE   // only compile the following function once:
+#ifdef DEBUG
+
+// ****************************************************************************
+// J U D Y   C H E C K   P O P
+//
+// Given a pointer to a Judy array, traverse the entire array to ensure
+// population counts add up correctly.  This can catch various coding errors.
+//
+// Since walking the entire tree is probably time-consuming, enable this
+// function by setting env parameter $CHECKPOP to first call at which to start
+// checking.  Note:  This function is called both from insert and delete code.
+//
+// Note:  Even though this function does nothing useful for LEAFW leaves, its
+// good practice to call it anyway, and cheap too.
+//
+// TBD:  This is a debug-only check function similar to JudyCheckSorted(), but
+// since it walks the tree it is Judy1/JudyL-specific and must live in a source
+// file that is built both ways.
+//
+// TBD:  As feared, enabling this code for every insert/delete makes Judy
+// deathly slow, even for a small tree (10K indexes).  Its not so bad if
+// present but disabled (<1% slowdown measured).  Still, should it be ifdefd
+// other than DEBUG and/or called less often?
+//
+// TBD:  Should this "population checker" be expanded to a comprehensive tree
+// checker?  It currently detects invalid LEAFW/JP types as well as inconsistent
+// pop1s.  Other possible checks, all based on essentially redundant data in
+// the Judy tree, include:
+//
+// - Zero LS bits in jp_Addr field.
+//
+// - Correct Dcd bits.
+//
+// - Consistent JP types (always descending down the tree).
+//
+// - Sorted linear lists in BranchLs and leaves (using JudyCheckSorted(), but
+//   ideally that function is already called wherever appropriate after any
+//   linear list is modified).
+//
+// - Any others possible?
+
+#include <stdlib.h>             // for getenv() and atol().
+
+static Word_t JudyCheckPopSM(Pjp_t Pjp, Word_t RootPop1);
+
+FUNCTION void JudyCheckPop(
+        Pvoid_t PArray)
+{
+static  bool_t  checked = FALSE;        // already checked env parameter.
+static  bool_t  enabled = FALSE;        // env parameter set.
+static  bool_t  active  = FALSE;        // calls >= callsmin.
+static  Word_t  callsmin;               // start point from $CHECKPOP.
+static  Word_t  calls = 0;              // times called so far.
+
+
+// CHECK FOR EXTERNAL ENABLING:
+
+        if (! checked)                  // only check once.
+        {
+            char * value;               // for getenv().
+
+            checked = TRUE;
+
+            if ((value = getenv("CHECKPOP")) == (char *) NULL)
+            {
+#ifdef notdef
+// Take this out because nightly tests want to be flavor-independent; its not
+// OK to emit special non-error output from the debug flavor:
+
+                (void) puts("JudyCheckPop() present but not enabled by "
+                            "$CHECKPOP env parameter; set it to the number of "
+                            "calls at which to begin checking");
+#endif
+                return;
+            }
+
+            callsmin = atol(value);     // note: non-number evaluates to 0.
+            enabled  = TRUE;
+
+            (void) printf("JudyCheckPop() present and enabled; callsmin = "
+                          "%lu\n", callsmin);
+        }
+        else if (! enabled) return;
+
+// Previously or just now enabled; check if non-active or newly active:
+
+        if (! active)
+        {
+            if (++calls < callsmin) return;
+
+            (void) printf("JudyCheckPop() activated at call %lu\n", calls);
+            active = TRUE;
+        }
+
+// IGNORE LEAFW AT TOP OF TREE:
+
+        if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
+                return;
+
+// Check JPM pop0 against tree, recursively:
+//
+// Note:  The traversal code in JudyCheckPopSM() is simplest when the case
+// statement for each JP type compares the pop1 for that JP to its subtree (if
+// any) after traversing the subtree (thats the hard part) and adding up
+// actual pop1s.  A top branchs JP in the JPM does not have room for a
+// full-word pop1, so pass it in as a special case.
+
+        {
+            Pjpm_t Pjpm = P_JPM(PArray);
+            (void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1);
+            return;
+        }
+
+} // JudyCheckPop()
+
+
+// ****************************************************************************
+// J U D Y   C H E C K   P O P   S M
+//
+// Recursive state machine (subroutine) for JudyCheckPop():  Given a Pjp (other
+// than JPNULL*; caller should shortcut) and the root population for top-level
+// branches, check the subtrees actual pop1 against its nominal value, and
+// return the total pop1 for the subtree.
+//
+// Note:  Expect RootPop1 to be ignored at lower levels, so pass down 0, which
+// should pop an assertion if this expectation is violated.
+
+FUNCTION static Word_t JudyCheckPopSM(
+        Pjp_t  Pjp,             // top of subtree.
+        Word_t RootPop1)        // whole array, for top-level branches only.
+{
+        Word_t pop1_jp;         // nominal population from the JP.
+        Word_t pop1 = 0;        // actual population at this level.
+        Word_t offset;          // in a branch.
+
+#define PREPBRANCH(cPopBytes,Next) \
+        pop1_jp = JU_JPBRANCH_POP0(Pjp, cPopBytes) + 1; goto Next
+
+assert((((Word_t) (Pjp->jp_Addr)) & 7) == 3);
+        switch (JU_JPTYPE(Pjp))
+        {
+
+        case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL);
+        case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL);
+#ifdef JU_64BIT
+        case cJU_JPBRANCH_L4: PREPBRANCH(4, BranchL);
+        case cJU_JPBRANCH_L5: PREPBRANCH(5, BranchL);
+        case cJU_JPBRANCH_L6: PREPBRANCH(6, BranchL);
+        case cJU_JPBRANCH_L7: PREPBRANCH(7, BranchL);
+#endif
+        case cJU_JPBRANCH_L:  pop1_jp = RootPop1;
+        {
+            Pjbl_t Pjbl;
+BranchL:
+            Pjbl = P_JBL(Pjp->jp_Addr);
+
+            for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset)
+                pop1 += JudyCheckPopSM((Pjbl->jbl_jp) + offset, 0);
+
+            assert(pop1_jp == pop1);
+            return(pop1);
+        }
+
+        case cJU_JPBRANCH_B2: PREPBRANCH(2, BranchB);
+        case cJU_JPBRANCH_B3: PREPBRANCH(3, BranchB);
+#ifdef JU_64BIT
+        case cJU_JPBRANCH_B4: PREPBRANCH(4, BranchB);
+        case cJU_JPBRANCH_B5: PREPBRANCH(5, BranchB);
+        case cJU_JPBRANCH_B6: PREPBRANCH(6, BranchB);
+        case cJU_JPBRANCH_B7: PREPBRANCH(7, BranchB);
+#endif
+        case cJU_JPBRANCH_B:  pop1_jp = RootPop1;
+        {
+            Word_t subexp;
+            Word_t jpcount;
+            Pjbb_t Pjbb;
+BranchB:
+            Pjbb = P_JBB(Pjp->jp_Addr);
+
+            for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
+            {
+                jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
+
+                for (offset = 0; offset < jpcount; ++offset)
+                {
+                    pop1 += JudyCheckPopSM(P_JP(JU_JBB_PJP(Pjbb, subexp))
+                                         + offset, 0);
+                }
+            }
+
+            assert(pop1_jp == pop1);
+            return(pop1);
+        }
+
+        case cJU_JPBRANCH_U2: PREPBRANCH(2, BranchU);
+        case cJU_JPBRANCH_U3: PREPBRANCH(3, BranchU);
+#ifdef JU_64BIT
+        case cJU_JPBRANCH_U4: PREPBRANCH(4, BranchU);
+        case cJU_JPBRANCH_U5: PREPBRANCH(5, BranchU);
+        case cJU_JPBRANCH_U6: PREPBRANCH(6, BranchU);
+        case cJU_JPBRANCH_U7: PREPBRANCH(7, BranchU);
+#endif
+        case cJU_JPBRANCH_U:  pop1_jp = RootPop1;
+        {
+            Pjbu_t Pjbu;
+BranchU:
+            Pjbu = P_JBU(Pjp->jp_Addr);
+
+            for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
+            {
+                if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1)
+                 && ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX))
+                {
+                    continue;           // skip null JP to save time.
+                }
+
+                pop1 += JudyCheckPopSM((Pjbu->jbu_jp) + offset, 0);
+            }
+
+            assert(pop1_jp == pop1);
+            return(pop1);
+        }
+
+
+// -- Cases below here terminate and do not recurse. --
+//
+// For all of these cases except JPLEAF_B1, there is no way to check the JPs
+// pop1 against the object itself; just return the pop1; but for linear leaves,
+// a bounds check is possible.
+
+#define CHECKLEAF(MaxPop1)                              \
+        pop1 = JU_JPLEAF_POP0(Pjp) + 1;                 \
+        assert(pop1 >= 1);                              \
+        assert(pop1 <= (MaxPop1));                      \
+        return(pop1)
+
+#if (defined(JUDYL) || (! defined(JU_64BIT)))
+        case cJU_JPLEAF1:  CHECKLEAF(cJU_LEAF1_MAXPOP1);
+#endif
+        case cJU_JPLEAF2:  CHECKLEAF(cJU_LEAF2_MAXPOP1);
+        case cJU_JPLEAF3:  CHECKLEAF(cJU_LEAF3_MAXPOP1);
+#ifdef JU_64BIT
+        case cJU_JPLEAF4:  CHECKLEAF(cJU_LEAF4_MAXPOP1);
+        case cJU_JPLEAF5:  CHECKLEAF(cJU_LEAF5_MAXPOP1);
+        case cJU_JPLEAF6:  CHECKLEAF(cJU_LEAF6_MAXPOP1);
+        case cJU_JPLEAF7:  CHECKLEAF(cJU_LEAF7_MAXPOP1);
+#endif
+
+        case cJU_JPLEAF_B1:
+        {
+            Word_t subexp;
+            Pjlb_t Pjlb;
+
+            pop1_jp = JU_JPLEAF_POP0(Pjp) + 1;
+
+            Pjlb = P_JLB(Pjp->jp_Addr);
+
+            for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
+                pop1 += j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
+
+            assert(pop1_jp == pop1);
+            return(pop1);
+        }
+
+        JUDY1CODE(case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0);)
+
+        case cJU_JPIMMED_1_01:  return(1);
+        case cJU_JPIMMED_2_01:  return(1);
+        case cJU_JPIMMED_3_01:  return(1);
+#ifdef JU_64BIT
+        case cJU_JPIMMED_4_01:  return(1);
+        case cJU_JPIMMED_5_01:  return(1);
+        case cJU_JPIMMED_6_01:  return(1);
+        case cJU_JPIMMED_7_01:  return(1);
+#endif
+
+        case cJU_JPIMMED_1_02:  return(2);
+        case cJU_JPIMMED_1_03:  return(3);
+#if (defined(JUDY1) || defined(JU_64BIT))
+        case cJU_JPIMMED_1_04:  return(4);
+        case cJU_JPIMMED_1_05:  return(5);
+        case cJU_JPIMMED_1_06:  return(6);
+        case cJU_JPIMMED_1_07:  return(7);
+#endif
+#if (defined(JUDY1) && defined(JU_64BIT))
+        case cJ1_JPIMMED_1_08:  return(8);
+        case cJ1_JPIMMED_1_09:  return(9);
+        case cJ1_JPIMMED_1_10:  return(10);
+        case cJ1_JPIMMED_1_11:  return(11);
+        case cJ1_JPIMMED_1_12:  return(12);
+        case cJ1_JPIMMED_1_13:  return(13);
+        case cJ1_JPIMMED_1_14:  return(14);
+        case cJ1_JPIMMED_1_15:  return(15);
+#endif
+
+#if (defined(JUDY1) || defined(JU_64BIT))
+        case cJU_JPIMMED_2_02:  return(2);
+        case cJU_JPIMMED_2_03:  return(3);
+#endif
+#if (defined(JUDY1) && defined(JU_64BIT))
+        case cJ1_JPIMMED_2_04:  return(4);
+        case cJ1_JPIMMED_2_05:  return(5);
+        case cJ1_JPIMMED_2_06:  return(6);
+        case cJ1_JPIMMED_2_07:  return(7);
+#endif
+
+#if (defined(JUDY1) || defined(JU_64BIT))
+        case cJU_JPIMMED_3_02:  return(2);
+#endif
+#if (defined(JUDY1) && defined(JU_64BIT))
+        case cJ1_JPIMMED_3_03:  return(3);
+        case cJ1_JPIMMED_3_04:  return(4);
+        case cJ1_JPIMMED_3_05:  return(5);
+
+        case cJ1_JPIMMED_4_02:  return(2);
+        case cJ1_JPIMMED_4_03:  return(3);
+        case cJ1_JPIMMED_5_02:  return(2);
+        case cJ1_JPIMMED_5_03:  return(3);
+        case cJ1_JPIMMED_6_02:  return(2);
+        case cJ1_JPIMMED_7_02:  return(2);
+#endif
+
+        } // switch (JU_JPTYPE(Pjp))
+
+        assert(FALSE);          // unrecognized JP type => corruption.
+        return(0);              // to make some compilers happy.
+
+} // JudyCheckPopSM()
+
+#endif // DEBUG
+#endif // ! JUDYGETINLINE