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