UNIXworkcode

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