ucw/doc/hashtable.txt

   1 Hash tables
   2 ===========
   3
   4 A hash table is very universal data structure. It does most of it's
   5 operations in O(1) average time. The library contains a header to
   6 generate hash tables suiting your needs.
   7
   8 They are <<generic:,generic data structures>>.
   9
  10 - <<mandatory,Mandatory macros>>
  11 - <<functions,Optional function switches>>
  12 - <<params,Optional parameters>>
  13 - <<wants,Functionality switches>>
  14 - <<generated,Generated functions>>
  15 - <<iterator,Iterator>>
  16
  17 [[mandatory]]
  18 Mandatory macros
  19 ----------------
  20
  21 - `HASH_NODE` -- a data type where a node dwells. It is usually a
  22   structure.
  23 - `HASH_PREFIX(x)` -- the name generating macro.
  24 - Key type and name. Must be one of following.
  25   [[key_atomic]]
  26   * `HASH_KEY_ATOMIC` -- the key (`node\->HASH_KEY_ATOMIC`) is an
  27     atomic type which can be compared using `==`.
  28   [[key_string]]
  29   * `HASH_KEY_STRING` -- the key is a zero-terminated string,
  30     allocated separately from the rest of the node.
  31   [[key_endstring]]
  32   * `HASH_KEY_ENDSTRING` -- a zero-terminated string which lives at
  33     the end of node (it is allocated together with the node). It
  34     should be declared as `char key[1]`.
  35   * `HASH_KEY_MEMORY` -- the `node\->HASH_KEY_MEMORY` is to be compared
  36     using memcmp() function. In this case, you need to provide
  37     `HASH_KEY_SIZE` macro as well, to specify the length of the key.
  38   [[key_complex]]
  39   * `HASH_KEY_COMPLEX(x)` -- the key is compound of more than one
  40     component. The macro should expand to `x key1, x key2, ..., x kn`.
  41     Furthermore, you need to provide a `HASH_KEY_DECL` macro. It is
  42     used to define function parameters. Therefore it should expand to
  43     `type1 key1, type2 key2, ..., typen keyn`. And
  44     <<give_hashfn,`HASH_GIVE_HASHFN`>> and <<give_eq,`HASH_GIVE_EQ`>>
  45     are mandatory for this key type.
  46
  47 [[functions]]
  48 Optional function switches
  49 --------------------------
  50
  51 You can define any of these macros and provide corresponding functions
  52 to customize the behaviour. The macros are:
  53
  54 [[give_hashfn]]
  55 - `HASH_GIVE_HASHFN` -- the table will use `uns
  56   HASH_PREFIX(hash)(key)` to calculate hash of `key`.
  57   There is a sensible default for integers and strings.
  58   In the case of <<key_complex,`HASH_KEY_COMPLEX`>>, it is mandatory
  59   to provide this macro and function.
  60 [[give_eq]]
  61 - `HASH_GIVE_EQ` -- tells the table to use `int HASH_PREFIX(eq)(key1,
  62   key2)` function to decide if `key1` and `key2` are equal. Default
  63   for atomic types is `==` and strcmp() or strcasecmp() for strings
  64   (depends on <<nocase,`HASH_NOCASE`>> switch).
  65   It is mandatory when you use <<key_complex,`HASH_KEY_COMPLEX`>>.
  66 - `HASH_GIVE_EXTRA_SIZE` -- function `int HASH_PREFIX(extra_size)(key)`
  67   returns how many bytes after the node should be allocated. It
  68   defaults to `0` or to length of key in case of
  69   <<key_endstring,`HASH_KEY_ENDSTRING`>>.
  70 - `HASH_GIVE_INIT_KEY` -- function
  71   `void HASH_PREFIX(init_key)(node *, key)` is used to initialize key
  72   in newly created node. The default is assignment for atomic keys and
  73   static strings (<<key_atomic,`HASH_KEY_ATOMIC`>>,
  74   <<key_string,`HASH_KEY_STRING`>>) and strcpy() for
  75   <<key_endstr,`HASH_KEY_ENDSTRING`>>.
  76 [[give_init_data]]
  77 - `HASH_GIVE_INIT_DATA` -- function `void HASH_PREFIX(init_data)(node
  78   *)` is used to initialize the rest of node. Useful if you use
  79   <<fun_HASH_PREFIX_OPEN_PAREN_lookup_CLOSE_PAREN_,`HASH_PREFIX(lookup())`>>
  80 - `HASH_GIVE_ALLOC` -- you need to provide `void
  81   \*HASH_PREFIX(alloc)(uns size` and `void HASH_PREFIX(free)(void \*)`
  82   to allocate and deallocate the nodes. Default uses
  83   <<basics:xmalloc()>> and <<basics:xfree()>>, <<mempool:mempool
  84   routines>> or <<eltpool:eltpool routines>>, depending on
  85   <<use_pool,`HASH_USE_POOL`>>, <<auto_pool,`HASH_AUTO_POOL`>>,
  86   <<use_eltpool,`HASH_USE_ELTPOOL`>> and <<auto_eltpool,`HASH_AUTO_ELTPOOL`>> switches.
  87 - <<table_alloc:`HASH_GIVE_TABLE_ALLOC`>> -- you need to provide `void
  88   \*HASH_PREFIX(table_alloc)(uns size` and `void HASH_PREFIX(table_free)(void \*)`
  89   to allocate and deallocate the table itself. Default uses
  90   <<basics:xmalloc()>> and <<basics:xfree()>> or the functions
  91   from `HASH_GIVE_ALLOC` depending on <<table_alloc:`HASH_TABLE_ALLOC`>> switch.
  92
  93 [[params]]
  94 Optional parameters
  95 -------------------
  96
  97 You can customize the hash table a little more by these macros:
  98
  99 [[nocase]]
 100 - `HASH_NOCASE` -- use case-insensitive comparison for strings.
 101 - `HASH_DEFAULT_SIZE` -- use approximately this many elements when
 102   creating the hash table.
 103 - `HASH_CONSERVE_SPACE` -- use as little space as possible.
 104 - `HASH_FN_BITS` -- the hash function only provides this many
 105   significants bits.
 106 - `HASH_ATOMIC_TYPE` -- the type of atomic key
 107   (<<key_atomic,`HASH_KEY_ATOMIC`>>) is not `int`, but this type.
 108 [[use_pool]]
 109 - `HASH_USE_POOL` -- tells to use <<mempool:,mempool allocation>> to
 110   allocate the nodes. You should define it to the name of mempool
 111   variable to be used for this purpose.
 112 [[auto_pool]]
 113 - `HASH_AUTO_POOL` -- like above, but it creates it's own mempool.
 114   Define it to the block size of the pool.
 115 [[use_eltpool]]
 116 - `HASH_USE_ELTPOOL` -- tells to use <<eltpool:,eltpool allocation>> to
 117   allocate the nodes. You should define it to the name of eltpool
 118   variable to be used for this purpose.
 119 [[auto_eltpool]]
 120 - `HASH_AUTO_ELTPOOL` -- like above, but it creates it's own mempool.
 121   Define it to the number of preallocated nodes in each chunk of memory.
 122 - `HASH_ZERO_FILL` -- initialize new nodes to all zeroes.
 123 [[table-alloc]]
 124 - `HASH_TABLE_ALLOC` -- allocate the table the same way as nodes. If
 125   not provided, <<basics:xmalloc()>> is used.
 126 - `HASH_TABLE_GROWING` -- never decrease the size of allocated table of nodes.
 127 [[table_dynamic]]
 128 - `HASH_TABLE_DYNAMIC` -- By default, only one global hash table is
 129   used. With this macro defined, all functions gain new first
 130   parameter of type `HASH_PREFIX(table) *` to allow them work with
 131   multiple hash tables.
 132 - `HASH_TABLE_VARS` -- extra variables to be defined at head
 133   of `HASH_PREFIX(table) *` structure. It can be useful in combination
 134   with <<table_dynamic:`HASH_TABLE_DYNAMIC`>> to access per-table custom variables
 135   from macros or function switches before you include the generator.
 136 [[lookup_detect_new]]
 137 - `HASH_LOOKUP_DETECT_NEW` -- the prototype for lookup is changed to `node *lookup(key, int *new_item)`,
 138  `new_item` must not be NULL and returns 1 whether lookup just created a new item in the hashtable
 139  or 0 otherwise.
 140
 141 [[wants]]
 142 Functionality switches
 143 ----------------------
 144
 145 Each of these macros enables some of the functionality the table has.
 146
 147 [[want_cleanup]]
 148 - `HASH_WANT_CLEANUP` --
 149   <<fun_HASH_PREFIX_OPEN_PAREN_cleanup_CLOSE_PAREN_,`HASH_PREFIX((cleanup()`>>
 150 [[want_find]]
 151 - `HASH_WANT_FIND` --
 152   <<fun_HASH_PREFIX_OPEN_PAREN_find_CLOSE_PAREN_,`HASH_PREFIX((find()`>>
 153 [[want_find_next]]
 154 - `HASH_WANT_FIND_NEXT` --
 155   <<fun_HASH_PREFIX_OPEN_PAREN_find_next_CLOSE_PAREN_,`HASH_PREFIX((find_next()`>>
 156 [[want_new]]
 157 - `HASH_WANT_NEW` --
 158   <<fun_HASH_PREFIX_OPEN_PAREN_new_CLOSE_PAREN_,`HASH_PREFIX((new()`>>
 159 [[want_lookup]]
 160 - `HASH_WANT_LOOKUP` --
 161   <<fun_HASH_PREFIX_OPEN_PAREN_lookup_CLOSE_PAREN_,`HASH_PREFIX((lookup()`>>
 162 [[want_delete]]
 163 - `HASH_WANT_DELETE` --
 164   <<fun_HASH_PREFIX_OPEN_PAREN_delete_CLOSE_PAREN_,`HASH_PREFIX((delete()`>>
 165 [[want_remove]]
 166 - `HASH_WANT_REMOVE` --
 167   <<fun_HASH_PREFIX_OPEN_PAREN_remove_CLOSE_PAREN_,`HASH_PREFIX((remove()`>>
 168
 169 [[generated]]
 170 Generated functions
 171 -------------------
 172
 173 These are the function that the header file generates for you. The
 174 strange first parameter of each function is a place where the
 175 `HASH_PREFIX(table) *` resides when you define
 176 <<table_dynamic,`HASH_TABLE_DYNAMIC`>>. If you do not, the parameter
 177 is empty.
 178
 179 !!ucw/hashtable.h HASH_PREFIX
 180
 181 [[iterator]]
 182 Iterator
 183 --------
 184
 185 You can use the `HASH_FOR_ALL` iterator macro to run trough all the
 186 nodes. Lets say your `HASH_PREFIX(x)` macro is defined as
 187 `prefix_##x`. Then you would do something like:
 188
 189   HASH_FOR_ALL(prefix, node_variable)
 190   {
 191      do_something_with_node(node_variable);
 192   }
 193   HASH_END_FOR;
 194
 195 If you use <<table_dynamic,`HASH_TABLE_DYNAMIC`>>, use
 196 `HASH_FOR_ALL_DYNAMIC(prefix, table, node_variable)` instead.
 197
 198 You may not modify the table inside the block. Use `HASH_BREAK` and
 199 `HASH_CONTINUE` instead of `break` and `continue` statements.