aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJacob Janzen <jacob.a.s.janzen@gmail.com>2024-02-12 21:43:52 -0600
committerJacob Janzen <jacob.a.s.janzen@gmail.com>2024-02-12 21:43:52 -0600
commit92cd6c46f410862466c143d96a3f577f2ede855f (patch)
tree18e1108fe18f3ab9e0988d1e908dafce509125eb
parent04ce76d5dc222b2bd031ebd24ede6114b76a2d52 (diff)
use hash table for entity list
-rw-r--r--Makefile11
-rw-r--r--ht.c185
-rw-r--r--ht.h20
-rw-r--r--main.c84
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);