Wed, 15 Feb 2023 16:48:11 +0100
implement backwards iterator - fixes #238
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@641 | 35 | static _Thread_local CxListComparator 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@647 | 98 | static int cx_pl_swap( |
universe@647 | 99 | struct cx_list_s *list, |
universe@647 | 100 | size_t i, |
universe@647 | 101 | size_t j |
universe@647 | 102 | ) { |
universe@647 | 103 | return list->climpl->swap(list, i, j); |
universe@647 | 104 | } |
universe@647 | 105 | |
universe@641 | 106 | static void *cx_pl_at( |
universe@641 | 107 | struct cx_list_s const *list, |
universe@641 | 108 | size_t index |
universe@641 | 109 | ) { |
universe@641 | 110 | void **ptr = list->climpl->at(list, index); |
universe@641 | 111 | return ptr == NULL ? NULL : *ptr; |
universe@641 | 112 | } |
universe@641 | 113 | |
universe@641 | 114 | static size_t cx_pl_find( |
universe@641 | 115 | struct cx_list_s const *list, |
universe@641 | 116 | void const *elem |
universe@641 | 117 | ) { |
universe@641 | 118 | cx_pl_hack_cmpfunc(list); |
universe@641 | 119 | size_t ret = list->climpl->find(list, &elem); |
universe@641 | 120 | cx_pl_unhack_cmpfunc(list); |
universe@641 | 121 | return ret; |
universe@641 | 122 | } |
universe@641 | 123 | |
universe@641 | 124 | static void cx_pl_sort(struct cx_list_s *list) { |
universe@641 | 125 | cx_pl_hack_cmpfunc(list); |
universe@641 | 126 | list->climpl->sort(list); |
universe@641 | 127 | cx_pl_unhack_cmpfunc(list); |
universe@641 | 128 | } |
universe@641 | 129 | |
universe@641 | 130 | static int cx_pl_compare( |
universe@641 | 131 | struct cx_list_s const *list, |
universe@641 | 132 | struct cx_list_s const *other |
universe@641 | 133 | ) { |
universe@641 | 134 | cx_pl_hack_cmpfunc(list); |
universe@641 | 135 | int ret = list->climpl->compare(list, other); |
universe@641 | 136 | cx_pl_unhack_cmpfunc(list); |
universe@641 | 137 | return ret; |
universe@641 | 138 | } |
universe@641 | 139 | |
universe@641 | 140 | static void cx_pl_reverse(struct cx_list_s *list) { |
universe@641 | 141 | list->climpl->reverse(list); |
universe@641 | 142 | } |
universe@641 | 143 | |
universe@641 | 144 | static void *cx_pl_iter_current(void const *it) { |
universe@641 | 145 | struct cx_iterator_s const *iter = it; |
universe@641 | 146 | void **ptr = iter->base.current_impl(it); |
universe@641 | 147 | return ptr == NULL ? NULL : *ptr; |
universe@641 | 148 | } |
universe@641 | 149 | |
universe@641 | 150 | static struct cx_iterator_s cx_pl_iterator( |
universe@641 | 151 | struct cx_list_s const *list, |
universe@655 | 152 | size_t index, |
universe@655 | 153 | bool backwards |
universe@641 | 154 | ) { |
universe@655 | 155 | struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); |
universe@641 | 156 | iter.base.current_impl = iter.base.current; |
universe@641 | 157 | iter.base.current = cx_pl_iter_current; |
universe@641 | 158 | return iter; |
universe@641 | 159 | } |
universe@641 | 160 | |
universe@641 | 161 | static cx_list_class cx_pointer_list_class = { |
universe@641 | 162 | cx_pl_destructor, |
universe@641 | 163 | cx_pl_insert_element, |
universe@641 | 164 | cx_pl_insert_array, |
universe@641 | 165 | cx_pl_insert_iter, |
universe@641 | 166 | cx_pl_remove, |
universe@647 | 167 | cx_pl_swap, |
universe@641 | 168 | cx_pl_at, |
universe@641 | 169 | cx_pl_find, |
universe@641 | 170 | cx_pl_sort, |
universe@641 | 171 | cx_pl_compare, |
universe@641 | 172 | cx_pl_reverse, |
universe@641 | 173 | cx_pl_iterator, |
universe@641 | 174 | }; |
universe@641 | 175 | |
universe@641 | 176 | void cxListStoreObjects(CxList *list) { |
universe@641 | 177 | if (list->climpl != NULL) { |
universe@641 | 178 | list->cl = list->climpl; |
universe@641 | 179 | list->climpl = NULL; |
universe@641 | 180 | } |
universe@641 | 181 | } |
universe@641 | 182 | |
universe@641 | 183 | void cxListStorePointers(CxList *list) { |
universe@641 | 184 | list->itemsize = sizeof(void *); |
universe@641 | 185 | list->climpl = list->cl; |
universe@641 | 186 | list->cl = &cx_pointer_list_class; |
universe@641 | 187 | } |
universe@641 | 188 | |
universe@641 | 189 | bool cxListIsStoringPointers(CxList *list) { |
universe@641 | 190 | return list->climpl != NULL; |
universe@641 | 191 | } |
universe@641 | 192 | |
universe@641 | 193 | // </editor-fold> |
universe@641 | 194 | |
universe@528 | 195 | void cxListDestroy(CxList *list) { |
universe@528 | 196 | switch (list->content_destructor_type) { |
universe@528 | 197 | case CX_DESTRUCTOR_SIMPLE: { |
universe@655 | 198 | CxIterator iter = cxListIterator(list); |
universe@528 | 199 | cx_foreach(void*, elem, iter) { |
universe@528 | 200 | list->simple_destructor(elem); |
universe@528 | 201 | } |
universe@528 | 202 | break; |
universe@503 | 203 | } |
universe@528 | 204 | case CX_DESTRUCTOR_ADVANCED: { |
universe@655 | 205 | CxIterator iter = cxListIterator(list); |
universe@528 | 206 | cx_foreach(void*, elem, iter) { |
universe@528 | 207 | list->advanced_destructor.func(list->advanced_destructor.data, elem); |
universe@528 | 208 | } |
universe@528 | 209 | break; |
universe@528 | 210 | } |
universe@528 | 211 | case CX_DESTRUCTOR_NONE: |
universe@528 | 212 | break; // nothing |
universe@503 | 213 | } |
universe@528 | 214 | |
universe@524 | 215 | list->cl->destructor(list); |
universe@524 | 216 | cxFree(list->allocator, list); |
universe@503 | 217 | } |
universe@618 | 218 | |
universe@618 | 219 | int cxListCompare( |
universe@618 | 220 | CxList const *list, |
universe@618 | 221 | CxList const *other |
universe@618 | 222 | ) { |
universe@618 | 223 | if (list->cl->compare == other->cl->compare) { |
universe@628 | 224 | // same compare function, lists are compatible |
universe@618 | 225 | return list->cl->compare(list, other); |
universe@618 | 226 | } else { |
universe@628 | 227 | // different compare functions, use iterator |
universe@618 | 228 | if (list->size == other->size) { |
universe@655 | 229 | CxIterator left = cxListIterator(list); |
universe@655 | 230 | CxIterator right = cxListIterator(other); |
universe@618 | 231 | for (size_t i = 0; i < list->size; i++) { |
universe@630 | 232 | void *leftValue = cxIteratorCurrent(left); |
universe@630 | 233 | void *rightValue = cxIteratorCurrent(right); |
universe@618 | 234 | int d = list->cmpfunc(leftValue, rightValue); |
universe@618 | 235 | if (d != 0) { |
universe@618 | 236 | return d; |
universe@618 | 237 | } |
universe@630 | 238 | cxIteratorNext(left); |
universe@630 | 239 | cxIteratorNext(right); |
universe@618 | 240 | } |
universe@618 | 241 | return 0; |
universe@618 | 242 | } else { |
universe@618 | 243 | return list->size < other->size ? -1 : 1; |
universe@618 | 244 | } |
universe@618 | 245 | } |
universe@618 | 246 | } |
universe@640 | 247 | |
universe@655 | 248 | CxMutIterator cxListMutIteratorAt( |
universe@640 | 249 | CxList *list, |
universe@640 | 250 | size_t index |
universe@640 | 251 | ) { |
universe@655 | 252 | CxIterator it = list->cl->iterator(list, index, false); |
universe@640 | 253 | it.base.mutating = true; |
universe@640 | 254 | |
universe@640 | 255 | // we know the iterators share the same memory layout |
universe@640 | 256 | CxMutIterator iter; |
universe@640 | 257 | memcpy(&iter, &it, sizeof(CxMutIterator)); |
universe@640 | 258 | return iter; |
universe@640 | 259 | } |
universe@655 | 260 | |
universe@655 | 261 | CxMutIterator cxListMutBackwardsIteratorAt( |
universe@655 | 262 | CxList *list, |
universe@655 | 263 | size_t index |
universe@655 | 264 | ) { |
universe@655 | 265 | CxIterator it = list->cl->iterator(list, index, true); |
universe@655 | 266 | it.base.mutating = true; |
universe@655 | 267 | |
universe@655 | 268 | // we know the iterators share the same memory layout |
universe@655 | 269 | CxMutIterator iter; |
universe@655 | 270 | memcpy(&iter, &it, sizeof(CxMutIterator)); |
universe@655 | 271 | return iter; |
universe@655 | 272 | } |