Initial commit

1 files changed, 157 insertions, 0 deletions

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; }