Judy1(3) Library Functions Manual Judy1(3) NAME Judy1 macros - C library for creating and accessing a dynamic array of bits, using any value of a word as an index. SYNOPSIS cc [flags] sourcefiles -lJudy #include <Judy.h> int Rc_int; // return code - integer Word_t Rc_word; // return code - unsigned word Word_t Index, Index1, Index2, Nth; Pvoid_t PJ1Array = (Pvoid_t) NULL; // initialize Judy1 array J1S( Rc_int, PJ1Array, Index); // Judy1Set() J1U( Rc_int, PJ1Array, Index); // Judy1Unset() J1T( Rc_int, PJ1Array, Index); // Judy1Test() J1C( Rc_word, PJ1Array, Index1, Index2); // Judy1Count() J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount() J1FA(Rc_word, PJ1Array); // Judy1FreeArray() J1MU(Rc_word, PJ1Array); // Judy1MemUsed() J1F( Rc_int, PJ1Array, Index); // Judy1First() J1N( Rc_int, PJ1Array, Index); // Judy1Next() J1L( Rc_int, PJ1Array, Index); // Judy1Last() J1P( Rc_int, PJ1Array, Index); // Judy1Prev() J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty() J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty() J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty() J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty() DESCRIPTION A Judy1 array is the equivalent of a bit array or bit map. A bit is ad- dressed by an Index (key). The array may be sparse, and the Index may be any word-sized Value. If an index is present, it represents a set bit (a bit set represents an index present). If an index is absent, it represents an unset bit (a bit unset represents an absent index). A Judy1 array is allocated with a NULL pointer Pvoid_t PJ1Array = (Pvoid_t) NULL; Memory to support the array is allocated as bits are set, and released as bits are unset. If the Judy1 pointer (PJ1Array) is NULL, all bits are un- set (and the Judy1 array requires no memory). As with an ordinary array, a Judy1 array contains no duplicate indexes. Using the macros described here, rather than the Judy1 function calls, the default error handling sends a message to the standard error and terminates the program with exit(1). For other error handling methods, see the ERRORS section. Because the macro forms are sometimes faster and have a simpler error han- dling interface than the equivalent functions, they are the preferred way of calling the Judy1 functions. J1S(Rc_int, PJ1Array, Index); // Judy1Set() Set Index's bit in the Judy1 array PJ1Array. Return Rc_int set to 1 if Index's bit was previously unset (successful), otherwise 0 if the bit was already set (unsuc- cessful). J1U(Rc_int, PJ1Array, Index); // Judy1Unset() Unset Index's bit in the Judy1 array PJ1Array; that is, re- move Index from the Judy1 array. Return Rc_int set to 1 if Index's bit was previously set (successful), otherwise 0 if the bit was already unset (un- successful). J1T(Rc_int, PJ1Array, Index); // Judy1Test() Test if Index's bit is set in the Judy1 array PJ1Array. Return Rc_int set to 1 if Index's bit is set (Index is present), 0 if it is unset (Index is absent). J1C(Rc_word, PJ1Array, Index1, Index2); // Judy1Count() Count the number of indexes present in the Judy1 array PJ1Array between Index1 and Index2 (inclusive). Return Rc_word set to the count. A return Value of 0 can be valid as a count, or it can indicate a special case for fully populated array (32-bit machines only). See Judy1Count() for ways to resolve this. To count all indexes present (population) in a Judy1 bit ar- ray, use: J1C(Rc_word, PJ1Array, 0, -1); Note: The -1 promotes to the maximum index, that is, all ones. J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount() Locate the Nth index that is present in the Judy1 array PJ1Array (Nth = 1 returns the first index present). To re- fer to the last index in a fully populated array (all in- dexes present, which is rare), use Nth = 0. Return Rc_int set to 1 and Index set to the Nth index if found, otherwise return Rc_int set to 0 (the Value of Index contains no useful information). J1FA(Rc_word, PJ1Array); // Judy1FreeArray() Free the entire Judy1 array PJ1Array (much faster than using a J1N(), J1U() loop). Return Rc_word set to the number of bytes freed, and PJ1Ar- ray set to NULL. J1MU(Rc_word, PJ1Array); // Judy1MemUsed() Return Rc_word set to the number of bytes of memory cur- rently in use by Judy1 array PJ1Array. This is a very fast routine, and may be used after a J1S() or J1U() call with little performance impact. Judy1 Search Functions The Judy1 search functions allow you to search for set or unset bits in the array. You may search inclusively or ex- clusively, in either forward or reverse directions. All of the search functions use a similar calling sequence. Rc_int is returned set to 1 for a successful search and the found Index is returned. Rc_int is returned set to 0 for an un- successful search, and Index contains no useful information. The return code Rc_int must be checked prior to using the returned Index, since a search failure is possible. J1F(Rc_int, PJ1Array, Index); // Judy1First() Search (inclusive) for the first index present that is equal to or greater than the passed Index. (Start with Index = 0 to find the first index in the array.) J1F() is typically used to begin a sorted-order scan of the indexes present in a Judy1 array. J1N(Rc_int, PJ1Array, Index); // Judy1Next() Search (exclusive) for the next index present that is greater than the passed Index. J1N() is typically used to continue a sorted-order scan of the indexes present in a Judy1 array, or to locate a "neighbor" of a given index. J1L(Rc_int, PJ1Array, Index); // Judy1Last() Search (inclusive) for the last index present that is equal to or less than the passed Index. (Start with Index = -1, that is, all ones, to find the last index in the array.) J1L() is typically used to begin a reverse-sorted-order scan of the indexes present in a Judy1 array. J1P(Rc_int, PJ1Array, Index); // Judy1Prev() Search (exclusive) for the previous index present that is less than the passed Index. J1P() is typically used to con- tinue a reverse-sorted-order scan of the indexes present in a Judy1 array, or to locate a "neighbor" of a given index. J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty() Search (inclusive) for the first absent index that is equal to or greater than the passed Index. (Start with Index = 0 to find the first index absent in the array.) J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty() Search (exclusive) for the next absent index that is greater than the passed Index. J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty() Search (inclusive) for the last absent index that is equal to or less than the passed Index. (Start with Index = -1 to find the last index absent in the array.) J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty() Search (exclusive) for the previous absent index that is less than the passed Index. ERRORS: See: Judy_3.htm#ERRORS EXAMPLE In the following example, errors in the J1S() or J1U() calls go to a user- defined procedure, process_malloc_failure. This is not needed when you use the default JUDYERROR() macro, since the default causes your program to exit on all failures, including malloc() failure. #include <stdio.h> #include <Judy.h> int main() // Example program of Judy1 macro APIs { Word_t Index; // index (or key) Word_t Rcount; // count of indexes (or bits set) Word_t Rc_word; // full word return value int Rc_int; // boolean values returned (0 or 1) Pvoid_t PJ1Array = (Pvoid_t) NULL; // initialize Judy1 array Index = 123456; J1S(Rc_int, J1Array, Index); // set bit at 123456 if (Rc_int == JERR) goto process_malloc_failure; if (Rc_int == 1) printf("OK - bit successfully set at %lu\n", Index); if (Rc_int == 0) printf("BUG - bit already set at %lu\n", Index); Index = 654321; J1T(Rc_int, J1Array, Index); // test if bit set at 654321 if (Rc_int == 1) printf("BUG - set bit at %lu\n", Index); if (Rc_int == 0) printf("OK - bit not set at %lu\n", Index); J1C(Rcount, J1Array, 0, -1); // count all bits set in array printf("%lu bits set in Judy1 array\n", Rcount); Index = 0; J1F(Rc_int, J1Array, Index); // find first bit set in array if (Rc_int == 1) printf("OK - first bit set is at %lu\n", Index); if (Rc_int == 0) printf("BUG - no bits set in array\n"); J1MU(Rc_word, J1Array); // how much memory was used? printf("%lu Indexes used %lu bytes of memory\n", Rcount, Rc_word); Index = 123456; J1U(Rc_int, J1Array, Index); // unset bit at 123456 if (Rc_int == JERR) goto process_malloc_failure; if (Rc_int == 1) printf("OK - bit successfully unset at %lu\n", Index); if (Rc_int == 0) printf("BUG - bit was not set at %lu\n", Index); return(0); } AUTHOR Judy was invented by Doug Baskins and implemented by Hewlett-Packard. SEE ALSO Judy(3), JudyL(3), JudySL(3), JudyHS(3), malloc(), the Judy website, http://judy.sourceforge.net, for more information and Ap- plication Notes. Judy1(3)
NAME | SYNOPSIS | DESCRIPTION | EXAMPLE | AUTHOR | SEE ALSO
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=Judy1&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>