view release on metacpan or  search on metacpan

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

#ifdef TRACEJP
#include "JudyPrintJP.c"
#endif

// These are defined to generic values in JudyCommon/JudyPrivateTypes.h:
//
// TBD:  These should be exported from a header file, but perhaps not, as they
// are only used here, and exported from JudyDecascade.c, which is a separate
// file for profiling reasons (to prevent inlining), but which potentially
// could be merged with this file, either in SoftCM or at compile-time:

#ifdef JUDY1

extern int      j__udy1BranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);
#ifndef JU_64BIT
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.