Index: user/gabor/tre-integration/contrib/tre/lib/hashtable.c =================================================================== --- user/gabor/tre-integration/contrib/tre/lib/hashtable.c (revision 225159) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c (revision 225160) @@ -1,218 +1,219 @@ /*- * 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" /* * 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; + hashtable *tbl; - tbl = malloc(sizeof(hashtable)); - if (tbl == NULL) - goto mem1; + tbl = malloc(sizeof(hashtable)); + if (tbl == NULL) + goto mem1; - tbl->entries = calloc(sizeof(hashtable_entry *), table_size); - if (tbl->entries == NULL) - goto mem2; + 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; + tbl->table_size = table_size; + tbl->usage = 0; + tbl->key_size = key_size; + tbl->value_size = value_size; - return (tbl); + return (tbl); mem2: - free(tbl); + free(tbl); mem1: - errno = ENOMEM; - return (NULL); + 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; + uint32_t hash = 0; - if (tbl->table_size == tbl->usage) { - return (HASH_FULL); - } + 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) % 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); - } - } + /* + * 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; + 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] = 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]->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; - } + 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++; + memcpy(tbl->entries[hash]->key, key, tbl->key_size); + memcpy(tbl->entries[hash]->value, value, tbl->value_size); + tbl->usage++; - return (HASH_OK); + return (HASH_OK); mem3: - free(tbl->entries[hash]->key); + free(tbl->entries[hash]->key); mem2: - free(tbl->entries[hash]); + free(tbl->entries[hash]); mem1: - return (HASH_FAIL); + return (HASH_FAIL); } static hashtable_entry **hashtable_lookup(const hashtable *tbl, const void *key) { - uint32_t hash = 0; + uint32_t hash = 0; - hash = hash32_buf(key, tbl->key_size, 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, - tbl->key_size) == 0) - return (&tbl->entries[hash]); + 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; - } + 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 (HASH_NOTFOUND); + entry = hashtable_lookup(tbl, key); + if (entry == NULL) + return (HASH_NOTFOUND); - memcpy(value, (*entry)->value, tbl->value_size); - return (HASH_OK); + 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 (HASH_NOTFOUND); + entry = hashtable_lookup(tbl, key); + if (entry == NULL) + return (HASH_NOTFOUND); - free((*entry)->key); - free((*entry)->value); - free(*entry); - *entry = NULL; + free((*entry)->key); + free((*entry)->value); + free(*entry); + *entry = NULL; - tbl->usage--; - - return (HASH_OK); + tbl->usage--; + return (HASH_OK); } /* * Frees the resources associated with the hash table tbl. */ void hashtable_free(hashtable *tbl) { + if (tbl == NULL) + return; - 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); + } - 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); + free(tbl->entries); }