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

// Copyright (C) 2000 - 2002 Hewlett-Packard Company
//
// This program is free software; you can redistribute it and/or modify it
// under the term of the GNU Lesser General Public License as published by the
// Free Software Foundation; either version 2 of the License, or (at your
// option) any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
// for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this program; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
// _________________

// @(#) $Revision: 4.25 $ $Source: /judy/src/JudyCommon/JudyDecascade.c $
//
// "Decascade" support functions for JudyDel.c:  These functions convert
// smaller-index-size leaves to larger-index-size leaves, and also, bitmap
// leaves (LeafB1s) to Leaf1s, and some types of branches to smaller branches
// at the same index size.  Some "decascading" occurs explicitly in JudyDel.c,
// but rare or large subroutines appear as functions here, and the overhead to
// call them is negligible.
//
// Compile with one of -DJUDY1 or -DJUDYL.  Note:  Function names are converted
// to Judy1 or JudyL specific values by external #defines.

#if (! (defined(JUDY1) || defined(JUDYL)))
#error:  One of -DJUDY1 or -DJUDYL must be specified.
#endif

#ifdef JUDY1
#include "Judy1.h"
#endif
#ifdef JUDYL
#include "JudyL.h"
#endif

#include "JudyPrivate1L.h"

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


// ****************************************************************************
// __ J U D Y   C O P Y   2   T O   3
//
// Copy one or more 2-byte Indexes to a series of 3-byte Indexes.

FUNCTION static void j__udyCopy2to3(
	uint8_t *  PDest,	// to where to copy 3-byte Indexes.
	uint16_t * PSrc,	// from where to copy 2-byte indexes.
	Word_t     Pop1,	// number of Indexes to copy.
	Word_t     MSByte)	// most-significant byte, prefix to each Index.
{
	Word_t	   Temp;	// for building 3-byte Index.

	assert(Pop1);

        do {
	    Temp = MSByte | *PSrc++;
	    JU_COPY3_LONG_TO_PINDEX(PDest, Temp);
	    PDest += 3;
        } while (--Pop1);

} // j__udyCopy2to3()


#ifdef JU_64BIT

// ****************************************************************************
// __ J U D Y   C O P Y   3   T O   4
//
// Copy one or more 3-byte Indexes to a series of 4-byte Indexes.

FUNCTION static void j__udyCopy3to4(
	uint32_t * PDest,	// to where to copy 4-byte Indexes.
	uint8_t *  PSrc,	// from where to copy 3-byte indexes.
	Word_t     Pop1,	// number of Indexes to copy.
	Word_t     MSByte)	// most-significant byte, prefix to each Index.
{
	Word_t	   Temp;	// for building 4-byte Index.

	assert(Pop1);

        do {
	    JU_COPY3_PINDEX_TO_LONG(Temp, PSrc);
	    Temp |= MSByte;
	    PSrc += 3;
	    *PDest++ = Temp;		// truncates to uint32_t.
        } while (--Pop1);

} // j__udyCopy3to4()


// ****************************************************************************
// __ J U D Y   C O P Y   4   T O   5
//
// Copy one or more 4-byte Indexes to a series of 5-byte Indexes.

FUNCTION static void j__udyCopy4to5(
	uint8_t *  PDest,	// to where to copy 4-byte Indexes.
	uint32_t * PSrc,	// from where to copy 4-byte indexes.
	Word_t     Pop1,	// number of Indexes to copy.
	Word_t     MSByte)	// most-significant byte, prefix to each Index.
{
	Word_t	   Temp;	// for building 5-byte Index.

	assert(Pop1);

        do {
	    Temp = MSByte | *PSrc++;
	    JU_COPY5_LONG_TO_PINDEX(PDest, Temp);
	    PDest += 5;
        } while (--Pop1);

} // j__udyCopy4to5()


// ****************************************************************************
// __ J U D Y   C O P Y   5   T O   6
//
// Copy one or more 5-byte Indexes to a series of 6-byte Indexes.

FUNCTION static void j__udyCopy5to6(
	uint8_t * PDest,	// to where to copy 6-byte Indexes.
	uint8_t * PSrc,		// from where to copy 5-byte indexes.
	Word_t    Pop1,		// number of Indexes to copy.
	Word_t    MSByte)	// most-significant byte, prefix to each Index.
{
	Word_t	  Temp;		// for building 6-byte Index.

	assert(Pop1);

        do {
	    JU_COPY5_PINDEX_TO_LONG(Temp, PSrc);
	    Temp |= MSByte;
	    JU_COPY6_LONG_TO_PINDEX(PDest, Temp);
	    PSrc  += 5;
	    PDest += 6;
        } while (--Pop1);

} // j__udyCopy5to6()


// ****************************************************************************
// __ J U D Y   C O P Y   6   T O   7
//
// Copy one or more 6-byte Indexes to a series of 7-byte Indexes.

FUNCTION static void j__udyCopy6to7(
	uint8_t * PDest,	// to where to copy 6-byte Indexes.
	uint8_t * PSrc,		// from where to copy 5-byte indexes.
	Word_t    Pop1,		// number of Indexes to copy.
	Word_t    MSByte)	// most-significant byte, prefix to each Index.
{
	Word_t	  Temp;		// for building 6-byte Index.

	assert(Pop1);

        do {
	    JU_COPY6_PINDEX_TO_LONG(Temp, PSrc);
	    Temp |= MSByte;
	    JU_COPY7_LONG_TO_PINDEX(PDest, Temp);
	    PSrc  += 6;
	    PDest += 7;
        } while (--Pop1);

} // j__udyCopy6to7()

#endif // JU_64BIT


#ifndef JU_64BIT // 32-bit

// ****************************************************************************
// __ J U D Y   C O P Y   3   T O   W
//
// Copy one or more 3-byte Indexes to a series of longs (words, always 4-byte).

FUNCTION static void j__udyCopy3toW(
	PWord_t   PDest,	// to where to copy full-word Indexes.
	uint8_t * PSrc,		// from where to copy 3-byte indexes.
	Word_t    Pop1,		// number of Indexes to copy.
	Word_t    MSByte)	// most-significant byte, prefix to each Index.
{
	assert(Pop1);

        do {
	    JU_COPY3_PINDEX_TO_LONG(*PDest, PSrc);
	    *PDest++ |= MSByte;
	    PSrc     += 3;
        } while (--Pop1);

} // j__udyCopy3toW()


#else // JU_64BIT

// ****************************************************************************
// __ J U D Y   C O P Y   7   T O   W
//
// Copy one or more 7-byte Indexes to a series of longs (words, always 8-byte).

FUNCTION static void j__udyCopy7toW(
	PWord_t   PDest,	// to where to copy full-word Indexes.
	uint8_t * PSrc,		// from where to copy 7-byte indexes.
	Word_t    Pop1,		// number of Indexes to copy.
	Word_t    MSByte)	// most-significant byte, prefix to each Index.
{
	assert(Pop1);

        do {
	    JU_COPY7_PINDEX_TO_LONG(*PDest, PSrc);
	    *PDest++ |= MSByte;
	    PSrc     += 7;
        } while (--Pop1);

} // j__udyCopy7toW()

#endif // JU_64BIT


// ****************************************************************************
// __ J U D Y   B R A N C H   B   T O   B R A N C H   L
//
// When a BranchB shrinks to have few enough JPs, call this function to convert
// it to a BranchL.  Return 1 for success, or -1 for failure (with details in
// Pjpm).

FUNCTION int j__udyBranchBToBranchL(
	Pjp_t	Pjp,		// points to BranchB to shrink.
	Pvoid_t	Pjpm)		// for global accounting.
{
	Pjbb_t	PjbbRaw;	// old BranchB to shrink.
	Pjbb_t	Pjbb;
	Pjbl_t	PjblRaw;	// new BranchL to create.
	Pjbl_t	Pjbl;
	Word_t	Digit;		// in BranchB.
	Word_t  NumJPs;		// non-null JPs in BranchB.
	uint8_t Expanse[cJU_BRANCHLMAXJPS];	// for building jbl_Expanse[].
	Pjp_t	Pjpjbl;		// current JP in BranchL.
	Word_t  SubExp;		// in BranchB.

	assert(JU_JPTYPE(Pjp) >= cJU_JPBRANCH_B2);
	assert(JU_JPTYPE(Pjp) <= cJU_JPBRANCH_B);

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

// Copy 1-byte subexpanse digits from BranchB to temporary buffer for BranchL,
// for each bit set in the BranchB:
//
// TBD:  The following supports variable-sized linear branches, but they are no
// longer variable; this could be simplified to save the copying.
//
// TBD:  Since cJU_BRANCHLMAXJP == 7 now, and cJU_BRANCHUNUMJPS == 256, the
// following might be inefficient; is there a faster way to do it?  At least
// skip wholly empty subexpanses?

	for (NumJPs = Digit = 0; Digit < cJU_BRANCHUNUMJPS; ++Digit)
	{
	    if (JU_BITMAPTESTB(Pjbb, Digit))
	    {
		Expanse[NumJPs++] = Digit;
		assert(NumJPs <= cJU_BRANCHLMAXJPS);	// required of caller.
	    }
	}

// Allocate and populate the BranchL:

	if ((PjblRaw = j__udyAllocJBL(Pjpm)) == (Pjbl_t) NULL) return(-1);
	Pjbl = P_JBL(PjblRaw);

	JU_COPYMEM(Pjbl->jbl_Expanse, Expanse, NumJPs);

	Pjbl->jbl_NumJPs = NumJPs;
	DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse), NumJPs, 1);)

// Copy JPs from each BranchB subexpanse subarray:

	Pjpjbl = P_JP(Pjbl->jbl_jp);	// start at first JP in array.

	for (SubExp = 0; SubExp < cJU_NUMSUBEXPB; ++SubExp)
	{
	    Pjp_t PjpRaw = JU_JBB_PJP(Pjbb, SubExp);	// current Pjp.
	    Pjp_t Pjp;

	    if (PjpRaw == (Pjp_t) NULL) continue;  // skip empty subexpanse.
	    Pjp = P_JP(PjpRaw);

	    NumJPs = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, SubExp));
	    assert(NumJPs);
	    JU_COPYMEM(Pjpjbl, Pjp, NumJPs);	 // one subarray at a time.

	    Pjpjbl += NumJPs;
	    j__udyFreeJBBJP(PjpRaw, NumJPs, Pjpm);	// subarray.
	}
	j__udyFreeJBB(PjbbRaw, Pjpm);		// BranchB itself.

// Finish up:  Calculate new JP type (same index size = level in new class),
// and tie new BranchB into parent JP:

	Pjp->jp_Type += cJU_JPBRANCH_L - cJU_JPBRANCH_B;
	Pjp->jp_Addr  = (Word_t) PjblRaw;

	return(1);

} // j__udyBranchBToBranchL()


#ifdef notdef

// ****************************************************************************
// __ J U D Y   B R A N C H   U   T O   B R A N C H   B
//
// When a BranchU shrinks to need little enough memory, call this function to
// convert it to a BranchB to save memory (at the cost of some speed).  Return
// 1 for success, or -1 for failure (with details in Pjpm).
//
// TBD:  Fill out if/when needed.  Not currently used in JudyDel.c for reasons
// explained there.

FUNCTION int j__udyBranchUToBranchB(
	Pjp_t	Pjp,		// points to BranchU to shrink.
	Pvoid_t	Pjpm)		// for global accounting.
{
	assert(FALSE);
	return(1);
}
#endif // notdef


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

// ****************************************************************************
// __ J U D Y   L E A F   B 1   T O   L E A F   1
//
// Shrink a bitmap leaf (cJU_LEAFB1) to linear leaf (cJU_JPLEAF1).
// Return 1 for success, or -1 for failure (with details in Pjpm).
//
// Note:  This function is different than the other JudyLeaf*ToLeaf*()
// functions because it receives a Pjp, not just a leaf, and handles its own
// allocation and free, in order to allow the caller to continue with a LeafB1
// if allocation fails.

FUNCTION int j__udyLeafB1ToLeaf1(
	Pjp_t	  Pjp,		// points to LeafB1 to shrink.
	Pvoid_t	  Pjpm)		// for global accounting.
{
	Pjlb_t    PjlbRaw;	// bitmap in old leaf.
	Pjlb_t    Pjlb;
	Pjll_t	  PjllRaw;	// new Leaf1.
	uint8_t	* Pleaf1;	// Leaf1 pointer type.
	Word_t    Digit;	// in LeafB1 bitmap.
#ifdef JUDYL
	Pjv_t	  PjvNew;	// value area in new Leaf1.
	Word_t    Pop1;
	Word_t    SubExp;
#endif

	assert(JU_JPTYPE(Pjp) == cJU_JPLEAF_B1);
	assert(((JU_JPDCDPOP0(Pjp) & 0xFF) + 1) == cJU_LEAF1_MAXPOP1);

// Allocate JPLEAF1 and prepare pointers:

	if ((PjllRaw = j__udyAllocJLL1(cJU_LEAF1_MAXPOP1, Pjpm)) == 0)
	    return(-1);

	Pleaf1	= (uint8_t *) P_JLL(PjllRaw);
	PjlbRaw	= (Pjlb_t) (Pjp->jp_Addr);
	Pjlb	= P_JLB(PjlbRaw);
	JUDYLCODE(PjvNew = JL_LEAF1VALUEAREA(Pleaf1, cJL_LEAF1_MAXPOP1);)

// Copy 1-byte indexes from old LeafB1 to new Leaf1:

	for (Digit = 0; Digit < cJU_BRANCHUNUMJPS; ++Digit)
	    if (JU_BITMAPTESTL(Pjlb, Digit))
		*Pleaf1++ = Digit;

#ifdef JUDYL

// Copy all old-LeafB1 value areas from value subarrays to new Leaf1:

	for (SubExp = 0; SubExp < cJU_NUMSUBEXPL; ++SubExp)
	{
	    Pjv_t PjvRaw = JL_JLB_PVALUE(Pjlb, SubExp);
	    Pjv_t Pjv    = P_JV(PjvRaw);

	    if (Pjv == (Pjv_t) NULL) continue;	// skip empty subarray.

	    Pop1 = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, SubExp));  // subarray.
	    assert(Pop1);

	    JU_COPYMEM(PjvNew, Pjv, Pop1);		// copy value areas.
	    j__udyLFreeJV(PjvRaw, Pop1, Pjpm);
	    PjvNew += Pop1;				// advance through new.
	}

	assert((((Word_t) Pleaf1) - (Word_t) P_JLL(PjllRaw))
	    == (PjvNew - JL_LEAF1VALUEAREA(P_JLL(PjllRaw), cJL_LEAF1_MAXPOP1)));
#endif // JUDYL

	DBGCODE(JudyCheckSorted((Pjll_t) P_JLL(PjllRaw),
			    (((Word_t) Pleaf1) - (Word_t) P_JLL(PjllRaw)), 1);)

// Finish up:  Free the old LeafB1 and plug the new Leaf1 into the JP:
//
// Note:  jp_DcdPopO does not change here.

	j__udyFreeJLB1(PjlbRaw, Pjpm);

	Pjp->jp_Addr = (Word_t) PjllRaw;
	Pjp->jp_Type = cJU_JPLEAF1;

	return(1);

} // j__udyLeafB1ToLeaf1()

#endif // (JUDYL || (! JU_64BIT))


// ****************************************************************************
// __ J U D Y   L E A F   1   T O   L E A F   2
//
// Copy 1-byte Indexes from a LeafB1 or Leaf1 to 2-byte Indexes in a Leaf2.
// Pjp MUST be one of:  cJU_JPLEAF_B1, cJU_JPLEAF1, or cJU_JPIMMED_1_*.
// Return number of Indexes copied.
//
// TBD:  In this and all following functions, the caller should already be able
// to compute the Pop1 return value, so why return it?

FUNCTION Word_t  j__udyLeaf1ToLeaf2(
	uint16_t * PLeaf2,	// destination uint16_t * Index portion of leaf.
#ifdef JUDYL
	Pjv_t	   Pjv2,	// destination value part of leaf.
#endif
	Pjp_t	   Pjp,		// 1-byte-index object from which to copy.
	Word_t     MSByte,	// most-significant byte, prefix to each Index.
	Pvoid_t	   Pjpm)	// for global accounting.
{
	Word_t	   Pop1;	// Indexes in leaf.
	Word_t	   Offset;	// in linear leaf list.
JUDYLCODE(Pjv_t	   Pjv1Raw;)	// source object value area.
JUDYLCODE(Pjv_t	   Pjv1;)

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF_B1:

	case cJU_JPLEAF_B1:
	{
	    Pjlb_t Pjlb = P_JLB(Pjp->jp_Addr);
	    Word_t Digit;	// in LeafB1 bitmap.
  JUDYLCODE(Word_t SubExp;)	// in LeafB1.

	    Pop1 = JU_JPBRANCH_POP0(Pjp, 1) + 1; assert(Pop1);

// Copy 1-byte indexes from old LeafB1 to new Leaf2, including splicing in
// the missing MSByte needed in the Leaf2:

	    for (Digit = 0; Digit < cJU_BRANCHUNUMJPS; ++Digit)
		if (JU_BITMAPTESTL(Pjlb, Digit))
		    *PLeaf2++ = MSByte | Digit;

#ifdef JUDYL

// Copy all old-LeafB1 value areas from value subarrays to new Leaf2:

	    for (SubExp = 0; SubExp < cJU_NUMSUBEXPL; ++SubExp)
	    {
		Word_t SubExpPop1;

		Pjv1Raw = JL_JLB_PVALUE(Pjlb, SubExp);
		if (Pjv1Raw == (Pjv_t) NULL) continue;	// skip empty.
		Pjv1 = P_JV(Pjv1Raw);

		SubExpPop1 = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, SubExp));
		assert(SubExpPop1);

		JU_COPYMEM(Pjv2, Pjv1, SubExpPop1);	// copy value areas.
		j__udyLFreeJV(Pjv1Raw, SubExpPop1, Pjpm);
		Pjv2 += SubExpPop1;			// advance through new.
	    }
#endif // JUDYL

	    j__udyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm);  // LeafB1 itself.
	    return(Pop1);

	} // case cJU_JPLEAF_B1


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

// JPLEAF1:

	case cJU_JPLEAF1:
	{
	    uint8_t * PLeaf1 = (uint8_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPBRANCH_POP0(Pjp, 1) + 1; assert(Pop1);
	    JUDYLCODE(Pjv1 = JL_LEAF1VALUEAREA(PLeaf1, Pop1);)

// Copy all Index bytes including splicing in missing MSByte needed in Leaf2
// (plus, for JudyL, value areas):

	    for (Offset = 0; Offset < Pop1; ++Offset)
	    {
		PLeaf2[Offset] = MSByte | PLeaf1[Offset];
		JUDYLCODE(Pjv2[Offset] = Pjv1[Offset];)
	    }
	    j__udyFreeJLL1((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}
#endif // (JUDYL || (! JU_64BIT))


// JPIMMED_1_01:
//
// Note:  jp_DcdPopO has 3 [7] bytes of Index (all but most significant byte),
// so the assignment to PLeaf2[] truncates and MSByte is not needed.

	case cJU_JPIMMED_1_01:
	{
	    PLeaf2[0] = JU_JPDCDPOP0(Pjp);	// see above.
	    JUDYLCODE(Pjv2[0] = Pjp->jp_Addr;)
	    return(1);
	}


// JPIMMED_1_0[2+]:

	case cJU_JPIMMED_1_02:
	case cJU_JPIMMED_1_03:
#if (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_1_04:
	case cJU_JPIMMED_1_05:
	case cJU_JPIMMED_1_06:
	case cJU_JPIMMED_1_07:
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
	case cJ1_JPIMMED_1_08:
	case cJ1_JPIMMED_1_09:
	case cJ1_JPIMMED_1_10:
	case cJ1_JPIMMED_1_11:
	case cJ1_JPIMMED_1_12:
	case cJ1_JPIMMED_1_13:
	case cJ1_JPIMMED_1_14:
	case cJ1_JPIMMED_1_15:
#endif
	{
	    Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_1_02 + 2; assert(Pop1);
	    JUDYLCODE(Pjv1Raw = (Pjv_t) (Pjp->jp_Addr);)
	    JUDYLCODE(Pjv1    = P_JV(Pjv1Raw);)

	    for (Offset = 0; Offset < Pop1; ++Offset)
	    {
#ifdef JUDY1
		PLeaf2[Offset] = MSByte | Pjp->jp_1Index[Offset];
#else
		PLeaf2[Offset] = MSByte | Pjp->jp_LIndex[Offset];
		Pjv2  [Offset] = Pjv1[Offset];
#endif
	    }
	    JUDYLCODE(j__udyLFreeJV(Pjv1Raw, Pop1, Pjpm);)
	    return(Pop1);
	}


// UNEXPECTED CASES, including JPNULL1, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf1ToLeaf2()


// *****************************************************************************
// __ J U D Y   L E A F   2   T O   L E A F   3
//
// Copy 2-byte Indexes from a Leaf2 to 3-byte Indexes in a Leaf3.
// Pjp MUST be one of:  cJU_JPLEAF2 or cJU_JPIMMED_2_*.
// Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-3 branch to a
// Leaf3, the branch has no narrow pointers under it, meaning only level-2
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf2ToLeaf3(
	uint8_t * PLeaf3,	// destination "uint24_t *" Index part of leaf.
#ifdef JUDYL
	Pjv_t	  Pjv3,		// destination value part of leaf.
#endif
	Pjp_t	  Pjp,		// 2-byte-index object from which to copy.
	Word_t    MSByte,	// most-significant byte, prefix to each Index.
	Pvoid_t	  Pjpm)		// for global accounting.
{
	Word_t	  Pop1;		// Indexes in leaf.
#if (defined(JUDYL) && defined(JU_64BIT))
	Pjv_t	  Pjv2Raw;	// source object value area.
#endif
JUDYLCODE(Pjv_t	  Pjv2;)

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF2:

	case cJU_JPLEAF2:
	{
	    uint16_t * PLeaf2 = (uint16_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1; assert(Pop1);
	    j__udyCopy2to3(PLeaf3, PLeaf2, Pop1, MSByte);
#ifdef JUDYL
	    Pjv2 = JL_LEAF2VALUEAREA(PLeaf2, Pop1);
	    JU_COPYMEM(Pjv3, Pjv2, Pop1);
#endif
	    j__udyFreeJLL2((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_2_01:
//
// Note:  jp_DcdPopO has 3 [7] bytes of Index (all but most significant byte),
// so the "assignment" to PLeaf3[] is exact [truncates] and MSByte is not
// needed.

	case cJU_JPIMMED_2_01:
	{
	    JU_COPY3_LONG_TO_PINDEX(PLeaf3, JU_JPDCDPOP0(Pjp));	// see above.
	    JUDYLCODE(Pjv3[0] = Pjp->jp_Addr;)
	    return(1);
	}


// JPIMMED_2_0[2+]:

#if (defined(JUDY1) || defined(JU_64BIT))
	case cJU_JPIMMED_2_02:
	case cJU_JPIMMED_2_03:
#endif
#if (defined(JUDY1) && defined(JU_64BIT))
	case cJ1_JPIMMED_2_04:
	case cJ1_JPIMMED_2_05:
	case cJ1_JPIMMED_2_06:
	case cJ1_JPIMMED_2_07:
#endif
#if (defined(JUDY1) || defined(JU_64BIT))
	{
	    JUDY1CODE(uint16_t * PLeaf2 = (uint16_t *) (Pjp->jp_1Index);)
	    JUDYLCODE(uint16_t * PLeaf2 = (uint16_t *) (Pjp->jp_LIndex);)

	    Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_2_02 + 2; assert(Pop1);
	    j__udyCopy2to3(PLeaf3, PLeaf2, Pop1, MSByte);
#ifdef JUDYL
	    Pjv2Raw = (Pjv_t) (Pjp->jp_Addr);
	    Pjv2    = P_JV(Pjv2Raw);
	    JU_COPYMEM(Pjv3, Pjv2, Pop1);
	    j__udyLFreeJV(Pjv2Raw, Pop1, Pjpm);
#endif
	    return(Pop1);
	}
#endif // (JUDY1 || JU_64BIT)


// UNEXPECTED CASES, including JPNULL2, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf2ToLeaf3()


#ifdef JU_64BIT

// ****************************************************************************
// __ J U D Y   L E A F   3   T O   L E A F   4
//
// Copy 3-byte Indexes from a Leaf3 to 4-byte Indexes in a Leaf4.
// Pjp MUST be one of:  cJU_JPLEAF3 or cJU_JPIMMED_3_*.
// Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-4 branch to a
// Leaf4, the branch has no narrow pointers under it, meaning only level-3
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf3ToLeaf4(
	uint32_t * PLeaf4,	// destination uint32_t * Index part of leaf.
#ifdef JUDYL
	Pjv_t	   Pjv4,	// destination value part of leaf.
#endif
	Pjp_t	   Pjp,		// 3-byte-index object from which to copy.
	Word_t     MSByte,	// most-significant byte, prefix to each Index.
	Pvoid_t	   Pjpm)	// for global accounting.
{
	Word_t	   Pop1;	// Indexes in leaf.
JUDYLCODE(Pjv_t	   Pjv3Raw;)	// source object value area.
JUDYLCODE(Pjv_t	   Pjv3;)

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF3:

	case cJU_JPLEAF3:
	{
	    uint8_t * PLeaf3 = (uint8_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1; assert(Pop1);
	    j__udyCopy3to4(PLeaf4, (uint8_t *) PLeaf3, Pop1, MSByte);
#ifdef JUDYL
	    Pjv3 = JL_LEAF3VALUEAREA(PLeaf3, Pop1);
	    JU_COPYMEM(Pjv4, Pjv3, Pop1);
#endif
	    j__udyFreeJLL3((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_3_01:
//
// Note:  jp_DcdPopO has 7 bytes of Index (all but most significant byte), so
// the assignment to PLeaf4[] truncates and MSByte is not needed.

	case cJU_JPIMMED_3_01:
	{
	    PLeaf4[0] = JU_JPDCDPOP0(Pjp);	// see above.
	    JUDYLCODE(Pjv4[0] = Pjp->jp_Addr;)
	    return(1);
	}


// JPIMMED_3_0[2+]:

	case cJU_JPIMMED_3_02:
#ifdef JUDY1
	case cJ1_JPIMMED_3_03:
	case cJ1_JPIMMED_3_04:
	case cJ1_JPIMMED_3_05:
#endif
	{
	    JUDY1CODE(uint8_t * PLeaf3 = (uint8_t *) (Pjp->jp_1Index);)
	    JUDYLCODE(uint8_t * PLeaf3 = (uint8_t *) (Pjp->jp_LIndex);)

	    JUDY1CODE(Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_3_02 + 2;)
	    JUDYLCODE(Pop1 = 2;)

	    j__udyCopy3to4(PLeaf4, PLeaf3, Pop1, MSByte);
#ifdef JUDYL
	    Pjv3Raw = (Pjv_t) (Pjp->jp_Addr);
	    Pjv3    = P_JV(Pjv3Raw);
	    JU_COPYMEM(Pjv4, Pjv3, Pop1);
	    j__udyLFreeJV(Pjv3Raw, Pop1, Pjpm);
#endif
	    return(Pop1);
	}


// UNEXPECTED CASES, including JPNULL3, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf3ToLeaf4()


// Note:  In all following j__udyLeaf*ToLeaf*() functions, JPIMMED_*_0[2+]
// cases exist for Judy1 (&& 64-bit) only.  JudyL has no equivalent Immeds.


// *****************************************************************************
// __ J U D Y   L E A F   4   T O   L E A F   5
//
// Copy 4-byte Indexes from a Leaf4 to 5-byte Indexes in a Leaf5.
// Pjp MUST be one of:  cJU_JPLEAF4 or cJU_JPIMMED_4_*.
// Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-5 branch to a
// Leaf5, the branch has no narrow pointers under it, meaning only level-4
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf4ToLeaf5(
	uint8_t * PLeaf5,	// destination "uint40_t *" Index part of leaf.
#ifdef JUDYL
	Pjv_t	  Pjv5,		// destination value part of leaf.
#endif
	Pjp_t	  Pjp,		// 4-byte-index object from which to copy.
	Word_t    MSByte,	// most-significant byte, prefix to each Index.
	Pvoid_t	  Pjpm)		// for global accounting.
{
	Word_t	  Pop1;		// Indexes in leaf.
JUDYLCODE(Pjv_t	  Pjv4;)	// source object value area.

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF4:

	case cJU_JPLEAF4:
	{
	    uint32_t * PLeaf4 = (uint32_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1; assert(Pop1);
	    j__udyCopy4to5(PLeaf5, PLeaf4, Pop1, MSByte);
#ifdef JUDYL
	    Pjv4 = JL_LEAF4VALUEAREA(PLeaf4, Pop1);
	    JU_COPYMEM(Pjv5, Pjv4, Pop1);
#endif
	    j__udyFreeJLL4((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_4_01:
//
// Note:  jp_DcdPopO has 7 bytes of Index (all but most significant byte), so
// the assignment to PLeaf5[] truncates and MSByte is not needed.

	case cJU_JPIMMED_4_01:
	{
	    JU_COPY5_LONG_TO_PINDEX(PLeaf5, JU_JPDCDPOP0(Pjp));	// see above.
	    JUDYLCODE(Pjv5[0] = Pjp->jp_Addr;)
	    return(1);
	}


#ifdef JUDY1

// JPIMMED_4_0[4+]:

	case cJ1_JPIMMED_4_02:
	case cJ1_JPIMMED_4_03:
	{
	    uint32_t * PLeaf4 = (uint32_t *) (Pjp->jp_1Index);

	    Pop1 = JU_JPTYPE(Pjp) - cJ1_JPIMMED_4_02 + 2;
	    j__udyCopy4to5(PLeaf5, PLeaf4, Pop1, MSByte);
	    return(Pop1);
	}
#endif // JUDY1


// UNEXPECTED CASES, including JPNULL4, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf4ToLeaf5()


// ****************************************************************************
// __ J U D Y   L E A F   5   T O   L E A F   6
//
// Copy 5-byte Indexes from a Leaf5 to 6-byte Indexes in a Leaf6.
// Pjp MUST be one of:  cJU_JPLEAF5 or cJU_JPIMMED_5_*.
// Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-6 branch to a
// Leaf6, the branch has no narrow pointers under it, meaning only level-5
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf5ToLeaf6(
	uint8_t * PLeaf6,	// destination uint8_t * Index part of leaf.
#ifdef JUDYL
	Pjv_t	  Pjv6,		// destination value part of leaf.
#endif
	Pjp_t	  Pjp,		// 5-byte-index object from which to copy.
	Word_t    MSByte,	// most-significant byte, prefix to each Index.
	Pvoid_t	  Pjpm)		// for global accounting.
{
	Word_t	  Pop1;		// Indexes in leaf.
JUDYLCODE(Pjv_t	  Pjv5;)	// source object value area.

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF5:

	case cJU_JPLEAF5:
	{
	    uint8_t * PLeaf5 = (uint8_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1; assert(Pop1);
	    j__udyCopy5to6(PLeaf6, PLeaf5, Pop1, MSByte);
#ifdef JUDYL
	    Pjv5 = JL_LEAF5VALUEAREA(PLeaf5, Pop1);
	    JU_COPYMEM(Pjv6, Pjv5, Pop1);
#endif
	    j__udyFreeJLL5((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_5_01:
//
// Note:  jp_DcdPopO has 7 bytes of Index (all but most significant byte), so
// the assignment to PLeaf6[] truncates and MSByte is not needed.

	case cJU_JPIMMED_5_01:
	{
	    JU_COPY6_LONG_TO_PINDEX(PLeaf6, JU_JPDCDPOP0(Pjp));	// see above.
	    JUDYLCODE(Pjv6[0] = Pjp->jp_Addr;)
	    return(1);
	}


#ifdef JUDY1

// JPIMMED_5_0[2+]:

	case cJ1_JPIMMED_5_02:
	case cJ1_JPIMMED_5_03:
	{
	    uint8_t * PLeaf5 = (uint8_t *) (Pjp->jp_1Index);

	    Pop1 = JU_JPTYPE(Pjp) - cJ1_JPIMMED_5_02 + 2;
	    j__udyCopy5to6(PLeaf6, PLeaf5, Pop1, MSByte);
	    return(Pop1);
	}
#endif // JUDY1


// UNEXPECTED CASES, including JPNULL5, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf5ToLeaf6()


// *****************************************************************************
// __ J U D Y   L E A F   6   T O   L E A F   7
//
// Copy 6-byte Indexes from a Leaf2 to 7-byte Indexes in a Leaf7.
// Pjp MUST be one of:  cJU_JPLEAF6 or cJU_JPIMMED_6_*.
// Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-7 branch to a
// Leaf7, the branch has no narrow pointers under it, meaning only level-6
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf6ToLeaf7(
	uint8_t * PLeaf7,	// destination "uint24_t *" Index part of leaf.
#ifdef JUDYL
	Pjv_t	  Pjv7,		// destination value part of leaf.
#endif
	Pjp_t	  Pjp,		// 6-byte-index object from which to copy.
	Word_t    MSByte,	// most-significant byte, prefix to each Index.
	Pvoid_t	  Pjpm)		// for global accounting.
{
	Word_t	  Pop1;		// Indexes in leaf.
JUDYLCODE(Pjv_t	  Pjv6;)	// source object value area.

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF6:

	case cJU_JPLEAF6:
	{
	    uint8_t * PLeaf6 = (uint8_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
	    j__udyCopy6to7(PLeaf7, PLeaf6, Pop1, MSByte);
#ifdef JUDYL
	    Pjv6 = JL_LEAF6VALUEAREA(PLeaf6, Pop1);
	    JU_COPYMEM(Pjv7, Pjv6, Pop1);
#endif
	    j__udyFreeJLL6((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_6_01:
//
// Note:  jp_DcdPopO has 7 bytes of Index (all but most significant byte), so
// the "assignment" to PLeaf7[] is exact and MSByte is not needed.

	case cJU_JPIMMED_6_01:
	{
	    JU_COPY7_LONG_TO_PINDEX(PLeaf7, JU_JPDCDPOP0(Pjp));	// see above.
	    JUDYLCODE(Pjv7[0] = Pjp->jp_Addr;)
	    return(1);
	}


#ifdef JUDY1

// JPIMMED_6_02:

	case cJ1_JPIMMED_6_02:
	{
	    uint8_t * PLeaf6 = (uint8_t *) (Pjp->jp_1Index);

	    j__udyCopy6to7(PLeaf7, PLeaf6, /* Pop1 = */ 2, MSByte);
	    return(2);
	}
#endif // JUDY1


// UNEXPECTED CASES, including JPNULL6, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf6ToLeaf7()

#endif // JU_64BIT


#ifndef JU_64BIT // 32-bit version first

// ****************************************************************************
// __ J U D Y   L E A F   3   T O   L E A F   W
//
// Copy 3-byte Indexes from a Leaf3 to 4-byte Indexes in a LeafW.  Pjp MUST be
// one of:  cJU_JPLEAF3 or cJU_JPIMMED_3_*.  Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-L branch to a
// LeafW, the branch has no narrow pointers under it, meaning only level-3
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf3ToLeafW(
	Pjlw_t	Pjlw,		// destination Index part of leaf.
#ifdef JUDYL
	Pjv_t	PjvW,		// destination value part of leaf.
#endif
	Pjp_t	Pjp,		// 3-byte-index object from which to copy.
	Word_t	MSByte,		// most-significant byte, prefix to each Index.
	Pvoid_t	Pjpm)		// for global accounting.
{
	Word_t	Pop1;		// Indexes in leaf.
JUDYLCODE(Pjv_t Pjv3;)		// source object value area.

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF3:

	case cJU_JPLEAF3:
	{
	    uint8_t * PLeaf3 = (uint8_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
	    j__udyCopy3toW((PWord_t) Pjlw, PLeaf3, Pop1, MSByte);
#ifdef JUDYL
	    Pjv3 = JL_LEAF3VALUEAREA(PLeaf3, Pop1);
	    JU_COPYMEM(PjvW, Pjv3, Pop1);
#endif
	    j__udyFreeJLL3((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_3_01:
//
// Note:  jp_DcdPopO has 3 bytes of Index (all but most significant byte), and
// MSByte must be ord in.

	case cJU_JPIMMED_3_01:
	{
	    Pjlw[0] = MSByte | JU_JPDCDPOP0(Pjp);		// see above.
	    JUDYLCODE(PjvW[0] = Pjp->jp_Addr;)
	    return(1);
	}


#ifdef JUDY1

// JPIMMED_3_02:

	case cJU_JPIMMED_3_02:
	{
	    uint8_t * PLeaf3 = (uint8_t *) (Pjp->jp_1Index);

	    j__udyCopy3toW((PWord_t) Pjlw, PLeaf3, /* Pop1 = */ 2, MSByte);
	    return(2);
	}
#endif // JUDY1


// UNEXPECTED CASES, including JPNULL3, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf3ToLeafW()


#else // JU_64BIT


// ****************************************************************************
// __ J U D Y   L E A F   7   T O   L E A F   W
//
// Copy 7-byte Indexes from a Leaf7 to 8-byte Indexes in a LeafW.
// Pjp MUST be one of:  cJU_JPLEAF7 or cJU_JPIMMED_7_*.
// Return number of Indexes copied.
//
// Note:  By the time this function is called to compress a level-L branch to a
// LeafW, the branch has no narrow pointers under it, meaning only level-7
// objects are below it and must be handled here.

FUNCTION Word_t  j__udyLeaf7ToLeafW(
	Pjlw_t	Pjlw,		// destination Index part of leaf.
#ifdef JUDYL
	Pjv_t	PjvW,		// destination value part of leaf.
#endif
	Pjp_t	Pjp,		// 7-byte-index object from which to copy.
	Word_t	MSByte,		// most-significant byte, prefix to each Index.
	Pvoid_t	Pjpm)		// for global accounting.
{
	Word_t	Pop1;		// Indexes in leaf.
JUDYLCODE(Pjv_t	Pjv7;)		// source object value area.

	switch (JU_JPTYPE(Pjp))
	{


// JPLEAF7:

	case cJU_JPLEAF7:
	{
	    uint8_t * PLeaf7 = (uint8_t *) P_JLL(Pjp->jp_Addr);

	    Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
	    j__udyCopy7toW((PWord_t) Pjlw, PLeaf7, Pop1, MSByte);
#ifdef JUDYL
	    Pjv7 = JL_LEAF7VALUEAREA(PLeaf7, Pop1);
	    JU_COPYMEM(PjvW, Pjv7, Pop1);
#endif
	    j__udyFreeJLL7((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
	    return(Pop1);
	}


// JPIMMED_7_01:
//
// Note:  jp_DcdPopO has 7 bytes of Index (all but most significant byte), and
// MSByte must be ord in.

	case cJU_JPIMMED_7_01:
	{
	    Pjlw[0] = MSByte | JU_JPDCDPOP0(Pjp);		// see above.
	    JUDYLCODE(PjvW[0] = Pjp->jp_Addr;)
	    return(1);
	}


#ifdef JUDY1

// JPIMMED_7_02:

	case cJ1_JPIMMED_7_02:
	{
	    uint8_t * PLeaf7 = (uint8_t *) (Pjp->jp_1Index);

	    j__udyCopy7toW((PWord_t) Pjlw, PLeaf7, /* Pop1 = */ 2, MSByte);
	    return(2);
	}
#endif


// UNEXPECTED CASES, including JPNULL7, should be handled by caller:

	default: assert(FALSE); break;

	} // switch

	return(0);

} // j__udyLeaf7ToLeafW()

#endif // JU_64BIT