f8eaec2fe3f99ae8ecff655e4eab425256f28dda
[openssl.git] / doc / crypto / lhash.pod
1 =pod
2
3 =head1 NAME
4
5 lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall,
6 lh_doall_arg, lh_error - dynamic hash table
7
8 =head1 SYNOPSIS
9
10  #include <openssl/lhash.h>
11
12  LHASH *lh_new(LHASH_HASH_FN_TYPE hash, LHASH_COMP_FN_TYPE compare);
13  void lh_free(LHASH *table);
14
15  void *lh_insert(LHASH *table, void *data);
16  void *lh_delete(LHASH *table, void *data);
17  void *lh_retrieve(LHASH *table, void *data);
18
19  void lh_doall(LHASH *table, LHASH_DOALL_FN_TYPE func);
20  void lh_doall_arg(LHASH *table, LHASH_DOALL_ARG_FN_TYPE func,
21           void *arg);
22
23  int lh_error(LHASH *table);
24
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 *);
29
30 =head1 DESCRIPTION
31
32 This library implements dynamic hash tables. The hash table entries
33 can be arbitrary structures. Usually they consist of key and value
34 fields.
35
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;
48
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; \
54                  return f_name(a); }
55  #define LHASH_HASH_FN(f_name) f_name##_LHASH_HASH
56
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; \
63                  return f_name(a,b); }
64  #define LHASH_COMP_FN(f_name) f_name##_LHASH_COMP
65
66 An example of a hash table storing (pointers to) a structure type 'foo'
67 could be defined as follows;
68
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 *);
73  /* ... */
74  int main(int argc, char *argv[]) {
75          LHASH *hashtable = lh_new(LHASH_HASH_FN(foo_hash),
76                                    LHASH_COMP_FN(foo_compare));
77          /* ... */
78  }
79
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.
83
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
87 copied.
88
89 lh_delete() deletes an entry from B<table>.
90
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.
94
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)
99   { STUFF_free(a); }
100  lh_doall(hash,(LHASH_DOALL_FN_TYPE)cleanup);
101  lh_free(hash);
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.
109
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).
114
115 lh_error() can be used to determine if an error occurred in the last
116 operation. lh_error() is a macro.
117
118 =head1 RETURN VALUES
119
120 lh_new() returns B<NULL> on error, otherwise a pointer to the new
121 B<LHASH> structure.
122
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.
125
126 lh_delete() returns the entry being deleted.  B<NULL> is returned if
127 there is no such value in the hash table.
128
129 lh_retrieve() returns the hash table entry if it has been found,
130 B<NULL> otherwise.
131
132 lh_error() returns 1 if an error occurred in the last operation, 0
133 otherwise.
134
135 lh_free(), lh_doall() and lh_doall_arg() return no values.
136
137 =head1 BUGS
138
139 lh_insert() returns B<NULL> both for success and error.
140
141 =head1 INTERNALS
142
143 The following description is based on the SSLeay documentation:
144
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'.
154
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.
166
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.
178
179 lh_strhash() is a demo string hashing function:
180
181  unsigned long lh_strhash(const char *c);
182
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().
186
187 =head1 SEE ALSO
188
189 L<lh_stats(3)|lh_stats(3)>
190
191 =head1 HISTORY
192
193 The B<lhash> library is available in all versions of SSLeay and OpenSSL.
194 lh_error() was added in SSLeay 0.9.1b.
195
196 This manpage is derived from the SSLeay documentation.
197
198 =cut