usr.bin/grep/regex/hashtable.c

   1 /*      $FreeBSD$       */
   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  */
  46 static uint32_t
  47 hash32_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  */
  63 hashtable
  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
  86 mem2:
  87   free(tbl);
  88 mem1:
  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  */
 106 int
 107 hashtable_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
 171 mem3:
 172   free(tbl->entries[hash]->key);
 173 mem2:
 174   free(tbl->entries[hash]);
 175 mem1:
 176   DPRINT(("hashtable_put: insertion failed\n"));
 177   return (HASH_FAIL);
 178 }
 179
 180 static 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  */
 208 int
 209 hashtable_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  */
 230 int
 231 hashtable_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  */
 255 void
 256 hashtable_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 }