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   <<memory:xmalloc()>> and <<memory:xfree()>> or <<mempool:,mempool
  84   routines>>, depending on <<use_pool,`HASH_USE_POOL`>> and
  85   <<auto_pool,`HASH_AUTO_POOL>> switches.
  86
  87 [[params]]
  88 Optional parameters
  89 -------------------
  90
  91 You can customize the hash table a little more by these macros:
  92
  93 [[nocase]]
  94 - `HASH_NOCASE` -- use case-insensitive comparison for strings.
  95 - `HASH_DEFAULT_SIZE` -- use approximately this many elements when
  96   creating the hash table.
  97 - `HASH_CONSERVE_SPACE` -- use as little space as possible.
  98 - `HASH_FN_BITS` -- the hash function only provides this many
  99   significants bits.
 100 - `HASH_ATOMIC_TYPE` -- the type of atomic key
 101   (<<key_atomic,`HASH_KEY_ATOMIC`>>) is not `int`, but this type.
 102 [[use_pool]]
 103 - `HASH_USE_POOL` -- tells to use <<mempool:,mempool allocation>> to
 104   allocate the nodes. You should define it to the name of mempool
 105   variable to be used for this purpose.
 106 [[auto_pool]]
 107 - `HASH_AUTO_POOL` -- like above, but it creates it's own mempool.
 108   Define it to the block size of the pool.
 109 - `HASH_ZERO_FILL` -- initialize new nodes to all zeroes.
 110 - `HASH_TABLE_ALLOC` -- allocate the table the same way as nodes. If
 111   not provided, <<mempory:xmalloc()>> is used.
 112 [[table_dynamic]]
 113 - `HASH_TABLE_DYNAMIC` -- By default, only one global hash table is
 114   used. With this macro defined, all functions gain new first
 115   parameter of type `HASH_PREFIX(table) *` to allow them work with
 116   multiple hash tables.
 117
 118 [[wants]]
 119 Functionality switches
 120 ----------------------
 121
 122 Each of these macros enables some of the functionality the table has.
 123
 124 [[want_cleanup]]
 125 - `HASH_WANT_CLEANUP` --
 126   <<fun_HASH_PREFIX_OPEN_PAREN_cleanup_CLOSE_PAREN_,`HASH_PREFIX((cleanup()`>>
 127 [[want_find]]
 128 - `HASH_WANT_FIND` --
 129   <<fun_HASH_PREFIX_OPEN_PAREN_find_CLOSE_PAREN_,`HASH_PREFIX((find()`>>
 130 [[want_find_next]]
 131 - `HASH_WANT_FIND_NEXT` --
 132   <<fun_HASH_PREFIX_OPEN_PAREN_find_next_CLOSE_PAREN_,`HASH_PREFIX((find_next()`>>
 133 [[want_new]]
 134 - `HASH_WANT_NEW` --
 135   <<fun_HASH_PREFIX_OPEN_PAREN_new_CLOSE_PAREN_,`HASH_PREFIX((new()`>>
 136 [[want_lookup]]
 137 - `HASH_WANT_LOOKUP` --
 138   <<fun_HASH_PREFIX_OPEN_PAREN_lookup_CLOSE_PAREN_,`HASH_PREFIX((lookup()`>>
 139 [[want_delete]]
 140 - `HASH_WANT_DELETE` --
 141   <<fun_HASH_PREFIX_OPEN_PAREN_delete_CLOSE_PAREN_,`HASH_PREFIX((delete()`>>
 142 [[want_remove]]
 143 - `HASH_WANT_REMOVE` --
 144   <<fun_HASH_PREFIX_OPEN_PAREN_remove_CLOSE_PAREN_,`HASH_PREFIX((remove()`>>
 145
 146 [[generated]]
 147 Generated functions
 148 -------------------
 149
 150 These are the function that the header file generates for you. The
 151 strange first parameter of each function is a place where the
 152 `HASH_PREFIX(table) *` resides when you define
 153 <<table_dynamic,`HASH_TABLE_DYNAMIC`>>. If you do not, the parameter
 154 is empty.
 155
 156 !!ucw/hashtable.h HASH_PREFIX
 157
 158 [[iterator]]
 159 Iterator
 160 --------
 161
 162 You can use the `HASH_FOR_ALL` iterator macro to run trough all the
 163 nodes. Lets say your `HASH_PREFIX(x)` macro is defined as
 164 `prefix_##x`. Then you would do something like:
 165
 166   HASH_FOR_ALL(prefix, node_variable)
 167   {
 168      do_something_with_node(node_variable);
 169   }
 170   HASH_END_FOR;
 171
 172 If you use <<table_dynamic,`HASH_TABLE_DYNAMIC`>>, use
 173 `HASH_FOR_ALL_DYNAMIC(prefix, table, node_variable)` instead.
 174
 175 You may not modify the table inside the block. Use `HASH_BREAK` and
 176 `HASH_CONTINUE` instead of `break` and `continue` statements.