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