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