array.h (9841B)
1 /* 2 * Copyright (c) 2020-2024 lumidify <nobody@lumidify.org> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a copy 5 * of this software and associated documentation files (the "Software"), to deal 6 * in the Software without restriction, including without limitation the rights 7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 * copies of the Software, and to permit persons to whom the Software is 9 * furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included in all 12 * copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20 * SOFTWARE. 21 */ 22 23 #ifndef LTK_ARRAY_H 24 #define LTK_ARRAY_H 25 26 #include <stdio.h> 27 #include <stdlib.h> 28 #include <string.h> 29 30 #include "util.h" 31 #include "memory.h" 32 33 /* FIXME: make this work on more compilers? */ 34 #if (defined(__GNUC__) || defined(__clang__)) 35 #define LTK_UNUSED_FUNC __attribute__((unused)) 36 #else 37 #define LTK_UNUSED_FUNC 38 #endif 39 40 /* FIXME: add accesser macros; also add init function to not allocate array itself but initialize given pointer */ 41 /* FIXME: separate struct definition and forward-declaration for header files */ 42 43 #define LTK_ARRAY_INIT_STRUCT_DECL_BASE(name, type, storage) \ 44 typedef struct { \ 45 type *buf; \ 46 size_t buf_size; \ 47 size_t len; \ 48 } ltk_array_##name; 49 50 #define LTK_ARRAY_INIT_FUNC_DECL_BASE(name, type, storage) \ 51 LTK_UNUSED_FUNC storage ltk_array_##name *ltk_array_create_##name(size_t initial_capacity); \ 52 LTK_UNUSED_FUNC storage type ltk_array_pop_##name(ltk_array_##name *ar); \ 53 LTK_UNUSED_FUNC storage size_t ltk_array_remove_if_##name( \ 54 ltk_array_##name *ar, int (*callback)(type *, void *), void *data \ 55 ); \ 56 LTK_UNUSED_FUNC storage void ltk_array_prepare_gap_##name(ltk_array_##name *ar, size_t index, size_t len); \ 57 LTK_UNUSED_FUNC storage void ltk_array_insert_##name(ltk_array_##name *ar, size_t index, type *elem, size_t len); \ 58 LTK_UNUSED_FUNC storage void ltk_array_resize_##name(ltk_array_##name *ar, size_t size); \ 59 LTK_UNUSED_FUNC storage void ltk_array_destroy_##name(ltk_array_##name *ar); \ 60 LTK_UNUSED_FUNC storage void ltk_array_clear_##name(ltk_array_##name *ar); \ 61 LTK_UNUSED_FUNC storage void ltk_array_append_##name(ltk_array_##name *ar, type elem); \ 62 LTK_UNUSED_FUNC storage void ltk_array_destroy_deep_##name(ltk_array_##name *ar, void (*destroy_func)(type)); \ 63 LTK_UNUSED_FUNC storage type ltk_array_get_safe_##name(ltk_array_##name *ar, size_t index); \ 64 LTK_UNUSED_FUNC storage void ltk_array_set_safe_##name(ltk_array_##name *ar, size_t index, type e); 65 66 #define LTK_ARRAY_INIT_IMPL_BASE(name, type, storage) \ 67 LTK_UNUSED_FUNC storage ltk_array_##name * \ 68 ltk_array_create_##name(size_t initial_capacity) { \ 69 if (initial_capacity == 0) \ 70 ltk_fatal("Array capacity is zero\n"); \ 71 ltk_array_##name *ar = ltk_malloc(sizeof(ltk_array_##name)); \ 72 ar->buf = ltk_reallocarray(NULL, initial_capacity, sizeof(type)); \ 73 ar->buf_size = initial_capacity; \ 74 ar->len = 0; \ 75 return ar; \ 76 } \ 77 \ 78 LTK_UNUSED_FUNC storage type \ 79 ltk_array_pop_##name(ltk_array_##name *ar) { \ 80 if (ar->len == 0) \ 81 ltk_fatal("Array empty; cannot pop.\n"); \ 82 ar->len--; \ 83 return ar->buf[ar->len]; \ 84 } \ 85 \ 86 LTK_UNUSED_FUNC storage size_t \ 87 ltk_array_remove_if_##name(ltk_array_##name *ar, int (*callback)(type *, void *), void *data) { \ 88 size_t removed = 0; \ 89 for (size_t i = 0; i < ar->len; i++) { \ 90 if (callback(&ar->buf[i], data)) \ 91 removed++; \ 92 else \ 93 ar->buf[i - removed] = ar->buf[i]; \ 94 } \ 95 /* FIXME: maybe release memory */ \ 96 ar->len -= removed; \ 97 return removed; \ 98 } \ 99 \ 100 /* FIXME: having this function in the public interface is ugly */ \ 101 LTK_UNUSED_FUNC storage void \ 102 ltk_array_prepare_gap_##name(ltk_array_##name *ar, size_t index, size_t len) { \ 103 if (index > ar->len) \ 104 ltk_fatal("Array index out of bounds\n"); \ 105 ltk_array_resize_##name(ar, ar->len + len); \ 106 ar->len += len; \ 107 if (ar->len - len == index) \ 108 return; \ 109 memmove(ar->buf + index + len, ar->buf + index, \ 110 (ar->len - len - index) * sizeof(type)); \ 111 } \ 112 \ 113 LTK_UNUSED_FUNC storage void \ 114 ltk_array_insert_##name(ltk_array_##name *ar, size_t index, type *elem, size_t len) { \ 115 ltk_array_prepare_gap_##name(ar, index, len); \ 116 for (size_t i = 0; i < len; i++) { \ 117 ar->buf[index + i] = elem[i]; \ 118 } \ 119 } \ 120 \ 121 LTK_UNUSED_FUNC storage void \ 122 ltk_array_delete_##name(ltk_array_##name *ar, size_t index, size_t len) { \ 123 /* FIXME: integer overflow protection everywhere */ \ 124 if (index + len > ar->len) \ 125 ltk_fatal("Array index out of bounds\n"); \ 126 /* FIXME: maybe release memory at some point? */ \ 127 memmove(ar->buf + index, ar->buf + index + len, (ar->len - index - len) * sizeof(type)); \ 128 ar->len -= len; \ 129 } \ 130 \ 131 LTK_UNUSED_FUNC storage void \ 132 ltk_array_append_##name(ltk_array_##name *ar, type elem) { \ 133 if (ar->len == ar->buf_size) \ 134 ltk_array_resize_##name(ar, ar->len + 1); \ 135 ar->buf[ar->len++] = elem; \ 136 } \ 137 \ 138 LTK_UNUSED_FUNC storage void \ 139 ltk_array_clear_##name(ltk_array_##name *ar) { \ 140 ar->len = 0; \ 141 ltk_array_resize_##name(ar, 1); \ 142 } \ 143 \ 144 LTK_UNUSED_FUNC storage void \ 145 ltk_array_resize_##name(ltk_array_##name *ar, size_t len) { \ 146 size_t new_size = ideal_array_size(ar->buf_size, len); \ 147 if (new_size != ar->buf_size) { \ 148 ar->buf = ltk_reallocarray(ar->buf, new_size, sizeof(type)); \ 149 ar->buf_size = new_size; \ 150 ar->len = ar->len < new_size ? ar->len : new_size; \ 151 } \ 152 } \ 153 \ 154 LTK_UNUSED_FUNC storage void \ 155 ltk_array_destroy_##name(ltk_array_##name *ar) { \ 156 if (!ar) \ 157 return; \ 158 ltk_free(ar->buf); \ 159 ltk_free(ar); \ 160 } \ 161 \ 162 LTK_UNUSED_FUNC storage void \ 163 ltk_array_destroy_deep_##name(ltk_array_##name *ar, void (*destroy_func)(type)) { \ 164 if (!ar) \ 165 return; \ 166 for (size_t i = 0; i < ar->len; i++) { \ 167 destroy_func(ar->buf[i]); \ 168 } \ 169 ltk_array_destroy_##name(ar); \ 170 } \ 171 \ 172 LTK_UNUSED_FUNC storage type \ 173 ltk_array_get_safe_##name(ltk_array_##name *ar, size_t index) { \ 174 if (index >= ar->len) \ 175 ltk_fatal("Index out of bounds.\n"); \ 176 return ar->buf[index]; \ 177 } \ 178 \ 179 LTK_UNUSED_FUNC storage void \ 180 ltk_array_set_safe_##name(ltk_array_##name *ar, size_t index, type e) { \ 181 if (index >= ar->len) \ 182 ltk_fatal("Index out of bounds.\n"); \ 183 ar->buf[index] = e; \ 184 } 185 186 #define ltk_array(name) ltk_array_##name 187 #define ltk_array_create(name, initial_capacity) ltk_array_create_##name(initial_capacity) 188 #define ltk_array_pop(name, ar) ltk_array_pop_##name(ar) 189 #define ltk_array_remove_if(name, ar, callback, data) ltk_array_remove_if_##name(ar, callback, data) 190 #define ltk_array_insert(name, ar, index, elem, len) ltk_array_insert_##name(ar, index, elem, len) 191 #define ltk_array_delete(name, ar, index, len) ltk_array_delete_##name(ar, index, len) 192 #define ltk_array_resize(name, ar, size) ltk_array_resize_##name(ar, size) 193 #define ltk_array_destroy(name, ar) ltk_array_destroy_##name(ar) 194 #define ltk_array_clear(name, ar) ltk_array_clear_##name(ar) 195 #define ltk_array_append(name, ar, elem) ltk_array_append_##name(ar, elem) 196 #define ltk_array_destroy_deep(name, ar, destroy_func) ltk_array_destroy_deep_##name(ar, destroy_func) 197 #define ltk_array_len(ar) ((ar)->len) 198 #define ltk_array_get_buf(ar) ((ar)->buf) 199 #define ltk_array_get(ar, index) ((ar)->buf[index]) 200 #define ltk_array_get_safe(name, ar, index) ltk_array_get_safe_##name(ar, index) 201 #define ltk_array_set_safe(name, ar, index, e) ltk_array_set_safe_##name(ar, index, e) 202 203 #define LTK_ARRAY_INIT_DECL(name, type) \ 204 LTK_ARRAY_INIT_STRUCT_DECL_BASE(name, type,) \ 205 LTK_ARRAY_INIT_FUNC_DECL_BASE(name, type,) 206 207 /* mainly for header files that shouldn't include all the function declarations */ 208 #define LTK_ARRAY_INIT_STRUCT_DECL(name, type)LTK_ARRAY_INIT_STRUCT_DECL_BASE(name, type,) 209 #define LTK_ARRAY_INIT_FUNC_DECL(name, type)LTK_ARRAY_INIT_FUNC_DECL_BASE(name, type,) 210 #define LTK_ARRAY_INIT_FUNC_DECL_STATIC(name, type)LTK_ARRAY_INIT_FUNC_DECL_BASE(name, type, static) 211 212 #define LTK_ARRAY_INIT_DECL_STATIC(name, type) \ 213 LTK_ARRAY_INIT_STRUCT_DECL_BASE(name, type, static) \ 214 LTK_ARRAY_INIT_FUNC_DECL_BASE(name, type, static) 215 216 #define LTK_ARRAY_INIT_IMPL(name, type) LTK_ARRAY_INIT_IMPL_BASE(name, type,) 217 #define LTK_ARRAY_INIT_IMPL_STATIC(name, type) LTK_ARRAY_INIT_IMPL_BASE(name, type, static) 218 219 #endif /* LTK_ARRAY_H */