diff options
Diffstat (limited to 'libnetdata/libjudy/src/JudyHS/JudyHS.c')
| -rw-r--r-- | libnetdata/libjudy/src/JudyHS/JudyHS.c | 771 |
1 files changed, 771 insertions, 0 deletions
diff --git a/libnetdata/libjudy/src/JudyHS/JudyHS.c b/libnetdata/libjudy/src/JudyHS/JudyHS.c new file mode 100644 index 00000000..21191bab --- /dev/null +++ b/libnetdata/libjudy/src/JudyHS/JudyHS.c @@ -0,0 +1,771 @@ +// @(#) $Revision: 4.1 $ $Source: /judy/src/JudyHS/JudyHS.c +//======================================================================= +// Author Douglas L. Baskins, Dec 2003. +// Permission to use this code is freely granted, provided that this +// statement is retained. +// email - doug@sourcejudy.com -or- dougbaskins@yahoo.com +//======================================================================= + +#include <string.h> // for memcmp(), memcpy() + +#include <Judy.h> // for JudyL* routines/macros + +/* + This routine is a very fast "string" version of an ADT that stores + (JudyHSIns()), retrieves (JudyHSGet()), deletes (JudyHSDel()) and + frees the entire ADT (JudyHSFreeArray()) strings. It uses the "Judy + arrays" JudyL() API as the main workhorse. The length of the string + is included in the calling parameters so that strings with embedded + \0s can be used. The string lengths can be from 0 bytes to whatever + malloc() can handle (~2GB). + + Compile: + + cc -O JudyHS.c -c needs to link with -lJudy (libJudy.a) + + Note: in gcc version 3.3.1, -O2 generates faster code than -O + Note: in gcc version 3.3.2, -O3 generates faster code than -O2 + + NOTES: + +1) There may be some performance issues with 64 bit machines, because I + have not characterized that it yet. + +2) It appears that a modern CPU (>2Ghz) that the instruction times are + much faster that a RAM access, so building up a word from bytes takes + no longer that a whole word access. I am taking advantage of this to + make this code endian neutral. A side effect of this is strings do + not need to be aligned, nor tested to be on to a word boundry. In + older and in slow (RISC) machines, this may be a performance issue. + I have given up trying to optimize for machines that have very slow + mpy, mod, variable shifts and call returns. + +3) JudyHS is very scalable from 1 string to billions (with enough RAM). + The memory usage is also scales with population. I have attempted to + combine the best characteristics of JudyL arrays with Hashing methods + and well designed modern processors (such as the 1.3Ghz Intel + Centrino this is being written on). + + HOW JudyHS WORKS: ( 4[8] means 4 bytes in 32 bit machine and 8 in 64) + + A) A JudyL array is used to separate strings of equal lengths into + their own structures (a different hash table is used for each length + of string). The additional time overhead is very near zero because + of the CPU cache. The space efficiency is improved because the + length need not be stored with the string (ls_t). The "JLHash" ADT + in the test program "StringCompare" is verification of both these + assumptions. + + B) A 32 bit hash value is produced from the string. Many thanks to + the Internet and the author (Bob Jenkins) for coming up with a very + good and fast universal string hash. Next the 32 bit hash number is + used as an Index to another JudyL array. Notice that one (1) JudyL + array is used as a hash table per each string length. If there are + no hash collisions (normally) then the string is copied to a + structure (ls_t) along with room for storing a Value. A flag is + added to the pointer to note it is pointing to a ls_t structure. + Since the lengths of the strings are the same, there is no need to + stored length of string in the ls_t structure. This saves about a + word per string of memory. + + C) When there is a hashing collision (very rare), a JudyL array is + used to decode the next 4[8] bytes of the string. That is, the next + 4[8] bytes of the string are used as the Index. This process is + repeated until the remaining string is unique. The remaining string + (if any) is stored in a (now smaller) ls_t structure. If the + remaining string is less or equal to 4[8] bytes, then the ls_t + structure is not needed and the Value area in the JudyL array is + used. A compile option -DDONOTUSEHASH is available to test this + structure without using hashing (only the JudyL tree is used). This + is equivalent to having all strings hashed to the same bucket. The + speed is still better than all other tree based ADTs I have tested. + An added benefit of this is a very fast "hash collision" resolving. + It could foil hackers that exploit the slow synonym (linked-list) + collision handling property used with most hashing algorithms. If + this is not a necessary property, then a simpler ADT "JLHash" that is + documented the the test program "StringCompare.c" may be used with a + little loss of memory efficiency (because it includes the string + length with the ls_t structure). JudyHS was written to be the + fastest, very scalable, memory efficient, general purpose string ADT + possible. (However, I would like to eat those words someday). (dlb) + +*/ + +#ifdef EXAMPLE_CODE +#include <stdio.h> +#include <unistd.h> +#include <string.h> + +#include <Judy.h> + +//#include "JudyHS.h" // for Judy.h without JudyHS*() + +// By Doug Baskins Apr 2004 - for JudyHS man page + +#define MAXLINE 1000000 /* max length of line */ +char Index[MAXLINE]; // string to check + +int // Usage: CheckDupLines < file +main() +{ + Pvoid_t PJArray = (PWord_t)NULL; // Judy array. + PWord_t PValue; // ^ Judy array element. + Word_t Bytes; // size of JudyHS array. + Word_t LineNumb = 0; // current line number + Word_t Dups = 0; // number of duplicate lines + + while (fgets(Index, MAXLINE, stdin) != (char *)NULL) + { + LineNumb++; // line number + +// store string into array + JHSI(PValue, PJArray, Index, strlen(Index)); + if (*PValue) // check if duplicate + { + Dups++; // count duplicates + printf("Duplicate lines %lu:%lu:%s", *PValue, LineNumb, Index); + } + else + { + *PValue = LineNumb; // store Line number + } + } + printf("%lu Duplicates, free JudyHS array of %lu Lines\n", + Dups, LineNumb - Dups); + JHSFA(Bytes, PJArray); // free array + printf("The JudyHS array allocated %lu bytes of memory\n", Bytes); + return (0); +} +#endif // EXAMPLE_CODE + +// Note: Use JLAP_INVALID, which is non-zero, to mark pointers to a ls_t +// This makes it compatable with previous versions of JudyL() + +#define IS_PLS(PLS) (((Word_t) (PLS)) & JLAP_INVALID) +#define CLEAR_PLS(PLS) (((Word_t) (PLS)) & (~JLAP_INVALID)) +#define SET_PLS(PLS) (((Word_t) (PLS)) | JLAP_INVALID) + +#define WORDSIZE (sizeof(Word_t)) + +// this is the struct used for "leaf" strings. Note that +// the Value is followed by a "variable" length ls_String array. +// +typedef struct L_EAFSTRING +{ + Word_t ls_Value; // Value area (cannot change size) + uint8_t ls_String[WORDSIZE]; // to fill out to a Word_t size +} ls_t , *Pls_t; + +#define LS_STRUCTOVD (sizeof(ls_t) - WORDSIZE) + +// Calculate size of ls_t including the string of length of LEN. +// +#define LS_WORDLEN(LEN) (((LEN) + LS_STRUCTOVD + WORDSIZE - 1) / WORDSIZE) + +// Copy from 0..4[8] bytes from string to a Word_t +// NOTE: the copy in in little-endian order to take advantage of improved +// memory efficiency of JudyLIns() with smaller numbers +// +#define COPYSTRING4toWORD(WORD,STR,LEN) \ +{ \ + WORD = 0; \ + switch(LEN) \ + { \ + default: /* four and greater */ \ + case 4: \ + WORD += (Word_t)(((uint8_t *)(STR))[3] << 24); \ + case 3: \ + WORD += (Word_t)(((uint8_t *)(STR))[2] << 16); \ + case 2: \ + WORD += (Word_t)(((uint8_t *)(STR))[1] << 8); \ + case 1: \ + WORD += (Word_t)(((uint8_t *)(STR))[0]); \ + case 0: break; \ + } \ +} + +#ifdef JU_64BIT + +// copy from 0..8 bytes from string to Word_t +// +#define COPYSTRING8toWORD(WORD,STR,LEN) \ +{ \ + WORD = 0UL; \ + switch(LEN) \ + { \ + default: /* eight and greater */ \ + case 8: \ + WORD += ((Word_t)((uint8_t *)(STR))[7] << 56); \ + case 7: \ + WORD += ((Word_t)((uint8_t *)(STR))[6] << 48); \ + case 6: \ + WORD += ((Word_t)((uint8_t *)(STR))[5] << 40); \ + case 5: \ + WORD += ((Word_t)((uint8_t *)(STR))[4] << 32); \ + case 4: \ + WORD += ((Word_t)((uint8_t *)(STR))[3] << 24); \ + case 3: \ + WORD += ((Word_t)((uint8_t *)(STR))[2] << 16); \ + case 2: \ + WORD += ((Word_t)((uint8_t *)(STR))[1] << 8); \ + case 1: \ + WORD += ((Word_t)((uint8_t *)(STR))[0]); \ + case 0: break; \ + } \ +} + +#define COPYSTRINGtoWORD COPYSTRING8toWORD + +#else // JU_32BIT + +#define COPYSTRINGtoWORD COPYSTRING4toWORD + +#endif // JU_32BIT + +// set JError_t locally + +#define JU_SET_ERRNO(PJERROR, JERRNO) \ +{ \ + if (PJERROR != (PJError_t) NULL) \ + { \ + if (JERRNO) \ + JU_ERRNO(PJError) = (JERRNO); \ + JU_ERRID(PJERROR) = __LINE__; \ + } \ +} + +//======================================================================= +// This routine must hash string to 24..32 bits. The "goodness" of +// the hash is not as important as its speed. +//======================================================================= + +// hash to no more than 32 bits + +// extern Word_t gHmask; for hash bits experiments + +#define JUDYHASHSTR(HVALUE,STRING,LENGTH) \ +{ \ + uint8_t *p_ = (uint8_t *)(STRING); \ + uint8_t *q_ = p_ + (LENGTH); \ + uint32_t c_ = 0; \ + for (; p_ != q_; ++p_) \ + { \ + c_ = (c_ * 31) + *p_; \ + } \ +/* c_ &= gHmask; see above */ \ + (HVALUE) = c_; \ +} + +// Find String of Len in JudyHS structure, return pointer to associated Value + +PPvoid_t +JudyHSGet(Pcvoid_t PArray, // pointer (^) to structure + void * Str, // pointer to string + Word_t Len // length of string + ) +{ + uint8_t *String = (uint8_t *)Str; + PPvoid_t PPValue; // pointer to Value + Word_t Index; // 4[8] bytes of String + + JLG(PPValue, PArray, Len); // find hash table for strings of Len + if (PPValue == (PPvoid_t) NULL) + return ((PPvoid_t) NULL); // no strings of this Len + +// check for caller error (null pointer) +// + if ((String == (void *) NULL) && (Len != 0)) + return ((PPvoid_t) NULL); // avoid null-pointer dereference + +#ifndef DONOTUSEHASH + if (Len > WORDSIZE) // Hash table not necessary with short + { + uint32_t HValue; // hash of input string + JUDYHASHSTR(HValue, String, Len); // hash to no more than 32 bits + JLG(PPValue, *PPValue, (Word_t)HValue); // get ^ to hash bucket + if (PPValue == (PPvoid_t) NULL) + return ((PPvoid_t) NULL); // no entry in Hash table + } +#endif // DONOTUSEHASH + +/* + Each JudyL array decodes 4[8] bytes of the string. Since the hash + collisions occur very infrequently, the performance is not important. + However, even if the Hash code is not used this method still is + significantly faster than common tree methods (AVL, Red-Black, Splay, + b-tree, etc..). You can compare it yourself with #define DONOTUSEHASH + 1 or putting -DDONOTUSEHASH in the cc line. Use the "StringCompare.c" + code to compare (9Dec2003 dlb). +*/ + while (Len > WORDSIZE) // traverse tree of JudyL arrays + { + if (IS_PLS(*PPValue)) // ^ to JudyL array or ls_t struct? + { + Pls_t Pls; // ls_t struct, termination of tree + Pls = (Pls_t) CLEAR_PLS(*PPValue); // remove flag from ^ + +// if remaining string matches, return ^ to Value, else NULL + + if (memcmp(String, Pls->ls_String, Len) == 0) + return ((PPvoid_t) (&(Pls->ls_Value))); + else + return ((PPvoid_t) NULL); // string does not match + } + else + { + COPYSTRINGtoWORD(Index, String, WORDSIZE); + + JLG(PPValue, *PPValue, Index); // decode next 4[8] bytes + if (PPValue == (PPvoid_t) NULL) // if NULL array, bail out + return ((PPvoid_t) NULL); // string does not match + + String += WORDSIZE; // advance + Len -= WORDSIZE; + } + } + +// Get remaining 1..4[8] bytes left in string + + COPYSTRINGtoWORD(Index, String, Len); + JLG(PPValue, *PPValue, Index); // decode last 1-4[8] bytes + return (PPValue); +} + +// Add string to a tree of JudyL arrays (all lengths must be same) + +static PPvoid_t +insStrJudyLTree(uint8_t * String, // string to add to tree of JudyL arrays + Word_t Len, // length of string + PPvoid_t PPValue, // pointer to root pointer + PJError_t PJError // for returning error info + ) +{ + Word_t Index; // next 4[8] bytes of String + + while (Len > WORDSIZE) // add to JudyL tree + { +// CASE 1, pointer is to a NULL, make a new ls_t leaf + + if (*PPValue == (Pvoid_t)NULL) + { + Pls_t Pls; // memory for a ls_t + Pls = (Pls_t) JudyMalloc(LS_WORDLEN(Len)); + if (Pls == NULL) + { + JU_SET_ERRNO(PJError, JU_ERRNO_NOMEM); + return (PPJERR); + } + Pls->ls_Value = 0; // clear Value word + memcpy(Pls->ls_String, String, Len); // copy to new struct + *PPValue = (Pvoid_t)SET_PLS(Pls); // mark pointer + return ((PPvoid_t) (&Pls->ls_Value)); // return ^ to Value + } // no exit here +// CASE 2: is a ls_t, free (and shorten), then decode into JudyL tree + + if (IS_PLS(*PPValue)) // pointer to a ls_t? (leaf) + { + Pls_t Pls; // ^ to ls_t + uint8_t *String0; // ^ to string in ls_t + Word_t Index0; // 4[8] bytes in string + Word_t FreeLen; // length of ls_t + PPvoid_t PPsplit; + + FreeLen = LS_WORDLEN(Len); // length of ls_t + + Pls = (Pls_t) CLEAR_PLS(*PPValue); // demangle ^ to ls_t + String0 = Pls->ls_String; + if (memcmp(String, String0, Len) == 0) // check if match? + { + return ((PPvoid_t) (&Pls->ls_Value)); // yes, duplicate + } + + *PPValue = NULL; // clear ^ to ls_t and make JudyL + +// This do loop is technically not required, saves multiple JudyFree() +// when storing already sorted strings into structure + + do // decode next 4[8] bytes of string + { // with a JudyL array +// Note: string0 is always aligned + + COPYSTRINGtoWORD(Index0, String0, WORDSIZE); + String0 += WORDSIZE; + COPYSTRINGtoWORD(Index, String, WORDSIZE); + String += WORDSIZE; + Len -= WORDSIZE; + PPsplit = PPValue; // save for split below + PPValue = JudyLIns(PPValue, Index0, PJError); + if (PPValue == PPJERR) + { + JU_SET_ERRNO(PJError, 0); + return (PPJERR); + } + + } while ((Index0 == Index) && (Len > WORDSIZE)); + +// finish storing remainder of string that was in the ls_t + + PPValue = insStrJudyLTree(String0, Len, PPValue, PJError); + if (PPValue == PPJERR) + { + return (PPJERR); + } +// copy old Value to Value in new struct + + *(PWord_t)PPValue = Pls->ls_Value; + +// free the string buffer (ls_t) + + JudyFree((Pvoid_t)Pls, FreeLen); + PPValue = JudyLIns(PPsplit, Index, PJError); + if (PPValue == PPJERR) + { + JU_SET_ERRNO(PJError, 0); + return (PPValue); + } + +// finish remainder of newly inserted string + + PPValue = insStrJudyLTree(String, Len, PPValue, PJError); + return (PPValue); + } // no exit here +// CASE 3, more JudyL arrays, decode to next tree + + COPYSTRINGtoWORD(Index, String, WORDSIZE); + Len -= WORDSIZE; + String += WORDSIZE; + + PPValue = JudyLIns(PPValue, Index, PJError); // next 4[8] bytes + if (PPValue == PPJERR) + { + JU_SET_ERRNO(PJError, 0); + return (PPValue); + } + } +// this is done outside of loop so "Len" can be an unsigned number + + COPYSTRINGtoWORD(Index, String, Len); + PPValue = JudyLIns(PPValue, Index, PJError); // remaining 4[8] bytes + + return (PPValue); +} + + +// Insert string to JudyHS structure, return pointer to associated Value + +PPvoid_t +JudyHSIns(PPvoid_t PPArray, // ^ to JudyHashArray name + void * Str, // pointer to string + Word_t Len, // length of string + PJError_t PJError // optional, for returning error info + ) +{ + uint8_t * String = (uint8_t *)Str; + PPvoid_t PPValue; + +// string can only be NULL if Len is 0. + + if ((String == (uint8_t *) NULL) && (Len != 0UL)) + { + JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX); + return (PPJERR); + } + JLG(PPValue, *PPArray, Len); // JudyL hash table for strings of Len + if (PPValue == (PPvoid_t) NULL) // make new if missing, (very rare) + { + PPValue = JudyLIns(PPArray, Len, PJError); + if (PPValue == PPJERR) + { + JU_SET_ERRNO(PJError, 0); + return (PPJERR); + } + } +#ifndef DONOTUSEHASH + if (Len > WORDSIZE) + { + uint32_t HValue; // hash of input string + JUDYHASHSTR(HValue, String, Len); // hash to no more than 32 bits + PPValue = JudyLIns(PPValue, (Word_t)HValue, PJError); + if (PPValue == PPJERR) + { + JU_SET_ERRNO(PJError, 0); + return (PPJERR); + } + } +#endif // DONOTUSEHASH + + PPValue = insStrJudyLTree(String, Len, PPValue, PJError); // add string + return (PPValue); // ^ to Value +} + +// Delete string from tree of JudyL arrays (all Lens must be same) + +static int +delStrJudyLTree(uint8_t * String, // delete from tree of JudyL arrays + Word_t Len, // length of string + PPvoid_t PPValue, // ^ to hash bucket + PJError_t PJError // for returning error info + ) +{ + PPvoid_t PPValueN; // next pointer + Word_t Index; + int Ret; // -1=failed, 1=success, 2=quit del + + if (IS_PLS(*PPValue)) // is pointer to ls_t? + { + Pls_t Pls; + Pls = (Pls_t) CLEAR_PLS(*PPValue); // demangle pointer + JudyFree((Pvoid_t)Pls, LS_WORDLEN(Len)); // free the ls_t + + *PPValue = (Pvoid_t)NULL; // clean pointer + return (1); // successfully deleted + } + + if (Len > WORDSIZE) // delete from JudyL tree, not leaf + { + COPYSTRINGtoWORD(Index, String, WORDSIZE); // get Index + JLG(PPValueN, *PPValue, Index); // get pointer to next JudyL array + + String += WORDSIZE; // advance to next 4[8] bytes + Len -= WORDSIZE; + + Ret = delStrJudyLTree(String, Len, PPValueN, PJError); + if (Ret != 1) return(Ret); + + if (*PPValueN == (PPvoid_t) NULL) + { +// delete JudyL element from tree + + Ret = JudyLDel(PPValue, Index, PJError); + } + } + else + { + COPYSTRINGtoWORD(Index, String, Len); // get leaf element + +// delete last 1-4[8] bytes from leaf element + + Ret = JudyLDel(PPValue, Index, PJError); + } + return (Ret); +} + +// Delete string from JHS structure + +int +JudyHSDel(PPvoid_t PPArray, // ^ to JudyHashArray struct + void * Str, // pointer to string + Word_t Len, // length of string + PJError_t PJError // optional, for returning error info + ) +{ + uint8_t * String = (uint8_t *)Str; + PPvoid_t PPBucket, PPHtble; + int Ret; // return bool from Delete routine +#ifndef DONOTUSEHASH + uint32_t HValue = 0; // hash value of input string +#endif // DONOTUSEHASH + + if (PPArray == NULL) + return (0); // no pointer, return not found + +// This is a little slower than optimum method, but not much in new CPU +// Verify that string is in the structure -- simplifies future assumptions + + if (JudyHSGet(*PPArray, String, Len) == (PPvoid_t) NULL) + return (0); // string not found, return + +// string is in structure, so testing for absence is not necessary + + JLG(PPHtble, *PPArray, Len); // JudyL hash table for strings of Len + +#ifdef DONOTUSEHASH + PPBucket = PPHtble; // simulate below code +#else // USEHASH + if (Len > WORDSIZE) + { + JUDYHASHSTR(HValue, String, Len); // hash to no more than 32 bits + +// get pointer to hash bucket + + JLG(PPBucket, *PPHtble, (Word_t)HValue); + } + else + { + PPBucket = PPHtble; // no bucket to JLGet + } +#endif // USEHASH + +// delete from JudyL tree +// + Ret = delStrJudyLTree(String, Len, PPBucket, PJError); + if (Ret != 1) + { + JU_SET_ERRNO(PJError, 0); + return(-1); + } +// handle case of missing JudyL array from hash table and length table + + if (*PPBucket == (Pvoid_t)NULL) // if JudyL tree gone + { +#ifndef DONOTUSEHASH + if (Len > WORDSIZE) + { +// delete entry in Hash table + + Ret = JudyLDel(PPHtble, (Word_t)HValue, PJError); + if (Ret != 1) + { + JU_SET_ERRNO(PJError, 0); + return(-1); + } + } +#endif // USEHASH + if (*PPHtble == (PPvoid_t) NULL) // if Hash table gone + { +// delete entry from the String length table + + Ret = JudyLDel(PPArray, Len, PJError); + if (Ret != 1) + { + JU_SET_ERRNO(PJError, 0); + return(-1); + } + } + } + return (1); // success +} + +static Word_t +delJudyLTree(PPvoid_t PPValue, // ^ to JudyL root pointer + Word_t Len, // length of string + PJError_t PJError) // for returning error info +{ + Word_t bytes_freed = 0; // bytes freed at point + Word_t bytes_total = 0; // accumulated bytes freed + PPvoid_t PPValueN; + +// Pointer is to another tree of JudyL arrays or ls_t struct + + if (Len > WORDSIZE) // more depth to tree + { + Word_t NEntry; + +// Pointer is to a ls_t struct + + if (IS_PLS(*PPValue)) + { + Pls_t Pls; + Word_t freewords; + + freewords = LS_WORDLEN(Len); // calculate length + Pls = (Pls_t)CLEAR_PLS(*PPValue); // demangle pointer + +// *PPValue = (Pvoid_t)NULL; // clean pointer + JudyFree((Pvoid_t)Pls, freewords); // free the ls_t + + return(freewords * WORDSIZE); + } +// else +// Walk all the entrys in the JudyL array + + NEntry = 0; // start at beginning + for (PPValueN = JudyLFirst(*PPValue, &NEntry, PJError); + (PPValueN != (PPvoid_t) NULL) && (PPValueN != PPJERR); + PPValueN = JudyLNext(*PPValue, &NEntry, PJError)) + { +// recurse to the next level in the tree of arrays + + bytes_freed = delJudyLTree(PPValueN, Len - WORDSIZE, PJError); + if (bytes_freed == JERR) return(JERR); + bytes_total += bytes_freed; + } + if (PPValueN == PPJERR) return(JERR); + +// now free this JudyL array + + bytes_freed = JudyLFreeArray(PPValue, PJError); + if (bytes_freed == JERR) return(JERR); + bytes_total += bytes_freed; + + return(bytes_total); // return amount freed + } +// else + +// Pointer to simple JudyL array + + bytes_freed = JudyLFreeArray(PPValue, PJError); + + return(bytes_freed); +} + + +Word_t // bytes freed +JudyHSFreeArray(PPvoid_t PPArray, // ^ to JudyHashArray struct + PJError_t PJError // optional, for returning error info + ) +{ + Word_t Len; // start at beginning + Word_t bytes_freed; // bytes freed at this level. + Word_t bytes_total; // bytes total at all levels. + PPvoid_t PPHtble; + + if (PPArray == NULL) + return (0); // no pointer, return none + +// Walk the string length table for subsidary hash structs +// NOTE: This is necessary to determine the depth of the tree + + bytes_freed = 0; + bytes_total = 0; + Len = 0; // walk to length table + + for (PPHtble = JudyLFirst(*PPArray, &Len, PJError); + (PPHtble != (PPvoid_t) NULL) && (PPHtble != PPJERR); + PPHtble = JudyLNext(*PPArray, &Len, PJError)) + { + PPvoid_t PPValueH; + +#ifndef DONOTUSEHASH + if (Len > WORDSIZE) + { + Word_t HEntry = 0; // walk the hash tables + + for (PPValueH = JudyLFirst(*PPHtble, &HEntry, PJError); + (PPValueH != (PPvoid_t) NULL) && (PPValueH != PPJERR); + PPValueH = JudyLNext(*PPHtble, &HEntry, PJError)) + { + bytes_freed = delJudyLTree(PPValueH, Len, PJError); + if (bytes_freed == JERR) return(JERR); + bytes_total += bytes_freed; + } + + if (PPValueH == PPJERR) return(JERR); + +// free the Hash table for this length of string + + bytes_freed = JudyLFreeArray(PPHtble, PJError); + if (bytes_freed == JERR) return(JERR); + bytes_total += bytes_freed; + } + else +#endif // DONOTUSEHASH + { + PPValueH = PPHtble; // simulate hash table + + bytes_freed = delJudyLTree(PPValueH, Len, PJError); + if (bytes_freed == JERR) return(JERR); + bytes_total += bytes_freed; + } + } + if (PPHtble == PPJERR) return(JERR); + +// free the length table + + bytes_freed = JudyLFreeArray(PPArray, PJError); + if (bytes_freed == JERR) return(JERR); + + bytes_total += bytes_freed; + + return(bytes_total); // return bytes freed +} |