view release on metacpan or  search on metacpan

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

#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;