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