Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
// DELETE BELOW NON-LAST INDEX WORD IN CURRENT JUDYL ARRAY:
//
// If a word before the end of the full Index is present in the current JudyL
// array, recurse through its value, which must be a pointer to another JudyL
// array, to continue the deletion at the next level. Return the JudyLGet()
// return if the Indexs current word is not in the JudyL array, or if no
// delete occurs below this level, both of which mean the whole Index is not
// currently valid.
//
JLG(PPValue, *PPArray, indexword);
if (PPValue == (PPvoid_t) NULL)
return (0); // Index not in JudySL array.
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25).
if ((retcode =
JudySLDelSub(PPValue, PPArrayOrig, Index + WORDSIZE,
len - WORDSIZE, PJError)) != 1)
{
return (retcode); // no lower-level delete, or error.
}
// DELETE EMPTY JUDYL ARRAY:
//
// A delete occurred below in the tree. If the child JudyL array became empty,
// delete the current Index word from the current JudyL array, which could
// empty the current array and null out *PPArray in turn (or pass through an
// error). Otherwise simply indicate that a deletion did occur.
if (*PPValue == (Pvoid_t)NULL)
{
if ((retcode = JudyLDel(PPArray, indexword, PJError)) == JERR)
{
JudySLModifyErrno(PJError, *PPArray, *PPArrayOrig);
return (JERR);
}
return (retcode);
}
return (1);
} // JudySLDelSub()
// ****************************************************************************
// J U D Y S L P R E V
//
// Recursively traverse the JudySL tree downward using JudyLGet() to look for
// each successive index word from Index in the JudyL array at each level. At
// the last level for the Index (LASTWORD_BY_LEN()), use JudyLPrev() instead of
// JudyLGet(), to exclude the initial Index. If this doesnt result in finding
// a previous Index, work back up the tree using JudyLPrev() at each higher
// level to search for a previous index word. Upon finding a previous index
// word, descend again if/as necessary, this time inclusively, to find and
// return the full previous Index.
//
// Also support shortcut leaves.
//
// Since this function is recursive and it also needs to know if its still
// looking for the original Index (to exclude it at the LASTWORD_BY_LEN()
// level) or for the remaining words of the previous Index (inclusive),
// actually call a subroutine that takes an additional parameter.
//
// See also the technical notes in JudySLDel() regarding the use of recursion
// rather than iteration.
PPvoid_t
JudySLPrev(Pcvoid_t PArray, uint8_t * Index, PJError_t PJError) // optional, for returning error info.
{
// Check for caller error (null pointer), or empty JudySL array:
if (Index == (uint8_t *) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
return (PPJERR);
}
if (PArray == (Pvoid_t)NULL)
return ((PPvoid_t) NULL);
// Do the search:
return (JudySLPrevSub(PArray, Index, /* original = */ 1,
STRLEN(Index), PJError));
} // JudySLPrev()
// ****************************************************************************
// J U D Y S L P R E V S U B
//
// This is the "engine" for JudySLPrev() that knows whether its still looking
// for the original Index (exclusive) or a neighbor index (inclusive), and that
// expects aligned and len to already be computed (only once). See the header
// comments for JudySLPrev().
static PPvoid_t
JudySLPrevSub(Pcvoid_t PArray, uint8_t * Index, int orig,
Word_t len, // bytes remaining.
PJError_t PJError) // optional, for returning error info.
{
Word_t indexword; // next word to find.
PPvoid_t PPValue; // from JudyL array.
// ORIGINAL SEARCH:
//
// When at a shortcut leaf, copy its remaining Index (string) chars into Index
// and return its value area if the current Index is after (greater than) the
// SCLs index; otherwise return null.
if (orig)
{
if (IS_PSCL(PArray))
{
if ((PPValue = PPSCLVALUE_GT(Index, PArray)) != (PPvoid_t) NULL)
(void)STRCPY(Index, PSCLINDEX(PArray));
return (PPValue);
}
// If the current Index word:
// - is not the last word in Index (end of string),
// - exists in the current JudyL array, and,
// - a previous Index is found below it, return that Indexs value area.
COPYSTRINGtoWORD(indexword, Index); // copy next 4[8] bytes.
if (len > WORDSIZE) // not at end of Index.
{
JLG(PPValue, PArray, indexword);
if (PPValue != (PPvoid_t) NULL)
{
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25):
PPValue = JudySLPrevSub(*PPValue, Index + WORDSIZE,
/* original = */ 1,
len - WORDSIZE, PJError);
if (PPValue == PPJERR)
return (PPJERR); // propagate error.
if (PPValue != (PPvoid_t) NULL)
return (PPValue); // see above.
}
}
// Search for previous index word:
//
// One of the above conditions is false. Search the current JudyL array for
// the Index word, if any, prior to the current index word. If none is found,
// return null; otherwise fall through to common later code.
if ((PPValue = JudyLPrev(PArray, &indexword, PJError)) == PPJERR)
{
JudySLModifyErrno(PJError, PArray, orig ? PArray : (Pvoid_t)NULL);
return (PPJERR);
}
if (PPValue == (PPvoid_t) NULL)
return ((PPvoid_t) NULL); // no previous index word.
} // if.
// SUBSEQUENT SEARCH:
//
// A higher level search already excluded the initial Index, then found a
// previous index word, and is now traversing down to determine the rest of the
// Index and to obtain its value area. If at a shortcut leaf, return its value
// area. Otherwise search the current JudyL array backward from the upper
// limit for its last index word. If no index word is found, return null --
// should never happen unless the JudySL tree is corrupt; otherwise fall
// through to common later code.
else
{
if (IS_PSCL(PArray)) // at shortcut leaf.
{
(void)STRCPY(Index, PSCLINDEX(PArray));
return (&PSCLVALUE(PArray));
}
indexword = ~0UL;
if ((PPValue = JudyLLast(PArray, &indexword, PJError)) == PPJERR)
{
JudySLModifyErrno(PJError, PArray, orig ? PArray : (Pvoid_t)NULL);
return (PPJERR);
}
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25):
if (PPValue == (PPvoid_t) NULL)
return ((PPvoid_t) NULL); // no previous index word.
}
// FOUND PREVIOUS INDEX WORD:
//
// A previous (if original) or last (if subsequent) index word was located in
// the current JudyL array. Store it into the callers Index (string). Then
// if the found (previous) Index ends here, return its value area; otherwise do
// a subsequent search below this point, which should never fail unless the
// JudySL tree is corrupt, but this is detected at a lower level by the above
// assertion.
//
// Note: Treat Index as unaligned, even if it is aligned, to avoid writing
// past the end of allocated memory (in case its less than a whole number of
// words).
COPYWORDtoSTRING(Index, indexword); // copy next 4[8] bytes.
if (LASTWORD_BY_VALUE(indexword))
return (PPValue);
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25):
return (JudySLPrevSub(*PPValue, Index + WORDSIZE, /* original = */ 0,
len - WORDSIZE, PJError));
} // JudySLPrevSub()
// ****************************************************************************
// J U D Y S L N E X T
//
// See the comments in JudySLPrev(), which is very similar.
//
// TBD: Could the two functions call a common engine function with various
// subfunctions and other constants specified?
PPvoid_t
JudySLNext(Pcvoid_t PArray, uint8_t * Index, PJError_t PJError) // optional, for returning error info.
{
// Check for caller error (null pointer), or empty JudySL array:
if (Index == (uint8_t *) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
return (PPJERR);
}
if (PArray == (Pvoid_t)NULL)
return ((PPvoid_t) NULL);
// Do the search:
return (JudySLNextSub(PArray, Index, /* original = */ 1,
STRLEN(Index), PJError));
} // JudySLNext()
// ****************************************************************************
// J U D Y S L N E X T S U B
//
// See the comments in JudySLPrevSub(), which is very similar.
static PPvoid_t
JudySLNextSub(Pcvoid_t PArray, uint8_t * Index, int orig,
Word_t len, // bytes remaining.
PJError_t PJError) // optional, for returning error info.
{
Word_t indexword; // next word to find.
PPvoid_t PPValue; // from JudyL array.
if (orig)
{
if (IS_PSCL(PArray))
{
if ((PPValue = PPSCLVALUE_LT(Index, PArray)) != (PPvoid_t) NULL)
(void)STRCPY(Index, PSCLINDEX(PArray));
return (PPValue);
}
COPYSTRINGtoWORD(indexword, Index); // copy next 4[8] bytes.
if (len > WORDSIZE) // not at end of Index.
{
JLG(PPValue, PArray, indexword);
if (PPValue != (PPvoid_t) NULL)
{
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25):
PPValue = JudySLNextSub(*PPValue, Index + WORDSIZE,
/* original = */ 1,
len - WORDSIZE, PJError);
if (PPValue == PPJERR)
return (PPJERR); // propagate error.
if (PPValue != (PPvoid_t) NULL)
return (PPValue); // see above.
}
}
if ((PPValue = JudyLNext(PArray, &indexword, PJError)) == PPJERR)
{
JudySLModifyErrno(PJError, PArray, orig ? PArray : (Pvoid_t)NULL);
return (PPJERR);
}
if (PPValue == (PPvoid_t) NULL)
return ((PPvoid_t) NULL); // no next index word.
}
else
{
if (IS_PSCL(PArray)) // at shortcut leaf.
{
(void)STRCPY(Index, PSCLINDEX(PArray));
return (&PSCLVALUE(PArray));
}
indexword = 0;
if ((PPValue = JudyLFirst(PArray, &indexword, PJError)) == PPJERR)
{
JudySLModifyErrno(PJError, PArray, orig ? PArray : (Pvoid_t)NULL);
return (PPJERR);
}
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25):
if (PPValue == (PPvoid_t) NULL)
return ((PPvoid_t) NULL); // no next index word.
}
COPYWORDtoSTRING(Index, indexword); // copy next 4[8] bytes
if (LASTWORD_BY_VALUE(indexword))
return (PPValue);
// If a previous JudySLIns() ran out of memory partway down the tree, it left a
// null *PPValue; this is automatically treated as a dead-end (not a core dump
// or assertion; see version 1.25):
return (JudySLNextSub(*PPValue, Index + WORDSIZE, /* original = */ 0,
len - WORDSIZE, PJError));
} // JudySLNextSub()
// ****************************************************************************
// J U D Y S L F I R S T
//
// Like JudyLFirst(), do a JudySLGet(), then if necessary a JudySLNext().
PPvoid_t
JudySLFirst(Pcvoid_t PArray, uint8_t * Index, PJError_t PJError) // optional, for returning error info.
{
PPvoid_t PPValue; // from JudyL array.
if (Index == (uint8_t *) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
return (PPJERR);
}
if ((PPValue = JudySLGet(PArray, Index, PJError)) == PPJERR)
return (PPJERR); // propagate serious error.
if ((PPValue == (PPvoid_t) NULL) // first try failed.
&& ((PPValue = JudySLNext(PArray, Index, PJError)) == PPJERR))
{
return (PPJERR); // propagate serious error.
}
return (PPValue);
} // JudySLFirst()
// ****************************************************************************
// J U D Y S L L A S T
//
// Like JudyLLast(), do a JudySLGet(), then if necessary a JudySLPrev().
PPvoid_t
JudySLLast(Pcvoid_t PArray, uint8_t * Index, PJError_t PJError) // optional, for returning error info.
{
PPvoid_t PPValue; // from JudyL array.
if (Index == (uint8_t *) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
return (PPJERR);
}
if ((PPValue = JudySLGet(PArray, Index, PJError)) == PPJERR)
return (PPJERR); // propagate serious error.
if ((PPValue == (PPvoid_t) NULL) // first try failed.
&& ((PPValue = JudySLPrev(PArray, Index, PJError)) == PPJERR))
{
return (PPJERR); // propagate serious error.
}
return (PPValue);
} // JudySLLast()
// ****************************************************************************
// J U D Y S L F R E E A R R A Y
//
// Walk the JudySL tree of JudyL arrays to free each JudyL array, depth-first.
// During the walk, ignore indexes (strings) that end in the current JudyL
( run in 1.575 second using v1.01-cache-2.11-cpan-e1769b4cff6 )