gap_buffer.h (7168B)
1 /* 2 * This file is part of the Lumidify ToolKit (LTK) 3 * Copyright (c) 2020 lumidify <nobody@lumidify.org> 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a copy 6 * of this software and associated documentation files (the "Software"), to deal 7 * in the Software without restriction, including without limitation the rights 8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9 * copies of the Software, and to permit persons to whom the Software is 10 * furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be included in all 13 * copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 21 * SOFTWARE. 22 */ 23 24 #ifndef _LTK_GAP_BUFFER_H_ 25 #define _LTK_GAP_BUFFER_H_ 26 27 #include <stdio.h> 28 #include <stdlib.h> 29 30 #define LTK_GAP_BUFFER_INIT_DECL(name, type) \ 31 struct ltk_gap_buffer_##name { \ 32 type *buf; \ 33 size_t buf_size; \ 34 size_t gap_left; \ 35 size_t gap_size; \ 36 size_t len; \ 37 }; \ 38 \ 39 struct ltk_gap_buffer_##name * ltk_gap_buffer_create_##name(void); \ 40 struct ltk_gap_buffer_##name * \ 41 ltk_gap_buffer_create_from_data_##name(type *data, size_t len); \ 42 type ltk_gap_buffer_get_##name(struct ltk_gap_buffer_##name *gb, size_t index); \ 43 void ltk_gap_buffer_set_##name( \ 44 struct ltk_gap_buffer_##name *gb, size_t index, type data); \ 45 void ltk_gap_buffer_resize_gap_##name( \ 46 struct ltk_gap_buffer_##name *gb, int len); \ 47 void ltk_gap_buffer_insert_##name(struct ltk_gap_buffer_##name *gb, \ 48 type *new, size_t start, size_t len); \ 49 void ltk_gap_buffer_insert_single_##name( \ 50 struct ltk_gap_buffer_##name *gb, type new); \ 51 void ltk_gap_buffer_move_gap_##name( \ 52 struct ltk_gap_buffer_##name *gb, size_t pos); \ 53 void ltk_gap_buffer_clear_##name(struct ltk_gap_buffer_##name *gb); \ 54 void ltk_gap_buffer_destroy_##name(struct ltk_gap_buffer_##name *gb); 55 56 #define LTK_GAP_BUFFER_INIT_IMPL(name, type) \ 57 struct ltk_gap_buffer_##name * \ 58 ltk_gap_buffer_create_##name(void) { \ 59 struct ltk_gap_buffer_##name *gb = \ 60 malloc(sizeof(struct ltk_gap_buffer_##name)); \ 61 if (!gb) \ 62 goto error; \ 63 gb->buf = malloc(8 * sizeof(type)); \ 64 if (!gb->buf) \ 65 goto error; \ 66 gb->buf_size = 8; \ 67 gb->gap_left = 0; \ 68 gb->gap_size = 8; \ 69 gb->len = 0; \ 70 return gb; \ 71 error: \ 72 (void)fprintf(stderr, "Out of memory while trying to" \ 73 "allocate gap buffer\n"); \ 74 exit(1); \ 75 } \ 76 \ 77 struct ltk_gap_buffer_##name * \ 78 ltk_gap_buffer_create_from_data_##name(type *data, size_t len) { \ 79 struct ltk_gap_buffer_##name *gb = \ 80 malloc(sizeof(struct ltk_gap_buffer_##name)); \ 81 if (!gb) { \ 82 (void)fprintf(stderr, "Out of memory while trying to" \ 83 "allocate gap buffer\n"); \ 84 exit(1); \ 85 } \ 86 gb->buf = data; \ 87 gb->buf_size = len; \ 88 gb->len = len; \ 89 gb->gap_left = 0; \ 90 gb->gap_size = 0; \ 91 return gb; \ 92 } \ 93 \ 94 type \ 95 ltk_gap_buffer_get_##name(struct ltk_gap_buffer_##name *gb, size_t index) { \ 96 if (index < gb->gap_left) \ 97 return gb->buf[index]; \ 98 else if (index + gb->gap_size < gb->len) \ 99 return gb->buf[index + gb->gap_size]; \ 100 (void)fprintf(stderr, "Gap buffer index out of bounds\n"); \ 101 exit(1); \ 102 } \ 103 \ 104 void \ 105 ltk_gap_buffer_set_##name( \ 106 struct ltk_gap_buffer_##name *gb, size_t index, type data) { \ 107 if (index < gb->gap_left) \ 108 gb->buf[index] = data; \ 109 else if (index + gb->gap_size < gb->len) \ 110 gb->buf[index + gb->gap_size] = data; \ 111 (void)fprintf(stderr, "Gap buffer index out of bounds\n"); \ 112 exit(1); \ 113 } \ 114 \ 115 /* FIXME: \ 116 a) use memmove() \ 117 b) properly calculate the most efficient larger size \ 118 */ \ 119 void \ 120 ltk_gap_buffer_resize_gap_##name( \ 121 struct ltk_gap_buffer_##name *gb, int len) { \ 122 /* FIXME: Should this use realloc? It's usually more efficient, but \ 123 in this case, I would still need to copy the part after the gap \ 124 manually, so it could potentially be copied twice, which really \ 125 wouldn't be good. Maybe use realloc if only a small part is after \ 126 the gap and just regular malloc otherwise? */ \ 127 int new_size = gb->buf_size - gb->gap_size + len; \ 128 type *new = malloc(new_size * sizeof(type)); \ 129 if (!new) { \ 130 (void)fprintf(stderr, "Out of memory while trying to" \ 131 "resize gap buffer\n"); \ 132 exit(1); \ 133 } \ 134 for (int i = 0; i < gb->gap_left; i++) { \ 135 new[i] = gb->buf[i]; \ 136 } \ 137 for (int i = gb->gap_left + gb->gap_size; i < gb->buf_size; i++) { \ 138 new[i - gb->gap_size + len] = gb->buf[i]; \ 139 } \ 140 free(gb->buf); \ 141 gb->buf = new; \ 142 } \ 143 \ 144 void \ 145 ltk_gap_buffer_insert_##name(struct ltk_gap_buffer_##name *gb, \ 146 type *new, size_t start, size_t len) { \ 147 if (gb->gap_size < len) \ 148 ltk_gap_buffer_resize_gap_##name(gb, len + 8); \ 149 for (int i = 0; i < len; i++) { \ 150 gb->buf[gb->gap_left + i] = new[start + i]; \ 151 } \ 152 gb->gap_left = gb->gap_left + len; \ 153 gb->gap_size -= len; \ 154 gb->len += len; \ 155 } \ 156 \ 157 void \ 158 ltk_gap_buffer_insert_single_##name( \ 159 struct ltk_gap_buffer_##name *gb, type new) { \ 160 ltk_gap_buffer_insert_##name(gb, &new, 0, 1); \ 161 } \ 162 \ 163 void \ 164 ltk_gap_buffer_move_gap_##name( \ 165 struct ltk_gap_buffer_##name *gb, size_t pos) { \ 166 if (pos == gb->gap_left) \ 167 return; \ 168 if (pos < 0 || pos > gb->buf_size - gb->gap_size) { \ 169 (void)fprintf(stderr, "Index out of range while moving" \ 170 "gap buffer gap\n"); \ 171 return; \ 172 } \ 173 if (pos >= gb->gap_left) { \ 174 for (int i = gb->gap_left; i < pos; i++) { \ 175 gb->buf[i] = gb->buf[i + gb->gap_size]; \ 176 } \ 177 } else { \ 178 for (int i = gb->gap_left - 1; i >= pos; i--) { \ 179 gb->buf[i + gb->gap_size] = gb->buf[i]; \ 180 } \ 181 } \ 182 gb->gap_left = pos; \ 183 } \ 184 \ 185 void ltk_gap_buffer_clear_##name(struct ltk_gap_buffer_##name *gb) { \ 186 gb->gap_left = 0; \ 187 gb->len = 0; \ 188 gb->gap_size = gb->buf_size; \ 189 } \ 190 \ 191 void \ 192 ltk_gap_buffer_destroy_##name(struct ltk_gap_buffer_##name *gb) { \ 193 free(gb->buf); \ 194 free(gb); \ 195 } 196 197 #endif /* _LTK_GAP_BUFFER_H_ */