NAME
JudySL macros - 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 by Hewlett-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.
JudySL(3)