Wed, 24 Jan 2024 22:19:05 +0100
add cx_array_default_reallocator
universe@503 | 1 | /* |
universe@503 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@503 | 3 | * |
universe@503 | 4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
universe@503 | 5 | * |
universe@503 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@503 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@503 | 8 | * |
universe@503 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@503 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@503 | 11 | * |
universe@503 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@503 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@503 | 14 | * documentation and/or other materials provided with the distribution. |
universe@503 | 15 | * |
universe@503 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@503 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@503 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@503 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@503 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@503 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@503 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@503 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@503 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@503 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@503 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@503 | 27 | */ |
universe@503 | 28 | |
universe@503 | 29 | #include "cx/list.h" |
universe@503 | 30 | |
universe@640 | 31 | #include <string.h> |
universe@640 | 32 | |
universe@641 | 33 | // <editor-fold desc="Store Pointers Functionality"> |
universe@641 | 34 | |
universe@677 | 35 | static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; |
universe@641 | 36 | |
universe@641 | 37 | static int cx_pl_cmpfunc( |
universe@641 | 38 | void const *l, |
universe@641 | 39 | void const *r |
universe@641 | 40 | ) { |
universe@641 | 41 | void *const *lptr = l; |
universe@641 | 42 | void *const *rptr = r; |
universe@641 | 43 | void const *left = lptr == NULL ? NULL : *lptr; |
universe@641 | 44 | void const *right = rptr == NULL ? NULL : *rptr; |
universe@641 | 45 | return cx_pl_cmpfunc_impl(left, right); |
universe@641 | 46 | } |
universe@641 | 47 | |
universe@641 | 48 | static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) { |
universe@641 | 49 | // cast away const - this is the hacky thing |
universe@641 | 50 | struct cx_list_s *l = (struct cx_list_s *) list; |
universe@641 | 51 | cx_pl_cmpfunc_impl = l->cmpfunc; |
universe@641 | 52 | l->cmpfunc = cx_pl_cmpfunc; |
universe@641 | 53 | } |
universe@641 | 54 | |
universe@641 | 55 | static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) { |
universe@641 | 56 | // cast away const - this is the hacky thing |
universe@641 | 57 | struct cx_list_s *l = (struct cx_list_s *) list; |
universe@641 | 58 | l->cmpfunc = cx_pl_cmpfunc_impl; |
universe@641 | 59 | } |
universe@641 | 60 | |
universe@641 | 61 | static void cx_pl_destructor(struct cx_list_s *list) { |
universe@641 | 62 | list->climpl->destructor(list); |
universe@641 | 63 | } |
universe@641 | 64 | |
universe@641 | 65 | static int cx_pl_insert_element( |
universe@641 | 66 | struct cx_list_s *list, |
universe@641 | 67 | size_t index, |
universe@641 | 68 | void const *element |
universe@641 | 69 | ) { |
universe@641 | 70 | return list->climpl->insert_element(list, index, &element); |
universe@641 | 71 | } |
universe@641 | 72 | |
universe@641 | 73 | static size_t cx_pl_insert_array( |
universe@641 | 74 | struct cx_list_s *list, |
universe@641 | 75 | size_t index, |
universe@641 | 76 | void const *array, |
universe@641 | 77 | size_t n |
universe@641 | 78 | ) { |
universe@641 | 79 | return list->climpl->insert_array(list, index, array, n); |
universe@641 | 80 | } |
universe@641 | 81 | |
universe@641 | 82 | static int cx_pl_insert_iter( |
universe@641 | 83 | struct cx_mut_iterator_s *iter, |
universe@641 | 84 | void const *elem, |
universe@641 | 85 | int prepend |
universe@641 | 86 | ) { |
universe@641 | 87 | struct cx_list_s *list = iter->src_handle; |
universe@641 | 88 | return list->climpl->insert_iter(iter, &elem, prepend); |
universe@641 | 89 | } |
universe@641 | 90 | |
universe@641 | 91 | static int cx_pl_remove( |
universe@641 | 92 | struct cx_list_s *list, |
universe@641 | 93 | size_t index |
universe@641 | 94 | ) { |
universe@641 | 95 | return list->climpl->remove(list, index); |
universe@641 | 96 | } |
universe@641 | 97 | |
universe@664 | 98 | static void cx_pl_clear(struct cx_list_s *list) { |
universe@664 | 99 | list->climpl->clear(list); |
universe@664 | 100 | } |
universe@664 | 101 | |
universe@647 | 102 | static int cx_pl_swap( |
universe@647 | 103 | struct cx_list_s *list, |
universe@647 | 104 | size_t i, |
universe@647 | 105 | size_t j |
universe@647 | 106 | ) { |
universe@647 | 107 | return list->climpl->swap(list, i, j); |
universe@647 | 108 | } |
universe@647 | 109 | |
universe@641 | 110 | static void *cx_pl_at( |
universe@641 | 111 | struct cx_list_s const *list, |
universe@641 | 112 | size_t index |
universe@641 | 113 | ) { |
universe@641 | 114 | void **ptr = list->climpl->at(list, index); |
universe@641 | 115 | return ptr == NULL ? NULL : *ptr; |
universe@641 | 116 | } |
universe@641 | 117 | |
universe@764 | 118 | static ssize_t cx_pl_find_remove( |
universe@764 | 119 | struct cx_list_s *list, |
universe@764 | 120 | void const *elem, |
universe@764 | 121 | bool remove |
universe@641 | 122 | ) { |
universe@641 | 123 | cx_pl_hack_cmpfunc(list); |
universe@764 | 124 | ssize_t ret = list->climpl->find_remove(list, &elem, remove); |
universe@641 | 125 | cx_pl_unhack_cmpfunc(list); |
universe@641 | 126 | return ret; |
universe@641 | 127 | } |
universe@641 | 128 | |
universe@641 | 129 | static void cx_pl_sort(struct cx_list_s *list) { |
universe@641 | 130 | cx_pl_hack_cmpfunc(list); |
universe@641 | 131 | list->climpl->sort(list); |
universe@641 | 132 | cx_pl_unhack_cmpfunc(list); |
universe@641 | 133 | } |
universe@641 | 134 | |
universe@641 | 135 | static int cx_pl_compare( |
universe@641 | 136 | struct cx_list_s const *list, |
universe@641 | 137 | struct cx_list_s const *other |
universe@641 | 138 | ) { |
universe@641 | 139 | cx_pl_hack_cmpfunc(list); |
universe@641 | 140 | int ret = list->climpl->compare(list, other); |
universe@641 | 141 | cx_pl_unhack_cmpfunc(list); |
universe@641 | 142 | return ret; |
universe@641 | 143 | } |
universe@641 | 144 | |
universe@641 | 145 | static void cx_pl_reverse(struct cx_list_s *list) { |
universe@641 | 146 | list->climpl->reverse(list); |
universe@641 | 147 | } |
universe@641 | 148 | |
universe@641 | 149 | static void *cx_pl_iter_current(void const *it) { |
universe@641 | 150 | struct cx_iterator_s const *iter = it; |
universe@641 | 151 | void **ptr = iter->base.current_impl(it); |
universe@641 | 152 | return ptr == NULL ? NULL : *ptr; |
universe@641 | 153 | } |
universe@641 | 154 | |
universe@641 | 155 | static struct cx_iterator_s cx_pl_iterator( |
universe@641 | 156 | struct cx_list_s const *list, |
universe@655 | 157 | size_t index, |
universe@655 | 158 | bool backwards |
universe@641 | 159 | ) { |
universe@655 | 160 | struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); |
universe@641 | 161 | iter.base.current_impl = iter.base.current; |
universe@641 | 162 | iter.base.current = cx_pl_iter_current; |
universe@641 | 163 | return iter; |
universe@641 | 164 | } |
universe@641 | 165 | |
universe@641 | 166 | static cx_list_class cx_pointer_list_class = { |
universe@641 | 167 | cx_pl_destructor, |
universe@641 | 168 | cx_pl_insert_element, |
universe@641 | 169 | cx_pl_insert_array, |
universe@641 | 170 | cx_pl_insert_iter, |
universe@641 | 171 | cx_pl_remove, |
universe@664 | 172 | cx_pl_clear, |
universe@647 | 173 | cx_pl_swap, |
universe@641 | 174 | cx_pl_at, |
universe@764 | 175 | cx_pl_find_remove, |
universe@641 | 176 | cx_pl_sort, |
universe@641 | 177 | cx_pl_compare, |
universe@641 | 178 | cx_pl_reverse, |
universe@641 | 179 | cx_pl_iterator, |
universe@641 | 180 | }; |
universe@641 | 181 | |
universe@641 | 182 | void cxListStoreObjects(CxList *list) { |
universe@677 | 183 | list->store_pointer = false; |
universe@641 | 184 | if (list->climpl != NULL) { |
universe@641 | 185 | list->cl = list->climpl; |
universe@641 | 186 | list->climpl = NULL; |
universe@641 | 187 | } |
universe@641 | 188 | } |
universe@641 | 189 | |
universe@641 | 190 | void cxListStorePointers(CxList *list) { |
universe@677 | 191 | list->item_size = sizeof(void *); |
universe@677 | 192 | list->store_pointer = true; |
universe@641 | 193 | list->climpl = list->cl; |
universe@641 | 194 | list->cl = &cx_pointer_list_class; |
universe@641 | 195 | } |
universe@641 | 196 | |
universe@641 | 197 | // </editor-fold> |
universe@641 | 198 | |
universe@704 | 199 | // <editor-fold desc="empty list implementation"> |
universe@704 | 200 | |
universe@704 | 201 | static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) { |
universe@704 | 202 | // this is a noop, but MUST be implemented |
universe@704 | 203 | } |
universe@704 | 204 | |
universe@704 | 205 | static void *cx_emptyl_at( |
universe@704 | 206 | __attribute__((__unused__)) struct cx_list_s const *list, |
universe@704 | 207 | __attribute__((__unused__)) size_t index |
universe@704 | 208 | ) { |
universe@704 | 209 | return NULL; |
universe@704 | 210 | } |
universe@704 | 211 | |
universe@764 | 212 | static ssize_t cx_emptyl_find_remove( |
universe@764 | 213 | __attribute__((__unused__)) struct cx_list_s *list, |
universe@764 | 214 | __attribute__((__unused__)) void const *elem, |
universe@764 | 215 | __attribute__((__unused__)) bool remove |
universe@704 | 216 | ) { |
universe@704 | 217 | return -1; |
universe@704 | 218 | } |
universe@704 | 219 | |
universe@704 | 220 | static int cx_emptyl_compare( |
universe@704 | 221 | __attribute__((__unused__)) struct cx_list_s const *list, |
universe@704 | 222 | struct cx_list_s const *other |
universe@704 | 223 | ) { |
universe@704 | 224 | if (other->size == 0) return 0; |
universe@704 | 225 | return -1; |
universe@704 | 226 | } |
universe@704 | 227 | |
universe@704 | 228 | static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { |
universe@704 | 229 | return false; |
universe@704 | 230 | } |
universe@704 | 231 | |
universe@704 | 232 | static CxIterator cx_emptyl_iterator( |
universe@704 | 233 | struct cx_list_s const *list, |
universe@704 | 234 | size_t index, |
universe@704 | 235 | __attribute__((__unused__)) bool backwards |
universe@704 | 236 | ) { |
universe@704 | 237 | CxIterator iter = {0}; |
universe@704 | 238 | iter.src_handle = list; |
universe@704 | 239 | iter.index = index; |
universe@704 | 240 | iter.base.valid = cx_emptyl_iter_valid; |
universe@704 | 241 | return iter; |
universe@704 | 242 | } |
universe@704 | 243 | |
universe@704 | 244 | static cx_list_class cx_empty_list_class = { |
universe@704 | 245 | cx_emptyl_noop, |
universe@704 | 246 | NULL, |
universe@704 | 247 | NULL, |
universe@704 | 248 | NULL, |
universe@704 | 249 | NULL, |
universe@704 | 250 | cx_emptyl_noop, |
universe@704 | 251 | NULL, |
universe@704 | 252 | cx_emptyl_at, |
universe@764 | 253 | cx_emptyl_find_remove, |
universe@704 | 254 | cx_emptyl_noop, |
universe@704 | 255 | cx_emptyl_compare, |
universe@704 | 256 | cx_emptyl_noop, |
universe@704 | 257 | cx_emptyl_iterator, |
universe@704 | 258 | }; |
universe@704 | 259 | |
universe@704 | 260 | CxList cx_empty_list = { |
universe@704 | 261 | NULL, |
universe@704 | 262 | NULL, |
universe@704 | 263 | 0, |
universe@704 | 264 | 0, |
universe@704 | 265 | NULL, |
universe@704 | 266 | NULL, |
universe@704 | 267 | NULL, |
universe@704 | 268 | false, |
universe@704 | 269 | &cx_empty_list_class, |
universe@704 | 270 | NULL |
universe@704 | 271 | }; |
universe@704 | 272 | |
universe@704 | 273 | CxList *const cxEmptyList = &cx_empty_list; |
universe@704 | 274 | |
universe@704 | 275 | // </editor-fold> |
universe@704 | 276 | |
universe@677 | 277 | void cxListDestroy(CxList *list) { |
universe@524 | 278 | list->cl->destructor(list); |
universe@503 | 279 | } |
universe@618 | 280 | |
universe@618 | 281 | int cxListCompare( |
universe@618 | 282 | CxList const *list, |
universe@618 | 283 | CxList const *other |
universe@618 | 284 | ) { |
universe@705 | 285 | if ( |
universe@705 | 286 | // if one is storing pointers but the other is not |
universe@705 | 287 | (list->store_pointer ^ other->store_pointer) || |
universe@705 | 288 | |
universe@705 | 289 | // if one class is wrapped but the other is not |
universe@705 | 290 | ((list->climpl == NULL) ^ (other->climpl == NULL)) || |
universe@705 | 291 | |
universe@705 | 292 | // if the resolved compare functions are not the same |
universe@680 | 293 | ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != |
universe@705 | 294 | (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) |
universe@705 | 295 | ) { |
universe@680 | 296 | // lists are definitely different - cannot use internal compare function |
universe@618 | 297 | if (list->size == other->size) { |
universe@776 | 298 | CxIterator left = list->cl->iterator(list, 0, false); |
universe@802 | 299 | CxIterator right = other->cl->iterator(other, 0, false); |
universe@618 | 300 | for (size_t i = 0; i < list->size; i++) { |
universe@630 | 301 | void *leftValue = cxIteratorCurrent(left); |
universe@630 | 302 | void *rightValue = cxIteratorCurrent(right); |
universe@618 | 303 | int d = list->cmpfunc(leftValue, rightValue); |
universe@618 | 304 | if (d != 0) { |
universe@618 | 305 | return d; |
universe@618 | 306 | } |
universe@630 | 307 | cxIteratorNext(left); |
universe@630 | 308 | cxIteratorNext(right); |
universe@618 | 309 | } |
universe@618 | 310 | return 0; |
universe@618 | 311 | } else { |
universe@618 | 312 | return list->size < other->size ? -1 : 1; |
universe@618 | 313 | } |
universe@680 | 314 | } else { |
universe@680 | 315 | // lists are compatible |
universe@680 | 316 | return list->cl->compare(list, other); |
universe@618 | 317 | } |
universe@618 | 318 | } |
universe@640 | 319 | |
universe@655 | 320 | CxMutIterator cxListMutIteratorAt( |
universe@640 | 321 | CxList *list, |
universe@640 | 322 | size_t index |
universe@640 | 323 | ) { |
universe@655 | 324 | CxIterator it = list->cl->iterator(list, index, false); |
universe@640 | 325 | it.base.mutating = true; |
universe@640 | 326 | |
universe@640 | 327 | // we know the iterators share the same memory layout |
universe@640 | 328 | CxMutIterator iter; |
universe@640 | 329 | memcpy(&iter, &it, sizeof(CxMutIterator)); |
universe@640 | 330 | return iter; |
universe@640 | 331 | } |
universe@655 | 332 | |
universe@655 | 333 | CxMutIterator cxListMutBackwardsIteratorAt( |
universe@655 | 334 | CxList *list, |
universe@655 | 335 | size_t index |
universe@655 | 336 | ) { |
universe@655 | 337 | CxIterator it = list->cl->iterator(list, index, true); |
universe@655 | 338 | it.base.mutating = true; |
universe@655 | 339 | |
universe@655 | 340 | // we know the iterators share the same memory layout |
universe@655 | 341 | CxMutIterator iter; |
universe@655 | 342 | memcpy(&iter, &it, sizeof(CxMutIterator)); |
universe@655 | 343 | return iter; |
universe@655 | 344 | } |