idav: comparison ucx/linked

-:d2bd73d28ff1
+:7b3a3130be44
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 #include "cx/linked_list.h"
-#include "cx/utils.h"
 #include "cx/compare.h"
 #include <string.h>
 #include <assert.h>
 // LOW LEVEL LINKED LIST FUNCTIONS
 const void *node = start;
 ssize_t index = 0;
 do {
 void *current = ll_data(node);
 if (cmp_func(current, elem) == 0) {
-*result = (void*) node;
+*result = (void *) node;
 return index;
 }
 node = ll_advance(node);
 index++;
 } while (node != NULL);
 *end = cx_linked_list_last(
 dest != NULL ? dest : dest_prev, loc_next);
 }
 }
-void cx_linked_list_remove(
+size_t cx_linked_list_remove_chain(
 void **begin,
 void **end,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next,
-void *node
+void *node,
+size_t num
 ) {
 assert(node != NULL);
 assert(loc_next >= 0);
 assert(loc_prev >= 0 || begin != NULL);
+// easy exit
+if (num == 0) return 0;
 // find adjacent nodes
-void *next = ll_next(node);
 void *prev;
 if (loc_prev >= 0) {
 prev = ll_prev(node);
 } else {
 prev = cx_linked_list_prev(*begin, loc_next, node);
+}
+void *next = ll_next(node);
+size_t removed = 1;
+for (; removed < num && next != NULL ; removed++) {
+next = ll_next(next);
 }
 // update next pointer of prev node, or set begin
 if (prev == NULL) {
 if (begin != NULL) {
 *end = prev;
 }
 } else if (loc_prev >= 0) {
 ll_prev(next) = prev;
 }
+return removed;
 }
 size_t cx_linked_list_size(
 const void *node,
 ptrdiff_t loc_next
 n++;
 }
 // Update pointer
 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
-cx_for_n (i, length - 1) {
+for (size_t i = 0 ; i < length - 1; i++) {
 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next);
 }
 ll_next(sorted[length - 1]) = NULL;
 *begin = sorted[0];
-*end = sorted[length-1];
+*end = sorted[length - 1];
 if (sorted != sbo) {
 free(sorted);
 }
 }
 // find position efficiently
 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
 // perform first insert
-if (0 != cx_ll_insert_at(list, node, array)) {
+if (0 != cx_ll_insert_at(list, node, array)) return 1;
-return 1;
-}
 // is there more?
 if (n == 1) return 1;
 // we now know exactly where we are
 // we can add the remaining nodes and immediately advance to the inserted node
 const char *source = array;
 for (size_t i = 1; i < n; i++) {
 source += list->collection.elem_size;
-if (0 != cx_ll_insert_at(list, node, source)) {
+if (0 != cx_ll_insert_at(list, node, source)) return i;
-return i;
-}
 node = node->next;
 }
 return n;
 }
 list->collection.size += inserted;
 return inserted;
 }
-static int cx_ll_remove(
+static size_t cx_ll_remove(
 struct cx_list_s *list,
-size_t index
+size_t index,
+size_t num,
+void *targetbuf
 ) {
 cx_linked_list *ll = (cx_linked_list *) list;
 cx_linked_list_node *node = cx_ll_node_at(ll, index);
 // out-of-bounds check
-if (node == NULL) return 1;
+if (node == NULL) return 0;
-// element destruction
-cx_invoke_destructor(list, node->payload);
 // remove
-cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+size_t removed = cx_linked_list_remove_chain(
-CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+(void **) &ll->begin,
+(void **) &ll->end,
+CX_LL_LOC_PREV,
+CX_LL_LOC_NEXT,
+node,
+num
+);
 // adjust size
-list->collection.size--;
+list->collection.size -= removed;
-// free and return
+// copy or destroy the removed chain
-cxFree(list->collection.allocator, node);
+if (targetbuf == NULL) {
+cx_linked_list_node *n = node;
-return 0;
+for (size_t i = 0; i < removed; i++) {
+// element destruction
+cx_invoke_destructor(list, n->payload);
+// free the node and advance
+void *next = n->next;
+cxFree(list->collection.allocator, n);
+n = next;
+}
+} else {
+char *dest = targetbuf;
+cx_linked_list_node *n = node;
+for (size_t i = 0; i < removed; i++) {
+// copy payload
+memcpy(dest, n->payload, list->collection.elem_size);
+// advance target buffer
+dest += list->collection.elem_size;
+// free the node and advance
+void *next = n->next;
+cxFree(list->collection.allocator, n);
+n = next;
+}
+}
+return removed;
 }
 static void cx_ll_clear(struct cx_list_s *list) {
 if (list->collection.size == 0) return;
 }
 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
 #endif
-unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
+const unsigned cx_linked_list_swap_sbo_size = CX_LINKED_LIST_SWAP_SBO_SIZE;
 static int cx_ll_swap(
 struct cx_list_s *list,
 size_t i,
 size_t j
 right = j;
 } else {
 left = j;
 right = i;
 }
-cx_linked_list_node *nleft, *nright;
+cx_linked_list_node *nleft = NULL, *nright = NULL;
 if (left < mid && right < mid) {
 // case 1: both items left from mid
 nleft = cx_ll_node_at(ll, left);
 assert(nleft != NULL);
 nright = nleft;

comparison: ucx/linked_list.c

ucx/linked_list.c

Mercurial > hg > idav / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c