Judy1 functions represent
Boolean values (bit maps) in a Judy array. These functions support
arrays of one-bit (binary) values, representing true/false, valid/invalid,
or present/absent.
The table below
lists the Judy1 functions. For more information, see the Judy1(3X
)man page.
Table 3-2 Title not available (Using Judy1)
Judy1 functions | Actions |
|---|
Judy1Test | Indicates whether the index is set in
the array. |
Judy1Set | Sets a bit in the array. |
Judy1Unset | Clears a bit in the array. |
Judy1First | Locates the first index set in the array
(including the passed index). |
Judy1Next | Typically continues a sorted order scan
of the set indexes in a bit array or locates a neighbor of an index. |
Judy1Last | Typically begins a reverse sorted-order
scan of the set indexes in a bit array. |
Judy1Prev | Typically continues a reverse sorted-order
scan of the set indexes in a bit array or locates a neighbor of
an index. |
Judy1Count | Returns the count of set indexes between
the specified indexes, including the specified indexes themselves. |
Judy1ByCount | Locates the Nth
index (N=count) that is set in the bit array. |
Judy1FreeArray() | Frees the entire bit array. This is much
faster than using Judy1Next and Judy1Unset. |
Judy1 example
You
can find the code for this example and others on the Judy web site: http://devresource.hp.com/judy/
// Judy 1 Example code: bit set operations.// There should be a header file that defines the bit operation types:#define JUDY1OP_AND 1L#define JUDY1OP_OR 2L#define JUDY1OP_ANDNOT 3L#include "Judy.h"/******************************************************************** Name: Judy1Op* Description:* Logical set operations on Judy1 arrays.* All of these operations can be done on an unbounded array.* Parameters:* PPvoid_t PPDest (OUT)* Ptr to the Judy destination array.* Any initial value pointed to by PPDest is ignored.* Pvoid_t PSet1 (IN)* First Judy1 set.* This will be NULL for an empty Judy1 array.* Pvoid_t PSet2 (IN)* Second Judy1 set.* This will be NULL for an empty Judy1 array.* ulong_t Operation (IN)* Operation to be performed (ie. PSet1 {Operation} PSet2)* Valid Operation values are:* JUDY1OP_AND - intersection of two sets* JUDY1OP_OR - union of two sets* JUDY1OP_ANDNOT - set1 with set2 removed* JError_t * PJError (OUT)* Judy Error struct used to return Judy error.* Returns:* !JERR if successful* JERR if an error occurs * If the error is a caller error (invalid Operation or no PPDest) * then the PJError error code will be JU_ERRNO_NONE. */int Judy1Op (PPvoid_t PPDest, Pvoid_t PSet1, Pvoid_t PSet2, ulong_t Operation, JError_t * PJError){ Pvoid_t PnewJArray = 0; // empty Judy array ulong_t Index1 = 0L; ulong_t Index2 = 0L; int Judy_rv; if (!PPDest) return JERR; switch (Operation) { case JUDY1OP_AND: // step through each array looking for index matches Judy_rv = Judy1First(PSet1, &Index1, PJError); Judy_rv += Judy1First(PSet2, &Index2, PJError); while(Judy_rv == 2) { if (Index1 < Index2) { Index1 = Index2; Judy_rv = Judy1First(PSet1, &Index1, PJError); } else if (Index1 > Index2) { Index2 = Index1; Judy_rv = Judy1First(PSet2, &Index2, PJError); } else { // do the AND Judy_rv = Judy1Set(&PnewJArray, Index1, PJError); if (Judy_rv == JERR) return JERR; // bump to the next bits Judy_rv = Judy1Next(PSet1, &Index1, PJError); Judy_rv += Judy1Next(PSet2, &Index2, PJError); } } *PPDest = PnewJArray; break; case JUDY1OP_OR: /* Set all the bits from PSet1 */ for (Index1 = 0L, Judy_rv = Judy1First(PSet1, &Index1, PJError); Judy_rv == 1; Judy_rv = Judy1Next(PSet1, &Index1, PJError)) { if (Judy1Set(&PnewJArray, Index1, PJError) == JERR) return JERR; } /* Set all the bits from PSet2 */ for (Index1 = 0L, Judy_rv = Judy1First(PSet2, &Index1, PJError); Judy_rv == 1; Judy_rv = Judy1Next(PSet2, &Index1, PJError)) { if (Judy1Set(&PnewJArray, Index1, PJError) == JERR) return JERR; } *PPDest = PnewJArray; break; case JUDY1OP_ANDNOT: // PSet1 with PSet2 removed // 0010 = PSet1(1010) ANDNOT PSet2(1100) for (Index1 = 0L, Judy_rv = Judy1First(PSet1, &Index1, PJError); Judy_rv == 1; Judy_rv = Judy1Next(PSet1, &Index1, PJError)) { // if bit doesn't exist in PSet2, then add to result if (0 == Judy1Test(PSet2, Index1, PJError)) { if (Judy1Set(&PnewJArray, Index1, PJError) == JERR) return JERR; } } *PPDest = PnewJArray; break; default: return JERR; } return !JERR;} /* Judy1Op */
Printable version
