view release on metacpan or  search on metacpan

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

//      no reason to search it.  "Slide right" to the high end of the leaf
//      (modify Index to maxindex) and continue with step 2 above.
//
// 3c.  If LESS, continue with step 4.
//
// 4.  If the offset based on maxindex minus Index falls BEFORE the start of
//     the leaf, or if, per 3c above, baseindex is LESS than Index, the leaf is
//     guaranteed "not dense to the end" and a usable empty Index must exist.
//     This supports a more efficient search loop.  Start at the FIRST index in
//     the leaf, or one BEYOND baseindex, respectively, and search the leaf as
//     follows, comparing each current index (currindex) with Index:
//
// 4a.  If LESS, keep going to next index.  Note:  This is certain to terminate
//      because maxindex is known to be greater than Index, hence the loop can
//      be small and fast.
//
// 4b.  If EQUAL, loop and increment Index until finding currindex greater than
//      Index, and return success with the modified Index.
//
// 4c.  If GREATER, return success, Index (unmodified) is empty.
//
// Note:  These are macros rather than functions for speed.

#ifdef JUDYPREV

#define	JSLE_EVEN(Addr,Pop0,cDigits,LeafType)				\
	{								\
	    LeafType * PjllLSB  = (LeafType *) (Addr);			\
	    LeafType   IndexLSB = Index;	/* auto-masking */	\
									\
	/* Index before or at start of leaf: */				\
									\
	    if (*PjllLSB >= IndexLSB)		/* no need to search */	\
	    {								\
		if (*PjllLSB > IndexLSB) RET_SUCCESS; /* Index empty */	\
		LEAF_EDGE(*PjllLSB, cDigits);				\
	    }								\
									\
	/* Index in or after leaf: */					\
									\
	    offset = IndexLSB - *PjllLSB;	/* tentative offset  */	\
	    if (offset <= (Pop0))		/* can check density */	\
	    {								\
		PjllLSB += offset;		/* move to slot */	\
									\
		if (*PjllLSB <= IndexLSB)	/* dense or corrupt */	\
		{							\
		    if (*PjllLSB == IndexLSB)	/* dense, check edge */	\
			LEAF_EDGE_SET(PjllLSB[-offset], cDigits);	\
		    RET_CORRUPT;					\
		}							\
		--PjllLSB;	/* not dense, start at previous */	\
	    }								\
	    else PjllLSB = ((LeafType *) (Addr)) + (Pop0); /* start at max */ \
									\
	    LEAF_HOLE_EVEN(cDigits, PjllLSB, IndexLSB);			\
	}

// JSLE_ODD is completely different from JSLE_EVEN because its important to
// minimize copying odd indexes to compare them (see 4.14).  Furthermore, a
// very complex version (4.17, but abandoned before fully debugged) that
// avoided calling j__udySearchLeaf*() ran twice as fast as 4.14, but still
// half as fast as SearchValid.  Doug suggested that to minimize complexity and
// share common code we should use j__udySearchLeaf*() for the initial search
// to establish if Index is empty, which should be common.  If Index is valid
// in a leaf or immediate indexes, odds are good that an empty Index is nearby,
// so for simplicity just use a *COPY* function to linearly search the
// remainder.
//
// TBD:  Pathological case?  Average performance should be good, but worst-case
// might suffer.  When Search says the initial Index is valid, so a linear
// copy-and-compare is begun, if the caller builds fairly large leaves with
// dense clusters AND frequently does a SearchEmpty at one end of such a
// cluster, performance wont be very good.  Might a dense-check help?  This
// means checking offset against the index at offset, and then against the
// first/last index in the leaf.  We doubt the pathological case will appear
// much in real applications because they will probably alternate SearchValid
// and SearchEmpty calls.

#define	JSLE_ODD(cDigits,Pjll,Pop0,Search,Copy)				\
	{								\
	    Word_t IndexLSB;		/* least bytes only */		\
	    Word_t IndexFound;		/* in leaf	    */		\
									\
	    if ((offset = Search(Pjll, (Pop0) + 1, Index)) < 0)		\
		RET_SUCCESS;		/* Index is empty */		\
									\
	    IndexLSB = JU_LEASTBYTES(Index, cDigits);			\
	    offset  *= (cDigits);					\
									\
	    while ((offset -= (cDigits)) >= 0)				\
	    {				/* skip until empty or start */	\
		Copy(IndexFound, ((uint8_t *) (Pjll)) + offset);	\
		if (IndexFound != (--IndexLSB))	/* found an empty */	\
		{ JU_SETDIGITS(Index, IndexLSB, cDigits); RET_SUCCESS; }\
	    }								\
	    LEAF_EDGE_SET(IndexLSB, cDigits);				\
	}

#else // JUDYNEXT

#define	JSLE_EVEN(Addr,Pop0,cDigits,LeafType)				\
	{								\
	    LeafType * PjllLSB   = ((LeafType *) (Addr)) + (Pop0);	\
	    LeafType   IndexLSB = Index;	/* auto-masking */	\
									\
	/* Index at or after end of leaf: */				\
									\
	    if (*PjllLSB <= IndexLSB)		/* no need to search */	\
	    {								\
		if (*PjllLSB < IndexLSB) RET_SUCCESS;  /* Index empty */\
		LEAF_EDGE(*PjllLSB, cDigits);				\
	    }								\
									\
	/* Index before or in leaf: */					\
									\
	    offset = *PjllLSB - IndexLSB;	/* tentative offset  */	\
	    if (offset <= (Pop0))		/* can check density */	\
	    {								\
		PjllLSB -= offset;		/* move to slot */	\
									\