1Judy::1(3) User Contributed Perl Documentation Judy::1(3)
2
6 Judy::1 - Efficient integer to bit map
7
9 use Judy::1 qw( Set Get Unset Count MemUsed First );
10 my $judy;
12 print Set( $judy, 123456 )
13 ? "ok - bit successfully set at 123456\n"
14 : "not ok - bit already set at 123456\n";
15 print Get( $judy, 654321 )
17 ? "not ok - set bit at 654321\n"
18 : "ok - bit not set at 654321\n";
19 my ( $count ) = Count( $judy, 0, -1 );
21 print "$count bits set in Judy::1 array\n";
22 my ( $key ) = First( $judy, 0 );
24 if ( defined $key ) {
25 print "ok - first bit set is at $key\n";
26 }
27 else {
28 print "not ok - no bits set in array\n";
29 }
30 printf "$count Keys used %d bytes of memory\n", MemUsed( $judy );
32 print Unset( $judy, 123456 )
34 ? "ok - bit successfully unset at 123456\n"
35 : "not ok - bit was not unset at 123456\n";
36
38 All functions are exportable by Sub::Exporter.
39
41 Judy::1 is the equivalent of a bit array or bit map. A bit is addressed
42 by an $Key. The array may be sparse, and the $Key may be any native
43 integer. If a key is present, it represents a set bit. If a key is
44 absent, it represents an unset bit.
45 Nothing special is required to allocate a Judy::1 array. Just start
47 using it.
48 my $judy;
50 if ( Get( $judy, 10 ) ) {
51 ...
52 }
53 Memory to support the array is allocated as bits are set, and released
55 as bits are unset. If the Judy::1 pointer ($Judy) is 0 or undef, all
56 bits are unset (and the Judy::1 array requires no memory).
57 As with an ordinary array, a Judy::1 array contains no duplicate keys.
59
61 $Judy - Judy::1 array
62 $Key - integer
63 bool - boolean
64 count - integer
66 bool = Set( $Judy, $Key )
67 Insert/set $Key's bit in the Judy::1 array $Judy. Return true if the
68 bit was previously unset, false otherwise.
69 bool = Unset( $Judy, $Key )
71 Unset $Key's bit in the Judy::1 array $Judy; that is, remove $Key from
72 the Judy::1 array. Return true if the bit was previously set, false
73 otherwise.
74 bool = Delete( $Judy, $Key )
76 Alias for "Unset()".
77 bool = Test( $Judy, $Key )
79 Test if $Key's bit is set in the Judy::1 array $Judy. Return true if
80 the bit is set, false otherwise.
81 bool = Get( $Judy, $Key )
83 Alias for "Test()".
84 count = Count( $Judy, $Key1, $Key2 )
86 Count the number of set bits between $Key1 and $Key2 (inclusive). To
87 count all set bits in a Judy::1 bit array, use:
88 $count = Count( $judy, 0, -1 );
90 Note: The -1 promotes to the maximum integer, that is, all ones.
92 $Key = Nth( $Judy, $Nth )
94 Locate the c<$Nth> key that is present in the Judy::1 array $Judy
95 ("$Nth = 1" returns the first key present). To refer to the last key in
96 a fully populated array (all keys present, which is rare), use "$Nth =
97 0".
98 Returns nothing if there is not an nth key.
100 bytes = Free( $Judy )
102 Free the entire Judy::1 array $Judy (much faster than using a Next(),
103 Unset() loop). Returns the number of bytes freed. $Judy is set to 0.
104 bytes = MemUsed( $Judy )
106 Returns the number of bytes of memory currently in use by Judy::1 array
107 $Judy. This is a very fast routine, and may be used after a Set() or
108 Unset() call with little performance impact.
109
111 The Judy::1 search functions allow you to search for set or unset bits
112 in the array. You may search inclusively or exclusively, in either
113 forward or reverse directions.
114 $Key = First( $Judy, $Key )
116 Search (inclusive) for the first set $Key that is equal to or greater
117 than the passed $Key. (Start with $Key = 0 to find the first key in the
118 array.) First() is typically used to begin a sorted-order scan of the
119 keys present in a Judy::1 array.
120 $Key = Next( $Judy, $Key )
122 Search (exclusive) for the next key present that is greater than the
123 passed $Key. Next() is typically used to continue a sorted-order scan
124 of the keys present in a Judy::1 array, or to locate a "neighbor" of a
125 given key.
126 $Key = Last( $Judy, $Key )
128 Search (inclusive) for the last key present that is equal to or less
129 than the passed $Key. (Start with $Key = -1, that is, all ones, to find
130 the last key in the array.) Last() is typically used to begin a
131 reverse-sorted-order scan of the keys present in a Judy::1 array.
132 $Key = Prev( $Judy, $Key )
134 Search (exclusive) for the previous key present that is less than the
135 passed $Key. Prev() is typically used to continue a reverse-sorted-
136 order scan of the keys present in a Judy::1 array, or to locate a
137 "neighbor" of a given key.
138 $Key = FirstEmpty( $Judy, $Key )
140 Search (inclusive) for the first absent key that is equal to or greater
141 than the passed $Key. (Start with $Key = 0 to find the first key absent
142 in the array.)
143 $Key = NextEmpty( $Judy, $Key )
145 Search (exclusive) for the next absent key that is greater than the
146 passed $Key.
147 $Key = LastEmpty( $Judy, $Key )
149 Search (inclusive) for the last absent key that is equal to or less
150 than the passed $Key. (Start with $Key = -1 to find the last key absent
151 in the array.)
152 $Key = PrevEmpty( $Judy, $Key )
154 Search (exclusive) for the previous absent key that is less than the
155 passed $Key.
156
158 See Judy.
159
161 See Judy.
162
164 See Judy.
165perl v5.34.0 2022-01-21 Judy::1(3)