Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
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*():
//
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
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 */ \
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
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;
}
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
// 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
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
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
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
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):
src/judy-1.0.5/src/JudyCommon/JudyDel.c view on Meta::CPAN
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);
( run in 0.787 second using v1.01-cache-2.11-cpan-2398b32b56e )