libJudy Summary
Last update: December 23, 2019 --
By
Alan Silverstein,
ajs@frii.com
Brief Overview of Features
Types of keys/values:
| Functions |
Macros |
Key/Index |
Value |
| Judy1*() |
J1*() |
word (32/64-bit) |
bit (true/false) |
| JudyL*() |
JL*() |
word (32/64-bit) |
word (32/64-bit) |
| JudySL*() |
JSL*() |
C string |
word (32/64-bit) |
| JudyNL*() |
JNL*() |
word(s) + length |
word (32/64-bit) |
Types of operations:
|
| Judy1
| JudyL
| JudySL
| JudyNL
|
| Generic
| Specific
| Function
| Macro
| Function
| Macro
| Function
| Macro
| Function
| Macro
|
| add |
set/insert |
Judy1Set() |
J1S() |
JudyLIns() |
JLI() |
JudySLIns() |
JSLI() |
JudyNLIns() |
JNLI() |
| delete |
unset/delete |
Judy1Unset() |
J1U() |
JudyLDel() |
JLD() |
JudySLDel() |
JSLD() |
JudyNLDel() |
JNLD() |
| lookup |
test/get |
Judy1Test |
J1T() |
JudyLGet |
JLG() |
JudySLGet |
JSLG() |
JudyNLGet |
JNLG() |
|
| count |
|
Judy1Count() |
J1C() |
JudyLCount() |
JLC() |
|
|
|
|
| by-count |
|
Judy1ByCount() |
J1BC() |
JudyLByCount() |
JLBC() |
|
|
|
|
| free-array |
|
Judy1FreeArray() |
J1FA() |
JudyLFreeArray() |
JLFA() |
JudySLFreeArray() |
JSLFA() |
JudyNLFreeArray() |
JNLFA() |
| mem-used |
|
Judy1MemUsed() |
J1MU() |
JudyLMemUsed() |
JLMU() |
|
|
|
|
|
| first |
(inclusive) |
Judy1First() |
J1F() |
JudyLFirst() |
JLF() |
JudySLFirst() |
JSLF() |
JudyNLFirst() |
JNLF() |
| next |
(exclusive) |
Judy1Next() |
J1N() |
JudyLNext() |
JLN() |
JudySLNext() |
JSLN() |
JudyNLNext() |
JNLN() |
| last |
(inclusive) |
Judy1Last() |
J1L() |
JudyLLast() |
JLL() |
JudySLLast() |
JSLL() |
JudyNLLast() |
JNLL() |
| prev |
(exclusive) |
Judy1Prev() |
J1P() |
JudyLPrev() |
JLP() |
JudySLPrev() |
JSLP() |
JudySLPrev() |
JNLP() |
|
| first empty |
(inclusive) |
Judy1FirstEmpty() |
J1FE() |
JudyLFirstEmpty() |
JLFE() |
|
|
|
|
| next empty |
(exclusive) |
Judy1NextEmpty() |
J1NE() |
JudyLNextEmpty() |
JLNE() |
|
|
|
|
| last empty |
(inclusive) |
Judy1LastEmpty() |
J1LE() |
JudyLLastEmpty() |
JLLE() |
|
|
|
|
| prev empty |
(exclusive) |
Judy1PrevEmpty() |
J1PE() |
JudyLPrevEmpty() |
JLPE() |
|
|
|
|
Key Points for Coders
-
Pure library API with 32-bit and 64-bit versions; archive
libraries only (shared libs ruin performance).
-
One header file, Judy.h.
-
A libJudy array is just a void* (Pvoid_t) initially set to
NULL.
-
No other initialization, configuration, or tuning needed, or
even possible.
-
Think of it like a hash table where the hash algorithm is the
ultimate simple and fast operation, "look at the next byte of the
index," and synonym chains are always one element (no issues about
spectral properties).
-
Key point: JL*(), JSL*(), JNL*() do not receive/return your
value, just a pointer to a value word in which you can store
anything you want, including a pointer to other memory (separately
malloc()'d/free()'d), or nothing at all (for a JudySL list of
strings without values).
-
The macros hide standardized error handling; other
than malloc(), errors are very rare unless you corrupt the array.
-
The macros also make all parameter types consistent, hiding
some details, but require careful thought in some cases.
-
Internal tree nodes are very wide (256-way), so the tree is
very shallow.
-
The internal algorithms are highly CPU-cache-efficient.
-
The tree is digital (radix, by-expanse), not by-population;
no balancing occurs; insert/delete operations are localized
and fast.
-
Array-of-array is relatively easy; a JL*(), JSL*(), or JNL*()
value word is just a pointer to another Judy array; JudySL is
constructed as array of array of JudyL. Each node in the meta-tree
has degree (fan-out) of 2^32 or 2^64!
-
Uses generic malloc()/free() for its own memory.
-
No known bugs! But some known usability issues.