Mercurial > hg > idav / file comparison

comparison: ucx/list.c

ucx/list.c

changeset 49
2f71f4ee247a
parent 2
fbdfaacc4182
equal deleted inserted replaced
48:ae61523bce20 49:2f71f4ee247a
33 // <editor-fold desc="Store Pointers Functionality"> 33 // <editor-fold desc="Store Pointers Functionality">
34 34
35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; 35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
36 36
37 static int cx_pl_cmpfunc( 37 static int cx_pl_cmpfunc(
38 void const *l, 38 const void *l,
39 void const *r 39 const void *r
40 ) { 40 ) {
41 void *const *lptr = l; 41 void *const *lptr = l;
42 void *const *rptr = r; 42 void *const *rptr = r;
43 void const *left = lptr == NULL ? NULL : *lptr; 43 const void *left = lptr == NULL ? NULL : *lptr;
44 void const *right = rptr == NULL ? NULL : *rptr; 44 const void *right = rptr == NULL ? NULL : *rptr;
45 return cx_pl_cmpfunc_impl(left, right); 45 return cx_pl_cmpfunc_impl(left, right);
46 } 46 }
47 47
48 static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) { 48 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
49 // cast away const - this is the hacky thing 49 // cast away const - this is the hacky thing
50 struct cx_list_s *l = (struct cx_list_s *) list; 50 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
51 cx_pl_cmpfunc_impl = l->cmpfunc; 51 cx_pl_cmpfunc_impl = l->cmpfunc;
52 l->cmpfunc = cx_pl_cmpfunc; 52 l->cmpfunc = cx_pl_cmpfunc;
53 } 53 }
54 54
55 static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) { 55 static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
56 // cast away const - this is the hacky thing 56 // cast away const - this is the hacky thing
57 struct cx_list_s *l = (struct cx_list_s *) list; 57 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
58 l->cmpfunc = cx_pl_cmpfunc_impl; 58 l->cmpfunc = cx_pl_cmpfunc_impl;
59 } 59 }
60 60
61 static void cx_pl_destructor(struct cx_list_s *list) { 61 static void cx_pl_destructor(struct cx_list_s *list) {
62 list->climpl->destructor(list); 62 list->climpl->destructor(list);
63 } 63 }
64 64
65 static int cx_pl_insert_element( 65 static int cx_pl_insert_element(
66 struct cx_list_s *list, 66 struct cx_list_s *list,
67 size_t index, 67 size_t index,
68 void const *element 68 const void *element
69 ) { 69 ) {
70 return list->climpl->insert_element(list, index, &element); 70 return list->climpl->insert_element(list, index, &element);
71 } 71 }
72 72
73 static size_t cx_pl_insert_array( 73 static size_t cx_pl_insert_array(
74 struct cx_list_s *list, 74 struct cx_list_s *list,
75 size_t index, 75 size_t index,
76 void const *array, 76 const void *array,
77 size_t n 77 size_t n
78 ) { 78 ) {
79 return list->climpl->insert_array(list, index, array, n); 79 return list->climpl->insert_array(list, index, array, n);
80 } 80 }
81 81
82 static size_t cx_pl_insert_sorted(
83 struct cx_list_s *list,
84 const void *array,
85 size_t n
86 ) {
87 cx_pl_hack_cmpfunc(list);
88 size_t result = list->climpl->insert_sorted(list, array, n);
89 cx_pl_unhack_cmpfunc(list);
90 return result;
91 }
92
82 static int cx_pl_insert_iter( 93 static int cx_pl_insert_iter(
83 struct cx_mut_iterator_s *iter, 94 struct cx_iterator_s *iter,
84 void const *elem, 95 const void *elem,
85 int prepend 96 int prepend
86 ) { 97 ) {
87 struct cx_list_s *list = iter->src_handle; 98 struct cx_list_s *list = iter->src_handle.m;
88 return list->climpl->insert_iter(iter, &elem, prepend); 99 return list->climpl->insert_iter(iter, &elem, prepend);
89 } 100 }
90 101
91 static int cx_pl_remove( 102 static int cx_pl_remove(
92 struct cx_list_s *list, 103 struct cx_list_s *list,
106 ) { 117 ) {
107 return list->climpl->swap(list, i, j); 118 return list->climpl->swap(list, i, j);
108 } 119 }
109 120
110 static void *cx_pl_at( 121 static void *cx_pl_at(
111 struct cx_list_s const *list, 122 const struct cx_list_s *list,
112 size_t index 123 size_t index
113 ) { 124 ) {
114 void **ptr = list->climpl->at(list, index); 125 void **ptr = list->climpl->at(list, index);
115 return ptr == NULL ? NULL : *ptr; 126 return ptr == NULL ? NULL : *ptr;
116 } 127 }
117 128
118 static ssize_t cx_pl_find_remove( 129 static ssize_t cx_pl_find_remove(
119 struct cx_list_s *list, 130 struct cx_list_s *list,
120 void const *elem, 131 const void *elem,
121 bool remove 132 bool remove
122 ) { 133 ) {
123 cx_pl_hack_cmpfunc(list); 134 cx_pl_hack_cmpfunc(list);
124 ssize_t ret = list->climpl->find_remove(list, &elem, remove); 135 ssize_t ret = list->climpl->find_remove(list, &elem, remove);
125 cx_pl_unhack_cmpfunc(list); 136 cx_pl_unhack_cmpfunc(list);
131 list->climpl->sort(list); 142 list->climpl->sort(list);
132 cx_pl_unhack_cmpfunc(list); 143 cx_pl_unhack_cmpfunc(list);
133 } 144 }
134 145
135 static int cx_pl_compare( 146 static int cx_pl_compare(
136 struct cx_list_s const *list, 147 const struct cx_list_s *list,
137 struct cx_list_s const *other 148 const struct cx_list_s *other
138 ) { 149 ) {
139 cx_pl_hack_cmpfunc(list); 150 cx_pl_hack_cmpfunc(list);
140 int ret = list->climpl->compare(list, other); 151 int ret = list->climpl->compare(list, other);
141 cx_pl_unhack_cmpfunc(list); 152 cx_pl_unhack_cmpfunc(list);
142 return ret; 153 return ret;
144 155
145 static void cx_pl_reverse(struct cx_list_s *list) { 156 static void cx_pl_reverse(struct cx_list_s *list) {
146 list->climpl->reverse(list); 157 list->climpl->reverse(list);
147 } 158 }
148 159
149 static void *cx_pl_iter_current(void const *it) { 160 static void *cx_pl_iter_current(const void *it) {
150 struct cx_iterator_s const *iter = it; 161 const struct cx_iterator_s *iter = it;
151 void **ptr = iter->base.current_impl(it); 162 void **ptr = iter->base.current_impl(it);
152 return ptr == NULL ? NULL : *ptr; 163 return ptr == NULL ? NULL : *ptr;
153 } 164 }
154 165
155 static struct cx_iterator_s cx_pl_iterator( 166 static struct cx_iterator_s cx_pl_iterator(
156 struct cx_list_s const *list, 167 const struct cx_list_s *list,
157 size_t index, 168 size_t index,
158 bool backwards 169 bool backwards
159 ) { 170 ) {
160 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); 171 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
161 iter.base.current_impl = iter.base.current; 172 iter.base.current_impl = iter.base.current;
165 176
166 static cx_list_class cx_pointer_list_class = { 177 static cx_list_class cx_pointer_list_class = {
167 cx_pl_destructor, 178 cx_pl_destructor,
168 cx_pl_insert_element, 179 cx_pl_insert_element,
169 cx_pl_insert_array, 180 cx_pl_insert_array,
181 cx_pl_insert_sorted,
170 cx_pl_insert_iter, 182 cx_pl_insert_iter,
171 cx_pl_remove, 183 cx_pl_remove,
172 cx_pl_clear, 184 cx_pl_clear,
173 cx_pl_swap, 185 cx_pl_swap,
174 cx_pl_at, 186 cx_pl_at,
178 cx_pl_reverse, 190 cx_pl_reverse,
179 cx_pl_iterator, 191 cx_pl_iterator,
180 }; 192 };
181 193
182 void cxListStoreObjects(CxList *list) { 194 void cxListStoreObjects(CxList *list) {
183 list->store_pointer = false; 195 list->collection.store_pointer = false;
184 if (list->climpl != NULL) { 196 if (list->climpl != NULL) {
185 list->cl = list->climpl; 197 list->cl = list->climpl;
186 list->climpl = NULL; 198 list->climpl = NULL;
187 } 199 }
188 } 200 }
189 201
190 void cxListStorePointers(CxList *list) { 202 void cxListStorePointers(CxList *list) {
191 list->item_size = sizeof(void *); 203 list->collection.elem_size = sizeof(void *);
192 list->store_pointer = true; 204 list->collection.store_pointer = true;
193 list->climpl = list->cl; 205 list->climpl = list->cl;
194 list->cl = &cx_pointer_list_class; 206 list->cl = &cx_pointer_list_class;
195 } 207 }
196 208
197 // </editor-fold> 209 // </editor-fold>
201 static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) { 213 static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) {
202 // this is a noop, but MUST be implemented 214 // this is a noop, but MUST be implemented
203 } 215 }
204 216
205 static void *cx_emptyl_at( 217 static void *cx_emptyl_at(
206 __attribute__((__unused__)) struct cx_list_s const *list, 218 __attribute__((__unused__)) const struct cx_list_s *list,
207 __attribute__((__unused__)) size_t index 219 __attribute__((__unused__)) size_t index
208 ) { 220 ) {
209 return NULL; 221 return NULL;
210 } 222 }
211 223
212 static ssize_t cx_emptyl_find_remove( 224 static ssize_t cx_emptyl_find_remove(
213 __attribute__((__unused__)) struct cx_list_s *list, 225 __attribute__((__unused__)) struct cx_list_s *list,
214 __attribute__((__unused__)) void const *elem, 226 __attribute__((__unused__)) const void *elem,
215 __attribute__((__unused__)) bool remove 227 __attribute__((__unused__)) bool remove
216 ) { 228 ) {
217 return -1; 229 return -1;
218 } 230 }
219 231
220 static int cx_emptyl_compare( 232 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) const void *iter) {
221 __attribute__((__unused__)) struct cx_list_s const *list,
222 struct cx_list_s const *other
223 ) {
224 if (other->size == 0) return 0;
225 return -1;
226 }
227
228 static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) {
229 return false; 233 return false;
230 } 234 }
231 235
232 static CxIterator cx_emptyl_iterator( 236 static CxIterator cx_emptyl_iterator(
233 struct cx_list_s const *list, 237 const struct cx_list_s *list,
234 size_t index, 238 size_t index,
235 __attribute__((__unused__)) bool backwards 239 __attribute__((__unused__)) bool backwards
236 ) { 240 ) {
237 CxIterator iter = {0}; 241 CxIterator iter = {0};
238 iter.src_handle = list; 242 iter.src_handle.c = list;
239 iter.index = index; 243 iter.index = index;
240 iter.base.valid = cx_emptyl_iter_valid; 244 iter.base.valid = cx_emptyl_iter_valid;
241 return iter; 245 return iter;
242 } 246 }
243 247
245 cx_emptyl_noop, 249 cx_emptyl_noop,
246 NULL, 250 NULL,
247 NULL, 251 NULL,
248 NULL, 252 NULL,
249 NULL, 253 NULL,
254 NULL,
250 cx_emptyl_noop, 255 cx_emptyl_noop,
251 NULL, 256 NULL,
252 cx_emptyl_at, 257 cx_emptyl_at,
253 cx_emptyl_find_remove, 258 cx_emptyl_find_remove,
254 cx_emptyl_noop, 259 cx_emptyl_noop,
255 cx_emptyl_compare, 260 NULL,
256 cx_emptyl_noop, 261 cx_emptyl_noop,
257 cx_emptyl_iterator, 262 cx_emptyl_iterator,
258 }; 263 };
259 264
260 CxList cx_empty_list = { 265 CxList cx_empty_list = {
261 NULL, 266 {
262 NULL, 267 NULL,
263 0, 268 NULL,
264 0, 269 0,
265 NULL, 270 0,
266 NULL, 271 NULL,
267 NULL, 272 NULL,
268 false, 273 NULL,
274 false
275 },
269 &cx_empty_list_class, 276 &cx_empty_list_class,
270 NULL 277 NULL
271 }; 278 };
272 279
273 CxList *const cxEmptyList = &cx_empty_list; 280 CxList *const cxEmptyList = &cx_empty_list;
274 281
275 // </editor-fold> 282 // </editor-fold>
276 283
284 #define invoke_list_func(name, list, ...) \
285 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
286 (list, __VA_ARGS__)
287
288 size_t cx_list_default_insert_array(
289 struct cx_list_s *list,
290 size_t index,
291 const void *data,
292 size_t n
293 ) {
294 size_t elem_size = list->collection.elem_size;
295 const char *src = data;
296 size_t i = 0;
297 for (; i < n; i++) {
298 if (0 != invoke_list_func(insert_element,
299 list, index + i, src + (i * elem_size))) {
300 return i;
301 }
302 }
303 return i;
304 }
305
306 size_t cx_list_default_insert_sorted(
307 struct cx_list_s *list,
308 const void *sorted_data,
309 size_t n
310 ) {
311 // corner case
312 if (n == 0) return 0;
313
314 size_t elem_size = list->collection.elem_size;
315 cx_compare_func cmp = list->collection.cmpfunc;
316 const char *src = sorted_data;
317
318 // track indices and number of inserted items
319 size_t di = 0, si = 0, inserted = 0;
320
321 // search the list for insertion points
322 for (; di < list->collection.size; di++) {
323 const void *list_elm = invoke_list_func(at, list, di);
324
325 // compare current list element with first source element
326 // if less or equal, skip
327 if (cmp(list_elm, src) <= 0) {
328 continue;
329 }
330
331 // determine number of consecutive elements that can be inserted
332 size_t ins = 1;
333 const char *next = src;
334 while (++si < n) {
335 next += elem_size;
336 // once we become larger than the list elem, break
337 if (cmp(list_elm, next) <= 0) {
338 break;
339 }
340 // otherwise, we can insert one more
341 ins++;
342 }
343
344 // insert the elements at location si
345 if (ins == 1) {
346 if (0 != invoke_list_func(insert_element,
347 list, di, src))
348 return inserted;
349 } else {
350 size_t r = invoke_list_func(insert_array, list, di, src, ins);
351 if (r < ins) return inserted + r;
352 }
353 inserted += ins;
354 di += ins;
355
356 // everything inserted?
357 if (inserted == n) return inserted;
358 src = next;
359 }
360
361 // insert remaining items
362 if (si < n) {
363 inserted += invoke_list_func(insert_array, list, di, src, n - si);
364 }
365
366 return inserted;
367 }
368
369 void cx_list_default_sort(struct cx_list_s *list) {
370 size_t elem_size = list->collection.elem_size;
371 size_t list_size = list->collection.size;
372 void *tmp = malloc(elem_size * list_size);
373 if (tmp == NULL) abort();
374
375 // copy elements from source array
376 char *loc = tmp;
377 for (size_t i = 0; i < list_size; i++) {
378 void *src = invoke_list_func(at, list, i);
379 memcpy(loc, src, elem_size);
380 loc += elem_size;
381 }
382
383 // qsort
384 qsort(tmp, list_size, elem_size,
385 list->collection.cmpfunc);
386
387 // copy elements back
388 loc = tmp;
389 for (size_t i = 0; i < list_size; i++) {
390 void *dest = invoke_list_func(at, list, i);
391 memcpy(dest, loc, elem_size);
392 loc += elem_size;
393 }
394
395 free(tmp);
396 }
397
398 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
399 if (i == j) return 0;
400 if (i >= list->collection.size) return 1;
401 if (j >= list->collection.size) return 1;
402
403 size_t elem_size = list->collection.elem_size;
404
405 void *tmp = malloc(elem_size);
406 if (tmp == NULL) return 1;
407
408 void *ip = invoke_list_func(at, list, i);
409 void *jp = invoke_list_func(at, list, j);
410
411 memcpy(tmp, ip, elem_size);
412 memcpy(ip, jp, elem_size);
413 memcpy(jp, tmp, elem_size);
414
415 free(tmp);
416
417 return 0;
418 }
419
277 void cxListDestroy(CxList *list) { 420 void cxListDestroy(CxList *list) {
278 list->cl->destructor(list); 421 list->cl->destructor(list);
279 } 422 }
280 423
281 int cxListCompare( 424 int cxListCompare(
282 CxList const *list, 425 const CxList *list,
283 CxList const *other 426 const CxList *other
284 ) { 427 ) {
285 if ( 428 bool cannot_optimize = false;
286 // if one is storing pointers but the other is not 429
287 (list->store_pointer ^ other->store_pointer) || 430 // if one is storing pointers but the other is not
288 431 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
289 // if one class is wrapped but the other is not 432
290 ((list->climpl == NULL) ^ (other->climpl == NULL)) || 433 // if one class is wrapped but the other is not
291 434 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
292 // if the resolved compare functions are not the same 435
293 ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != 436 // if the compare functions do not match or both are NULL
294 (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) 437 if (!cannot_optimize) {
295 ) { 438 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
439 list->climpl->compare : list->cl->compare);
440 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
441 other->climpl->compare : other->cl->compare);
442 cannot_optimize |= list_cmp != other_cmp;
443 cannot_optimize |= list_cmp == NULL;
444 }
445
446 if (cannot_optimize) {
296 // lists are definitely different - cannot use internal compare function 447 // lists are definitely different - cannot use internal compare function
297 if (list->size == other->size) { 448 if (list->collection.size == other->collection.size) {
298 CxIterator left = list->cl->iterator(list, 0, false); 449 CxIterator left = list->cl->iterator(list, 0, false);
299 CxIterator right = other->cl->iterator(other, 0, false); 450 CxIterator right = other->cl->iterator(other, 0, false);
300 for (size_t i = 0; i < list->size; i++) { 451 for (size_t i = 0; i < list->collection.size; i++) {
301 void *leftValue = cxIteratorCurrent(left); 452 void *leftValue = cxIteratorCurrent(left);
302 void *rightValue = cxIteratorCurrent(right); 453 void *rightValue = cxIteratorCurrent(right);
303 int d = list->cmpfunc(leftValue, rightValue); 454 int d = list->collection.cmpfunc(leftValue, rightValue);
304 if (d != 0) { 455 if (d != 0) {
305 return d; 456 return d;
306 } 457 }
307 cxIteratorNext(left); 458 cxIteratorNext(left);
308 cxIteratorNext(right); 459 cxIteratorNext(right);
309 } 460 }
310 return 0; 461 return 0;
311 } else { 462 } else {
312 return list->size < other->size ? -1 : 1; 463 return list->collection.size < other->collection.size ? -1 : 1;
313 } 464 }
314 } else { 465 } else {
315 // lists are compatible 466 // lists are compatible
316 return list->cl->compare(list, other); 467 return list->cl->compare(list, other);
317 } 468 }
318 } 469 }
319 470
320 CxMutIterator cxListMutIteratorAt( 471 CxIterator cxListMutIteratorAt(
321 CxList *list, 472 CxList *list,
322 size_t index 473 size_t index
323 ) { 474 ) {
324 CxIterator it = list->cl->iterator(list, index, false); 475 CxIterator it = list->cl->iterator(list, index, false);
325 it.base.mutating = true; 476 it.base.mutating = true;
326 477 return it;
327 // we know the iterators share the same memory layout 478 }
328 CxMutIterator iter; 479
329 memcpy(&iter, &it, sizeof(CxMutIterator)); 480 CxIterator cxListMutBackwardsIteratorAt(
330 return iter;
331 }
332
333 CxMutIterator cxListMutBackwardsIteratorAt(
334 CxList *list, 481 CxList *list,
335 size_t index 482 size_t index
336 ) { 483 ) {
337 CxIterator it = list->cl->iterator(list, index, true); 484 CxIterator it = list->cl->iterator(list, index, true);
338 it.base.mutating = true; 485 it.base.mutating = true;
339 486 return it;
340 // we know the iterators share the same memory layout 487 }
341 CxMutIterator iter;
342 memcpy(&iter, &it, sizeof(CxMutIterator));
343 return iter;
344 }

Mercurial Repository: idav

mercurial