comparison: src/ucx/linked_list.c
src/ucx/linked_list.c
- changeset 645
- 0c85c4cd0dd8
- parent 621
- 956c03c25edd
equal
deleted
inserted
replaced
| 644:e96e92e3508f | 645:0c85c4cd0dd8 |
|---|---|
| 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 } |
| 1250 cx_ll_at, | 1264 cx_ll_at, |
| 1251 cx_ll_find_remove, | 1265 cx_ll_find_remove, |
| 1252 cx_ll_sort, | 1266 cx_ll_sort, |
| 1253 cx_ll_compare, | 1267 cx_ll_compare, |
| 1254 cx_ll_reverse, | 1268 cx_ll_reverse, |
| 1269 NULL, // no overallocation supported | |
| 1255 cx_ll_iterator, | 1270 cx_ll_iterator, |
| 1256 }; | 1271 }; |
| 1257 | 1272 |
| 1258 CxList *cxLinkedListCreate( | 1273 CxList *cxLinkedListCreate( |
| 1259 const CxAllocator *allocator, | 1274 const CxAllocator *allocator, |
| 1264 allocator = cxDefaultAllocator; | 1279 allocator = cxDefaultAllocator; |
| 1265 } | 1280 } |
| 1266 | 1281 |
| 1267 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); | 1282 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
| 1268 if (list == NULL) return NULL; | 1283 if (list == NULL) return NULL; |
| 1269 list->extra_data_len = 0; | |
| 1270 list->loc_prev = 0; | 1284 list->loc_prev = 0; |
| 1271 list->loc_next = sizeof(void*); | 1285 list->loc_next = sizeof(void*); |
| 1272 list->loc_data = sizeof(void*)*2; | 1286 list->loc_data = sizeof(void*)*2; |
| 1287 list->loc_extra = -1; | |
| 1288 list->extra_data_len = 0; | |
| 1273 cx_list_init((CxList*)list, &cx_linked_list_class, | 1289 cx_list_init((CxList*)list, &cx_linked_list_class, |
| 1274 allocator, comparator, elem_size); | 1290 allocator, comparator, elem_size); |
| 1275 | 1291 |
| 1276 return (CxList *) list; | 1292 return (CxList *) list; |
| 1277 } | 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 } |
