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