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 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 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 * 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 * 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 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 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 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 * 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 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 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 * 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