From 40db61eb7a2019ced97f09a9687139f35749f4e0 Mon Sep 17 00:00:00 2001 From: Albert Cervin Date: Sat, 25 Feb 2023 21:37:48 +0100 Subject: Introduce vec and hashmap Convenience macros for a hashmap and a growable vector. --- src/buffer.c | 21 ++++++++---- src/command.c | 48 +++++++++----------------- src/command.h | 7 ++-- src/hashmap.h | 86 ++++++++++++++++++++++++++++++++++++++++++++++ src/settings.c | 74 +++++++++++++--------------------------- src/settings.h | 15 +++------ src/undo.c | 105 +++++++++++++++++++++++---------------------------------- src/undo.h | 5 ++- src/vec.h | 61 +++++++++++++++++++++++++++++++++ 9 files changed, 253 insertions(+), 169 deletions(-) create mode 100644 src/hashmap.h create mode 100644 src/vec.h (limited to 'src') diff --git a/src/buffer.c b/src/buffer.c index 2decdea..e6c3552 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -185,14 +185,13 @@ void delete_with_undo(struct buffer *buffer, struct buffer_location start, struct text_chunk txt = text_get_region(buffer->text, start.line, start.col, end.line, end.col); - undo_push_boundary(&buffer->undo, - (struct undo_boundary){.save_point = false}); - undo_push_delete( &buffer->undo, (struct undo_delete){.data = txt.text, .nbytes = txt.nbytes, .pos = {.row = start.line, .col = start.col}}); + undo_push_boundary(&buffer->undo, + (struct undo_boundary){.save_point = false}); text_delete(buffer->text, start.line, start.col, end.line, end.col); buffer->modified = true; @@ -522,6 +521,11 @@ void buffer_to_file(struct buffer *buffer) { return; } + if (!buffer->modified) { + minibuffer_echo_timeout(4, "buffer already saved"); + return; + } + FILE *file = fopen(buffer->filename, "w"); if (file == NULL) { minibuffer_echo("failed to open file %s for writing: %s", buffer->filename, @@ -538,6 +542,7 @@ void buffer_to_file(struct buffer *buffer) { buffer->filename); fclose(file); + buffer->modified = false; undo_push_boundary(&buffer->undo, (struct undo_boundary){.save_point = true}); } @@ -574,15 +579,16 @@ int buffer_add_text(struct buffer *buffer, uint8_t *text, uint32_t nbytes) { moveh(buffer, cols_added); struct buffer_location final = buffer->dot; - if (lines_added > 0) { - undo_push_boundary(&buffer->undo, - (struct undo_boundary){.save_point = false}); - } undo_push_add( &buffer->undo, (struct undo_add){.begin = {.row = initial.line, .col = initial.col}, .end = {.row = final.line, .col = final.col}}); + if (lines_added > 0) { + undo_push_boundary(&buffer->undo, + (struct undo_boundary){.save_point = false}); + } + buffer->modified = true; return lines_added; } @@ -679,6 +685,7 @@ void buffer_undo(struct buffer *buffer) { } } } + undo_push_boundary(undo, (struct undo_boundary){.save_point = false}); free(records); undo_end(undo); diff --git a/src/command.c b/src/command.c index 55b5bb3..65543a0 100644 --- a/src/command.c +++ b/src/command.c @@ -2,6 +2,7 @@ #include "buffer.h" #include "buffers.h" #include "hash.h" +#include "hashmap.h" #include "minibuffer.h" #include @@ -9,37 +10,21 @@ #include #include -struct hashed_command { - uint32_t hash; - struct command command; -}; - struct commands command_registry_create(uint32_t capacity) { - return (struct commands){ - .commands = calloc(capacity, sizeof(struct hashed_command)), - .ncommands = 0, - .capacity = capacity, - }; + + struct commands cmds = {0}; + HASHMAP_INIT(&cmds.commands, capacity, hash_name); + return cmds; } void command_registry_destroy(struct commands *commands) { - free(commands->commands); - commands->ncommands = 0; - commands->capacity = 0; + HASHMAP_DESTROY(&commands->commands); } uint32_t register_command(struct commands *commands, struct command command) { - if (commands->ncommands == commands->capacity) { - commands->capacity *= 2; - commands->commands = realloc( - commands->commands, sizeof(struct hashed_command) * commands->capacity); - } - - uint32_t hash = hash_name(command.name); - commands->commands[commands->ncommands] = - (struct hashed_command){.command = command, .hash = hash}; - - ++commands->ncommands; + uint32_t hash = 0; + HASHMAP_INSERT(&commands->commands, struct command_entry, command.name, + command, hash); return hash; } @@ -52,19 +37,16 @@ void register_commands(struct commands *command_list, struct command *commands, struct command *lookup_command(struct commands *command_list, const char *name) { - uint32_t needle = hash_name(name); - return lookup_command_by_hash(command_list, needle); + HASHMAP_GET(&command_list->commands, struct command_entry, name, + struct command * command); + return command; } struct command *lookup_command_by_hash(struct commands *commands, uint32_t hash) { - for (uint32_t ci = 0; ci < commands->ncommands; ++ci) { - if (commands->commands[ci].hash == hash) { - return &commands->commands[ci].command; - } - } - - return NULL; + HASHMAP_GET_BY_HASH(&commands->commands, struct command_entry, hash, + struct command * command); + return command; } int32_t execute_command(struct command *command, struct commands *commands, diff --git a/src/command.h b/src/command.h index b151eb8..7ece486 100644 --- a/src/command.h +++ b/src/command.h @@ -4,6 +4,7 @@ /** @file command.h * Commands and command registries */ +#include "hashmap.h" #include struct buffer; @@ -78,10 +79,10 @@ struct command { /** * A command registry */ +HASHMAP_ENTRY_TYPE(command_entry, struct command); + struct commands { - struct hashed_command *commands; - uint32_t ncommands; - uint32_t capacity; + HASHMAP(struct command_entry) commands; }; /** diff --git a/src/hashmap.h b/src/hashmap.h new file mode 100644 index 0000000..405c193 --- /dev/null +++ b/src/hashmap.h @@ -0,0 +1,86 @@ +#ifndef _HASHMAP_H +#define _HASHMAP_H + +#include "vec.h" +#include + +#define HASHMAP_ENTRY_TYPE(name, entry) \ + struct name { \ + uint32_t key; \ + entry value; \ + } + +#define HASHMAP(entry) \ + struct { \ + VEC(entry) entries; \ + uint32_t (*hash_fn)(const char *); \ + } + +#define HASHMAP_INIT(map, initial_capacity, hasher) \ + VEC_INIT(&(map)->entries, initial_capacity) \ + (map)->hash_fn = hasher; + +#define HASHMAP_DESTROY(map) VEC_DESTROY(&(map)->entries) + +#define HASHMAP_INSERT(map, type, k, v, hash_var) \ + uint32_t key = (map)->hash_fn(k); \ + bool duplicate = false; \ + VEC_FOR_EACH(&(map)->entries, type *pair) { \ + if (pair->key == key) { \ + duplicate = true; \ + break; \ + } \ + } \ + if (!duplicate) { \ + VEC_PUSH(&(map)->entries, ((type){.key = key, .value = v})); \ + } \ + hash_var = key; + +#define HASHMAP_APPEND(map, type, k, var) \ + uint32_t key = (map)->hash_fn(k); \ + bool duplicate = false; \ + VEC_FOR_EACH(&(map)->entries, type *pair) { \ + if (pair->key == key) { \ + duplicate = true; \ + break; \ + } \ + } \ + type *v = NULL; \ + if (!duplicate) { \ + VEC_APPEND(&(map)->entries, v); \ + v->key = key; \ + } \ + var = v; + +#define HASHMAP_GET(map, type, k, var) \ + HASHMAP_GET_BY_HASH(map, type, (map)->hash_fn(k), var) + +#define HASHMAP_GET_BY_HASH(map, type, h, var) \ + type *res = NULL; \ + uint32_t needle = h; \ + VEC_FOR_EACH(&(map)->entries, type *pair) { \ + if (needle == pair->key) { \ + res = pair; \ + break; \ + } \ + } \ + var = res != NULL ? &(res->value) : NULL; + +#define HASHMAP_CONTAINS_KEY(map, key) \ + uint32_t needle = (map)->hash_fn(key); \ + bool exists = false; \ + VEC_FOR_EACH((map)->entries, struct pair *pair) { \ + if (needle == pair->key) { \ + exists = true; \ + break; \ + } \ + } \ + exists + +#define HASHMAP_FOR_EACH(map, var) VEC_FOR_EACH_INDEXED(&(map)->entries, var, i) + +#define HASHMAP_SIZE(map) VEC_SIZE(&(map)->entries) +#define HASHMAP_CAPACITY(map) VEC_CAPACITY(&(map)->entries) +#define HASHMAP_EMPTY(map) HASHMAP_SIZE == 0 + +#endif diff --git a/src/settings.c b/src/settings.c index 08e31d4..c00fd94 100644 --- a/src/settings.c +++ b/src/settings.c @@ -1,7 +1,9 @@ #include "settings.h" #include "command.h" #include "hash.h" +#include "hashmap.h" #include "minibuffer.h" +#include "vec.h" #include #include @@ -9,83 +11,55 @@ static struct settings g_settings = {0}; -void settings_resize(uint32_t new_capacity) { - if (new_capacity > g_settings.capacity) { - g_settings.settings = - realloc(g_settings.settings, sizeof(struct setting) * new_capacity); - } -} - void settings_init(uint32_t initial_capacity) { - settings_resize(initial_capacity); - g_settings.capacity = initial_capacity; - g_settings.nsettings = 0; + HASHMAP_INIT(&g_settings.settings, initial_capacity, hash_name); } void settings_destroy() { - for (uint32_t i = 0; i < g_settings.nsettings; ++i) { - struct setting *setting = &g_settings.settings[i]; + HASHMAP_FOR_EACH(&g_settings.settings, struct setting_entry * entry) { + struct setting *setting = &entry->value; if (setting->value.type == Setting_String) { free(setting->value.string_value); } } - free(g_settings.settings); - g_settings.settings = NULL; - g_settings.capacity = 0; - g_settings.nsettings = 0; + HASHMAP_DESTROY(&g_settings.settings); } void settings_register_setting(const char *path, struct setting_value default_value) { - if (g_settings.nsettings + 1 == g_settings.capacity) { - g_settings.capacity *= 2; - settings_resize(g_settings.capacity); + HASHMAP_APPEND(&g_settings.settings, struct setting_entry, path, + struct setting_entry * s); + + if (s != NULL) { + struct setting *new_setting = &s->value; + new_setting->value = default_value; + strncpy(new_setting->path, path, 128); + new_setting->path[127] = '\0'; } - - struct setting *s = &g_settings.settings[g_settings.nsettings]; - s->value = default_value; - s->hash = hash_name(path); - strncpy(s->path, path, 128); - s->path[127] = '\0'; - - ++g_settings.nsettings; } struct setting *settings_get(const char *path) { - uint32_t needle = hash_name(path); - - for (uint32_t i = 0; i < g_settings.nsettings; ++i) { - struct setting *setting = &g_settings.settings[i]; - if (setting->hash == needle) { - return setting; - } - } - - return NULL; + HASHMAP_GET(&g_settings.settings, struct setting_entry, path, + struct setting * s); + return s; } void settings_get_prefix(const char *prefix, struct setting **settings_out[], uint32_t *nsettings_out) { uint32_t capacity = 16; - struct setting **res = malloc(sizeof(struct setting *) * capacity); - uint32_t nsettings = 0; - for (uint32_t i = 0; i < g_settings.nsettings; ++i) { - struct setting *setting = &g_settings.settings[i]; + VEC(struct setting *) res; + VEC_INIT(&res, 16); + HASHMAP_FOR_EACH(&g_settings.settings, struct setting_entry * entry) { + struct setting *setting = &entry->value; if (strncmp(prefix, setting->path, strlen(prefix)) == 0) { - if (nsettings + 1 == capacity) { - capacity *= 2; - res = realloc(res, sizeof(struct setting *) * capacity); - } - - res[nsettings] = setting; - ++nsettings; + VEC_PUSH(&res, setting); } } - *nsettings_out = nsettings; - *settings_out = res; + *nsettings_out = VEC_SIZE(&res); + *settings_out = VEC_ENTRIES(&res); } void settings_set(const char *path, struct setting_value value) { diff --git a/src/settings.h b/src/settings.h index 8d6f1f2..a2387ed 100644 --- a/src/settings.h +++ b/src/settings.h @@ -1,4 +1,5 @@ #include "command.h" +#include "hashmap.h" #include #include @@ -48,25 +49,17 @@ struct setting { /** Path of the setting. */ char path[128]; - /** Hashed path that can be used for equality checks. */ - uint32_t hash; - /** Value of the setting. */ struct setting_value value; }; +HASHMAP_ENTRY_TYPE(setting_entry, struct setting); + /** * A collection of settings. */ struct settings { - /** Settings */ - struct setting *settings; - - /** Number of settings currently in collection. */ - uint32_t nsettings; - - /** Current capacity of collection. */ - uint32_t capacity; + HASHMAP(struct setting_entry) settings; }; /** diff --git a/src/undo.c b/src/undo.c index 6ebec12..2780557 100644 --- a/src/undo.c +++ b/src/undo.c @@ -1,72 +1,55 @@ #include "undo.h" #include "string.h" +#include "vec.h" #include #include void undo_init(struct undo_stack *undo, uint32_t initial_capacity) { undo->top = INVALID_TOP; - undo->nrecords = 0; undo->undo_in_progress = false; - - undo->records = calloc(initial_capacity, sizeof(struct undo_record)); - undo->capacity = initial_capacity; -} - -void grow_if_needed(struct undo_stack *undo, uint32_t needed_capacity) { - if (needed_capacity > undo->capacity) { - undo->capacity += undo->capacity + needed_capacity > undo->capacity * 2 - ? needed_capacity - : undo->capacity; - - undo->records = - realloc(undo->records, sizeof(struct undo_record) * undo->capacity); - } + VEC_INIT(&undo->records, initial_capacity); } void undo_clear(struct undo_stack *undo) { undo->top = INVALID_TOP; - undo->nrecords = 0; + VEC_CLEAR(&undo->records); } void undo_destroy(struct undo_stack *undo) { - for (uint32_t i = 0; i < undo->nrecords; ++i) { - struct undo_record *rec = &undo->records[i]; + VEC_FOR_EACH(&undo->records, struct undo_record * rec) { if (rec->type == Undo_Delete && rec->delete.data != NULL && rec->delete.nbytes > 0) { free(rec->delete.data); } } + undo_clear(undo); - undo->capacity = 0; - free(undo->records); - undo->records = NULL; + VEC_DESTROY(&undo->records); } uint32_t undo_push_boundary(struct undo_stack *undo, struct undo_boundary boundary) { - grow_if_needed(undo, undo->nrecords + 1); - undo->records[undo->nrecords].type = Undo_Boundary; - undo->records[undo->nrecords].boundary = boundary; - - if (!undo->undo_in_progress) { - undo->top = undo->nrecords; - } + VEC_APPEND(&undo->records, struct undo_record * rec); + rec->type = Undo_Boundary; + rec->boundary = boundary; // we can only have one save point if (boundary.save_point) { - for (uint32_t i = 0; i < undo->nrecords; ++i) { - if (undo->records[i].type && Undo_Boundary && - undo->records[i].boundary.save_point) { - undo->records[i].boundary.save_point = false; + VEC_FOR_EACH(&undo->records, struct undo_record * rec) { + if (rec->type && Undo_Boundary && rec->boundary.save_point) { + rec->boundary.save_point = false; } } } - ++undo->nrecords; - return undo->nrecords - 1; + if (!undo->undo_in_progress) { + undo->top = VEC_SIZE(&undo->records) - 1; + } + + return VEC_SIZE(&undo->records) - 1; } bool pos_equal(struct position *a, struct position *b) { @@ -74,39 +57,35 @@ bool pos_equal(struct position *a, struct position *b) { } uint32_t undo_push_add(struct undo_stack *undo, struct undo_add add) { - grow_if_needed(undo, undo->nrecords + 1); // "compress" - if (undo->nrecords > 0 && - undo->records[undo->nrecords - 1].type == Undo_Add && - pos_equal(&undo->records[undo->nrecords - 1].add.end, &add.begin)) { - undo->records[undo->nrecords - 1].add.end = add.end; - return undo->nrecords; + if (!VEC_EMPTY(&undo->records) && + VEC_BACK(&undo->records)->type == Undo_Add && + pos_equal(&VEC_BACK(&undo->records)->add.end, &add.begin)) { + VEC_BACK(&undo->records)->add.end = add.end; + } else { + VEC_APPEND(&undo->records, struct undo_record * rec); + rec->type = Undo_Add; + rec->add = add; } - undo->records[undo->nrecords].type = Undo_Add; - undo->records[undo->nrecords].add = add; - if (!undo->undo_in_progress) { - undo->top = undo->nrecords; + undo->top = VEC_SIZE(&undo->records) - 1; } - ++undo->nrecords; - return undo->nrecords - 1; + return VEC_SIZE(&undo->records) - 1; } uint32_t undo_push_delete(struct undo_stack *undo, struct undo_delete delete) { - grow_if_needed(undo, undo->nrecords + 1); - - undo->records[undo->nrecords].type = Undo_Delete; - undo->records[undo->nrecords].delete = delete; + VEC_APPEND(&undo->records, struct undo_record * rec); + rec->type = Undo_Delete; + rec->delete = delete; if (!undo->undo_in_progress) { - undo->top = undo->nrecords; + undo->top = VEC_SIZE(&undo->records) - 1; } - ++undo->nrecords; - return undo->nrecords - 1; + return VEC_SIZE(&undo->records) - 1; } void undo_begin(struct undo_stack *undo) { undo->undo_in_progress = true; } @@ -116,27 +95,30 @@ void undo_next(struct undo_stack *undo, struct undo_record **records_out, *nrecords_out = 0; *records_out = NULL; - if (undo->nrecords == 0) { + if (VEC_EMPTY(&undo->records)) { return; } if (undo->top == INVALID_TOP) { // reset back to the top (redo) - undo->top = undo->nrecords - 1; + undo->top = VEC_SIZE(&undo->records) - 1; } uint32_t nrecords = 1; - struct undo_record *current = &undo->records[undo->top]; + struct undo_record *current = &VEC_ENTRIES(&undo->records)[undo->top]; + + // skip any leading boundaries while (undo->top > 0 && current->type == Undo_Boundary) { ++nrecords; --undo->top; - current = &undo->records[undo->top]; + current = &VEC_ENTRIES(&undo->records)[undo->top]; } + // find the next boundary while (undo->top > 0 && current->type != Undo_Boundary) { ++nrecords; --undo->top; - current = &undo->records[undo->top]; + current = &VEC_ENTRIES(&undo->records)[undo->top]; } if (nrecords > 0) { @@ -148,7 +130,7 @@ void undo_next(struct undo_stack *undo, struct undo_record **records_out, // copy backwards for (uint32_t reci = undo->top + nrecords, outi = 0; reci > undo->top; --reci, ++outi) { - dest[outi] = undo->records[reci - 1]; + dest[outi] = VEC_ENTRIES(&undo->records)[reci - 1]; } } @@ -161,7 +143,7 @@ void undo_next(struct undo_stack *undo, struct undo_record **records_out, void undo_end(struct undo_stack *undo) { undo->undo_in_progress = false; } -uint32_t undo_size(struct undo_stack *undo) { return undo->nrecords; } +uint32_t undo_size(struct undo_stack *undo) { return VEC_SIZE(&undo->records); } uint32_t undo_current_position(struct undo_stack *undo) { return undo->top; } size_t rec_to_str(struct undo_record *rec, char *buffer, size_t n) { @@ -187,8 +169,7 @@ const char *undo_dump(struct undo_stack *undo) { pos[0] = '\0'; char rec_buf[256]; - for (uint32_t reci = 0; reci < undo->nrecords && left > 0; ++reci) { - struct undo_record *rec = &undo->records[reci]; + VEC_FOR_EACH_INDEXED(&undo->records, struct undo_record * rec, reci) { rec_to_str(rec, rec_buf, 256); uint32_t written = snprintf(pos, left, "%d: [%s]%s\n", reci, rec_buf, reci == undo->top ? " <- top" : ""); diff --git a/src/undo.h b/src/undo.h index 42022c5..1ce3a8a 100644 --- a/src/undo.h +++ b/src/undo.h @@ -1,3 +1,4 @@ +#include "vec.h" #include #include @@ -40,10 +41,8 @@ struct undo_record { #define INVALID_TOP -1 struct undo_stack { - struct undo_record *records; - uint32_t nrecords; + VEC(struct undo_record) records; uint32_t top; - uint32_t capacity; bool undo_in_progress; }; diff --git a/src/vec.h b/src/vec.h new file mode 100644 index 0000000..2d5bd32 --- /dev/null +++ b/src/vec.h @@ -0,0 +1,61 @@ +#ifndef _VEC_H +#define _VEC_H + +#define VEC(entry) \ + struct { \ + entry *entries; \ + uint32_t nentries; \ + uint32_t capacity; \ + } + +#define VEC_INIT(vec, initial_capacity) \ + (vec)->entries = malloc(sizeof((vec)->entries[0]) * initial_capacity); \ + (vec)->capacity = initial_capacity; \ + (vec)->nentries = 0; + +#define VEC_DESTROY(vec) \ + free((vec)->entries); \ + (vec)->entries = NULL; \ + (vec)->capacity = 0; \ + (vec)->nentries = 0; + +#define VEC_GROW(vec, new_size) \ + if (new_size > (vec)->capacity) { \ + (vec)->capacity = new_size; \ + (vec)->entries = realloc((vec)->entries, \ + (sizeof((vec)->entries[0]) * (vec)->capacity)); \ + } + +#define VEC_PUSH(vec, entry) \ + if ((vec)->nentries + 1 >= (vec)->capacity) { \ + VEC_GROW(vec, (vec)->capacity * 2); \ + } \ + \ + (vec)->entries[(vec)->nentries] = entry; \ + ++(vec)->nentries; + +#define VEC_APPEND(vec, var) \ + if ((vec)->nentries + 1 >= (vec)->capacity) { \ + VEC_GROW(vec, (vec)->capacity * 2); \ + } \ + \ + var = &((vec)->entries[(vec)->nentries]); \ + ++(vec)->nentries; + +#define VEC_FOR_EACH(vec, var) VEC_FOR_EACH_INDEXED(vec, var, i) + +#define VEC_FOR_EACH_INDEXED(vec, var, idx) \ + for (uint32_t keep = 1, idx = 0, size = (vec)->nentries; \ + keep && idx != size; keep = !keep, idx++) \ + for (var = (vec)->entries + idx; keep; keep = !keep) + +#define VEC_SIZE(vec) (vec)->nentries +#define VEC_CAPACITY(vec) (vec)->capacity +#define VEC_ENTRIES(vec) (vec)->entries +#define VEC_EMPTY(vec) ((vec)->nentries == 0) + +#define VEC_CLEAR(vec) (vec)->nentries = 0 +#define VEC_BACK(vec) \ + ((vec)->nentries > 0 ? &((vec)->entries[(vec)->nentries - 1]) : NULL) + +#endif -- cgit v1.2.3