Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
// a reliable way to tell that the pointer is not a root pointer to another
// JudyL array, it should save a lot of time to instead point to a "leaf"
// object, similar to leaves in JudyL arrays.
//
// TBD: Multi-index leaves, like those in JudyL, are also worth considering,
// but their payback for JudySL is less certain. Likewise, shortcut branches
// are worth considering too.
//
// This code uses the Judy.h definitions and Doug Baskins convention of a "P"
// prefix for pointers, except no "P" for the first level of char * (strings).
// IMPORTS:
#include <string.h> // for strcmp(), strlen(), strcpy()
#include <Judy.h>
#ifndef NDEDUG
#define NDEBUG 1
#endif
#include <assert.h>
//=======================================================================
// Compile:
//
// cc -O JudyHS.c -c
//
// Notes:
// 1) use -DJU_64BIT for 64 bit compiles (HP, Sun, IPF, Motorola/IBM? etc..)
// 2) In gcc version 3.3.1 for a Centrino, -O2 is faster than -O
// 3) In gcc version 3.3.2 for a Centrino, -O3 is faster than -O2
//=======================================================================
#define JU_SET_ERRNO(PJERROR, JERRNO) \
{ \
if (PJERROR != (PJError_t)NULL) \
{ \
JU_ERRNO(PJERROR) = (JERRNO); \
JU_ERRID(PJERROR) = __LINE__; \
} \
}
#define JU_SET_ERRNO_NONNULL(PJERROR, JERRNO) \
{ \
JU_ERRNO(PJERROR) = (JERRNO); \
JU_ERRID(PJERROR) = __LINE__; \
}
// SUPPORT FOR HANDLING WORDS:
#define WORDSIZE (sizeof (Word_t)) // bytes in word = JudyL index.
#define WORDS(BYTES) (((BYTES) + WORDSIZE - 1) / WORDSIZE) // round up.
// To mark a pointer is to a "short cut leaf", set least bit
#define IS_PSCL(PSCL) (((Word_t) (PSCL)) & JLAP_INVALID)
#define CLEAR_PSCL(PSCL) ((Pscl_t)(((Word_t) (PSCL)) & (~JLAP_INVALID)))
#define SET_PSCL(PSCL) (((Word_t) (PSCL)) | JLAP_INVALID)
// MISCELLANEOUS GLOBALS:
// Get the Index (string) length in bytes, including the trailing \0, which
// is an integral part of the string:
// A string is "in the last word" if a previously-set byte count is at or below
// the system word size, or in some cases if the last byte in the (null-padded)
// word is null (assume big-endian, including in a register on a little-endian
// machine):
#define LASTWORD_BY_VALUE(WORD) (! ((WORD) & 0xffL))
#ifdef JU_64BIT
// copy from 1..7 bytes from string to Word_t and test if \0 bytes
//
#define COPYSTRINGtoWORD(WORD,STR) \
{ \
do \
{ \
uint8_t chr; \
WORD = (Word_t)(STR)[0] << 56; \
if (!(WORD)) break; \
if (!(chr = (STR)[1])) break; \
WORD += ((Word_t)(chr) << 48); \
if (!(chr = (STR)[2])) break; \
WORD += ((Word_t)(chr) << 40); \
if (!(chr = (STR)[3])) break; \
WORD += ((Word_t)(chr) << 32); \
if (!(chr = (STR)[4])) break; \
WORD += ((Word_t)(chr) << 24); \
if (!(chr = (STR)[5])) break; \
WORD += ((Word_t)(chr) << 16); \
if (!(chr = (STR)[6])) break; \
WORD += ((Word_t)(chr) << 8) + (STR)[7]; \
} while(0); \
}
// copy Word_t from 1..8 bytes to string and test of \0 bytes
//
#define COPYWORDtoSTRING(STR,WORD) \
{ \
do \
{ \
if (!((STR)[0] = (uint8_t)((WORD) >> 56))) break; \
if (!((STR)[1] = (uint8_t)((WORD) >> 48))) break; \
if (!((STR)[2] = (uint8_t)((WORD) >> 40))) break; \
if (!((STR)[3] = (uint8_t)((WORD) >> 32))) break; \
if (!((STR)[4] = (uint8_t)((WORD) >> 24))) break; \
if (!((STR)[5] = (uint8_t)((WORD) >> 16))) break; \
if (!((STR)[6] = (uint8_t)((WORD) >> 8))) break; \
(STR)[7] = (uint8_t)(WORD); \
} while(0); \
}
#else // JU_32BIT
// copy from 1..4 bytes from string to Word_t and test if \0 bytes
#define COPYSTRINGtoWORD(WORD,STR) \
{ \
do \
{ \
uint8_t chr; \
WORD = (STR)[0] << 24; \
if (WORD == 0) break; \
if (!(chr = (STR)[1])) break; \
WORD += (Word_t)(chr << 16); \
if (!(chr = (STR)[2])) break; \
WORD += (Word_t)(chr << 8) + (STR)[3]; \
} while(0); \
}
// copy Word_t from 1..4 bytes to string and test of \0 bytes
#define COPYWORDtoSTRING(STR,WORD) \
{ \
do \
{ \
if (!((STR)[0] = (uint8_t)((WORD) >> 24))) break; \
if (!((STR)[1] = (uint8_t)((WORD) >> 16))) break; \
if (!((STR)[2] = (uint8_t)((WORD) >> 8))) break; \
(STR)[3] = (uint8_t)(WORD); \
} while(0); \
}
#endif // JU_32BIT
// SUPPORT FOR SINGLE-INDEX SHORTCUT LEAVES:
typedef struct SHORCUTLEAF
{
Pvoid_t scl_Pvalue; // callers value area.
uint8_t scl_Index[WORDSIZE]; // base Index string.
} scl_t , *Pscl_t;
// overhead of the scl_Pvalue only, the scl_Index is calculate elsewhere
#define STRUCTOVD (sizeof(scl_t) - WORDSIZE)
// How big to malloc a shortcut leaf; stringlen should already include the
// trailing null char:
#define SCLSIZE(LEN) (((LEN) + STRUCTOVD + WORDSIZE - 1) / WORDSIZE)
// string routines, may replace with your own
//
#define STRCMP(S1,S2) strcmp((void *)(S1), (void *)(S2))
#define STRCPY(S1,S2) strcpy((void *)(S1), (void *)(S2))
#define STRLEN(S1) (strlen((void *)(S1)) + 1)
// Index and value area for a shortcut leaf, depending on how it matches the
// undecoded remainder of the Index, given a Pscl_t that includes type bits
// that must be cleared:
//
// PSCLINDEX() and PSCLVALUE() are also useful when Pscl contains uncleared
// TYPE bits.
//
// Note: SCLCMP() cannot take advantage of knowing the Index length because
// the scl_Index length is not pre-known when these macros are used.
#define PSCLINDEX(PSCL) ((CLEAR_PSCL(PSCL))->scl_Index)
#define PSCLVALUE(PSCL) ((CLEAR_PSCL(PSCL))->scl_Pvalue)
#define SCLCMP(INDEX,PSCL) STRCMP(INDEX, PSCLINDEX(PSCL))
#define PPSCLVALUE_EQ(INDEX,PSCL) \
((SCLCMP(INDEX, PSCL) == 0) ? &PSCLVALUE(PSCL) : (PPvoid_t)NULL)
#define PPSCLVALUE_LT(INDEX,PSCL) \
((SCLCMP(INDEX, PSCL) < 0) ? &PSCLVALUE(PSCL) : (PPvoid_t)NULL)
#define PPSCLVALUE_GT(INDEX,PSCL) \
((SCLCMP(INDEX, PSCL) > 0) ? &PSCLVALUE(PSCL) : (PPvoid_t)NULL)
// Common in-lined code to append or free a shortcut leaf:
//
// See header comments about premature return(). Note that malloc() does not
// pre-zero the memory, so ensure scl_Pvalue is zeroed, just like a value area
// in a JudyL array. Hope strcpy() is fast enough in this context.
#define APPEND_SCL(PSCL,PPARRAY,INDEX,LEN,PJERROR) \
{ \
if (((PSCL) = (Pscl_t) JudyMalloc(SCLSIZE(LEN))) == (Pscl_t)NULL) \
{ \
JU_SET_ERRNO(PJERROR, JU_ERRNO_NOMEM); \
return (PPJERR); \
} \
*(PPARRAY) = (Pvoid_t)SET_PSCL(PSCL); \
((PSCL)->scl_Pvalue) = (Pvoid_t)NULL; \
(void)STRCPY((PSCL)->scl_Index, INDEX); \
}
// "FORWARD" DECLARATIONS:
static void JudySLModifyErrno(PJError_t PJError,
Pcvoid_t PArray, Pcvoid_t PArrayOrig);
static int JudySLDelSub(PPvoid_t PPArray, PPvoid_t PPArrayOrig,
const uint8_t * Index, Word_t len, PJError_t PJError);
static PPvoid_t JudySLPrevSub(Pcvoid_t PArray, uint8_t * Index, int orig,
Word_t len, PJError_t PJError);
static PPvoid_t JudySLNextSub(Pcvoid_t PArray, uint8_t * Index, int orig,
Word_t len, PJError_t PJError);
// ****************************************************************************
// J U D Y S L M O D I F Y E R R N O
//
// Common code for error translation: When a caller passes an invalid JAP
// ("not a JudyL pointer"), OR if the JudySL array is corrupted at a lower
// level, various JudyL*() calls return JU_ERRNO_NOTJUDYL. If the caller wants
// detailed error info, convert this particular error to JU_ERRNO_NOTJUDYSL if
// at the top of the tree, otherwise convert it to JU_ERRNO_CORRUPT, meaning
// there was a corruption (the only one even detectable outside JudyL) in the
// JudySL tree; but pass through any other errors unaltered.
static void
JudySLModifyErrno(PJError_t PJError, // to modify if non-null.
Pcvoid_t PArray, // current JudyL array.
Pcvoid_t PArrayOrig // top-of-tree JudyL array.
)
src/judy-1.0.5/src/JudySL/JudySL.c view on Meta::CPAN
(Pscl2->scl_Pvalue) = Pscl->scl_Pvalue;
}
// old SCL no longer needed.
JudyFree((void *)Pscl, scl2);
Pscl = (Pscl_t) NULL;
}
}
// APPEND NEXT LEVEL JUDYL ARRAY TO TREE:
//
// If a shortcut leaf was carried down and diverged at this level, the code
// above already appended the new JudyL array, but the next word of the new
// Index still must be inserted in it.
//
// See header comments about premature return().
//
// Note: If JudyLIns() returns JU_ERRNO_NOTJUDYL here, *PPArray should not be
// modified, so JudySLModifyErrno() can do the right thing.
if ((PPValue = JudyLIns(PPArray, indexword, PJError)) == PPJERR)
{
JudySLModifyErrno(PJError, *PPArray, *PPArrayOrig);
return (PPJERR);
}
assert(PPValue != (PPvoid_t) NULL);
// CHECK IF NEW INDEX TERMINATES:
//
// Note that if it does, and an old SCL was being carried down, it must have
// diverged by this point, and is already handled.
if (len <= WORDSIZE)
{
assert(Pscl == (Pscl_t) NULL);
return (PPValue); // is value for whole Index string.
}
pos += WORDSIZE;
len -= WORDSIZE;
pos2 += WORDSIZE; // useless unless Pscl is set.
len2 -= WORDSIZE;
PPArray = PPValue; // each value -> next array.
} // while.
} // NOTREACHED, JudySLIns()
// ****************************************************************************
// J U D Y S L D E L
//
// See the comments in JudySLGet(), which is somewhat similar.
//
// Unlike JudySLGet() and JudySLIns(), recurse downward through the tree of
// JudyL arrays to find and delete the given Index, if present, and then on the
// way back up, any of its parent arrays which ends up empty.
//
// TECHNICAL NOTES:
//
// Recursion seems bad, but this allows for an arbitrary-length Index. Also, a
// more clever iterative solution that used JudyLCount() (see below) would
// still require a function call per tree level, so why not just recurse?
//
// An earlier version (1.20) used a fixed-size stack, which limited the Index
// size. We were going to replace this with using JudyLCount(), in order to
// note and return to (read this carefully) the highest level JudyL array with
// a count of 1, all of whose descendant JudyL arrays also have a count of 1,
// and delete from that point downwards. This solution would traverse the
// array tree downward looking to see if the given Index is in the tree, then
// if so, delete layers downwards starting below the last one that contains
// other Indexes than the one being deleted.
//
// TBD: To save time coding, and to very likely save time overall during
// execution, this function does "lazy deletions", or putting it more nicely,
// it allows "hysteresis" in the JudySL tree, when shortcut leafs are present.
// It only removes the specified Index, and recursively any empty JudyL arrays
// above it, without fully reversing the effects of JudySLIns(). This is
// probably OK because any application that calls JudySLDel() is likely to call
// JudySLIns() again with the same or a neighbor Index.
int
JudySLDel(PPvoid_t PPArray, const uint8_t * Index, PJError_t PJError) // optional, for returning error info.
{
// Check for caller error (null pointer):
if (PPArray == (PPvoid_t) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
return (JERR);
}
if (Index == (uint8_t *) NULL)
{
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);
return (JERR);
}
// Do the deletion:
return (JudySLDelSub(PPArray, PPArray, Index, STRLEN(Index), PJError));
} // JudySLDel()
// ****************************************************************************
// J U D Y S L D E L S U B
//
// This is the "engine" for JudySLDel() that expects aligned and len to already
// be computed (only once). See the header comments for JudySLDel().
static int
JudySLDelSub(PPvoid_t PPArray, // in which to delete.
PPvoid_t PPArrayOrig, // for error reporting.
const uint8_t * Index, // to delete.
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.
int retcode; // from lower-level call.
( run in 1.200 second using v1.01-cache-2.11-cpan-13bb782fe5a )