1226035Sgabor/* $FreeBSD$ */ 2226035Sgabor 3226035Sgabor/*- 4226035Sgabor * Copyright (C) 2011 Gabor Kovesdan <gabor@FreeBSD.org> 5226035Sgabor * All rights reserved. 6226035Sgabor * 7226035Sgabor * Redistribution and use in source and binary forms, with or without 8226035Sgabor * modification, are permitted provided that the following conditions 9226035Sgabor * are met: 10226035Sgabor * 1. Redistributions of source code must retain the above copyright 11226035Sgabor * notice, this list of conditions and the following disclaimer. 12226035Sgabor * 2. Redistributions in binary form must reproduce the above copyright 13226035Sgabor * notice, this list of conditions and the following disclaimer in the 14226035Sgabor * documentation and/or other materials provided with the distribution. 15226035Sgabor * 16226035Sgabor * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17226035Sgabor * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18226035Sgabor * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19226035Sgabor * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20226035Sgabor * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21226035Sgabor * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22226035Sgabor * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23226035Sgabor * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24226035Sgabor * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25226035Sgabor * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26226035Sgabor * SUCH DAMAGE. 27226035Sgabor */ 28226035Sgabor 29226035Sgabor#include "glue.h" 30226035Sgabor 31226035Sgabor#include <errno.h> 32226035Sgabor#include <inttypes.h> 33226035Sgabor#include <stdlib.h> 34226035Sgabor#include <string.h> 35226035Sgabor 36226035Sgabor#include "hashtable.h" 37226035Sgabor 38226035Sgabor 39226035Sgabor/* 40226035Sgabor * Return a 32-bit hash of the given buffer. The init 41226035Sgabor * value should be 0, or the previous hash value to extend 42226035Sgabor * the previous hash. 43226035Sgabor */ 44226035Sgaborstatic uint32_t 45226035Sgaborhash32_buf(const void *buf, size_t len, uint32_t hash) 46226035Sgabor{ 47226035Sgabor const unsigned char *p = buf; 48226035Sgabor 49226035Sgabor while (len--) 50226035Sgabor hash = HASHSTEP(hash, *p++); 51226035Sgabor 52226035Sgabor return hash; 53226035Sgabor} 54226035Sgabor 55226035Sgabor/* 56226035Sgabor * Initializes a hash table that can hold table_size number of entries, 57226035Sgabor * each of which has a key of key_size bytes and a value of value_size 58226035Sgabor * bytes. On successful allocation returns a pointer to the hash table. 59226035Sgabor * Otherwise, returns NULL and sets errno to indicate the error. 60226035Sgabor */ 61226035Sgaborhashtable 62226035Sgabor*hashtable_init(size_t table_size, size_t key_size, size_t value_size) 63226035Sgabor{ 64226035Sgabor hashtable *tbl; 65226035Sgabor 66226035Sgabor DPRINT(("hashtable_init: table_size %zu, key_size %zu, value_size %zu\n", 67226035Sgabor table_size, key_size, value_size)); 68226035Sgabor 69226035Sgabor tbl = malloc(sizeof(hashtable)); 70226035Sgabor if (tbl == NULL) 71226035Sgabor goto mem1; 72226035Sgabor 73226035Sgabor tbl->entries = calloc(sizeof(hashtable_entry *), table_size); 74226035Sgabor if (tbl->entries == NULL) 75226035Sgabor goto mem2; 76226035Sgabor 77226035Sgabor tbl->table_size = table_size; 78226035Sgabor tbl->usage = 0; 79226035Sgabor tbl->key_size = key_size; 80226035Sgabor tbl->value_size = value_size; 81226035Sgabor 82226035Sgabor return (tbl); 83226035Sgabor 84226035Sgabormem2: 85226035Sgabor free(tbl); 86226035Sgabormem1: 87226035Sgabor DPRINT(("hashtable_init: allocation failed\n")); 88226035Sgabor errno = ENOMEM; 89226035Sgabor return (NULL); 90226035Sgabor} 91226035Sgabor 92226035Sgabor/* 93226035Sgabor * Places the key-value pair to the hashtable tbl. 94226035Sgabor * Returns: 95226035Sgabor * HASH_OK: if the key was not present in the hash table yet 96226035Sgabor * but the kay-value pair has been successfully added. 97226035Sgabor * HASH_UPDATED: if the value for the key has been updated with the 98226035Sgabor * new value. 99226035Sgabor * HASH_FULL: if the hash table is full and the entry could not 100226035Sgabor * be added. 101226035Sgabor * HASH_FAIL: if an error has occurred and errno has been set to 102226035Sgabor * indicate the error. 103226035Sgabor */ 104226035Sgaborint 105226035Sgaborhashtable_put(hashtable *tbl, const void *key, const void *value) 106226035Sgabor{ 107226035Sgabor uint32_t hash = 0; 108226035Sgabor 109226035Sgabor if (tbl->table_size == tbl->usage) 110226035Sgabor { 111226035Sgabor DPRINT(("hashtable_put: hashtable is full\n")); 112226035Sgabor return (HASH_FULL); 113226035Sgabor } 114226035Sgabor 115226035Sgabor hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size; 116226035Sgabor DPRINT(("hashtable_put: calculated hash %" PRIu32 "\n", hash)); 117226035Sgabor 118226035Sgabor /* 119226035Sgabor * On hash collision entries are inserted at the next free space, 120226035Sgabor * so we have to increase the index until we either find an entry 121226035Sgabor * with the same key (and update it) or we find a free space. 122226035Sgabor */ 123226035Sgabor for(;;) 124226035Sgabor { 125226035Sgabor if (tbl->entries[hash] == NULL) 126226035Sgabor break; 127226035Sgabor else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0) 128226035Sgabor { 129226035Sgabor memcpy(tbl->entries[hash]->value, value, tbl->value_size); 130226035Sgabor DPRINT(("hashtable_put: effective location is %" PRIu32 131226035Sgabor ", entry updated\n", hash)); 132226035Sgabor return (HASH_UPDATED); 133226035Sgabor } 134226035Sgabor if (++hash == tbl->table_size) 135226035Sgabor hash = 0; 136226035Sgabor } 137226035Sgabor 138226035Sgabor DPRINT(("hashtable_put: effective location is %" PRIu32 "\n", hash)); 139226035Sgabor 140226035Sgabor tbl->entries[hash] = malloc(sizeof(hashtable_entry)); 141226035Sgabor if (tbl->entries[hash] == NULL) 142226035Sgabor { 143226035Sgabor errno = ENOMEM; 144226035Sgabor goto mem1; 145226035Sgabor } 146226035Sgabor 147226035Sgabor tbl->entries[hash]->key = malloc(tbl->key_size); 148226035Sgabor if (tbl->entries[hash]->key == NULL) 149226035Sgabor { 150226035Sgabor errno = ENOMEM; 151226035Sgabor goto mem2; 152226035Sgabor } 153226035Sgabor 154226035Sgabor tbl->entries[hash]->value = malloc(tbl->value_size); 155226035Sgabor if (tbl->entries[hash]->value == NULL) 156226035Sgabor { 157226035Sgabor errno = ENOMEM; 158226035Sgabor goto mem3; 159226035Sgabor } 160226035Sgabor 161226035Sgabor memcpy(tbl->entries[hash]->key, key, tbl->key_size); 162226035Sgabor memcpy(tbl->entries[hash]->value, value, tbl->value_size); 163226035Sgabor tbl->usage++; 164226035Sgabor 165226035Sgabor DPRINT(("hashtable_put: entry successfully inserted\n")); 166226035Sgabor 167226035Sgabor return (HASH_OK); 168226035Sgabor 169226035Sgabormem3: 170226035Sgabor free(tbl->entries[hash]->key); 171226035Sgabormem2: 172226035Sgabor free(tbl->entries[hash]); 173226035Sgabormem1: 174226035Sgabor DPRINT(("hashtable_put: insertion failed\n")); 175226035Sgabor return (HASH_FAIL); 176226035Sgabor} 177226035Sgabor 178226035Sgaborstatic hashtable_entry 179226035Sgabor**hashtable_lookup(const hashtable *tbl, const void *key) 180226035Sgabor{ 181226035Sgabor uint32_t hash = 0; 182226035Sgabor 183226035Sgabor hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size; 184226035Sgabor 185226035Sgabor for (;;) 186226035Sgabor { 187226035Sgabor if (tbl->entries[hash] == NULL) 188226035Sgabor return (NULL); 189226035Sgabor else if (memcmp(key, tbl->entries[hash]->key, tbl->key_size) == 0) 190226035Sgabor { 191226035Sgabor DPRINT(("hashtable_lookup: entry found at location %" PRIu32 "\n", hash)); 192226035Sgabor return (&tbl->entries[hash]); 193226035Sgabor } 194226035Sgabor 195226035Sgabor if (++hash == tbl->table_size) 196226035Sgabor hash = 0; 197226035Sgabor } 198226035Sgabor} 199226035Sgabor 200226035Sgabor/* 201226035Sgabor * Retrieves the value for key from the hash table tbl and places 202226035Sgabor * it to the space indicated by the value argument. 203226035Sgabor * Returns HASH_OK if the value has been found and retrieved or 204226035Sgabor * HASH_NOTFOUND otherwise. 205226035Sgabor */ 206226035Sgaborint 207226035Sgaborhashtable_get(hashtable *tbl, const void *key, void *value) 208226035Sgabor{ 209226035Sgabor hashtable_entry **entry; 210226035Sgabor 211226035Sgabor entry = hashtable_lookup(tbl, key); 212226035Sgabor if (entry == NULL) 213226035Sgabor { 214226035Sgabor DPRINT(("hashtable_get: entry is not available in the hashtable\n")); 215226035Sgabor return (HASH_NOTFOUND); 216226035Sgabor } 217226035Sgabor 218226035Sgabor memcpy(value, (*entry)->value, tbl->value_size); 219226035Sgabor DPRINT(("hashtable_get: entry successfully copied into output buffer\n")); 220226035Sgabor return (HASH_OK); 221226035Sgabor} 222226035Sgabor 223226035Sgabor/* 224226035Sgabor * Removes the entry with the specifified key from the hash table 225226035Sgabor * tbl. Returns HASH_OK if the entry has been found and removed 226226035Sgabor * or HASH_NOTFOUND otherwise. 227226035Sgabor */ 228226035Sgaborint 229226035Sgaborhashtable_remove(hashtable *tbl, const void *key) 230226035Sgabor{ 231226035Sgabor hashtable_entry **entry; 232226035Sgabor 233226035Sgabor entry = hashtable_lookup(tbl, key); 234226035Sgabor if (entry == NULL) 235226035Sgabor { 236226035Sgabor DPRINT(("hashtable_remove: entry is not available in the hashtable\n")); 237226035Sgabor return (HASH_NOTFOUND); 238226035Sgabor } 239226035Sgabor 240226035Sgabor free((*entry)->key); 241226035Sgabor free((*entry)->value); 242226035Sgabor free(*entry); 243226035Sgabor *entry = NULL; 244226035Sgabor 245226035Sgabor tbl->usage--; 246226035Sgabor DPRINT(("hashtable_remove: entry successfully removed\n")); 247226035Sgabor return (HASH_OK); 248226035Sgabor} 249226035Sgabor 250226035Sgabor/* 251226035Sgabor * Frees the resources associated with the hash table tbl. 252226035Sgabor */ 253226035Sgaborvoid 254226035Sgaborhashtable_free(hashtable *tbl) 255226035Sgabor{ 256226035Sgabor if (tbl == NULL) 257226035Sgabor return; 258226035Sgabor 259226035Sgabor for (unsigned int i = 0; i < tbl->table_size; i++) 260226035Sgabor if ((tbl->entries[i] != NULL)) 261226035Sgabor { 262226035Sgabor free(tbl->entries[i]->key); 263226035Sgabor free(tbl->entries[i]->value); 264226035Sgabor } 265226035Sgabor 266226035Sgabor free(tbl->entries); 267226035Sgabor DPRINT(("hashtable_free: resources are successfully freed\n")); 268226035Sgabor} 269