Mercurial > hg > webserver / file comparison

comparison: src/ucx/list.c

src/ucx/list.c

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

Mercurial Repository: webserver

mercurial