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
11struct 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 */
19struct 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
27struct hashtable_bucket {
28    struct hashtable_list *first;
29    struct hashtable_list *last;
30};
31
32typedef 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 */
54int 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 */
63void 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 */
80int 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 */
92void *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 */
102int 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 */
111void 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 */
128void *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 */
139void *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 */
150void *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 */
157void *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 */
164size_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 */
171void *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 */
179void hashtable_iter_set(void *iter, json_t *value);
180
181#endif
182