view release on metacpan or  search on metacpan

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

// @(#) $Revision: 4.68 $ $Source: /judy/src/JudyCommon/JudyDel.c $
//
// Judy1Unset() and JudyLDel() functions for Judy1 and JudyL.
// Compile with one of -DJUDY1 or -DJUDYL.
//
// About HYSTERESIS:  In the Judy code, hysteresis means leaving around a
// nominally suboptimal (not maximally compressed) data structure after a
// deletion.  As a result, the shape of the tree for two identical index sets
// can differ depending on the insert/delete path taken to arrive at the index
// sets.  The purpose is to minimize worst-case behavior (thrashing) that could
// result from a series of intermixed insertions and deletions.  It also makes
// for MUCH simpler code, because instead of performing, "delete and then
// compress," it can say, "compress and then delete," where due to hysteresis,
// compression is not even attempted until the object IS compressible.
//
// In some cases the code has no choice and it must "ungrow" a data structure
// across a "phase transition" boundary without hysteresis.  In other cases the
// amount (such as "hysteresis = 1") is indicated by the number of JP deletions
// (in branches) or index deletions (in leaves) that can occur in succession
// before compressing the data structure.  (It appears that hysteresis <= 1 in
// all cases.)
//
// In general no hysteresis occurs when the data structure type remains the
// same but the allocated memory chunk for the node must shrink, because the
// relationship is hardwired and theres no way to know how much memory is
// allocated to a given data structure.  Hysteresis = 0 in all these cases.
//
// TBD:  Could this code be faster if memory chunk hysteresis were supported
// somehow along with data structure type hysteresis?
//
// TBD:  Should some of the assertions here be converted to product code that
// returns JU_ERRNO_CORRUPT?
//
// TBD:  Dougs code had an odd mix of function-wide and limited-scope
// variables.  Should some of the function-wide variables appear only in
// limited scopes, or more likely, vice-versa?

#if (! (defined(JUDY1) || defined(JUDYL)))
#error:  One of -DJUDY1 or -DJUDYL must be specified.
#endif

#ifdef JUDY1
#include "Judy1.h"
#else
#include "JudyL.h"
#endif

#include "JudyPrivate1L.h"

DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)
DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)

#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:
//