diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | Makefile | 30 | ||||
| -rw-r--r-- | compile_commands.json | 54 | ||||
| -rw-r--r-- | include/cavegen.h (renamed from cavegen.h) | 7 | ||||
| -rw-r--r-- | include/common.h | 9 | ||||
| -rw-r--r-- | include/display.h | 40 | ||||
| -rw-r--r-- | include/entity.h | 13 | ||||
| -rw-r--r-- | include/ht.h (renamed from ht.h) | 15 | ||||
| -rw-r--r-- | main.c | 246 | ||||
| -rw-r--r-- | src/cavegen.c (renamed from cavegen.c) | 0 | ||||
| -rw-r--r-- | src/display.c | 201 | ||||
| -rw-r--r-- | src/ht.c (renamed from ht.c) | 62 |
12 files changed, 441 insertions, 239 deletions
@@ -4,6 +4,5 @@ tmp/ *.o -/main +build/ .ccls-cache -main.dSYM/ @@ -1,15 +1,27 @@ -all: main +CC=clang +SRCDIR=src +BUILDDIR=build +TARGET=$(BUILDDIR)/main -CFLAGS=-g +INCLUDE_PATHS=-Iinclude +LDFLAGS=-lcurses -main: main.c cavegen.o ht.o - $(CC) main.c cavegen.o ht.o -lcurses -o main -D_XOPEN_SOURCE_EXTENDED $(CFLAGS) +SRCS=$(wildcard $(SRCDIR)/*.c) +OBJS=$(patsubst $(SRCDIR)/%.c,$(BUILDDIR)/%.o,$(SRCS)) -cavegen.o: cavegen.c - $(CC) cavegen.c -c -o cavegen.o $(CFLAGS) +all: $(TARGET) -ht.o: ht.c - $(CC) ht.c -c -o ht.o $(CFLAGS) +$(BUILDDIR)/%.o: $(SRCDIR)/%.c + mkdir -p $(BUILDDIR) + $(CC) -c $(CFLAGS) $(INCLUDE_PATHS) $^ -o $@ + +$(BUILDDIR)/main.o: main.c + mkdir -p $(BUILDDIR) + $(CC) -c $(CFLAGS) $(INCLUDE_PATHS) $^ -o $@ + +$(TARGET): $(OBJS) $(BUILDDIR)/main.o + mkdir -p $(BUILDDIR) + $(CC) -o $@ $(LDFLAGS) $^ clean: - rm -rf main cavegen.o + rm -rf $(BUILDDIR) diff --git a/compile_commands.json b/compile_commands.json new file mode 100644 index 0000000..d26e416 --- /dev/null +++ b/compile_commands.json @@ -0,0 +1,54 @@ +[ + { + "arguments": [ + "/usr/bin/clang", + "-c", + "-Iinclude", + "-o", + "build/cavegen.o", + "src/cavegen.c" + ], + "directory": "/Users/jjanzen/Documents/projects/mapgen", + "file": "/Users/jjanzen/Documents/projects/mapgen/src/cavegen.c", + "output": "/Users/jjanzen/Documents/projects/mapgen/build/cavegen.o" + }, + { + "arguments": [ + "/usr/bin/clang", + "-c", + "-Iinclude", + "-o", + "build/display.o", + "src/display.c" + ], + "directory": "/Users/jjanzen/Documents/projects/mapgen", + "file": "/Users/jjanzen/Documents/projects/mapgen/src/display.c", + "output": "/Users/jjanzen/Documents/projects/mapgen/build/display.o" + }, + { + "arguments": [ + "/usr/bin/clang", + "-c", + "-Iinclude", + "-o", + "build/ht.o", + "src/ht.c" + ], + "directory": "/Users/jjanzen/Documents/projects/mapgen", + "file": "/Users/jjanzen/Documents/projects/mapgen/src/ht.c", + "output": "/Users/jjanzen/Documents/projects/mapgen/build/ht.o" + }, + { + "arguments": [ + "/usr/bin/clang", + "-c", + "-Iinclude", + "-o", + "build/main.o", + "main.c" + ], + "directory": "/Users/jjanzen/Documents/projects/mapgen", + "file": "/Users/jjanzen/Documents/projects/mapgen/main.c", + "output": "/Users/jjanzen/Documents/projects/mapgen/build/main.o" + } +] diff --git a/cavegen.h b/include/cavegen.h index 05d2fd2..b6ed1e4 100644 --- a/cavegen.h +++ b/include/cavegen.h @@ -1,7 +1,7 @@ #ifndef CAVEGEN_H_ #define CAVEGEN_H_ -#include <stdbool.h> +#include "common.h" #define HEIGHT 100 #define WIDTH 180 @@ -13,11 +13,6 @@ enum tile_type { DOWN_STAIR, }; -struct point { - int x; - int y; -}; - struct map { enum tile_type *map; struct point entry_point; diff --git a/include/common.h b/include/common.h new file mode 100644 index 0000000..11b11d4 --- /dev/null +++ b/include/common.h @@ -0,0 +1,9 @@ +#ifndef COMMON_H_ +#define COMMON_H_ + +struct point { + int x; + int y; +}; + +#endif // COMMON_H_ diff --git a/include/display.h b/include/display.h new file mode 100644 index 0000000..c4f5249 --- /dev/null +++ b/include/display.h @@ -0,0 +1,40 @@ +#ifndef DISPLAY_H_ +#define DISPLAY_H_ + +#include <stdbool.h> + +#include "cavegen.h" +#include "entity.h" +#include "ht.h" + +#define MAIN_PANEL_WIDTH 100 +#define MAIN_PANEL_HEIGHT 41 +#define INSTRUCTION_PANEL_WIDTH 32 +#define INSTRUCTION_PANEL_HEIGHT 39 +#define MESSAGE_PANEL_WIDTH 100 +#define MESSAGE_PANEL_HEIGHT 3 +#define STATUS_PANEL_WIDTH 32 +#define STATUS_PANEL_HEIGHT 5 + +typedef struct windows display_t; + +enum action { + ACTION_NONE, + ACTION_EXIT, + ACTION_DOWN, + ACTION_UP, + ACTION_LEFT, + ACTION_RIGHT, + ACTION_STAIR_DOWN, + ACTION_STAIR_UP, + NUM_ACTIONS, +}; + +display_t *display_init(void); +void display_map(display_t *disp, struct map *map, ht_t *entities); +void display_instructions(display_t *disp); +void display_message(display_t *disp, char *msg); +void display_status(display_t *disp, struct entity *entity); +enum action display_process_input(void); + +#endif // DISPLAY_H_ diff --git a/include/entity.h b/include/entity.h new file mode 100644 index 0000000..b003efe --- /dev/null +++ b/include/entity.h @@ -0,0 +1,13 @@ +#ifndef ENTITY_H_ +#define ENTITY_H_ + +#include "common.h" + +struct entity { + struct point p; + char *disp_ch; + bool solid; + bool visible; +}; + +#endif // ENTITY_H_ @@ -5,16 +5,25 @@ typedef struct hash_table ht_t; -ht_t *ht_create(void); +struct kvp { + char *key; + void *val; +}; + +// construct and destructor +ht_t *ht_create(int size); void ht_destroy(ht_t *h); +// accessors 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); +// queries int ht_size(ht_t *h); -void ht_iter_init(ht_t *h); -void *ht_iter_next(ht_t *h); +// iterator +void ht_iter_init(ht_t *h); +struct kvp ht_iter_next(ht_t *h); #endif // HT_H_ @@ -4,169 +4,11 @@ #include <time.h> #include "cavegen.h" +#include "common.h" +#include "display.h" +#include "entity.h" #include "ht.h" -#define MAIN_PANEL_WIDTH 100 -#define MAIN_PANEL_HEIGHT 41 -#define INSTRUCTION_PANEL_WIDTH 32 -#define INSTRUCTION_PANEL_HEIGHT 39 -#define MESSAGE_PANEL_WIDTH 100 -#define MESSAGE_PANEL_HEIGHT 3 -#define STATUS_PANEL_WIDTH 32 -#define STATUS_PANEL_HEIGHT 5 - -#define MAX_ENTITIES 100 - -struct entity { - struct point p; - char *disp_ch; - bool solid; - bool visible; -}; - -struct windows { - WINDOW *main; - WINDOW *inst; - WINDOW *msgs; - WINDOW *stat; -}; - -WINDOW *create_newwin(int height, int width, int starty, int startx) - -{ - WINDOW *local_win = newwin(height, width, starty, startx); - box(local_win, 0, 0); - wrefresh(local_win); - - return local_win; -} - -void initialize(void) -{ - setlocale(LC_ALL, ""); // allow extended ASCII - - initscr(); // initialize curses - - // exit on unsupported consoles - if (LINES < MAIN_PANEL_HEIGHT + MESSAGE_PANEL_HEIGHT || - COLS < MAIN_PANEL_WIDTH + INSTRUCTION_PANEL_WIDTH || !has_colors()) { - endwin(); - fprintf( - stderr, - "a color terminal is required with at least %dx%d characters\n", - INSTRUCTION_PANEL_WIDTH + MAIN_PANEL_WIDTH, - MAIN_PANEL_HEIGHT + MESSAGE_PANEL_HEIGHT - ); - exit(1); - } - - // configure curses if startup was successful - raw(); // disable line buffering - keypad(stdscr, TRUE); // enable reading function keys - noecho(); // don't print input - curs_set(0); // disable the cursor - start_color(); // enable colours - - // setup colours - init_pair(1, COLOR_WHITE, COLOR_BLACK); - init_pair(2, COLOR_BLACK, COLOR_RED); - wattron(stdscr, COLOR_PAIR(1)); - refresh(); -} - -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 + 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) { - mvwaddch(win, i, j, ' '); - } else { - switch (map->map[map_i * map->width + map_j]) { - case GROUND : mvwaddch(win, i, j, '.'); break; - case UP_STAIR : mvwaddch(win, i, j, '<'); break; - case DOWN_STAIR : - wattron(win, COLOR_PAIR(2)); - mvwaddch(win, i, j, '>'); - wattroff(win, COLOR_PAIR(2)); - break; - case WALL : - if (map_i > 0 && - map->map[(map_i - 1) * map->width + map_j] != WALL) { - mvwprintw(win, i, j, "█"); - } else if (map_i < map->width - 1 && map->map[(map_i + 1) * map->width + map_j] != WALL) { - mvwprintw(win, i, j, "█"); - } else if (map_j > 0 && map->map[map_i * map->width + map_j - 1] != WALL) { - mvwprintw(win, i, j, "█"); - } else if (map_j < map->width - 1 && map->map[map_i * map->width + map_j + 1] != WALL) { - mvwprintw(win, i, j, "█"); - } else { - mvwaddch(win, i, j, ' '); - } - break; - default : mvwaddch(win, i, j, ' '); - } - } - } - } - - // print entities - ht_iter_init(entities); - struct entity *e; - while ((e = ht_iter_next(entities))) { - if (e->visible) { - mvwprintw( - win, e->p.y - camera->p.y + 1, e->p.x - camera->p.x + 1, - e->disp_ch - ); - } - } - - wrefresh(win); -} - -void display_instructions(WINDOW *win) -{ - mvwprintw(win, 1, 2, "h - move left"); - mvwprintw(win, 2, 2, "j - move down"); - mvwprintw(win, 3, 2, "k - move up"); - mvwprintw(win, 4, 2, "l - move right"); - mvwprintw(win, 5, 2, "> - move down staircase"); - mvwprintw(win, 6, 2, "< - exit via staircase"); - wrefresh(win); -} - -void display_message(WINDOW *win, char *msg) -{ - for (int i = 1; i < MESSAGE_PANEL_WIDTH - 1; ++i) { - mvwaddch(win, 1, i, ' '); - } - - mvwprintw(win, 1, 1, msg); - wrefresh(win); -} - -void display_status(WINDOW *win, struct entity *entity) -{ - for (int i = 1; i < STATUS_PANEL_HEIGHT - 1; ++i) { - for (int j = 1; j < STATUS_PANEL_WIDTH - 1; ++j) { - mvwaddch(win, i, j, ' '); - } - } - - mvwprintw(win, 1, 2, "HP:"); - mvwprintw(win, 2, 2, "STAMINA:"); - mvwprintw(win, 3, 2, "MANA:"); - - wrefresh(win); -} - bool entity_set_pos(struct entity *e, struct point p, struct map *map) { if (e->solid) { @@ -183,59 +25,38 @@ bool entity_set_pos(struct entity *e, struct point p, struct map *map) return true; } -void create_windows(struct windows *wins) -{ - wins->inst = create_newwin( - INSTRUCTION_PANEL_HEIGHT, INSTRUCTION_PANEL_WIDTH, - (LINES - INSTRUCTION_PANEL_HEIGHT - STATUS_PANEL_HEIGHT) / 2 + 1, - (COLS - MAIN_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 + - MAIN_PANEL_WIDTH - 1 - ); - wins->msgs = create_newwin( - MESSAGE_PANEL_HEIGHT, MESSAGE_PANEL_WIDTH, - (LINES - MAIN_PANEL_HEIGHT - MESSAGE_PANEL_HEIGHT) / 2 + - MAIN_PANEL_HEIGHT, - (COLS - MESSAGE_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 - ); - wins->stat = create_newwin( - STATUS_PANEL_HEIGHT, STATUS_PANEL_WIDTH, - (LINES - INSTRUCTION_PANEL_HEIGHT - STATUS_PANEL_HEIGHT) / 2 + - INSTRUCTION_PANEL_HEIGHT, - (COLS - MAIN_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 + - MAIN_PANEL_WIDTH - 1 - ); - wins->main = create_newwin( - MAIN_PANEL_HEIGHT, MAIN_PANEL_WIDTH, - (LINES - MAIN_PANEL_HEIGHT - MESSAGE_PANEL_HEIGHT) / 2 + 1, - (COLS - MAIN_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 - ); -} - -bool process_input(int ch, ht_t *entities, struct map *map) +bool game_update( + display_t *disp, enum action action, ht_t *entities, struct map *map +) { struct entity *player = ht_find(entities, "player"); struct entity *camera = ht_find(entities, "camera"); struct point newp = player->p; struct point newp_cam = camera->p; - switch (ch) { - case 'k' : + switch (action) { + case ACTION_EXIT : return true; + case ACTION_UP : --newp.y; --newp_cam.y; + display_message(disp, "moving up"); break; - case 'j' : + case ACTION_DOWN : ++newp.y; ++newp_cam.y; + display_message(disp, "moving down"); break; - case 'h' : + case ACTION_LEFT : --newp.x; --newp_cam.x; + display_message(disp, "moving left"); break; - case 'l' : + case ACTION_RIGHT : ++newp.x; ++newp_cam.x; + display_message(disp, "moving right"); break; - case '>' : + case ACTION_STAIR_DOWN : if (map->map[player->p.y * map->width + player->p.x] == DOWN_STAIR) { free(map->map); create_cave(map); @@ -243,13 +64,20 @@ bool process_input(int ch, ht_t *entities, struct map *map) newp = map->entry_point; newp_cam.x = map->entry_point.x - MAIN_PANEL_WIDTH / 2 + 1; newp_cam.y = map->entry_point.y - MAIN_PANEL_HEIGHT / 2 + 1; + display_message(disp, "moving down stairs"); + } else { + display_message(disp, "no stairs to go down"); } break; - case '<' : + case ACTION_STAIR_UP : if (map->map[player->p.y * WIDTH + player->p.x] == UP_STAIR) { + display_message(disp, "moving up stairs"); return true; + } else { + display_message(disp, "no stairs to go up"); } break; + default : display_message(disp, "unrecognized command"); break; } if (entity_set_pos(player, newp, map)) @@ -263,18 +91,14 @@ int main(void) unsigned int seed = time(NULL); srand(seed); - initialize(); - - // create windows - struct windows windows; - create_windows(&windows); + display_t *disp = display_init(); // create the map struct map map; create_cave(&map); // create the entity map - ht_t *entities = ht_create(); + ht_t *entities = ht_create(1); // create the camera struct entity camera; @@ -299,17 +123,17 @@ int main(void) entity_set_pos(&camera, cam_p, &map); // start displaying things - display_map(windows.main, &map, entities); - display_instructions(windows.inst); - display_status(windows.stat, &player); - display_message(windows.msgs, ""); + display_map(disp, &map, entities); + display_instructions(disp); + display_status(disp, &player); + display_message(disp, ""); int ch; bool done = false; - while (!done && (ch = getch()) != KEY_F(1)) { - if (process_input(ch, entities, &map)) - break; - display_map(windows.main, &map, entities); + while (!done) { + enum action action = display_process_input(); + done = game_update(disp, action, entities, &map); + display_map(disp, &map, entities); } free(map.map); diff --git a/cavegen.c b/src/cavegen.c index 1365e9d..1365e9d 100644 --- a/cavegen.c +++ b/src/cavegen.c diff --git a/src/display.c b/src/display.c new file mode 100644 index 0000000..0b08390 --- /dev/null +++ b/src/display.c @@ -0,0 +1,201 @@ +#include "display.h" + +#include <curses.h> +#include <locale.h> +#include <stdlib.h> + +#include "entity.h" + +struct windows { + WINDOW *main; + WINDOW *inst; + WINDOW *msgs; + WINDOW *stat; +}; + +static WINDOW *create_newwin(int height, int width, int y, int x) +{ + WINDOW *local_win = newwin(height, width, y, x); + box(local_win, 0, 0); + wrefresh(local_win); + + return local_win; +} + +static display_t *create_windows(void) +{ + display_t *wins = malloc(sizeof(display_t)); + + wins->inst = create_newwin( + INSTRUCTION_PANEL_HEIGHT, INSTRUCTION_PANEL_WIDTH, + (LINES - INSTRUCTION_PANEL_HEIGHT - STATUS_PANEL_HEIGHT) / 2 + 1, + (COLS - MAIN_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 + + MAIN_PANEL_WIDTH - 1 + ); + wins->msgs = create_newwin( + MESSAGE_PANEL_HEIGHT, MESSAGE_PANEL_WIDTH, + (LINES - MAIN_PANEL_HEIGHT - MESSAGE_PANEL_HEIGHT) / 2 + + MAIN_PANEL_HEIGHT, + (COLS - MESSAGE_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 + ); + wins->stat = create_newwin( + STATUS_PANEL_HEIGHT, STATUS_PANEL_WIDTH, + (LINES - INSTRUCTION_PANEL_HEIGHT - STATUS_PANEL_HEIGHT) / 2 + + INSTRUCTION_PANEL_HEIGHT, + (COLS - MAIN_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 + + MAIN_PANEL_WIDTH - 1 + ); + wins->main = create_newwin( + MAIN_PANEL_HEIGHT, MAIN_PANEL_WIDTH, + (LINES - MAIN_PANEL_HEIGHT - MESSAGE_PANEL_HEIGHT) / 2 + 1, + (COLS - MAIN_PANEL_WIDTH - INSTRUCTION_PANEL_WIDTH) / 2 + ); + + return wins; +} + +display_t *display_init(void) +{ + setlocale(LC_ALL, ""); // allow extended ASCII + + initscr(); // initialize curses + + // exit on unsupported consoles + if (LINES < MAIN_PANEL_HEIGHT + MESSAGE_PANEL_HEIGHT || + COLS < MAIN_PANEL_WIDTH + INSTRUCTION_PANEL_WIDTH || !has_colors()) { + endwin(); + fprintf( + stderr, + "a color terminal is required with at least %dx%d characters\n", + INSTRUCTION_PANEL_WIDTH + MAIN_PANEL_WIDTH, + MAIN_PANEL_HEIGHT + MESSAGE_PANEL_HEIGHT + ); + return NULL; + } + + // configure curses if startup was successful + raw(); // disable line buffering + keypad(stdscr, TRUE); // enable reading function keys + noecho(); // don't print input + curs_set(0); // disable the cursor + start_color(); // enable colours + + // setup colours + init_pair(1, COLOR_WHITE, COLOR_BLACK); + init_pair(2, COLOR_BLACK, COLOR_RED); + wattron(stdscr, COLOR_PAIR(1)); + refresh(); + + return create_windows(); +} + +void display_map(display_t *disp, 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 + 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) { + mvwaddch(disp->main, i, j, ' '); + } else { + switch (map->map[map_i * map->width + map_j]) { + case GROUND : mvwaddch(disp->main, i, j, '.'); break; + case UP_STAIR : mvwaddch(disp->main, i, j, '<'); break; + case DOWN_STAIR : + wattron(disp->main, COLOR_PAIR(2)); + mvwaddch(disp->main, i, j, '>'); + wattroff(disp->main, COLOR_PAIR(2)); + break; + case WALL : + if (map_i > 0 && + map->map[(map_i - 1) * map->width + map_j] != WALL) { + mvwprintw(disp->main, i, j, "█"); + } else if (map_i < map->width - 1 && map->map[(map_i + 1) * map->width + map_j] != WALL) { + mvwprintw(disp->main, i, j, "█"); + } else if (map_j > 0 && map->map[map_i * map->width + map_j - 1] != WALL) { + mvwprintw(disp->main, i, j, "█"); + } else if (map_j < map->width - 1 && map->map[map_i * map->width + map_j + 1] != WALL) { + mvwprintw(disp->main, i, j, "█"); + } else { + mvwaddch(disp->main, i, j, ' '); + } + break; + default : mvwaddch(disp->main, i, j, ' '); + } + } + } + } + + // print entities + ht_iter_init(entities); + struct kvp kvp = ht_iter_next(entities); + while (kvp.key) { + struct entity *e = kvp.val; + if (e->visible) { + mvwprintw( + disp->main, e->p.y - camera->p.y + 1, e->p.x - camera->p.x + 1, + e->disp_ch + ); + } + + kvp = ht_iter_next(entities); + } + + wrefresh(disp->main); +} + +void display_instructions(display_t *disp) +{ + mvwprintw(disp->inst, 1, 2, "h - move left"); + mvwprintw(disp->inst, 2, 2, "j - move down"); + mvwprintw(disp->inst, 3, 2, "k - move up"); + mvwprintw(disp->inst, 4, 2, "l - move right"); + mvwprintw(disp->inst, 5, 2, "> - move down staircase"); + mvwprintw(disp->inst, 6, 2, "< - exit via staircase"); + wrefresh(disp->inst); +} + +void display_message(display_t *disp, char *msg) +{ + for (int i = 1; i < MESSAGE_PANEL_WIDTH - 1; ++i) { + mvwaddch(disp->msgs, 1, i, ' '); + } + + mvwprintw(disp->msgs, 1, 1, msg); + wrefresh(disp->msgs); +} + +void display_status(display_t *disp, struct entity *entity) +{ + for (int i = 1; i < STATUS_PANEL_HEIGHT - 1; ++i) { + for (int j = 1; j < STATUS_PANEL_WIDTH - 1; ++j) { + mvwaddch(disp->stat, i, j, ' '); + } + } + + mvwprintw(disp->stat, 1, 2, "HP:"); + mvwprintw(disp->stat, 2, 2, "STAMINA:"); + mvwprintw(disp->stat, 3, 2, "MANA:"); + + wrefresh(disp->stat); +} + +enum action display_process_input(void) +{ + int ch = getch(); + switch (ch) { + case 'k' : return ACTION_UP; + case 'j' : return ACTION_DOWN; + case 'h' : return ACTION_LEFT; + case 'l' : return ACTION_RIGHT; + case '>' : return ACTION_STAIR_DOWN; + case '<' : return ACTION_STAIR_UP; + case KEY_F(1) : return ACTION_EXIT; + default : return ACTION_NONE; + } +} @@ -22,6 +22,42 @@ struct hash_table { 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; @@ -33,12 +69,12 @@ static unsigned long djb2_hash(char *str) return hash; } -ht_t *ht_create(void) +ht_t *ht_create(int max_size) { ht_t *h = malloc(sizeof(ht_t)); - h->max_size = SIZE; + h->max_size = max_size; h->size = 0; - h->vals = malloc(sizeof(struct node) * h->max_size); + h->vals = malloc(sizeof(struct node) * max_size); h->curr_index = 0; h->curr_node = NULL; h->iterating = false; @@ -91,6 +127,9 @@ void *ht_find(ht_t *h, char *key) 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 @@ -114,6 +153,9 @@ void ht_insert(ht_t *h, char *key, void *val) 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]) @@ -154,25 +196,29 @@ void ht_iter_init(ht_t *h) h->curr_node = h->vals[0]; } -void *ht_iter_next(ht_t *h) +struct kvp ht_iter_next(ht_t *h) { - void *out; + 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 NULL; + 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 NULL; + return out; } } // get the value and move to the next node - out = h->curr_node->val; + out.key = h->curr_node->key; + out.val = h->curr_node->val; h->curr_node = h->curr_node->next; return out; } |