src/hashtable.h

   1 /*
   2  * Copyright (c) 2009-2011 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 size_t (*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 /* "pair" may be a bit confusing a name, but think of it as a
  21    key-value pair. In this case, it just encodes some extra data,
  22    too */
  23 struct hashtable_pair {
  24     size_t hash;
  25     struct hashtable_list list;
  26     json_t *value;
  27     size_t serial;
  28     char key[1];
  29 };
  30
  31 struct hashtable_bucket {
  32     struct hashtable_list *first;
  33     struct hashtable_list *last;
  34 };
  35
  36 typedef struct hashtable {
  37     size_t size;
  38     struct hashtable_bucket *buckets;
  39     size_t num_buckets;  /* index to primes[] */
  40     struct hashtable_list list;
  41 } hashtable_t;
  42
  43
  44 #define hashtable_key_to_iter(key_) \
  45     (&(container_of(key_, struct hashtable_pair, key)->list))
  46
  47 /**
  48  * hashtable_init - Initialize a hashtable object
  49  *
  50  * @hashtable: The (statically allocated) hashtable object
  51  *
  52  * Initializes a statically allocated hashtable object. The object
  53  * should be cleared with hashtable_close when it's no longer used.
  54  *
  55  * Returns 0 on success, -1 on error (out of memory).
  56  */
  57 int hashtable_init(hashtable_t *hashtable);
  58
  59 /**
  60  * hashtable_close - Release all resources used by a hashtable object
  61  *
  62  * @hashtable: The hashtable
  63  *
  64  * Destroys a statically allocated hashtable object.
  65  */
  66 void hashtable_close(hashtable_t *hashtable);
  67
  68 /**
  69  * hashtable_set - Add/modify value in hashtable
  70  *
  71  * @hashtable: The hashtable object
  72  * @key: The key
  73  * @serial: For addition order of keys
  74  * @value: The value
  75  *
  76  * If a value with the given key already exists, its value is replaced
  77  * with the new value. Value is "stealed" in the sense that hashtable
  78  * doesn't increment its refcount but decreases the refcount when the
  79  * value is no longer needed.
  80  *
  81  * Returns 0 on success, -1 on failure (out of memory).
  82  */
  83 int hashtable_set(hashtable_t *hashtable,
  84                   const char *key, size_t serial,
  85                   json_t *value);
  86
  87 /**
  88  * hashtable_get - Get a value associated with a key
  89  *
  90  * @hashtable: The hashtable object
  91  * @key: The key
  92  *
  93  * Returns value if it is found, or NULL otherwise.
  94  */
  95 void *hashtable_get(hashtable_t *hashtable, const char *key);
  96
  97 /**
  98  * hashtable_del - Remove a value from the hashtable
  99  *
 100  * @hashtable: The hashtable object
 101  * @key: The key
 102  *
 103  * Returns 0 on success, or -1 if the key was not found.
 104  */
 105 int hashtable_del(hashtable_t *hashtable, const char *key);
 106
 107 /**
 108  * hashtable_clear - Clear hashtable
 109  *
 110  * @hashtable: The hashtable object
 111  *
 112  * Removes all items from the hashtable.
 113  */
 114 void hashtable_clear(hashtable_t *hashtable);
 115
 116 /**
 117  * hashtable_iter - Iterate over hashtable
 118  *
 119  * @hashtable: The hashtable object
 120  *
 121  * Returns an opaque iterator to the first element in the hashtable.
 122  * The iterator should be passed to hashtable_iter_* functions.
 123  * The hashtable items are not iterated over in any particular order.
 124  *
 125  * There's no need to free the iterator in any way. The iterator is
 126  * valid as long as the item that is referenced by the iterator is not
 127  * deleted. Other values may be added or deleted. In particular,
 128  * hashtable_iter_next() may be called on an iterator, and after that
 129  * the key/value pair pointed by the old iterator may be deleted.
 130  */
 131 void *hashtable_iter(hashtable_t *hashtable);
 132
 133 /**
 134  * hashtable_iter_at - Return an iterator at a specific key
 135  *
 136  * @hashtable: The hashtable object
 137  * @key: The key that the iterator should point to
 138  *
 139  * Like hashtable_iter() but returns an iterator pointing to a
 140  * specific key.
 141  */
 142 void *hashtable_iter_at(hashtable_t *hashtable, const char *key);
 143
 144 /**
 145  * hashtable_iter_next - Advance an iterator
 146  *
 147  * @hashtable: The hashtable object
 148  * @iter: The iterator
 149  *
 150  * Returns a new iterator pointing to the next element in the
 151  * hashtable or NULL if the whole hastable has been iterated over.
 152  */
 153 void *hashtable_iter_next(hashtable_t *hashtable, void *iter);
 154
 155 /**
 156  * hashtable_iter_key - Retrieve the key pointed by an iterator
 157  *
 158  * @iter: The iterator
 159  */
 160 void *hashtable_iter_key(void *iter);
 161
 162 /**
 163  * hashtable_iter_serial - Retrieve the serial number pointed to by an iterator
 164  *
 165  * @iter: The iterator
 166  */
 167 size_t hashtable_iter_serial(void *iter);
 168
 169 /**
 170  * hashtable_iter_value - Retrieve the value pointed by an iterator
 171  *
 172  * @iter: The iterator
 173  */
 174 void *hashtable_iter_value(void *iter);
 175
 176 /**
 177  * hashtable_iter_set - Set the value pointed by an iterator
 178  *
 179  * @iter: The iterator
 180  * @value: The value to set
 181  */
 182 void hashtable_iter_set(void *iter, json_t *value);
 183
 184 #endif