view release on metacpan or  search on metacpan

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

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

#include "JudyPrivate1L.h"

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


// ****************************************************************************
// J U D Y   1   P R E V   E M P T Y
// J U D Y   1   N E X T   E M P T Y
// J U D Y   L   P R E V   E M P T Y
// J U D Y   L   N E X T   E M P T Y
//
// See the manual entry for the API.
//
// OVERVIEW OF Judy*PrevEmpty() / Judy*NextEmpty():
//
// See also for comparison the equivalent comments in JudyPrevNext.c.
//
// Take the callers *PIndex and subtract/add 1, but watch out for
// underflow/overflow, which means "no previous/next empty index found."  Use a
// reentrant switch statement (state machine, see SMGetRestart and
// SMGetContinue) to decode Index, starting with the JRP (PArray), through a
// JPM and branches, if any, down to an immediate or a leaf.  Look for Index in
// that immediate or leaf, and if not found (invalid index), return success
// (Index is empty).
//
// This search can result in a dead end where taking a different path is
// required.  There are four kinds of dead ends:
//
// BRANCH PRIMARY dead end:  Encountering a fully-populated JP for the
// appropriate digit in Index.  Search sideways in the branch for the
// previous/next absent/null/non-full JP, and if one is found, set Index to the
// highest/lowest index possible in that JPs expanse.  Then if the JP is an
// absent or null JP, return success; otherwise for a non-full JP, traverse
// through the partially populated JP.
//
// BRANCH SECONDARY dead end:  Reaching the end of a branch during a sideways
// search after a branch primary dead end.  Set Index to the lowest/highest
// index possible in the whole branchs expanse (one higher/lower than the
// previous/next branchs expanse), then restart at the top of the tree, which
// includes pre-decrementing/incrementing Index (again) and watching for
// underflow/overflow (again).
//
// LEAF PRIMARY dead end:  Finding a valid (non-empty) index in an immediate or
// leaf matching Index.  Search sideways in the immediate/leaf for the
// previous/next empty index; if found, set *PIndex to match and return success.
//
// LEAF SECONDARY dead end:  Reaching the end of an immediate or leaf during a
// sideways search after a leaf primary dead end.  Just as for a branch
// secondary dead end, restart at the top of the tree with Index set to the
// lowest/highest index possible in the whole immediate/leafs expanse.
// TBD:  If leaf secondary dead end occurs, could shortcut and treat it as a
// branch primary dead end; but this would require remembering the parent
// branchs type and offset (a "one-deep stack"), and also wrestling with
// narrow pointers, at least for leaves (but not for immediates).
//
// Note some ASYMMETRIES between SearchValid and SearchEmpty:
//
// - The SearchValid code, upon descending through a narrow pointer, if Index
//   is outside the expanse of the subsidiary node (effectively a secondary
//   dead end), must decide whether to backtrack or findlimit.  But the
//   SearchEmpty code simply returns success (Index is empty).
//
// - Similarly, the SearchValid code, upon finding no previous/next index in
//   the expanse of a narrow pointer (again, a secondary dead end), can simply
//   start to backtrack at the parent JP.  But the SearchEmpty code would have
//   to first determine whether or not the parent JPs narrow expanse contains
//   a previous/next empty index outside the subexpanse.  Rather than keeping a
//   parent state stack and backtracking this way, upon a secondary dead end,
//   the SearchEmpty code simply restarts at the top of the tree, whether or
//   not a narrow pointer is involved.  Again, see the equivalent comments in
//   JudyPrevNext.c for comparison.
//
// This function is written iteratively for speed, rather than recursively.
//
// TBD:  Wed like to enhance this function to make successive searches faster.
// This would require saving some previous state, including the previous Index
// returned, and in which leaf it was found.  If the next call is for the same
// Index and the array has not been modified, start at the same leaf.  This
// should be much easier to implement since this is iterative rather than
// recursive code.

#ifdef JUDY1
#ifdef JUDYPREV
FUNCTION int Judy1PrevEmpty
#else
FUNCTION int Judy1NextEmpty
#endif
#else
#ifdef JUDYPREV
FUNCTION int JudyLPrevEmpty
#else
FUNCTION int JudyLNextEmpty
#endif
#endif
        (
	Pcvoid_t  PArray,	// Judy array to search.
	Word_t *  PIndex,	// starting point and result.
	PJError_t PJError	// optional, for returning error info.
        )
{
	Word_t	  Index;	// fast copy, in a register.
	Pjp_t	  Pjp;		// current JP.
	Pjbl_t	  Pjbl;		// Pjp->jp_Addr masked and cast to types:
	Pjbb_t	  Pjbb;
	Pjbu_t	  Pjbu;
	Pjlb_t	  Pjlb;
	PWord_t	  Pword;	// alternate name for use by GET* macros.

	Word_t	  digit;	// next digit to decode from Index.
	Word_t	  digits;	// current state in SM = digits left to decode.
	Word_t	  pop0;		// in a leaf.
	Word_t	  pop0mask;	// precalculated to avoid variable shifts.
	long	  offset;	// within a branch or leaf (can be large).
	int	  subexp;	// subexpanse in a bitmap branch.
	BITMAPB_t bitposmaskB;	// bit in bitmap for bitmap branch.
	BITMAPL_t bitposmaskL;	// bit in bitmap for bitmap leaf.
	Word_t	  possfullJP1;	// JP types for possibly full subexpanses:
	Word_t	  possfullJP2;
	Word_t	  possfullJP3;


// ----------------------------------------------------------------------------
// M A C R O S
//
// These are intended to make the code a bit more readable and less redundant.


// CHECK FOR NULL JP:
//
// TBD:  In principle this can be reduced (here and in other *.c files) to just
// the latter clause since no Type should ever be below cJU_JPNULL1, but in
// fact some root pointer types can be lower, so for safety do both checks.

#define	JPNULL(Type)  (((Type) >= cJU_JPNULL1) && ((Type) <= cJU_JPNULLMAX))


// CHECK FOR A FULL JP:
//
// Given a JP, indicate if it is fully populated.  Use digits, pop0mask, and
// possfullJP1..3 in the context.
//
// This is a difficult problem because it requires checking the Pop0 bits for
// all-ones, but the number of bytes depends on the JP type, which is not
// directly related to the parent branchs type or level -- the JPs child
// could be under a narrow pointer (hence not full).  The simple answer
// requires switching on or otherwise calculating the JP type, which could be
// slow.  Instead, in SMPREPB* precalculate pop0mask and also record in
// possfullJP1..3 the child JP (branch) types that could possibly be full (one
// level down), and use them here.  For level-2 branches (with digits == 2),
// the test for a full child depends on Judy1/JudyL.
//
// Note:  This cannot be applied to the JP in a JPM because it doesnt have
// enough pop0 digits.
//
// TBD:  JPFULL_BRANCH diligently checks for BranchL or BranchB, where neither
// of those can ever be full as it turns out.  Could just check for a BranchU
// at the right level.  Also, pop0mask might be overkill, its not used much,
// so perhaps just call cJU_POP0MASK(digits - 1) here?
//
// First, JPFULL_BRANCH checks for a full expanse for a JP whose child can be a
// branch, that is, a JP in a branch at level 3 or higher:

#define	JPFULL_BRANCH(Pjp)						\
	  ((((JU_JPDCDPOP0(Pjp) ^ cJU_ALLONES) & pop0mask) == 0)	\
	&& ((JU_JPTYPE(Pjp) == possfullJP1)				\
	 || (JU_JPTYPE(Pjp) == possfullJP2)				\
	 || (JU_JPTYPE(Pjp) == possfullJP3)))

#ifdef JUDY1
#define	JPFULL(Pjp)							\
	((digits == 2) ?						\
	 (JU_JPTYPE(Pjp) == cJ1_JPFULLPOPU1) : JPFULL_BRANCH(Pjp))
#else
#define	JPFULL(Pjp)							\
	((digits == 2) ?						\
	   (JU_JPTYPE(Pjp) == cJU_JPLEAF_B1)				\
	 && (((JU_JPDCDPOP0(Pjp) & cJU_POP0MASK(1)) == cJU_POP0MASK(1))) : \
	 JPFULL_BRANCH(Pjp))
#endif


// RETURN SUCCESS:
//
// This hides the need to set *PIndex back to the local value of Index -- use a
// local value for faster operation.  Note that the callers *PIndex is ALWAYS
// modified upon success, at least decremented/incremented.

#define	RET_SUCCESS { *PIndex = Index; return(1); }


// RETURN A CORRUPTION:

#define	RET_CORRUPT { JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); return(JERRI); }


// SEARCH A BITMAP BRANCH:
//
// This is a weak analog of j__udySearchLeaf*() for bitmap branches.  Return
// the actual or next-left position, base 0, of Digit in a BITMAPB_t bitmap
// (subexpanse of a full bitmap), also given a Bitposmask for Digit.  The
// position is the offset within the set bits.
//
// Unlike j__udySearchLeaf*(), the offset is not returned bit-complemented if
// Digits bit is unset, because the caller can check the bitmap themselves to