svn commit: r225156 - in user/gabor/tre-integration:
contrib/tre/lib include
Gabor Kovesdan
gabor at FreeBSD.org
Wed Aug 24 23:49:21 UTC 2011
Author: gabor
Date: Wed Aug 24 23:49:21 2011
New Revision: 225156
URL: http://svn.freebsd.org/changeset/base/225156
Log:
- Clean up the hashtable code
Added:
user/gabor/tre-integration/contrib/tre/lib/hashtable.h
- copied, changed from r224979, user/gabor/tre-integration/include/hashtable.h
Deleted:
user/gabor/tre-integration/include/hashtable.h
Modified:
user/gabor/tre-integration/contrib/tre/lib/hashtable.c
user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c
user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.h
user/gabor/tre-integration/include/Makefile
user/gabor/tre-integration/include/fastmatch.h
Modified: user/gabor/tre-integration/contrib/tre/lib/hashtable.c
==============================================================================
--- user/gabor/tre-integration/contrib/tre/lib/hashtable.c Wed Aug 24 22:46:18 2011 (r225155)
+++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c Wed Aug 24 23:49:21 2011 (r225156)
@@ -25,10 +25,19 @@
*/
#include <sys/hash.h>
-#include <hashtable.h>
+
+#include <errno.h>
#include <stdlib.h>
#include <string.h>
+#include "hashtable.h"
+
+/*
+ * 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)
{
@@ -36,13 +45,11 @@ hashtable
tbl = malloc(sizeof(hashtable));
if (tbl == NULL)
- return (NULL);
+ goto mem1;
tbl->entries = calloc(sizeof(hashtable_entry *), table_size);
- if (tbl->entries == NULL) {
- free(tbl);
- return (NULL);
- }
+ if (tbl->entries == NULL)
+ goto mem2;
tbl->table_size = table_size;
tbl->usage = 0;
@@ -50,96 +57,151 @@ hashtable
tbl->value_size = value_size;
return (tbl);
-}
+mem2:
+ free(tbl);
+mem1:
+ 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)
- return (-1);
+ if (tbl->table_size == tbl->usage) {
+ return (HASH_FULL);
+ }
+
+ hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size;
- hash = hash32_buf(key, tbl->key_size, hash);
- hash %= tbl->table_size;
+ /*
+ * 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);
+ return (HASH_UPDATED);
+ }
+ }
while (tbl->entries[hash] != NULL)
hash = (hash >= tbl->table_size) ? 0 : hash + 1;
tbl->entries[hash] = malloc(sizeof(hashtable_entry));
- if (tbl->entries[hash] == NULL)
- return (-1);
+ if (tbl->entries[hash] == NULL) {
+ errno = ENOMEM;
+ goto mem1;
+ }
tbl->entries[hash]->key = malloc(tbl->key_size);
if (tbl->entries[hash]->key == NULL) {
- free(tbl->entries[hash]);
- return (-1);
+ errno = ENOMEM;
+ goto mem2;
}
tbl->entries[hash]->value = malloc(tbl->value_size);
if (tbl->entries[hash]->value == NULL) {
- free(tbl->entries[hash]->key);
- free(tbl->entries[hash]);
- return (-1);
+ errno = ENOMEM;
+ goto mem3;
}
- memcpy(&tbl->entries[hash]->key, key, tbl->key_size);
- memcpy(&tbl->entries[hash]->value, value, tbl->value_size);
+ memcpy(tbl->entries[hash]->key, key, tbl->key_size);
+ memcpy(tbl->entries[hash]->value, value, tbl->value_size);
tbl->usage++;
- return (0);
+ return (HASH_OK);
+
+mem3:
+ free(tbl->entries[hash]->key);
+mem2:
+ free(tbl->entries[hash]);
+mem1:
+ return (HASH_FAIL);
}
static hashtable_entry
-*hashtable_lookup(const hashtable *tbl, const void *key)
+**hashtable_lookup(const hashtable *tbl, const void *key)
{
uint32_t hash = 0;
- hash = hash32_buf(key, tbl->key_size, hash);
- hash %= tbl->table_size;
+ 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,
+ else if (memcmp(key, tbl->entries[hash]->key,
tbl->key_size) == 0)
- return (tbl->entries[hash]);
+ return (&tbl->entries[hash]);
hash = (hash == tbl->table_size) ? 0 : hash + 1;
}
}
+/*
+ * 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;
+ hashtable_entry **entry;
entry = hashtable_lookup(tbl, key);
if (entry == NULL)
- return (-1);
+ return (HASH_NOTFOUND);
- memcpy(value, &entry->value, tbl->value_size);
- return (0);
+ memcpy(value, (*entry)->value, tbl->value_size);
+ 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;
+ hashtable_entry **entry;
entry = hashtable_lookup(tbl, key);
if (entry == NULL)
- return (-1);
+ return (HASH_NOTFOUND);
-// free(entry->key);
-// free(entry->value);
- free(entry);
+ free((*entry)->key);
+ free((*entry)->value);
+ free(*entry);
+ *entry = NULL;
tbl->usage--;
- return (0);
+ return (HASH_OK);
}
+/*
+ * Frees the resources associated with the hash table tbl.
+ */
void
hashtable_free(hashtable *tbl)
{
@@ -148,10 +210,9 @@ hashtable_free(hashtable *tbl)
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[i]);
- }
+ if ((tbl->entries[i] != NULL)) {
+ free(tbl->entries[i]->key);
+ free(tbl->entries[i]->value);
+ }
free(tbl->entries);
}
Copied and modified: user/gabor/tre-integration/contrib/tre/lib/hashtable.h (from r224979, user/gabor/tre-integration/include/hashtable.h)
==============================================================================
--- user/gabor/tre-integration/include/hashtable.h Thu Aug 18 16:57:51 2011 (r224979, copy source)
+++ user/gabor/tre-integration/contrib/tre/lib/hashtable.h Wed Aug 24 23:49:21 2011 (r225156)
@@ -5,6 +5,12 @@
#include <sys/types.h>
+#define HASH_OK 0
+#define HASH_UPDATED 1
+#define HASH_FAIL 2
+#define HASH_FULL 3
+#define HASH_NOTFOUND 4
+
typedef struct {
void *key;
void *value;
Modified: user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c
==============================================================================
--- user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c Wed Aug 24 22:46:18 2011 (r225155)
+++ user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c Wed Aug 24 23:49:21 2011 (r225156)
@@ -28,7 +28,6 @@
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif /* HAVE_CONFIG_H */
-#include <hashtable.h>
#include <limits.h>
#include <regex.h>
#include <stdbool.h>
@@ -133,7 +132,7 @@ static int fastcmp(const void *, const v
&((tre_char_t *)startptr)[mismatch + 1], &bc); \
gs = fg->bmGs[mismatch]; \
} \
- bc = (r == 0) ? bc : fg->defBc; \
+ bc = (r == HASH_OK) ? bc : fg->defBc; \
DPRINT(("tre_fast_match: mismatch on character %lc," \
"BC %d, GS %d\n", \
((tre_char_t *)startptr)[mismatch + 1], bc, gs)); \
Modified: user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.h
==============================================================================
--- user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.h Wed Aug 24 22:46:18 2011 (r225155)
+++ user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.h Wed Aug 24 23:49:21 2011 (r225156)
@@ -2,7 +2,6 @@
#define TRE_FASTMATCH_H 1
#include <fastmatch.h>
-#include <hashtable.h>
#include <limits.h>
#include <regex.h>
#include <stdbool.h>
Modified: user/gabor/tre-integration/include/Makefile
==============================================================================
--- user/gabor/tre-integration/include/Makefile Wed Aug 24 22:46:18 2011 (r225155)
+++ user/gabor/tre-integration/include/Makefile Wed Aug 24 23:49:21 2011 (r225156)
@@ -11,7 +11,7 @@ INCS= a.out.h ar.h assert.h bitstring.h
db.h \
dirent.h dlfcn.h elf.h elf-hints.h err.h fastmatch.h fmtmsg.h fnmatch.h \
fstab.h fts.h ftw.h getopt.h glob.h grp.h gssapi.h \
- hashtable.h ieeefp.h ifaddrs.h \
+ ieeefp.h ifaddrs.h \
inttypes.h iso646.h kenv.h langinfo.h libgen.h limits.h link.h \
locale.h malloc.h malloc_np.h memory.h monetary.h mpool.h mqueue.h \
ndbm.h netconfig.h \
Modified: user/gabor/tre-integration/include/fastmatch.h
==============================================================================
--- user/gabor/tre-integration/include/fastmatch.h Wed Aug 24 22:46:18 2011 (r225155)
+++ user/gabor/tre-integration/include/fastmatch.h Wed Aug 24 23:49:21 2011 (r225156)
@@ -3,7 +3,6 @@
#ifndef FASTMATCH_H
#define FASTMATCH_H 1
-#include <hashtable.h>
#include <limits.h>
#include <regex.h>
#include <stdbool.h>
@@ -18,7 +17,7 @@ typedef struct {
int *bmGs;
char *pattern;
int defBc;
- hashtable *qsBc_table;
+ void *qsBc_table;
int *sbmGs;
const char *re_endp;
More information about the svn-src-user
mailing list