1 /*
2 * Copyright 2016 Jakub Klama <jceel@FreeBSD.org>
3 * All rights reserved
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted providing that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
22 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
23 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 *
26 */
27
28 #include <stdlib.h>
29 #include <string.h>
30 #include <errno.h>
31 #include <assert.h>
32 #include <pthread.h>
33 #include <sys/types.h>
34 #include <sys/queue.h>
35 #include "lib9p_impl.h"
36 #include "hashtable.h"
37
38 static struct ht_item *ht_iter_advance(struct ht_iter *, struct ht_item *);
39
40 void
ht_init(struct ht * h,ssize_t size)41 ht_init(struct ht *h, ssize_t size)
42 {
43 ssize_t i;
44
45 memset(h, 0, sizeof(struct ht));
46 h->ht_nentries = size;
47 h->ht_entries = l9p_calloc((size_t)size, sizeof(struct ht_entry));
48 (void) pthread_rwlock_init(&h->ht_rwlock, NULL);
49
50 for (i = 0; i < size; i++)
51 TAILQ_INIT(&h->ht_entries[i].hte_items);
52 }
53
54 void
ht_destroy(struct ht * h)55 ht_destroy(struct ht *h)
56 {
57 struct ht_entry *he;
58 struct ht_item *item, *tmp;
59 ssize_t i;
60
61 for (i = 0; i < h->ht_nentries; i++) {
62 he = &h->ht_entries[i];
63 TAILQ_FOREACH_SAFE(item, &he->hte_items, hti_link, tmp) {
64 free(item);
65 }
66 }
67
68 (void) pthread_rwlock_destroy(&h->ht_rwlock);
69 free(h->ht_entries);
70 h->ht_entries = NULL;
71 }
72
73 void *
ht_find(struct ht * h,uint32_t hash)74 ht_find(struct ht *h, uint32_t hash)
75 {
76 void *result;
77
78 if (ht_rdlock(h) != 0)
79 return (NULL);
80 result = ht_find_locked(h, hash);
81 (void) ht_unlock(h);
82 return (result);
83 }
84
85 void *
ht_find_locked(struct ht * h,uint32_t hash)86 ht_find_locked(struct ht *h, uint32_t hash)
87 {
88 struct ht_entry *entry;
89 struct ht_item *item;
90
91 entry = &h->ht_entries[hash % h->ht_nentries];
92
93 TAILQ_FOREACH(item, &entry->hte_items, hti_link) {
94 if (item->hti_hash == hash)
95 return (item->hti_data);
96 }
97
98 return (NULL);
99 }
100
101 int
ht_add(struct ht * h,uint32_t hash,void * value)102 ht_add(struct ht *h, uint32_t hash, void *value)
103 {
104 struct ht_entry *entry;
105 struct ht_item *item;
106 int err;
107
108 if ((err = ht_wrlock(h)) != 0)
109 return (err);
110
111 entry = &h->ht_entries[hash % h->ht_nentries];
112
113 TAILQ_FOREACH(item, &entry->hte_items, hti_link) {
114 if (item->hti_hash == hash) {
115 errno = EEXIST;
116 (void) ht_unlock(h);
117 return (-1);
118 }
119 }
120
121 item = l9p_calloc(1, sizeof(struct ht_item));
122 item->hti_hash = hash;
123 item->hti_data = value;
124 TAILQ_INSERT_TAIL(&entry->hte_items, item, hti_link);
125 (void) ht_unlock(h);
126
127 return (0);
128 }
129
130 int
ht_remove(struct ht * h,uint32_t hash)131 ht_remove(struct ht *h, uint32_t hash)
132 {
133 int result;
134 int err;
135
136 if ((err = ht_wrlock(h)) != 0)
137 return (err);
138 result = ht_remove_locked(h, hash);
139 (void) ht_unlock(h);
140 return (result);
141 }
142
143 int
ht_remove_locked(struct ht * h,uint32_t hash)144 ht_remove_locked(struct ht *h, uint32_t hash)
145 {
146 struct ht_entry *entry;
147 struct ht_item *item, *tmp;
148 ssize_t slot = hash % h->ht_nentries;
149
150 entry = &h->ht_entries[slot];
151
152 TAILQ_FOREACH_SAFE(item, &entry->hte_items, hti_link, tmp) {
153 if (item->hti_hash == hash) {
154 TAILQ_REMOVE(&entry->hte_items, item, hti_link);
155 free(item);
156 return (0);
157 }
158 }
159
160 errno = ENOENT;
161 return (-1);
162 }
163
164 /*
165 * Inner workings for advancing the iterator.
166 *
167 * If we have a current item, that tells us how to find the
168 * next item. If not, we get the first item from the next
169 * slot (well, the next slot with an item); in any case, we
170 * record the new slot and return the next item.
171 *
172 * For bootstrapping, iter->htit_slot can be -1 to start
173 * searching at slot 0.
174 *
175 * Caller must hold a lock on the table.
176 */
177 static struct ht_item *
ht_iter_advance(struct ht_iter * iter,struct ht_item * cur)178 ht_iter_advance(struct ht_iter *iter, struct ht_item *cur)
179 {
180 struct ht_item *next;
181 struct ht *h;
182 ssize_t slot;
183
184 h = iter->htit_parent;
185
186 if (cur == NULL)
187 next = NULL;
188 else
189 next = TAILQ_NEXT(cur, hti_link);
190
191 if (next == NULL) {
192 slot = iter->htit_slot;
193 while (++slot < h->ht_nentries) {
194 next = TAILQ_FIRST(&h->ht_entries[slot].hte_items);
195 if (next != NULL)
196 break;
197 }
198 iter->htit_slot = slot;
199 }
200 return (next);
201 }
202
203 /*
204 * Remove the current item - there must be one, or this is an
205 * error. This (necessarily) pre-locates the next item, so callers
206 * must not use it on an actively-changing table.
207 */
208 int
ht_remove_at_iter(struct ht_iter * iter)209 ht_remove_at_iter(struct ht_iter *iter)
210 {
211 struct ht_item *item;
212 struct ht *h;
213 ssize_t slot;
214 int err;
215
216 assert(iter != NULL);
217
218 if ((item = iter->htit_curr) == NULL) {
219 errno = EINVAL;
220 return (-1);
221 }
222
223 /* remove the item from the table, saving the NEXT one */
224 h = iter->htit_parent;
225 if ((err = ht_wrlock(h)) != 0)
226 return (err);
227 slot = iter->htit_slot;
228 iter->htit_next = ht_iter_advance(iter, item);
229 TAILQ_REMOVE(&h->ht_entries[slot].hte_items, item, hti_link);
230 (void) ht_unlock(h);
231
232 /* mark us as no longer on an item, then free it */
233 iter->htit_curr = NULL;
234 free(item);
235
236 return (0);
237 }
238
239 /*
240 * Initialize iterator. Subsequent ht_next calls will find the
241 * first item, then the next, and so on. Callers should in general
242 * not use this on actively-changing tables, though we do our best
243 * to make it semi-sensible.
244 */
245 void
ht_iter(struct ht * h,struct ht_iter * iter)246 ht_iter(struct ht *h, struct ht_iter *iter)
247 {
248
249 iter->htit_parent = h;
250 iter->htit_curr = NULL;
251 iter->htit_next = NULL;
252 iter->htit_slot = -1; /* which will increment to 0 */
253 }
254
255 /*
256 * Return the next item, which is the first item if we have not
257 * yet been called on this iterator, or the next item if we have.
258 */
259 void *
ht_next(struct ht_iter * iter)260 ht_next(struct ht_iter *iter)
261 {
262 struct ht_item *item;
263 struct ht *h;
264
265 if ((item = iter->htit_next) == NULL) {
266 /* no pre-loaded next; find next from current */
267 h = iter->htit_parent;
268 if (ht_rdlock(h) != 0)
269 return (NULL);
270 item = ht_iter_advance(iter, iter->htit_curr);
271 (void) ht_unlock(h);
272 } else
273 iter->htit_next = NULL;
274 iter->htit_curr = item;
275 return (item == NULL ? NULL : item->hti_data);
276 }
277