summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--SConstruct9
-rw-r--r--include/datastructures/hashtable.h17
-rw-r--r--src/hashtable.c129
-rw-r--r--test/hashtable.c17
4 files changed, 172 insertions, 0 deletions
diff --git a/SConstruct b/SConstruct
new file mode 100644
index 0000000..633e300
--- /dev/null
+++ b/SConstruct
@@ -0,0 +1,9 @@
+from os import environ
+
+env = Environment(ENV={"PATH": environ["PATH"],
+ "TERM": environ["TERM"]},
+ CC="gcc",
+ CFLAGS=["-std=c11", "-Wall", "-Wextra", "-Wpedantic", "-Werror", "-ggdb3", "-Og"],
+ CPPPATH=["include"])
+
+env.Program("build/hashtable", ["test/hashtable.c", "src/hashtable.c"])
diff --git a/include/datastructures/hashtable.h b/include/datastructures/hashtable.h
new file mode 100644
index 0000000..c9020dd
--- /dev/null
+++ b/include/datastructures/hashtable.h
@@ -0,0 +1,17 @@
+#ifndef HASHTABLE_
+#define HASHTABLE_
+
+typedef struct hashtable HashTable;
+typedef char const * Key;
+typedef int Value;
+
+HashTable *ht_create(void);
+void ht_destroy(HashTable *ht);
+
+void ht_insert(HashTable * const ht, Key k, Value v);
+int ht_contains(HashTable const * const ht, Key k);
+int ht_delete(HashTable * const ht, Key k);
+
+int ht_count(HashTable const * const ht);
+
+#endif
diff --git a/src/hashtable.c b/src/hashtable.c
new file mode 100644
index 0000000..14536b7
--- /dev/null
+++ b/src/hashtable.c
@@ -0,0 +1,129 @@
+#include "datastructures/hashtable.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <stdbool.h>
+
+
+#define HASHTABLE_SIZE 27
+
+struct ht_entry {
+ struct ht_entry *next, *prev;
+ Key key;
+ Value val;
+};
+
+struct hashtable {
+ struct ht_entry *keys[HASHTABLE_SIZE];
+};
+
+
+static
+void *xcalloc(size_t nmemb, size_t size)
+{
+ void *p = calloc(nmemb, size);
+ if (!p)
+ abort();
+ return p;
+}
+
+
+static
+unsigned ht_hash_(Key const key)
+{
+ int hash = 0;
+ for (Key k = key; *k; ++k)
+ hash += *k;
+ return (unsigned) (hash % HASHTABLE_SIZE);
+}
+
+static
+int ht_eq_(Key const a, Key const b)
+{
+ return (0 == strcmp(a, b));
+}
+
+HashTable *ht_create(void) {
+ return xcalloc(sizeof (HashTable), 1);
+}
+
+void ht_destroy(HashTable *ht)
+{
+ for (int i = 0; i < HASHTABLE_SIZE; ++i) {
+ struct ht_entry *current = ht->keys[i], *next;
+ while (current) {
+ next = current->next;
+ free(current);
+ current = next;
+ }
+ }
+ free(ht);
+}
+
+void ht_insert(HashTable * const ht, Key k, Value v)
+{
+ unsigned const hash = ht_hash_(k);
+ struct ht_entry *e;
+ if ((e = ht->keys[hash])) {
+ while (e) {
+ if (ht_eq_(k, e->key))
+ return;
+ if (!e->next) {
+ struct ht_entry *entry = xcalloc(sizeof (struct ht_entry), 1);
+ entry->key = k;
+ entry->val = v;
+ e->next = entry;
+ entry->prev = e;
+ return;
+ }
+ e = e->next;
+ }
+ } else {
+ struct ht_entry *entry = xcalloc(sizeof (struct ht_entry), 1);
+ entry->key = k;
+ entry->val = v;
+ ht->keys[hash] = entry;
+ return;
+ }
+}
+
+int ht_contains(HashTable const * const ht, Key k)
+{
+ unsigned const hash = ht_hash_(k);
+ for (struct ht_entry *e = ht->keys[hash]; e; e = e->next) {
+ if (ht_eq_(k, e->key))
+ return true;
+ }
+ return false;
+}
+
+int ht_delete(HashTable * const ht, Key k)
+{
+ unsigned const hash = ht_hash_(k);
+ for (struct ht_entry *e = ht->keys[hash]; e; e = e->next) {
+ if (ht_eq_(k, e->key)) {
+ if (e->next)
+ e->next->prev = e->prev;
+ if (e->prev)
+ e->prev->next = e->next;
+ else
+ ht->keys[hash] = e->next;
+ free(e);
+ return true;
+ }
+ }
+ return false;
+}
+
+int ht_count(HashTable const * const ht)
+{
+ int total = 0;
+ for (int i = 0; i < HASHTABLE_SIZE; ++i) {
+ for (struct ht_entry *e = ht->keys[i]; e; e = e->next) {
+ ++total;
+ }
+ }
+ return total;
+}
diff --git a/test/hashtable.c b/test/hashtable.c
new file mode 100644
index 0000000..3df05b6
--- /dev/null
+++ b/test/hashtable.c
@@ -0,0 +1,17 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "datastructures/hashtable.h"
+
+int main(int argc, char *argv[])
+{
+ HashTable *h = ht_create();
+ for (int i = 1; i < argc; ++i)
+ ht_insert(h, argv[i], i);
+ printf("%d elements in h\n", ht_count(h));
+ for (int i = argc; i-- > 1;)
+ ht_delete(h, argv[i]);
+ printf("%d elements in h\n", ht_count(h));
+ ht_destroy(h);
+ exit(EXIT_SUCCESS);
+}