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