1 /* $OpenBSD: hash.c,v 1.5 2015/12/17 08:01:55 tb Exp $ */ 2 /*- 3 * Copyright (c) 2009 Internet Initiative Japan Inc. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 #include <sys/types.h> 28 #include <stdio.h> 29 #include <stdlib.h> 30 #include <string.h> 31 32 #include "hash.h" 33 34 /* hash_create - Create a new hash table. 35 * Returns a pointer of new hash_table on success. Otherwise returns 36 * NULL. 37 */ 38 hash_table * 39 hash_create(cmp_func, hash_func, hsz) 40 int (*cmp_func) (const void *, const void *); 41 uint32_t (*hash_func) (const void *, int); 42 int hsz; 43 { 44 hash_table *htbl; 45 46 htbl = malloc(sizeof(hash_table)); 47 if (htbl == NULL) 48 return NULL; 49 50 if (hsz < 1) 51 htbl->size = HASH_SIZE; 52 else 53 htbl->size = hsz; 54 55 htbl->bucket = calloc(htbl->size, sizeof(hash_link *)); 56 htbl->cmp = cmp_func; 57 htbl->hash = hash_func; 58 htbl->cur = 0; 59 htbl->bucket_cur = NULL; 60 61 return htbl; 62 } 63 64 /* hash_first - Get first item from hash table. 65 * Returns a pointer of first bucket on success. Otherwise returns 66 * NULL. 67 */ 68 hash_link * 69 hash_first(htbl) 70 hash_table *htbl; 71 { 72 htbl->cur = 0; 73 htbl->bucket_cur = NULL; 74 return hash_next(htbl); 75 } 76 77 /* hash_next - Get next item from hash table. 78 * Returns a pointer of next bucket on success. Otherwise returns 79 * NULL. 80 */ 81 hash_link * 82 hash_next(htbl) 83 hash_table *htbl; 84 { 85 hash_link *hlink; 86 87 if (htbl->bucket_cur != NULL) { 88 hlink = htbl->bucket_cur; 89 htbl->bucket_cur = hlink->next; 90 return hlink; 91 } 92 while (htbl->cur < htbl->size) { 93 if (htbl->bucket[htbl->cur] != NULL) { 94 hlink = htbl->bucket[htbl->cur++]; 95 htbl->bucket_cur = hlink->next; 96 return hlink; 97 } 98 htbl->cur++; 99 } 100 return NULL; 101 } 102 103 /* hash_lookup - Lookup item under the key in hash table. 104 * Return a pointer of the bucket on success. Otherwise returns 105 * NULL 106 */ 107 hash_link * 108 hash_lookup(htbl, k) 109 hash_table *htbl; 110 const void *k; 111 { 112 int c; 113 hash_link *w; 114 115 if (htbl == NULL || k == NULL) 116 return NULL; 117 c = (htbl->hash) (k, (int)htbl->size); 118 for (w = htbl->bucket[c]; w != NULL; w = w->next) 119 if (htbl->cmp(w->key, k) == 0) 120 return w; 121 return NULL; 122 } 123 124 /* hash_insert - Insert a item into hash table. 125 * Return 0 on success. Return -1 on failure. 126 */ 127 int 128 hash_insert(htbl, k, i) 129 hash_table *htbl; 130 const void *k; 131 void *i; 132 { 133 int c; 134 hash_link *n; 135 136 if (htbl == NULL || k == NULL) 137 return -1; 138 139 if ((n = malloc(sizeof(hash_link))) == NULL) { 140 return -1; 141 } 142 143 c = (htbl->hash) (k, (int)htbl->size); 144 145 n->item = i; 146 n->key = k; 147 n->next = htbl->bucket[c]; 148 htbl->bucket[c] = n; 149 150 return 0; 151 } 152 153 /* hash_delete - Remove a item from hash table. 154 * If memfree then free the item. Return 0 on success. Return -1 155 * on failure. 156 */ 157 int 158 hash_delete(htbl, k, memfree) 159 hash_table *htbl; 160 const void *k; 161 int memfree; 162 { 163 int i; 164 hash_link *b, *w; 165 166 if (htbl == NULL || k == NULL) 167 return -1; 168 169 i = (htbl->hash) (k, (int)htbl->size); 170 171 for (w = htbl->bucket[i], b = NULL; w != NULL; w = w->next) { 172 if (htbl->cmp(w->key, k) == 0) { 173 if (b != NULL) 174 b->next = w->next; 175 else 176 htbl->bucket[i] = w->next; 177 178 if (htbl->bucket_cur == w) 179 htbl->bucket_cur = w->next; 180 181 if (w->item != NULL && memfree) { 182 free(w->item); 183 } 184 free(w); 185 return 0; 186 } 187 b = w; 188 } 189 return -1; 190 } 191 192 /* 193 * delete all items from this hash_table. 194 * If memfree != 0 then free items. 195 */ 196 void 197 hash_delete_all(htbl, memfree) 198 hash_table *htbl; 199 int memfree; 200 { 201 int i; 202 hash_link *w, *hl; 203 204 for (i = 0; i < htbl->size; i++) { 205 hl = htbl->bucket[i]; 206 htbl->bucket[i] = NULL; 207 while (hl != NULL) { 208 w = hl; 209 hl = hl->next; 210 if (memfree && w->item != NULL) 211 free(w->item); 212 free(w); 213 } 214 } 215 } 216 217 /* hash_free - Free hash table and all buckets. 218 */ 219 void 220 hash_free(htbl) 221 hash_table *htbl; 222 { 223 if (htbl != NULL) { 224 free(htbl->bucket); 225 free(htbl); 226 } 227 } 228