1/* $FreeBSD$ */ 2 3/*- 4 * Copyright (C) 2011 Gabor Kovesdan <gabor@FreeBSD.org> 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29#include "glue.h" 30 31#include <errno.h> 32#include <inttypes.h> 33#include <stdlib.h> 34#include <string.h> 35 36#include "hashtable.h" 37 38 39/* 40 * Return a 32-bit hash of the given buffer. The init 41 * value should be 0, or the previous hash value to extend 42 * the previous hash. 43 */ 44static uint32_t 45hash32_buf(const void *buf, size_t len, uint32_t hash) 46{ 47 const unsigned char *p = buf; 48 49 while (len--) 50 hash = HASHSTEP(hash, *p++); 51 52 return hash; 53} 54 55/* 56 * Initializes a hash table that can hold table_size number of entries, 57 * each of which has a key of key_size bytes and a value of value_size 58 * bytes. On successful allocation returns a pointer to the hash table. 59 * Otherwise, returns NULL and sets errno to indicate the error. 60 */ 61hashtable 62*hashtable_init(size_t table_size, size_t key_size, size_t value_size) 63{ 64 hashtable *tbl; 65 66 DPRINT(("hashtable_init: table_size %zu, key_size %zu, value_size %zu\n", 67 table_size, key_size, value_size)); 68 69 tbl = malloc(sizeof(hashtable)); 70 if (tbl == NULL) 71 goto mem1; 72 73 tbl->entries = calloc(sizeof(hashtable_entry *), table_size); 74 if (tbl->entries == NULL) 75 goto mem2; 76 77 tbl->table_size = table_size; 78 tbl->usage = 0; 79 tbl->key_size = key_size; 80 tbl->value_size = value_size; 81 82 return (tbl); 83 84mem2: 85 free(tbl); 86mem1: 87 DPRINT(("hashtable_init: allocation failed\n")); 88 errno = ENOMEM; 89 return (NULL); 90} 91 92/* 93 * Places the key-value pair to the hashtable tbl. 94 * Returns: 95 * HASH_OK: if the key was not present in the hash table yet 96 * but the kay-value pair has been successfully added. 97 * HASH_UPDATED: if the value for the key has been updated with the 98 * new value. 99 * HASH_FULL: if the hash table is full and the entry could not 100 * be added. 101 * HASH_FAIL: if an error has occurred and errno has been set to 102 * indicate the error. 103 */ 104int 105hashtable_put(hashtable *tbl, const void *key, const void *value) 106{ 107 uint32_t hash = 0; 108 109 if (tbl->table_size == tbl->usage) 110 { 111 DPRINT(("hashtable_put: hashtable is full\n")); 112 return (HASH_FULL); 113 } 114 115 hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size; 116 DPRINT(("hashtable_put: calculated hash %" PRIu32 "\n", hash)); 117 118 /* 119 * On hash collision entries are inserted at the next free space, 120 * so we have to increase the index until we either find an entry 121 * with the same key (and update it) or we find a free space. 122 */ 123 for(;;) 124 { 125 if (tbl->entries[hash] == NULL) 126 break; 127 else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0) 128 { 129 memcpy(tbl->entries[hash]->value, value, tbl->value_size); 130 DPRINT(("hashtable_put: effective location is %" PRIu32 131 ", entry updated\n", hash)); 132 return (HASH_UPDATED); 133 } 134 if (++hash == tbl->table_size) 135 hash = 0; 136 } 137 138 DPRINT(("hashtable_put: effective location is %" PRIu32 "\n", hash)); 139 140 tbl->entries[hash] = malloc(sizeof(hashtable_entry)); 141 if (tbl->entries[hash] == NULL) 142 { 143 errno = ENOMEM; 144 goto mem1; 145 } 146 147 tbl->entries[hash]->key = malloc(tbl->key_size); 148 if (tbl->entries[hash]->key == NULL) 149 { 150 errno = ENOMEM; 151 goto mem2; 152 } 153 154 tbl->entries[hash]->value = malloc(tbl->value_size); 155 if (tbl->entries[hash]->value == NULL) 156 { 157 errno = ENOMEM; 158 goto mem3; 159 } 160 161 memcpy(tbl->entries[hash]->key, key, tbl->key_size); 162 memcpy(tbl->entries[hash]->value, value, tbl->value_size); 163 tbl->usage++; 164 165 DPRINT(("hashtable_put: entry successfully inserted\n")); 166 167 return (HASH_OK); 168 169mem3: 170 free(tbl->entries[hash]->key); 171mem2: 172 free(tbl->entries[hash]); 173mem1: 174 DPRINT(("hashtable_put: insertion failed\n")); 175 return (HASH_FAIL); 176} 177 178static hashtable_entry 179**hashtable_lookup(const hashtable *tbl, const void *key) 180{ 181 uint32_t hash = 0; 182 183 hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size; 184 185 for (;;) 186 { 187 if (tbl->entries[hash] == NULL) 188 return (NULL); 189 else if (memcmp(key, tbl->entries[hash]->key, tbl->key_size) == 0) 190 { 191 DPRINT(("hashtable_lookup: entry found at location %" PRIu32 "\n", hash)); 192 return (&tbl->entries[hash]); 193 } 194 195 if (++hash == tbl->table_size) 196 hash = 0; 197 } 198} 199 200/* 201 * Retrieves the value for key from the hash table tbl and places 202 * it to the space indicated by the value argument. 203 * Returns HASH_OK if the value has been found and retrieved or 204 * HASH_NOTFOUND otherwise. 205 */ 206int 207hashtable_get(hashtable *tbl, const void *key, void *value) 208{ 209 hashtable_entry **entry; 210 211 entry = hashtable_lookup(tbl, key); 212 if (entry == NULL) 213 { 214 DPRINT(("hashtable_get: entry is not available in the hashtable\n")); 215 return (HASH_NOTFOUND); 216 } 217 218 memcpy(value, (*entry)->value, tbl->value_size); 219 DPRINT(("hashtable_get: entry successfully copied into output buffer\n")); 220 return (HASH_OK); 221} 222 223/* 224 * Removes the entry with the specifified key from the hash table 225 * tbl. Returns HASH_OK if the entry has been found and removed 226 * or HASH_NOTFOUND otherwise. 227 */ 228int 229hashtable_remove(hashtable *tbl, const void *key) 230{ 231 hashtable_entry **entry; 232 233 entry = hashtable_lookup(tbl, key); 234 if (entry == NULL) 235 { 236 DPRINT(("hashtable_remove: entry is not available in the hashtable\n")); 237 return (HASH_NOTFOUND); 238 } 239 240 free((*entry)->key); 241 free((*entry)->value); 242 free(*entry); 243 *entry = NULL; 244 245 tbl->usage--; 246 DPRINT(("hashtable_remove: entry successfully removed\n")); 247 return (HASH_OK); 248} 249 250/* 251 * Frees the resources associated with the hash table tbl. 252 */ 253void 254hashtable_free(hashtable *tbl) 255{ 256 if (tbl == NULL) 257 return; 258 259 for (unsigned int i = 0; i < tbl->table_size; i++) 260 if ((tbl->entries[i] != NULL)) 261 { 262 free(tbl->entries[i]->key); 263 free(tbl->entries[i]->value); 264 } 265 266 free(tbl->entries); 267 DPRINT(("hashtable_free: resources are successfully freed\n")); 268} 269