Initial commit

6 files changed, 482 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..f9ed49a
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+bin/*
+build/*
+lib/*
diff --git a/Makefile b/Makefile
new file mode 100755
index 0000000..97269af
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,23 @@
+CFLAGS = -Wall -Wextra -Werror -std=c11 -Iinclude -Wno-unused-function -I/usr/local/include -ggdb -O0
+
+.PHONY build:
+build:
+	mkdir -p build
+	mkdir -p bin
+	mkdir -p lib
+
+build/strmap.o: src/strmap.c build
+	clang $(CFLAGS) -c src/strmap.c -o build/strmap.o
+
+lib/strmap.a: build/strmap.o
+	ar rcs lib/strmap.a build/strmap.o 
+	ranlib lib/strmap.a
+
+.PHONY tests:
+tests: lib/strmap.a
+	clang $(CFLAGS) -L/usr/local/lib -lcheck -pthread lib/strmap.a tests/strmap_tests.c -o bin/strmap_tests
+
+
+.PHONY clean:
+clean:
+	rm -r build bin lib
diff --git a/include/hashfuncs.h b/include/hashfuncs.h
new file mode 100755
index 0000000..da5d788
--- /dev/null
+++ b/include/hashfuncs.h
@@ -0,0 +1,33 @@
+#include <stdlib.h>
+
+/*
+ *
+ * 32 bit FNV-1a algorithm
+ * https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+ *
+ */
+static size_t hash_key(const char *key, const size_t max_hash_value) {
+  uint32_t hash = 2166136261U; /* FNV-1a 32-bit offset basis */
+  /*
+   * We'll explicitly use unsigned chars here, since we're doing arithmetic. The
+   * C standard doesn't state whether an implementation must use signed or
+   * unsigned values for characters, so this conversion ensures we get
+   * correct behavior. If signed characters are used, we'll get overflows
+   * and other odd issues in the hash calculation.
+   */
+  const unsigned char *p = (unsigned char *) key;
+
+  while (*p) {
+    hash ^= *p++;
+    hash *= 16777619U; /* FNV-1a prime */
+  }
+
+  return hash % max_hash_value;
+}
+
+static size_t test_hash(const char *key, const size_t max_hash_value) {
+  (void) max_hash_value;
+
+  return key[0] % 3;
+}
+
diff --git a/include/strmap.h b/include/strmap.h
new file mode 100755
index 0000000..634da60
--- /dev/null
+++ b/include/strmap.h
@@ -0,0 +1,38 @@
+/*
+ * strmap.h
+ *
+ * A close-addressing based string -> string hash map
+ * for CISC 301: Operating Systems
+ */
+
+#ifndef H_STRMAP
+#define H_STRMAP
+
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct strmap strmap;
+typedef size_t (*hash_func) (const char *, size_t);
+
+typedef enum {
+  STRMAP_OK,
+  STRMAP_ERR,
+  STRMAP_NOTFOUND
+} strmap_status;
+
+/*
+ * Inserts a new string into a strmap, returning
+ */
+strmap_status strmap_put(strmap*, const char*, const char*);
+
+strmap_status strmap_get(const strmap*, const char*, const char**);
+
+strmap_status strmap_delete(strmap*, const char*);
+
+size_t strmap_size(const strmap*);
+
+strmap *strmap_create(hash_func);
+void strmap_destroy(strmap *);
+
+
+#endif
diff --git a/src/strmap.c b/src/strmap.c
new file mode 100755
index 0000000..c3d0261
--- /dev/null
+++ b/src/strmap.c
@@ -0,0 +1,157 @@
+/*
+ * strmap.c
+ *
+ * A closed-addressing based string -> string hash map
+ * for CISC 301: Operating Systems
+ */
+
+#include "strmap.h"
+
+struct node {
+  char *key;
+  char *value;
+  struct node *next;
+};
+
+struct bucket {
+  struct node *node;
+};
+
+struct strmap {
+  struct bucket *buckets;
+  size_t bucket_cnt;
+  size_t node_cnt;
+  hash_func hash;
+};
+
+static const size_t BCKT_CNT = 101;
+
+static void _destroy_node(struct node *nd) {
+  free(nd->key);
+  free(nd->value);
+  free(nd);
+}
+
+strmap *strmap_create(hash_func hash) {
+  strmap *map = calloc(1, sizeof(*map));
+  if (!map)
+    return NULL;
+
+  map->buckets = calloc(BCKT_CNT, sizeof(struct bucket));
+
+  if (!map->buckets) {
+    free(map);
+    return NULL;
+  }
+
+  map->bucket_cnt = BCKT_CNT;
+  map->node_cnt = 0;
+  map->hash = hash;
+
+  return map;
+}
+
+void strmap_destroy(strmap *map) {
+  for (size_t i = 0; i < map->bucket_cnt; i++) {
+    struct node *nd = map->buckets[i].node;
+    while (nd) {
+      struct node *nd2 = nd->next;
+      _destroy_node(nd);
+      nd = nd2;
+    }
+  }
+
+  free(map->buckets);
+  free(map);
+}
+
+strmap_status strmap_put(strmap *map, const char *key, const char *value) {
+  if (!key || !value)
+    return STRMAP_ERR;
+  struct bucket *bckt = map->buckets + map->hash(key, map->bucket_cnt);
+
+  /*
+   * check if the key already exists in the bucket, in which case we
+   * do an update, rather than allocating a new node
+   */
+  for (struct node *nd = bckt->node; nd; nd = nd->next) {
+    if (!strcmp(nd->key, key)) {
+      char *old_value = nd->value;
+      nd->value = strdup(value);
+      /* if the allocation fails, put the old value back */
+      if (!nd->value) {
+        nd->value = old_value;
+        return STRMAP_ERR;
+      }
+
+      free(old_value);
+      return STRMAP_OK;
+    }
+  }
+
+  struct node *nd = malloc(sizeof(struct node));
+  if (!nd) {
+    /* node allocation failed */
+    goto error_nodealloc;
+  }
+
+  nd->key = strdup(key);
+  nd->value = strdup(value);
+
+  if (nd->key == NULL || nd->value == NULL) {
+    /* string allocation failed */
+    goto error_stringalloc;
+  }
+
+  nd->next = bckt->node;
+  bckt->node = nd;
+  map->node_cnt++;
+  return STRMAP_OK;
+
+error_stringalloc:
+  free(nd->key);
+  free(nd->value);
+error_nodealloc:
+  free(nd);
+  return STRMAP_ERR;
+}
+
+strmap_status strmap_get(const strmap *map, const char *key,
+                         const char **value) {
+  if (!key)
+    return STRMAP_NOTFOUND;
+
+  size_t idx = map->hash(key, map->bucket_cnt);
+
+  struct node *nd;
+  for (nd = map->buckets[idx].node; nd; nd = nd->next) {
+    if (!strcmp(nd->key, key)) {
+      *value = nd->value;
+      return STRMAP_OK;
+    }
+  }
+
+  return STRMAP_NOTFOUND;
+}
+
+strmap_status strmap_delete(strmap *map, const char *key) {
+  if (!key)
+    return STRMAP_NOTFOUND;
+  struct node **nd_ptr = &(map->buckets[map->hash(key, map->bucket_cnt)].node);
+
+  while (*nd_ptr) {
+    struct node *nd = *nd_ptr;
+    if (!strcmp(nd->key, key)) {
+      *nd_ptr = nd->next;
+      _destroy_node(nd);
+      map->node_cnt--;
+      return STRMAP_OK;
+    }
+
+    nd_ptr = &nd->next;
+  }
+
+  return STRMAP_NOTFOUND;
+}
+
+size_t strmap_size(const strmap *map) { return map->node_cnt; }
diff --git a/tests/strmap_tests.c b/tests/strmap_tests.c
new file mode 100755
index 0000000..7f3c34f
--- /dev/null
+++ b/tests/strmap_tests.c
@@ -0,0 +1,228 @@
+/*
+ * strmap_test.c
+ *
+ * Unit tests for strmap implementation
+ */
+
+#include "hashfuncs.h"
+#include "strmap.h"
+
+#include <check.h>
+#include <stdlib.h>
+#include <string.h>
+
+START_TEST(test_create_destroy) {
+  strmap *map = strmap_create(hash_key);
+  ck_assert_ptr_nonnull(map);
+  ck_assert_uint_eq(strmap_size(map), 0);
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_put_get_basic) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 1);
+
+  ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value1");
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_put_update) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "key1", "value2"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 1);
+
+  ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value2");
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_get_nonexistent) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  ck_assert_int_eq(strmap_get(map, "nonexistent", &value), STRMAP_NOTFOUND);
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_delete_basic) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK);
+  ck_assert_int_eq(strmap_delete(map, "key1"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 0);
+
+  ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_NOTFOUND);
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_delete_nonexistent) {
+  strmap *map = strmap_create(hash_key);
+
+  ck_assert_int_eq(strmap_delete(map, "nonexistent"), STRMAP_NOTFOUND);
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_delete_multiple) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  // Add multiple items
+  ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "key2", "value2"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "key3", "value3"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 3);
+
+  // Delete middle item
+  ck_assert_int_eq(strmap_delete(map, "key2"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 2);
+  ck_assert_int_eq(strmap_get(map, "key2", &value), STRMAP_NOTFOUND);
+
+  // Verify remaining items
+  ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value1");
+  ck_assert_int_eq(strmap_get(map, "key3", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value3");
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_delete_head) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  // Add items that will likely hash to same bucket
+  ck_assert_int_eq(strmap_put(map, "a", "first"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "b", "second"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "c", "third"), STRMAP_OK);
+
+  // Delete head item
+  ck_assert_int_eq(strmap_delete(map, "c"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 2);
+  ck_assert_int_eq(strmap_get(map, "c", &value), STRMAP_NOTFOUND);
+
+  // Verify remaining items
+  ck_assert_int_eq(strmap_get(map, "a", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "first");
+  ck_assert_int_eq(strmap_get(map, "b", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "second");
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_collision_handling) {
+  strmap *map = strmap_create(test_hash);
+  const char *value;
+
+  /* all keys with the same initial letter should map to the same bucket */
+  ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "key2", "value2"), STRMAP_OK);
+  ck_assert_int_eq(strmap_put(map, "key3", "value3"), STRMAP_OK);
+  ck_assert_uint_eq(strmap_size(map), 3);
+
+  // Retrieve all values
+  ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value1");
+  ck_assert_int_eq(strmap_get(map, "key2", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value2");
+  ck_assert_int_eq(strmap_get(map, "key3", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "value3");
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_empty_key_value) {
+  strmap *map = strmap_create(hash_key);
+  const char *value;
+
+  // Test empty string key
+  ck_assert_int_eq(strmap_put(map, "", "empty_key_value"), STRMAP_OK);
+  ck_assert_int_eq(strmap_get(map, "", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "empty_key_value");
+
+  // Test empty string value
+  ck_assert_int_eq(strmap_put(map, "empty_value_key", ""), STRMAP_OK);
+  ck_assert_int_eq(strmap_get(map, "empty_value_key", &value), STRMAP_OK);
+  ck_assert_str_eq(value, "");
+
+  strmap_destroy(map);
+}
+END_TEST
+
+START_TEST(test_put_null_key) {
+  strmap *map = strmap_create(hash_key);
+
+  // This should ideally be handled gracefully
+  // Behavior depends on your strdup implementation with NULL
+  // For now, we'll assume it fails gracefully
+  ck_assert_int_eq(strmap_put(map, NULL, "value"), STRMAP_ERR);
+
+  strmap_destroy(map);
+}
+END_TEST
+
+Suite *strmap_suite(void) {
+  Suite *s;
+  TCase *tc_core;
+  TCase *tc_edge;
+
+  s = suite_create("Strmap");
+
+  /* Core test case */
+  tc_core = tcase_create("Core");
+  tcase_add_test(tc_core, test_create_destroy);
+  tcase_add_test(tc_core, test_put_get_basic);
+  tcase_add_test(tc_core, test_put_update);
+  tcase_add_test(tc_core, test_get_nonexistent);
+  tcase_add_test(tc_core, test_delete_basic);
+  tcase_add_test(tc_core, test_delete_nonexistent);
+  tcase_add_test(tc_core, test_delete_multiple);
+  tcase_add_test(tc_core, test_delete_head);
+  tcase_add_test(tc_core, test_collision_handling);
+
+  /* Edge cases */
+  tc_edge = tcase_create("Edge");
+  tcase_add_test(tc_edge, test_empty_key_value);
+  tcase_add_test(tc_edge, test_put_null_key);
+
+  suite_add_tcase(s, tc_core);
+  suite_add_tcase(s, tc_edge);
+
+  return s;
+}
+
+int main(void) {
+  int number_failed;
+  Suite *s;
+  SRunner *sr;
+
+  s = strmap_suite();
+  sr = srunner_create(s);
+
+  srunner_run_all(sr, CK_NORMAL);
+  number_failed = srunner_ntests_failed(sr);
+  srunner_free(sr);
+
+  return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}