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