Judy(3pm)

1Judy(3)               User Contributed Perl Documentation              Judy(3)
2
3
4

NAME

6       Judy - Library for creating and accessing dynamic arrays
7

DESCRIPTION

9       The Judy family of functions supports fully dynamic arrays. These
10       arrays may be indexed by a 32- or 64-bit word (depending on processor
11       word size) (Judy::1, Judy::L), a null terminated string (Judy::SL), or
12       an ordinary perl string (Judy::HS).
13
14       Judy arrays are both speed- and memory-efficient, with no tuning or
15       configuration required, across a wide range of key set types
16       (sequential, periodic, clustered, random). Judy's speed and memory
17       usage are typically better than other data storage models such as
18       skiplists, linked lists, binary, ternary, b-trees, or even hashing, and
19       improves with very large data sets.
20
21       The memory used by a Judy array is nearly proportional to the
22       population (number of elements).
23
24       Since an initial (empty) Judy array is represented by a null pointer,
25       it is possible to construct an array of Judy arrays. In other words, a
26       Judy array's Values can be pointers to other Judy arrays. This makes it
27       very simple to construct an array with an arbitrary number of
28       dimensions or Index sizes.
29
30       The libJudy author believes JudyHS is a good replacement for a hashing
31       method when resizing the hash table is done during population growth. A
32       correctly tuned hash method with a static hash table size and
33       population is unbeatable for speed. However, Judy::HS will perform
34       better than a hashing method with smaller and larger populations than
35       the optimum hash table size. JudyHS does not have a degenerate
36       performance case where knowledge of the hash algorithm can be
37       exploited. (I.E. JudyHS does not use a linked list to handle hash
38       collisions, it uses a tree of JudyL arrays and a virtual hash table
39       size of 4 billion).
40

SYNOPSIS

42       Judy::1:
43           This can be thought of as a bit vector. For a comparison between
44           Judy::1 and "vec" in perlfunc, take a look at
45           <http://perlmonks.org/?node_id=732843>.
46
47               # Turn the 43rd bit on. A bit like:
48               #
49               #   vec( $str, 42, 1 ) = 1
50               #
51               Judy::1::Set(
52                   $judy_1,
53                   42
54               );
55
56       Judy::L
57           Maps an integer to another integer. This is sort of like a very
58           compact perl hash where the only allowed keys and values are
59           integers.
60
61               # A bit like:
62               #
63               #   $array[ 42 ] = 9000
64               #
65               Judy::L::Set(
66                   $judy_l,
67                   42,
68                   9000
69               );
70
71       Judy::SL
72           Maps null terminated strings to integers.
73
74               # A bit like:
75               #
76               #   $hash{world} = 9000
77               #
78               Judy::SL::Set(
79                   $judy_sl,
80                   'world',
81                   9000
82               );
83
84       Judy::HS
85           Maps perl strings to integers.
86
87               # A bit like:
88               #
89               #   $hash{world} = 9000
90               #
91               Judy::HS::Set(
92                   $judy_sl,
93                   'world',
94                   9000
95               );
96

Multi-dimensional Judy::L/Judy::SL/Judy::HS Arrays

98       Storing a pointer to another Judy::L array in a Judy::L array's Value
99       is a simple way to support dynamic multi-dimensional Judy::L arrays.
100       These arrays (or trees) built using Judy::L arrays are very fast and
101       memory efficient. (In fact, that is how JudySL and JudyHS are
102       implemented). An arbitrary number of dimensions can be realized this
103       way. To terminate the number of dimensions (or tree), the Value pointer
104       is marked to NOT point to another Judy array. A "Judy::JLAP_INVALID"
105       flag is used in the least significant bit(s) of the pointer. After the
106       flag "Judy::JLAP_INVALID" is removed, it is used as a pointer to the
107       users data.
108
109       Note: The current version of Judy.h changed this flag from 0x4 to 0x1
110       to allow for a malloc() that does not deliver memory on an 8 byte
111       aligned boundry (such as old v algrind).
112
113       The following example code segment can be used to dive into a multi-
114       dimensional Judy::L using an API similar to Tye McQueen's Data::Diver.
115       This makes a Judy::HS object and looks past the public API as an
116       example of a multi-dimensional Judy::* structure.
117
118           # For kicks, allocate a Judy::HS object and look inside it a
119           # little bit.
120           use Judy::HS;
121           Judy::HS::Set( my ($judy), 'abcd', 42 );
122           Dive( $judy, 4 );
123
124           use Judy;
125           use Judy::L;
126           sub Dive {
127               my ( $judy, @walk ) = @_;
128
129               my ( $pvalue, $value );
130               for my $key ( @walk ) {
131                   return if ! $judy;
132
133                   # Advance to next dimension.
134                   ( $pvalue, $value ) = Judy::L::Get( $judy, $key );
135
136                   # Check if pointer to user buffer
137                   last if $value & Judy::JLAP_INVALID;
138
139                   $judy = $value;
140               }
141
142               if ( $value & JLAP_INVALID ) {
143                   # Remove our flag.
144                   $value &= ~ Judy::JLAP_INVALID;
145
146                   # Return the value.
147                   printf "User object pointer is 0x%x at 0x%x\n", $value, $pvalue;
148               }
149               else {
150                   warn sprintf "Judy::* object pointer is 0x%x at 0x%x\n", $value, $pvalue;
151               }
152               return ( $pvalue, $value );
153           }
154
155       Note: This works because malloc() guarantees to return a pointer with
156       the least bit(s) == 0x0. You must remove JLAP_INVALID before using the
157       pointer.
158

CONSTANTS

160       JLAP_INVALID
161       PJERR
162

FILES

175       Locations of interest include: http://sourceforge.net/projects/judy --
176       project downloads file:/usr/share/doc/Judy/ -- for HTML version of man
177       pages.  /usr/share/doc/Judy/demo/ -- demonstration program source
178       files.
179
180       The author attempted to write interesting application notes using
181       advanced features of Judy. They may be found at
182       "http://judy.sourceforge.net/application/ (Some may be out of date).
183

ERRORS & WARNINGS

185       File '%s', line %d: %s(), JU_ERRNO_* == %d, ID == %d
186           See the header file Judy.h from the Judy C source library. You
187           already have a local copy of this to have been able to build this
188           perl library.
189
190       Sorry, can't use keys longer than %d for now. This is a bug.
191       Coercing %d to 0. Can't use negative values as keys.
192       Truncating %d to %d because your number is larger than fits in a signed
193       integer
194       Truncating %d to %u because your number is larger than fits in an
195       unsigned integer
196       Truncating %d to %d because your number is smaller than fits in a
197       signed integer
198       Dropping UTF8 flag for '%s'
199

BUGS

201       Please report any bugs or feature requests to "bug-Judy-HS at
202       rt.cpan.org", or through the web interface at
203       <http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Judy-HS>.  I will be
204       notified, and then you'll automatically be notified of progress on your
205       bug as I make changes.
206

SUPPORT

208       You can find documentation for this module with the perldoc command.
209
210         perldoc Judy
211
212       You can also look for information at:
213
214       •   RT: CPAN's request tracker
215
216           <http://rt.cpan.org/NoAuth/Bugs.html?Dist=Judy>
217
218       •   AnnoCPAN: Annotated CPAN documentation
219
220           <http://annocpan.org/dist/Judy>
221
222       •   CPAN Ratings
223
224           <http://cpanratings.perl.org/d/Judy>
225
226       •   Search CPAN
227
228           <http://search.cpan.org/dist/Judy/>
229

ACKNOWLEDGEMENTS

231       Doug Baskins, totally.
232
233       Michael Schwern for writing Alien::SVN which made this possible.
234
235       Tye McQueen for inspiring the minimal API.
236
237       Yitzchak Scott-Thoennes for reminding me that perl's magic requires
238       extra care and attention.
239

COPYRIGHT & LICENSE

241       Copyright 2012 Josh Jore, all rights reserved.
242
243       This program is free software; you can redistribute it and/or modify it
244       under the same terms as Perl itself.
245

SOURCE AVAILABILITY

247       This source is in Github: <git://github.com/jbenjore/judy-hs.git>
248

AUTHOR

250       Judy was invented by Doug Baskins (dougbaskins .AT, yahoo.com) and
251       implemented by Hewlett-Packard. (Note: Judy is named for the inventor's
252       sister, after discarding many proposed names.)
253
254       The perl wrapper was written by Josh Jore
255
256
257
258perl v5.32.1                      2021-01-27                           Judy(3)