diff options
author | Eric Anholt <eric@anholt.net> | 2011-08-18 09:19:53 -0700 |
---|---|---|
committer | Eric Anholt <eric@anholt.net> | 2011-08-18 09:25:27 -0700 |
commit | 391a6c0aefab18eacb83456b3bcb161cc7371773 (patch) | |
tree | 35b93476b4b0bc1c1fed921a3ead8b6c381b51f0 | |
parent | 1bb8bdb4653e9b05706901fe01012eb170ee0500 (diff) |
Add defined behavior for inserts with matching keys, and a test.
-rw-r--r-- | README | 6 | ||||
-rw-r--r-- | hash_table.c | 19 | ||||
-rw-r--r-- | tests/.gitignore | 1 | ||||
-rw-r--r-- | tests/Makefile.am | 1 | ||||
-rw-r--r-- | tests/replacement.c | 63 |
5 files changed, 88 insertions, 2 deletions
@@ -13,8 +13,10 @@ with rehashing. The table stores for each entry: * pointer to the data. Inserts occur at key->hash % hash->size. When an insert collides, the insert -reattempts at (key->hash % hash->size + hash->reprobe) % hash->size, and -onwards at increments of reprobe until a free or dead entry is found. +steps through the table using the reprobe stride until a free or dead entry is +found. When an insert occurs with a key matching a key already in the table, +the new data is associated with the key. Note that old key/data is not freed, +so if memory management is required, do a search before insert. When searching, the search starts at key % hash_size and continues at increments of reprobe as with inserts, until the matching entry or an diff --git a/hash_table.c b/hash_table.c index 6367ea3..e295472 100644 --- a/hash_table.c +++ b/hash_table.c @@ -255,6 +255,25 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, return entry; } + /* Implement replacement when another insert happens + * with a matching key. This is a relatively common + * feature of hash tables, with the alternative + * generally being "insert the new value as well, and + * return it first when the key is searched for". + * + * Note that the hash table doesn't have a delete + * callback. If freeing of old data pointers is + * required to avoid memory leaks, perform a search + * before inserting. + */ + if (entry->hash == hash && + ht->key_equals_function(key, entry->key)) { + entry->key = key; + entry->data = data; + return entry; + } + + double_hash = 1 + hash % ht->rehash; hash_address = (hash_address + double_hash) % ht->size; diff --git a/tests/.gitignore b/tests/.gitignore index 6c96e28..41ca9e7 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -5,3 +5,4 @@ insert_and_lookup insert_many null_destroy random_entry +replacement diff --git a/tests/Makefile.am b/tests/Makefile.am index 83610ba..e681df1 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -29,6 +29,7 @@ TESTS = \ insert_many \ null_destroy \ random_entry \ + replacement \ $() EXTRA_PROGRAMS = $(TESTS) diff --git a/tests/replacement.c b/tests/replacement.c new file mode 100644 index 0000000..eb70906 --- /dev/null +++ b/tests/replacement.c @@ -0,0 +1,63 @@ +/* + * Copyright © 2011 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" +#include "fnv_hash.h" + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + char *str1 = strdup("test1"); + char *str2 = strdup("test1"); + uint32_t hash_str1 = fnv1_hash_string(str1); + uint32_t hash_str2 = fnv1_hash_string(str2); + struct hash_entry *entry; + + ht = hash_table_create(string_key_equals); + + hash_table_insert(ht, hash_str1, str1, str1); + hash_table_insert(ht, hash_str2, str2, str2); + + entry = hash_table_search(ht, hash_str1, str1); + assert(entry); + assert(entry->data == str2); + + hash_table_remove(ht, entry); + + entry = hash_table_search(ht, hash_str1, str1); + assert(!entry); + + hash_table_destroy(ht, NULL); + free(str1); + free(str2); + + return 0; +} |