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