use hash table for entity list

4 files changed, 262 insertions, 38 deletions

diff --git a/Makefile b/Makefile
index 73bf4ce..6ed373f 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,15 @@
 all: main
 
-main: main.c cavegen.o
-	$(CC) main.c cavegen.o -lcurses -o main -D_XOPEN_SOURCE_EXTENDED
+CFLAGS=-g
+
+main: main.c cavegen.o ht.o
+	$(CC) main.c cavegen.o ht.o -lcurses -o main -D_XOPEN_SOURCE_EXTENDED $(CFLAGS)
 
 cavegen.o: cavegen.c
-	$(CC) cavegen.c -c -o cavegen.o
+	$(CC) cavegen.c -c -o cavegen.o $(CFLAGS)
+
+ht.o: ht.c
+	$(CC) ht.c -c -o ht.o $(CFLAGS)
 
 clean:
 	rm -rf main cavegen.o
diff --git a/ht.c b/ht.c
new file mode 100644
index 0000000..d23e141
--- /dev/null
+++ b/ht.c
@@ -0,0 +1,185 @@
+#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 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(void)
+{
+    ht_t *h       = malloc(sizeof(ht_t));
+    h->max_size   = SIZE;
+    h->size       = 0;
+    h->vals       = malloc(sizeof(struct node) * h->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)
+{
+    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)
+{
+    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];
+}
+
+void *ht_iter_next(ht_t *h)
+{
+    // return NULL if we've reached the end
+    if (!h->curr_node && h->curr_index >= h->max_size)
+        return NULL;
+
+    if (!h->curr_node) {
+        // look for next index with node if current node is NULL
+        while (!h->curr_node) {
+            h->curr_node = h->vals[h->curr_index++];
+            if (h->curr_index >= h->max_size)
+                return NULL;
+        }
+        return h->curr_node->val;
+    } else {
+        // move to the next node
+        h->curr_node = h->curr_node->next;
+        if (h->curr_node)
+            return h->curr_node->val;
+
+        // look for next index with node if necessary
+        while (!h->curr_node) {
+            h->curr_node = h->vals[h->curr_index++];
+            if (h->curr_index >= h->max_size)
+                return NULL;
+        }
+        return h->curr_node->val;
+    }
+}
diff --git a/ht.h b/ht.h
new file mode 100644
index 0000000..e2582c6
--- /dev/null
+++ b/ht.h
@@ -0,0 +1,20 @@
+#ifndef HT_H_
+#define HT_H_
+
+#include <stdbool.h>
+
+typedef struct hash_table ht_t;
+
+ht_t *ht_create(void);
+void  ht_destroy(ht_t *h);
+
+void *ht_find(ht_t *h, char *key);
+void  ht_insert(ht_t *h, char *key, void *val);
+void  ht_delete(ht_t *h, char *key);
+
+int ht_size(ht_t *h);
+
+void  ht_iter_init(ht_t *h);
+void *ht_iter_next(ht_t *h);
+
+#endif // HT_H_
diff --git a/main.c b/main.c
index 67a8d07..fd12ba6 100644
--- a/main.c
+++ b/main.c
@@ -4,6 +4,7 @@
 #include <time.h>
 
 #include "cavegen.h"
+#include "ht.h"
 
 #define MAIN_PANEL_WIDTH         100
 #define MAIN_PANEL_HEIGHT        41
@@ -17,7 +18,6 @@
 #define MAX_ENTITIES 100
 
 struct entity {
-    char        *name;
     struct point p;
     char        *disp_ch;
     bool         solid;
@@ -75,15 +75,15 @@ void initialize(void)
     refresh();
 }
 
-void display_map(
-    WINDOW *win, struct map *map, struct entity *entities, int num_entities
-)
+void display_map(WINDOW *win, struct map *map, ht_t *entities)
 {
     // print map
+    struct entity *camera = ht_find(entities, "camera");
+
     for (int i = 1; i < MAIN_PANEL_HEIGHT - 1; ++i) {
         for (int j = 1; j < MAIN_PANEL_WIDTH - 1; ++j) {
-            int map_i = i - 1 + entities[0].p.y;
-            int map_j = j - 1 + entities[0].p.x;
+            int map_i = i - 1 + camera->p.y;
+            int map_j = j - 1 + camera->p.x;
 
             if (map_i > map->height || map_j > map->width || map_i < 0 ||
                 map_j < 0) {
@@ -118,14 +118,17 @@ void display_map(
     }
 
     // print entities
-    for (int i = 1; i < num_entities; ++i) {
-        if (entities[i].visible) {
+    ht_iter_init(entities);
+    struct entity *e;
+    while ((e = ht_iter_next(entities))) {
+        if (e->visible) {
             mvwprintw(
-                win, entities[i].p.y - entities[0].p.y + 1,
-                entities[i].p.x - entities[0].p.x + 1, entities[i].disp_ch
+                win, e->p.y - camera->p.y + 1, e->p.x - camera->p.x + 1,
+                e->disp_ch
             );
         }
     }
+
     wrefresh(win);
 }
 
@@ -221,32 +224,42 @@ int main(void)
     struct map map;
     create_cave(&map);
 
-    // create the camera and player at the up stairs
-    struct entity *entities = malloc(sizeof(struct entity) * MAX_ENTITIES);
-    entities[0].disp_ch     = "";
-    entities[0].name        = "camera";
-    entities[0].p.x         = map.entry_point.x - MAIN_PANEL_WIDTH / 2 + 1;
-    entities[0].p.y         = map.entry_point.y - MAIN_PANEL_HEIGHT / 2 + 1;
-    entities[0].solid       = false;
-    entities[0].visible     = false;
-    entities[1].disp_ch     = "@";
-    entities[1].name        = "player";
-    entities[1].p           = map.entry_point;
-    entities[1].solid       = true;
-    entities[1].visible     = true;
-    int num_entities        = 2;
+    // create the entity map
+    ht_t *entities = ht_create();
+
+    // create the camera
+    struct entity camera;
+    camera.disp_ch = "";
+    camera.solid   = false;
+    camera.visible = false;
+    ht_insert(entities, "camera", &camera);
+
+    // create the player
+    struct entity player;
+    player.disp_ch = "@";
+    player.solid   = true;
+    player.visible = true;
+    ht_insert(entities, "player", &player);
+
+    // set starting point
+    struct point cam_p = {
+        .x = map.entry_point.x - MAIN_PANEL_WIDTH / 2 + 1,
+        .y = map.entry_point.y - MAIN_PANEL_HEIGHT / 2 + 1,
+    };
+    entity_set_pos(&player, map.entry_point, &map);
+    entity_set_pos(&camera, cam_p, &map);
 
     // start displaying things
-    display_map(windows.main, &map, entities, num_entities);
+    display_map(windows.main, &map, entities);
     display_instructions(windows.inst);
-    display_status(windows.stat, &entities[1]);
+    display_status(windows.stat, &player);
     display_message(windows.msgs, "");
 
     int  ch;
     bool done = false;
     while (!done && (ch = getch()) != KEY_F(1)) {
-        struct point newp     = entities[1].p;
-        struct point newp_cam = entities[0].p;
+        struct point newp     = player.p;
+        struct point newp_cam = camera.p;
         switch (ch) {
         case 'k' :
             --newp.y;
@@ -265,8 +278,7 @@ int main(void)
             ++newp_cam.x;
             break;
         case '>' :
-            if (map.map[entities[1].p.y * map.width + entities[1].p.x] ==
-                DOWN_STAIR) {
+            if (map.map[player.p.y * map.width + player.p.x] == DOWN_STAIR) {
                 free(map.map);
                 create_cave(&map);
 
@@ -278,17 +290,19 @@ int main(void)
             }
             break;
         case '<' :
-            if (map.map[entities[1].p.y * WIDTH + entities[1].p.x] ==
-                UP_STAIR) {
+            if (map.map[player.p.y * WIDTH + player.p.x] == UP_STAIR) {
                 done = true;
             }
             break;
         }
 
-        if (entity_set_pos(&entities[1], newp, &map))
-            entity_set_pos(&entities[0], newp_cam, &map);
+        if (entity_set_pos(&player, newp, &map))
+            entity_set_pos(&camera, newp_cam, &map);
 
-        display_map(windows.main, &map, entities, num_entities);
+        display_map(windows.main, &map, entities);
+        char msg[100];
+        sprintf(msg, "x: %d, y: %d", player.p.x, player.p.y);
+        display_message(windows.msgs, msg);
     }
 
     free(map.map);