Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
// This program is free software; you can redistribute it and/or modify it
// under the term of the GNU Lesser General Public License as published by the
// Free Software Foundation; either version 2 of the License, or (at your
// option) any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
// for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with this program; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
// _________________
// @(#) $Revision: 4.54 $ $Source: /judy/src/JudyCommon/JudyPrevNext.c $
//
// Judy*Prev() and Judy*Next() functions for Judy1 and JudyL.
// Compile with one of -DJUDY1 or -DJUDYL.
//
// Compile with -DJUDYNEXT for the Judy*Next() function; otherwise defaults to
// Judy*Prev().
#if (! (defined(JUDY1) || defined(JUDYL)))
#error: One of -DJUDY1 or -DJUDYL must be specified.
#endif
#ifndef JUDYNEXT
#ifndef JUDYPREV
#define JUDYPREV 1 // neither set => use default.
#endif
#endif
#ifdef JUDY1
#include "Judy1.h"
#else
#include "JudyL.h"
#endif
#include "JudyPrivate1L.h"
// ****************************************************************************
// J U D Y 1 P R E V
// J U D Y 1 N E X T
// J U D Y L P R E V
// J U D Y L N E X T
//
// See the manual entry for the API.
//
// OVERVIEW OF Judy*Prev():
//
// Use a reentrant switch statement (state machine, SM1 = "get") to decode the
// callers *PIndex-1, starting with the (PArray), through branches, if
// any, down to an immediate or a leaf. Look for *PIndex-1 in that leaf, and
// if found, return it.
//
// A dead end is either a branch that does not contain a JP for the appropriate
// digit in *PIndex-1, or a leaf that does not contain the undecoded digits of
// *PIndex-1. Upon reaching a dead end, backtrack through the leaf/branches
// that were just traversed, using a list (history) of parent JPs that is built
// while going forward in SM1Get. Start with the current leaf or branch. In a
// backtracked leaf, look for an Index less than *PIndex-1. In each
// backtracked branch, look "sideways" for the next JP, if any, lower than the
// one for the digit (from *PIndex-1) that was previously decoded. While
// backtracking, if a leaf has no previous Index or a branch has no lower JP,
// go to its parent branch in turn. Upon reaching the JRP, return failure, "no
// previous Index". The backtrack process is sufficiently different from
// SM1Get to merit its own separate reentrant switch statement (SM2 =
// "backtrack").
//
// While backtracking, upon finding a lower JP in a branch, there is certain to
// be a "prev" Index under that JP (unless the Judy array is corrupt).
// Traverse forward again, this time taking the last (highest, right-most) JP
// in each branch, and the last (highest) Index upon reaching an immediate or a
// leaf. This traversal is sufficiently different from SM1Get and SM2Backtrack
// to merit its own separate reentrant switch statement (SM3 = "findlimit").
//
// "Decode" bytes in JPs complicate this process a little. In SM1Get, when a
// JP is a narrow pointer, that is, when states are skipped (so the skipped
// digits are stored in jp_DcdPopO), compare the relevant digits to the same
// digits in *PIndex-1. If they are EQUAL, proceed in SM1Get as before. If
// jp_DcdPopOs digits are GREATER, treat the JP as a dead end and proceed in
// SM2Backtrack. If jp_DcdPopOs digits are LESS, treat the JP as if it had
// just been found during a backtrack and proceed directly in SM3Findlimit.
//
// Note that Decode bytes can be ignored in SM3Findlimit; they dont matter.
// Also note that in practice the Decode bytes are routinely compared with
// *PIndex-1 because thats simpler and no slower than first testing for
// narrowness.
//
// Decode bytes also make it unnecessary to construct the Index to return (the
// revised *PIndex) during the search. This step is deferred until finding an
// Index during backtrack or findlimit, before returning it. The first digit
// of *PIndex is derived (saved) based on which JP is used in a JRP branch.
// The remaining digits are obtained from the jp_DcdPopO field in the JP (if
// any) above the immediate or leaf containing the found (prev) Index, plus the
// remaining digit(s) in the immediate or leaf itself. In the case of a LEAFW,
// the Index to return is found directly in the leaf.
//
// Note: Theoretically, as described above, upon reaching a dead end, SM1Get
// passes control to SM2Backtrack to look sideways, even in a leaf. Actually
// its a little more efficient for the SM1Get leaf cases to shortcut this and
// take care of the sideways searches themselves. Hence the history list only
// contains branch JPs, and SM2Backtrack only handles branches. In fact, even
// the branch handling cases in SM1Get do some shortcutting (sideways
// searching) to avoid pushing history and calling SM2Backtrack unnecessarily.
//
// Upon reaching an Index to return after backtracking, *PIndex must be
// modified to the found Index. In principle this could be done by building
// the Index from a saved rootdigit (in the top branch) plus the Dcd bytes from
// the parent JP plus the appropriate Index bytes from the leaf. However,
// Immediates are difficult because their parent JPs lack one (last) digit. So
// instead just build the *PIndex to return "top down" while backtracking and
// findlimiting.
//
// This function is written iteratively for speed, rather than recursively.
//
// 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);) \
}
#define HISTPOP(Pjp,Offset) \
if ((histnum--) < 1) JU_RET_NOTFOUND; \
(Pjp) = APjphist[histnum]; \
(Offset) = Aoffhist[histnum]
// How to pack/unpack Aoffhist[] values for bitmap branches:
#ifdef JUDYPREV
#define HISTPUSHBOFF(Subexp,Offset,Digit) \
(((Subexp) * cJU_BITSPERSUBEXPB) | (Offset))
#define HISTPOPBOFF(Subexp,Offset,Digit) \
(Subexp) = (Offset) / cJU_BITSPERSUBEXPB; \
(Offset) %= cJU_BITSPERSUBEXPB
#else
src/judy-1.0.5/src/JudyCommon/JudyPrevNext.c view on Meta::CPAN
}
else // JRP BRANCH
{
Pjpm_t Pjpm = P_JPM(PArray);
Pjp = &(Pjpm->jpm_JP);
// goto SM1Get;
}
// ============================================================================
// STATE MACHINE 1 -- GET INDEX:
//
// Search for *PIndex (already decremented/incremented so as to be inclusive).
// If found, return it. Otherwise in theory hand off to SM2Backtrack or
// SM3Findlimit, but in practice "shortcut" by first sideways searching the
// current branch or leaf upon hitting a dead end. During sideways search,
// modify *PIndex to a new path taken.
//
// ENTRY: Pjp points to next JP to interpret, whose Decode bytes have not yet
// been checked. This JP is not yet listed in history.
//
// Note: Check Decode bytes at the start of each loop, not after looking up a
// new JP, so its easy to do constant shifts/masks, although this requires
// cautious handling of Pjp, offset, and *hist[] for correct entry to
// SM2Backtrack.
//
// EXIT: Return, or branch to SM2Backtrack or SM3Findlimit with correct
// interface, as described elsewhere.
//
// WARNING: For run-time efficiency the following cases replicate code with
// varying constants, rather than using common code with variable values!
SM1Get: // return here for next branch/leaf.
switch (JU_JPTYPE(Pjp))
{
// ----------------------------------------------------------------------------
// LINEAR BRANCH:
//
// Check Decode bytes, if any, in the current JP, then search for a JP for the
// next digit in *PIndex.
case cJU_JPBRANCH_L2: CHECKDCD(2); SM1PREPB(2, SM1BranchL);
case cJU_JPBRANCH_L3: CHECKDCD(3); SM1PREPB(3, SM1BranchL);
#ifdef JU_64BIT
case cJU_JPBRANCH_L4: CHECKDCD(4); SM1PREPB(4, SM1BranchL);
case cJU_JPBRANCH_L5: CHECKDCD(5); SM1PREPB(5, SM1BranchL);
case cJU_JPBRANCH_L6: CHECKDCD(6); SM1PREPB(6, SM1BranchL);
case cJU_JPBRANCH_L7: CHECKDCD(7); SM1PREPB(7, SM1BranchL);
#endif
case cJU_JPBRANCH_L: SM1PREPB(cJU_ROOTSTATE, SM1BranchL);
// Common code (state-independent) for all cases of linear branches:
SM1BranchL:
Pjbl = P_JBL(Pjp->jp_Addr);
// Found JP matching current digit in *PIndex; record parent JP and the next
// JPs offset, and iterate to the next JP:
if ((offset = j__udySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse),
Pjbl->jbl_NumJPs, digit)) >= 0)
{
HISTPUSH(Pjp, offset);
Pjp = (Pjbl->jbl_jp) + offset;
goto SM1Get;
}
// Dead end, no JP in BranchL for next digit in *PIndex:
//
// Get the ideal location of digits JP, and if theres no next-left/right JP
// in the BranchL, shortcut and start backtracking one level up; ignore the
// current Pjp because it points to a BranchL with no next-left/right JP.
#ifdef JUDYPREV
if ((offset = (~offset) - 1) < 0) // no next-left JP in BranchL.
#else
if ((offset = (~offset)) >= Pjbl->jbl_NumJPs) // no next-right.
#endif
goto SM2Backtrack;
// Theres a next-left/right JP in the current BranchL; save its digit in
// *PIndex and shortcut to SM3Findlimit:
JU_SETDIGIT(*PIndex, Pjbl->jbl_Expanse[offset], state);
Pjp = (Pjbl->jbl_jp) + offset;
goto SM3Findlimit;
// ----------------------------------------------------------------------------
// BITMAP BRANCH:
//
// Check Decode bytes, if any, in the current JP, then look for a JP for the
// next digit in *PIndex.
case cJU_JPBRANCH_B2: CHECKDCD(2); SM1PREPB(2, SM1BranchB);
case cJU_JPBRANCH_B3: CHECKDCD(3); SM1PREPB(3, SM1BranchB);
#ifdef JU_64BIT
case cJU_JPBRANCH_B4: CHECKDCD(4); SM1PREPB(4, SM1BranchB);
case cJU_JPBRANCH_B5: CHECKDCD(5); SM1PREPB(5, SM1BranchB);
case cJU_JPBRANCH_B6: CHECKDCD(6); SM1PREPB(6, SM1BranchB);
case cJU_JPBRANCH_B7: CHECKDCD(7); SM1PREPB(7, SM1BranchB);
#endif
case cJU_JPBRANCH_B: SM1PREPB(cJU_ROOTSTATE, SM1BranchB);
// Common code (state-independent) for all cases of bitmap branches:
SM1BranchB:
Pjbb = P_JBB(Pjp->jp_Addr);
// Locate the digits JP in the subexpanse list, if present, otherwise the
// offset of the next-left JP, if any:
subexp = digit / cJU_BITSPERSUBEXPB;
assert(subexp < cJU_NUMSUBEXPB); // falls in expected range.
bitposmask = JU_BITPOSMASKB(digit);
offset = SEARCHBITMAPB(JU_JBB_BITMAP(Pjbb, subexp), digit,
bitposmask);
// right range:
assert((offset >= -1) && (offset < (int) cJU_BITSPERSUBEXPB));
// Found JP matching current digit in *PIndex:
//
// Record the parent JP and the next JPs offset; and iterate to the next JP.
// if (JU_BITMAPTESTB(Pjbb, digit)) // slower.
if (JU_JBB_BITMAP(Pjbb, subexp) & bitposmask) // faster.
{
// not negative since at least one bit is set:
assert(offset >= 0);
HISTPUSH(Pjp, HISTPUSHBOFF(subexp, offset, digit));
if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
JUDY1CODE(return(JERRI );)
JUDYLCODE(return(PPJERR);)
}
Pjp += offset;
goto SM1Get; // iterate to next JP.
}
// Dead end, no JP in BranchB for next digit in *PIndex:
//
// If theres a next-left/right JP in the current BranchB, shortcut to
// SM3Findlimit. Note: offset is already set to the correct value for the
// next-left/right JP.
#ifdef JUDYPREV
if (offset >= 0) // next-left JP is in this subexpanse.
goto SM1BranchBFindlimit;
while (--subexp >= 0) // search next-left subexpanses.
#else
if (JU_JBB_BITMAP(Pjbb, subexp) & JU_MASKHIGHEREXC(bitposmask))
{
++offset; // next-left => next-right.
goto SM1BranchBFindlimit;
}
while (++subexp < cJU_NUMSUBEXPB) // search next-right subexps.
#endif
{
if (! JU_JBB_PJP(Pjbb, subexp)) continue; // empty subexpanse.
#ifdef JUDYPREV
offset = SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp));
// expected range:
assert((offset >= 0) && (offset < cJU_BITSPERSUBEXPB));
#else
offset = 0;
#endif
// Save the next-left/right JPs digit in *PIndex:
SM1BranchBFindlimit:
JU_BITMAPDIGITB(digit, subexp, JU_JBB_BITMAP(Pjbb, subexp),
offset);
JU_SETDIGIT(*PIndex, digit, state);
if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
JUDY1CODE(return(JERRI );)
JUDYLCODE(return(PPJERR);)
}
Pjp += offset;
goto SM3Findlimit;
}
// Theres no next-left/right JP in the BranchB:
//
// Shortcut and start backtracking one level up; ignore the current Pjp because
// it points to a BranchB with no next-left/right JP.
goto SM2Backtrack;
// ----------------------------------------------------------------------------
// UNCOMPRESSED BRANCH:
//
// Check Decode bytes, if any, in the current JP, then look for a JP for the
// next digit in *PIndex.
case cJU_JPBRANCH_U2: CHECKDCD(2); SM1PREPB(2, SM1BranchU);
case cJU_JPBRANCH_U3: CHECKDCD(3); SM1PREPB(3, SM1BranchU);
#ifdef JU_64BIT
case cJU_JPBRANCH_U4: CHECKDCD(4); SM1PREPB(4, SM1BranchU);
case cJU_JPBRANCH_U5: CHECKDCD(5); SM1PREPB(5, SM1BranchU);
case cJU_JPBRANCH_U6: CHECKDCD(6); SM1PREPB(6, SM1BranchU);
case cJU_JPBRANCH_U7: CHECKDCD(7); SM1PREPB(7, SM1BranchU);
#endif
case cJU_JPBRANCH_U: SM1PREPB(cJU_ROOTSTATE, SM1BranchU);
// Common code (state-independent) for all cases of uncompressed branches:
SM1BranchU:
Pjbu = P_JBU(Pjp->jp_Addr);
Pjp2 = (Pjbu->jbu_jp) + digit;
// Found JP matching current digit in *PIndex:
//
// Record the parent JP and the next JPs digit, and iterate to the next JP.
//
// TBD: Instead of this, just goto SM1Get, and add cJU_JPNULL* cases to the
// SM1Get state machine? Then backtrack? However, it means you cant detect
// an inappropriate cJU_JPNULL*, when it occurs in other than a BranchU, and
// return JU_RET_CORRUPT.
if (! JPNULL(JU_JPTYPE(Pjp2))) // digit has a JP.
{
HISTPUSH(Pjp, digit);
Pjp = Pjp2;
goto SM1Get;
}
// Dead end, no JP in BranchU for next digit in *PIndex:
//
// Search for a next-left/right JP in the current BranchU, and if one is found,
// save its digit in *PIndex and shortcut to SM3Findlimit:
#ifdef JUDYPREV
while (digit >= 1)
{
Pjp = (Pjbu->jbu_jp) + (--digit);
#else
while (digit < cJU_BRANCHUNUMJPS - 1)
{
Pjp = (Pjbu->jbu_jp) + (++digit);
#endif
if (JPNULL(JU_JPTYPE(Pjp))) continue;
JU_SETDIGIT(*PIndex, digit, state);
goto SM3Findlimit;
}
// Theres no next-left/right JP in the BranchU:
//
// Shortcut and start backtracking one level up; ignore the current Pjp because
// it points to a BranchU with no next-left/right JP.
goto SM2Backtrack;
// ----------------------------------------------------------------------------
// LINEAR LEAF:
//
// Check Decode bytes, if any, in the current JP, then search the leaf for
// *PIndex.
#define SM1LEAFL(Func) \
Pjll = P_JLL(Pjp->jp_Addr); \
pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
offset = Func(Pjll, pop1, *PIndex); \
goto SM1LeafLImm
#if (defined(JUDYL) || (! defined(JU_64BIT)))
case cJU_JPLEAF1: CHECKDCD(1); SM1LEAFL(j__udySearchLeaf1);
#endif
case cJU_JPLEAF2: CHECKDCD(2); SM1LEAFL(j__udySearchLeaf2);
case cJU_JPLEAF3: CHECKDCD(3); SM1LEAFL(j__udySearchLeaf3);
#ifdef JU_64BIT
( run in 1.168 second using v1.01-cache-2.11-cpan-2398b32b56e )