comparison: ucx/linked_list.c
ucx/linked_list.c
- changeset 113
- dde28a806552
- parent 112
- c3f2f16fa4b8
equal
deleted
inserted
replaced
| 112:c3f2f16fa4b8 | 113:dde28a806552 |
|---|---|
| 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 #include <unistd.h> | |
| 34 | 33 |
| 35 // LOW LEVEL LINKED LIST FUNCTIONS | 34 // LOW LEVEL LINKED LIST FUNCTIONS |
| 36 | 35 |
| 37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) | 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) |
| 38 #define ll_prev(node) CX_LL_PTR(node, loc_prev) | 37 #define ll_prev(node) CX_LL_PTR(node, loc_prev) |
| 473 } | 472 } |
| 474 | 473 |
| 475 return removed; | 474 return removed; |
| 476 } | 475 } |
| 477 | 476 |
| 477 void cx_linked_list_remove( | |
| 478 void **begin, | |
| 479 void **end, | |
| 480 ptrdiff_t loc_prev, | |
| 481 ptrdiff_t loc_next, | |
| 482 void *node | |
| 483 ) { | |
| 484 cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1); | |
| 485 } | |
| 486 | |
| 478 size_t cx_linked_list_size( | 487 size_t cx_linked_list_size( |
| 479 const void *node, | 488 const void *node, |
| 480 ptrdiff_t loc_next | 489 ptrdiff_t loc_next |
| 481 ) { | 490 ) { |
| 482 assert(loc_next >= 0); | 491 assert(loc_next >= 0); |
| 740 node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next); | 749 node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next); |
| 741 | 750 |
| 742 // we can add the remaining nodes and immediately advance to the inserted node | 751 // we can add the remaining nodes and immediately advance to the inserted node |
| 743 const char *source = array; | 752 const char *source = array; |
| 744 for (size_t i = 1; i < n; i++) { | 753 for (size_t i = 1; i < n; i++) { |
| 745 source += list->collection.elem_size; | 754 if (source != NULL) { |
| 755 source += list->collection.elem_size; | |
| 756 } | |
| 746 if (0 != cx_ll_insert_at(list, node, source)) return i; | 757 if (0 != cx_ll_insert_at(list, node, source)) return i; |
| 747 node = CX_LL_PTR(node, ll->loc_next); | 758 node = CX_LL_PTR(node, ll->loc_next); |
| 748 } | 759 } |
| 749 return n; | 760 return n; |
| 750 } | 761 } |
| 1114 return iter->elem_handle != NULL; | 1125 return iter->elem_handle != NULL; |
| 1115 } | 1126 } |
| 1116 | 1127 |
| 1117 static void cx_ll_iter_next(void *it) { | 1128 static void cx_ll_iter_next(void *it) { |
| 1118 struct cx_iterator_s *iter = it; | 1129 struct cx_iterator_s *iter = it; |
| 1130 cx_linked_list *ll = iter->src_handle; | |
| 1119 if (iter->base.remove) { | 1131 if (iter->base.remove) { |
| 1120 iter->base.remove = false; | 1132 iter->base.remove = false; |
| 1121 struct cx_list_s *list = iter->src_handle.m; | 1133 struct cx_list_s *list = iter->src_handle; |
| 1122 cx_linked_list *ll = iter->src_handle.m; | |
| 1123 char *node = iter->elem_handle; | 1134 char *node = iter->elem_handle; |
| 1124 iter->elem_handle = CX_LL_PTR(node, ll->loc_next); | 1135 iter->elem_handle = CX_LL_PTR(node, ll->loc_next); |
| 1125 cx_invoke_destructor(list, node + ll->loc_data); | 1136 cx_invoke_destructor(list, node + ll->loc_data); |
| 1126 cx_linked_list_remove(&ll->begin, &ll->end, | 1137 cx_linked_list_remove(&ll->begin, &ll->end, |
| 1127 ll->loc_prev, ll->loc_next, node); | 1138 ll->loc_prev, ll->loc_next, node); |
| 1128 list->collection.size--; | 1139 list->collection.size--; |
| 1129 iter->elem_count--; | 1140 iter->elem_count--; |
| 1130 cxFree(list->collection.allocator, node); | 1141 cxFree(list->collection.allocator, node); |
| 1131 } else { | 1142 } else { |
| 1132 const cx_linked_list *ll = iter->src_handle.c; | |
| 1133 iter->index++; | 1143 iter->index++; |
| 1134 void *node = iter->elem_handle; | 1144 void *node = iter->elem_handle; |
| 1135 iter->elem_handle = CX_LL_PTR(node, ll->loc_next); | 1145 iter->elem_handle = CX_LL_PTR(node, ll->loc_next); |
| 1136 } | 1146 } |
| 1137 } | 1147 } |
| 1138 | 1148 |
| 1139 static void cx_ll_iter_prev(void *it) { | 1149 static void cx_ll_iter_prev(void *it) { |
| 1140 struct cx_iterator_s *iter = it; | 1150 struct cx_iterator_s *iter = it; |
| 1151 cx_linked_list *ll = iter->src_handle; | |
| 1141 if (iter->base.remove) { | 1152 if (iter->base.remove) { |
| 1142 iter->base.remove = false; | 1153 iter->base.remove = false; |
| 1143 struct cx_list_s *list = iter->src_handle.m; | 1154 struct cx_list_s *list = iter->src_handle; |
| 1144 cx_linked_list *ll = iter->src_handle.m; | |
| 1145 char *node = iter->elem_handle; | 1155 char *node = iter->elem_handle; |
| 1146 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); | 1156 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); |
| 1147 iter->index--; | 1157 iter->index--; |
| 1148 cx_invoke_destructor(list, node + ll->loc_data); | 1158 cx_invoke_destructor(list, node + ll->loc_data); |
| 1149 cx_linked_list_remove(&ll->begin, &ll->end, | 1159 cx_linked_list_remove(&ll->begin, &ll->end, |
| 1150 ll->loc_prev, ll->loc_next, node); | 1160 ll->loc_prev, ll->loc_next, node); |
| 1151 list->collection.size--; | 1161 list->collection.size--; |
| 1152 iter->elem_count--; | 1162 iter->elem_count--; |
| 1153 cxFree(list->collection.allocator, node); | 1163 cxFree(list->collection.allocator, node); |
| 1154 } else { | 1164 } else { |
| 1155 const cx_linked_list *ll = iter->src_handle.c; | |
| 1156 iter->index--; | 1165 iter->index--; |
| 1157 char *node = iter->elem_handle; | 1166 char *node = iter->elem_handle; |
| 1158 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); | 1167 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); |
| 1159 } | 1168 } |
| 1160 } | 1169 } |
| 1161 | 1170 |
| 1162 static void *cx_ll_iter_current(const void *it) { | 1171 static void *cx_ll_iter_current(const void *it) { |
| 1163 const struct cx_iterator_s *iter = it; | 1172 const struct cx_iterator_s *iter = it; |
| 1164 const cx_linked_list *ll = iter->src_handle.c; | 1173 const cx_linked_list *ll = iter->src_handle; |
| 1165 char *node = iter->elem_handle; | 1174 char *node = iter->elem_handle; |
| 1166 return node + ll->loc_data; | 1175 return node + ll->loc_data; |
| 1167 } | 1176 } |
| 1168 | 1177 |
| 1169 static CxIterator cx_ll_iterator( | 1178 static CxIterator cx_ll_iterator( |
| 1171 size_t index, | 1180 size_t index, |
| 1172 bool backwards | 1181 bool backwards |
| 1173 ) { | 1182 ) { |
| 1174 CxIterator iter; | 1183 CxIterator iter; |
| 1175 iter.index = index; | 1184 iter.index = index; |
| 1176 iter.src_handle.c = list; | 1185 iter.src_handle = (void*)list; |
| 1177 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index); | 1186 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index); |
| 1178 iter.elem_size = list->collection.elem_size; | 1187 iter.elem_size = list->collection.elem_size; |
| 1179 iter.elem_count = list->collection.size; | 1188 iter.elem_count = list->collection.size; |
| 1180 iter.base.valid = cx_ll_iter_valid; | 1189 iter.base.valid = cx_ll_iter_valid; |
| 1181 iter.base.current = cx_ll_iter_current; | 1190 iter.base.current = cx_ll_iter_current; |
| 1182 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; | 1191 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; |
| 1183 iter.base.mutating = false; | 1192 iter.base.allow_remove = true; |
| 1184 iter.base.remove = false; | 1193 iter.base.remove = false; |
| 1185 return iter; | 1194 return iter; |
| 1186 } | 1195 } |
| 1187 | 1196 |
| 1188 static int cx_ll_insert_iter( | 1197 static int cx_ll_insert_iter( |
| 1189 CxIterator *iter, | 1198 CxIterator *iter, |
| 1190 const void *elem, | 1199 const void *elem, |
| 1191 int prepend | 1200 int prepend |
| 1192 ) { | 1201 ) { |
| 1193 struct cx_list_s *list = iter->src_handle.m; | 1202 struct cx_list_s *list = iter->src_handle; |
| 1194 cx_linked_list *ll = iter->src_handle.m; | 1203 cx_linked_list *ll = iter->src_handle; |
| 1195 void *node = iter->elem_handle; | 1204 void *node = iter->elem_handle; |
| 1196 if (node != NULL) { | 1205 if (node != NULL) { |
| 1197 assert(prepend >= 0 && prepend <= 1); | 1206 assert(prepend >= 0 && prepend <= 1); |
| 1198 void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)}; | 1207 void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)}; |
| 1199 int result = cx_ll_insert_at(list, choice[prepend], elem); | 1208 int result = cx_ll_insert_at(list, choice[prepend], elem); |
| 1241 cx_ll_at, | 1250 cx_ll_at, |
| 1242 cx_ll_find_remove, | 1251 cx_ll_find_remove, |
| 1243 cx_ll_sort, | 1252 cx_ll_sort, |
| 1244 cx_ll_compare, | 1253 cx_ll_compare, |
| 1245 cx_ll_reverse, | 1254 cx_ll_reverse, |
| 1255 NULL, // no overallocation supported | |
| 1246 cx_ll_iterator, | 1256 cx_ll_iterator, |
| 1247 }; | 1257 }; |
| 1248 | 1258 |
| 1249 CxList *cxLinkedListCreate( | 1259 CxList *cxLinkedListCreate( |
| 1250 const CxAllocator *allocator, | 1260 const CxAllocator *allocator, |
