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 38static struct ht_item *ht_iter_advance(struct ht_iter *, struct ht_item *); 39 40void 41ht_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 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 54void 55ht_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 pthread_rwlock_destroy(&h->ht_rwlock); 69 free(h->ht_entries); 70 h->ht_entries = NULL; 71} 72 73void * 74ht_find(struct ht *h, uint32_t hash) 75{ 76 void *result; 77 78 ht_rdlock(h); 79 result = ht_find_locked(h, hash); 80 ht_unlock(h); 81 return (result); 82} 83 84void * 85ht_find_locked(struct ht *h, uint32_t hash) 86{ 87 struct ht_entry *entry; 88 struct ht_item *item; 89 90 entry = &h->ht_entries[hash % h->ht_nentries]; 91 92 TAILQ_FOREACH(item, &entry->hte_items, hti_link) { 93 if (item->hti_hash == hash) 94 return (item->hti_data); 95 } 96 97 return (NULL); 98} 99 100int 101ht_add(struct ht *h, uint32_t hash, void *value) 102{ 103 struct ht_entry *entry; 104 struct ht_item *item; 105 106 ht_wrlock(h); 107 entry = &h->ht_entries[hash % h->ht_nentries]; 108 109 TAILQ_FOREACH(item, &entry->hte_items, hti_link) { 110 if (item->hti_hash == hash) { 111 errno = EEXIST; 112 ht_unlock(h); 113 return (-1); 114 } 115 } 116 117 item = l9p_calloc(1, sizeof(struct ht_item)); 118 item->hti_hash = hash; 119 item->hti_data = value; 120 TAILQ_INSERT_TAIL(&entry->hte_items, item, hti_link); 121 ht_unlock(h); 122 123 return (0); 124} 125 126int 127ht_remove(struct ht *h, uint32_t hash) 128{ 129 int result; 130 131 ht_wrlock(h); 132 result = ht_remove_locked(h, hash); 133 ht_unlock(h); 134 return (result); 135} 136 137int 138ht_remove_locked(struct ht *h, uint32_t hash) 139{ 140 struct ht_entry *entry; 141 struct ht_item *item, *tmp; 142 ssize_t slot = hash % h->ht_nentries; 143 144 entry = &h->ht_entries[slot]; 145 146 TAILQ_FOREACH_SAFE(item, &entry->hte_items, hti_link, tmp) { 147 if (item->hti_hash == hash) { 148 TAILQ_REMOVE(&entry->hte_items, item, hti_link); 149 free(item); 150 return (0); 151 } 152 } 153 154 errno = ENOENT; 155 return (-1); 156} 157 158/* 159 * Inner workings for advancing the iterator. 160 * 161 * If we have a current item, that tells us how to find the 162 * next item. If not, we get the first item from the next 163 * slot (well, the next slot with an item); in any case, we 164 * record the new slot and return the next item. 165 * 166 * For bootstrapping, iter->htit_slot can be -1 to start 167 * searching at slot 0. 168 * 169 * Caller must hold a lock on the table. 170 */ 171static struct ht_item * 172ht_iter_advance(struct ht_iter *iter, struct ht_item *cur) 173{ 174 struct ht_item *next; 175 struct ht *h; 176 ssize_t slot; 177 178 h = iter->htit_parent; 179 180 if (cur == NULL) 181 next = NULL; 182 else 183 next = TAILQ_NEXT(cur, hti_link); 184 185 if (next == NULL) { 186 slot = iter->htit_slot; 187 while (++slot < h->ht_nentries) { 188 next = TAILQ_FIRST(&h->ht_entries[slot].hte_items); 189 if (next != NULL) 190 break; 191 } 192 iter->htit_slot = slot; 193 } 194 return (next); 195} 196 197/* 198 * Remove the current item - there must be one, or this is an 199 * error. This (necessarily) pre-locates the next item, so callers 200 * must not use it on an actively-changing table. 201 */ 202int 203ht_remove_at_iter(struct ht_iter *iter) 204{ 205 struct ht_item *item; 206 struct ht *h; 207 ssize_t slot; 208 209 assert(iter != NULL); 210 211 if ((item = iter->htit_curr) == NULL) { 212 errno = EINVAL; 213 return (-1); 214 } 215 216 /* remove the item from the table, saving the NEXT one */ 217 h = iter->htit_parent; 218 ht_wrlock(h); 219 slot = iter->htit_slot; 220 iter->htit_next = ht_iter_advance(iter, item); 221 TAILQ_REMOVE(&h->ht_entries[slot].hte_items, item, hti_link); 222 ht_unlock(h); 223 224 /* mark us as no longer on an item, then free it */ 225 iter->htit_curr = NULL; 226 free(item); 227 228 return (0); 229} 230 231/* 232 * Initialize iterator. Subsequent ht_next calls will find the 233 * first item, then the next, and so on. Callers should in general 234 * not use this on actively-changing tables, though we do our best 235 * to make it semi-sensible. 236 */ 237void 238ht_iter(struct ht *h, struct ht_iter *iter) 239{ 240 241 iter->htit_parent = h; 242 iter->htit_curr = NULL; 243 iter->htit_next = NULL; 244 iter->htit_slot = -1; /* which will increment to 0 */ 245} 246 247/* 248 * Return the next item, which is the first item if we have not 249 * yet been called on this iterator, or the next item if we have. 250 */ 251void * 252ht_next(struct ht_iter *iter) 253{ 254 struct ht_item *item; 255 struct ht *h; 256 257 if ((item = iter->htit_next) == NULL) { 258 /* no pre-loaded next; find next from current */ 259 h = iter->htit_parent; 260 ht_rdlock(h); 261 item = ht_iter_advance(iter, iter->htit_curr); 262 ht_unlock(h); 263 } else 264 iter->htit_next = NULL; 265 iter->htit_curr = item; 266 return (item == NULL ? NULL : item->hti_data); 267} 268