view release on metacpan or  search on metacpan

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

// Copyright (C) 2000 - 2002 Hewlett-Packard Company
//
// 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.