usr.bin/grep/regex/hashtable.c

   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  */
  44 static uint32_t
  45 hash32_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  */
  61 hashtable
  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
  84 mem2:
  85   free(tbl);
  86 mem1:
  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  */
 104 int
 105 hashtable_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
 169 mem3:
 170   free(tbl->entries[hash]->key);
 171 mem2:
 172   free(tbl->entries[hash]);
 173 mem1:
 174   DPRINT(("hashtable_put: insertion failed\n"));
 175   return (HASH_FAIL);
 176 }
 177
 178 static 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  */
 206 int
 207 hashtable_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  */
 228 int
 229 hashtable_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  */
 253 void
 254 hashtable_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 }