diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLDecascade.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyL/JudyLDecascade.c | 1206 |
1 files changed, 1206 insertions, 0 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLDecascade.c b/libnetdata/libjudy/src/JudyL/JudyLDecascade.c new file mode 100644 index 00000000..39a89eff --- /dev/null +++ b/libnetdata/libjudy/src/JudyL/JudyLDecascade.c @@ -0,0 +1,1206 @@ +// 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 |