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 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 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 ht_rdlock(h); 79 result = ht_find_locked(h, hash); 80 ht_unlock(h); 81 return (result); 82 } 83 84 void * 85 ht_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 100 int 101 ht_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 126 int 127 ht_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 137 int 138 ht_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 */ 171 static struct ht_item * 172 ht_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 */ 202 int 203 ht_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 */ 237 void 238 ht_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 */ 251 void * 252 ht_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