From owner-svn-src-user@FreeBSD.ORG Wed Aug 24 23:49:21 2011 Return-Path: Delivered-To: svn-src-user@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id B2EA51065674; Wed, 24 Aug 2011 23:49:21 +0000 (UTC) (envelope-from gabor@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id A16DA8FC08; Wed, 24 Aug 2011 23:49:21 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id p7ONnLf9075626; Wed, 24 Aug 2011 23:49:21 GMT (envelope-from gabor@svn.freebsd.org) Received: (from gabor@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p7ONnLB8075619; Wed, 24 Aug 2011 23:49:21 GMT (envelope-from gabor@svn.freebsd.org) Message-Id: <201108242349.p7ONnLB8075619@svn.freebsd.org> From: Gabor Kovesdan Date: Wed, 24 Aug 2011 23:49:21 +0000 (UTC) To: src-committers@freebsd.org, svn-src-user@freebsd.org X-SVN-Group: user MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r225156 - in user/gabor/tre-integration: contrib/tre/lib include X-BeenThere: svn-src-user@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the experimental " user" src tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 24 Aug 2011 23:49:21 -0000 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 -#include + +#include #include #include +#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 +#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 #endif /* HAVE_CONFIG_H */ -#include #include #include #include @@ -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 -#include #include #include #include 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 #include #include #include @@ -18,7 +17,7 @@ typedef struct { int *bmGs; char *pattern; int defBc; - hashtable *qsBc_table; + void *qsBc_table; int *sbmGs; const char *re_endp;