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