view release on metacpan or  search on metacpan

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

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

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

                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.
            }