Add a testcase for the upcoming deletion management code.

6 files changed, 107 insertions, 5 deletions

diff --git a/README b/README
index 7622075..877314b 100644
--- a/README
+++ b/README
@@ -24,11 +24,11 @@ When deleting an entry, the entry is marked deleted.
 
 Performance considerations:
 
- * Only an extra 10% free is given.
+ * Only an extra 10% free entries is given at any table size.
 
 	This means that as entries are added, the performance of insertion and
 	lookups will degrade as one approaches maximum entries until the table
-	gets resized.  Unless an outside entry management results in a maximum
+	gets resized.  Unless an outside entry manager results in a maximum
 	number of entries close to the hash table's current size limit, this
 	shouldn't be a concern.
 
@@ -40,6 +40,12 @@ Performance considerations:
 	The solution here is to decide when the table is too full of deleted
 	entries and recompute the data into a clean version of the hashtable.
 
+ * The data pointer increases space consumption for the hash table by around
+   50%
+
+	For some applications, such as tracking a set, the data pointer can
+	be removed from the interface and code relatively easily.
+
 In addition to the core hash_table implementation, a sample of the FNV-1a
 32-bit hash function is included for convenience for those that don't wish
 to analyze hash functions on their own.
diff --git a/tests/.gitignore b/tests/.gitignore
index 89dc805..6c96e28 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -1,4 +1,5 @@
 delete_and_lookup
+delete_management
 destroy_callback
 insert_and_lookup
 insert_many
diff --git a/tests/Makefile.am b/tests/Makefile.am
index d941c86..83610ba 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -23,6 +23,7 @@ LDADD = ../libhash_table.la
 
 TESTS = \
 	delete_and_lookup \
+	delete_management \
 	destroy_callback \
 	insert_and_lookup \
 	insert_many \
diff --git a/tests/delete_management.c b/tests/delete_management.c
new file mode 100644
index 0000000..5e3c1e1
--- /dev/null
+++ b/tests/delete_management.c
@@ -0,0 +1,88 @@
+/*
+ * Copyright © 2009 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"
+
+static uint32_t
+key_value(const void *key)
+{
+	return *(const uint32_t *)key;
+}
+
+static int
+uint32_t_key_equals(const void *a, const void *b)
+{
+	return key_value(a) == key_value(b);
+}
+
+int
+main(int argc, char **argv)
+{
+	struct hash_table *ht;
+	struct hash_entry *entry;
+	int size = 10000;
+	uint32_t keys[size];
+	uint32_t i;
+
+	ht = hash_table_create(uint32_t_key_equals);
+
+	for (i = 0; i < size; i++) {
+		keys[i] = i;
+
+		hash_table_insert(ht, i, keys + i, NULL);
+
+		if (i >= 100) {
+			uint32_t delete_value = i - 100;
+			entry = hash_table_search(ht, delete_value,
+						  &delete_value);
+			hash_table_remove(ht, entry);
+		}
+	}
+
+	/* Make sure that all our entries were present at the end. */
+	for (i = size - 100; i < size; i++) {
+		entry = hash_table_search(ht, i, keys + i);
+		assert(entry);
+		assert(key_value(entry->key) == i);
+	}
+
+	/* Make sure that no extra entries got in */
+	for (entry = hash_table_next_entry(ht, NULL);
+	     entry != NULL;
+	     entry = hash_table_next_entry(ht, entry)) {
+		assert(key_value(entry->key) >= size - 100 &&
+		       key_value(entry->key) < size);
+	}
+
+	hash_table_destroy(NULL, NULL);
+
+	return 0;
+}
diff --git a/tests/insert_many.c b/tests/insert_many.c
index b027d23..fc654d8 100644
--- a/tests/insert_many.c
+++ b/tests/insert_many.c
@@ -31,10 +31,16 @@
 #include "hash_table.h"
 #include "fnv_hash.h"
 
+static uint32_t
+key_value(const void *key)
+{
+	return *(const uint32_t *)key;
+}
+
 static int
 uint32_t_key_equals(const void *a, const void *b)
 {
-	return *(uint32_t *)a == *(uint32_t *)b;
+	return key_value(a) == key_value(b);
 }
 
 int
@@ -57,7 +63,7 @@ main(int argc, char **argv)
 	for (i = 0; i < size; i++) {
 		entry = hash_table_search(ht, i, keys + i);
 		assert(entry);
-		assert(*(uint32_t *)entry->key == i);
+		assert(key_value(entry->key) == i);
 	}
 
 	hash_table_destroy(NULL, NULL);
diff --git a/tests/random_entry.c b/tests/random_entry.c
index 796461b..ec6ba18 100644
--- a/tests/random_entry.c
+++ b/tests/random_entry.c
@@ -34,7 +34,7 @@
 static uint32_t
 key_value(const void *key)
 {
-	return *(uint32_t *)key;
+	return *(const uint32_t *)key;
 }
 
 static int