Add a set implementation derived from the hash_table implementation.

While it was easy to produce, it's easier to do it once and maintain it than
leave this up to every possible user.  Plus, it means it gets testing.

17 files changed, 1062 insertions, 7 deletions

diff --git a/Makefile.am b/Makefile.am
index b7bd6f2..069932c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -24,7 +24,9 @@ SUBDIRS = . tests
 
 AM_CFLAGS = $(WARN_CFLAGS)
 
-noinst_LTLIBRARIES = libhash_table.la
+noinst_LTLIBRARIES = \
+	libhash_table.la \
+	libset.la
 
 libhash_table_la_SOURCES = \
 	fnv_hash.c \
@@ -32,6 +34,12 @@ libhash_table_la_SOURCES = \
 	hash_table.c \
 	hash_table.h
 
+libset_la_SOURCES = \
+	fnv_hash.c \
+	fnv_hash.h \
+	set.c \
+	set.h
+
 EXTRA_DIST = \
 	COPYING \
 	README
diff --git a/README b/README
index fb85a68..7da0ab7 100644
--- a/README
+++ b/README
@@ -2,6 +2,9 @@ This is a simple hash table implementation written in plain old C.  The goal
 is for this code to be reusable in many of the projects I've worked on that
 could use something better than a poorly-tuned chaining implementation.
 
+A variant is included which is just a set -- hash and key, not hash, key, and
+data.
+
 The intention is that users of this code copy it directly into their
 repositories, as it's quite small and should see very little development.
 
@@ -42,12 +45,6 @@ Performance considerations:
 	This is worked around in practice by later inserts into a hash table
 	with many deletes in it triggering a rehash at the current size.
 
- * 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/configure.ac b/configure.ac
index 8b56d4b..de6ee3d 100644
--- a/configure.ac
+++ b/configure.ac
@@ -50,4 +50,5 @@ AC_SUBST([WARN_CFLAGS])
 AC_OUTPUT([
 	Makefile
 	tests/Makefile
+	tests/set/Makefile
 ])
diff --git a/set.c b/set.c
new file mode 100644
index 0000000..edc4e4e
--- /dev/null
+++ b/set.c
@@ -0,0 +1,346 @@
+/*
+ * Copyright © 2009 Intel Corporation
+ * Copyright © 1988-2004 Keith Packard and Bart Massey.
+ *
+ * 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.
+ *
+ * Except as contained in this notice, the names of the authors
+ * or their institutions shall not be used in advertising or
+ * otherwise to promote the sale, use or other dealings in this
+ * Software without prior written authorization from the
+ * authors.
+ *
+ * Authors:
+ *    Eric Anholt <eric@anholt.net>
+ *    Keith Packard <keithp@keithp.com>
+ */
+
+#include <stdlib.h>
+
+#include "set.h"
+
+#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
+
+/*
+ * From Knuth -- a good choice for hash/rehash values is p, p-2 where
+ * p and p-2 are both prime.  These tables are sized to have an extra 10%
+ * free to avoid exponential performance degradation as the hash table fills
+ */
+
+uint32_t deleted_key_value;
+const void *deleted_key = &deleted_key_value;
+
+static const struct {
+   uint32_t max_entries, size, rehash;
+} hash_sizes[] = {
+    { 2,		5,		3	  },
+    { 4,		7,		5	  },
+    { 8,		13,		11	  },
+    { 16,		19,		17	  },
+    { 32,		43,		41        },
+    { 64,		73,		71        },
+    { 128,		151,		149       },
+    { 256,		283,		281       },
+    { 512,		571,		569       },
+    { 1024,		1153,		1151      },
+    { 2048,		2269,		2267      },
+    { 4096,		4519,		4517      },
+    { 8192,		9013,		9011      },
+    { 16384,		18043,		18041     },
+    { 32768,		36109,		36107     },
+    { 65536,		72091,		72089     },
+    { 131072,		144409,		144407    },
+    { 262144,		288361,		288359    },
+    { 524288,		576883,		576881    },
+    { 1048576,		1153459,	1153457   },
+    { 2097152,		2307163,	2307161   },
+    { 4194304,		4613893,	4613891   },
+    { 8388608,		9227641,	9227639   },
+    { 16777216,		18455029,	18455027  },
+    { 33554432,		36911011,	36911009  },
+    { 67108864,		73819861,	73819859  },
+    { 134217728,	147639589,	147639587 },
+    { 268435456,	295279081,	295279079 },
+    { 536870912,	590559793,	590559791 },
+    { 1073741824,	1181116273,	1181116271},
+    { 2147483648ul,	2362232233ul,	2362232231ul}
+};
+
+static int
+entry_is_free(struct set_entry *entry)
+{
+	return entry->key == NULL;
+}
+
+static int
+entry_is_deleted(struct set_entry *entry)
+{
+	return entry->key == deleted_key;
+}
+
+static int
+entry_is_present(struct set_entry *entry)
+{
+	return entry->key != NULL && entry->key != deleted_key;
+}
+
+struct set *
+set_create(int key_equals_function(const void *a,
+					  const void *b))
+{
+	struct set *ht;
+
+	ht = malloc(sizeof(*ht));
+	if (ht == NULL)
+		return NULL;
+
+	ht->size_index = 0;
+	ht->size = hash_sizes[ht->size_index].size;
+	ht->rehash = hash_sizes[ht->size_index].rehash;
+	ht->max_entries = hash_sizes[ht->size_index].max_entries;
+	ht->key_equals_function = key_equals_function;
+	ht->table = calloc(ht->size, sizeof(*ht->table));
+	ht->entries = 0;
+	ht->deleted_entries = 0;
+
+	if (ht->table == NULL) {
+		free(ht);
+		return NULL;
+	}
+
+	return ht;
+}
+
+/**
+ * Frees the given set.
+ *
+ * If delete_function is passed, it gets called on each entry present before
+ * freeing.
+ */
+void
+set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
+{
+	if (!ht)
+		return;
+
+	if (delete_function) {
+		struct set_entry *entry;
+
+		for (entry = set_next_entry(ht, NULL);
+		     entry != NULL;
+		     entry = set_next_entry(ht, entry)) {
+			delete_function(entry);
+		}
+	}
+	free(ht->table);
+	free(ht);
+}
+
+/**
+ * Finds a set entry with the given key and hash of that key.
+ *
+ * Returns NULL if no entry is found.
+ */
+struct set_entry *
+set_search(struct set *ht, uint32_t hash, const void *key)
+{
+	uint32_t hash_address;
+
+	hash_address = hash % ht->size;
+	do {
+		uint32_t double_hash;
+
+		struct set_entry *entry = ht->table + hash_address;
+
+		if (entry_is_free(entry)) {
+			return NULL;
+		} else if (entry_is_present(entry) && entry->hash == hash) {
+			if (ht->key_equals_function(key, entry->key)) {
+				return entry;
+			}
+		}
+
+		double_hash = 1 + hash % ht->rehash;
+
+		hash_address = (hash_address + double_hash) % ht->size;
+	} while (hash_address != hash % ht->size);
+
+	return NULL;
+}
+
+static void
+set_rehash(struct set *ht, int new_size_index)
+{
+	struct set old_ht;
+	struct set_entry *table, *entry;
+
+	if (new_size_index >= ARRAY_SIZE(hash_sizes))
+		return;
+
+	table = calloc(hash_sizes[new_size_index].size, sizeof(*ht->table));
+	if (table == NULL)
+		return;
+
+	old_ht = *ht;
+
+	ht->table = table;
+	ht->size_index = new_size_index;
+	ht->size = hash_sizes[ht->size_index].size;
+	ht->rehash = hash_sizes[ht->size_index].rehash;
+	ht->max_entries = hash_sizes[ht->size_index].max_entries;
+	ht->entries = 0;
+	ht->deleted_entries = 0;
+
+	for (entry = old_ht.table;
+	     entry != old_ht.table + old_ht.size;
+	     entry++) {
+		if (entry_is_present(entry)) {
+			set_add(ht, entry->hash, entry->key);
+		}
+	}
+
+	free(old_ht.table);
+}
+
+/**
+ * Inserts the key with the given hash into the table.
+ *
+ * Note that insertion may rearrange the table on a resize or rehash,
+ * so previously found hash_entries are no longer valid after this function.
+ */
+struct set_entry *
+set_add(struct set *ht, uint32_t hash, const void *key)
+{
+	uint32_t hash_address;
+
+	if (ht->entries >= ht->max_entries) {
+		set_rehash(ht, ht->size_index + 1);
+	} else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
+		set_rehash(ht, ht->size_index);
+	}
+
+	hash_address = hash % ht->size;
+	do {
+		struct set_entry *entry = ht->table + hash_address;
+		uint32_t double_hash;
+
+		if (!entry_is_present(entry)) {
+			if (entry_is_deleted(entry))
+				ht->deleted_entries--;
+			entry->hash = hash;
+			entry->key = key;
+			ht->entries++;
+			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 keys 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;
+			return entry;
+		}
+
+
+		double_hash = 1 + hash % ht->rehash;
+
+		hash_address = (hash_address + double_hash) % ht->size;
+	} while (hash_address != hash % ht->size);
+
+	/* We could hit here if a required resize failed. An unchecked-malloc
+	 * application could ignore this result.
+	 */
+	return NULL;
+}
+
+/**
+ * This function deletes the given hash table entry.
+ *
+ * Note that deletion doesn't otherwise modify the table, so an iteration over
+ * the table deleting entries is safe.
+ */
+void
+set_remove(struct set *ht, struct set_entry *entry)
+{
+	if (!entry)
+		return;
+
+	entry->key = deleted_key;
+	ht->entries--;
+	ht->deleted_entries++;
+}
+
+/**
+ * This function is an iterator over the hash table.
+ *
+ * Pass in NULL for the first entry, as in the start of a for loop.  Note that
+ * an iteration over the table is O(table_size) not O(entries).
+ */
+struct set_entry *
+set_next_entry(struct set *ht, struct set_entry *entry)
+{
+	if (entry == NULL)
+		entry = ht->table;
+	else
+		entry = entry + 1;
+
+	for (; entry != ht->table + ht->size; entry++) {
+		if (entry_is_present(entry)) {
+			return entry;
+		}
+	}
+
+	return NULL;
+}
+
+struct set_entry *
+set_random_entry(struct set *ht,
+		 int (*predicate)(struct set_entry *entry))
+{
+	struct set_entry *entry;
+	uint32_t i = random() % ht->size;
+
+	if (ht->entries == 0)
+		return NULL;
+
+	for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
+		if (entry_is_present(entry) &&
+		    (!predicate || predicate(entry))) {
+			return entry;
+		}
+	}
+
+	for (entry = ht->table; entry != ht->table + i; entry++) {
+		if (entry_is_present(entry) &&
+		    (!predicate || predicate(entry))) {
+			return entry;
+		}
+	}
+
+	return NULL;
+}
diff --git a/set.h b/set.h
new file mode 100644
index 0000000..a3b930b
--- /dev/null
+++ b/set.h
@@ -0,0 +1,60 @@
+/*
+ * 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 <inttypes.h>
+
+struct set_entry {
+	uint32_t hash;
+	const void *key;
+};
+
+struct set {
+	struct set_entry *table;
+	int (*key_equals_function)(const void *a, const void *b);
+	uint32_t size;
+	uint32_t rehash;
+	uint32_t max_entries;
+	uint32_t size_index;
+	uint32_t entries;
+	uint32_t deleted_entries;
+};
+
+struct set *set_create(int (*key_equals_function)(const void *a,
+						  const void *b));
+void set_destroy(struct set *set,
+		 void (*delete_function)(struct set_entry *entry));
+
+struct set_entry *set_add(struct set *set, uint32_t hash, const void *key);
+struct set_entry *set_search(struct set *set, uint32_t hash,
+			     const void *key);
+void set_remove(struct set *set, struct set_entry *entry);
+
+struct set_entry *set_next_entry(struct set *set,
+				 struct set_entry *entry);
+struct set_entry *
+set_random_entry(struct set *set,
+		 int (*predicate)(struct set_entry *entry));
diff --git a/tests/Makefile.am b/tests/Makefile.am
index df9bccc..2a1f7eb 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,6 +18,8 @@
 #  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.
 
+SUBDIRS = set
+
 AM_CFLAGS = $(WARN_CFLAGS) -I..
 LDADD = ../libhash_table.la
 
diff --git a/tests/set/.gitignore b/tests/set/.gitignore
new file mode 100644
index 0000000..9cd5918
--- /dev/null
+++ b/tests/set/.gitignore
@@ -0,0 +1,9 @@
+delete_and_lookup
+delete_management
+destroy_callback
+insert_and_lookup
+insert_many
+null_destroy
+null_remove
+random_entry
+replacement
diff --git a/tests/set/Makefile.am b/tests/set/Makefile.am
new file mode 100644
index 0000000..f37e710
--- /dev/null
+++ b/tests/set/Makefile.am
@@ -0,0 +1,36 @@
+# 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
+#  on the rights to use, copy, modify, merge, publish, distribute, sub
+#  license, 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 NON-INFRINGEMENT.  IN NO EVENT SHALL
+#  ADAM JACKSON 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.
+
+AM_CFLAGS = $(WARN_CFLAGS) -I../..
+LDADD = ../../libset.la
+
+TESTS = \
+	delete_and_lookup \
+	delete_management \
+	destroy_callback \
+	insert_and_lookup \
+	insert_many \
+	null_destroy \
+	null_remove \
+	random_entry \
+	replacement \
+	$()
+
+EXTRA_PROGRAMS = $(TESTS)
diff --git a/tests/set/delete_and_lookup.c b/tests/set/delete_and_lookup.c
new file mode 100644
index 0000000..d05c819
--- /dev/null
+++ b/tests/set/delete_and_lookup.c
@@ -0,0 +1,75 @@
+/*
+ * 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 "set.h"
+#include "fnv_hash.h"
+
+/* Return collisions, so we can test the deletion behavior for chained
+ * objects.
+ */
+static uint32_t
+badhash(const void *key)
+{
+	return 1;
+}
+
+int
+main(int argc, char **argv)
+{
+	struct set *set;
+	const char *str1 = "test1";
+	const char *str2 = "test2";
+	uint32_t hash_str1 = badhash(str1);
+	uint32_t hash_str2 = badhash(str2);
+	struct set_entry *entry;
+
+	set = set_create(string_key_equals);
+
+	set_add(set, hash_str1, str1);
+	set_add(set, hash_str2, str2);
+
+	entry = set_search(set, hash_str2, str2);
+	assert(strcmp(entry->key, str2) == 0);
+
+	entry = set_search(set, hash_str1, str1);
+	assert(strcmp(entry->key, str1) == 0);
+
+	set_remove(set, entry);
+
+	entry = set_search(set, hash_str1, str1);
+	assert(entry == NULL);
+
+	entry = set_search(set, hash_str2, str2);
+	assert(strcmp(entry->key, str2) == 0);
+
+	set_destroy(set, NULL);
+
+	return 0;
+}
diff --git a/tests/set/delete_management.c b/tests/set/delete_management.c
new file mode 100644
index 0000000..b5c16fe
--- /dev/null
+++ b/tests/set/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 "set.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 set *set;
+	struct set_entry *entry;
+	int size = 10000;
+	uint32_t keys[size];
+	uint32_t i;
+
+	set = set_create(uint32_t_key_equals);
+
+	for (i = 0; i < size; i++) {
+		keys[i] = i;
+
+		set_add(set, i, &keys[i]);
+
+		if (i >= 100) {
+			uint32_t delete_value = i - 100;
+			entry = set_search(set, delete_value, &delete_value);
+			set_remove(set, entry);
+		}
+	}
+
+	/* Make sure that all our entries were present at the end. */
+	for (i = size - 100; i < size; i++) {
+		entry = set_search(set, i, &keys[i]);
+		assert(entry);
+		assert(key_value(entry->key) == i);
+	}
+
+	/* Make sure that no extra entries got in */
+	for (entry = set_next_entry(set, NULL);
+	     entry != NULL;
+	     entry = set_next_entry(set, entry)) {
+		assert(key_value(entry->key) >= size - 100 &&
+		       key_value(entry->key) < size);
+	}
+	assert(set->entries == 100);
+
+	set_destroy(set, NULL);
+
+	return 0;
+}
diff --git a/tests/set/destroy_callback.c b/tests/set/destroy_callback.c
new file mode 100644
index 0000000..6dff3e1
--- /dev/null
+++ b/tests/set/destroy_callback.c
@@ -0,0 +1,67 @@
+/*
+ * 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 "set.h"
+#include "fnv_hash.h"
+
+static const char *str1 = "test1";
+static const char *str2 = "test2";
+static int delete_str1 = 0;
+static int delete_str2 = 0;
+
+static void
+delete_callback(struct set_entry *entry)
+{
+	if (strcmp(entry->key, str1) == 0)
+		delete_str1 = 1;
+	else if (strcmp(entry->key, str2) == 0)
+		delete_str2 = 1;
+	else
+		abort();
+}
+
+int
+main(int argc, char **argv)
+{
+	struct set *set;
+	uint32_t hash_str1 = fnv1_hash_string(str1);
+	uint32_t hash_str2 = fnv1_hash_string(str2);
+
+	set = set_create(string_key_equals);
+
+	set_add(set, hash_str1, str1);
+	set_add(set, hash_str2, str2);
+
+	set_destroy(set, delete_callback);
+
+	assert(delete_str1 && delete_str2);
+
+	return 0;
+}
diff --git a/tests/set/insert_and_lookup.c b/tests/set/insert_and_lookup.c
new file mode 100644
index 0000000..367daac
--- /dev/null
+++ b/tests/set/insert_and_lookup.c
@@ -0,0 +1,58 @@
+/*
+ * 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 "set.h"
+#include "fnv_hash.h"
+
+int
+main(int argc, char **argv)
+{
+	struct set *set;
+	const char *str1 = "test1";
+	const char *str2 = "test2";
+	uint32_t hash_str1 = fnv1_hash_string(str1);
+	uint32_t hash_str2 = fnv1_hash_string(str2);
+	struct set_entry *entry;
+
+	set = set_create(string_key_equals);
+
+	set_add(set, hash_str1, str1);
+	set_add(set, hash_str2, str2);
+
+	entry = set_search(set, hash_str1, str1);
+	assert(strcmp(entry->key, str1) == 0);
+
+	entry = set_search(set, hash_str2, str2);
+	assert(strcmp(entry->key, str2) == 0);
+
+	set_destroy(set, NULL);
+
+	return 0;
+}
diff --git a/tests/set/insert_many.c b/tests/set/insert_many.c
new file mode 100644
index 0000000..4c8dfd0
--- /dev/null
+++ b/tests/set/insert_many.c
@@ -0,0 +1,73 @@
+/*
+ * 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 "set.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 set *set;
+	struct set_entry *entry;
+	int size = 10000;
+	uint32_t keys[size];
+	uint32_t i;
+
+	set = set_create(uint32_t_key_equals);
+
+	for (i = 0; i < size; i++) {
+		keys[i] = i;
+
+		set_add(set, i, keys + i);
+	}
+
+	for (i = 0; i < size; i++) {
+		entry = set_search(set, i, keys + i);
+		assert(entry);
+		assert(key_value(entry->key) == i);
+	}
+	assert(set->entries == size);
+
+	set_destroy(set, NULL);
+
+	return 0;
+}
diff --git a/tests/set/null_destroy.c b/tests/set/null_destroy.c
new file mode 100644
index 0000000..cf7fc7a
--- /dev/null
+++ b/tests/set/null_destroy.c
@@ -0,0 +1,37 @@
+/*
+ * 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 "set.h"
+
+int
+main(int argc, char **argv)
+{
+	set_destroy(NULL, NULL);
+
+	return 0;
+}
diff --git a/tests/set/null_remove.c b/tests/set/null_remove.c
new file mode 100644
index 0000000..e607062
--- /dev/null
+++ b/tests/set/null_remove.c
@@ -0,0 +1,46 @@
+/*
+ * 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 "set.h"
+#include "fnv_hash.h"
+
+int
+main(int argc, char **argv)
+{
+	struct set *set;
+
+	set = set_create(string_key_equals);
+
+	set_remove(set, NULL);
+
+	set_destroy(set, NULL);
+
+	return 0;
+}
diff --git a/tests/set/random_entry.c b/tests/set/random_entry.c
new file mode 100644
index 0000000..371d02f
--- /dev/null
+++ b/tests/set/random_entry.c
@@ -0,0 +1,89 @@
+/*
+ * Copyrigset © 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 rigsets 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 copyrigset 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 COPYRIGSET 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 "set.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);
+}
+
+static int
+uint32_t_key_is_even(struct set_entry *entry)
+{
+	return (key_value(entry->key) & 1) == 0;
+}
+
+int
+main(int argc, char **argv)
+{
+	struct set *set;
+	struct set_entry *entry;
+	int size = 10000;
+	uint32_t keys[size];
+	uint32_t i, random_value;
+
+	set = set_create(uint32_t_key_equals);
+
+	for (i = 0; i < size; i++) {
+		keys[i] = i;
+
+		set_add(set, i, keys + i);
+	}
+
+	/* Test the no-predicate case. */
+	entry = set_random_entry(set, NULL);
+	assert(entry);
+
+	/* Check that we're getting different entries and that the predicate
+	 * works.
+	 */
+	for (i = 0; i < 100; i++) {
+		entry = set_random_entry(set, uint32_t_key_is_even);
+		assert(entry);
+		assert((key_value(entry->key) & 1) == 0);
+		if (i == 0 || key_value(entry->key) != random_value)
+			break;
+		random_value = key_value(entry->key);
+	}
+	assert(i != 100);
+
+	set_destroy(set, NULL);
+
+	return 0;
+}
diff --git a/tests/set/replacement.c b/tests/set/replacement.c
new file mode 100644
index 0000000..1d6d924
--- /dev/null
+++ b/tests/set/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 "set.h"
+#include "fnv_hash.h"
+
+int
+main(int argc, char **argv)
+{
+	struct set *set;
+	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 set_entry *entry;
+
+	set = set_create(string_key_equals);
+
+	set_add(set, hash_str1, str1);
+	set_add(set, hash_str2, str2);
+
+	entry = set_search(set, hash_str1, str1);
+	assert(entry);
+	assert(entry->key == str2);
+
+	set_remove(set, entry);
+
+	entry = set_search(set, hash_str1, str1);
+	assert(!entry);
+
+	set_destroy(set, NULL);
+	free(str1);
+	free(str2);
+
+	return 0;
+}