aboutsummaryrefslogtreecommitdiff
path: root/src/ht.c
diff options
context:
space:
mode:
authorJacob Janzen <jacob.a.s.janzen@gmail.com>2024-02-14 12:01:03 -0600
committerJacob Janzen <jacob.a.s.janzen@gmail.com>2024-02-14 12:01:03 -0600
commitb5b4a5d66deefa3858bedf7bc58e6c96340e829b (patch)
tree4aa42f746be3c6ce409938796ca95175dfd1da86 /src/ht.c
parent8bd664e467f760db6f689eb9d30c3d685abe6de5 (diff)
major refactor
Diffstat (limited to 'src/ht.c')
-rw-r--r--src/ht.c224
1 files changed, 224 insertions, 0 deletions
diff --git a/src/ht.c b/src/ht.c
new file mode 100644
index 0000000..39093eb
--- /dev/null
+++ b/src/ht.c
@@ -0,0 +1,224 @@
+#include "ht.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define SIZE 1024
+
+struct node {
+ char *key;
+ void *val;
+ struct node *next;
+};
+
+struct hash_table {
+ struct node **vals;
+ int max_size;
+ int size;
+
+ int curr_index;
+ struct node *curr_node;
+ bool iterating;
+};
+
+static void rehash(ht_t *h, int newsize)
+{
+ ht_t *new_h = ht_create(newsize);
+
+ ht_iter_init(h);
+
+ struct kvp kvp = ht_iter_next(h);
+ while (kvp.key) {
+ ht_insert(new_h, kvp.key, kvp.val);
+ kvp = ht_iter_next(h);
+ }
+
+ // only destroy vals if it isn't NULL
+ if (h->vals) {
+ // iterate through the hash values
+ for (int i = 0; i < h->max_size; ++i) {
+ // iterate through the linked list and remove the value
+ struct node *curr = h->vals[i];
+ struct node *prev;
+ while (curr) {
+ prev = curr;
+ curr = curr->next;
+ free(prev->key);
+ free(prev);
+ }
+ }
+ free(h->vals);
+ }
+
+ h->max_size = newsize;
+ h->vals = new_h->vals;
+ h->curr_index = 0;
+ h->curr_node = NULL;
+ h->iterating = false;
+}
+
+static unsigned long djb2_hash(char *str)
+{
+ unsigned long hash = 5381;
+ int c;
+
+ // hash * 33 + c
+ while ((c = *str++)) hash = ((hash << 5) + hash) + c;
+
+ return hash;
+}
+
+ht_t *ht_create(int max_size)
+{
+ ht_t *h = malloc(sizeof(ht_t));
+ h->max_size = max_size;
+ h->size = 0;
+ h->vals = malloc(sizeof(struct node) * max_size);
+ h->curr_index = 0;
+ h->curr_node = NULL;
+ h->iterating = false;
+
+ return h;
+}
+
+void ht_destroy(ht_t *h)
+{
+ // only destroy if h isn't NULL
+ if (h) {
+ // only destroy vals if it isn't NULL
+ if (h->vals) {
+ // iterate through the hash values
+ for (int i = 0; i < h->max_size; ++i) {
+ // iterate through the linked list and remove the value
+ struct node *curr = h->vals[i];
+ struct node *prev;
+ while (curr) {
+ prev = curr;
+ curr = curr->next;
+ free(prev->key);
+ free(prev);
+ }
+ }
+ free(h->vals);
+ }
+ free(h);
+ }
+}
+
+void *ht_find(ht_t *h, char *key)
+{
+ unsigned int hash = djb2_hash(key) % h->max_size;
+
+ // exit early if hash isn't in table
+ if (!h->vals[hash])
+ return NULL;
+
+ // iterate through values stored at `hash`; exit early if found
+ struct node *curr = h->vals[hash];
+ while (curr) {
+ if (strcmp(key, curr->key) == 0)
+ return curr->val;
+ curr = curr->next;
+ }
+
+ return NULL;
+}
+
+void ht_insert(ht_t *h, char *key, void *val)
+{
+ if (h->size > h->max_size * 0.75)
+ rehash(h, h->max_size * 2);
+
+ unsigned int hash = djb2_hash(key) % h->max_size;
+
+ // create a node
+ int len = strlen(key);
+ struct node *new = malloc(sizeof(struct node));
+ new->key = malloc(sizeof(char) * (len + 1));
+ for (int i = 0; i < len; ++i) {
+ new->key[i] = key[i];
+ }
+ new->key[len] = 0;
+ new->val = val;
+
+ // insert node at beginning of list
+ if (h->vals[hash]) {
+ new->next = h->vals[hash];
+ }
+ h->vals[hash] = new;
+
+ ++(h->size);
+}
+
+void ht_delete(ht_t *h, char *key)
+{
+ if (h->size < h->max_size * 0.25)
+ rehash(h, h->max_size * 0.5);
+
+ unsigned int hash = djb2_hash(key) % h->max_size;
+
+ if (!h->vals[hash])
+ return; // exit if the hash is not found
+
+ // remove the key from the front of the list if it's there
+ if (strcmp(key, h->vals[hash]->key) == 0) {
+ struct node *temp = h->vals[hash];
+ h->vals[hash] = h->vals[hash]->next;
+ free(temp->key);
+ free(temp);
+ } else {
+ // iterate through list and remove once a match is found
+ struct node *prev = h->vals[hash];
+ struct node *curr = h->vals[hash]->next;
+ while (curr) {
+ if (strcmp(key, curr->key) == 0) {
+ prev->next = curr->next;
+ free(curr->key);
+ free(curr);
+ return;
+ }
+
+ prev = curr;
+ curr = curr->next;
+ }
+ }
+}
+
+int ht_size(ht_t *h)
+{
+ return h->size;
+}
+
+void ht_iter_init(ht_t *h)
+{
+ h->curr_index = 0;
+ h->curr_node = h->vals[0];
+}
+
+struct kvp ht_iter_next(ht_t *h)
+{
+ struct kvp out = {
+ .key = NULL,
+ .val = NULL,
+ };
+
+ // return NULL if we've reached the end
+ if (!h->curr_node && h->curr_index >= h->max_size)
+ return out;
+
+ // look for next index with node if current node is NULL
+ if (!h->curr_node) {
+ while (!h->curr_node) {
+ h->curr_node = h->vals[h->curr_index++];
+ if (h->curr_index >= h->max_size)
+ return out;
+ }
+ }
+
+ // get the value and move to the next node
+ out.key = h->curr_node->key;
+ out.val = h->curr_node->val;
+ h->curr_node = h->curr_node->next;
+ return out;
+}