summaryrefslogtreecommitdiffstats
path: root/libnetdata/libjudy/src/JudyCommon
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 14:31:17 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 14:31:17 +0000
commit8020f71afd34d7696d7933659df2d763ab05542f (patch)
tree2fdf1b5447ffd8bdd61e702ca183e814afdcb4fc /libnetdata/libjudy/src/JudyCommon
parentInitial commit. (diff)
downloadnetdata-upstream.tar.xz
netdata-upstream.zip
Adding upstream version 1.37.1.upstream/1.37.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'libnetdata/libjudy/src/JudyCommon')
-rw-r--r--libnetdata/libjudy/src/JudyCommon/JudyMalloc.c87
-rw-r--r--libnetdata/libjudy/src/JudyCommon/JudyPrivate.h1613
-rw-r--r--libnetdata/libjudy/src/JudyCommon/JudyPrivate1L.h485
-rw-r--r--libnetdata/libjudy/src/JudyCommon/JudyPrivateBranch.h788
4 files changed, 2973 insertions, 0 deletions
diff --git a/libnetdata/libjudy/src/JudyCommon/JudyMalloc.c b/libnetdata/libjudy/src/JudyCommon/JudyMalloc.c
new file mode 100644
index 0000000..09a20e3
--- /dev/null
+++ b/libnetdata/libjudy/src/JudyCommon/JudyMalloc.c
@@ -0,0 +1,87 @@
+// 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.33 $ $Source: /judy/src/JudyCommon/JudyMalloc.c $
+// ************************************************************************ //
+// JUDY - Memory Allocater //
+// -by- //
+// Douglas L. Baskins //
+// Hewlett Packard //
+// Fort Collins, Co //
+// (970) 229-2027 //
+// //
+// ************************************************************************ //
+
+// JUDY INCLUDE FILES
+#include "Judy.h"
+
+// ****************************************************************************
+// J U D Y M A L L O C
+//
+// Allocate RAM. This is the single location in Judy code that calls
+// malloc(3C). Note: JPM accounting occurs at a higher level.
+
+Word_t JudyMalloc(
+ Word_t Words)
+{
+ Word_t Addr;
+
+ Addr = (Word_t) malloc(Words * sizeof(Word_t));
+ return(Addr);
+
+} // JudyMalloc()
+
+
+// ****************************************************************************
+// J U D Y F R E E
+
+void JudyFree(
+ void * PWord,
+ Word_t Words)
+{
+ (void) Words;
+ free(PWord);
+
+} // JudyFree()
+
+
+// ****************************************************************************
+// J U D Y M A L L O C
+//
+// Higher-level "wrapper" for allocating objects that need not be in RAM,
+// although at this time they are in fact only in RAM. Later we hope that some
+// entire subtrees (at a JPM or branch) can be "virtual", so their allocations
+// and frees should go through this level.
+
+Word_t JudyMallocVirtual(
+ Word_t Words)
+{
+ return(JudyMalloc(Words));
+
+} // JudyMallocVirtual()
+
+
+// ****************************************************************************
+// J U D Y F R E E
+
+void JudyFreeVirtual(
+ void * PWord,
+ Word_t Words)
+{
+ JudyFree(PWord, Words);
+
+} // JudyFreeVirtual()
diff --git a/libnetdata/libjudy/src/JudyCommon/JudyPrivate.h b/libnetdata/libjudy/src/JudyCommon/JudyPrivate.h
new file mode 100644
index 0000000..350631f
--- /dev/null
+++ b/libnetdata/libjudy/src/JudyCommon/JudyPrivate.h
@@ -0,0 +1,1613 @@
+#ifndef _JUDYPRIVATE_INCLUDED
+#define _JUDYPRIVATE_INCLUDED
+// _________________
+//
+// 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.77 $ $Source: /judy/src/JudyCommon/JudyPrivate.h $
+//
+// Header file for all Judy sources, for global but private (non-exported)
+// declarations.
+
+#include "Judy.h"
+
+// ****************************************************************************
+// A VERY BRIEF EXPLANATION OF A JUDY ARRAY
+//
+// A Judy array is, effectively, a digital tree (or Trie) with 256 element
+// branches (nodes), and with "compression tricks" applied to low-population
+// branches or leaves to save a lot of memory at the cost of relatively little
+// CPU time or cache fills.
+//
+// In the actual implementation, a Judy array is level-less, and traversing the
+// "tree" actually means following the states in a state machine (SM) as
+// directed by the Index. A Judy array is referred to here as an "SM", rather
+// than as a "tree"; having "states", rather than "levels".
+//
+// Each branch or leaf in the SM decodes a portion ("digit") of the original
+// Index; with 256-way branches there are 8 bits per digit. There are 3 kinds
+// of branches, called: Linear, Bitmap and Uncompressed, of which the first 2
+// are compressed to contain no NULL entries.
+//
+// An Uncompressed branch has a 1.0 cache line fill cost to decode 8 bits of
+// (digit, part of an Index), but it might contain many NULL entries, and is
+// therefore inefficient with memory if lightly populated.
+//
+// A Linear branch has a ~1.75 cache line fill cost when at maximum population.
+// A Bitmap branch has ~2.0 cache line fills. Linear and Bitmap branches are
+// converted to Uncompressed branches when the additional memory can be
+// amortized with larger populations. Higher-state branches have higher
+// priority to be converted.
+//
+// Linear branches can hold 28 elements (based on detailed analysis) -- thus 28
+// expanses. A Linear branch is converted to a Bitmap branch when the 29th
+// expanse is required.
+//
+// A Bitmap branch could hold 256 expanses, but is forced to convert to an
+// Uncompressed branch when 185 expanses are required. Hopefully, it is
+// converted before that because of population growth (again, based on detailed
+// analysis and heuristics in the code).
+//
+// A path through the SM terminates to a leaf when the Index (or key)
+// population in the expanse below a pointer will fit into 1 or 2 cache lines
+// (~31..255 Indexes). A maximum-population Leaf has ~1.5 cache line fill
+// cost.
+//
+// Leaves are sorted arrays of Indexes, where the Index Sizes (IS) are: 0, 1,
+// 8, 16, 24, 32, [40, 48, 56, 64] bits. The IS depends on the "density"
+// (population/expanse) of the values in the Leaf. Zero bits are possible if
+// population == expanse in the SM (that is, a full small expanse).
+//
+// Elements of a branches are called Judy Pointers (JPs). Each JP object
+// points to the next object in the SM, plus, a JP can decode an additional
+// 2[6] bytes of an Index, but at the cost of "narrowing" the expanse
+// represented by the next object in the SM. A "narrow" JP (one which has
+// decode bytes/digits) is a way of skipping states in the SM.
+//
+// Although counterintuitive, we think a Judy SM is optimal when the Leaves are
+// stored at MINIMUM compression (narrowing, or use of Decode bytes). If more
+// aggressive compression was used, decompression of a leaf be required to
+// insert an index. Additional compression would save a little memory but not
+// help performance significantly.
+
+
+#ifdef A_PICTURE_IS_WORTH_1000_WORDS
+*******************************************************************************
+
+JUDY 32-BIT STATE MACHINE (SM) EXAMPLE, FOR INDEX = 0x02040103
+
+The Index used in this example is purposely chosen to allow small, simple
+examples below; each 1-byte "digit" from the Index has a small numeric value
+that fits in one column. In the drawing below:
+
+ JRP == Judy Root Pointer;
+
+ C == 1 byte of a 1..3 byte Population (count of Indexes) below this
+ pointer. Since this is shared with the Decode field, the combined
+ sizes must be 3[7], that is, 1 word less 1 byte for the JP Type.
+
+ The 1-byte field jp_Type is represented as:
+
+ 1..3 == Number of bytes in the population (Pop0) word of the Branch or Leaf
+ below the pointer (note: 1..7 on 64-bit); indicates:
+ - number of bytes in Decode field == 3 - this number;
+ - number of bytes remaining to decode.
+ Note: The maximum is 3, not 4, because the 1st byte of the Index is
+ always decoded digitally in the top branch.
+ -B- == JP points to a Branch (there are many kinds of Branches).
+ -L- == JP points to a Leaf (there are many kinds of Leaves).
+
+ (2) == Digit of Index decoded by position offset in branch (really
+ 0..0xff).
+
+ 4* == Digit of Index necessary for decoding a "narrow" pointer, in a
+ Decode field; replaces 1 missing branch (really 0..0xff).
+
+ 4+ == Digit of Index NOT necessary for decoding a "narrow" pointer, but
+ used for fast traversal of the SM by Judy1Test() and JudyLGet()
+ (see the code) (really 0..0xff).
+
+ 0 == Byte in a JPs Pop0 field that is always ignored, because a leaf
+ can never contain more than 256 Indexes (Pop0 <= 255).
+
+ +----- == A Branch or Leaf; drawn open-ended to remind you that it could
+ | have up to 256 columns.
+ +-----
+
+ |
+ | == Pointer to next Branch or Leaf.
+ V
+
+ |
+ O == A state is skipped by using a "narrow" pointer.
+ |
+
+ < 1 > == Digit (Index) shown as an example is not necessarily in the
+ position shown; is sorted in order with neighbor Indexes.
+ (Really 0..0xff.)
+
+Note that this example shows every possibly topology to reach a leaf in a
+32-bit Judy SM, although this is a very subtle point!
+
+ STATE or`
+ LEVEL
+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
+ |RJP| |RJP| |RJP| |RJP| |RJP| |RJP| |RJP| |RJP|
+ L---+ B---+ B---+ B---+ B---+ B---+ B---+ B---+
+ | | | | | | | |
+ | | | | | | | |
+ V V (2) V (2) V (2) V (2) V (2) V (2) V (2)
+ +------ +------ +------ +------ +------ +------ +------ +------
+Four |< 2 > | 0 | 4* | C | 4* | 4* | C | C
+byte |< 4 > | 0 | 0 | C | 1* | C | C | C 4
+Index|< 1 > | C | C | C | C | C | C | C
+Leaf |< 3 > | 3 | 2 | 3 | 1 | 2 | 3 | 3
+ +------ +--L--- +--L--- +--B--- +--L--- +--B--- +--B--- +--B---
+ | | | | | | |
+ / | / | | / /
+ / | / | | / /
+ | | | | | | |
+ V | V (4) | | V (4) V (4)
+ +------ | +------ | | +------ +------
+ Three |< 4 > | | 4+ | | | 4+ | 4+
+ byte Index|< 1 > O | 0 O O | 1* | C 3
+ Leaf |< 3 > | | C | | | C | C
+ +------ | | 2 | | | 1 | 2
+ / +----L- | | +----L- +----B-
+ / | | | | |
+ | / | / / /
+ | / | / / /
+ | / | | / /
+ | / | | / /
+ | | | | | |
+ V V | V(1) | V(1)
+ +------ +------ | +------ | +------
+ Two byte |< 1 > |< 1 > | | 4+ | | 4+
+ Index Leaf |< 3 > |< 3 > O | 1+ O | 1+ 2
+ +------ +------ / | C | | C
+ / | 1 | | 1
+ | +-L---- | +-L----
+ | | | |
+ | / | /
+ | | | |
+ V V V V
+ +------ +------ +------ +------
+ One byte Index Leaf |< 3 > |< 3 > |< 3 > |< 3 > 1
+ +------ +------ +------ +------
+
+
+#endif // A_PICTURE_IS_WORTH_1000_WORDS
+
+
+// ****************************************************************************
+// MISCELLANEOUS GLOBALS:
+//
+// PLATFORM-SPECIFIC CONVENIENCE MACROS:
+//
+// These are derived from context (set by cc or in system header files) or
+// based on JU_<PLATFORM> macros from make_includes/platform.*.mk. We decided
+// on 011018 that any macro reliably derivable from context (cc or headers) for
+// ALL platforms supported by Judy is based on that derivation, but ANY
+// exception means to stop using the external macro completely and derive from
+// JU_<PLATFORM> instead.
+
+// Other miscellaneous stuff:
+
+#ifndef _BOOL_T
+#define _BOOL_T
+typedef int bool_t;
+#endif
+
+#define FUNCTION // null; easy to find functions.
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+#ifdef TRACE // turn on all other tracing in the code:
+#define TRACEJP 1 // JP traversals in JudyIns.c and JudyDel.c.
+#define TRACEJPR 1 // JP traversals in retrieval code, JudyGet.c.
+#define TRACECF 1 // cache fills in JudyGet.c.
+#define TRACEMI 1 // malloc calls in JudyMallocIF.c.
+#define TRACEMF 1 // malloc calls at a lower level in JudyMalloc.c.
+#endif
+
+
+// SUPPORT FOR DEBUG-ONLY CODE:
+//
+// By convention, use -DDEBUG to enable both debug-only code AND assertions in
+// the Judy sources.
+//
+// Invert the sense of assertions, so they are off unless explicitly requested,
+// in a uniform way.
+//
+// Note: It is NOT appropriate to put this in Judy.h; it would mess up
+// application code.
+
+#ifndef DEBUG
+#define NDEBUG 1 // must be 1 for "#if".
+#endif
+
+// Shorthand notations to avoid #ifdefs for single-line conditional statements:
+//
+// Warning: These cannot be used around compiler directives, such as
+// "#include", nor in the case where Code contains a comma other than nested
+// within parentheses or quotes.
+
+#ifndef DEBUG
+#define DBGCODE(Code) // null.
+#else
+#define DBGCODE(Code) Code
+#endif
+
+#ifdef JUDY1
+#define JUDY1CODE(Code) Code
+#define JUDYLCODE(Code) // null.
+#endif
+
+#ifdef JUDYL
+#define JUDYLCODE(Code) Code
+#define JUDY1CODE(Code) // null.
+#endif
+
+#include <assert.h>
+
+// ****************************************************************************
+// FUNDAMENTAL CONSTANTS FOR MACHINE
+// ****************************************************************************
+
+// Machine (CPU) cache line size:
+//
+// NOTE: A leaf size of 2 cache lines maximum is the target (optimal) for
+// Judy. Its hard to obtain a machines cache line size at compile time, but
+// if the machine has an unexpected cache line size, its not devastating if
+// the following constants end up causing leaves that are 1 cache line in size,
+// or even 4 cache lines in size. The assumed 32-bit system has 16-word =
+// 64-byte cache lines, and the assumed 64-bit system has 16-word = 128-byte
+// cache lines.
+
+#ifdef JU_64BIT
+#define cJU_BYTESPERCL 128 // cache line size in bytes.
+#else
+#define cJU_BYTESPERCL 64 // cache line size in bytes.
+#endif
+
+// Bits Per Byte:
+
+#define cJU_BITSPERBYTE 0x8
+
+// Bytes Per Word and Bits Per Word, latter assuming sizeof(byte) is 8 bits:
+//
+// Expect 32 [64] bits per word.
+
+#define cJU_BYTESPERWORD (sizeof(Word_t))
+#define cJU_BITSPERWORD (sizeof(Word_t) * cJU_BITSPERBYTE)
+
+#define JU_BYTESTOWORDS(BYTES) \
+ (((BYTES) + cJU_BYTESPERWORD - 1) / cJU_BYTESPERWORD)
+
+// A word that is all-ones, normally equal to -1UL, but safer with ~0:
+
+#define cJU_ALLONES (~0UL)
+
+// Note, these are forward references, but thats OK:
+
+#define cJU_FULLBITMAPB ((BITMAPB_t) cJU_ALLONES)
+#define cJU_FULLBITMAPL ((BITMAPL_t) cJU_ALLONES)
+
+
+// ****************************************************************************
+// MISCELLANEOUS JUDY-SPECIFIC DECLARATIONS
+// ****************************************************************************
+
+// ROOT STATE:
+//
+// State at the start of the Judy SM, based on 1 byte decoded per state; equal
+// to the number of bytes per Index to decode.
+
+#define cJU_ROOTSTATE (sizeof(Word_t))
+
+
+// SUBEXPANSES PER STATE:
+//
+// Number of subexpanses per state traversed, which is the number of JPs in a
+// branch (actual or theoretical) and the number of bits in a bitmap.
+
+#define cJU_SUBEXPPERSTATE 256
+
+
+// LEAF AND VALUE POINTERS:
+//
+// Some other basic object types are in declared in JudyPrivateBranch.h
+// (Pjbl_t, Pjbb_t, Pjbu_t, Pjp_t) or are Judy1/L-specific (Pjlb_t). The
+// few remaining types are declared below.
+//
+// Note: Leaf pointers are cast to different-sized objects depending on the
+// leafs level, but are at least addresses (not just numbers), so use void *
+// (Pvoid_t), not PWord_t or Word_t for them, except use Pjlw_t for whole-word
+// (top-level, root-level) leaves. Value areas, however, are always whole
+// words.
+//
+// Furthermore, use Pjll_t only for generic leaf pointers (for various size
+// LeafLs). Use Pjlw_t for LeafWs. Use Pleaf (with type uint8_t *, uint16_t
+// *, etc) when the leaf index size is known.
+
+typedef PWord_t Pjlw_t; // pointer to root-level leaf (whole-word indexes).
+typedef Pvoid_t Pjll_t; // pointer to lower-level linear leaf.
+
+#ifdef JUDYL
+typedef PWord_t Pjv_t; // pointer to JudyL value area.
+#endif
+
+
+// POINTER PREPARATION MACROS:
+//
+// These macros are used to strip malloc-namespace-type bits from a pointer +
+// malloc-type word (which references any Judy mallocd object that might be
+// obtained from other than a direct call of malloc()), prior to dereferencing
+// the pointer as an address. The malloc-type bits allow Judy mallocd objects
+// to come from different "malloc() namespaces".
+//
+// (root pointer) (JRP, see above)
+// jp.jp_Addr generic pointer to next-level node, except when used
+// as a JudyL Immed01 value area
+// JU_JBB_PJP macro hides jbbs_Pjp (pointer to JP subarray)
+// JL_JLB_PVALUE macro hides jLlbs_PValue (pointer to value subarray)
+//
+// When setting one of these fields or passing an address to j__udyFree*(), the
+// "raw" memory address is used; otherwise the memory address must be passed
+// through one of the macros below before its dereferenced.
+//
+// Note: After much study, the typecasts below appear in the macros rather
+// than at the point of use, which is both simpler and allows the compiler to
+// do type-checking.
+
+
+#define P_JLW( ADDR) ((Pjlw_t) (ADDR)) // root leaf.
+#define P_JPM( ADDR) ((Pjpm_t) (ADDR)) // root JPM.
+#define P_JBL( ADDR) ((Pjbl_t) (ADDR)) // BranchL.
+#define P_JBB( ADDR) ((Pjbb_t) (ADDR)) // BranchB.
+#define P_JBU( ADDR) ((Pjbu_t) (ADDR)) // BranchU.
+#define P_JLL( ADDR) ((Pjll_t) (ADDR)) // LeafL.
+#define P_JLB( ADDR) ((Pjlb_t) (ADDR)) // LeafB1.
+#define P_JP( ADDR) ((Pjp_t) (ADDR)) // JP.
+
+#ifdef JUDYL
+#define P_JV( ADDR) ((Pjv_t) (ADDR)) // &value.
+#endif
+
+
+// LEAST BYTES:
+//
+// Mask for least bytes of a word, and a macro to perform this mask on an
+// Index.
+//
+// Note: This macro has been problematic in the past to get right and to make
+// portable. Its not OK on all systems to shift by the full word size. This
+// macro should allow shifting by 1..N bytes, where N is the word size, but
+// should produce a compiler warning if the macro is called with Bytes == 0.
+//
+// Warning: JU_LEASTBYTESMASK() is not a constant macro unless Bytes is a
+// constant; otherwise it is a variable shift, which is expensive on some
+// processors.
+
+#define JU_LEASTBYTESMASK(BYTES) \
+ ((0x100UL << (cJU_BITSPERBYTE * ((BYTES) - 1))) - 1)
+
+#define JU_LEASTBYTES(INDEX,BYTES) ((INDEX) & JU_LEASTBYTESMASK(BYTES))
+
+
+// BITS IN EACH BITMAP SUBEXPANSE FOR BITMAP BRANCH AND LEAF:
+//
+// The bits per bitmap subexpanse times the number of subexpanses equals a
+// constant (cJU_SUBEXPPERSTATE). You can also think of this as a compile-time
+// choice of "aspect ratio" for bitmap branches and leaves (which can be set
+// independently for each).
+//
+// A default aspect ratio is hardwired here if not overridden at compile time,
+// such as by "EXTCCOPTS=-DBITMAP_BRANCH16x16 make".
+
+#if (! (defined(BITMAP_BRANCH8x32) || defined(BITMAP_BRANCH16x16) || defined(BITMAP_BRANCH32x8)))
+#define BITMAP_BRANCH32x8 1 // 32 bits per subexpanse, 8 subexpanses.
+#endif
+
+#ifdef BITMAP_BRANCH8x32
+#define BITMAPB_t uint8_t
+#endif
+
+#ifdef BITMAP_BRANCH16x16
+#define BITMAPB_t uint16_t
+#endif
+
+#ifdef BITMAP_BRANCH32x8
+#define BITMAPB_t uint32_t
+#endif
+
+// Note: For bitmap leaves, BITMAP_LEAF64x4 is only valid for 64 bit:
+//
+// Note: Choice of aspect ratio mostly matters for JudyL bitmap leaves. For
+// Judy1 the choice doesnt matter much -- the code generated for different
+// BITMAP_LEAF* values choices varies, but correctness and performance are the
+// same.
+
+#ifndef JU_64BIT
+
+#if (! (defined(BITMAP_LEAF8x32) || defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8)))
+#define BITMAP_LEAF32x8 // 32 bits per subexpanse, 8 subexpanses.
+#endif
+
+#else // 32BIT
+
+#if (! (defined(BITMAP_LEAF8x32) || defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)))
+#define BITMAP_LEAF64x4 // 64 bits per subexpanse, 4 subexpanses.
+
+#endif
+#endif // JU_64BIT
+
+#ifdef BITMAP_LEAF8x32
+#define BITMAPL_t uint8_t
+#endif
+
+#ifdef BITMAP_LEAF16x16
+#define BITMAPL_t uint16_t
+#endif
+
+#ifdef BITMAP_LEAF32x8
+#define BITMAPL_t uint32_t
+#endif
+
+#ifdef BITMAP_LEAF64x4
+#define BITMAPL_t uint64_t
+#endif
+
+
+// EXPORTED DATA AND FUNCTIONS:
+
+#ifdef JUDY1
+extern const uint8_t j__1_BranchBJPPopToWords[];
+#endif
+
+#ifdef JUDYL
+extern const uint8_t j__L_BranchBJPPopToWords[];
+#endif
+
+// Fast LeafL search routine used for inlined code:
+
+#if (! defined(SEARCH_BINARY)) || (! defined(SEARCH_LINEAR))
+// default a binary search leaf method
+#define SEARCH_BINARY 1
+//#define SEARCH_LINEAR 1
+#endif
+
+#ifdef SEARCH_LINEAR
+
+#define SEARCHLEAFNATIVE(LEAFTYPE,ADDR,POP1,INDEX) \
+ LEAFTYPE *P_leaf = (LEAFTYPE *)(ADDR); \
+ LEAFTYPE I_ndex = (INDEX); /* with masking */ \
+ if (I_ndex > P_leaf[(POP1) - 1]) return(~(POP1)); \
+ while(I_ndex > *P_leaf) P_leaf++; \
+ if (I_ndex == *P_leaf) return(P_leaf - (LEAFTYPE *)(ADDR)); \
+ return(~(P_leaf - (LEAFTYPE *)(ADDR)));
+
+
+#define SEARCHLEAFNONNAT(ADDR,POP1,INDEX,LFBTS,COPYINDEX) \
+{ \
+ uint8_t *P_leaf, *P_leafEnd; \
+ Word_t i_ndex; \
+ Word_t I_ndex = JU_LEASTBYTES((INDEX), (LFBTS)); \
+ Word_t p_op1; \
+ \
+ P_leaf = (uint8_t *)(ADDR); \
+ P_leafEnd = P_leaf + ((POP1) * (LFBTS)); \
+ \
+ do { \
+ JU_COPY3_PINDEX_TO_LONG(i_ndex, P_leaf); \
+ if (I_ndex <= i_ndex) break; \
+ P_leaf += (LFBTS); \
+ } while (P_leaf < P_leafEnd); \
+ \
+ p_op1 = (P_leaf - (uint8_t *) (ADDR)) / (LFBTS); \
+ if (I_ndex == i_ndex) return(p_op1); \
+ return(~p_op1); \
+}
+#endif // SEARCH_LINEAR
+
+#ifdef SEARCH_BINARY
+
+#define SEARCHLEAFNATIVE(LEAFTYPE,ADDR,POP1,INDEX) \
+ LEAFTYPE *P_leaf = (LEAFTYPE *)(ADDR); \
+ LEAFTYPE I_ndex = (LEAFTYPE)INDEX; /* truncate hi bits */ \
+ Word_t l_ow = cJU_ALLONES; \
+ Word_t m_id; \
+ Word_t h_igh = POP1; \
+ \
+ while ((h_igh - l_ow) > 1UL) \
+ { \
+ m_id = (h_igh + l_ow) / 2; \
+ if (P_leaf[m_id] > I_ndex) \
+ h_igh = m_id; \
+ else \
+ l_ow = m_id; \
+ } \
+ if (l_ow == cJU_ALLONES || P_leaf[l_ow] != I_ndex) \
+ return(~h_igh); \
+ return(l_ow)
+
+
+#define SEARCHLEAFNONNAT(ADDR,POP1,INDEX,LFBTS,COPYINDEX) \
+ uint8_t *P_leaf = (uint8_t *)(ADDR); \
+ Word_t l_ow = cJU_ALLONES; \
+ Word_t m_id; \
+ Word_t h_igh = POP1; \
+ Word_t I_ndex = JU_LEASTBYTES((INDEX), (LFBTS)); \
+ Word_t i_ndex; \
+ \
+ I_ndex = JU_LEASTBYTES((INDEX), (LFBTS)); \
+ \
+ while ((h_igh - l_ow) > 1UL) \
+ { \
+ m_id = (h_igh + l_ow) / 2; \
+ COPYINDEX(i_ndex, &P_leaf[m_id * (LFBTS)]); \
+ if (i_ndex > I_ndex) \
+ h_igh = m_id; \
+ else \
+ l_ow = m_id; \
+ } \
+ if (l_ow == cJU_ALLONES) return(~h_igh); \
+ \
+ COPYINDEX(i_ndex, &P_leaf[l_ow * (LFBTS)]); \
+ if (i_ndex != I_ndex) return(~h_igh); \
+ return(l_ow)
+
+#endif // SEARCH_BINARY
+
+// Fast way to count bits set in 8..32[64]-bit int:
+//
+// For performance, j__udyCountBits*() are written to take advantage of
+// platform-specific features where available.
+//
+
+#ifdef JU_NOINLINE
+
+extern BITMAPB_t j__udyCountBitsB(BITMAPB_t word);
+extern BITMAPL_t j__udyCountBitsL(BITMAPL_t word);
+
+// Compiler supports inline
+
+#elif defined(JU_HPUX_IPF)
+
+#define j__udyCountBitsB(WORD) _Asm_popcnt(WORD)
+#define j__udyCountBitsL(WORD) _Asm_popcnt(WORD)
+
+#elif defined(JU_LINUX_IPF)
+
+static inline BITMAPB_t j__udyCountBitsB(BITMAPB_t word)
+{
+ BITMAPB_t result;
+ __asm__ ("popcnt %0=%1" : "=r" (result) : "r" (word));
+ return(result);
+}
+
+static inline BITMAPL_t j__udyCountBitsL(BITMAPL_t word)
+{
+ BITMAPL_t result;
+ __asm__ ("popcnt %0=%1" : "=r" (result) : "r" (word));
+ return(result);
+}
+
+
+#else // No instructions available, use inline code
+
+// ****************************************************************************
+// __ J U D Y C O U N T B I T S B
+//
+// Return the number of bits set in "Word", for a bitmap branch.
+//
+// Note: Bitmap branches have maximum bitmap size = 32 bits.
+
+#ifdef JU_WIN
+static __inline BITMAPB_t j__udyCountBitsB(BITMAPB_t word)
+#else
+static inline BITMAPB_t j__udyCountBitsB(BITMAPB_t word)
+#endif
+{
+ word = (word & 0x55555555) + ((word & 0xAAAAAAAA) >> 1);
+ word = (word & 0x33333333) + ((word & 0xCCCCCCCC) >> 2);
+ word = (word & 0x0F0F0F0F) + ((word & 0xF0F0F0F0) >> 4); // >= 8 bits.
+#if defined(BITMAP_BRANCH16x16) || defined(BITMAP_BRANCH32x8)
+ word = (word & 0x00FF00FF) + ((word & 0xFF00FF00) >> 8); // >= 16 bits.
+#endif
+
+#ifdef BITMAP_BRANCH32x8
+ word = (word & 0x0000FFFF) + ((word & 0xFFFF0000) >> 16); // >= 32 bits.
+#endif
+ return(word);
+
+} // j__udyCountBitsB()
+
+
+// ****************************************************************************
+// __ J U D Y C O U N T B I T S L
+//
+// Return the number of bits set in "Word", for a bitmap leaf.
+//
+// Note: Bitmap branches have maximum bitmap size = 32 bits.
+
+// Note: Need both 32-bit and 64-bit versions of j__udyCountBitsL() because
+// bitmap leaves can have 64-bit bitmaps.
+
+#ifdef JU_WIN
+static __inline BITMAPL_t j__udyCountBitsL(BITMAPL_t word)
+#else
+static inline BITMAPL_t j__udyCountBitsL(BITMAPL_t word)
+#endif
+{
+#ifndef JU_64BIT
+
+ word = (word & 0x55555555) + ((word & 0xAAAAAAAA) >> 1);
+ word = (word & 0x33333333) + ((word & 0xCCCCCCCC) >> 2);
+ word = (word & 0x0F0F0F0F) + ((word & 0xF0F0F0F0) >> 4); // >= 8 bits.
+#if defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8)
+ word = (word & 0x00FF00FF) + ((word & 0xFF00FF00) >> 8); // >= 16 bits.
+#endif
+#ifdef BITMAP_LEAF32x8
+ word = (word & 0x0000FFFF) + ((word & 0xFFFF0000) >> 16); // >= 32 bits.
+#endif
+
+#else // JU_64BIT
+
+ word = (word & 0x5555555555555555) + ((word & 0xAAAAAAAAAAAAAAAA) >> 1);
+ word = (word & 0x3333333333333333) + ((word & 0xCCCCCCCCCCCCCCCC) >> 2);
+ word = (word & 0x0F0F0F0F0F0F0F0F) + ((word & 0xF0F0F0F0F0F0F0F0) >> 4);
+#if defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)
+ word = (word & 0x00FF00FF00FF00FF) + ((word & 0xFF00FF00FF00FF00) >> 8);
+#endif
+#if defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)
+ word = (word & 0x0000FFFF0000FFFF) + ((word & 0xFFFF0000FFFF0000) >>16);
+#endif
+#ifdef BITMAP_LEAF64x4
+ word = (word & 0x00000000FFFFFFFF) + ((word & 0xFFFFFFFF00000000) >>32);
+#endif
+#endif // JU_64BIT
+
+ return(word);
+
+} // j__udyCountBitsL()
+
+#endif // Compiler supports inline
+
+// GET POP0:
+//
+// Get from jp_DcdPopO the Pop0 for various JP Types.
+//
+// Notes:
+//
+// - Different macros require different parameters...
+//
+// - There are no simple macros for cJU_BRANCH* Types because their
+// populations must be added up and dont reside in an already-calculated
+// place. (TBD: This is no longer true, now its in the JPM.)
+//
+// - cJU_JPIMM_POP0() is not defined because it would be redundant because the
+// Pop1 is already encoded in each enum name.
+//
+// - A linear or bitmap leaf Pop0 cannot exceed cJU_SUBEXPPERSTATE - 1 (Pop0 =
+// 0..255), so use a simpler, faster macro for it than for other JP Types.
+//
+// - Avoid any complex calculations that would slow down the compiled code.
+// Assume these macros are only called for the appropriate JP Types.
+// Unfortunately theres no way to trigger an assertion here if the JP type
+// is incorrect for the macro, because these are merely expressions, not
+// statements.
+
+#define JU_LEAFW_POP0(JRP) (*P_JLW(JRP))
+#define cJU_JPFULLPOPU1_POP0 (cJU_SUBEXPPERSTATE - 1)
+
+// GET JP Type:
+// Since bit fields greater than 32 bits are not supported in some compilers
+// the jp_DcdPopO field is expanded to include the jp_Type in the high 8 bits
+// of the Word_t.
+// First the read macro:
+
+#define JU_JPTYPE(PJP) ((PJP)->jp_Type)
+
+#define JU_JPLEAF_POP0(PJP) ((PJP)->jp_DcdP0[sizeof(Word_t) - 2])
+
+#ifdef JU_64BIT
+
+#define JU_JPDCDPOP0(PJP) \
+ ((Word_t)(PJP)->jp_DcdP0[0] << 48 | \
+ (Word_t)(PJP)->jp_DcdP0[1] << 40 | \
+ (Word_t)(PJP)->jp_DcdP0[2] << 32 | \
+ (Word_t)(PJP)->jp_DcdP0[3] << 24 | \
+ (Word_t)(PJP)->jp_DcdP0[4] << 16 | \
+ (Word_t)(PJP)->jp_DcdP0[5] << 8 | \
+ (Word_t)(PJP)->jp_DcdP0[6])
+
+
+#define JU_JPSETADT(PJP,ADDR,DCDPOP0,TYPE) \
+{ \
+ (PJP)->jp_Addr = (ADDR); \
+ (PJP)->jp_DcdP0[0] = (uint8_t)((Word_t)(DCDPOP0) >> 48); \
+ (PJP)->jp_DcdP0[1] = (uint8_t)((Word_t)(DCDPOP0) >> 40); \
+ (PJP)->jp_DcdP0[2] = (uint8_t)((Word_t)(DCDPOP0) >> 32); \
+ (PJP)->jp_DcdP0[3] = (uint8_t)((Word_t)(DCDPOP0) >> 24); \
+ (PJP)->jp_DcdP0[4] = (uint8_t)((Word_t)(DCDPOP0) >> 16); \
+ (PJP)->jp_DcdP0[5] = (uint8_t)((Word_t)(DCDPOP0) >> 8); \
+ (PJP)->jp_DcdP0[6] = (uint8_t)((Word_t)(DCDPOP0)); \
+ (PJP)->jp_Type = (TYPE); \
+}
+
+#else // 32 Bit
+
+#define JU_JPDCDPOP0(PJP) \
+ ((Word_t)(PJP)->jp_DcdP0[0] << 16 | \
+ (Word_t)(PJP)->jp_DcdP0[1] << 8 | \
+ (Word_t)(PJP)->jp_DcdP0[2])
+
+
+#define JU_JPSETADT(PJP,ADDR,DCDPOP0,TYPE) \
+{ \
+ (PJP)->jp_Addr = (ADDR); \
+ (PJP)->jp_DcdP0[0] = (uint8_t)((Word_t)(DCDPOP0) >> 16); \
+ (PJP)->jp_DcdP0[1] = (uint8_t)((Word_t)(DCDPOP0) >> 8); \
+ (PJP)->jp_DcdP0[2] = (uint8_t)((Word_t)(DCDPOP0)); \
+ (PJP)->jp_Type = (TYPE); \
+}
+
+#endif // 32 Bit
+
+// NUMBER OF BITS IN A BRANCH OR LEAF BITMAP AND SUBEXPANSE:
+//
+// Note: cJU_BITSPERBITMAP must be the same as the number of JPs in a branch.
+
+#define cJU_BITSPERBITMAP cJU_SUBEXPPERSTATE
+
+// Bitmaps are accessed in units of "subexpanses":
+
+#define cJU_BITSPERSUBEXPB (sizeof(BITMAPB_t) * cJU_BITSPERBYTE)
+#define cJU_NUMSUBEXPB (cJU_BITSPERBITMAP / cJU_BITSPERSUBEXPB)
+
+#define cJU_BITSPERSUBEXPL (sizeof(BITMAPL_t) * cJU_BITSPERBYTE)
+#define cJU_NUMSUBEXPL (cJU_BITSPERBITMAP / cJU_BITSPERSUBEXPL)
+
+
+// MASK FOR A SPECIFIED BIT IN A BITMAP:
+//
+// Warning: If BitNum is a variable, this results in a variable shift that is
+// expensive, at least on some processors. Use with caution.
+//
+// Warning: BitNum must be less than cJU_BITSPERWORD, that is, 0 ..
+// cJU_BITSPERWORD - 1, to avoid a truncated shift on some machines.
+//
+// TBD: Perhaps use an array[32] of masks instead of calculating them.
+
+#define JU_BITPOSMASKB(BITNUM) (1L << ((BITNUM) % cJU_BITSPERSUBEXPB))
+#define JU_BITPOSMASKL(BITNUM) (1L << ((BITNUM) % cJU_BITSPERSUBEXPL))
+
+
+// TEST/SET/CLEAR A BIT IN A BITMAP LEAF:
+//
+// Test if a byte-sized Digit (portion of Index) has a corresponding bit set in
+// a bitmap, or set a byte-sized Digits bit into a bitmap, by looking up the
+// correct subexpanse and then checking/setting the correct bit.
+//
+// Note: Mask higher bits, if any, for the convenience of the user of this
+// macro, in case they pass a full Index, not just a digit. If the caller has
+// a true 8-bit digit, make it of type uint8_t and the compiler should skip the
+// unnecessary mask step.
+
+#define JU_SUBEXPL(DIGIT) (((DIGIT) / cJU_BITSPERSUBEXPL) & (cJU_NUMSUBEXPL-1))
+
+#define JU_BITMAPTESTL(PJLB, INDEX) \
+ (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) & JU_BITPOSMASKL(INDEX))
+
+#define JU_BITMAPSETL(PJLB, INDEX) \
+ (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) |= JU_BITPOSMASKL(INDEX))
+
+#define JU_BITMAPCLEARL(PJLB, INDEX) \
+ (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) ^= JU_BITPOSMASKL(INDEX))
+
+
+// MAP BITMAP BIT OFFSET TO DIGIT:
+//
+// Given a digit variable to set, a bitmap branch or leaf subexpanse (base 0),
+// the bitmap (BITMAP*_t) for that subexpanse, and an offset (Nth set bit in
+// the bitmap, base 0), compute the digit (also base 0) corresponding to the
+// subexpanse and offset by counting all bits in the bitmap until offset+1 set
+// bits are seen. Avoid expensive variable shifts. Offset should be less than
+// the number of set bits in the bitmap; assert this.
+//
+// If theres a better way to do this, I dont know what it is.
+
+#define JU_BITMAPDIGITB(DIGIT,SUBEXP,BITMAP,OFFSET) \
+ { \
+ BITMAPB_t bitmap = (BITMAP); int remain = (OFFSET); \
+ (DIGIT) = (SUBEXP) * cJU_BITSPERSUBEXPB; \
+ \
+ while ((remain -= (bitmap & 1)) >= 0) \
+ { \
+ bitmap >>= 1; ++(DIGIT); \
+ assert((DIGIT) < ((SUBEXP) + 1) * cJU_BITSPERSUBEXPB); \
+ } \
+ }
+
+#define JU_BITMAPDIGITL(DIGIT,SUBEXP,BITMAP,OFFSET) \
+ { \
+ BITMAPL_t bitmap = (BITMAP); int remain = (OFFSET); \
+ (DIGIT) = (SUBEXP) * cJU_BITSPERSUBEXPL; \
+ \
+ while ((remain -= (bitmap & 1)) >= 0) \
+ { \
+ bitmap >>= 1; ++(DIGIT); \
+ assert((DIGIT) < ((SUBEXP) + 1) * cJU_BITSPERSUBEXPL); \
+ } \
+ }
+
+
+// MASKS FOR PORTIONS OF 32-BIT WORDS:
+//
+// These are useful for bitmap subexpanses.
+//
+// "LOWER"/"HIGHER" means bits representing lower/higher-valued Indexes. The
+// exact order of bits in the word is explicit here but is hidden from the
+// caller.
+//
+// "EXC" means exclusive of the specified bit; "INC" means inclusive.
+//
+// In each case, BitPos is either "JU_BITPOSMASK*(BitNum)", or a variable saved
+// from an earlier call of that macro; either way, it must be a 32-bit word
+// with a single bit set. In the first case, assume the compiler is smart
+// enough to optimize out common subexpressions.
+//
+// The expressions depend on unsigned decimal math that should be universal.
+
+#define JU_MASKLOWEREXC( BITPOS) ((BITPOS) - 1)
+#define JU_MASKLOWERINC( BITPOS) (JU_MASKLOWEREXC(BITPOS) | (BITPOS))
+#define JU_MASKHIGHERINC(BITPOS) (-(BITPOS))
+#define JU_MASKHIGHEREXC(BITPOS) (JU_MASKHIGHERINC(BITPOS) ^ (BITPOS))
+
+
+// ****************************************************************************
+// SUPPORT FOR NATIVE INDEX SIZES
+// ****************************************************************************
+//
+// Copy a series of generic objects (uint8_t, uint16_t, uint32_t, Word_t) from
+// one place to another.
+
+#define JU_COPYMEM(PDST,PSRC,POP1) \
+ { \
+ Word_t i_ndex = 0; \
+ assert((POP1) > 0); \
+ do { (PDST)[i_ndex] = (PSRC)[i_ndex]; } \
+ while (++i_ndex < (POP1)); \
+ }
+
+
+// ****************************************************************************
+// SUPPORT FOR NON-NATIVE INDEX SIZES
+// ****************************************************************************
+//
+// Copy a 3-byte Index pointed by a uint8_t * to a Word_t:
+//
+#define JU_COPY3_PINDEX_TO_LONG(DESTLONG,PINDEX) \
+ DESTLONG = (Word_t)(PINDEX)[0] << 16; \
+ DESTLONG += (Word_t)(PINDEX)[1] << 8; \
+ DESTLONG += (Word_t)(PINDEX)[2]
+
+// Copy a Word_t to a 3-byte Index pointed at by a uint8_t *:
+
+#define JU_COPY3_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
+ (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 16); \
+ (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 8); \
+ (PINDEX)[2] = (uint8_t)((SOURCELONG))
+
+#ifdef JU_64BIT
+
+// Copy a 5-byte Index pointed by a uint8_t * to a Word_t:
+//
+#define JU_COPY5_PINDEX_TO_LONG(DESTLONG,PINDEX) \
+ DESTLONG = (Word_t)(PINDEX)[0] << 32; \
+ DESTLONG += (Word_t)(PINDEX)[1] << 24; \
+ DESTLONG += (Word_t)(PINDEX)[2] << 16; \
+ DESTLONG += (Word_t)(PINDEX)[3] << 8; \
+ DESTLONG += (Word_t)(PINDEX)[4]
+
+// Copy a Word_t to a 5-byte Index pointed at by a uint8_t *:
+
+#define JU_COPY5_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
+ (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 32); \
+ (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 24); \
+ (PINDEX)[2] = (uint8_t)((SOURCELONG) >> 16); \
+ (PINDEX)[3] = (uint8_t)((SOURCELONG) >> 8); \
+ (PINDEX)[4] = (uint8_t)((SOURCELONG))
+
+// Copy a 6-byte Index pointed by a uint8_t * to a Word_t:
+//
+#define JU_COPY6_PINDEX_TO_LONG(DESTLONG,PINDEX) \
+ DESTLONG = (Word_t)(PINDEX)[0] << 40; \
+ DESTLONG += (Word_t)(PINDEX)[1] << 32; \
+ DESTLONG += (Word_t)(PINDEX)[2] << 24; \
+ DESTLONG += (Word_t)(PINDEX)[3] << 16; \
+ DESTLONG += (Word_t)(PINDEX)[4] << 8; \
+ DESTLONG += (Word_t)(PINDEX)[5]
+
+// Copy a Word_t to a 6-byte Index pointed at by a uint8_t *:
+
+#define JU_COPY6_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
+ (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 40); \
+ (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 32); \
+ (PINDEX)[2] = (uint8_t)((SOURCELONG) >> 24); \
+ (PINDEX)[3] = (uint8_t)((SOURCELONG) >> 16); \
+ (PINDEX)[4] = (uint8_t)((SOURCELONG) >> 8); \
+ (PINDEX)[5] = (uint8_t)((SOURCELONG))
+
+// Copy a 7-byte Index pointed by a uint8_t * to a Word_t:
+//
+#define JU_COPY7_PINDEX_TO_LONG(DESTLONG,PINDEX) \
+ DESTLONG = (Word_t)(PINDEX)[0] << 48; \
+ DESTLONG += (Word_t)(PINDEX)[1] << 40; \
+ DESTLONG += (Word_t)(PINDEX)[2] << 32; \
+ DESTLONG += (Word_t)(PINDEX)[3] << 24; \
+ DESTLONG += (Word_t)(PINDEX)[4] << 16; \
+ DESTLONG += (Word_t)(PINDEX)[5] << 8; \
+ DESTLONG += (Word_t)(PINDEX)[6]
+
+// Copy a Word_t to a 7-byte Index pointed at by a uint8_t *:
+
+#define JU_COPY7_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
+ (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 48); \
+ (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 40); \
+ (PINDEX)[2] = (uint8_t)((SOURCELONG) >> 32); \
+ (PINDEX)[3] = (uint8_t)((SOURCELONG) >> 24); \
+ (PINDEX)[4] = (uint8_t)((SOURCELONG) >> 16); \
+ (PINDEX)[5] = (uint8_t)((SOURCELONG) >> 8); \
+ (PINDEX)[6] = (uint8_t)((SOURCELONG))
+
+#endif // JU_64BIT
+
+// ****************************************************************************
+// COMMON CODE FRAGMENTS (MACROS)
+// ****************************************************************************
+//
+// These code chunks are shared between various source files.
+
+
+// SET (REPLACE) ONE DIGIT IN AN INDEX:
+//
+// To avoid endian issues, use masking and ORing, which operates in a
+// big-endian register, rather than treating the Index as an array of bytes,
+// though that would be simpler, but would operate in endian-specific memory.
+//
+// TBD: This contains two variable shifts, is that bad?
+
+#define JU_SETDIGIT(INDEX,DIGIT,STATE) \
+ (INDEX) = ((INDEX) & (~cJU_MASKATSTATE(STATE))) \
+ | (((Word_t) (DIGIT)) \
+ << (((STATE) - 1) * cJU_BITSPERBYTE))
+
+// Fast version for single LSB:
+
+#define JU_SETDIGIT1(INDEX,DIGIT) (INDEX) = ((INDEX) & ~0xff) | (DIGIT)
+
+
+// SET (REPLACE) "N" LEAST DIGITS IN AN INDEX:
+
+#define JU_SETDIGITS(INDEX,INDEX2,cSTATE) \
+ (INDEX) = ((INDEX ) & (~JU_LEASTBYTESMASK(cSTATE))) \
+ | ((INDEX2) & ( JU_LEASTBYTESMASK(cSTATE)))
+
+// COPY DECODE BYTES FROM JP TO INDEX:
+//
+// Modify Index digit(s) to match the bytes in jp_DcdPopO in case one or more
+// branches are skipped and the digits are significant. Its probably faster
+// to just do this unconditionally than to check if its necessary.
+//
+// To avoid endian issues, use masking and ORing, which operates in a
+// big-endian register, rather than treating the Index as an array of bytes,
+// though that would be simpler, but would operate in endian-specific memory.
+//
+// WARNING: Must not call JU_LEASTBYTESMASK (via cJU_DCDMASK) with Bytes =
+// cJU_ROOTSTATE or a bad mask is generated, but there are no Dcd bytes to copy
+// in this case anyway. In fact there are no Dcd bytes unless State <
+// cJU_ROOTSTATE - 1, so dont call this macro except in those cases.
+//
+// TBD: It would be nice to validate jp_DcdPopO against known digits to ensure
+// no corruption, but this is non-trivial.
+
+#define JU_SETDCD(INDEX,PJP,cSTATE) \
+ (INDEX) = ((INDEX) & ~cJU_DCDMASK(cSTATE)) \
+ | (JU_JPDCDPOP0(PJP) & cJU_DCDMASK(cSTATE))
+
+// INSERT/DELETE AN INDEX IN-PLACE IN MEMORY:
+//
+// Given a pointer to an array of "even" (native), same-sized objects
+// (indexes), the current population of the array, an offset in the array, and
+// a new Index to insert, "shift up" the array elements (Indexes) above the
+// insertion point and insert the new Index. Assume there is sufficient memory
+// to do this.
+//
+// In these macros, "i_offset" is an index offset, and "b_off" is a byte
+// offset for odd Index sizes.
+//
+// Note: Endian issues only arise fro insertion, not deletion, and even for
+// insertion, they are transparent when native (even) objects are used, and
+// handled explicitly for odd (non-native) Index sizes.
+//
+// Note: The following macros are tricky enough that there is some test code
+// for them appended to this file.
+
+#define JU_INSERTINPLACE(PARRAY,POP1,OFFSET,INDEX) \
+ assert((long) (POP1) > 0); \
+ assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
+ { \
+ Word_t i_offset = (POP1); \
+ \
+ while (i_offset-- > (OFFSET)) \
+ (PARRAY)[i_offset + 1] = (PARRAY)[i_offset]; \
+ \
+ (PARRAY)[OFFSET] = (INDEX); \
+ }
+
+
+// Variation for non-native Indexes, where cIS = Index Size
+// and PByte must point to a uint8_t (byte); shift byte-by-byte:
+//
+
+#define JU_INSERTINPLACE3(PBYTE,POP1,OFFSET,INDEX) \
+{ \
+ Word_t i_off = POP1; \
+ \
+ while (i_off-- > (OFFSET)) \
+ { \
+ Word_t i_dx = i_off * 3; \
+ (PBYTE)[i_dx + 0 + 3] = (PBYTE)[i_dx + 0]; \
+ (PBYTE)[i_dx + 1 + 3] = (PBYTE)[i_dx + 1]; \
+ (PBYTE)[i_dx + 2 + 3] = (PBYTE)[i_dx + 2]; \
+ } \
+ JU_COPY3_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 3]), INDEX); \
+}
+
+#ifdef JU_64BIT
+
+#define JU_INSERTINPLACE5(PBYTE,POP1,OFFSET,INDEX) \
+{ \
+ Word_t i_off = POP1; \
+ \
+ while (i_off-- > (OFFSET)) \
+ { \
+ Word_t i_dx = i_off * 5; \
+ (PBYTE)[i_dx + 0 + 5] = (PBYTE)[i_dx + 0]; \
+ (PBYTE)[i_dx + 1 + 5] = (PBYTE)[i_dx + 1]; \
+ (PBYTE)[i_dx + 2 + 5] = (PBYTE)[i_dx + 2]; \
+ (PBYTE)[i_dx + 3 + 5] = (PBYTE)[i_dx + 3]; \
+ (PBYTE)[i_dx + 4 + 5] = (PBYTE)[i_dx + 4]; \
+ } \
+ JU_COPY5_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 5]), INDEX); \
+}
+
+#define JU_INSERTINPLACE6(PBYTE,POP1,OFFSET,INDEX) \
+{ \
+ Word_t i_off = POP1; \
+ \
+ while (i_off-- > (OFFSET)) \
+ { \
+ Word_t i_dx = i_off * 6; \
+ (PBYTE)[i_dx + 0 + 6] = (PBYTE)[i_dx + 0]; \
+ (PBYTE)[i_dx + 1 + 6] = (PBYTE)[i_dx + 1]; \
+ (PBYTE)[i_dx + 2 + 6] = (PBYTE)[i_dx + 2]; \
+ (PBYTE)[i_dx + 3 + 6] = (PBYTE)[i_dx + 3]; \
+ (PBYTE)[i_dx + 4 + 6] = (PBYTE)[i_dx + 4]; \
+ (PBYTE)[i_dx + 5 + 6] = (PBYTE)[i_dx + 5]; \
+ } \
+ JU_COPY6_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 6]), INDEX); \
+}
+
+#define JU_INSERTINPLACE7(PBYTE,POP1,OFFSET,INDEX) \
+{ \
+ Word_t i_off = POP1; \
+ \
+ while (i_off-- > (OFFSET)) \
+ { \
+ Word_t i_dx = i_off * 7; \
+ (PBYTE)[i_dx + 0 + 7] = (PBYTE)[i_dx + 0]; \
+ (PBYTE)[i_dx + 1 + 7] = (PBYTE)[i_dx + 1]; \
+ (PBYTE)[i_dx + 2 + 7] = (PBYTE)[i_dx + 2]; \
+ (PBYTE)[i_dx + 3 + 7] = (PBYTE)[i_dx + 3]; \
+ (PBYTE)[i_dx + 4 + 7] = (PBYTE)[i_dx + 4]; \
+ (PBYTE)[i_dx + 5 + 7] = (PBYTE)[i_dx + 5]; \
+ (PBYTE)[i_dx + 6 + 7] = (PBYTE)[i_dx + 6]; \
+ } \
+ JU_COPY7_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 7]), INDEX); \
+}
+#endif // JU_64BIT
+
+// Counterparts to the above for deleting an Index:
+//
+// "Shift down" the array elements starting at the Index to be deleted.
+
+#define JU_DELETEINPLACE(PARRAY,POP1,OFFSET,IGNORE) \
+ assert((long) (POP1) > 0); \
+ assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
+ { \
+ Word_t i_offset = (OFFSET); \
+ \
+ while (++i_offset < (POP1)) \
+ (PARRAY)[i_offset - 1] = (PARRAY)[i_offset]; \
+ }
+
+// Variation for odd-byte-sized (non-native) Indexes, where cIS = Index Size
+// and PByte must point to a uint8_t (byte); copy byte-by-byte:
+//
+// Note: If cIS == 1, JU_DELETEINPLACE_ODD == JU_DELETEINPLACE.
+//
+// Note: There are no endian issues here because bytes are just shifted as-is,
+// not converted to/from an Index.
+
+#define JU_DELETEINPLACE_ODD(PBYTE,POP1,OFFSET,cIS) \
+ assert((long) (POP1) > 0); \
+ assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
+ { \
+ Word_t b_off = (((OFFSET) + 1) * (cIS)) - 1; \
+ \
+ while (++b_off < ((POP1) * (cIS))) \
+ (PBYTE)[b_off - (cIS)] = (PBYTE)[b_off]; \
+ }
+
+
+// INSERT/DELETE AN INDEX WHILE COPYING OTHERS:
+//
+// Copy PSource[] to PDest[], where PSource[] has Pop1 elements (Indexes),
+// inserting Index at PDest[Offset]. Unlike JU_*INPLACE*() above, these macros
+// are used when moving Indexes from one memory object to another.
+
+#define JU_INSERTCOPY(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
+ assert((long) (POP1) > 0); \
+ assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
+ { \
+ Word_t i_offset; \
+ \
+ for (i_offset = 0; i_offset < (OFFSET); ++i_offset) \
+ (PDEST)[i_offset] = (PSOURCE)[i_offset]; \
+ \
+ (PDEST)[i_offset] = (INDEX); \
+ \
+ for (/* null */; i_offset < (POP1); ++i_offset) \
+ (PDEST)[i_offset + 1] = (PSOURCE)[i_offset]; \
+ }
+
+#define JU_INSERTCOPY3(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
+assert((long) (POP1) > 0); \
+assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
+{ \
+ Word_t o_ff; \
+ \
+ for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 3; \
+ (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
+ } \
+ JU_COPY3_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 3]), INDEX); \
+ \
+ for (/* null */; o_ff < (POP1); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 3; \
+ (PDEST)[i_dx + 0 + 3] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1 + 3] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2 + 3] = (PSOURCE)[i_dx + 2]; \
+ } \
+}
+
+#ifdef JU_64BIT
+
+#define JU_INSERTCOPY5(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
+assert((long) (POP1) > 0); \
+assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
+{ \
+ Word_t o_ff; \
+ \
+ for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 5; \
+ (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
+ (PDEST)[i_dx + 3] = (PSOURCE)[i_dx + 3]; \
+ (PDEST)[i_dx + 4] = (PSOURCE)[i_dx + 4]; \
+ } \
+ JU_COPY5_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 5]), INDEX); \
+ \
+ for (/* null */; o_ff < (POP1); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 5; \
+ (PDEST)[i_dx + 0 + 5] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1 + 5] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2 + 5] = (PSOURCE)[i_dx + 2]; \
+ (PDEST)[i_dx + 3 + 5] = (PSOURCE)[i_dx + 3]; \
+ (PDEST)[i_dx + 4 + 5] = (PSOURCE)[i_dx + 4]; \
+ } \
+}
+
+#define JU_INSERTCOPY6(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
+assert((long) (POP1) > 0); \
+assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
+{ \
+ Word_t o_ff; \
+ \
+ for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 6; \
+ (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
+ (PDEST)[i_dx + 3] = (PSOURCE)[i_dx + 3]; \
+ (PDEST)[i_dx + 4] = (PSOURCE)[i_dx + 4]; \
+ (PDEST)[i_dx + 5] = (PSOURCE)[i_dx + 5]; \
+ } \
+ JU_COPY6_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 6]), INDEX); \
+ \
+ for (/* null */; o_ff < (POP1); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 6; \
+ (PDEST)[i_dx + 0 + 6] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1 + 6] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2 + 6] = (PSOURCE)[i_dx + 2]; \
+ (PDEST)[i_dx + 3 + 6] = (PSOURCE)[i_dx + 3]; \
+ (PDEST)[i_dx + 4 + 6] = (PSOURCE)[i_dx + 4]; \
+ (PDEST)[i_dx + 5 + 6] = (PSOURCE)[i_dx + 5]; \
+ } \
+}
+
+#define JU_INSERTCOPY7(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
+assert((long) (POP1) > 0); \
+assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
+{ \
+ Word_t o_ff; \
+ \
+ for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 7; \
+ (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
+ (PDEST)[i_dx + 3] = (PSOURCE)[i_dx + 3]; \
+ (PDEST)[i_dx + 4] = (PSOURCE)[i_dx + 4]; \
+ (PDEST)[i_dx + 5] = (PSOURCE)[i_dx + 5]; \
+ (PDEST)[i_dx + 6] = (PSOURCE)[i_dx + 6]; \
+ } \
+ JU_COPY7_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 7]), INDEX); \
+ \
+ for (/* null */; o_ff < (POP1); o_ff++) \
+ { \
+ Word_t i_dx = o_ff * 7; \
+ (PDEST)[i_dx + 0 + 7] = (PSOURCE)[i_dx + 0]; \
+ (PDEST)[i_dx + 1 + 7] = (PSOURCE)[i_dx + 1]; \
+ (PDEST)[i_dx + 2 + 7] = (PSOURCE)[i_dx + 2]; \
+ (PDEST)[i_dx + 3 + 7] = (PSOURCE)[i_dx + 3]; \
+ (PDEST)[i_dx + 4 + 7] = (PSOURCE)[i_dx + 4]; \
+ (PDEST)[i_dx + 5 + 7] = (PSOURCE)[i_dx + 5]; \
+ (PDEST)[i_dx + 6 + 7] = (PSOURCE)[i_dx + 6]; \
+ } \
+}
+
+#endif // JU_64BIT
+
+// Counterparts to the above for deleting an Index:
+
+#define JU_DELETECOPY(PDEST,PSOURCE,POP1,OFFSET,IGNORE) \
+ assert((long) (POP1) > 0); \
+ assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
+ { \
+ Word_t i_offset; \
+ \
+ for (i_offset = 0; i_offset < (OFFSET); ++i_offset) \
+ (PDEST)[i_offset] = (PSOURCE)[i_offset]; \
+ \
+ for (++i_offset; i_offset < (POP1); ++i_offset) \
+ (PDEST)[i_offset - 1] = (PSOURCE)[i_offset]; \
+ }
+
+// Variation for odd-byte-sized (non-native) Indexes, where cIS = Index Size;
+// copy byte-by-byte:
+//
+// Note: There are no endian issues here because bytes are just shifted as-is,
+// not converted to/from an Index.
+//
+// Note: If cIS == 1, JU_DELETECOPY_ODD == JU_DELETECOPY, at least in concept.
+
+#define JU_DELETECOPY_ODD(PDEST,PSOURCE,POP1,OFFSET,cIS) \
+ assert((long) (POP1) > 0); \
+ assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
+ { \
+ uint8_t *_Pdest = (uint8_t *) (PDEST); \
+ uint8_t *_Psource = (uint8_t *) (PSOURCE); \
+ Word_t b_off; \
+ \
+ for (b_off = 0; b_off < ((OFFSET) * (cIS)); ++b_off) \
+ *_Pdest++ = *_Psource++; \
+ \
+ _Psource += (cIS); \
+ \
+ for (b_off += (cIS); b_off < ((POP1) * (cIS)); ++b_off) \
+ *_Pdest++ = *_Psource++; \
+ }
+
+
+// GENERIC RETURN CODE HANDLING FOR JUDY1 (NO VALUE AREAS) AND JUDYL (VALUE
+// AREAS):
+//
+// This common code hides Judy1 versus JudyL details of how to return various
+// conditions, including a pointer to a value area for JudyL.
+//
+// First, define an internal variation of JERR called JERRI (I = int) to make
+// lint happy. We accidentally shipped to 11.11 OEUR with all functions that
+// return int or Word_t using JERR, which is type Word_t, for errors. Lint
+// complains about this for functions that return int. So, internally use
+// JERRI for error returns from the int functions. Experiments show that
+// callers which compare int Foo() to (Word_t) JERR (~0UL) are OK, since JERRI
+// sign-extends to match JERR.
+
+#define JERRI ((int) ~0) // see above.
+
+#ifdef JUDY1
+
+#define JU_RET_FOUND return(1)
+#define JU_RET_NOTFOUND return(0)
+
+// For Judy1, these all "fall through" to simply JU_RET_FOUND, since there is no
+// value area pointer to return:
+
+#define JU_RET_FOUND_LEAFW(PJLW,POP1,OFFSET) JU_RET_FOUND
+
+#define JU_RET_FOUND_JPM(Pjpm) JU_RET_FOUND
+#define JU_RET_FOUND_PVALUE(Pjv,OFFSET) JU_RET_FOUND
+#ifndef JU_64BIT
+#define JU_RET_FOUND_LEAF1(Pjll,POP1,OFFSET) JU_RET_FOUND
+#endif
+#define JU_RET_FOUND_LEAF2(Pjll,POP1,OFFSET) JU_RET_FOUND
+#define JU_RET_FOUND_LEAF3(Pjll,POP1,OFFSET) JU_RET_FOUND
+#ifdef JU_64BIT
+#define JU_RET_FOUND_LEAF4(Pjll,POP1,OFFSET) JU_RET_FOUND
+#define JU_RET_FOUND_LEAF5(Pjll,POP1,OFFSET) JU_RET_FOUND
+#define JU_RET_FOUND_LEAF6(Pjll,POP1,OFFSET) JU_RET_FOUND
+#define JU_RET_FOUND_LEAF7(Pjll,POP1,OFFSET) JU_RET_FOUND
+#endif
+#define JU_RET_FOUND_IMM_01(Pjp) JU_RET_FOUND
+#define JU_RET_FOUND_IMM(Pjp,OFFSET) JU_RET_FOUND
+
+// Note: No JudyL equivalent:
+
+#define JU_RET_FOUND_FULLPOPU1 JU_RET_FOUND
+#define JU_RET_FOUND_LEAF_B1(PJLB,SUBEXP,OFFSET) JU_RET_FOUND
+
+#else // JUDYL
+
+// JU_RET_FOUND // see below; must NOT be defined for JudyL.
+#define JU_RET_NOTFOUND return((PPvoid_t) NULL)
+
+// For JudyL, the location of the value area depends on the JP type and other
+// factors:
+//
+// TBD: The value areas should be accessed via data structures, here and in
+// Dougs code, not by hard-coded address calculations.
+//
+// This is useful in insert/delete code when the value area is returned from
+// lower levels in the JPM:
+
+#define JU_RET_FOUND_JPM(Pjpm) return((PPvoid_t) ((Pjpm)->jpm_PValue))
+
+// This is useful in insert/delete code when the value area location is already
+// computed:
+
+#define JU_RET_FOUND_PVALUE(Pjv,OFFSET) return((PPvoid_t) ((Pjv) + OFFSET))
+
+#define JU_RET_FOUND_LEAFW(PJLW,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAFWVALUEAREA(PJLW, POP1) + (OFFSET)))
+
+#define JU_RET_FOUND_LEAF1(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF1VALUEAREA(Pjll, POP1) + (OFFSET)))
+#define JU_RET_FOUND_LEAF2(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF2VALUEAREA(Pjll, POP1) + (OFFSET)))
+#define JU_RET_FOUND_LEAF3(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF3VALUEAREA(Pjll, POP1) + (OFFSET)))
+#ifdef JU_64BIT
+#define JU_RET_FOUND_LEAF4(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF4VALUEAREA(Pjll, POP1) + (OFFSET)))
+#define JU_RET_FOUND_LEAF5(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF5VALUEAREA(Pjll, POP1) + (OFFSET)))
+#define JU_RET_FOUND_LEAF6(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF6VALUEAREA(Pjll, POP1) + (OFFSET)))
+#define JU_RET_FOUND_LEAF7(Pjll,POP1,OFFSET) \
+ return((PPvoid_t) (JL_LEAF7VALUEAREA(Pjll, POP1) + (OFFSET)))
+#endif
+
+// Note: Here jp_Addr is a value area itself and not an address, so P_JV() is
+// not needed:
+
+#define JU_RET_FOUND_IMM_01(PJP) return((PPvoid_t) (&((PJP)->jp_Addr)))
+
+// Note: Here jp_Addr is a pointer to a separately-mallocd value area, so
+// P_JV() is required; likewise for JL_JLB_PVALUE:
+
+#define JU_RET_FOUND_IMM(PJP,OFFSET) \
+ return((PPvoid_t) (P_JV((PJP)->jp_Addr) + (OFFSET)))
+
+#define JU_RET_FOUND_LEAF_B1(PJLB,SUBEXP,OFFSET) \
+ return((PPvoid_t) (P_JV(JL_JLB_PVALUE(PJLB, SUBEXP)) + (OFFSET)))
+
+#endif // JUDYL
+
+
+// GENERIC ERROR HANDLING:
+//
+// This is complicated by variations in the needs of the callers of these
+// macros. Only use JU_SET_ERRNO() for PJError, because it can be null; use
+// JU_SET_ERRNO_NONNULL() for Pjpm, which is never null, and also in other
+// cases where the pointer is known not to be null (to save dead branches).
+//
+// Note: Most cases of JU_ERRNO_OVERRUN or JU_ERRNO_CORRUPT should result in
+// an assertion failure in debug code, so they are more likely to be caught, so
+// do that here in each macro.
+
+#define JU_SET_ERRNO(PJError, JErrno) \
+ { \
+ assert((JErrno) != JU_ERRNO_OVERRUN); \
+ assert((JErrno) != JU_ERRNO_CORRUPT); \
+ \
+ if (PJError != (PJError_t) NULL) \
+ { \
+ JU_ERRNO(PJError) = (JErrno); \
+ JU_ERRID(PJError) = __LINE__; \
+ } \
+ }
+
+// Variation for callers who know already that PJError is non-null; and, it can
+// also be Pjpm (both PJError_t and Pjpm_t have je_* fields), so only assert it
+// for null, not cast to any specific pointer type:
+
+#define JU_SET_ERRNO_NONNULL(PJError, JErrno) \
+ { \
+ assert((JErrno) != JU_ERRNO_OVERRUN); \
+ assert((JErrno) != JU_ERRNO_CORRUPT); \
+ assert(PJError); \
+ \
+ JU_ERRNO(PJError) = (JErrno); \
+ JU_ERRID(PJError) = __LINE__; \
+ }
+
+// Variation to copy error info from a (required) JPM to an (optional)
+// PJError_t:
+//
+// Note: The assertions above about JU_ERRNO_OVERRUN and JU_ERRNO_CORRUPT
+// should have already popped, so they are not needed here.
+
+#define JU_COPY_ERRNO(PJError, Pjpm) \
+ { \
+ if (PJError) \
+ { \
+ JU_ERRNO(PJError) = (uint8_t)JU_ERRNO(Pjpm); \
+ JU_ERRID(PJError) = JU_ERRID(Pjpm); \
+ } \
+ }
+
+// For JErrno parameter to previous macros upon return from Judy*Alloc*():
+//
+// The memory allocator returns an address of 0 for out of memory,
+// 1..sizeof(Word_t)-1 for corruption (an invalid pointer), otherwise a valid
+// pointer.
+
+#define JU_ALLOC_ERRNO(ADDR) \
+ (((void *) (ADDR) != (void *) NULL) ? JU_ERRNO_OVERRUN : JU_ERRNO_NOMEM)
+
+#define JU_CHECKALLOC(Type,Ptr,Retval) \
+ if ((Ptr) < (Type) sizeof(Word_t)) \
+ { \
+ JU_SET_ERRNO(PJError, JU_ALLOC_ERRNO(Ptr)); \
+ return(Retval); \
+ }
+
+// Leaf search routines
+
+#ifdef JU_NOINLINE
+
+int j__udySearchLeaf1(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+int j__udySearchLeaf2(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+int j__udySearchLeaf3(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+
+#ifdef JU_64BIT
+
+int j__udySearchLeaf4(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+int j__udySearchLeaf5(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+int j__udySearchLeaf6(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+int j__udySearchLeaf7(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
+
+#endif // JU_64BIT
+
+int j__udySearchLeafW(Pjlw_t Pjlw, Word_t LeafPop1, Word_t Index);
+
+#else // complier support for inline
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf1(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf1(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNATIVE(uint8_t, Pjll, LeafPop1, Index); }
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf2(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf2(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNATIVE(uint16_t, Pjll, LeafPop1, Index); }
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf3(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf3(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 3, JU_COPY3_PINDEX_TO_LONG); }
+
+#ifdef JU_64BIT
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf4(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf4(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNATIVE(uint32_t, Pjll, LeafPop1, Index); }
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf5(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf5(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 5, JU_COPY5_PINDEX_TO_LONG); }
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf6(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf6(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 6, JU_COPY6_PINDEX_TO_LONG); }
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeaf7(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeaf7(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 7, JU_COPY7_PINDEX_TO_LONG); }
+
+#endif // JU_64BIT
+
+#ifdef JU_WIN
+static __inline int j__udySearchLeafW(Pjlw_t Pjlw, Word_t LeafPop1, Word_t Index)
+#else
+static inline int j__udySearchLeafW(Pjlw_t Pjlw, Word_t LeafPop1, Word_t Index)
+#endif
+{ SEARCHLEAFNATIVE(Word_t, Pjlw, LeafPop1, Index); }
+
+#endif // compiler support for inline
+
+#endif // ! _JUDYPRIVATE_INCLUDED
diff --git a/libnetdata/libjudy/src/JudyCommon/JudyPrivate1L.h b/libnetdata/libjudy/src/JudyCommon/JudyPrivate1L.h
new file mode 100644
index 0000000..5b47048
--- /dev/null
+++ b/libnetdata/libjudy/src/JudyCommon/JudyPrivate1L.h
@@ -0,0 +1,485 @@
+#ifndef _JUDYPRIVATE1L_INCLUDED
+#define _JUDYPRIVATE1L_INCLUDED
+// _________________
+//
+// 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.31 $ $Source: /judy/src/JudyCommon/JudyPrivate1L.h $
+
+// ****************************************************************************
+// Declare common cJU_* names for JP Types that occur in both Judy1 and JudyL,
+// for use by code that ifdefs JUDY1 and JUDYL. Only JP Types common to both
+// Judy1 and JudyL are #defined here with equivalent cJU_* names. JP Types
+// unique to only Judy1 or JudyL are listed in comments, so the type lists
+// match the Judy1.h and JudyL.h files.
+//
+// This file also defines cJU_* for other JP-related constants and functions
+// that some shared JUDY1/JUDYL code finds handy.
+//
+// At least in principle this file should be included AFTER Judy1.h or JudyL.h.
+//
+// WARNING: This file must be kept consistent with the enums in Judy1.h and
+// JudyL.h.
+//
+// TBD: You might think, why not define common cJU_* enums in, say,
+// JudyPrivate.h, and then inherit them into superset enums in Judy1.h and
+// JudyL.h? The problem is that the enum lists for each class (cJ1_* and
+// cJL_*) must be numerically "packed" into the correct order, for two reasons:
+// (1) allow the compiler to generate "tight" switch statements with no wasted
+// slots (although this is not very big), and (2) allow calculations using the
+// enum values, although this is also not an issue if the calculations are only
+// within each cJ*_JPIMMED_*_* class and the members are packed within the
+// class.
+
+#ifdef JUDY1
+
+#define cJU_JRPNULL cJ1_JRPNULL
+#define cJU_JPNULL1 cJ1_JPNULL1
+#define cJU_JPNULL2 cJ1_JPNULL2
+#define cJU_JPNULL3 cJ1_JPNULL3
+#ifdef JU_64BIT
+#define cJU_JPNULL4 cJ1_JPNULL4
+#define cJU_JPNULL5 cJ1_JPNULL5
+#define cJU_JPNULL6 cJ1_JPNULL6
+#define cJU_JPNULL7 cJ1_JPNULL7
+#endif
+#define cJU_JPNULLMAX cJ1_JPNULLMAX
+#define cJU_JPBRANCH_L2 cJ1_JPBRANCH_L2
+#define cJU_JPBRANCH_L3 cJ1_JPBRANCH_L3
+#ifdef JU_64BIT
+#define cJU_JPBRANCH_L4 cJ1_JPBRANCH_L4
+#define cJU_JPBRANCH_L5 cJ1_JPBRANCH_L5
+#define cJU_JPBRANCH_L6 cJ1_JPBRANCH_L6
+#define cJU_JPBRANCH_L7 cJ1_JPBRANCH_L7
+#endif
+#define cJU_JPBRANCH_L cJ1_JPBRANCH_L
+#define j__U_BranchBJPPopToWords j__1_BranchBJPPopToWords
+#define cJU_JPBRANCH_B2 cJ1_JPBRANCH_B2
+#define cJU_JPBRANCH_B3 cJ1_JPBRANCH_B3
+#ifdef JU_64BIT
+#define cJU_JPBRANCH_B4 cJ1_JPBRANCH_B4
+#define cJU_JPBRANCH_B5 cJ1_JPBRANCH_B5
+#define cJU_JPBRANCH_B6 cJ1_JPBRANCH_B6
+#define cJU_JPBRANCH_B7 cJ1_JPBRANCH_B7
+#endif
+#define cJU_JPBRANCH_B cJ1_JPBRANCH_B
+#define cJU_JPBRANCH_U2 cJ1_JPBRANCH_U2
+#define cJU_JPBRANCH_U3 cJ1_JPBRANCH_U3
+#ifdef JU_64BIT
+#define cJU_JPBRANCH_U4 cJ1_JPBRANCH_U4
+#define cJU_JPBRANCH_U5 cJ1_JPBRANCH_U5
+#define cJU_JPBRANCH_U6 cJ1_JPBRANCH_U6
+#define cJU_JPBRANCH_U7 cJ1_JPBRANCH_U7
+#endif
+#define cJU_JPBRANCH_U cJ1_JPBRANCH_U
+#ifndef JU_64BIT
+#define cJU_JPLEAF1 cJ1_JPLEAF1
+#endif
+#define cJU_JPLEAF2 cJ1_JPLEAF2
+#define cJU_JPLEAF3 cJ1_JPLEAF3
+#ifdef JU_64BIT
+#define cJU_JPLEAF4 cJ1_JPLEAF4
+#define cJU_JPLEAF5 cJ1_JPLEAF5
+#define cJU_JPLEAF6 cJ1_JPLEAF6
+#define cJU_JPLEAF7 cJ1_JPLEAF7
+#endif
+#define cJU_JPLEAF_B1 cJ1_JPLEAF_B1
+// cJ1_JPFULLPOPU1
+#define cJU_JPIMMED_1_01 cJ1_JPIMMED_1_01
+#define cJU_JPIMMED_2_01 cJ1_JPIMMED_2_01
+#define cJU_JPIMMED_3_01 cJ1_JPIMMED_3_01
+#ifdef JU_64BIT
+#define cJU_JPIMMED_4_01 cJ1_JPIMMED_4_01
+#define cJU_JPIMMED_5_01 cJ1_JPIMMED_5_01
+#define cJU_JPIMMED_6_01 cJ1_JPIMMED_6_01
+#define cJU_JPIMMED_7_01 cJ1_JPIMMED_7_01
+#endif
+#define cJU_JPIMMED_1_02 cJ1_JPIMMED_1_02
+#define cJU_JPIMMED_1_03 cJ1_JPIMMED_1_03
+#define cJU_JPIMMED_1_04 cJ1_JPIMMED_1_04
+#define cJU_JPIMMED_1_05 cJ1_JPIMMED_1_05
+#define cJU_JPIMMED_1_06 cJ1_JPIMMED_1_06
+#define cJU_JPIMMED_1_07 cJ1_JPIMMED_1_07
+#ifdef JU_64BIT
+// cJ1_JPIMMED_1_08
+// cJ1_JPIMMED_1_09
+// cJ1_JPIMMED_1_10
+// cJ1_JPIMMED_1_11
+// cJ1_JPIMMED_1_12
+// cJ1_JPIMMED_1_13
+// cJ1_JPIMMED_1_14
+// cJ1_JPIMMED_1_15
+#endif
+#define cJU_JPIMMED_2_02 cJ1_JPIMMED_2_02
+#define cJU_JPIMMED_2_03 cJ1_JPIMMED_2_03
+#ifdef JU_64BIT
+// cJ1_JPIMMED_2_04
+// cJ1_JPIMMED_2_05
+// cJ1_JPIMMED_2_06
+// cJ1_JPIMMED_2_07
+#endif
+#define cJU_JPIMMED_3_02 cJ1_JPIMMED_3_02
+#ifdef JU_64BIT
+// cJ1_JPIMMED_3_03
+// cJ1_JPIMMED_3_04
+// cJ1_JPIMMED_3_05
+// cJ1_JPIMMED_4_02
+// cJ1_JPIMMED_4_03
+// cJ1_JPIMMED_5_02
+// cJ1_JPIMMED_5_03
+// cJ1_JPIMMED_6_02
+// cJ1_JPIMMED_7_02
+#endif
+#define cJU_JPIMMED_CAP cJ1_JPIMMED_CAP
+
+#else // JUDYL ****************************************************************
+
+#define cJU_JRPNULL cJL_JRPNULL
+#define cJU_JPNULL1 cJL_JPNULL1
+#define cJU_JPNULL2 cJL_JPNULL2
+#define cJU_JPNULL3 cJL_JPNULL3
+#ifdef JU_64BIT
+#define cJU_JPNULL4 cJL_JPNULL4
+#define cJU_JPNULL5 cJL_JPNULL5
+#define cJU_JPNULL6 cJL_JPNULL6
+#define cJU_JPNULL7 cJL_JPNULL7
+#endif
+#define cJU_JPNULLMAX cJL_JPNULLMAX
+#define cJU_JPBRANCH_L2 cJL_JPBRANCH_L2
+#define cJU_JPBRANCH_L3 cJL_JPBRANCH_L3
+#ifdef JU_64BIT
+#define cJU_JPBRANCH_L4 cJL_JPBRANCH_L4
+#define cJU_JPBRANCH_L5 cJL_JPBRANCH_L5
+#define cJU_JPBRANCH_L6 cJL_JPBRANCH_L6
+#define cJU_JPBRANCH_L7 cJL_JPBRANCH_L7
+#endif
+#define cJU_JPBRANCH_L cJL_JPBRANCH_L
+#define j__U_BranchBJPPopToWords j__L_BranchBJPPopToWords
+#define cJU_JPBRANCH_B2 cJL_JPBRANCH_B2
+#define cJU_JPBRANCH_B3 cJL_JPBRANCH_B3
+#ifdef JU_64BIT
+#define cJU_JPBRANCH_B4 cJL_JPBRANCH_B4
+#define cJU_JPBRANCH_B5 cJL_JPBRANCH_B5
+#define cJU_JPBRANCH_B6 cJL_JPBRANCH_B6
+#define cJU_JPBRANCH_B7 cJL_JPBRANCH_B7
+#endif
+#define cJU_JPBRANCH_B cJL_JPBRANCH_B
+#define cJU_JPBRANCH_U2 cJL_JPBRANCH_U2
+#define cJU_JPBRANCH_U3 cJL_JPBRANCH_U3
+#ifdef JU_64BIT
+#define cJU_JPBRANCH_U4 cJL_JPBRANCH_U4
+#define cJU_JPBRANCH_U5 cJL_JPBRANCH_U5
+#define cJU_JPBRANCH_U6 cJL_JPBRANCH_U6
+#define cJU_JPBRANCH_U7 cJL_JPBRANCH_U7
+#endif
+#define cJU_JPBRANCH_U cJL_JPBRANCH_U
+#define cJU_JPLEAF1 cJL_JPLEAF1
+#define cJU_JPLEAF2 cJL_JPLEAF2
+#define cJU_JPLEAF3 cJL_JPLEAF3
+#ifdef JU_64BIT
+#define cJU_JPLEAF4 cJL_JPLEAF4
+#define cJU_JPLEAF5 cJL_JPLEAF5
+#define cJU_JPLEAF6 cJL_JPLEAF6
+#define cJU_JPLEAF7 cJL_JPLEAF7
+#endif
+#define cJU_JPLEAF_B1 cJL_JPLEAF_B1
+#define cJU_JPIMMED_1_01 cJL_JPIMMED_1_01
+#define cJU_JPIMMED_2_01 cJL_JPIMMED_2_01
+#define cJU_JPIMMED_3_01 cJL_JPIMMED_3_01
+#ifdef JU_64BIT
+#define cJU_JPIMMED_4_01 cJL_JPIMMED_4_01
+#define cJU_JPIMMED_5_01 cJL_JPIMMED_5_01
+#define cJU_JPIMMED_6_01 cJL_JPIMMED_6_01
+#define cJU_JPIMMED_7_01 cJL_JPIMMED_7_01
+#endif
+#define cJU_JPIMMED_1_02 cJL_JPIMMED_1_02
+#define cJU_JPIMMED_1_03 cJL_JPIMMED_1_03
+#ifdef JU_64BIT
+#define cJU_JPIMMED_1_04 cJL_JPIMMED_1_04
+#define cJU_JPIMMED_1_05 cJL_JPIMMED_1_05
+#define cJU_JPIMMED_1_06 cJL_JPIMMED_1_06
+#define cJU_JPIMMED_1_07 cJL_JPIMMED_1_07
+#define cJU_JPIMMED_2_02 cJL_JPIMMED_2_02
+#define cJU_JPIMMED_2_03 cJL_JPIMMED_2_03
+#define cJU_JPIMMED_3_02 cJL_JPIMMED_3_02
+#endif
+#define cJU_JPIMMED_CAP cJL_JPIMMED_CAP
+
+#endif // JUDYL
+
+
+// ****************************************************************************
+// cJU*_ other than JP types:
+
+#ifdef JUDY1
+
+#define cJU_LEAFW_MAXPOP1 cJ1_LEAFW_MAXPOP1
+#ifndef JU_64BIT
+#define cJU_LEAF1_MAXPOP1 cJ1_LEAF1_MAXPOP1
+#endif
+#define cJU_LEAF2_MAXPOP1 cJ1_LEAF2_MAXPOP1
+#define cJU_LEAF3_MAXPOP1 cJ1_LEAF3_MAXPOP1
+#ifdef JU_64BIT
+#define cJU_LEAF4_MAXPOP1 cJ1_LEAF4_MAXPOP1
+#define cJU_LEAF5_MAXPOP1 cJ1_LEAF5_MAXPOP1
+#define cJU_LEAF6_MAXPOP1 cJ1_LEAF6_MAXPOP1
+#define cJU_LEAF7_MAXPOP1 cJ1_LEAF7_MAXPOP1
+#endif
+#define cJU_IMMED1_MAXPOP1 cJ1_IMMED1_MAXPOP1
+#define cJU_IMMED2_MAXPOP1 cJ1_IMMED2_MAXPOP1
+#define cJU_IMMED3_MAXPOP1 cJ1_IMMED3_MAXPOP1
+#ifdef JU_64BIT
+#define cJU_IMMED4_MAXPOP1 cJ1_IMMED4_MAXPOP1
+#define cJU_IMMED5_MAXPOP1 cJ1_IMMED5_MAXPOP1
+#define cJU_IMMED6_MAXPOP1 cJ1_IMMED6_MAXPOP1
+#define cJU_IMMED7_MAXPOP1 cJ1_IMMED7_MAXPOP1
+#endif
+
+#define JU_LEAF1POPTOWORDS(Pop1) J1_LEAF1POPTOWORDS(Pop1)
+#define JU_LEAF2POPTOWORDS(Pop1) J1_LEAF2POPTOWORDS(Pop1)
+#define JU_LEAF3POPTOWORDS(Pop1) J1_LEAF3POPTOWORDS(Pop1)
+#ifdef JU_64BIT
+#define JU_LEAF4POPTOWORDS(Pop1) J1_LEAF4POPTOWORDS(Pop1)
+#define JU_LEAF5POPTOWORDS(Pop1) J1_LEAF5POPTOWORDS(Pop1)
+#define JU_LEAF6POPTOWORDS(Pop1) J1_LEAF6POPTOWORDS(Pop1)
+#define JU_LEAF7POPTOWORDS(Pop1) J1_LEAF7POPTOWORDS(Pop1)
+#endif
+#define JU_LEAFWPOPTOWORDS(Pop1) J1_LEAFWPOPTOWORDS(Pop1)
+
+#ifndef JU_64BIT
+#define JU_LEAF1GROWINPLACE(Pop1) J1_LEAF1GROWINPLACE(Pop1)
+#endif
+#define JU_LEAF2GROWINPLACE(Pop1) J1_LEAF2GROWINPLACE(Pop1)
+#define JU_LEAF3GROWINPLACE(Pop1) J1_LEAF3GROWINPLACE(Pop1)
+#ifdef JU_64BIT
+#define JU_LEAF4GROWINPLACE(Pop1) J1_LEAF4GROWINPLACE(Pop1)
+#define JU_LEAF5GROWINPLACE(Pop1) J1_LEAF5GROWINPLACE(Pop1)
+#define JU_LEAF6GROWINPLACE(Pop1) J1_LEAF6GROWINPLACE(Pop1)
+#define JU_LEAF7GROWINPLACE(Pop1) J1_LEAF7GROWINPLACE(Pop1)
+#endif
+#define JU_LEAFWGROWINPLACE(Pop1) J1_LEAFWGROWINPLACE(Pop1)
+
+#define j__udyCreateBranchL j__udy1CreateBranchL
+#define j__udyCreateBranchB j__udy1CreateBranchB
+#define j__udyCreateBranchU j__udy1CreateBranchU
+#define j__udyCascade1 j__udy1Cascade1
+#define j__udyCascade2 j__udy1Cascade2
+#define j__udyCascade3 j__udy1Cascade3
+#ifdef JU_64BIT
+#define j__udyCascade4 j__udy1Cascade4
+#define j__udyCascade5 j__udy1Cascade5
+#define j__udyCascade6 j__udy1Cascade6
+#define j__udyCascade7 j__udy1Cascade7
+#endif
+#define j__udyCascadeL j__udy1CascadeL
+#define j__udyInsertBranch j__udy1InsertBranch
+
+#define j__udyBranchBToBranchL j__udy1BranchBToBranchL
+#ifndef JU_64BIT
+#define j__udyLeafB1ToLeaf1 j__udy1LeafB1ToLeaf1
+#endif
+#define j__udyLeaf1ToLeaf2 j__udy1Leaf1ToLeaf2
+#define j__udyLeaf2ToLeaf3 j__udy1Leaf2ToLeaf3
+#ifndef JU_64BIT
+#define j__udyLeaf3ToLeafW j__udy1Leaf3ToLeafW
+#else
+#define j__udyLeaf3ToLeaf4 j__udy1Leaf3ToLeaf4
+#define j__udyLeaf4ToLeaf5 j__udy1Leaf4ToLeaf5
+#define j__udyLeaf5ToLeaf6 j__udy1Leaf5ToLeaf6
+#define j__udyLeaf6ToLeaf7 j__udy1Leaf6ToLeaf7
+#define j__udyLeaf7ToLeafW j__udy1Leaf7ToLeafW
+#endif
+
+#define jpm_t j1pm_t
+#define Pjpm_t Pj1pm_t
+
+#define jlb_t j1lb_t
+#define Pjlb_t Pj1lb_t
+
+#define JU_JLB_BITMAP J1_JLB_BITMAP
+
+#define j__udyAllocJPM j__udy1AllocJ1PM
+#define j__udyAllocJBL j__udy1AllocJBL
+#define j__udyAllocJBB j__udy1AllocJBB
+#define j__udyAllocJBBJP j__udy1AllocJBBJP
+#define j__udyAllocJBU j__udy1AllocJBU
+#ifndef JU_64BIT
+#define j__udyAllocJLL1 j__udy1AllocJLL1
+#endif
+#define j__udyAllocJLL2 j__udy1AllocJLL2
+#define j__udyAllocJLL3 j__udy1AllocJLL3
+#ifdef JU_64BIT
+#define j__udyAllocJLL4 j__udy1AllocJLL4
+#define j__udyAllocJLL5 j__udy1AllocJLL5
+#define j__udyAllocJLL6 j__udy1AllocJLL6
+#define j__udyAllocJLL7 j__udy1AllocJLL7
+#endif
+#define j__udyAllocJLW j__udy1AllocJLW
+#define j__udyAllocJLB1 j__udy1AllocJLB1
+#define j__udyFreeJPM j__udy1FreeJ1PM
+#define j__udyFreeJBL j__udy1FreeJBL
+#define j__udyFreeJBB j__udy1FreeJBB
+#define j__udyFreeJBBJP j__udy1FreeJBBJP
+#define j__udyFreeJBU j__udy1FreeJBU
+#ifndef JU_64BIT
+#define j__udyFreeJLL1 j__udy1FreeJLL1
+#endif
+#define j__udyFreeJLL2 j__udy1FreeJLL2
+#define j__udyFreeJLL3 j__udy1FreeJLL3
+#ifdef JU_64BIT
+#define j__udyFreeJLL4 j__udy1FreeJLL4
+#define j__udyFreeJLL5 j__udy1FreeJLL5
+#define j__udyFreeJLL6 j__udy1FreeJLL6
+#define j__udyFreeJLL7 j__udy1FreeJLL7
+#endif
+#define j__udyFreeJLW j__udy1FreeJLW
+#define j__udyFreeJLB1 j__udy1FreeJLB1
+#define j__udyFreeSM j__udy1FreeSM
+
+#define j__uMaxWords j__u1MaxWords
+
+#ifdef DEBUG
+#define JudyCheckPop Judy1CheckPop
+#endif
+
+#else // JUDYL ****************************************************************
+
+#define cJU_LEAFW_MAXPOP1 cJL_LEAFW_MAXPOP1
+#define cJU_LEAF1_MAXPOP1 cJL_LEAF1_MAXPOP1
+#define cJU_LEAF2_MAXPOP1 cJL_LEAF2_MAXPOP1
+#define cJU_LEAF3_MAXPOP1 cJL_LEAF3_MAXPOP1
+#ifdef JU_64BIT
+#define cJU_LEAF4_MAXPOP1 cJL_LEAF4_MAXPOP1
+#define cJU_LEAF5_MAXPOP1 cJL_LEAF5_MAXPOP1
+#define cJU_LEAF6_MAXPOP1 cJL_LEAF6_MAXPOP1
+#define cJU_LEAF7_MAXPOP1 cJL_LEAF7_MAXPOP1
+#endif
+#define cJU_IMMED1_MAXPOP1 cJL_IMMED1_MAXPOP1
+#define cJU_IMMED2_MAXPOP1 cJL_IMMED2_MAXPOP1
+#define cJU_IMMED3_MAXPOP1 cJL_IMMED3_MAXPOP1
+#ifdef JU_64BIT
+#define cJU_IMMED4_MAXPOP1 cJL_IMMED4_MAXPOP1
+#define cJU_IMMED5_MAXPOP1 cJL_IMMED5_MAXPOP1
+#define cJU_IMMED6_MAXPOP1 cJL_IMMED6_MAXPOP1
+#define cJU_IMMED7_MAXPOP1 cJL_IMMED7_MAXPOP1
+#endif
+
+#define JU_LEAF1POPTOWORDS(Pop1) JL_LEAF1POPTOWORDS(Pop1)
+#define JU_LEAF2POPTOWORDS(Pop1) JL_LEAF2POPTOWORDS(Pop1)
+#define JU_LEAF3POPTOWORDS(Pop1) JL_LEAF3POPTOWORDS(Pop1)
+#ifdef JU_64BIT
+#define JU_LEAF4POPTOWORDS(Pop1) JL_LEAF4POPTOWORDS(Pop1)
+#define JU_LEAF5POPTOWORDS(Pop1) JL_LEAF5POPTOWORDS(Pop1)
+#define JU_LEAF6POPTOWORDS(Pop1) JL_LEAF6POPTOWORDS(Pop1)
+#define JU_LEAF7POPTOWORDS(Pop1) JL_LEAF7POPTOWORDS(Pop1)
+#endif
+#define JU_LEAFWPOPTOWORDS(Pop1) JL_LEAFWPOPTOWORDS(Pop1)
+
+#define JU_LEAF1GROWINPLACE(Pop1) JL_LEAF1GROWINPLACE(Pop1)
+#define JU_LEAF2GROWINPLACE(Pop1) JL_LEAF2GROWINPLACE(Pop1)
+#define JU_LEAF3GROWINPLACE(Pop1) JL_LEAF3GROWINPLACE(Pop1)
+#ifdef JU_64BIT
+#define JU_LEAF4GROWINPLACE(Pop1) JL_LEAF4GROWINPLACE(Pop1)
+#define JU_LEAF5GROWINPLACE(Pop1) JL_LEAF5GROWINPLACE(Pop1)
+#define JU_LEAF6GROWINPLACE(Pop1) JL_LEAF6GROWINPLACE(Pop1)
+#define JU_LEAF7GROWINPLACE(Pop1) JL_LEAF7GROWINPLACE(Pop1)
+#endif
+#define JU_LEAFWGROWINPLACE(Pop1) JL_LEAFWGROWINPLACE(Pop1)
+
+#define j__udyCreateBranchL j__udyLCreateBranchL
+#define j__udyCreateBranchB j__udyLCreateBranchB
+#define j__udyCreateBranchU j__udyLCreateBranchU
+#define j__udyCascade1 j__udyLCascade1
+#define j__udyCascade2 j__udyLCascade2
+#define j__udyCascade3 j__udyLCascade3
+#ifdef JU_64BIT
+#define j__udyCascade4 j__udyLCascade4
+#define j__udyCascade5 j__udyLCascade5
+#define j__udyCascade6 j__udyLCascade6
+#define j__udyCascade7 j__udyLCascade7
+#endif
+#define j__udyCascadeL j__udyLCascadeL
+#define j__udyInsertBranch j__udyLInsertBranch
+
+#define j__udyBranchBToBranchL j__udyLBranchBToBranchL
+#define j__udyLeafB1ToLeaf1 j__udyLLeafB1ToLeaf1
+#define j__udyLeaf1ToLeaf2 j__udyLLeaf1ToLeaf2
+#define j__udyLeaf2ToLeaf3 j__udyLLeaf2ToLeaf3
+#ifndef JU_64BIT
+#define j__udyLeaf3ToLeafW j__udyLLeaf3ToLeafW
+#else
+#define j__udyLeaf3ToLeaf4 j__udyLLeaf3ToLeaf4
+#define j__udyLeaf4ToLeaf5 j__udyLLeaf4ToLeaf5
+#define j__udyLeaf5ToLeaf6 j__udyLLeaf5ToLeaf6
+#define j__udyLeaf6ToLeaf7 j__udyLLeaf6ToLeaf7
+#define j__udyLeaf7ToLeafW j__udyLLeaf7ToLeafW
+#endif
+
+#define jpm_t jLpm_t
+#define Pjpm_t PjLpm_t
+
+#define jlb_t jLlb_t
+#define Pjlb_t PjLlb_t
+
+#define JU_JLB_BITMAP JL_JLB_BITMAP
+
+#define j__udyAllocJPM j__udyLAllocJLPM
+#define j__udyAllocJBL j__udyLAllocJBL
+#define j__udyAllocJBB j__udyLAllocJBB
+#define j__udyAllocJBBJP j__udyLAllocJBBJP
+#define j__udyAllocJBU j__udyLAllocJBU
+#define j__udyAllocJLL1 j__udyLAllocJLL1
+#define j__udyAllocJLL2 j__udyLAllocJLL2
+#define j__udyAllocJLL3 j__udyLAllocJLL3
+#ifdef JU_64BIT
+#define j__udyAllocJLL4 j__udyLAllocJLL4
+#define j__udyAllocJLL5 j__udyLAllocJLL5
+#define j__udyAllocJLL6 j__udyLAllocJLL6
+#define j__udyAllocJLL7 j__udyLAllocJLL7
+#endif
+#define j__udyAllocJLW j__udyLAllocJLW
+#define j__udyAllocJLB1 j__udyLAllocJLB1
+// j__udyLAllocJV
+#define j__udyFreeJPM j__udyLFreeJLPM
+#define j__udyFreeJBL j__udyLFreeJBL
+#define j__udyFreeJBB j__udyLFreeJBB
+#define j__udyFreeJBBJP j__udyLFreeJBBJP
+#define j__udyFreeJBU j__udyLFreeJBU
+#define j__udyFreeJLL1 j__udyLFreeJLL1
+#define j__udyFreeJLL2 j__udyLFreeJLL2
+#define j__udyFreeJLL3 j__udyLFreeJLL3
+#ifdef JU_64BIT
+#define j__udyFreeJLL4 j__udyLFreeJLL4
+#define j__udyFreeJLL5 j__udyLFreeJLL5
+#define j__udyFreeJLL6 j__udyLFreeJLL6
+#define j__udyFreeJLL7 j__udyLFreeJLL7
+#endif
+#define j__udyFreeJLW j__udyLFreeJLW
+#define j__udyFreeJLB1 j__udyLFreeJLB1
+#define j__udyFreeSM j__udyLFreeSM
+// j__udyLFreeJV
+
+#define j__uMaxWords j__uLMaxWords
+
+#ifdef DEBUG
+#define JudyCheckPop JudyLCheckPop
+#endif
+
+#endif // JUDYL
+
+#endif // _JUDYPRIVATE1L_INCLUDED
diff --git a/libnetdata/libjudy/src/JudyCommon/JudyPrivateBranch.h b/libnetdata/libjudy/src/JudyCommon/JudyPrivateBranch.h
new file mode 100644
index 0000000..10295ba
--- /dev/null
+++ b/libnetdata/libjudy/src/JudyCommon/JudyPrivateBranch.h
@@ -0,0 +1,788 @@
+#ifndef _JUDY_PRIVATE_BRANCH_INCLUDED
+#define _JUDY_PRIVATE_BRANCH_INCLUDED
+// _________________
+//
+// 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: 1.2 $ $Source: /home/doug/judy-1.0.5_min/test/../src/JudyCommon/RCS/JudyPrivateBranch.h,v $
+//
+// Header file for all Judy sources, for global but private (non-exported)
+// declarations specific to branch support.
+//
+// See also the "Judy Shop Manual" (try judy/doc/int/JudyShopManual.*).
+
+
+// ****************************************************************************
+// JUDY POINTER (JP) SUPPORT
+// ****************************************************************************
+//
+// This "rich pointer" object is pivotal to Judy execution.
+//
+// JP CONTAINING OTHER THAN IMMEDIATE INDEXES:
+//
+// If the JP points to a linear or bitmap leaf, jp_DcdPopO contains the
+// Population-1 in LSbs and Decode (Dcd) bytes in the MSBs. (In practice the
+// Decode bits are masked off while accessing the Pop0 bits.)
+//
+// The Decode Size, the number of Dcd bytes available, is encoded in jpo_Type.
+// It can also be thought of as the number of states "skipped" in the SM, where
+// each state decodes 8 bits = 1 byte.
+//
+// TBD: Dont need two structures, except possibly to force jp_Type to highest
+// address!
+//
+// Note: The jpo_u union is not required by HP-UX or Linux but Win32 because
+// the cl.exe compiler otherwise refuses to pack a bitfield (DcdPopO) with
+// anything else, even with the -Zp option. This is pretty ugly, but
+// fortunately portable, and its all hide-able by macros (see below).
+
+typedef struct J_UDY_POINTER_OTHERS // JPO.
+ {
+ Word_t j_po_Addr; // first word: Pjp_t, Word_t, etc.
+ union {
+ Word_t j_po_Addr1;
+ uint8_t j_po_DcdP0[sizeof(Word_t) - 1];
+ uint8_t j_po_Bytes[sizeof(Word_t)]; // last byte = jp_Type.
+ } jpo_u;
+ } jpo_t;
+
+
+// JP CONTAINING IMMEDIATE INDEXES:
+//
+// j_pi_1Index[] plus j_pi_LIndex[] together hold as many N-byte (1..3-byte
+// [1..7-byte]) Indexes as will fit in sizeof(jpi_t) less 1 byte for j_pi_Type
+// (that is, 7..1 [15..1] Indexes).
+//
+// For Judy1, j_pi_1Index[] is used and j_pi_LIndex[] is not used.
+// For JudyL, j_pi_LIndex[] is used and j_pi_1Index[] is not used.
+//
+// Note: Actually when Pop1 = 1, jpi_t is not used, and the least bytes of the
+// single Index are stored in j_po_DcdPopO, for both Judy1 and JudyL, so for
+// JudyL the j_po_Addr field can hold the target value.
+//
+// TBD: Revise this structure to not overload j_po_DcdPopO this way? The
+// current arrangement works, its just confusing.
+
+typedef struct _JUDY_POINTER_IMMEDL
+ {
+ Word_t j_pL_Addr;
+ uint8_t j_pL_LIndex[sizeof(Word_t) - 1]; // see above.
+ uint8_t j_pL_Type;
+ } jpL_t;
+
+typedef struct _JUDY_POINTER_IMMED1
+ {
+ uint8_t j_p1_1Index[(2 * sizeof(Word_t)) - 1];
+ uint8_t j_p1_Type;
+ } jp1_t;
+
+// UNION OF JP TYPES:
+//
+// A branch is an array of cJU_BRANCHUNUMJPS (256) of this object, or an
+// alternate data type such as: A linear branch which is a list of 2..7 JPs,
+// or a bitmap branch which contains 8 lists of 0..32 JPs. JPs reside only in
+// branches of a Judy SM.
+
+typedef union J_UDY_POINTER // JP.
+ {
+ jpo_t j_po; // other than immediate indexes.
+ jpL_t j_pL; // immediate indexes.
+ jp1_t j_p1; // immediate indexes.
+ } jp_t, *Pjp_t;
+
+// For coding convenience:
+//
+// Note, jp_Type has the same bits in jpo_t jpL_t and jp1_t.
+
+#define jp_1Index j_p1.j_p1_1Index // for storing Indexes in first word.
+#define jp_LIndex j_pL.j_pL_LIndex // for storing Indexes in second word.
+#define jp_Addr j_po.j_po_Addr
+#define jp_Addr1 j_po.jpo_u.j_po_Addr1
+//#define jp_DcdPop0 j_po.jpo_u.j_po_DcdPop0
+#define jp_Addr1 j_po.jpo_u.j_po_Addr1
+//#define jp_Type j_po.jpo_u.j_po_Bytes[sizeof(Word_t) - 1]
+#define jp_Type j_p1.j_p1_Type
+#define jp_DcdP0 j_po.jpo_u.j_po_DcdP0
+
+
+// ****************************************************************************
+// JUDY POINTER (JP) -- RELATED MACROS AND CONSTANTS
+// ****************************************************************************
+
+// EXTRACT VALUES FROM JP:
+//
+// Masks for the bytes in the Dcd and Pop0 parts of jp_DcdPopO:
+//
+// cJU_DCDMASK() consists of a mask that excludes the (LSb) Pop0 bytes and
+// also, just to be safe, the top byte of the word, since jp_DcdPopO is 1 byte
+// less than a full word.
+//
+// Note: These are constant macros (cJU) because cPopBytes should be a
+// constant. Also note cPopBytes == state in the SM.
+
+#define cJU_POP0MASK(cPopBytes) JU_LEASTBYTESMASK(cPopBytes)
+
+#define cJU_DCDMASK(cPopBytes) \
+ ((cJU_ALLONES >> cJU_BITSPERBYTE) & (~cJU_POP0MASK(cPopBytes)))
+
+// Mask off the high byte from INDEX to it can be compared to DcdPopO:
+
+#define JU_TRIMTODCDSIZE(INDEX) ((cJU_ALLONES >> cJU_BITSPERBYTE) & (INDEX))
+
+// Get from jp_DcdPopO the Pop0 for various branch JP Types:
+//
+// Note: There are no simple macros for cJU_BRANCH* Types because their
+// populations must be added up and dont reside in an already-calculated
+// place.
+
+#define JU_JPBRANCH_POP0(PJP,cPopBytes) \
+ (JU_JPDCDPOP0(PJP) & cJU_POP0MASK(cPopBytes))
+
+// METHOD FOR DETERMINING IF OBJECTS HAVE ROOM TO GROW:
+//
+// J__U_GROWCK() is a generic method to determine if an object can grow in
+// place, based on whether the next population size (one more) would use the
+// same space.
+
+#define J__U_GROWCK(POP1,MAXPOP1,POPTOWORDS) \
+ (((POP1) != (MAXPOP1)) && (POPTOWORDS[POP1] == POPTOWORDS[(POP1) + 1]))
+
+#define JU_BRANCHBJPGROWINPLACE(NumJPs) \
+ J__U_GROWCK(NumJPs, cJU_BITSPERSUBEXPB, j__U_BranchBJPPopToWords)
+
+
+// DETERMINE IF AN INDEX IS (NOT) IN A JPS EXPANSE:
+
+#define JU_DCDNOTMATCHINDEX(INDEX,PJP,POP0BYTES) \
+ (((INDEX) ^ JU_JPDCDPOP0(PJP)) & cJU_DCDMASK(POP0BYTES))
+
+
+// NUMBER OF JPs IN AN UNCOMPRESSED BRANCH:
+//
+// An uncompressed branch is simply an array of 256 Judy Pointers (JPs). It is
+// a minimum cacheline fill object. Define it here before its first needed.
+
+#define cJU_BRANCHUNUMJPS cJU_SUBEXPPERSTATE
+
+
+// ****************************************************************************
+// JUDY BRANCH LINEAR (JBL) SUPPORT
+// ****************************************************************************
+//
+// A linear branch is a way of compressing empty expanses (null JPs) out of an
+// uncompressed 256-way branch, when the number of populated expanses is so
+// small that even a bitmap branch is excessive.
+//
+// The maximum number of JPs in a Judy linear branch:
+//
+// Note: This number results in a 1-cacheline sized structure. Previous
+// versions had a larger struct so a linear branch didnt become a bitmap
+// branch until the memory consumed was even, but for speed, its better to
+// switch "sooner" and keep a linear branch fast.
+
+#define cJU_BRANCHLMAXJPS 7
+
+
+// LINEAR BRANCH STRUCT:
+//
+// 1-byte count, followed by array of byte-sized expanses, followed by JPs.
+
+typedef struct J__UDY_BRANCH_LINEAR
+ {
+ uint8_t jbl_NumJPs; // num of JPs (Pjp_t), 1..N.
+ uint8_t jbl_Expanse[cJU_BRANCHLMAXJPS]; // 1..7 MSbs of pop exps.
+ jp_t jbl_jp [cJU_BRANCHLMAXJPS]; // JPs for populated exps.
+ } jbl_t, * Pjbl_t;
+
+
+// ****************************************************************************
+// JUDY BRANCH BITMAP (JBB) SUPPORT
+// ****************************************************************************
+//
+// A bitmap branch is a way of compressing empty expanses (null JPs) out of
+// uncompressed 256-way branch. This costs 1 additional cache line fill, but
+// can save a lot of memory when it matters most, near the leaves, and
+// typically there will be only one at most in the path to any Index (leaf).
+//
+// The bitmap indicates which of the cJU_BRANCHUNUMJPS (256) JPs in the branch
+// are NOT null, that is, their expanses are populated. The jbb_t also
+// contains N pointers to "mini" Judy branches ("subexpanses") of up to M JPs
+// each (see BITMAP_BRANCHMxN, for example, BITMAP_BRANCH32x8), where M x N =
+// cJU_BRANCHUNUMJPS. These are dynamically allocated and never contain
+// cJ*_JPNULL* jp_Types. An empty subexpanse is represented by no bit sets in
+// the corresponding subexpanse bitmap, in which case the corresponding
+// jbbs_Pjp pointers value is unused.
+//
+// Note that the number of valid JPs in each 1-of-N subexpanses is determined
+// by POPULATION rather than by EXPANSE -- the desired outcome to save memory
+// when near the leaves. Note that the memory required for 185 JPs is about as
+// much as an uncompressed 256-way branch, therefore 184 is set as the maximum.
+// However, it is expected that a conversion to an uncompressed 256-way branch
+// will normally take place before this limit is reached for other reasons,
+// such as improving performance when the "wasted" memory is well amortized by
+// the population under the branch, preserving an acceptable overall
+// bytes/Index in the Judy array.
+//
+// The number of pointers to arrays of JPs in the Judy bitmap branch:
+//
+// Note: The numbers below are the same in both 32 and 64 bit systems.
+
+#define cJU_BRANCHBMAXJPS 184 // maximum JPs for bitmap branches.
+
+// Convenience wrappers for referencing BranchB bitmaps or JP subarray
+// pointers:
+//
+// Note: JU_JBB_PJP produces a "raw" memory address that must pass through
+// P_JP before use, except when freeing memory:
+
+#define JU_JBB_BITMAP(Pjbb, SubExp) ((Pjbb)->jbb_jbbs[SubExp].jbbs_Bitmap)
+#define JU_JBB_PJP( Pjbb, SubExp) ((Pjbb)->jbb_jbbs[SubExp].jbbs_Pjp)
+
+#define JU_SUBEXPB(Digit) (((Digit) / cJU_BITSPERSUBEXPB) & (cJU_NUMSUBEXPB-1))
+
+#define JU_BITMAPTESTB(Pjbb, Index) \
+ (JU_JBB_BITMAP(Pjbb, JU_SUBEXPB(Index)) & JU_BITPOSMASKB(Index))
+
+#define JU_BITMAPSETB(Pjbb, Index) \
+ (JU_JBB_BITMAP(Pjbb, JU_SUBEXPB(Index)) |= JU_BITPOSMASKB(Index))
+
+// Note: JU_BITMAPCLEARB is not defined because the code does it a faster way.
+
+typedef struct J__UDY_BRANCH_BITMAP_SUBEXPANSE
+ {
+ BITMAPB_t jbbs_Bitmap;
+ Pjp_t jbbs_Pjp;
+
+ } jbbs_t;
+
+typedef struct J__UDY_BRANCH_BITMAP
+ {
+ jbbs_t jbb_jbbs [cJU_NUMSUBEXPB];
+#ifdef SUBEXPCOUNTS
+ Word_t jbb_subPop1[cJU_NUMSUBEXPB];
+#endif
+ } jbb_t, * Pjbb_t;
+
+#define JU_BRANCHJP_NUMJPSTOWORDS(NumJPs) (j__U_BranchBJPPopToWords[NumJPs])
+
+#ifdef SUBEXPCOUNTS
+#define cJU_NUMSUBEXPU 16 // number of subexpanse counts.
+#endif
+
+
+// ****************************************************************************
+// JUDY BRANCH UNCOMPRESSED (JBU) SUPPORT
+// ****************************************************************************
+
+// Convenience wrapper for referencing BranchU JPs:
+//
+// Note: This produces a non-"raw" address already passed through P_JBU().
+
+#define JU_JBU_PJP(Pjp,Index,Level) \
+ (&((P_JBU((Pjp)->jp_Addr))->jbu_jp[JU_DIGITATSTATE(Index, Level)]))
+#define JU_JBU_PJP0(Pjp) \
+ (&((P_JBU((Pjp)->jp_Addr))->jbu_jp[0]))
+
+typedef struct J__UDY_BRANCH_UNCOMPRESSED
+ {
+ jp_t jbu_jp [cJU_BRANCHUNUMJPS]; // JPs for populated exp.
+#ifdef SUBEXPCOUNTS
+ Word_t jbu_subPop1[cJU_NUMSUBEXPU];
+#endif
+ } jbu_t, * Pjbu_t;
+
+
+// ****************************************************************************
+// OTHER SUPPORT FOR JUDY STATE MACHINES (SMs)
+// ****************************************************************************
+
+// OBJECT SIZES IN WORDS:
+//
+// Word_ts per various JudyL structures that have constant sizes.
+// cJU_WORDSPERJP should always be 2; this is fundamental to the Judy
+// structures.
+
+#define cJU_WORDSPERJP (sizeof(jp_t) / cJU_BYTESPERWORD)
+#define cJU_WORDSPERCL (cJU_BYTESPERCL / cJU_BYTESPERWORD)
+
+
+// OPPORTUNISTIC UNCOMPRESSION:
+//
+// Define populations at which a BranchL or BranchB must convert to BranchU.
+// Earlier conversion is possible with good memory efficiency -- see below.
+
+#ifndef NO_BRANCHU
+
+// Max population below BranchL, then convert to BranchU:
+
+#define JU_BRANCHL_MAX_POP 1000
+
+// Minimum global population increment before next conversion of a BranchB to a
+// BranchU:
+//
+// This is was done to allow malloc() to coalesce memory before the next big
+// (~512 words) allocation.
+
+#define JU_BTOU_POP_INCREMENT 300
+
+// Min/max population below BranchB, then convert to BranchU:
+
+#define JU_BRANCHB_MIN_POP 135
+#define JU_BRANCHB_MAX_POP 750
+
+#else // NO_BRANCHU
+
+// These are set up to have conservative conversion schedules to BranchU:
+
+#define JU_BRANCHL_MAX_POP (-1UL)
+#define JU_BTOU_POP_INCREMENT 300
+#define JU_BRANCHB_MIN_POP 1000
+#define JU_BRANCHB_MAX_POP (-1UL)
+
+#endif // NO_BRANCHU
+
+
+// MISCELLANEOUS MACROS:
+
+// Get N most significant bits from the shifted Index word:
+//
+// As Index words are decoded, they are shifted left so only relevant,
+// undecoded Index bits remain.
+
+#define JU_BITSFROMSFTIDX(SFTIDX, N) ((SFTIDX) >> (cJU_BITSPERWORD - (N)))
+
+// TBD: I have my doubts about the necessity of these macros (dlb):
+
+// Produce 1-digit mask at specified state:
+
+#define cJU_MASKATSTATE(State) (0xffL << (((State) - 1) * cJU_BITSPERBYTE))
+
+// Get byte (digit) from Index at the specified state, right justified:
+//
+// Note: State must be 1..cJU_ROOTSTATE, and Digits must be 1..(cJU_ROOTSTATE
+// - 1), but theres no way to assert these within an expression.
+
+#define JU_DIGITATSTATE(Index,cState) \
+ ((uint8_t)((Index) >> (((cState) - 1) * cJU_BITSPERBYTE)))
+
+// Similarly, place byte (digit) at correct position for the specified state:
+//
+// Note: Cast digit to a Word_t first so there are no complaints or problems
+// about shifting it more than 32 bits on a 64-bit system, say, when it is a
+// uint8_t from jbl_Expanse[]. (Believe it or not, the C standard says to
+// promote an unsigned char to a signed int; -Ac does not do this, but -Ae
+// does.)
+//
+// Also, to make lint happy, cast the whole result again because apparently
+// shifting a Word_t does not result in a Word_t!
+
+#define JU_DIGITTOSTATE(Digit,cState) \
+ ((Word_t) (((Word_t) (Digit)) << (((cState) - 1) * cJU_BITSPERBYTE)))
+
+#endif // ! _JUDY_PRIVATE_BRANCH_INCLUDED
+
+
+#ifdef TEST_INSDEL
+
+// ****************************************************************************
+// TEST CODE FOR INSERT/DELETE MACROS
+// ****************************************************************************
+//
+// To use this, compile a temporary *.c file containing:
+//
+// #define DEBUG
+// #define JUDY_ASSERT
+// #define TEST_INSDEL
+// #include "JudyPrivate.h"
+// #include "JudyPrivateBranch.h"
+//
+// Use a command like this: cc -Ae +DD64 -I. -I JudyCommon -o t t.c
+// For best results, include +DD64 on a 64-bit system.
+//
+// This test code exercises some tricky macros, but the output must be studied
+// manually to verify it. Assume that for even-index testing, whole words
+// (Word_t) suffices.
+
+#include <stdio.h>
+
+#define INDEXES 3 // in each array.
+
+
+// ****************************************************************************
+// I N I T
+//
+// Set up variables for next test. See usage.
+
+FUNCTION void Init (
+ int base,
+ PWord_t PeIndex,
+ PWord_t PoIndex,
+ PWord_t Peleaf, // always whole words.
+#ifndef JU_64BIT
+ uint8_t * Poleaf3)
+#else
+ uint8_t * Poleaf3,
+ uint8_t * Poleaf5,
+ uint8_t * Poleaf6,
+ uint8_t * Poleaf7)
+#endif
+{
+ int offset;
+
+ *PeIndex = 99;
+
+ for (offset = 0; offset <= INDEXES; ++offset)
+ Peleaf[offset] = base + offset;
+
+ for (offset = 0; offset < (INDEXES + 1) * 3; ++offset)
+ Poleaf3[offset] = base + offset;
+
+#ifndef JU_64BIT
+ *PoIndex = (91 << 24) | (92 << 16) | (93 << 8) | 94;
+#else
+
+ *PoIndex = (91L << 56) | (92L << 48) | (93L << 40) | (94L << 32)
+ | (95L << 24) | (96L << 16) | (97L << 8) | 98L;
+
+ for (offset = 0; offset < (INDEXES + 1) * 5; ++offset)
+ Poleaf5[offset] = base + offset;
+
+ for (offset = 0; offset < (INDEXES + 1) * 6; ++offset)
+ Poleaf6[offset] = base + offset;
+
+ for (offset = 0; offset < (INDEXES + 1) * 7; ++offset)
+ Poleaf7[offset] = base + offset;
+#endif
+
+} // Init()
+
+
+// ****************************************************************************
+// P R I N T L E A F
+//
+// Print the byte values in a leaf.
+
+FUNCTION void PrintLeaf (
+ char * Label, // for output.
+ int IOffset, // insertion offset in array.
+ int Indsize, // index size in bytes.
+ uint8_t * PLeaf) // array of Index bytes.
+{
+ int offset; // in PLeaf.
+ int byte; // in one word.
+
+ (void) printf("%s %u: ", Label, IOffset);
+
+ for (offset = 0; offset <= INDEXES; ++offset)
+ {
+ for (byte = 0; byte < Indsize; ++byte)
+ (void) printf("%2d", PLeaf[(offset * Indsize) + byte]);
+
+ (void) printf(" ");
+ }
+
+ (void) printf("\n");
+
+} // PrintLeaf()
+
+
+// ****************************************************************************
+// M A I N
+//
+// Test program.
+
+FUNCTION main()
+{
+ Word_t eIndex; // even, to insert.
+ Word_t oIndex; // odd, to insert.
+ Word_t eleaf [ INDEXES + 1]; // even leaf, index size 4.
+ uint8_t oleaf3[(INDEXES + 1) * 3]; // odd leaf, index size 3.
+#ifdef JU_64BIT
+ uint8_t oleaf5[(INDEXES + 1) * 5]; // odd leaf, index size 5.
+ uint8_t oleaf6[(INDEXES + 1) * 6]; // odd leaf, index size 6.
+ uint8_t oleaf7[(INDEXES + 1) * 7]; // odd leaf, index size 7.
+#endif
+ Word_t eleaf_2 [ INDEXES + 1]; // same, but second arrays:
+ uint8_t oleaf3_2[(INDEXES + 1) * 3];
+#ifdef JU_64BIT
+ uint8_t oleaf5_2[(INDEXES + 1) * 5];
+ uint8_t oleaf6_2[(INDEXES + 1) * 6];
+ uint8_t oleaf7_2[(INDEXES + 1) * 7];
+#endif
+ int ioffset; // index insertion offset.
+
+#ifndef JU_64BIT
+#define INIT Init( 0, & eIndex, & oIndex, eleaf, oleaf3)
+#define INIT2 INIT; Init(50, & eIndex, & oIndex, eleaf_2, oleaf3_2)
+#else
+#define INIT Init( 0, & eIndex, & oIndex, eleaf, oleaf3, \
+ oleaf5, oleaf6, oleaf7)
+#define INIT2 INIT; Init(50, & eIndex, & oIndex, eleaf_2, oleaf3_2, \
+ oleaf5_2, oleaf6_2, oleaf7_2)
+#endif
+
+#define WSIZE sizeof (Word_t) // shorthand.
+
+#ifdef PRINTALL // to turn on "noisy" printouts.
+#define PRINTLEAF(Label,IOffset,Indsize,PLeaf) \
+ PrintLeaf(Label,IOffset,Indsize,PLeaf)
+#else
+#define PRINTLEAF(Label,IOffset,Indsize,PLeaf) \
+ if (ioffset == 0) \
+ PrintLeaf(Label,IOffset,Indsize,PLeaf)
+#endif
+
+ (void) printf(
+"In each case, tests operate on an initial array of %d indexes. Even-index\n"
+"tests set index values to 0,1,2...; odd-index tests set byte values to\n"
+"0,1,2... Inserted indexes have a value of 99 or else byte values 91,92,...\n",
+ INDEXES);
+
+ (void) puts("\nJU_INSERTINPLACE():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, WSIZE, (uint8_t *) eleaf);
+ JU_INSERTINPLACE(eleaf, INDEXES, ioffset, eIndex);
+ PrintLeaf("After ", ioffset, WSIZE, (uint8_t *) eleaf);
+ }
+
+ (void) puts("\nJU_INSERTINPLACE3():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 3, oleaf3);
+ JU_INSERTINPLACE3(oleaf3, INDEXES, ioffset, oIndex);
+ PrintLeaf("After ", ioffset, 3, oleaf3);
+ }
+
+#ifdef JU_64BIT
+ (void) puts("\nJU_INSERTINPLACE5():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 5, oleaf5);
+ JU_INSERTINPLACE5(oleaf5, INDEXES, ioffset, oIndex);
+ PrintLeaf("After ", ioffset, 5, oleaf5);
+ }
+
+ (void) puts("\nJU_INSERTINPLACE6():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 6, oleaf6);
+ JU_INSERTINPLACE6(oleaf6, INDEXES, ioffset, oIndex);
+ PrintLeaf("After ", ioffset, 6, oleaf6);
+ }
+
+ (void) puts("\nJU_INSERTINPLACE7():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 7, oleaf7);
+ JU_INSERTINPLACE7(oleaf7, INDEXES, ioffset, oIndex);
+ PrintLeaf("After ", ioffset, 7, oleaf7);
+ }
+#endif // JU_64BIT
+
+ (void) puts("\nJU_DELETEINPLACE():");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, WSIZE, (uint8_t *) eleaf);
+ JU_DELETEINPLACE(eleaf, INDEXES, ioffset);
+ PrintLeaf("After ", ioffset, WSIZE, (uint8_t *) eleaf);
+ }
+
+ (void) puts("\nJU_DELETEINPLACE_ODD(3):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 3, oleaf3);
+ JU_DELETEINPLACE_ODD(oleaf3, INDEXES, ioffset, 3);
+ PrintLeaf("After ", ioffset, 3, oleaf3);
+ }
+
+#ifdef JU_64BIT
+ (void) puts("\nJU_DELETEINPLACE_ODD(5):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 5, oleaf5);
+ JU_DELETEINPLACE_ODD(oleaf5, INDEXES, ioffset, 5);
+ PrintLeaf("After ", ioffset, 5, oleaf5);
+ }
+
+ (void) puts("\nJU_DELETEINPLACE_ODD(6):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 6, oleaf6);
+ JU_DELETEINPLACE_ODD(oleaf6, INDEXES, ioffset, 6);
+ PrintLeaf("After ", ioffset, 6, oleaf6);
+ }
+
+ (void) puts("\nJU_DELETEINPLACE_ODD(7):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT;
+ PRINTLEAF("Before", ioffset, 7, oleaf7);
+ JU_DELETEINPLACE_ODD(oleaf7, INDEXES, ioffset, 7);
+ PrintLeaf("After ", ioffset, 7, oleaf7);
+ }
+#endif // JU_64BIT
+
+ (void) puts("\nJU_INSERTCOPY():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, WSIZE, (uint8_t *) eleaf);
+ PRINTLEAF("Before, dest", ioffset, WSIZE, (uint8_t *) eleaf_2);
+ JU_INSERTCOPY(eleaf_2, eleaf, INDEXES, ioffset, eIndex);
+ PRINTLEAF("After, src ", ioffset, WSIZE, (uint8_t *) eleaf);
+ PrintLeaf("After, dest", ioffset, WSIZE, (uint8_t *) eleaf_2);
+ }
+
+ (void) puts("\nJU_INSERTCOPY3():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 3, oleaf3);
+ PRINTLEAF("Before, dest", ioffset, 3, oleaf3_2);
+ JU_INSERTCOPY3(oleaf3_2, oleaf3, INDEXES, ioffset, oIndex);
+ PRINTLEAF("After, src ", ioffset, 3, oleaf3);
+ PrintLeaf("After, dest", ioffset, 3, oleaf3_2);
+ }
+
+#ifdef JU_64BIT
+ (void) puts("\nJU_INSERTCOPY5():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 5, oleaf5);
+ PRINTLEAF("Before, dest", ioffset, 5, oleaf5_2);
+ JU_INSERTCOPY5(oleaf5_2, oleaf5, INDEXES, ioffset, oIndex);
+ PRINTLEAF("After, src ", ioffset, 5, oleaf5);
+ PrintLeaf("After, dest", ioffset, 5, oleaf5_2);
+ }
+
+ (void) puts("\nJU_INSERTCOPY6():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 6, oleaf6);
+ PRINTLEAF("Before, dest", ioffset, 6, oleaf6_2);
+ JU_INSERTCOPY6(oleaf6_2, oleaf6, INDEXES, ioffset, oIndex);
+ PRINTLEAF("After, src ", ioffset, 6, oleaf6);
+ PrintLeaf("After, dest", ioffset, 6, oleaf6_2);
+ }
+
+ (void) puts("\nJU_INSERTCOPY7():");
+
+ for (ioffset = 0; ioffset <= INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 7, oleaf7);
+ PRINTLEAF("Before, dest", ioffset, 7, oleaf7_2);
+ JU_INSERTCOPY7(oleaf7_2, oleaf7, INDEXES, ioffset, oIndex);
+ PRINTLEAF("After, src ", ioffset, 7, oleaf7);
+ PrintLeaf("After, dest", ioffset, 7, oleaf7_2);
+ }
+#endif // JU_64BIT
+
+ (void) puts("\nJU_DELETECOPY():");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, WSIZE, (uint8_t *) eleaf);
+ PRINTLEAF("Before, dest", ioffset, WSIZE, (uint8_t *) eleaf_2);
+ JU_DELETECOPY(eleaf_2, eleaf, INDEXES, ioffset, ignore);
+ PRINTLEAF("After, src ", ioffset, WSIZE, (uint8_t *) eleaf);
+ PrintLeaf("After, dest", ioffset, WSIZE, (uint8_t *) eleaf_2);
+ }
+
+ (void) puts("\nJU_DELETECOPY_ODD(3):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 3, oleaf3);
+ PRINTLEAF("Before, dest", ioffset, 3, oleaf3_2);
+ JU_DELETECOPY_ODD(oleaf3_2, oleaf3, INDEXES, ioffset, 3);
+ PRINTLEAF("After, src ", ioffset, 3, oleaf3);
+ PrintLeaf("After, dest", ioffset, 3, oleaf3_2);
+ }
+
+#ifdef JU_64BIT
+ (void) puts("\nJU_DELETECOPY_ODD(5):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 5, oleaf5);
+ PRINTLEAF("Before, dest", ioffset, 5, oleaf5_2);
+ JU_DELETECOPY_ODD(oleaf5_2, oleaf5, INDEXES, ioffset, 5);
+ PRINTLEAF("After, src ", ioffset, 5, oleaf5);
+ PrintLeaf("After, dest", ioffset, 5, oleaf5_2);
+ }
+
+ (void) puts("\nJU_DELETECOPY_ODD(6):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 6, oleaf6);
+ PRINTLEAF("Before, dest", ioffset, 6, oleaf6_2);
+ JU_DELETECOPY_ODD(oleaf6_2, oleaf6, INDEXES, ioffset, 6);
+ PRINTLEAF("After, src ", ioffset, 6, oleaf6);
+ PrintLeaf("After, dest", ioffset, 6, oleaf6_2);
+ }
+
+ (void) puts("\nJU_DELETECOPY_ODD(7):");
+
+ for (ioffset = 0; ioffset < INDEXES; ++ioffset)
+ {
+ INIT2;
+ PRINTLEAF("Before, src ", ioffset, 7, oleaf7);
+ PRINTLEAF("Before, dest", ioffset, 7, oleaf7_2);
+ JU_DELETECOPY_ODD(oleaf7_2, oleaf7, INDEXES, ioffset, 7);
+ PRINTLEAF("After, src ", ioffset, 7, oleaf7);
+ PrintLeaf("After, dest", ioffset, 7, oleaf7_2);
+ }
+#endif // JU_64BIT
+
+ return(0);
+
+} // main()
+
+#endif // TEST_INSDEL