Index: user/gabor/tre-integration/contrib/tre/lib/hashtable.c =================================================================== --- user/gabor/tre-integration/contrib/tre/lib/hashtable.c (revision 225160) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c (revision 225161) @@ -1,219 +1,231 @@ /*- * Copyright (C) 2011 Gabor Kovesdan * 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 - #include #include #include #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; 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: 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 (HASH_FULL); hash = hash32_buf(key, tbl->key_size, 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) { 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++; 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) { 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) 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; entry = hashtable_lookup(tbl, key); if (entry == NULL) return (HASH_NOTFOUND); 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; entry = hashtable_lookup(tbl, key); if (entry == NULL) return (HASH_NOTFOUND); free((*entry)->key); free((*entry)->value); free(*entry); *entry = NULL; tbl->usage--; 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); }