5 lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall,
6 lh_doall_arg, lh_error - dynamic hash table
10 #include <openssl/lhash.h>
12 LHASH *lh_new(LHASH_HASH_FN_TYPE hash, LHASH_COMP_FN_TYPE compare);
13 void lh_free(LHASH *table);
15 void *lh_insert(LHASH *table, void *data);
16 void *lh_delete(LHASH *table, void *data);
17 void *lh_retrieve(LHASH *table, void *data);
19 void lh_doall(LHASH *table, LHASH_DOALL_FN_TYPE func);
20 void lh_doall_arg(LHASH *table, LHASH_DOALL_ARG_FN_TYPE func,
23 int lh_error(LHASH *table);
25 typedef int (*LHASH_COMP_FN_TYPE)(void *, void *);
26 typedef unsigned long (*LHASH_HASH_FN_TYPE)(void *);
27 typedef void (*LHASH_DOALL_FN_TYPE)(void *);
28 typedef void (*LHASH_DOALL_ARG_FN_TYPE)(void *, void *);
32 This library implements dynamic hash tables. The hash table entries
33 can be arbitrary structures. Usually they consist of key and value
36 lh_new() creates a new B<LHASH> structure. B<hash> takes a pointer to
37 the structure and returns an unsigned long hash value of its key
38 field. The hash value is normally truncated to a power of 2, so make
39 sure that your hash function returns well mixed low order
40 bits. B<compare> takes two arguments, and returns 0 if their keys are
41 equal, non-zero otherwise. If your hash table will contain items of
42 some uniform type, and similarly the B<hash> and B<compare> callbacks
43 hash or compare the same type, then the B<DECLARE_LHASH_HASH_FN> and
44 B<IMPLEMENT_LHASH_COMP_FN> macros can be used to create callback
45 wrappers of the prototypes required in lh_new(). These provide
46 per-variable casts before calling the type-specific callbacks written
47 by the application author. These macros are defined as;
49 #define DECLARE_LHASH_HASH_FN(f_name,o_type) \
50 unsigned long f_name##_LHASH_HASH(void *)
51 #define IMPLEMENT_LHASH_HASH_FN(f_name,o_type) \
52 unsigned long f_name##_LHASH_HASH(void *arg) { \
53 o_type a = (o_type)arg; \
55 #define LHASH_HASH_FN(f_name) f_name##_LHASH_HASH
57 #define DECLARE_LHASH_COMP_FN(f_name,o_type) \
58 int f_name##_LHASH_COMP(void *, void *)
59 #define IMPLEMENT_LHASH_COMP_FN(f_name,o_type) \
60 int f_name##_LHASH_COMP(void *arg1, void *arg2) { \
61 o_type a = (o_type)arg1; \
62 o_type b = (o_type)arg2; \
64 #define LHASH_COMP_FN(f_name) f_name##_LHASH_COMP
66 An example of a hash table storing (pointers to) a structure type 'foo'
67 could be defined as follows;
69 unsigned long foo_hash(foo *tohash);
70 int foo_compare(foo *arg1, foo *arg2);
71 static IMPLEMENT_LHASH_HASH_FN(foo_hash, foo *)
72 static IMPLEMENT_LHASH_COMP_FN(foo_compare, foo *);
74 int main(int argc, char *argv[]) {
75 LHASH *hashtable = lh_new(LHASH_HASH_FN(foo_hash),
76 LHASH_COMP_FN(foo_compare));
80 lh_free() frees the B<LHASH> structure B<table>. Allocated hash table
81 entries will not be freed; consider using lh_doall() to deallocate any
82 remaining entries in the hash table.
84 lh_insert() inserts the structure pointed to by B<data> into B<table>.
85 If there already is an entry with the same key, the old value is
86 replaced. Note that lh_insert() stores pointers, the data are not
89 lh_delete() deletes an entry from B<table>.
91 lh_retrieve() looks up an entry in B<table>. Normally, B<data> is
92 a structure with the key field(s) set; the function will return a
93 pointer to a fully populated structure.
95 lh_doall() will, for every entry in the hash table, call B<func> with
96 the data item as parameters.
97 This function can be quite useful when used as follows:
98 void cleanup(STUFF *a)
100 lh_doall(hash,(LHASH_DOALL_FN_TYPE)cleanup);
102 This can be used to free all the entries. lh_free() then cleans up the
103 'buckets' that point to nothing. When doing this, be careful if you
104 delete entries from the hash table in B<func>: the table may decrease
105 in size, moving item that you are currently on down lower in the hash
106 table. This could cause some entries to be skipped. The best
107 solution to this problem is to set hash-E<gt>down_load=0 before you
108 start. This will stop the hash table ever being decreased in size.
110 lh_doall_arg() is the same as lh_doall() except that B<func> will
111 be called with B<arg> as the second argument and B<func> should be
112 of type B<LHASH_DOALL_ARG_FN_TYPE> (a callback prototype that is
113 passed an extra argument).
115 lh_error() can be used to determine if an error occurred in the last
116 operation. lh_error() is a macro.
120 lh_new() returns B<NULL> on error, otherwise a pointer to the new
123 When a hash table entry is replaced, lh_insert() returns the value
124 being replaced. B<NULL> is returned on normal operation and on error.
126 lh_delete() returns the entry being deleted. B<NULL> is returned if
127 there is no such value in the hash table.
129 lh_retrieve() returns the hash table entry if it has been found,
132 lh_error() returns 1 if an error occurred in the last operation, 0
135 lh_free(), lh_doall() and lh_doall_arg() return no values.
139 lh_insert() returns B<NULL> both for success and error.
143 The following description is based on the SSLeay documentation:
145 The B<lhash> library implements a hash table described in the
146 I<Communications of the ACM> in 1991. What makes this hash table
147 different is that as the table fills, the hash table is increased (or
148 decreased) in size via OPENSSL_realloc(). When a 'resize' is done, instead of
149 all hashes being redistributed over twice as many 'buckets', one
150 bucket is split. So when an 'expand' is done, there is only a minimal
151 cost to redistribute some values. Subsequent inserts will cause more
152 single 'bucket' redistributions but there will never be a sudden large
153 cost due to redistributing all the 'buckets'.
155 The state for a particular hash table is kept in the B<LHASH> structure.
156 The decision to increase or decrease the hash table size is made
157 depending on the 'load' of the hash table. The load is the number of
158 items in the hash table divided by the size of the hash table. The
159 default values are as follows. If (hash->up_load E<lt> load) =E<gt>
160 expand. if (hash-E<gt>down_load E<gt> load) =E<gt> contract. The
161 B<up_load> has a default value of 1 and B<down_load> has a default value
162 of 2. These numbers can be modified by the application by just
163 playing with the B<up_load> and B<down_load> variables. The 'load' is
164 kept in a form which is multiplied by 256. So
165 hash-E<gt>up_load=8*256; will cause a load of 8 to be set.
167 If you are interested in performance the field to watch is
168 num_comp_calls. The hash library keeps track of the 'hash' value for
169 each item so when a lookup is done, the 'hashes' are compared, if
170 there is a match, then a full compare is done, and
171 hash-E<gt>num_comp_calls is incremented. If num_comp_calls is not equal
172 to num_delete plus num_retrieve it means that your hash function is
173 generating hashes that are the same for different values. It is
174 probably worth changing your hash function if this is the case because
175 even if your hash table has 10 items in a 'bucket', it can be searched
176 with 10 B<unsigned long> compares and 10 linked list traverses. This
177 will be much less expensive that 10 calls to you compare function.
179 lh_strhash() is a demo string hashing function:
181 unsigned long lh_strhash(const char *c);
183 Since the B<LHASH> routines would normally be passed structures, this
184 routine would not normally be passed to lh_new(), rather it would be
185 used in the function passed to lh_new().
189 L<lh_stats(3)|lh_stats(3)>
193 The B<lhash> library is available in all versions of SSLeay and OpenSSL.
194 lh_error() was added in SSLeay 0.9.1b.
196 This manpage is derived from the SSLeay documentation.