doc/man3/OPENSSL_LH_COMPFUNC.pod

   1 =pod
   2
   3 =head1 NAME
   4
   5 LHASH, LHASH_OF, DEFINE_LHASH_OF_EX, DEFINE_LHASH_OF,
   6 OPENSSL_LH_COMPFUNC, OPENSSL_LH_HASHFUNC, OPENSSL_LH_DOALL_FUNC,
   7 LHASH_DOALL_ARG_FN_TYPE,
   8 IMPLEMENT_LHASH_HASH_FN, IMPLEMENT_LHASH_COMP_FN,
   9 lh_TYPE_new, lh_TYPE_free, lh_TYPE_flush,
  10 lh_TYPE_insert, lh_TYPE_delete, lh_TYPE_retrieve,
  11 lh_TYPE_doall, lh_TYPE_doall_arg, lh_TYPE_num_items, lh_TYPE_get_down_load,
  12 lh_TYPE_set_down_load, lh_TYPE_error,
  13 OPENSSL_LH_new, OPENSSL_LH_free,  OPENSSL_LH_flush,
  14 OPENSSL_LH_insert, OPENSSL_LH_delete, OPENSSL_LH_retrieve,
  15 OPENSSL_LH_doall, OPENSSL_LH_doall_arg, OPENSSL_LH_doall_arg_thunk,
  16 OPENSSL_LH_set_thunks, OPENSSL_LH_num_items,
  17 OPENSSL_LH_get_down_load, OPENSSL_LH_set_down_load, OPENSSL_LH_error
  18 - dynamic hash table
  19
  20 =head1 SYNOPSIS
  21
  22 =for openssl generic
  23
  24  #include <openssl/lhash.h>
  25
  26  LHASH_OF(TYPE)
  27
  28  DEFINE_LHASH_OF_EX(TYPE);
  29
  30  LHASH_OF(TYPE) *lh_TYPE_new(OPENSSL_LH_HASHFUNC hash, OPENSSL_LH_COMPFUNC compare);
  31  void lh_TYPE_free(LHASH_OF(TYPE) *table);
  32  void lh_TYPE_flush(LHASH_OF(TYPE) *table);
  33  OPENSSL_LHASH *OPENSSL_LH_set_thunks(OPENSSL_LHASH *lh,
  34                                       OPENSSL_LH_HASHFUNCTHUNK hw,
  35                                       OPENSSL_LH_COMPFUNCTHUNK cw,
  36                                       OPENSSL_LH_DOALL_FUNC_THUNK daw,
  37                                       OPENSSL_LH_DOALL_FUNCARG_THUNK daaw)
  38
  39  TYPE *lh_TYPE_insert(LHASH_OF(TYPE) *table, TYPE *data);
  40  TYPE *lh_TYPE_delete(LHASH_OF(TYPE) *table, TYPE *data);
  41  TYPE *lh_TYPE_retrieve(LHASH_OF(TYPE) *table, TYPE *data);
  42
  43  void lh_TYPE_doall(LHASH_OF(TYPE) *table, OPENSSL_LH_DOALL_FUNC func);
  44  void lh_TYPE_doall_arg(LHASH_OF(TYPE) *table, OPENSSL_LH_DOALL_FUNCARG func,
  45                         TYPE *arg);
  46  void OPENSSL_LH_doall_arg_thunk(OPENSSL_LHASH *lh,
  47                                  OPENSSL_LH_DOALL_FUNCARG_THUNK daaw,
  48                                  OPENSSL_LH_DOALL_FUNCARG fn, void *arg)
  49
  50  unsigned long lh_TYPE_num_items(OPENSSL_LHASH *lh);
  51  unsigned long lh_TYPE_get_down_load(OPENSSL_LHASH *lh);
  52  void lh_TYPE_set_down_load(OPENSSL_LHASH *lh, unsigned long dl);
  53
  54  int lh_TYPE_error(LHASH_OF(TYPE) *table);
  55
  56  typedef int (*OPENSSL_LH_COMPFUNC)(const void *, const void *);
  57  typedef unsigned long (*OPENSSL_LH_HASHFUNC)(const void *);
  58  typedef void (*OPENSSL_LH_DOALL_FUNC)(const void *);
  59  typedef void (*LHASH_DOALL_ARG_FN_TYPE)(const void *, const void *);
  60
  61  OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c);
  62  void OPENSSL_LH_free(OPENSSL_LHASH *lh);
  63  void OPENSSL_LH_flush(OPENSSL_LHASH *lh);
  64
  65  void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data);
  66  void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data);
  67  void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data);
  68
  69  void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func);
  70  void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void *arg);
  71
  72  unsigned long OPENSSL_LH_num_items(OPENSSL_LHASH *lh);
  73  unsigned long OPENSSL_LH_get_down_load(OPENSSL_LHASH *lh);
  74  void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long dl);
  75
  76  int OPENSSL_LH_error(OPENSSL_LHASH *lh);
  77
  78  #define LH_LOAD_MULT   /* integer constant */
  79
  80 The following macro is deprecated:
  81
  82  DEFINE_LHASH_OF(TYPE);
  83
  84 =head1 DESCRIPTION
  85
  86 This library implements type-checked dynamic hash tables. The hash
  87 table entries can be arbitrary structures. Usually they consist of key
  88 and value fields.  In the description here, B<I<TYPE>> is used a placeholder
  89 for any of the OpenSSL datatypes, such as I<SSL_SESSION>.
  90
  91 To define a new type-checked dynamic hash table, use B<DEFINE_LHASH_OF_EX>().
  92 B<DEFINE_LHASH_OF>() was previously used for this purpose, but is now
  93 deprecated. The B<DEFINE_LHASH_OF_EX>() macro provides all functionality of
  94 B<DEFINE_LHASH_OF>() except for certain deprecated statistics functions (see
  95 OPENSSL_LH_stats(3)).
  96
  97 B<lh_I<TYPE>_new>() creates a new B<LHASH_OF>(B<I<TYPE>>) structure to store
  98 arbitrary data entries, and specifies the 'hash' and 'compare'
  99 callbacks to be used in organising the table's entries.  The I<hash>
 100 callback takes a pointer to a table entry as its argument and returns
 101 an unsigned long hash value for its key field.  The hash value is
 102 normally truncated to a power of 2, so make sure that your hash
 103 function returns well mixed low order bits.  The I<compare> callback
 104 takes two arguments (pointers to two hash table entries), and returns
 105 0 if their keys are equal, nonzero otherwise.
 106
 107 If your hash table
 108 will contain items of some particular type and the I<hash> and
 109 I<compare> callbacks hash/compare these types, then the
 110 B<IMPLEMENT_LHASH_HASH_FN> and B<IMPLEMENT_LHASH_COMP_FN> macros can be
 111 used to create callback wrappers of the prototypes required by
 112 B<lh_I<TYPE>_new>() as shown in this example:
 113
 114  /*
 115   * Implement the hash and compare functions; "stuff" can be any word.
 116   */
 117  static unsigned long stuff_hash(const TYPE *a)
 118  {
 119      ...
 120  }
 121  static int stuff_cmp(const TYPE *a, const TYPE *b)
 122  {
 123      ...
 124  }
 125
 126  /*
 127   * Implement the wrapper functions.
 128   */
 129  static IMPLEMENT_LHASH_HASH_FN(stuff, TYPE)
 130  static IMPLEMENT_LHASH_COMP_FN(stuff, TYPE)
 131
 132 If the type is going to be used in several places, the following macros
 133 can be used in a common header file to declare the function wrappers:
 134
 135  DECLARE_LHASH_HASH_FN(stuff, TYPE)
 136  DECLARE_LHASH_COMP_FN(stuff, TYPE)
 137
 138 Then a hash table of B<I<TYPE>> objects can be created using this:
 139
 140  LHASH_OF(TYPE) *htable;
 141
 142  htable = B<lh_I<TYPE>_new>(LHASH_HASH_FN(stuff), LHASH_COMP_FN(stuff));
 143
 144 B<lh_I<TYPE>_free>() frees the B<LHASH_OF>(B<I<TYPE>>) structure
 145 I<table>. Allocated hash table entries will not be freed; consider
 146 using B<lh_I<TYPE>_doall>() to deallocate any remaining entries in the
 147 hash table (see below).
 148
 149 B<lh_I<TYPE>_flush>() empties the B<LHASH_OF>(B<I<TYPE>>) structure I<table>. New
 150 entries can be added to the flushed table.  Allocated hash table entries
 151 will not be freed; consider using B<lh_I<TYPE>_doall>() to deallocate any
 152 remaining entries in the hash table (see below).
 153
 154 B<lh_I<TYPE>_insert>() inserts the structure pointed to by I<data> into
 155 I<table>.  If there already is an entry with the same key, the old
 156 value is replaced. Note that B<lh_I<TYPE>_insert>() stores pointers, the
 157 data are not copied.
 158
 159 B<lh_I<TYPE>_delete>() deletes an entry from I<table>.
 160
 161 B<lh_I<TYPE>_retrieve>() looks up an entry in I<table>. Normally, I<data>
 162 is a structure with the key field(s) set; the function will return a
 163 pointer to a fully populated structure.
 164
 165 B<lh_I<TYPE>_doall>() will, for every entry in the hash table, call
 166 I<func> with the data item as its parameter.
 167 For example:
 168
 169  /* Cleans up resources belonging to 'a' (this is implemented elsewhere) */
 170  void TYPE_cleanup_doall(TYPE *a);
 171
 172  /* Implement a prototype-compatible wrapper for "TYPE_cleanup" */
 173  IMPLEMENT_LHASH_DOALL_FN(TYPE_cleanup, TYPE)
 174
 175  /* Call "TYPE_cleanup" against all items in a hash table. */
 176  lh_TYPE_doall(hashtable, LHASH_DOALL_FN(TYPE_cleanup));
 177
 178  /* Then the hash table itself can be deallocated */
 179  lh_TYPE_free(hashtable);
 180
 181 B<lh_I<TYPE>_doall_arg>() is the same as B<lh_I<TYPE>_doall>() except that
 182 I<func> will be called with I<arg> as the second argument and I<func>
 183 should be of type B<LHASH_DOALL_ARG_FN>(B<I<TYPE>>) (a callback prototype
 184 that is passed both the table entry and an extra argument).  As with
 185 lh_doall(), you can instead choose to declare your callback with a
 186 prototype matching the types you are dealing with and use the
 187 declare/implement macros to create compatible wrappers that cast
 188 variables before calling your type-specific callbacks.  An example of
 189 this is demonstrated here (printing all hash table entries to a BIO
 190 that is provided by the caller):
 191
 192  /* Prints item 'a' to 'output_bio' (this is implemented elsewhere) */
 193  void TYPE_print_doall_arg(const TYPE *a, BIO *output_bio);
 194
 195  /* Implement a prototype-compatible wrapper for "TYPE_print" */
 196  static IMPLEMENT_LHASH_DOALL_ARG_FN(TYPE, const TYPE, BIO)
 197
 198  /* Print out the entire hashtable to a particular BIO */
 199  lh_TYPE_doall_arg(hashtable, LHASH_DOALL_ARG_FN(TYPE_print), BIO,
 200                    logging_bio);
 201
 202 Note that it is by default B<not> safe to use B<lh_I<TYPE>_delete>() inside a
 203 callback passed to B<lh_I<TYPE>_doall>() or B<lh_I<TYPE>_doall_arg>(). The
 204 reason for this is that deleting an item from the hash table may result in the
 205 hash table being contracted to a smaller size and rehashed.
 206 B<lh_I<TYPE>_doall>() and B<lh_I<TYPE>_doall_arg>() are unsafe and will exhibit
 207 undefined behaviour under these conditions, as these functions assume the hash
 208 table size and bucket pointers do not change during the call.
 209
 210 If it is desired to use B<lh_I<TYPE>_doall>() or B<lh_I<TYPE>_doall_arg>() with
 211 B<lh_I<TYPE>_delete>(), it is essential that you call
 212 B<lh_I<TYPE>_set_down_load>() with a I<down_load> argument of 0 first. This
 213 disables hash table contraction and guarantees that it will be safe to delete
 214 items from a hash table during a call to B<lh_I<TYPE>_doall>() or
 215 B<lh_I<TYPE>_doall_arg>().
 216
 217 It is never safe to call B<lh_I<TYPE>_insert>() during a call to
 218 B<lh_I<TYPE>_doall>() or B<lh_I<TYPE>_doall_arg>().
 219
 220 B<lh_I<TYPE>_error>() can be used to determine if an error occurred in the last
 221 operation.
 222
 223 B<lh_I<TYPE>_num_items>() returns the number of items in the hash table.
 224
 225 B<lh_I<TYPE>_get_down_load>() and B<lh_I<TYPE>_set_down_load>() get and set the
 226 factor used to determine when the hash table is contracted. The factor is the
 227 load factor at or below which hash table contraction will occur, multiplied by
 228 B<LH_LOAD_MULT>, where the load factor is the number of items divided by the
 229 number of nodes. Setting this value to 0 disables hash table contraction.
 230
 231 OPENSSL_LH_new() is the same as the B<lh_I<TYPE>_new>() except that it is not
 232 type specific. So instead of returning an B<LHASH_OF(I<TYPE>)> value it returns
 233 a B<void *>. In the same way the functions OPENSSL_LH_free(),
 234 OPENSSL_LH_flush(), OPENSSL_LH_insert(), OPENSSL_LH_delete(),
 235 OPENSSL_LH_retrieve(), OPENSSL_LH_doall(), OPENSSL_LH_doall_arg(),
 236 OPENSSL_LH_num_items(), OPENSSL_LH_get_down_load(), OPENSSL_LH_set_down_load()
 237 and OPENSSL_LH_error() are equivalent to the similarly named B<lh_I<TYPE>>
 238 functions except that they return or use a B<void *> where the equivalent
 239 B<lh_I<TYPE>> function returns or uses a B<I<TYPE> *> or B<LHASH_OF(I<TYPE>) *>.
 240 B<lh_I<TYPE>> functions are implemented as type checked wrappers around the
 241 B<OPENSSL_LH> functions. Most applications should not call the B<OPENSSL_LH>
 242 functions directly.
 243
 244 OPENSSL_LH_set_thunks() and OPENSSL_LH_doall_arg_thunk(), while public by
 245 necessity, are actually internal functions and should not be used.
 246
 247 =head1 RETURN VALUES
 248
 249 B<lh_I<TYPE>_new>() and OPENSSL_LH_new() return NULL on error, otherwise a
 250 pointer to the new B<LHASH> structure.
 251
 252 When a hash table entry is replaced, B<lh_I<TYPE>_insert>() or
 253 OPENSSL_LH_insert() return the value being replaced. NULL is returned on normal
 254 operation and on error.
 255
 256 B<lh_I<TYPE>_delete>() and OPENSSL_LH_delete() return the entry being deleted.
 257 NULL is returned if there is no such value in the hash table.
 258
 259 B<lh_I<TYPE>_retrieve>() and OPENSSL_LH_retrieve() return the hash table entry
 260 if it has been found, NULL otherwise.
 261
 262 B<lh_I<TYPE>_error>() and OPENSSL_LH_error() return 1 if an error occurred in
 263 the last operation, 0 otherwise. It's meaningful only after non-retrieve
 264 operations.
 265
 266 B<lh_I<TYPE>_free>(), OPENSSL_LH_free(), B<lh_I<TYPE>_flush>(),
 267 OPENSSL_LH_flush(), B<lh_I<TYPE>_doall>() OPENSSL_LH_doall(),
 268 B<lh_I<TYPE>_doall_arg>() and OPENSSL_LH_doall_arg() return no values.
 269
 270 =head1 NOTE
 271
 272 The LHASH code is not thread safe. All updating operations, as well as
 273 B<lh_I<TYPE>_error>() or OPENSSL_LH_error() calls must be performed under
 274 a write lock. All retrieve operations should be performed under a read lock,
 275 I<unless> accurate usage statistics are desired. In which case, a write lock
 276 should be used for retrieve operations as well. For output of the usage
 277 statistics, using the functions from L<OPENSSL_LH_stats(3)>, a read lock
 278 suffices.
 279
 280 The LHASH code regards table entries as constant data.  As such, it
 281 internally represents lh_insert()'d items with a "const void *"
 282 pointer type.  This is why callbacks such as those used by lh_doall()
 283 and lh_doall_arg() declare their prototypes with "const", even for the
 284 parameters that pass back the table items' data pointers - for
 285 consistency, user-provided data is "const" at all times as far as the
 286 LHASH code is concerned.  However, as callers are themselves providing
 287 these pointers, they can choose whether they too should be treating
 288 all such parameters as constant.
 289
 290 As an example, a hash table may be maintained by code that, for
 291 reasons of encapsulation, has only "const" access to the data being
 292 indexed in the hash table (i.e. it is returned as "const" from
 293 elsewhere in their code) - in this case the LHASH prototypes are
 294 appropriate as-is.  Conversely, if the caller is responsible for the
 295 life-time of the data in question, then they may well wish to make
 296 modifications to table item passed back in the lh_doall() or
 297 lh_doall_arg() callbacks (see the "TYPE_cleanup" example above).  If
 298 so, the caller can either cast the "const" away (if they're providing
 299 the raw callbacks themselves) or use the macros to declare/implement
 300 the wrapper functions without "const" types.
 301
 302 Callers that only have "const" access to data they're indexing in a
 303 table, yet declare callbacks without constant types (or cast the
 304 "const" away themselves), are therefore creating their own risks/bugs
 305 without being encouraged to do so by the API.  On a related note,
 306 those auditing code should pay special attention to any instances of
 307 DECLARE/IMPLEMENT_LHASH_DOALL_[ARG_]_FN macros that provide types
 308 without any "const" qualifiers.
 309
 310 =head1 BUGS
 311
 312 B<lh_I<TYPE>_insert>() and OPENSSL_LH_insert() return NULL both for success
 313 and error.
 314
 315 =head1 SEE ALSO
 316
 317 L<OPENSSL_LH_stats(3)>
 318
 319 =head1 HISTORY
 320
 321 In OpenSSL 1.0.0, the lhash interface was revamped for better
 322 type checking.
 323
 324 In OpenSSL 3.1, B<DEFINE_LHASH_OF_EX>() was introduced and B<DEFINE_LHASH_OF>()
 325 was deprecated.
 326
 327 =head1 COPYRIGHT
 328
 329 Copyright 2000-2024 The OpenSSL Project Authors. All Rights Reserved.
 330
 331 Licensed under the Apache License 2.0 (the "License").  You may not use
 332 this file except in compliance with the License.  You can obtain a copy
 333 in the file LICENSE in the source distribution or at
 334 L<https://www.openssl.org/source/license.html>.
 335
 336 =cut