view release on metacpan or  search on metacpan

src/judy-1.0.5/src/JudyCommon/JudyDel.c  view on Meta::CPAN

// 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;)                                          \
            }                                                           \