summaryrefslogtreecommitdiffstats
path: root/usr.bin/grep/regex/hashtable.c
diff options
context:
space:
mode:
Diffstat (limited to 'usr.bin/grep/regex/hashtable.c')
-rw-r--r--usr.bin/grep/regex/hashtable.c268
1 files changed, 268 insertions, 0 deletions
diff --git a/usr.bin/grep/regex/hashtable.c b/usr.bin/grep/regex/hashtable.c
new file mode 100644
index 0000000..41ebcd1
--- /dev/null
+++ b/usr.bin/grep/regex/hashtable.c
@@ -0,0 +1,268 @@
+/* $FreeBSD$ */
+
+/*-
+ * Copyright (C) 2011 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "glue.h"
+
+#include <errno.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "hashtable.h"
+
+
+/*
+ * Return a 32-bit hash of the given buffer. The init
+ * value should be 0, or the previous hash value to extend
+ * the previous hash.
+ */
+static uint32_t
+hash32_buf(const void *buf, size_t len, uint32_t hash)
+{
+ const unsigned char *p = buf;
+
+ while (len--)
+ hash = HASHSTEP(hash, *p++);
+
+ return hash;
+}
+
+/*
+ * Initializes a hash table that can hold table_size number of entries,
+ * each of which has a key of key_size bytes and a value of value_size
+ * bytes. On successful allocation returns a pointer to the hash table.
+ * Otherwise, returns NULL and sets errno to indicate the error.
+ */
+hashtable
+*hashtable_init(size_t table_size, size_t key_size, size_t value_size)
+{
+ hashtable *tbl;
+
+ DPRINT(("hashtable_init: table_size %zu, key_size %zu, value_size %zu\n",
+ table_size, key_size, value_size));
+
+ tbl = malloc(sizeof(hashtable));
+ if (tbl == NULL)
+ goto mem1;
+
+ tbl->entries = calloc(sizeof(hashtable_entry *), table_size);
+ if (tbl->entries == NULL)
+ goto mem2;
+
+ tbl->table_size = table_size;
+ tbl->usage = 0;
+ tbl->key_size = key_size;
+ tbl->value_size = value_size;
+
+ return (tbl);
+
+mem2:
+ free(tbl);
+mem1:
+ DPRINT(("hashtable_init: allocation failed\n"));
+ errno = ENOMEM;
+ return (NULL);
+}
+
+/*
+ * Places the key-value pair to the hashtable tbl.
+ * Returns:
+ * HASH_OK: if the key was not present in the hash table yet
+ * but the kay-value pair has been successfully added.
+ * HASH_UPDATED: if the value for the key has been updated with the
+ * new value.
+ * HASH_FULL: if the hash table is full and the entry could not
+ * be added.
+ * HASH_FAIL: if an error has occurred and errno has been set to
+ * indicate the error.
+ */
+int
+hashtable_put(hashtable *tbl, const void *key, const void *value)
+{
+ uint32_t hash = 0;
+
+ if (tbl->table_size == tbl->usage)
+ {
+ DPRINT(("hashtable_put: hashtable is full\n"));
+ return (HASH_FULL);
+ }
+
+ hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size;
+ DPRINT(("hashtable_put: calculated hash %" PRIu32 "\n", hash));
+
+ /*
+ * On hash collision entries are inserted at the next free space,
+ * so we have to increase the index until we either find an entry
+ * with the same key (and update it) or we find a free space.
+ */
+ for(;;)
+ {
+ if (tbl->entries[hash] == NULL)
+ break;
+ else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0)
+ {
+ memcpy(tbl->entries[hash]->value, value, tbl->value_size);
+ DPRINT(("hashtable_put: effective location is %" PRIu32
+ ", entry updated\n", hash));
+ return (HASH_UPDATED);
+ }
+ if (++hash == tbl->table_size)
+ hash = 0;
+ }
+
+ DPRINT(("hashtable_put: effective location is %" PRIu32 "\n", hash));
+
+ tbl->entries[hash] = malloc(sizeof(hashtable_entry));
+ if (tbl->entries[hash] == NULL)
+ {
+ errno = ENOMEM;
+ goto mem1;
+ }
+
+ tbl->entries[hash]->key = malloc(tbl->key_size);
+ if (tbl->entries[hash]->key == NULL)
+ {
+ errno = ENOMEM;
+ goto mem2;
+ }
+
+ tbl->entries[hash]->value = malloc(tbl->value_size);
+ if (tbl->entries[hash]->value == NULL)
+ {
+ errno = ENOMEM;
+ goto mem3;
+ }
+
+ memcpy(tbl->entries[hash]->key, key, tbl->key_size);
+ memcpy(tbl->entries[hash]->value, value, tbl->value_size);
+ tbl->usage++;
+
+ DPRINT(("hashtable_put: entry successfully inserted\n"));
+
+ return (HASH_OK);
+
+mem3:
+ free(tbl->entries[hash]->key);
+mem2:
+ free(tbl->entries[hash]);
+mem1:
+ DPRINT(("hashtable_put: insertion failed\n"));
+ return (HASH_FAIL);
+}
+
+static hashtable_entry
+**hashtable_lookup(const hashtable *tbl, const void *key)
+{
+ uint32_t hash = 0;
+
+ hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size;
+
+ for (;;)
+ {
+ if (tbl->entries[hash] == NULL)
+ return (NULL);
+ else if (memcmp(key, tbl->entries[hash]->key, tbl->key_size) == 0)
+ {
+ DPRINT(("hashtable_lookup: entry found at location %" PRIu32 "\n", hash));
+ return (&tbl->entries[hash]);
+ }
+
+ if (++hash == tbl->table_size)
+ hash = 0;
+ }
+}
+
+/*
+ * Retrieves the value for key from the hash table tbl and places
+ * it to the space indicated by the value argument.
+ * Returns HASH_OK if the value has been found and retrieved or
+ * HASH_NOTFOUND otherwise.
+ */
+int
+hashtable_get(hashtable *tbl, const void *key, void *value)
+{
+ hashtable_entry **entry;
+
+ entry = hashtable_lookup(tbl, key);
+ if (entry == NULL)
+ {
+ DPRINT(("hashtable_get: entry is not available in the hashtable\n"));
+ return (HASH_NOTFOUND);
+ }
+
+ memcpy(value, (*entry)->value, tbl->value_size);
+ DPRINT(("hashtable_get: entry successfully copied into output buffer\n"));
+ return (HASH_OK);
+}
+
+/*
+ * Removes the entry with the specifified key from the hash table
+ * tbl. Returns HASH_OK if the entry has been found and removed
+ * or HASH_NOTFOUND otherwise.
+ */
+int
+hashtable_remove(hashtable *tbl, const void *key)
+{
+ hashtable_entry **entry;
+
+ entry = hashtable_lookup(tbl, key);
+ if (entry == NULL)
+ {
+ DPRINT(("hashtable_remove: entry is not available in the hashtable\n"));
+ return (HASH_NOTFOUND);
+ }
+
+ free((*entry)->key);
+ free((*entry)->value);
+ free(*entry);
+ *entry = NULL;
+
+ tbl->usage--;
+ DPRINT(("hashtable_remove: entry successfully removed\n"));
+ return (HASH_OK);
+}
+
+/*
+ * Frees the resources associated with the hash table tbl.
+ */
+void
+hashtable_free(hashtable *tbl)
+{
+ if (tbl == NULL)
+ return;
+
+ for (unsigned int i = 0; i < tbl->table_size; i++)
+ if ((tbl->entries[i] != NULL))
+ {
+ free(tbl->entries[i]->key);
+ free(tbl->entries[i]->value);
+ }
+
+ free(tbl->entries);
+ DPRINT(("hashtable_free: resources are successfully freed\n"));
+}
OpenPOWER on IntegriCloud