From 41c33e59e85909989009e96370403abf319008ad Mon Sep 17 00:00:00 2001 From: Leo Tenenbaum Date: Mon, 21 Dec 2020 13:02:30 -0500 Subject: more undo --- arr.c | 214 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ buffer.c | 152 +++++++++++++++++++++++++++++---------------- main.c | 10 +++ 3 files changed, 321 insertions(+), 55 deletions(-) create mode 100644 arr.c diff --git a/arr.c b/arr.c new file mode 100644 index 0000000..b9b3387 --- /dev/null +++ b/arr.c @@ -0,0 +1,214 @@ +#ifndef ARR_C_ +#define ARR_C_ +/* +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or +distribute this software, either in source code form or as a compiled +binary, for any purpose, commercial or non-commercial, and by any +means. +In jurisdictions that recognize copyright laws, the author or authors +of this software dedicate any and all copyright interest in the +software to the public domain. We make this dedication for the benefit +of the public at large and to the detriment of our heirs and +successors. We intend this dedication to be an overt act of +relinquishment in perpetuity of all present and future rights to this +software under copyright law. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +OTHER DEALINGS IN THE SOFTWARE. +For more information, please refer to +*/ + +// functions in this file suffixed with _ are not meant to be used outside here, unless you +// know what you're doing + +// IMPORTANT NOTE: If you are using this with structures containing `long double`s, do +// #define ARR_LONG_DOUBLE +// before including this file + +#include +#if __STDC_VERSION__ >= 201112L +typedef max_align_t ArrMaxAlign; +#else +typedef union { + long num; + void *ptr; + void (*fnptr)(void); +#ifdef ARR_LONG_DOUBLE + long +#endif + double flt; +} ArrMaxAlign; +#endif +#if __STDC_VERSION__ < 199901L && !defined inline +#define inline +#endif + + +typedef struct { + u32 len; + u32 cap; + ArrMaxAlign data[]; +} ArrHeader; + +// watch out! do not call this function if arr is NULL. +static inline ArrHeader *arr_hdr_(void *arr) { + return (ArrHeader *)((char *)arr - offsetof(ArrHeader, data)); +} + +static inline u32 arr_len(void *arr) { + return arr ? arr_hdr_(arr)->len : 0; +} + +static inline unsigned arr_lenu(void *arr) { + return (unsigned)arr_len(arr); +} + +// grow array to fit one more member +static void *arr_grow1_(void *arr, size_t member_size) { + if (arr) { + ArrHeader *hdr = arr_hdr_(arr); + if (hdr->len >= hdr->cap) { + u32 new_capacity = hdr->cap * 2; + ArrHeader *old_hdr = hdr; + hdr = (ArrHeader *)realloc(old_hdr, sizeof(ArrHeader) + new_capacity * member_size); + if (hdr) { + hdr->cap = new_capacity; + } else { + free(old_hdr); + return NULL; + } + } + return hdr->data; + } else { + // create a new array + u32 initial_capacity = 2; // allocate enough space for two members + ArrHeader *ret = (ArrHeader *)calloc(1, sizeof(ArrHeader) + initial_capacity * member_size); + if (ret) { + ret->cap = initial_capacity; + return ret->data; + } else { + return NULL; + } + } +} + +static inline void *arr_add_ptr_(void **arr, size_t member_size) { + u8 *ret; + *arr = arr_grow1_(*arr, member_size); + if (*arr) { + ret = (u8 *)*arr + member_size * (arr_hdr_(*arr)->len++); + memset(ret, 0, member_size); + } else { + ret = NULL; + } + return ret; +} + +#if 0 +// NOT TESTED +static inline void arr_set_len_(void **arr, size_t member_size, size_t n) { + if (n >= U32_MAX-1) { + // too big; free arr. + if (*arr) free(arr_hdr_(*arr)); + *arr = NULL; + } + + if (!*arr) { + // create a new array with capacity n+1 + ArrHeader *hdr = calloc(1, sizeof(ArrHeader) + (n+1) * member_size); + if (hdr) { + hdr->cap = (u32)n+1; + hdr->len = (u32)n; + *arr = hdr->data; + } + } else { + // increase capacity of array + ArrHeader *hdr = arr_hdr_(*arr); + u32 curr_cap = hdr->cap; + if (n > curr_cap) { + ArrHeader *old_hdr = hdr; + while (n > curr_cap) { + if (curr_cap < U32_MAX/2) + curr_cap *= 2; + else + curr_cap = U32_MAX; + } + hdr = realloc(hdr, sizeof(ArrHeader) + curr_cap * member_size); + if (hdr) { + hdr->cap = curr_cap; + } else { + // growing failed + free(old_hdr); + *arr = NULL; + return; + } + } + if (n > hdr->len) { + // zero new elements + memset((char *)hdr->data + hdr->len, 0, (n - hdr->len) * member_size); + } + hdr->len = (u32)n; + } +} +#define arr_set_len(a, n) arr_set_len_((void **)&a, sizeof *(a), n) +#endif + +#ifdef __cplusplus +#define arr_cast_typeof(a) (decltype(a)) +#elif defined __GNUC__ +#define arr_cast_typeof(a) (__typeof__(a)) +#else +#define arr_cast_typeof(a) +#endif + +// if the array is not NULL, free it and set it to NULL +#define arr_free(a) do { if (a) { free(arr_hdr_(a)); (a) = NULL; } } while (0) +// add an item to the array - if allocation fails, the array will be freed and set to NULL. +// (how this works: if we can successfully grow the array, increase the length and add the item.) +#define arr_add(a, x) do { if (((a) = arr_cast_typeof(a) arr_grow1_((a), sizeof *(a)))) ((a)[arr_hdr_(a)->len++] = (x)); } while (0) +// like arr_add, but instead of passing it the value, it returns a pointer to the value. returns NULL if allocation failed. +// the added item will be zero-initialized. +#define arr_addp(a) arr_cast_typeof(a) arr_add_ptr_((void **)&(a), sizeof *(a)) +// set the length of `a` to `n`, increasing the capacity if necessary. +// the newly-added elements are zero-initialized. +#define arr_qsort(a, cmp) qsort((a), arr_len(a), sizeof *(a), (cmp)) +#define arr_remove_last(a) do { assert(a); if (--arr_hdr_(a)->len == 0) arr_free(a); } while (0) +#define arr_pop_last(a) ((a)[--arr_hdr_(a)->len]) +#define arr_size_in_bytes(a) (arr_len(a) * sizeof *(a)) +#define arr_lastp(a) ((a) ? &(a)[arr_len(a)-1] : NULL) +#define arr_shrink(a, n) ((void)((a) && (arr_hdr_(a)->len -= (n)))) +#define arr_foreach_backwards(a, var) for (var = arr_lastp(a); var; var = var == (a) ? NULL : var-1) +#define arr_reverse(a, type) do { \ + u64 _i, _len = arr_len(a); \ + for (_i = 0; 2*_i < _len; ++_i) { \ + type *_x = &(a)[_i]; \ + type *_y = &(a)[_len-1-_i]; \ + type _tmp; \ + _tmp = *_x; \ + *_x = *_y; \ + *_y = _tmp; \ + } \ + } while (0) + +static void arr_test(void) { + u32 *arr = NULL; + u32 i; + assert(arr_len(arr) == 0); + for (i = 0; i < 10000; ++i) { + arr_add(arr, i*i); + } + assert(arr_len(arr) == 10000); + arr_remove_last(arr); + assert(arr_len(arr) == 9999); + for (i = 0; i < arr_len(arr); ++i) + assert(arr[i] == i*i); + while (arr_len(arr)) + arr_remove_last(arr); + assert(arr_len(arr) == 0); +} +#endif // ARR_C_ diff --git a/buffer.c b/buffer.c index 39a25a5..7ede69d 100644 --- a/buffer.c +++ b/buffer.c @@ -4,6 +4,7 @@ #include "util.c" #include "text.h" #include "string32.c" +#include "arr.c" // a position in the buffer typedef struct { @@ -19,16 +20,15 @@ typedef struct { typedef enum { BUFFER_EDIT_DELETE_TEXT, // text = deleted text, text_len = length of text deleted, pos = where text was deleted (first character) - BUFFER_EDIT_INSERT_TEXT // text unused, text_len = length of text inserted, pos = where text was inserted (first character) + BUFFER_EDIT_INSERT_TEXT // text = NULL, text_len = length of text inserted, pos = where text was inserted (first character) // (we don't need to know what text was inserted for BUFFER_EDIT_INSERT_TEXT, since it'll be right there) } BufferEditType; typedef struct BufferEdit { - struct BufferEdit *next; BufferEditType type; BufferPos pos; - u32 text_len; - char32_t text[]; + size_t text_len; + char32_t *text; } BufferEdit; typedef struct { @@ -42,8 +42,8 @@ typedef struct { u32 lines_capacity; Line *lines; char error[128]; - BufferEdit *undo_history; - BufferEdit *redo_history; + BufferEdit *undo_history; // dynamic array of undo history + BufferEdit *redo_history; // dynamic array of redo history } TextBuffer; @@ -91,15 +91,15 @@ static void buffer_out_of_mem(TextBuffer *buffer) { } // add this edit to the undo history -static void buffer_append_edit(TextBuffer *buffer, BufferEdit *edit) { - edit->next = buffer->undo_history; - buffer->undo_history = edit; +static void buffer_append_edit(TextBuffer *buffer, BufferEdit const *edit) { + arr_add(buffer->undo_history, *edit); + if (!buffer->undo_history) buffer_out_of_mem(buffer); } // add this edit to the redo history -static void buffer_append_redo(TextBuffer *buffer, BufferEdit *edit) { - edit->next = buffer->redo_history; - buffer->redo_history = edit; +static void buffer_append_redo(TextBuffer *buffer, BufferEdit const *edit) { + arr_add(buffer->redo_history, *edit); + if (!buffer->redo_history) buffer_out_of_mem(buffer); } @@ -130,12 +130,12 @@ static bool buffer_pos_valid(TextBuffer *buffer, BufferPos p) { // get some number of characters of text from the given position in the buffer. -static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t *text, u32 nchars) { +static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t *text, size_t nchars) { if (!buffer_pos_valid(buffer, pos)) { return false; } char32_t *p = text; - u32 chars_left = nchars; + size_t chars_left = nchars; Line *line = &buffer->lines[pos.line], *end = buffer->lines + buffer->nlines; u32 index = pos.index; while (chars_left) { @@ -154,7 +154,7 @@ static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t ++line; if (chars_left && line == end) { // reached end of file before getting full text... this isn't good - buffer_seterr(buffer, "Failed to fetch " U32_FMT " characters at " U32_FMT ":" U32_FMT ".", nchars, pos.line+1, pos.index+1); + buffer_seterr(buffer, "Failed to fetch %zu characters at " U32_FMT ":" U32_FMT ".", nchars, pos.line+1, pos.index+1); return false; } } @@ -163,32 +163,44 @@ static Status buffer_get_text_at_pos(TextBuffer *buffer, BufferPos pos, char32_t // functions for creating buffer edits: // call these before you make an edit to create an undo event -static WarnUnusedResult BufferEdit *buffer_create_edit_delete_text(TextBuffer *buffer, BufferPos start, u32 len) { - BufferEdit *e = buffer_calloc(buffer, 1, sizeof *e + len * sizeof *e->text); - if (e) { - e->type = BUFFER_EDIT_DELETE_TEXT; - e->pos = start; - e->text_len = len; - if (!buffer_get_text_at_pos(buffer, start, e->text, len)) { - free(e); - e = NULL; +static Status buffer_create_edit_delete_text(TextBuffer *buffer, BufferEdit *edit, BufferPos start, size_t len) { + edit->text = calloc(1, len * sizeof *edit->text); + if (edit->text) { + edit->type = BUFFER_EDIT_DELETE_TEXT; + edit->pos = start; + edit->text_len = len; + if (!buffer_get_text_at_pos(buffer, start, edit->text, len)) { + free(edit->text); + return false; } + return true; + } else { + return false; } - return e; } -static WarnUnusedResult BufferEdit *buffer_create_edit_insert_text(TextBuffer *buffer, BufferPos start, u32 len) { - if (!buffer_pos_valid(buffer, start)) return NULL; - BufferEdit *e = buffer_calloc(buffer, 1, sizeof *e); - if (e) { - e->type = BUFFER_EDIT_INSERT_TEXT; - e->pos = start; - e->text_len = len; - } - return e; +static Status buffer_create_edit_insert_text(TextBuffer *buffer, BufferEdit *edit, BufferPos start, size_t len) { + if (!buffer_pos_valid(buffer, start)) return false; + edit->type = BUFFER_EDIT_INSERT_TEXT; + edit->pos = start; + edit->text_len = len; + edit->text = NULL; + return true; } +static void buffer_edit_delete_text(TextBuffer *buffer, BufferPos start, size_t len) { + BufferEdit edit = {0}; + if (buffer_create_edit_delete_text(buffer, &edit, start, len)) { + buffer_append_edit(buffer, &edit); + } +} +static void buffer_edit_insert_text(TextBuffer *buffer, BufferPos start, size_t len) { + BufferEdit edit = {0}; + if (buffer_create_edit_insert_text(buffer, &edit, start, len)) { + buffer_append_edit(buffer, &edit); + } +} // grow capacity of line to at least minimum_capacity // returns true if allocation was succesful @@ -251,6 +263,9 @@ void buffer_free(TextBuffer *buffer) { } free(lines); + arr_free(buffer->undo_history); + arr_free(buffer->redo_history); + // zero buffer, except for error char error[sizeof buffer->error]; memcpy(error, buffer->error, sizeof error); @@ -913,6 +928,8 @@ static void buffer_insert_lines(TextBuffer *buffer, u32 where, u32 number) { // inserts the given text, returning the position of the end of the text BufferPos buffer_insert_text_at_pos(TextBuffer *buffer, BufferPos pos, String32 str) { + buffer_edit_insert_text(buffer, pos, str.len); + u32 line_idx = pos.line; u32 index = pos.index; Line *line = &buffer->lines[line_idx]; @@ -1012,6 +1029,11 @@ void buffer_delete_lines(TextBuffer *buffer, u32 first_line_idx, u32 nlines) { } void buffer_delete_chars_at_pos(TextBuffer *buffer, BufferPos pos, i64 nchars) { + assert(nchars >= 0); + if (nchars <= 0) return; + + buffer_edit_delete_text(buffer, pos, (size_t)nchars); + u32 line_idx = pos.line; u32 index = pos.index; Line *line = &buffer->lines[line_idx], *lines_end = &buffer->lines[buffer->nlines]; @@ -1099,31 +1121,51 @@ void buffer_backspace_words_at_cursor(TextBuffer *buffer, i64 nwords) { buffer_backspace_words_at_pos(buffer, &buffer->cursor_pos, nwords); } +// returns the inverse edit +static Status buffer_undo_edit(TextBuffer *buffer, BufferEdit const *edit, BufferEdit *inverse) { + switch (edit->type) { + case BUFFER_EDIT_INSERT_TEXT: + // the inverse edit is the deletion of this text + if (!buffer_create_edit_delete_text(buffer, inverse, edit->pos, edit->text_len)) + return false; + // delete the text + buffer_delete_chars_at_pos(buffer, edit->pos, (i64)edit->text_len); + break; + case BUFFER_EDIT_DELETE_TEXT: { + // the inverse edit is the insertion of this text + if (!buffer_create_edit_insert_text(buffer, inverse, edit->pos, edit->text_len)) + return false; + // insert the text + String32 str = {edit->text_len, edit->text}; + buffer_insert_text_at_pos(buffer, edit->pos, str); + } break; + } + + return true; +} + void buffer_undo(TextBuffer *buffer, i64 ntimes) { for (i64 i = 0; i < ntimes; ++i) { - BufferEdit *edit = buffer->undo_history; - BufferEdit *inverse = NULL; - - switch (edit->type) { - case BUFFER_EDIT_INSERT_TEXT: - // the inverse edit is the deletion of this text - inverse = buffer_create_edit_delete_text(buffer, edit->pos, edit->text_len); - // delete the text - buffer_delete_chars_at_pos(buffer, edit->pos, edit->text_len); - break; - case BUFFER_EDIT_DELETE_TEXT: { - // the inverse edit is the insertion of this text - inverse = buffer_create_edit_insert_text(buffer, edit->pos, edit->text_len); - // insert the text - String32 str = {edit->text_len, edit->text}; - buffer_insert_text_at_pos(buffer, edit->pos, str); - } break; + BufferEdit *edit = arr_lastp(buffer->undo_history); + if (edit) { + BufferEdit inverse = {0}; + if (buffer_undo_edit(buffer, edit, &inverse)) { + buffer_append_redo(buffer, &inverse); + arr_remove_last(buffer->undo_history); + } } + } +} - if (inverse) { - buffer_append_redo(buffer, inverse); +void buffer_redo(TextBuffer *buffer, i64 ntimes) { + for (i64 i = 0; i < ntimes; ++i) { + BufferEdit *edit = arr_lastp(buffer->redo_history); + if (edit) { + BufferEdit inverse = {0}; + if (buffer_undo_edit(buffer, edit, &inverse)) { + buffer_append_edit(buffer, &inverse); + arr_remove_last(buffer->redo_history); + } } - - free(edit); } } diff --git a/main.c b/main.c index 93bac8a..31dd849 100644 --- a/main.c +++ b/main.c @@ -78,6 +78,7 @@ int main(void) { SDL_Event event; Uint8 const *keyboard_state = SDL_GetKeyboardState(NULL); bool ctrl = keyboard_state[SDL_SCANCODE_LCTRL] || keyboard_state[SDL_SCANCODE_RCTRL]; + bool shift = keyboard_state[SDL_SCANCODE_LSHIFT] || keyboard_state[SDL_SCANCODE_RSHIFT]; while (SDL_PollEvent(&event)) { // @TODO: make a function to handle text buffer events @@ -142,6 +143,15 @@ int main(void) { } } break; + case SDLK_z: + if (ctrl) { + if (shift) { + buffer_undo(&text_buffer, 1); + } else { + buffer_redo(&text_buffer, 1); + } + } + break; } } break; case SDL_TEXTINPUT: { -- cgit v1.2.3