src/hashtable.h

   1 /*
   2  * Copyright (c) 2009, 2010 Petri Lehtinen <petri@digip.org>
   3  *
   4  * This library is free software; you can redistribute it and/or modify
   5  * it under the terms of the MIT license. See LICENSE for details.
   6  */
   7
   8 #ifndef HASHTABLE_H
   9 #define HASHTABLE_H
  10
  11 typedef unsigned int (*key_hash_fn)(const void *key);
  12 typedef int (*key_cmp_fn)(const void *key1, const void *key2);
  13 typedef void (*free_fn)(void *key);
  14
  15 struct hashtable_list {
  16     struct hashtable_list *prev;
  17     struct hashtable_list *next;
  18 };
  19
  20 struct hashtable_pair {
  21     void *key;
  22     void *value;
  23     unsigned int hash;
  24     struct hashtable_list list;
  25 };
  26
  27 struct hashtable_bucket {
  28     struct hashtable_list *first;
  29     struct hashtable_list *last;
  30 };
  31
  32 typedef struct hashtable {
  33     unsigned int size;
  34     struct hashtable_bucket *buckets;
  35     unsigned int num_buckets;  /* index to primes[] */
  36     struct hashtable_list list;
  37
  38     key_hash_fn hash_key;
  39     key_cmp_fn cmp_keys;  /* returns non-zero for equal keys */
  40     free_fn free_key;
  41     free_fn free_value;
  42 } hashtable_t;
  43
  44 /**
  45  * hashtable_create - Create a hashtable object
  46  *
  47  * @hash_key: The key hashing function
  48  * @cmp_keys: The key compare function. Returns non-zero for equal and
  49  *     zero for unequal unequal keys
  50  * @free_key: If non-NULL, called for a key that is no longer referenced.
  51  * @free_value: If non-NULL, called for a value that is no longer referenced.
  52  *
  53  * Returns a new hashtable object that should be freed with
  54  * hashtable_destroy when it's no longer used, or NULL on failure (out
  55  * of memory).
  56  */
  57 hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys,
  58                               free_fn free_key, free_fn free_value);
  59
  60 /**
  61  * hashtable_destroy - Destroy a hashtable object
  62  *
  63  * @hashtable: The hashtable
  64  *
  65  * Destroys a hashtable created with hashtable_create().
  66  */
  67 void hashtable_destroy(hashtable_t *hashtable);
  68
  69 /**
  70  * hashtable_init - Initialize a hashtable object
  71  *
  72  * @hashtable: The (statically allocated) hashtable object
  73  * @hash_key: The key hashing function
  74  * @cmp_keys: The key compare function. Returns non-zero for equal and
  75  *     zero for unequal unequal keys
  76  * @free_key: If non-NULL, called for a key that is no longer referenced.
  77  * @free_value: If non-NULL, called for a value that is no longer referenced.
  78  *
  79  * Initializes a statically allocated hashtable object. The object
  80  * should be cleared with hashtable_close when it's no longer used.
  81  *
  82  * Returns 0 on success, -1 on error (out of memory).
  83  */
  84 int hashtable_init(hashtable_t *hashtable,
  85                    key_hash_fn hash_key, key_cmp_fn cmp_keys,
  86                    free_fn free_key, free_fn free_value);
  87
  88 /**
  89  * hashtable_close - Release all resources used by a hashtable object
  90  *
  91  * @hashtable: The hashtable
  92  *
  93  * Destroys a statically allocated hashtable object.
  94  */
  95 void hashtable_close(hashtable_t *hashtable);
  96
  97 /**
  98  * hashtable_set - Add/modify value in hashtable
  99  *
 100  * @hashtable: The hashtable object
 101  * @key: The key
 102  * @value: The value
 103  *
 104  * If a value with the given key already exists, its value is replaced
 105  * with the new value.
 106  *
 107  * Key and value are "stealed" in the sense that hashtable frees them
 108  * automatically when they are no longer used. The freeing is
 109  * accomplished by calling free_key and free_value functions that were
 110  * supplied to hashtable_new. In case one or both of the free
 111  * functions is NULL, the corresponding item is not "stealed".
 112  *
 113  * Returns 0 on success, -1 on failure (out of memory).
 114  */
 115 int hashtable_set(hashtable_t *hashtable, void *key, void *value);
 116
 117 /**
 118  * hashtable_get - Get a value associated with a key
 119  *
 120  * @hashtable: The hashtable object
 121  * @key: The key
 122  *
 123  * Returns value if it is found, or NULL otherwise.
 124  */
 125 void *hashtable_get(hashtable_t *hashtable, const void *key);
 126
 127 /**
 128  * hashtable_del - Remove a value from the hashtable
 129  *
 130  * @hashtable: The hashtable object
 131  * @key: The key
 132  *
 133  * Returns 0 on success, or -1 if the key was not found.
 134  */
 135 int hashtable_del(hashtable_t *hashtable, const void *key);
 136
 137 /**
 138  * hashtable_clear - Clear hashtable
 139  *
 140  * @hashtable: The hashtable object
 141  *
 142  * Removes all items from the hashtable.
 143  */
 144 void hashtable_clear(hashtable_t *hashtable);
 145
 146 /**
 147  * hashtable_iter - Iterate over hashtable
 148  *
 149  * @hashtable: The hashtable object
 150  *
 151  * Returns an opaque iterator to the first element in the hashtable.
 152  * The iterator should be passed to hashtable_iter_* functions.
 153  * The hashtable items are not iterated over in any particular order.
 154  *
 155  * There's no need to free the iterator in any way. The iterator is
 156  * valid as long as the item that is referenced by the iterator is not
 157  * deleted. Other values may be added or deleted. In particular,
 158  * hashtable_iter_next() may be called on an iterator, and after that
 159  * the key/value pair pointed by the old iterator may be deleted.
 160  */
 161 void *hashtable_iter(hashtable_t *hashtable);
 162
 163 /**
 164  * hashtable_iter - Return an iterator at a specific key
 165  *
 166  * @hashtable: The hashtable object
 167  * @key: The key that the iterator should point to
 168  *
 169  * Like hashtable_iter() but returns an iterator pointing to a
 170  * specific key.
 171  */
 172 void *hashtable_iter_at(hashtable_t *hashtable, const void *key);
 173
 174 /**
 175  * hashtable_iter_next - Advance an iterator
 176  *
 177  * @hashtable: The hashtable object
 178  * @iter: The iterator
 179  *
 180  * Returns a new iterator pointing to the next element in the
 181  * hashtable or NULL if the whole hastable has been iterated over.
 182  */
 183 void *hashtable_iter_next(hashtable_t *hashtable, void *iter);
 184
 185 /**
 186  * hashtable_iter_key - Retrieve the key pointed by an iterator
 187  *
 188  * @iter: The iterator
 189  */
 190 void *hashtable_iter_key(void *iter);
 191
 192 /**
 193  * hashtable_iter_value - Retrieve the value pointed by an iterator
 194  *
 195  * @iter: The iterator
 196  */
 197 void *hashtable_iter_value(void *iter);
 198
 199 /**
 200  * hashtable_iter_set - Set the value pointed by an iterator
 201  *
 202  * @iter: The iterator
 203  * @value: The value to set
 204  */
 205 void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value);
 206
 207 #endif