diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyL/JudyLDel.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyL/JudyLDel.c | 2146 |
1 files changed, 0 insertions, 2146 deletions
diff --git a/libnetdata/libjudy/src/JudyL/JudyLDel.c b/libnetdata/libjudy/src/JudyL/JudyLDel.c deleted file mode 100644 index ced4b5fb3..000000000 --- a/libnetdata/libjudy/src/JudyL/JudyLDel.c +++ /dev/null @@ -1,2146 +0,0 @@ -// 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.68 $ $Source: /judy/src/JudyCommon/JudyDel.c $ -// -// Judy1Unset() and JudyLDel() functions for Judy1 and JudyL. -// Compile with one of -DJUDY1 or -DJUDYL. -// -// About HYSTERESIS: In the Judy code, hysteresis means leaving around a -// nominally suboptimal (not maximally compressed) data structure after a -// deletion. As a result, the shape of the tree for two identical index sets -// can differ depending on the insert/delete path taken to arrive at the index -// sets. The purpose is to minimize worst-case behavior (thrashing) that could -// result from a series of intermixed insertions and deletions. It also makes -// for MUCH simpler code, because instead of performing, "delete and then -// compress," it can say, "compress and then delete," where due to hysteresis, -// compression is not even attempted until the object IS compressible. -// -// In some cases the code has no choice and it must "ungrow" a data structure -// across a "phase transition" boundary without hysteresis. In other cases the -// amount (such as "hysteresis = 1") is indicated by the number of JP deletions -// (in branches) or index deletions (in leaves) that can occur in succession -// before compressing the data structure. (It appears that hysteresis <= 1 in -// all cases.) -// -// In general no hysteresis occurs when the data structure type remains the -// same but the allocated memory chunk for the node must shrink, because the -// relationship is hardwired and theres no way to know how much memory is -// allocated to a given data structure. Hysteresis = 0 in all these cases. -// -// TBD: Could this code be faster if memory chunk hysteresis were supported -// somehow along with data structure type hysteresis? -// -// TBD: Should some of the assertions here be converted to product code that -// returns JU_ERRNO_CORRUPT? -// -// TBD: Dougs code had an odd mix of function-wide and limited-scope -// variables. Should some of the function-wide variables appear only in -// limited scopes, or more likely, vice-versa? - -#if (! (defined(JUDY1) || defined(JUDYL))) -#error: One of -DJUDY1 or -DJUDYL must be specified. -#endif - -#ifdef JUDY1 -#include "Judy1.h" -#else -#include "JudyL.h" -#endif - -#include "JudyPrivate1L.h" - -DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);) -DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);) - -#ifdef TRACEJP -#include "JudyPrintJP.c" -#endif - -// These are defined to generic values in JudyCommon/JudyPrivateTypes.h: -// -// TBD: These should be exported from a header file, but perhaps not, as they -// are only used here, and exported from JudyDecascade.c, which is a separate -// file for profiling reasons (to prevent inlining), but which potentially -// could be merged with this file, either in SoftCM or at compile-time: - -#ifdef JUDY1 - -extern int j__udy1BranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm); -#ifndef JU_64BIT -extern int j__udy1LeafB1ToLeaf1(Pjp_t, Pvoid_t); -#endif -extern Word_t j__udy1Leaf1ToLeaf2(uint16_t *, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udy1Leaf2ToLeaf3(uint8_t *, Pjp_t, Word_t, Pvoid_t); -#ifndef JU_64BIT -extern Word_t j__udy1Leaf3ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t); -#else -extern Word_t j__udy1Leaf3ToLeaf4(uint32_t *, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udy1Leaf4ToLeaf5(uint8_t *, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udy1Leaf5ToLeaf6(uint8_t *, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udy1Leaf6ToLeaf7(uint8_t *, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udy1Leaf7ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t); -#endif - -#else // JUDYL - -extern int j__udyLBranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm); -extern int j__udyLLeafB1ToLeaf1(Pjp_t, Pvoid_t); -extern Word_t j__udyLLeaf1ToLeaf2(uint16_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udyLLeaf2ToLeaf3(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t); -#ifndef JU_64BIT -extern Word_t j__udyLLeaf3ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t); -#else -extern Word_t j__udyLLeaf3ToLeaf4(uint32_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udyLLeaf4ToLeaf5(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udyLLeaf5ToLeaf6(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udyLLeaf6ToLeaf7(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t); -extern Word_t j__udyLLeaf7ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t); -#endif - -#endif // JUDYL - -// For convenience in the calling code; "M1" means "minus one": - -#ifndef JU_64BIT -#define j__udyLeafM1ToLeafW j__udyLeaf3ToLeafW -#else -#define j__udyLeafM1ToLeafW j__udyLeaf7ToLeafW -#endif - - -// **************************************************************************** -// __ J U D Y D E L W A L K -// -// Given a pointer to a JP, an Index known to be valid, the number of bytes -// left to decode (== level in the tree), and a pointer to a global JPM, walk a -// Judy (sub)tree to do an unset/delete of that index, and possibly modify the -// JPM. This function is only called internally, and recursively. Unlike -// Judy1Test() and JudyLGet(), the extra time required for recursion should be -// negligible compared with the total. -// -// Return values: -// -// -1 error; details in JPM -// -// 0 Index already deleted (should never happen, Index is known to be valid) -// -// 1 previously valid Index deleted -// -// 2 same as 1, but in addition the JP now points to a BranchL containing a -// single JP, which should be compressed into the parent branch (if there -// is one, which is not the case for a top-level branch under a JPM) - -DBGCODE(uint8_t parentJPtype;) // parent branch JP type. - -FUNCTION static int j__udyDelWalk( - Pjp_t Pjp, // current JP under which to delete. - Word_t Index, // to delete. - Word_t ParentLevel, // of parent branch. - Pjpm_t Pjpm) // for returning info to top level. -{ - Word_t pop1; // of a leaf. - Word_t level; // of a leaf. - uint8_t digit; // from Index, in current branch. - Pjll_t PjllnewRaw; // address of newly allocated leaf. - Pjll_t Pjllnew; - int offset; // within a branch. - int retcode; // return code: -1, 0, 1, 2. -JUDYLCODE(Pjv_t PjvRaw;) // value area. -JUDYLCODE(Pjv_t Pjv;) - - DBGCODE(level = 0;) - -ContinueDelWalk: // for modifying state without recursing. - -#ifdef TRACEJP - JudyPrintJP(Pjp, "d", __LINE__); -#endif - - switch (JU_JPTYPE(Pjp)) // entry: Pjp, Index. - { - - -// **************************************************************************** -// LINEAR BRANCH: -// -// MACROS FOR COMMON CODE: -// -// Check for population too high to compress a branch to a leaf, meaning just -// descend through the branch, with a purposeful off-by-one error that -// constitutes hysteresis = 1. In other words, do not compress until the -// branchs CURRENT population fits in the leaf, even BEFORE deleting one -// index. -// -// Next is a label for branch-type-specific common code. Variables pop1, -// level, digit, and Index are in the context. - -#define JU_BRANCH_KEEP(cLevel,MaxPop1,Next) \ - if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \ - { \ - assert((cLevel) >= 2); \ - level = (cLevel); \ - digit = JU_DIGITATSTATE(Index, cLevel); \ - goto Next; \ - } - -// Support for generic calling of JudyLeaf*ToLeaf*() functions: -// -// Note: Cannot use JUDYLCODE() because this contains a comma. - -#ifdef JUDY1 -#define JU_PVALUEPASS // null. -#else -#define JU_PVALUEPASS Pjv, -#endif - -// During compression to a leaf, check if a JP contains nothing but a -// cJU_JPIMMED_*_01, in which case shortcut calling j__udyLeaf*ToLeaf*(): -// -// Copy the index bytes from the jp_DcdPopO field (with possible truncation), -// and continue the branch-JP-walk loop. Variables Pjp and Pleaf are in the -// context. - -#define JU_BRANCH_COPY_IMMED_EVEN(cLevel,Pjp,ignore) \ - if (JU_JPTYPE(Pjp) == cJU_JPIMMED_1_01 + (cLevel) - 2) \ - { \ - *Pleaf++ = JU_JPDCDPOP0(Pjp); \ - JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \ - continue; /* for-loop */ \ - } - -#define JU_BRANCH_COPY_IMMED_ODD(cLevel,Pjp,CopyIndex) \ - if (JU_JPTYPE(Pjp) == cJU_JPIMMED_1_01 + (cLevel) - 2) \ - { \ - CopyIndex(Pleaf, (Word_t) (JU_JPDCDPOP0(Pjp))); \ - Pleaf += (cLevel); /* index size = level */ \ - JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \ - continue; /* for-loop */ \ - } - -// Compress a BranchL into a leaf one index size larger: -// -// Allocate a new leaf, walk the JPs in the old BranchL and pack their contents -// into the new leaf (of type NewJPType), free the old BranchL, and finally -// restart the switch to delete Index from the new leaf. (Note that all -// BranchLs are the same size.) Variables Pjp, Pjpm, Pleaf, digit, and pop1 -// are in the context. - -#define JU_BRANCHL_COMPRESS(cLevel,LeafType,MaxPop1,NewJPType, \ - LeafToLeaf,Alloc,ValueArea, \ - CopyImmed,CopyIndex) \ - { \ - LeafType Pleaf; \ - Pjbl_t PjblRaw; \ - Pjbl_t Pjbl; \ - Word_t numJPs; \ - \ - if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \ - Pjllnew = P_JLL(PjllnewRaw); \ - Pleaf = (LeafType) Pjllnew; \ - JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \ - \ - PjblRaw = (Pjbl_t) (Pjp->jp_Addr); \ - Pjbl = P_JBL(PjblRaw); \ - numJPs = Pjbl->jbl_NumJPs; \ - \ - for (offset = 0; offset < numJPs; ++offset) \ - { \ - CopyImmed(cLevel, (Pjbl->jbl_jp) + offset, CopyIndex); \ - \ - pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS \ - (Pjbl->jbl_jp) + offset, \ - JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset], \ - cLevel), (Pvoid_t) Pjpm); \ - Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \ - JUDYLCODE(Pjv += pop1;) \ - } \ - assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \ - JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \ - DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \ - \ - j__udyFreeJBL(PjblRaw, Pjpm); \ - \ - Pjp->jp_Type = (NewJPType); \ - Pjp->jp_Addr = (Word_t) PjllnewRaw; \ - goto ContinueDelWalk; /* delete from new leaf */ \ - } - -// Overall common code for initial BranchL deletion handling: -// -// Assert that Index is in the branch, then see if the BranchL should be kept -// or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the -// context. - -#define JU_BRANCHL(cLevel,MaxPop1,LeafType,NewJPType, \ - LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \ - \ - assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \ - assert(ParentLevel > (cLevel)); \ - \ - pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \ - JU_BRANCH_KEEP(cLevel, MaxPop1, BranchLKeep); \ - assert(pop1 == (MaxPop1)); \ - \ - JU_BRANCHL_COMPRESS(cLevel, LeafType, MaxPop1, NewJPType, \ - LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex) - - -// END OF MACROS, START OF CASES: - - case cJU_JPBRANCH_L2: - - JU_BRANCHL(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2, - j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA, - JU_BRANCH_COPY_IMMED_EVEN, ignore); - - case cJU_JPBRANCH_L3: - - JU_BRANCHL(3, cJU_LEAF3_MAXPOP1, uint8_t *, cJU_JPLEAF3, - j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX); - -#ifdef JU_64BIT - case cJU_JPBRANCH_L4: - - JU_BRANCHL(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4, - j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA, - JU_BRANCH_COPY_IMMED_EVEN, ignore); - - case cJU_JPBRANCH_L5: - - JU_BRANCHL(5, cJU_LEAF5_MAXPOP1, uint8_t *, cJU_JPLEAF5, - j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX); - - case cJU_JPBRANCH_L6: - - JU_BRANCHL(6, cJU_LEAF6_MAXPOP1, uint8_t *, cJU_JPLEAF6, - j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX); - - case cJU_JPBRANCH_L7: - - JU_BRANCHL(7, cJU_LEAF7_MAXPOP1, uint8_t *, cJU_JPLEAF7, - j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX); -#endif // JU_64BIT - -// A top-level BranchL is different and cannot use JU_BRANCHL(): Dont try to -// compress to a (LEAFW) leaf yet, but leave this for a later deletion -// (hysteresis > 0); and the next JP type depends on the system word size; so -// dont use JU_BRANCH_KEEP(): - - case cJU_JPBRANCH_L: - { - Pjbl_t Pjbl; - Word_t numJPs; - - level = cJU_ROOTSTATE; - digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE); - - // fall through: - - -// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHL: -// -// Come here with level and digit set. - -BranchLKeep: - Pjbl = P_JBL(Pjp->jp_Addr); - numJPs = Pjbl->jbl_NumJPs; - assert(numJPs > 0); - DBGCODE(parentJPtype = JU_JPTYPE(Pjp);) - -// Search for a match to the digit (valid Index => must find digit): - - for (offset = 0; (Pjbl->jbl_Expanse[offset]) != digit; ++offset) - assert(offset < numJPs - 1); - - Pjp = (Pjbl->jbl_jp) + offset; - -// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through -// the BranchL): - - assert(level >= 2); - if ((JU_JPTYPE(Pjp)) != cJU_JPIMMED_1_01 + level - 2) break; - -// At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the -// Immed from the BranchL: -// -// Note: A BranchL has a fixed size and format regardless of numJPs. - - assert(JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(Index)); - - JU_DELETEINPLACE(Pjbl->jbl_Expanse, numJPs, offset, ignore); - JU_DELETEINPLACE(Pjbl->jbl_jp, numJPs, offset, ignore); - - DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse), - numJPs - 1, 1);) - -// If only one index left in the BranchL, indicate this to the caller: - - return ((--(Pjbl->jbl_NumJPs) <= 1) ? 2 : 1); - - } // case cJU_JPBRANCH_L. - - -// **************************************************************************** -// BITMAP BRANCH: -// -// MACROS FOR COMMON CODE: -// -// Note the reuse of common macros here, defined earlier: JU_BRANCH_KEEP(), -// JU_PVALUE*. -// -// Compress a BranchB into a leaf one index size larger: -// -// Allocate a new leaf, walk the JPs in the old BranchB (one bitmap subexpanse -// at a time) and pack their contents into the new leaf (of type NewJPType), -// free the old BranchB, and finally restart the switch to delete Index from -// the new leaf. Variables Pjp, Pjpm, Pleaf, digit, and pop1 are in the -// context. -// -// Note: Its no accident that the interface to JU_BRANCHB_COMPRESS() is -// identical to JU_BRANCHL_COMPRESS(). Only the details differ in how to -// traverse the branchs JPs. - -#define JU_BRANCHB_COMPRESS(cLevel,LeafType,MaxPop1,NewJPType, \ - LeafToLeaf,Alloc,ValueArea, \ - CopyImmed,CopyIndex) \ - { \ - LeafType Pleaf; \ - Pjbb_t PjbbRaw; /* BranchB to compress */ \ - Pjbb_t Pjbb; \ - Word_t subexp; /* current subexpanse number */ \ - BITMAPB_t bitmap; /* portion for this subexpanse */ \ - Pjp_t Pjp2Raw; /* one subexpanses subarray */ \ - Pjp_t Pjp2; \ - \ - if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \ - Pjllnew = P_JLL(PjllnewRaw); \ - Pleaf = (LeafType) Pjllnew; \ - JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \ - \ - PjbbRaw = (Pjbb_t) (Pjp->jp_Addr); \ - Pjbb = P_JBB(PjbbRaw); \ - \ - for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) \ - { \ - if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0) \ - continue; /* empty subexpanse */ \ - \ - digit = subexp * cJU_BITSPERSUBEXPB; \ - Pjp2Raw = JU_JBB_PJP(Pjbb, subexp); \ - Pjp2 = P_JP(Pjp2Raw); \ - assert(Pjp2 != (Pjp_t) NULL); \ - \ - for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit) \ - { \ - if (! (bitmap & 1)) \ - continue; /* empty sub-subexpanse */ \ - \ - ++offset; /* before any continue */ \ - \ - CopyImmed(cLevel, Pjp2 + offset - 1, CopyIndex); \ - \ - pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS \ - Pjp2 + offset - 1, \ - JU_DIGITTOSTATE(digit, cLevel), \ - (Pvoid_t) Pjpm); \ - Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \ - JUDYLCODE(Pjv += pop1;) \ - } \ - j__udyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm); \ - } \ - assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \ - JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \ - DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \ - \ - j__udyFreeJBB(PjbbRaw, Pjpm); \ - \ - Pjp->jp_Type = (NewJPType); \ - Pjp->jp_Addr = (Word_t) PjllnewRaw; \ - goto ContinueDelWalk; /* delete from new leaf */ \ - } - -// Overall common code for initial BranchB deletion handling: -// -// Assert that Index is in the branch, then see if the BranchB should be kept -// or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the -// context. - -#define JU_BRANCHB(cLevel,MaxPop1,LeafType,NewJPType, \ - LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \ - \ - assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \ - assert(ParentLevel > (cLevel)); \ - \ - pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \ - JU_BRANCH_KEEP(cLevel, MaxPop1, BranchBKeep); \ - assert(pop1 == (MaxPop1)); \ - \ - JU_BRANCHB_COMPRESS(cLevel, LeafType, MaxPop1, NewJPType, \ - LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex) - - -// END OF MACROS, START OF CASES: -// -// Note: Its no accident that the macro calls for these cases is nearly -// identical to the code for BranchLs. - - case cJU_JPBRANCH_B2: - - JU_BRANCHB(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2, - j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA, - JU_BRANCH_COPY_IMMED_EVEN, ignore); - - case cJU_JPBRANCH_B3: - - JU_BRANCHB(3, cJU_LEAF3_MAXPOP1, uint8_t *, cJU_JPLEAF3, - j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX); - -#ifdef JU_64BIT - case cJU_JPBRANCH_B4: - - JU_BRANCHB(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4, - j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA, - JU_BRANCH_COPY_IMMED_EVEN, ignore); - - case cJU_JPBRANCH_B5: - - JU_BRANCHB(5, cJU_LEAF5_MAXPOP1, uint8_t *, cJU_JPLEAF5, - j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX); - - case cJU_JPBRANCH_B6: - - JU_BRANCHB(6, cJU_LEAF6_MAXPOP1, uint8_t *, cJU_JPLEAF6, - j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX); - - case cJU_JPBRANCH_B7: - - JU_BRANCHB(7, cJU_LEAF7_MAXPOP1, uint8_t *, cJU_JPLEAF7, - j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX); -#endif // JU_64BIT - -// A top-level BranchB is different and cannot use JU_BRANCHB(): Dont try to -// compress to a (LEAFW) leaf yet, but leave this for a later deletion -// (hysteresis > 0); and the next JP type depends on the system word size; so -// dont use JU_BRANCH_KEEP(): - - case cJU_JPBRANCH_B: - { - Pjbb_t Pjbb; // BranchB to modify. - Word_t subexp; // current subexpanse number. - Word_t subexp2; // in second-level loop. - BITMAPB_t bitmap; // portion for this subexpanse. - BITMAPB_t bitmask; // with digits bit set. - Pjp_t Pjp2Raw; // one subexpanses subarray. - Pjp_t Pjp2; - Word_t numJPs; // in one subexpanse. - - level = cJU_ROOTSTATE; - digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE); - - // fall through: - - -// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHB: -// -// Come here with level and digit set. - -BranchBKeep: - Pjbb = P_JBB(Pjp->jp_Addr); - subexp = digit / cJU_BITSPERSUBEXPB; - bitmap = JU_JBB_BITMAP(Pjbb, subexp); - bitmask = JU_BITPOSMASKB(digit); - assert(bitmap & bitmask); // Index valid => digits bit is set. - DBGCODE(parentJPtype = JU_JPTYPE(Pjp);) - -// Compute digits offset into the bitmap, with a fast method if all bits are -// set: - - offset = ((bitmap == (cJU_FULLBITMAPB)) ? - digit % cJU_BITSPERSUBEXPB : - j__udyCountBitsB(bitmap & JU_MASKLOWEREXC(bitmask))); - - Pjp2Raw = JU_JBB_PJP(Pjbb, subexp); - Pjp2 = P_JP(Pjp2Raw); - assert(Pjp2 != (Pjp_t) NULL); // valid subexpanse pointer. - -// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through -// the BranchB): - - if (JU_JPTYPE(Pjp2 + offset) != cJU_JPIMMED_1_01 + level - 2) - { - Pjp = Pjp2 + offset; - break; - } - -// At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the -// Immed from the BranchB: - - assert(JU_JPDCDPOP0(Pjp2 + offset) - == JU_TRIMTODCDSIZE(Index)); - -// If only one index is left in the subexpanse, free the JP array: - - if ((numJPs = j__udyCountBitsB(bitmap)) == 1) - { - j__udyFreeJBBJP(Pjp2Raw, /* pop1 = */ 1, Pjpm); - JU_JBB_PJP(Pjbb, subexp) = (Pjp_t) NULL; - } - -// Shrink JP array in-place: - - else if (JU_BRANCHBJPGROWINPLACE(numJPs - 1)) - { - assert(numJPs > 0); - JU_DELETEINPLACE(Pjp2, numJPs, offset, ignore); - } - -// JP array would end up too large; compress it to a smaller one: - - else - { - Pjp_t PjpnewRaw; - Pjp_t Pjpnew; - - if ((PjpnewRaw = j__udyAllocJBBJP(numJPs - 1, Pjpm)) - == (Pjp_t) NULL) return(-1); - Pjpnew = P_JP(PjpnewRaw); - - JU_DELETECOPY(Pjpnew, Pjp2, numJPs, offset, ignore); - j__udyFreeJBBJP(Pjp2Raw, numJPs, Pjpm); // old. - - JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw; - } - -// Clear digits bit in the bitmap: - - JU_JBB_BITMAP(Pjbb, subexp) ^= bitmask; - -// If the current subexpanse alone is still too large for a BranchL (with -// hysteresis = 1), the delete is all done: - - if (numJPs > cJU_BRANCHLMAXJPS) return(1); - -// Consider shrinking the current BranchB to a BranchL: -// -// Check the numbers of JPs in other subexpanses in the BranchL. Upon reaching -// the critical number of numJPs (which could be right at the start; again, -// with hysteresis = 1), its faster to just watch for any non-empty subexpanse -// than to count bits in each subexpanse. Upon finding too many JPs, give up -// on shrinking the BranchB. - - for (subexp2 = 0; subexp2 < cJU_NUMSUBEXPB; ++subexp2) - { - if (subexp2 == subexp) continue; // skip current subexpanse. - - if ((numJPs == cJU_BRANCHLMAXJPS) ? - JU_JBB_BITMAP(Pjbb, subexp2) : - ((numJPs += j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp2))) - > cJU_BRANCHLMAXJPS)) - { - return(1); // too many JPs, cannot shrink. - } - } - -// Shrink current BranchB to a BranchL: -// -// Note: In this rare case, ignore the return value, do not pass it to the -// caller, because the deletion is already successfully completed and the -// caller(s) must decrement population counts. The only errors expected from -// this call are JU_ERRNO_NOMEM and JU_ERRNO_OVERRUN, neither of which is worth -// forwarding from this point. See also 4.1, 4.8, and 4.15 of this file. - - (void) j__udyBranchBToBranchL(Pjp, Pjpm); - return(1); - - } // case. - - -// **************************************************************************** -// UNCOMPRESSED BRANCH: -// -// MACROS FOR COMMON CODE: -// -// Note the reuse of common macros here, defined earlier: JU_PVALUE*. -// -// Compress a BranchU into a leaf one index size larger: -// -// Allocate a new leaf, walk the JPs in the old BranchU and pack their contents -// into the new leaf (of type NewJPType), free the old BranchU, and finally -// restart the switch to delete Index from the new leaf. Variables Pjp, Pjpm, -// digit, and pop1 are in the context. -// -// Note: Its no accident that the interface to JU_BRANCHU_COMPRESS() is -// nearly identical to JU_BRANCHL_COMPRESS(); just NullJPType is added. The -// details differ in how to traverse the branchs JPs -- -// -// -- and also, what to do upon encountering a cJU_JPIMMED_*_01 JP. In -// BranchLs and BranchBs the JP must be deleted, but in a BranchU its merely -// converted to a null JP, and this is done by other switch cases, so the "keep -// branch" situation is simpler here and JU_BRANCH_KEEP() is not used. Also, -// theres no code to convert a BranchU to a BranchB since counting the JPs in -// a BranchU is (at least presently) expensive, and besides, keeping around a -// BranchU is form of hysteresis. - -#define JU_BRANCHU_COMPRESS(cLevel,LeafType,MaxPop1,NullJPType,NewJPType, \ - LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \ - { \ - LeafType Pleaf; \ - Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr); \ - Pjp_t Pjp2 = JU_JBU_PJP0(Pjp); \ - Word_t ldigit; /* larger than uint8_t */ \ - \ - if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \ - Pjllnew = P_JLL(PjllnewRaw); \ - Pleaf = (LeafType) Pjllnew; \ - JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \ - \ - for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit, ++Pjp2) \ - { \ - /* fast-process common types: */ \ - if (JU_JPTYPE(Pjp2) == (NullJPType)) continue; \ - CopyImmed(cLevel, Pjp2, CopyIndex); \ - \ - pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS Pjp2, \ - JU_DIGITTOSTATE(ldigit, cLevel), \ - (Pvoid_t) Pjpm); \ - Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \ - JUDYLCODE(Pjv += pop1;) \ - } \ - assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \ - JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \ - DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \ - \ - j__udyFreeJBU(PjbuRaw, Pjpm); \ - \ - Pjp->jp_Type = (NewJPType); \ - Pjp->jp_Addr = (Word_t) PjllnewRaw; \ - goto ContinueDelWalk; /* delete from new leaf */ \ - } - -// Overall common code for initial BranchU deletion handling: -// -// Assert that Index is in the branch, then see if a BranchU should be kept or -// else compressed to a leaf. Variables level, Index, Pjp, and pop1 are in the -// context. -// -// Note: BranchU handling differs from BranchL and BranchB as described above. - -#define JU_BRANCHU(cLevel,MaxPop1,LeafType,NullJPType,NewJPType, \ - LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \ - \ - assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \ - assert(ParentLevel > (cLevel)); \ - DBGCODE(parentJPtype = JU_JPTYPE(Pjp);) \ - \ - pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \ - \ - if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \ - { \ - level = (cLevel); \ - Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cLevel);\ - break; /* descend to next level */ \ - } \ - assert(pop1 == (MaxPop1)); \ - \ - JU_BRANCHU_COMPRESS(cLevel, LeafType, MaxPop1, NullJPType, NewJPType, \ - LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex) - - -// END OF MACROS, START OF CASES: -// -// Note: Its no accident that the macro calls for these cases is nearly -// identical to the code for BranchLs, with the addition of cJU_JPNULL* -// parameters only needed for BranchUs. - - case cJU_JPBRANCH_U2: - - JU_BRANCHU(2, cJU_LEAF2_MAXPOP1, uint16_t *, - cJU_JPNULL1, cJU_JPLEAF2, - j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA, - JU_BRANCH_COPY_IMMED_EVEN, ignore); - - case cJU_JPBRANCH_U3: - - JU_BRANCHU(3, cJU_LEAF3_MAXPOP1, uint8_t *, - cJU_JPNULL2, cJU_JPLEAF3, - j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX); - -#ifdef JU_64BIT - case cJU_JPBRANCH_U4: - - JU_BRANCHU(4, cJU_LEAF4_MAXPOP1, uint32_t *, - cJU_JPNULL3, cJU_JPLEAF4, - j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA, - JU_BRANCH_COPY_IMMED_EVEN, ignore); - - case cJU_JPBRANCH_U5: - - JU_BRANCHU(5, cJU_LEAF5_MAXPOP1, uint8_t *, - cJU_JPNULL4, cJU_JPLEAF5, - j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX); - - case cJU_JPBRANCH_U6: - - JU_BRANCHU(6, cJU_LEAF6_MAXPOP1, uint8_t *, - cJU_JPNULL5, cJU_JPLEAF6, - j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX); - - case cJU_JPBRANCH_U7: - - JU_BRANCHU(7, cJU_LEAF7_MAXPOP1, uint8_t *, - cJU_JPNULL6, cJU_JPLEAF7, - j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA, - JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX); -#endif // JU_64BIT - -// A top-level BranchU is different and cannot use JU_BRANCHU(): Dont try to -// compress to a (LEAFW) leaf yet, but leave this for a later deletion -// (hysteresis > 0); just descend through the BranchU: - - case cJU_JPBRANCH_U: - - DBGCODE(parentJPtype = JU_JPTYPE(Pjp);) - - level = cJU_ROOTSTATE; - Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cJU_ROOTSTATE); - break; - - -// **************************************************************************** -// LINEAR LEAF: -// -// State transitions while deleting an Index, the inverse of the similar table -// that appears in JudyIns.c: -// -// Note: In JudyIns.c this table is not needed and does not appear until the -// Immed handling code; because once a Leaf is reached upon growing the tree, -// the situation remains simpler, but for deleting indexes, the complexity -// arises when leaves must compress to Immeds. -// -// Note: There are other transitions possible too, not shown here, such as to -// a leaf one level higher. -// -// (Yes, this is very terse... Study it and it will make sense.) -// (Note, parts of this diagram are repeated below for quick reference.) -// -// reformat JP here for Judy1 only, from word-1 to word-2 -// | -// JUDY1 && JU_64BIT JUDY1 || JU_64BIT | -// V -// (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01 -// Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01 -// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01 -// JU_64BIT only: -// Leaf4 [[ => 4_03..02 ]] => 4_01 -// Leaf5 [[ => 5_03..02 ]] => 5_01 -// Leaf6 [[ => 6_02 ]] => 6_01 -// Leaf7 [[ => 7_02 ]] => 7_01 -// -// (*) For Judy1 & 64-bit, go directly from a LeafB1 to cJU_JPIMMED_1_15; skip -// Leaf1, as described in Judy1.h regarding cJ1_JPLEAF1. -// -// MACROS FOR COMMON CODE: -// -// (De)compress a LeafX into a LeafY one index size (cIS) larger (X+1 = Y): -// -// This is only possible when the current leaf is under a narrow pointer -// ((ParentLevel - 1) > cIS) and its population fits in a higher-level leaf. -// Variables ParentLevel, pop1, PjllnewRaw, Pjllnew, Pjpm, and Index are in the -// context. -// -// Note: Doing an "uplevel" doesnt occur until the old leaf can be compressed -// up one level BEFORE deleting an index; that is, hysteresis = 1. -// -// Note: LeafType, MaxPop1, NewJPType, and Alloc refer to the up-level leaf, -// not the current leaf. -// -// Note: 010327: Fixed bug where the jp_DcdPopO next-uplevel digit (byte) -// above the current Pop0 value was not being cleared. When upleveling, one -// digit in jp_DcdPopO "moves" from being part of the Dcd subfield to the Pop0 -// subfield, but since a leaf maxpop1 is known to be <= 1 byte in size, the new -// Pop0 byte should always be zero. This is easy to overlook because -// JU_JPLEAF_POP0() "knows" to only use the LSB of Pop0 (for efficiency) and -// ignore the other bytes... Until someone uses cJU_POP0MASK() instead of -// JU_JPLEAF_POP0(), such as in JudyInsertBranch.c. -// -// TBD: Should JudyInsertBranch.c use JU_JPLEAF_POP0() rather than -// cJU_POP0MASK(), for efficiency? Does it know for sure its a narrow pointer -// under the leaf? Not necessarily. - -#define JU_LEAF_UPLEVEL(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \ - Alloc,ValueArea) \ - \ - assert(((ParentLevel - 1) == (cIS)) || (pop1 >= (MaxPop1))); \ - \ - if (((ParentLevel - 1) > (cIS)) /* under narrow pointer */ \ - && (pop1 == (MaxPop1))) /* hysteresis = 1 */ \ - { \ - Word_t D_cdP0; \ - if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \ - Pjllnew = P_JLL(PjllnewRaw); \ - JUDYLCODE(Pjv = ValueArea((LeafType) Pjllnew, MaxPop1);) \ - \ - (void) LeafToLeaf((LeafType) Pjllnew, JU_PVALUEPASS Pjp, \ - Index & cJU_DCDMASK(cIS), /* TBD, Doug says */ \ - (Pvoid_t) Pjpm); \ - DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cIS + 1);) \ - \ - D_cdP0 = (~cJU_MASKATSTATE((cIS) + 1)) & JU_JPDCDPOP0(Pjp); \ - JU_JPSETADT(Pjp, (Word_t)PjllnewRaw, D_cdP0, NewJPType); \ - goto ContinueDelWalk; /* delete from new leaf */ \ - } - - -// For Leaf3, only support JU_LEAF_UPLEVEL on a 64-bit system, and for Leaf7, -// there is no JU_LEAF_UPLEVEL: -// -// Note: Theres no way here to go from Leaf3 [Leaf7] to LEAFW on a 32-bit -// [64-bit] system. Thats handled in the main code, because its different in -// that a JPM is involved. - -#ifndef JU_64BIT // 32-bit. -#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \ - Alloc,ValueArea) // null. -#else -#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \ - Alloc,ValueArea) \ - JU_LEAF_UPLEVEL (cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \ - Alloc,ValueArea) -#define JU_LEAF_UPLEVEL_NONE(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \ - Alloc,ValueArea) // null. -#endif - -// Compress a Leaf* with pop1 = 2, or a JPIMMED_*_02, into a JPIMMED_*_01: -// -// Copy whichever Index is NOT being deleted (and assert that the other one is -// found; Index must be valid). This requires special handling of the Index -// bytes (and value area). Variables Pjp, Index, offset, and Pleaf are in the -// context, offset is modified to the undeleted Index, and Pjp is modified -// including jp_Addr. - - -#define JU_TOIMMED_01_EVEN(cIS,ignore1,ignore2) \ -{ \ - Word_t D_cdP0; \ - Word_t A_ddr = 0; \ - uint8_t T_ype = JU_JPTYPE(Pjp); \ - offset = (Pleaf[0] == JU_LEASTBYTES(Index, cIS)); /* undeleted Ind */ \ - assert(Pleaf[offset ? 0 : 1] == JU_LEASTBYTES(Index, cIS)); \ - D_cdP0 = (Index & cJU_DCDMASK(cIS)) | Pleaf[offset]; \ -JUDYLCODE(A_ddr = Pjv[offset];) \ - JU_JPSETADT(Pjp, A_ddr, D_cdP0, T_ype); \ -} - -#define JU_TOIMMED_01_ODD(cIS,SearchLeaf,CopyPIndex) \ - { \ - Word_t D_cdP0; \ - Word_t A_ddr = 0; \ - uint8_t T_ype = JU_JPTYPE(Pjp); \ - \ - offset = SearchLeaf(Pleaf, 2, Index); \ - assert(offset >= 0); /* Index must be valid */ \ - CopyPIndex(D_cdP0, & (Pleaf[offset ? 0 : cIS])); \ - D_cdP0 |= Index & cJU_DCDMASK(cIS); \ - JUDYLCODE(A_ddr = Pjv[offset ? 0 : 1];) \ - JU_JPSETADT(Pjp, A_ddr, D_cdP0, T_ype); \ - } - - -// Compress a Leaf* into a JPIMMED_*_0[2+]: -// -// This occurs as soon as its possible, with hysteresis = 0. Variables pop1, -// Pleaf, offset, and Pjpm are in the context. -// -// TBD: Explain why hysteresis = 0 here, rather than > 0. Probably because -// the insert code assumes if the population is small enough, an Immed is used, -// not a leaf. -// -// The differences between Judy1 and JudyL with respect to value area handling -// are just too large for completely common code between them... Oh well, some -// big ifdefs follow. - -#ifdef JUDY1 - -#define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\ - ignore2,ignore3,ignore4, \ - DeleteCopy,FreeLeaf) \ - \ - assert(pop1 > (MaxPop1)); \ - \ - if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \ - { \ - Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \ - DeleteCopy((LeafType) (Pjp->jp_1Index), Pleaf, pop1, offset, cIS); \ - DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index), pop1-1, cIS);) \ - Pjp->jp_Type = (BaseJPType) - 1 + (MaxPop1) - 1; \ - FreeLeaf(PjllRaw, pop1, Pjpm); \ - return(1); \ - } - -#else // JUDYL - -// Pjv is also in the context. - -#define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\ - ignore2,ignore3,ignore4, \ - DeleteCopy,FreeLeaf) \ - \ - assert(pop1 > (MaxPop1)); \ - \ - if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \ - { \ - Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \ - Pjv_t PjvnewRaw; \ - Pjv_t Pjvnew; \ - \ - if ((PjvnewRaw = j__udyLAllocJV(pop1 - 1, Pjpm)) \ - == (Pjv_t) NULL) return(-1); \ - JUDYLCODE(Pjvnew = P_JV(PjvnewRaw);) \ - \ - DeleteCopy((LeafType) (Pjp->jp_LIndex), Pleaf, pop1, offset, cIS); \ - JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \ - DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_LIndex), pop1-1, cIS);) \ - FreeLeaf(PjllRaw, pop1, Pjpm); \ - Pjp->jp_Addr = (Word_t) PjvnewRaw; \ - Pjp->jp_Type = (BaseJPType) - 2 + (MaxPop1); \ - return(1); \ - } - -// A complicating factor for JudyL & 32-bit is that Leaf2..3, and for JudyL & -// 64-bit Leaf 4..7, go directly to an Immed*_01, where the value is stored in -// jp_Addr and not in a separate LeafV. For efficiency, use the following -// macro in cases where it can apply; it is rigged to do the right thing. -// Unfortunately, this requires the calling code to "know" the transition table -// and call the right macro. -// -// This variant compresses a Leaf* with pop1 = 2 into a JPIMMED_*_01: - -#define JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) \ - \ - assert(pop1 > (MaxPop1)); \ - \ - if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \ - { \ - Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \ - ToImmed(cIS, SearchLeaf, CopyPIndex); \ - FreeLeaf(PjllRaw, pop1, Pjpm); \ - Pjp->jp_Type = (Immed01JPType); \ - return(1); \ - } -#endif // JUDYL - -// See comments above about these: -// -// Note: Here "23" means index size 2 or 3, and "47" means 4..7. - -#if (defined(JUDY1) || defined(JU_64BIT)) -#define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) \ - JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \ - ignore2,ignore3,ignore4, \ - DeleteCopy,FreeLeaf) -#else // JUDYL && 32-bit -#define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) \ - JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) -#endif - -#ifdef JU_64BIT -#ifdef JUDY1 -#define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) \ - JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \ - ignore2,ignore3,ignore4, \ - DeleteCopy,FreeLeaf) -#else // JUDYL && 64-bit -#define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) \ - JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \ - ToImmed,SearchLeaf,CopyPIndex, \ - DeleteCopy,FreeLeaf) -#endif // JUDYL -#endif // JU_64BIT - -// Compress a Leaf* in place: -// -// Here hysteresis = 0 (no memory is wasted). Variables pop1, Pleaf, and -// offset, and for JudyL, Pjv, are in the context. - -#ifdef JUDY1 -#define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \ - if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \ - { \ - DeleteInPlace(Pleaf, pop1, offset, cIS); \ - DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \ - return(1); \ - } -#else -#define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \ - if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \ - { \ - DeleteInPlace(Pleaf, pop1, offset, cIS); \ -/**/ JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \ - DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \ - return(1); \ - } -#endif - -// Compress a Leaf* into a smaller memory object of the same JP type: -// -// Variables PjllnewRaw, Pjllnew, Pleafpop1, Pjpm, PleafRaw, Pleaf, and offset -// are in the context. - -#ifdef JUDY1 - -#define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \ - if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \ - Pjllnew = P_JLL(PjllnewRaw); \ - DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \ - DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \ - FreeLeaf(PleafRaw, pop1, Pjpm); \ - Pjp->jp_Addr = (Word_t) PjllnewRaw; \ - return(1) - -#else // JUDYL - -#define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \ - { \ -/**/ Pjv_t Pjvnew; \ - \ - if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \ - Pjllnew = P_JLL(PjllnewRaw); \ -/**/ Pjvnew = ValueArea(Pjllnew, pop1 - 1); \ - DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \ -/**/ JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \ - DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \ - FreeLeaf(PleafRaw, pop1, Pjpm); \ - Pjp->jp_Addr = (Word_t) PjllnewRaw; \ - return(1); \ - } -#endif // JUDYL - -// Overall common code for Leaf* deletion handling: -// -// See if the leaf can be: -// - (de)compressed to one a level higher (JU_LEAF_UPLEVEL()), or if not, -// - compressed to an Immediate JP (JU_LEAF_TOIMMED()), or if not, -// - shrunk in place (JU_LEAF_INPLACE()), or if none of those, then -// - shrink the leaf to a smaller chunk of memory (JU_LEAF_SHRINK()). -// -// Variables Pjp, pop1, Index, and offset are in the context. -// The *Up parameters refer to a leaf one level up, if there is any. - -#define JU_LEAF(cIS, \ - UpLevel, \ - LeafTypeUp,MaxPop1Up,LeafJPTypeUp,LeafToLeaf, \ - AllocUp,ValueAreaUp, \ - LeafToImmed,ToImmed,CopyPIndex, \ - LeafType,ImmedMaxPop1,ImmedBaseJPType,Immed01JPType, \ - SearchLeaf,GrowInPlace,DeleteInPlace,DeleteCopy, \ - Alloc,FreeLeaf,ValueArea) \ - { \ - Pjll_t PleafRaw; \ - LeafType Pleaf; \ - \ - assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cIS)); \ - assert(ParentLevel > (cIS)); \ - \ - PleafRaw = (Pjll_t) (Pjp->jp_Addr); \ - Pleaf = (LeafType) P_JLL(PleafRaw); \ - pop1 = JU_JPLEAF_POP0(Pjp) + 1; \ - \ - UpLevel(cIS, LeafTypeUp, MaxPop1Up, LeafJPTypeUp, \ - LeafToLeaf, AllocUp, ValueAreaUp); \ - \ - offset = SearchLeaf(Pleaf, pop1, Index); \ - assert(offset >= 0); /* Index must be valid */ \ - JUDYLCODE(Pjv = ValueArea(Pleaf, pop1);) \ - \ - LeafToImmed(cIS, LeafType, ImmedMaxPop1, \ - ImmedBaseJPType, Immed01JPType, \ - ToImmed, SearchLeaf, CopyPIndex, \ - DeleteCopy, FreeLeaf); \ - \ - JU_LEAF_INPLACE(cIS, GrowInPlace, DeleteInPlace); \ - \ - JU_LEAF_SHRINK(cIS, LeafType, DeleteCopy, Alloc, FreeLeaf, \ - ValueArea); \ - } - -// END OF MACROS, START OF CASES: -// -// (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01 - -#if (defined(JUDYL) || (! defined(JU_64BIT))) - case cJU_JPLEAF1: - - JU_LEAF(1, - JU_LEAF_UPLEVEL, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2, - j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA, - JU_LEAF_TOIMMED, ignore, ignore, - uint8_t *, cJU_IMMED1_MAXPOP1, - cJU_JPIMMED_1_02, cJU_JPIMMED_1_01, j__udySearchLeaf1, - JU_LEAF1GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY, - j__udyAllocJLL1, j__udyFreeJLL1, JL_LEAF1VALUEAREA); -#endif - -// A complicating factor is that for JudyL & 32-bit, a Leaf2 must go directly -// to an Immed 2_01 and a Leaf3 must go directly to an Immed 3_01: -// -// Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01 -// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01 -// -// Hence use JU_LEAF_TOIMMED_23 instead of JU_LEAF_TOIMMED in the cases below, -// and also the parameters ToImmed and, for odd index sizes, CopyPIndex, are -// required. - - case cJU_JPLEAF2: - - JU_LEAF(2, - JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF3_MAXPOP1, cJU_JPLEAF3, - j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA, - JU_LEAF_TOIMMED_23, JU_TOIMMED_01_EVEN, ignore, - uint16_t *, cJU_IMMED2_MAXPOP1, - cJU_JPIMMED_2_02, cJU_JPIMMED_2_01, j__udySearchLeaf2, - JU_LEAF2GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY, - j__udyAllocJLL2, j__udyFreeJLL2, JL_LEAF2VALUEAREA); - -// On 32-bit there is no transition to "uplevel" for a Leaf3, so use -// JU_LEAF_UPLEVEL64 instead of JU_LEAF_UPLEVEL: - - case cJU_JPLEAF3: - - JU_LEAF(3, - JU_LEAF_UPLEVEL64, uint32_t *, cJU_LEAF4_MAXPOP1, - cJU_JPLEAF4, - j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA, - JU_LEAF_TOIMMED_23, - JU_TOIMMED_01_ODD, JU_COPY3_PINDEX_TO_LONG, - uint8_t *, cJU_IMMED3_MAXPOP1, - cJU_JPIMMED_3_02, cJU_JPIMMED_3_01, j__udySearchLeaf3, - JU_LEAF3GROWINPLACE, JU_DELETEINPLACE_ODD, - JU_DELETECOPY_ODD, - j__udyAllocJLL3, j__udyFreeJLL3, JL_LEAF3VALUEAREA); - -#ifdef JU_64BIT - -// A complicating factor is that for JudyL & 64-bit, a Leaf[4-7] must go -// directly to an Immed [4-7]_01: -// -// Leaf4 [[ => 4_03..02 ]] => 4_01 -// Leaf5 [[ => 5_03..02 ]] => 5_01 -// Leaf6 [[ => 6_02 ]] => 6_01 -// Leaf7 [[ => 7_02 ]] => 7_01 -// -// Hence use JU_LEAF_TOIMMED_47 instead of JU_LEAF_TOIMMED in the cases below. - - case cJU_JPLEAF4: - - JU_LEAF(4, - JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF5_MAXPOP1, cJU_JPLEAF5, - j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA, - JU_LEAF_TOIMMED_47, JU_TOIMMED_01_EVEN, ignore, - uint32_t *, cJU_IMMED4_MAXPOP1, - cJ1_JPIMMED_4_02, cJU_JPIMMED_4_01, j__udySearchLeaf4, - JU_LEAF4GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY, - j__udyAllocJLL4, j__udyFreeJLL4, JL_LEAF4VALUEAREA); - - case cJU_JPLEAF5: - - JU_LEAF(5, - JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF6_MAXPOP1, cJU_JPLEAF6, - j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA, - JU_LEAF_TOIMMED_47, - JU_TOIMMED_01_ODD, JU_COPY5_PINDEX_TO_LONG, - uint8_t *, cJU_IMMED5_MAXPOP1, - cJ1_JPIMMED_5_02, cJU_JPIMMED_5_01, j__udySearchLeaf5, - JU_LEAF5GROWINPLACE, JU_DELETEINPLACE_ODD, - JU_DELETECOPY_ODD, - j__udyAllocJLL5, j__udyFreeJLL5, JL_LEAF5VALUEAREA); - - case cJU_JPLEAF6: - - JU_LEAF(6, - JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF7_MAXPOP1, cJU_JPLEAF7, - j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA, - JU_LEAF_TOIMMED_47, - JU_TOIMMED_01_ODD, JU_COPY6_PINDEX_TO_LONG, - uint8_t *, cJU_IMMED6_MAXPOP1, - cJ1_JPIMMED_6_02, cJU_JPIMMED_6_01, j__udySearchLeaf6, - JU_LEAF6GROWINPLACE, JU_DELETEINPLACE_ODD, - JU_DELETECOPY_ODD, - j__udyAllocJLL6, j__udyFreeJLL6, JL_LEAF6VALUEAREA); - -// There is no transition to "uplevel" for a Leaf7, so use JU_LEAF_UPLEVEL_NONE -// instead of JU_LEAF_UPLEVEL, and ignore all of the parameters to that macro: - - case cJU_JPLEAF7: - - JU_LEAF(7, - JU_LEAF_UPLEVEL_NONE, ignore1, ignore2, ignore3, ignore4, - ignore5, ignore6, - JU_LEAF_TOIMMED_47, - JU_TOIMMED_01_ODD, JU_COPY7_PINDEX_TO_LONG, - uint8_t *, cJU_IMMED7_MAXPOP1, - cJ1_JPIMMED_7_02, cJU_JPIMMED_7_01, j__udySearchLeaf7, - JU_LEAF7GROWINPLACE, JU_DELETEINPLACE_ODD, - JU_DELETECOPY_ODD, - j__udyAllocJLL7, j__udyFreeJLL7, JL_LEAF7VALUEAREA); -#endif // JU_64BIT - - -// **************************************************************************** -// BITMAP LEAF: - - case cJU_JPLEAF_B1: - { -#ifdef JUDYL - Pjv_t PjvnewRaw; // new value area. - Pjv_t Pjvnew; - Word_t subexp; // 1 of 8 subexpanses in bitmap. - Pjlb_t Pjlb; // pointer to bitmap part of the leaf. - BITMAPL_t bitmap; // for one subexpanse. - BITMAPL_t bitmask; // bit set for Indexs digit. -#endif - assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, 1)); - assert(ParentLevel > 1); - // valid Index: - assert(JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index)); - - pop1 = JU_JPLEAF_POP0(Pjp) + 1; - -// Like a Leaf1, see if its under a narrow pointer and can become a Leaf2 -// (hysteresis = 1): - - JU_LEAF_UPLEVEL(1, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2, - j__udyLeaf1ToLeaf2, j__udyAllocJLL2, - JL_LEAF2VALUEAREA); - -#if (defined(JUDY1) && defined(JU_64BIT)) - -// Handle the unusual special case, on Judy1 64-bit only, where a LeafB1 goes -// directly to a JPIMMED_1_15; as described in comments in Judy1.h and -// JudyIns.c. Copy 1-byte indexes from old LeafB1 to the Immed: - - if ((pop1 - 1) == cJU_IMMED1_MAXPOP1) // hysteresis = 0. - { - Pjlb_t PjlbRaw; // bitmap in old leaf. - Pjlb_t Pjlb; - uint8_t * Pleafnew; // JPIMMED as a pointer. - Word_t ldigit; // larger than uint8_t. - - PjlbRaw = (Pjlb_t) (Pjp->jp_Addr); - Pjlb = P_JLB(PjlbRaw); - Pleafnew = Pjp->jp_1Index; - - JU_BITMAPCLEARL(Pjlb, Index); // unset Indexs bit. - -// TBD: This is very slow, there must be a better way: - - for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit) - { - if (JU_BITMAPTESTL(Pjlb, ldigit)) - { - *Pleafnew++ = ldigit; - assert(Pleafnew - (Pjp->jp_1Index) - <= cJU_IMMED1_MAXPOP1); - } - } - - DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index), - cJU_IMMED1_MAXPOP1, 1);) - j__udyFreeJLB1(PjlbRaw, Pjpm); - - Pjp->jp_Type = cJ1_JPIMMED_1_15; - return(1); - } - -#else // (JUDYL || (! JU_64BIT)) - -// Compress LeafB1 to a Leaf1: -// -// Note: 4.37 of this file contained alternate code for Judy1 only that simply -// cleared the bit and allowed the LeafB1 to go below cJU_LEAF1_MAXPOP1. This -// was the ONLY case where a malloc failure was not fatal; however, it violated -// the critical assumption that the tree is always kept in least-compressed -// form. - - if (pop1 == cJU_LEAF1_MAXPOP1) // hysteresis = 1. - { - if (j__udyLeafB1ToLeaf1(Pjp, Pjpm) == -1) return(-1); - goto ContinueDelWalk; // delete Index in new Leaf1. - } -#endif // (JUDYL || (! JU_64BIT)) - -#ifdef JUDY1 - // unset Indexs bit: - - JU_BITMAPCLEARL(P_JLB(Pjp->jp_Addr), Index); -#else // JUDYL - -// This is very different from Judy1 because of the need to manage the value -// area: -// -// Get last byte to decode from Index, and pointer to bitmap leaf: - - digit = JU_DIGITATSTATE(Index, 1); - Pjlb = P_JLB(Pjp->jp_Addr); - -// Prepare additional values: - - subexp = digit / cJU_BITSPERSUBEXPL; // which subexpanse. - bitmap = JU_JLB_BITMAP(Pjlb, subexp); // subexps 32-bit map. - PjvRaw = JL_JLB_PVALUE(Pjlb, subexp); // corresponding values. - Pjv = P_JV(PjvRaw); - bitmask = JU_BITPOSMASKL(digit); // mask for Index. - - assert(bitmap & bitmask); // Index must be valid. - - if (bitmap == cJU_FULLBITMAPL) // full bitmap, take shortcut: - { - pop1 = cJU_BITSPERSUBEXPL; - offset = digit % cJU_BITSPERSUBEXPL; - } - else // compute subexpanse pop1 and value area offset: - { - pop1 = j__udyCountBitsL(bitmap); - offset = j__udyCountBitsL(bitmap & (bitmask - 1)); - } - -// Handle solitary Index remaining in subexpanse: - - if (pop1 == 1) - { - j__udyLFreeJV(PjvRaw, 1, Pjpm); - - JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) NULL; - JU_JLB_BITMAP(Pjlb, subexp) = 0; - - return(1); - } - -// Shrink value area in place or move to a smaller value area: - - if (JL_LEAFVGROWINPLACE(pop1 - 1)) // hysteresis = 0. - { - JU_DELETEINPLACE(Pjv, pop1, offset, ignore); - } - else - { - if ((PjvnewRaw = j__udyLAllocJV(pop1 - 1, Pjpm)) - == (Pjv_t) NULL) return(-1); - Pjvnew = P_JV(PjvnewRaw); - - JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore); - j__udyLFreeJV(PjvRaw, pop1, Pjpm); - JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) PjvnewRaw; - } - - JU_JLB_BITMAP(Pjlb, subexp) ^= bitmask; // clear Indexs bit. - -#endif // JUDYL - - return(1); - - } // case. - - -#ifdef JUDY1 - -// **************************************************************************** -// FULL POPULATION LEAF: -// -// Convert to a LeafB1 and delete the index. Hysteresis = 0; none is possible. -// -// Note: Earlier the second assertion below said, "== 2", but in fact the -// parent could be at a higher level if a fullpop is under a narrow pointer. - - case cJ1_JPFULLPOPU1: - { - Pjlb_t PjlbRaw; - Pjlb_t Pjlb; - Word_t subexp; - - assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, 2)); - assert(ParentLevel > 1); // see above. - - if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL) - return(-1); - Pjlb = P_JLB(PjlbRaw); - -// Fully populate the leaf, then unset Indexs bit: - - for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp) - JU_JLB_BITMAP(Pjlb, subexp) = cJU_FULLBITMAPL; - - JU_BITMAPCLEARL(Pjlb, Index); - - Pjp->jp_Addr = (Word_t) PjlbRaw; - Pjp->jp_Type = cJU_JPLEAF_B1; - - return(1); - } -#endif // JUDY1 - - -// **************************************************************************** -// IMMEDIATE JP: -// -// If theres just the one Index in the Immed, convert the JP to a JPNULL* -// (should only happen in a BranchU); otherwise delete the Index from the -// Immed. See the state transitions table elsewhere in this file for a summary -// of which Immed types must be handled. Hysteresis = 0; none is possible with -// Immeds. -// -// MACROS FOR COMMON CODE: -// -// Single Index remains in cJU_JPIMMED_*_01; convert JP to null: -// -// Variables Pjp and parentJPtype are in the context. -// -// Note: cJU_JPIMMED_*_01 should only be encountered in BranchUs, not in -// BranchLs or BranchBs (where its improper to merely modify the JP to be a -// null JP); that is, BranchL and BranchB code should have already handled -// any cJU_JPIMMED_*_01 by different means. - -#define JU_IMMED_01(NewJPType,ParentJPType) \ - \ - assert(parentJPtype == (ParentJPType)); \ - assert(JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(Index)); \ - JU_JPSETADT(Pjp, 0, 0, NewJPType); \ - return(1) - -// Convert cJ*_JPIMMED_*_02 to cJU_JPIMMED_*_01: -// -// Move the undeleted Index, whichever does not match the least bytes of Index, -// from undecoded-bytes-only (in jp_1Index or jp_LIndex as appropriate) to -// jp_DcdPopO (full-field). Pjp, Index, and offset are in the context. - -#define JU_IMMED_02(cIS,LeafType,NewJPType) \ - { \ - LeafType Pleaf; \ - \ - assert((ParentLevel - 1) == (cIS)); \ - JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \ - JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \ - JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \ - JUDYLCODE(Pjv = P_JV(PjvRaw);) \ - JU_TOIMMED_01_EVEN(cIS, ignore, ignore); \ - JUDYLCODE(j__udyLFreeJV(PjvRaw, 2, Pjpm);) \ - Pjp->jp_Type = (NewJPType); \ - return(1); \ - } - -#if (defined(JUDY1) || defined(JU_64BIT)) - -// Variation for "odd" cJ*_JPIMMED_*_02 JP types, which are very different from -// "even" types because they use leaf search code and odd-copy macros: -// -// Note: JudyL 32-bit has no "odd" JPIMMED_*_02 types. - -#define JU_IMMED_02_ODD(cIS,NewJPType,SearchLeaf,CopyPIndex) \ - { \ - uint8_t * Pleaf; \ - \ - assert((ParentLevel - 1) == (cIS)); \ - JUDY1CODE(Pleaf = (uint8_t *) (Pjp->jp_1Index);) \ - JUDYLCODE(Pleaf = (uint8_t *) (Pjp->jp_LIndex);) \ - JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \ - JUDYLCODE(Pjv = P_JV(PjvRaw);) \ - JU_TOIMMED_01_ODD(cIS, SearchLeaf, CopyPIndex); \ - JUDYLCODE(j__udyLFreeJV(PjvRaw, 2, Pjpm);) \ - Pjp->jp_Type = (NewJPType); \ - return(1); \ - } -#endif // (JUDY1 || JU_64BIT) - -// Core code for deleting one Index (and for JudyL, its value area) from a -// larger Immed: -// -// Variables Pleaf, pop1, and offset are in the context. - -#ifdef JUDY1 -#define JU_IMMED_DEL(cIS,DeleteInPlace) \ - DeleteInPlace(Pleaf, pop1, offset, cIS); \ - DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) - -#else // JUDYL - -// For JudyL the value area might need to be shrunk: - -#define JU_IMMED_DEL(cIS,DeleteInPlace) \ - \ - if (JL_LEAFVGROWINPLACE(pop1 - 1)) /* hysteresis = 0 */ \ - { \ - DeleteInPlace( Pleaf, pop1, offset, cIS); \ - JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \ - DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \ - } \ - else \ - { \ - Pjv_t PjvnewRaw; \ - Pjv_t Pjvnew; \ - \ - if ((PjvnewRaw = j__udyLAllocJV(pop1 - 1, Pjpm)) \ - == (Pjv_t) NULL) return(-1); \ - Pjvnew = P_JV(PjvnewRaw); \ - \ - DeleteInPlace(Pleaf, pop1, offset, cIS); \ - JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore); \ - DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \ - j__udyLFreeJV(PjvRaw, pop1, Pjpm); \ - \ - (Pjp->jp_Addr) = (Word_t) PjvnewRaw; \ - } -#endif // JUDYL - -// Delete one Index from a larger Immed where no restructuring is required: -// -// Variables pop1, Pjp, offset, and Index are in the context. - -#define JU_IMMED(cIS,LeafType,BaseJPType,SearchLeaf,DeleteInPlace) \ - { \ - LeafType Pleaf; \ - \ - assert((ParentLevel - 1) == (cIS)); \ - JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \ - JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \ - JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \ - JUDYLCODE(Pjv = P_JV(PjvRaw);) \ - pop1 = (JU_JPTYPE(Pjp)) - (BaseJPType) + 2; \ - offset = SearchLeaf(Pleaf, pop1, Index); \ - assert(offset >= 0); /* Index must be valid */ \ - \ - JU_IMMED_DEL(cIS, DeleteInPlace); \ - --(Pjp->jp_Type); \ - return(1); \ - } - - -// END OF MACROS, START OF CASES: - -// Single Index remains in Immed; convert JP to null: - - case cJU_JPIMMED_1_01: JU_IMMED_01(cJU_JPNULL1, cJU_JPBRANCH_U2); - case cJU_JPIMMED_2_01: JU_IMMED_01(cJU_JPNULL2, cJU_JPBRANCH_U3); -#ifndef JU_64BIT - case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U); -#else - case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U4); - case cJU_JPIMMED_4_01: JU_IMMED_01(cJU_JPNULL4, cJU_JPBRANCH_U5); - case cJU_JPIMMED_5_01: JU_IMMED_01(cJU_JPNULL5, cJU_JPBRANCH_U6); - case cJU_JPIMMED_6_01: JU_IMMED_01(cJU_JPNULL6, cJU_JPBRANCH_U7); - case cJU_JPIMMED_7_01: JU_IMMED_01(cJU_JPNULL7, cJU_JPBRANCH_U); -#endif - -// Multiple Indexes remain in the Immed JP; delete the specified Index: - - case cJU_JPIMMED_1_02: - - JU_IMMED_02(1, uint8_t *, cJU_JPIMMED_1_01); - - 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 - JU_IMMED(1, uint8_t *, cJU_JPIMMED_1_02, - j__udySearchLeaf1, JU_DELETEINPLACE); - -#if (defined(JUDY1) || defined(JU_64BIT)) - case cJU_JPIMMED_2_02: - - JU_IMMED_02(2, uint16_t *, cJU_JPIMMED_2_01); - - 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)) - JU_IMMED(2, uint16_t *, cJU_JPIMMED_2_02, - j__udySearchLeaf2, JU_DELETEINPLACE); - - case cJU_JPIMMED_3_02: - - JU_IMMED_02_ODD(3, cJU_JPIMMED_3_01, - j__udySearchLeaf3, JU_COPY3_PINDEX_TO_LONG); - -#endif - -#if (defined(JUDY1) && defined(JU_64BIT)) - case cJ1_JPIMMED_3_03: - case cJ1_JPIMMED_3_04: - case cJ1_JPIMMED_3_05: - - JU_IMMED(3, uint8_t *, cJU_JPIMMED_3_02, - j__udySearchLeaf3, JU_DELETEINPLACE_ODD); - - case cJ1_JPIMMED_4_02: - - JU_IMMED_02(4, uint32_t *, cJU_JPIMMED_4_01); - - case cJ1_JPIMMED_4_03: - - JU_IMMED(4, uint32_t *, cJ1_JPIMMED_4_02, - j__udySearchLeaf4, JU_DELETEINPLACE); - - case cJ1_JPIMMED_5_02: - - JU_IMMED_02_ODD(5, cJU_JPIMMED_5_01, - j__udySearchLeaf5, JU_COPY5_PINDEX_TO_LONG); - - case cJ1_JPIMMED_5_03: - - JU_IMMED(5, uint8_t *, cJ1_JPIMMED_5_02, - j__udySearchLeaf5, JU_DELETEINPLACE_ODD); - - case cJ1_JPIMMED_6_02: - - JU_IMMED_02_ODD(6, cJU_JPIMMED_6_01, - j__udySearchLeaf6, JU_COPY6_PINDEX_TO_LONG); - - case cJ1_JPIMMED_7_02: - - JU_IMMED_02_ODD(7, cJU_JPIMMED_7_01, - j__udySearchLeaf7, JU_COPY7_PINDEX_TO_LONG); - -#endif // (JUDY1 && JU_64BIT) - - -// **************************************************************************** -// INVALID JP TYPE: - - default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1); - - } // switch - - -// PROCESS JP -- RECURSIVELY: -// -// For non-Immed JP types, if successful, post-decrement the population count -// at this level, or collapse a BranchL if necessary by copying the remaining -// JP in the BranchL to the parent (hysteresis = 0), which implicitly creates a -// narrow pointer if there was not already one in the hierarchy. - - assert(level); - retcode = j__udyDelWalk(Pjp, Index, level, Pjpm); - assert(retcode != 0); // should never happen. - - if ((JU_JPTYPE(Pjp)) < cJU_JPIMMED_1_01) // not an Immed. - { - switch (retcode) - { - case 1: - { - jp_t JP = *Pjp; - Word_t DcdP0; - - DcdP0 = JU_JPDCDPOP0(Pjp) - 1; // decrement count. - JU_JPSETADT(Pjp, JP.jp_Addr, DcdP0, JU_JPTYPE(&JP)); - break; - } - case 2: // collapse BranchL to single JP; see above: - { - Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr); - Pjbl_t Pjbl = P_JBL(PjblRaw); - - *Pjp = Pjbl->jbl_jp[0]; - j__udyFreeJBL(PjblRaw, Pjpm); - retcode = 1; - } - } - } - - return(retcode); - -} // j__udyDelWalk() - - -// **************************************************************************** -// J U D Y 1 U N S E T -// J U D Y L D E L -// -// Main entry point. See the manual entry for details. - -#ifdef JUDY1 -FUNCTION int Judy1Unset -#else -FUNCTION int JudyLDel -#endif - ( - PPvoid_t PPArray, // in which to delete. - Word_t Index, // to delete. - PJError_t PJError // optional, for returning error info. - ) -{ - Word_t pop1; // population of leaf. - int offset; // at which to delete Index. - JUDY1CODE(int retcode;) // return code from Judy1Test(). -JUDYLCODE(PPvoid_t PPvalue;) // pointer from JudyLGet(). - - -// CHECK FOR NULL ARRAY POINTER (error by caller): - - if (PPArray == (PPvoid_t) NULL) - { - JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY); - return(JERRI); - } - - -// CHECK IF INDEX IS INVALID: -// -// If so, theres nothing to do. This saves a lot of time. Pass through -// PJError, if any, from the "get" function. - -#ifdef JUDY1 - if ((retcode = Judy1Test(*PPArray, Index, PJError)) == JERRI) - return (JERRI); - - if (retcode == 0) return(0); -#else - if ((PPvalue = JudyLGet(*PPArray, Index, PJError)) == PPJERR) - return (JERRI); - - if (PPvalue == (PPvoid_t) NULL) return(0); -#endif - - -// **************************************************************************** -// PROCESS TOP LEVEL (LEAFW) BRANCHES AND LEAVES: - -// **************************************************************************** -// LEAFW LEAF, OTHER SIZE: -// -// Shrink or convert the leaf as necessary. Hysteresis = 0; none is possible. - - if (JU_LEAFW_POP0(*PPArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW - { - JUDYLCODE(Pjv_t Pjv;) // current value area. - JUDYLCODE(Pjv_t Pjvnew;) // value area in new leaf. - Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf. - Pjlw_t Pjlwnew; // replacement leaf. - pop1 = Pjlw[0] + 1; // first word of leaf is pop0. - -// Delete single (last) Index from array: - - if (pop1 == 1) - { - j__udyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL); - *PPArray = (Pvoid_t) NULL; - return(1); - } - -// Locate Index in compressible leaf: - - offset = j__udySearchLeafW(Pjlw + 1, pop1, Index); - assert(offset >= 0); // Index must be valid. - - JUDYLCODE(Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);) - -// Delete Index in-place: -// -// Note: "Grow in place from pop1 - 1" is the logical inverse of, "shrink in -// place from pop1." Also, Pjlw points to the count word, so skip that for -// doing the deletion. - - if (JU_LEAFWGROWINPLACE(pop1 - 1)) - { - JU_DELETEINPLACE(Pjlw + 1, pop1, offset, ignore); -#ifdef JUDYL // also delete from value area: - JU_DELETEINPLACE(Pjv, pop1, offset, ignore); -#endif - DBGCODE(JudyCheckSorted((Pjll_t) (Pjlw + 1), pop1 - 1, - cJU_ROOTSTATE);) - --(Pjlw[0]); // decrement population. - DBGCODE(JudyCheckPop(*PPArray);) - return(1); - } - -// Allocate new leaf for use in either case below: - - Pjlwnew = j__udyAllocJLW(pop1 - 1); - JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI); - -// Shrink to smaller LEAFW: -// -// Note: Skip the first word = pop0 in each leaf. - - Pjlwnew[0] = (pop1 - 1) - 1; - JU_DELETECOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, ignore); - -#ifdef JUDYL // also delete from value area: - Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 - 1); - JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore); -#endif - DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 - 1, cJU_ROOTSTATE);) - - j__udyFreeJLW(Pjlw, pop1, (Pjpm_t) NULL); - -//// *PPArray = (Pvoid_t) Pjlwnew | cJU_LEAFW); - *PPArray = (Pvoid_t) Pjlwnew; - DBGCODE(JudyCheckPop(*PPArray);) - return(1); - - } - else - - -// **************************************************************************** -// JRP BRANCH: -// -// Traverse through the JPM to do the deletion unless the population is small -// enough to convert immediately to a LEAFW. - - { - Pjpm_t Pjpm; - Pjp_t Pjp; // top-level JP to process. - Word_t digit; // in a branch. - JUDYLCODE(Pjv_t Pjv;) // to value area. - Pjlw_t Pjlwnew; // replacement leaf. - DBGCODE(Pjlw_t Pjlwnew_orig;) - - Pjpm = P_JPM(*PPArray); // top object in array (tree). - Pjp = &(Pjpm->jpm_JP); // next object (first branch or leaf). - - assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L) - || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B) - || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U)); - -// WALK THE TREE -// -// Note: Recursive code in j__udyDelWalk() knows how to collapse a lower-level -// BranchL containing a single JP into the parent JP as a narrow pointer, but -// the code here cant do that for a top-level BranchL. The result can be -// PArray -> JPM -> BranchL containing a single JP. This situation is -// unavoidable because a JPM cannot contain a narrow pointer; the BranchL is -// required in order to hold the top digit decoded, and it does not collapse to -// a LEAFW until the population is low enough. -// -// TBD: Should we add a topdigit field to JPMs so they can hold narrow -// pointers? - - if (j__udyDelWalk(Pjp, Index, cJU_ROOTSTATE, Pjpm) == -1) - { - JU_COPY_ERRNO(PJError, Pjpm); - return(JERRI); - } - - --(Pjpm->jpm_Pop0); // success; decrement total population. - - if ((Pjpm->jpm_Pop0 + 1) != cJU_LEAFW_MAXPOP1) - { - DBGCODE(JudyCheckPop(*PPArray);) - return(1); - } - -// COMPRESS A BRANCH[LBU] TO A LEAFW: -// - Pjlwnew = j__udyAllocJLW(cJU_LEAFW_MAXPOP1); - JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI); - -// Plug leaf into root pointer and set population count: - -//// *PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_LEAFW); - *PPArray = (Pvoid_t) Pjlwnew; -#ifdef JUDYL // prepare value area: - Pjv = JL_LEAFWVALUEAREA(Pjlwnew, cJU_LEAFW_MAXPOP1); -#endif - *Pjlwnew++ = cJU_LEAFW_MAXPOP1 - 1; // set pop0. - DBGCODE(Pjlwnew_orig = Pjlwnew;) - - switch (JU_JPTYPE(Pjp)) - { - -// JPBRANCH_L: Copy each JPs indexes to the new LEAFW and free the old -// branch: - - case cJU_JPBRANCH_L: - { - Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr); - Pjbl_t Pjbl = P_JBL(PjblRaw); - - for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset) - { - pop1 = j__udyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS - (Pjbl->jbl_jp) + offset, - JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset], - cJU_BYTESPERWORD), - (Pvoid_t) Pjpm); - Pjlwnew += pop1; // advance through indexes. - JUDYLCODE(Pjv += pop1;) // advance through values. - } - j__udyFreeJBL(PjblRaw, Pjpm); - - assert(Pjlwnew == Pjlwnew_orig + cJU_LEAFW_MAXPOP1); - break; // delete Index from new LEAFW. - } - -// JPBRANCH_B: Copy each JPs indexes to the new LEAFW and free the old -// branch, including each JP subarray: - - case cJU_JPBRANCH_B: - { - Pjbb_t PjbbRaw = (Pjbb_t) (Pjp->jp_Addr); - Pjbb_t Pjbb = P_JBB(PjbbRaw); - Word_t subexp; // current subexpanse number. - BITMAPB_t bitmap; // portion for this subexpanse. - Pjp_t Pjp2Raw; // one subexpanses subarray. - Pjp_t Pjp2; - - for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) - { - if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0) - continue; // skip empty subexpanse. - - digit = subexp * cJU_BITSPERSUBEXPB; - Pjp2Raw = JU_JBB_PJP(Pjbb, subexp); - Pjp2 = P_JP(Pjp2Raw); - assert(Pjp2 != (Pjp_t) NULL); - -// Walk through bits for all possible sub-subexpanses (digits); increment -// offset for each populated subexpanse; until no more set bits: - - for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit) - { - if (! (bitmap & 1)) // skip empty sub-subexpanse. - continue; - - pop1 = j__udyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS - Pjp2 + offset, - JU_DIGITTOSTATE(digit, cJU_BYTESPERWORD), - (Pvoid_t) Pjpm); - Pjlwnew += pop1; // advance through indexes. - JUDYLCODE(Pjv += pop1;) // advance through values. - ++offset; - } - j__udyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm); - } - j__udyFreeJBB(PjbbRaw, Pjpm); - - assert(Pjlwnew == Pjlwnew_orig + cJU_LEAFW_MAXPOP1); - break; // delete Index from new LEAFW. - - } // case cJU_JPBRANCH_B. - - -// JPBRANCH_U: Copy each JPs indexes to the new LEAFW and free the old -// branch: - - case cJU_JPBRANCH_U: - { - Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr); - Pjbu_t Pjbu = P_JBU(PjbuRaw); - Word_t ldigit; // larger than uint8_t. - - for (Pjp = Pjbu->jbu_jp, ldigit = 0; - ldigit < cJU_BRANCHUNUMJPS; - ++Pjp, ++ldigit) - { - -// Shortcuts, to save a little time for possibly big branches: - - if ((JU_JPTYPE(Pjp)) == cJU_JPNULLMAX) // skip null JP. - continue; - -// TBD: Should the following shortcut also be used in BranchL and BranchB -// code? - -#ifndef JU_64BIT - if ((JU_JPTYPE(Pjp)) == cJU_JPIMMED_3_01) -#else - if ((JU_JPTYPE(Pjp)) == cJU_JPIMMED_7_01) -#endif - { // single Immed: - *Pjlwnew++ = JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD) - | JU_JPDCDPOP0(Pjp); // rebuild Index. -#ifdef JUDYL - *Pjv++ = Pjp->jp_Addr; // copy value area. -#endif - continue; - } - - pop1 = j__udyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS - Pjp, JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD), - (Pvoid_t) Pjpm); - Pjlwnew += pop1; // advance through indexes. - JUDYLCODE(Pjv += pop1;) // advance through values. - } - j__udyFreeJBU(PjbuRaw, Pjpm); - - assert(Pjlwnew == Pjlwnew_orig + cJU_LEAFW_MAXPOP1); - break; // delete Index from new LEAFW. - - } // case cJU_JPBRANCH_U. - - -// INVALID JP TYPE in jpm_t struct - - default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); - return(JERRI); - - } // end switch on sub-JP type. - - DBGCODE(JudyCheckSorted((Pjll_t) Pjlwnew_orig, cJU_LEAFW_MAXPOP1, - cJU_ROOTSTATE);) - -// FREE JPM (no longer needed): - - j__udyFreeJPM(Pjpm, (Pjpm_t) NULL); - DBGCODE(JudyCheckPop(*PPArray);) - return(1); - - } - /*NOTREACHED*/ - -} // Judy1Unset() / JudyLDel() |