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