NAME¶
JudySL - C library for creating and accessing a dynamic array, using a
null-terminated string as an
Index (associative array)
SYNOPSIS¶
cc [flags] sourcefiles -lJudy
#include <Judy.h>
#define MAXLINELEN 1000000 // define maximum string length
Word_t * PValue; // JudySL array element
uint8_t Index[MAXLINELEN]; // string
int Rc_int; // return value
Word_t Rc_word; // full word return value
Pvoid_t PJSLArray = (Pvoid_t) NULL; // initialize JudySL array
JSLI( PValue, PJSLArray, Index); // JudySLIns()
JSLD( Rc_int, PJSLArray, Index); // JudySLDel()
JSLG( PValue, PJSLArray, Index); // JudySLGet()
JSLFA(Rc_word, PJSLArray); // JudySLFreeArray()
JSLF( PValue, PJSLArray, Index); // JudySLFirst()
JSLN( PValue, PJSLArray, Index); // JudySLNext()
JSLL( PValue, PJSLArray, Index); // JudySLLast()
JSLP( PValue, PJSLArray, Index); // JudySLPrev()
DESCRIPTION¶
A JudySL array is the equivalent of a sorted set of strings, each associated
with a
Value (word). A
Value is addressed by an
Index
(key), which is a null-terminated character string of any length. Memory to
support the array is allocated as index/value pairs are inserted, and released
as index/value pairs are deleted. This is a form of associative array, where
array elements are also sorted lexicographically (case-sensitive) by indexes.
This could be thought of as
void * JudySLArray["Toto, I don't think we're in Kansas any more"];
A JudySL array is allocated with a
NULL pointer
Pvoid_t PJSLArray = (Pvoid_t) NULL;
As with an ordinary array, there are no duplicate indexes (strings) in a JudySL
array.
Using the macros described here, rather than the
JudySL function calls,
the default error handling sends a message to the standard error and
terminates the program with
exit(1).
JSLI(PValue, PJSLArray, Index) // JudySLIns()¶
Insert an
Index string and
Value in the JudySL array
PJSLArray. If the
Index is successfully inserted, the
Value is initialized to 0. If the
Index was already present, the
Value is not modified.
Return
PValue pointing to
Index's
Value. Your program must
use this pointer to modify the
Value, for example:
*PValue = 1234;
Note:
JSLI() and
JSLD reorganize the JudySL array.
Therefore, pointers returned from previous
JudySL calls become invalid
and must be reacquired.
JSLD(Rc_int, PJSLArray, Index) // JudySLDel()¶
Delete the specified
Index/
Value pair (array element) from the
JudySL array.
Return
Rc_int set to 1 if successful. array and it was previously
inserted. Return
Rc_int set to 0 if
Index was not present.
JSLG(PValue, PJSLArray, Index) // JudySLGet()¶
Get the pointer to
Index's
Value.
Return
PValue pointing to
Index's
Value. Return
PValue set to
NULL if the
Index was not present.
JSLFA(Rc_word, PJSLArray) // JudySLFreeArray()¶
Given a pointer to a JudySL array (
PJSLArray), free the entire array
(much faster than using a
JSLN(),
JSLD() loop.)
Return
Rc_word set to the number of bytes freed and
PJSLArray set
to NULL.
JudySL Search Functions¶
The JudySL search functions allow you to search for indexes in the array. You
may search inclusively or exclusively, in either forward or reverse
directions.
If successful,
Index is returned set to the found index, and
PValue is returned set to a pointer to
Index's
Value. If
unsuccessful,
PValue is returned set to
NULL, and
Index
contains no useful information.
PValue must be tested for
non-
NULL prior to using
Index, since a search failure is
possible.
Note: To accomodate all possible returns, the
Index buffer must be
at least as large as the largest string stored in the array.
JSLF(PValue, PJSLArray, Index) // JudySLFirst()¶
Search (inclusive) for the first index present that is equal to or greater than
the passed
Index string. (Start with a null string to find the first
index in the array.)
JSLF() is typically used to
begin a
sorted-order scan of the valid indexes in a JudySL array.
uint8_t Index[MAXLINELEN];
strcpy (Index, "");
JSLF(PValue, PJSLArray, Index);
JSLN(PValue, PJSLArray, Index) // JudySLNext()¶
Search (exclusive) for the next index present that is greater than the passed
Index string.
JSLN() is typically used to
continue a
sorted-order scan of the valid indexes in a JudySL array, or to locate a
"neighbor" of a given index.
JSLL(PValue, PJSLArray, Index) // JudySLLast()¶
Search (inclusive) for the last index present that is equal to or less than the
passed
Index string. (Start with a maximum-valued string to look up the
last index in the array, such as a max-length string of 0xff bytes.)
JSLL() is typically used to
begin a reverse-sorted-order scan of
the valid indexes in a JudySL array.
JSLP(PValue, PJSLArray, Index) // JudySLPrev()¶
Search (exclusive) for the previous index present that is less than the passed
Index string.
JSLP() is typically used to
continue a
reverse-sorted-order scan of the valid indexes in a JudySL array, or to locate
a "neighbor" of a given index.
ERRORS: See: Judy_3.htm#ERRORS¶
EXAMPLE of a string sort routine¶
#include <stdio.h>
#include <Judy.h>
#define MAXLINE 1000000 // max string (line) length
uint8_t Index[MAXLINE]; // string to insert
int // Usage: JudySort < file_to_sort
main()
{
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // Judy array element.
Word_t Bytes; // size of JudySL array.
while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
{
JSLI(PValue, PJArray, Index); // store string into array
if (PValue == PJERR) // if out of memory?
{ // so do something
printf("Malloc failed -- get more ram\n");
exit(1);
}
++(*PValue); // count instances of string
}
Index[0] = '\0'; // start with smallest string.
JSLF(PValue, PJArray, Index); // get first string
while (PValue != NULL)
{
while ((*PValue)--) // print duplicates
printf("%s", Index);
JSLN(PValue, PJArray, Index); // get next string
}
JSLFA(Bytes, PJArray); // free array
fprintf(stderr, "The JudySL array used %lu bytes of memory\n", Bytes);
return (0);
}
AUTHOR¶
Judy was invented by Doug Baskins and implemented -Packard.
SEE ALSO¶
Judy(3),
Judy1(3),
JudyL(3),
JudyHS(3),
malloc(),
the Judy website,
http://judy.sourceforge.net, for further information
and Application Notes.