comparison: ucx/linked_list.c
ucx/linked_list.c
- changeset 23
- b26390e77237
- parent 22
- 112b85020dc9
equal
deleted
inserted
replaced
| 22:112b85020dc9 | 23:b26390e77237 |
|---|---|
| 28 | 28 |
| 29 #include "cx/linked_list.h" | 29 #include "cx/linked_list.h" |
| 30 #include "cx/compare.h" | 30 #include "cx/compare.h" |
| 31 #include <string.h> | 31 #include <string.h> |
| 32 #include <assert.h> | 32 #include <assert.h> |
| 33 | |
| 34 #if __STDC_VERSION__ < 202311L | |
| 35 // we cannot simply include stdalign.h | |
| 36 // because Solaris is not entirely C11 complaint | |
| 37 #ifndef __alignof_is_defined | |
| 38 #define alignof _Alignof | |
| 39 #define __alignof_is_defined 1 | |
| 40 #endif | |
| 41 #endif | |
| 33 | 42 |
| 34 // LOW LEVEL LINKED LIST FUNCTIONS | 43 // LOW LEVEL LINKED LIST FUNCTIONS |
| 35 | 44 |
| 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) | 45 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
| 37 #define ll_prev(node) CX_LL_PTR(node, loc_prev) | 46 #define ll_prev(node) CX_LL_PTR(node, loc_prev) |
| 514 void **end | 523 void **end |
| 515 ) { | 524 ) { |
| 516 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; | 525 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; |
| 517 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? | 526 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? |
| 518 cxMallocDefault(sizeof(void *) * length) : sbo; | 527 cxMallocDefault(sizeof(void *) * length) : sbo; |
| 519 if (sorted == NULL) abort(); | 528 if (sorted == NULL) abort(); // LCOV_EXCL_LINE |
| 520 void *rc, *lc; | 529 void *rc, *lc; |
| 521 | 530 |
| 522 lc = ls; | 531 lc = ls; |
| 523 rc = le; | 532 rc = le; |
| 524 size_t n = 0; | 533 size_t n = 0; |
| 690 return cx_linked_list_at(list->begin, 0, list->loc_next, index); | 699 return cx_linked_list_at(list->begin, 0, list->loc_next, index); |
| 691 } | 700 } |
| 692 } | 701 } |
| 693 | 702 |
| 694 static void *cx_ll_malloc_node(const cx_linked_list *list) { | 703 static void *cx_ll_malloc_node(const cx_linked_list *list) { |
| 695 return cxZalloc(list->base.collection.allocator, | 704 size_t n; |
| 696 list->loc_data + list->base.collection.elem_size + list->extra_data_len); | 705 if (list->extra_data_len == 0) { |
| 706 n = list->loc_data + list->base.collection.elem_size; | |
| 707 } else { | |
| 708 n = list->loc_extra + list->extra_data_len; | |
| 709 } | |
| 710 return cxZalloc(list->base.collection.allocator, n); | |
| 697 } | 711 } |
| 698 | 712 |
| 699 static int cx_ll_insert_at( | 713 static int cx_ll_insert_at( |
| 700 struct cx_list_s *list, | 714 struct cx_list_s *list, |
| 701 void *node, | 715 void *node, |
| 1213 } | 1227 } |
| 1214 } | 1228 } |
| 1215 return result; | 1229 return result; |
| 1216 } else { | 1230 } else { |
| 1217 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { | 1231 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { |
| 1218 return 1; | 1232 return 1; // LCOV_EXCL_LINE |
| 1219 } | 1233 } |
| 1220 iter->elem_count++; | 1234 iter->elem_count++; |
| 1221 iter->index = list->collection.size; | 1235 iter->index = list->collection.size; |
| 1222 return 0; | 1236 return 0; |
| 1223 } | 1237 } |
| 1265 allocator = cxDefaultAllocator; | 1279 allocator = cxDefaultAllocator; |
| 1266 } | 1280 } |
| 1267 | 1281 |
| 1268 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); | 1282 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
| 1269 if (list == NULL) return NULL; | 1283 if (list == NULL) return NULL; |
| 1270 list->extra_data_len = 0; | |
| 1271 list->loc_prev = 0; | 1284 list->loc_prev = 0; |
| 1272 list->loc_next = sizeof(void*); | 1285 list->loc_next = sizeof(void*); |
| 1273 list->loc_data = sizeof(void*)*2; | 1286 list->loc_data = sizeof(void*)*2; |
| 1287 list->loc_extra = -1; | |
| 1288 list->extra_data_len = 0; | |
| 1274 cx_list_init((CxList*)list, &cx_linked_list_class, | 1289 cx_list_init((CxList*)list, &cx_linked_list_class, |
| 1275 allocator, comparator, elem_size); | 1290 allocator, comparator, elem_size); |
| 1276 | 1291 |
| 1277 return (CxList *) list; | 1292 return (CxList *) list; |
| 1278 } | 1293 } |
| 1294 | |
| 1295 void cx_linked_list_extra_data(cx_linked_list *list, size_t len) { | |
| 1296 list->extra_data_len = len; | |
| 1297 | |
| 1298 off_t loc_extra = list->loc_data + list->base.collection.elem_size; | |
| 1299 size_t alignment = alignof(void*); | |
| 1300 size_t padding = alignment - (loc_extra % alignment); | |
| 1301 list->loc_extra = loc_extra + padding; | |
| 1302 } |
