view release on metacpan or  search on metacpan

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

//
// CAVEATS:
//
// Why use a backtrack list (history stack), since it has finite size?  The
// size is small for Judy on both 32-bit and 64-bit systems, and a list (really
// just an array) is fast to maintain and use.  Other alternatives include
// doing a lookahead (lookaside) in each branch while traversing forward
// (decoding), and restarting from the top upon a dead end.
//
// A lookahead means noting the last branch traversed which contained a
// non-null JP lower than the one specified by a digit in *PIndex-1, and
// returning to that point for SM3Findlimit.  This seems like a good idea, and
// should be pretty cheap for linear and bitmap branches, but it could result
// in up to 31 unnecessary additional cache line fills (in extreme cases) for
// every uncompressed branch traversed.  We have considered means of attaching
// to or hiding within an uncompressed branch (in null JPs) a "cache line map"
// or other structure, such as an offset to the next non-null JP, that would
// speed this up, but it seems unnecessary merely to avoid having a
// finite-length list (array).  (If JudySL is ever made "native", the finite
// list length will be an issue.)
//
// Restarting at the top of the Judy array after a dead end requires a careful
// modification of *PIndex-1 to decrement the digit for the parent branch and
// set the remaining lower digits to all 1s.  This must be repeated each time a
// parent branch contains another dead end, so even though it should all happen
// in cache, the CPU time can be excessive.  (For JudySL or an equivalent
// "infinitely deep" Judy array, consider a hybrid of a large, finite,
// "circular" list and a restart-at-top when the list is backtracked to
// exhaustion.)
//
// Why search for *PIndex-1 instead of *PIndex during SM1Get?  In rare
// instances this prevents an unnecessary decode down the wrong path followed
// by a backtrack; its pretty cheap to set up initially; and it means the
// SM1Get machine can simply return if/when it finds that Index.
//
// 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.
//
// VARIATIONS FOR Judy*Next():
//
// The Judy*Next() code is nearly a perfect mirror of the Judy*Prev() code.
// See the Judy*Prev() overview comments, and mentally switch the following:
//
// - "*PIndex-1"  => "*PIndex+1"
// - "less than"  => "greater than"
// - "lower"      => "higher"
// - "lowest"     => "highest"
// - "next-left"  => "next-right"
// - "right-most" => "left-most"
//
// Note:  SM3Findlimit could be called SM3Findmax/SM3Findmin, but a common name
// for both Prev and Next means many fewer ifdefs in this code.
//
// TBD:  Currently this code traverses a JP whether its expanse is partially or
// completely full (populated).  For Judy1 (only), since there is no value area
// needed, consider shortcutting to a "success" return upon encountering a full
// JP in SM1Get (or even SM3Findlimit?)  A full JP looks like this:
//
//	(((JU_JPDCDPOP0(Pjp) ^ cJU_ALLONES) & cJU_POP0MASK(cLevel)) == 0)

#ifdef JUDY1
#ifdef JUDYPREV
FUNCTION int Judy1Prev
#else
FUNCTION int Judy1Next
#endif
#else
#ifdef JUDYPREV
FUNCTION PPvoid_t JudyLPrev
#else
FUNCTION PPvoid_t JudyLNext
#endif
#endif
        (
	Pcvoid_t  PArray,	// Judy array to search.
	Word_t *  PIndex,	// starting point and result.
	PJError_t PJError	// optional, for returning error info.
        )
{
	Pjp_t	  Pjp, Pjp2;	// current JPs.
	Pjbl_t	  Pjbl;		// Pjp->jp_Addr masked and cast to types:
	Pjbb_t	  Pjbb;
	Pjbu_t	  Pjbu;

// Note:  The following initialization is not strictly required but it makes
// gcc -Wall happy because there is an "impossible" path from Immed handling to
// SM1LeafLImm code that looks like Pjll might be used before set:

	Pjll_t	  Pjll = (Pjll_t) NULL;
	Word_t	  state;	// current state in SM.
	Word_t	  digit;	// next digit to decode from Index.

// Note:  The following initialization is not strictly required but it makes
// gcc -Wall happy because there is an "impossible" path from Immed handling to
// SM1LeafLImm code (for JudyL & JudyPrev only) that looks like pop1 might be
// used before set:

#if (defined(JUDYL) && defined(JUDYPREV))
	Word_t	  pop1 = 0;	// in a leaf.
#else
	Word_t	  pop1;		// in a leaf.
#endif
	int	  offset;	// linear branch/leaf, from j__udySearchLeaf*().
	int	  subexp;	// subexpanse in a bitmap branch.
	Word_t	  bitposmask;	// bit in bitmap for Index.

// History for SM2Backtrack:
//
// For a given histnum, APjphist[histnum] is a parent JP that points to a
// branch, and Aoffhist[histnum] is the offset of the NEXT JP in the branch to
// which the parent JP points.  The meaning of Aoffhist[histnum] depends on the
// type of branch to which the parent JP points:
//
// Linear:  Offset of the next JP in the JP list.
//
// Bitmap:  Which subexpanse, plus the offset of the next JP in the
// subexpanses JP list (to avoid bit-counting again), plus for Judy*Next(),
// hidden one byte to the left, which digit, because Judy*Next() also needs
// this.
//
// Uncompressed:  Digit, which is actually the offset of the JP in the branch.
//
// Note:  Only branch JPs are stored in APjphist[] because, as explained
// earlier, SM1Get shortcuts sideways searches in leaves (and even in branches
// in some cases), so SM2Backtrack only handles branches.

#define	HISTNUMMAX cJU_ROOTSTATE	// maximum branches traversable.
	Pjp_t	APjphist[HISTNUMMAX];	// list of branch JPs traversed.
	int	Aoffhist[HISTNUMMAX];	// list of next JP offsets; see above.
	int	histnum = 0;		// number of JPs now in list.


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


// "PUSH" AND "POP" Pjp AND offset ON HISTORY STACKS:
//
// Note:  Ensure a corrupt Judy array does not overflow *hist[].  Meanwhile,
// underflowing *hist[] simply means theres no more room to backtrack =>
// "no previous/next Index".

#define	HISTPUSH(Pjp,Offset)			\
	APjphist[histnum] = (Pjp);		\
	Aoffhist[histnum] = (Offset);		\
						\
	if (++histnum >= HISTNUMMAX)		\
	{					\
	    JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT) \
	    JUDY1CODE(return(JERRI );)		\
	    JUDYLCODE(return(PPJERR);)		\
	}