Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/doc/ext/Judy_3.htm view on Meta::CPAN
<HTML>
<HEAD>
<!-- @(#) $Revision: 4.36 $ $Source: /cvsroot/judy/doc/ext/Judy_3.htm,v $ --->
<TITLE>Judy(3)</TITLE>
</HEAD>
<BODY>
<TABLE border=0 width="100%"><TR>
<TD width="40%" align="left">Judy(3)</TD>
<TD width="10%" align="center"> </TD>
<TD width="40%" align="right">Judy(3)</TD>
</TR></TABLE>
<P>
<!----------------->
<DT><B>NAME</B></DT>
<DD>
Judy arrays -
C library functions for creating and accessing dynamic arrays
</DD>
<!----------------->
<P>
<DT><B>SYNOPSIS</B></DT>
<DD>
<PRE>
<A href="Judy1_3.htm">Judy1</A> - maps an <B>Index</B> (word) to a <B>bit</B>
<A href="JudyL_3.htm">JudyL</A> - maps an <B>Index</B> (word) to a <B>Value</B> (word/pointer)
<A href="JudySL_3.htm">JudySL</A> - maps an <B>Index</B> (null terminated string) to a <B>Value</B>
<A href="JudyHS_3.htm">JudyHS</A> - maps an <B>Index</B> (array-of-bytes) of <B>Length</B> to a <B>Value</B>
</PRE>
<!----------------->
<P>
<DT><B>DESCRIPTION</B></DT>
<DD>
The Judy family of functions supports fully dynamic arrays. These
arrays may be indexed by a 32- or 64-bit word (depending on processor
word size), a null terminated string or an array-of-bytes plus length.
A dynamic array (sparsely populated) can also be thought of as a
<I>mapping function</I> or <I>associative memory</I>.
<P>
A <B>Word_t</B> is a <I>typedef unsigned long int </I> in <B>Judy.h</B>
and must be the same size as <I>sizeof(void *)</I> I.E. a pointer.
<P>
<A href="Judy1_3.htm">Judy1</A> functions: <B>Index</B> is a
<B>Word_t</B> and <B>Value</B> is just a <B>bit</B> or simply
a flag that <B>Index</B> is present or missing from the array.
This can be thought of as a huge bitmap.
<P>
<A href="JudyL_3.htm">JudyL</A> functions: <B>Index</B> is a
<B>Word_t</B> and <B>Value</B> is a <B>Word_t</B>. This makes
<B>JudyL</B> a pure word-to-word/pointer mapper. <B>JudySL</B> and
<B>JudyHL</B> are based on this property of <B>JudyL</B>.
<P>
<A href="JudySL_3.htm">JudySL</A> functions: <B>Index</B> is a
null-terminated string and <B>Value</B> is a <B>Word_t</B>.
<P>
<A href="JudyHS_3.htm">JudyHS</A> functions: <B>Index</B> is an
array-of-bytes of length: <B>Length</B>. <B>Value</B> is a
<B>Word_t</B>. This new addition (May 2004) to Judy is a hybird using
the best features of hashing and Judy methods. The author believes
<B>JudyHS</B> is a good replacement for a hashing method when resizing
the hash table is done during population growth. A correctly tuned hash
method with a <B>static</B> hash table size and population is unbeatable
for speed. However, <B>JudyHS</B> will perform better than a hashing
method with smaller and larger populations than the optimum hash table
size. <B>JudyHS</B> does not have a degenerate performance case where
knowledge of the hash algorithm can be exploited. (I.E. JudyHS does
not use a linked list to handle hash collisions, it uses a tree of
<B>JudyL</B> arrays and a virtual hash table size of 4 billion).
<P>
Judy arrays are both <B>speed-</B> and <B>memory-efficient</B>, with no
tuning or configuration required, across a wide range of index set types
(sequential, periodic, clustered, random). Judy's speed and memory
usage are typically better than other data storage models such as
skiplists, linked lists, binary, ternary, b-trees, or even hashing, and
improves with very large data sets.
<P>
A Judy array is created merely by defining a null pointer and then
storing (inserting) the first element into the array under that pointer.
The memory used by a Judy array is nearly proportional to the population
(number of elements).
<P>
Judy has two Application Program Interfaces (APIs): a C macro
interface, and a function call interface. Because the macro forms are
sometimes faster and have a simpler error handling interface than the
equivalent functions, they are the preferred way of using the Judy
functions.
<P>
Since an initial (empty) Judy array is represented by a null pointer, it
is possible to construct an array of Judy arrays. In other words, a
Judy array's <B>Values</B> (except Judy1) can be pointers to other Judy
arrays. This makes it very simple to construct an array with an
arbitrary number of dimensions or <B>Index</B> sizes. (JudySL and
JudyHS are implemented using JudyL this way).
<!----------------->
<P>
( run in 1.684 second using v1.01-cache-2.11-cpan-140bd7fdf52 )