Hash tables =========== A hash table is very universal data structure. It does most of it's operations in O(1) average time. The library contains a header to generate hash tables suiting your needs. They are <>. - <> - <> - <> - <> - <> - <> [[mandatory]] Mandatory macros ---------------- - `HASH_NODE` -- a data type where a node dwells. It is usually a structure. - `HASH_PREFIX(x)` -- the name generating macro. - Key type and name. Must be one of following. [[key_atomic]] * `HASH_KEY_ATOMIC` -- the key (`node\->HASH_KEY_ATOMIC`) is an atomic type which can be compared using `==`. [[key_string]] * `HASH_KEY_STRING` -- the key is a zero-terminated string, allocated separately from the rest of the node. [[key_endstring]] * `HASH_KEY_ENDSTRING` -- a zero-terminated string which lives at the end of node (it is allocated together with the node). It should be declared as `char key[1]`. * `HASH_KEY_MEMORY` -- the `node\->HASH_KEY_MEMORY` is to be compared using memcmp() function. In this case, you need to provide `HASH_KEY_SIZE` macro as well, to specify the length of the key. [[key_complex]] * `HASH_KEY_COMPLEX(x)` -- the key is compound of more than one component. The macro should expand to `x key1, x key2, ..., x kn`. Furthermore, you need to provide a `HASH_KEY_DECL` macro. It is used to define function parameters. Therefore it should expand to `type1 key1, type2 key2, ..., typen keyn`. And <> and <> are mandatory for this key type. [[functions]] Optional function switches -------------------------- You can define any of these macros and provide corresponding functions to customize the behaviour. The macros are: [[give_hashfn]] - `HASH_GIVE_HASHFN` -- the table will use `uns HASH_PREFIX(hash)(key)` to calculate hash of `key`. There is a sensible default for integers and strings. In the case of <>, it is mandatory to provide this macro and function. [[give_eq]] - `HASH_GIVE_EQ` -- tells the table to use `int HASH_PREFIX(eq)(key1, key2)` function to decide if `key1` and `key2` are equal. Default for atomic types is `==` and strcmp() or strcasecmp() for strings (depends on <> switch). It is mandatory when you use <>. - `HASH_GIVE_EXTRA_SIZE` -- function `int HASH_PREFIX(extra_size)(key)` returns how many bytes after the node should be allocated. It defaults to `0` or to length of key in case of <>. - `HASH_GIVE_INIT_KEY` -- function `void HASH_PREFIX(init_key)(node *, key)` is used to initialize key in newly created node. The default is assignment for atomic keys and static strings (<>, <>) and strcpy() for <>. [[give_init_data]] - `HASH_GIVE_INIT_DATA` -- function `void HASH_PREFIX(init_data)(node *)` is used to initialize the rest of node. Useful if you use <> - `HASH_GIVE_ALLOC` -- you need to provide `void \*HASH_PREFIX(alloc)(uns size` and `void HASH_PREFIX(free)(void \*)` to allocate and deallocate the nodes. Default uses <> and <>, <> or <>, depending on <>, <>, <> and <> switches. - <> -- you need to provide `void \*HASH_PREFIX(table_alloc)(uns size` and `void HASH_PREFIX(table_free)(void \*)` to allocate and deallocate the table itself. Default uses <> and <> or the functions from `HASH_GIVE_ALLOC` depending on <> switch. [[params]] Optional parameters ------------------- You can customize the hash table a little more by these macros: [[nocase]] - `HASH_NOCASE` -- use case-insensitive comparison for strings. - `HASH_DEFAULT_SIZE` -- use approximately this many elements when creating the hash table. - `HASH_CONSERVE_SPACE` -- use as little space as possible. - `HASH_FN_BITS` -- the hash function only provides this many significants bits. - `HASH_ATOMIC_TYPE` -- the type of atomic key (<>) is not `int`, but this type. [[use_pool]] - `HASH_USE_POOL` -- tells to use <> to allocate the nodes. You should define it to the name of mempool variable to be used for this purpose. [[auto_pool]] - `HASH_AUTO_POOL` -- like above, but it creates it's own mempool. Define it to the block size of the pool. [[use_eltpool]] - `HASH_USE_ELTPOOL` -- tells to use <> to allocate the nodes. You should define it to the name of eltpool variable to be used for this purpose. [[auto_eltpool]] - `HASH_AUTO_ELTPOOL` -- like above, but it creates it's own mempool. Define it to the number of preallocated nodes in each chunk of memory. - `HASH_ZERO_FILL` -- initialize new nodes to all zeroes. [[table-alloc]] - `HASH_TABLE_ALLOC` -- allocate the table the same way as nodes. If not provided, <> is used. - `HASH_TABLE_GROWING` -- never decrease the size of allocated table of nodes. [[table_dynamic]] - `HASH_TABLE_DYNAMIC` -- By default, only one global hash table is used. With this macro defined, all functions gain new first parameter of type `HASH_PREFIX(table) *` to allow them work with multiple hash tables. - `HASH_TABLE_VARS` -- extra variables to be defined at head of `HASH_PREFIX(table) *` structure. It can be useful in combination with <> to access per-table custom variables from macros or function switches before you include the generator. [[lookup_detect_new]] - `HASH_LOOKUP_DETECT_NEW` -- the prototype for lookup is changed to `node *lookup(key, int *new_item)`, `new_item` must not be NULL and returns 1 whether lookup just created a new item in the hashtable or 0 otherwise. [[wants]] Functionality switches ---------------------- Each of these macros enables some of the functionality the table has. [[want_cleanup]] - `HASH_WANT_CLEANUP` -- <> [[want_find]] - `HASH_WANT_FIND` -- <> [[want_find_next]] - `HASH_WANT_FIND_NEXT` -- <> [[want_new]] - `HASH_WANT_NEW` -- <> [[want_lookup]] - `HASH_WANT_LOOKUP` -- <> [[want_delete]] - `HASH_WANT_DELETE` -- <> [[want_remove]] - `HASH_WANT_REMOVE` -- <> [[generated]] Generated functions ------------------- These are the function that the header file generates for you. The strange first parameter of each function is a place where the `HASH_PREFIX(table) *` resides when you define <>. If you do not, the parameter is empty. !!ucw/hashtable.h HASH_PREFIX [[iterator]] Iterator -------- You can use the `HASH_FOR_ALL` iterator macro to run trough all the nodes. Lets say your `HASH_PREFIX(x)` macro is defined as `prefix_##x`. Then you would do something like: HASH_FOR_ALL(prefix, node_variable) { do_something_with_node(node_variable); } HASH_END_FOR; If you use <>, use `HASH_FOR_ALL_DYNAMIC(prefix, table, node_variable)` instead. You may not modify the table inside the block. Use `HASH_BREAK` and `HASH_CONTINUE` instead of `break` and `continue` statements.