toolkit: comparison ucx/list.c

-:38cb8e3992e8
+:ce13a778654a
 // <editor-fold desc="Store Pointers Functionality">
 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
 static int cx_pl_cmpfunc(
-void const *l,
+const void *l,
-void const *r
+const void *r
 ) {
 void *const *lptr = l;
 void *const *rptr = r;
-void const *left = lptr == NULL ? NULL : *lptr;
+const void *left = lptr == NULL ? NULL : *lptr;
-void const *right = rptr == NULL ? NULL : *rptr;
+const void *right = rptr == NULL ? NULL : *rptr;
 return cx_pl_cmpfunc_impl(left, right);
 }
-static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) {
+static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
 // cast away const - this is the hacky thing
-struct cx_list_s *l = (struct cx_list_s *) list;
+struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
 cx_pl_cmpfunc_impl = l->cmpfunc;
 l->cmpfunc = cx_pl_cmpfunc;
 }
-static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) {
+static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
 // cast away const - this is the hacky thing
-struct cx_list_s *l = (struct cx_list_s *) list;
+struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
 l->cmpfunc = cx_pl_cmpfunc_impl;
 }
 static void cx_pl_destructor(struct cx_list_s *list) {
 list->climpl->destructor(list);
 }
 static int cx_pl_insert_element(
 struct cx_list_s *list,
 size_t index,
-void const *element
+const void *element
 ) {
 return list->climpl->insert_element(list, index, &element);
 }
 static size_t cx_pl_insert_array(
 struct cx_list_s *list,
 size_t index,
-void const *array,
+const void *array,
 size_t n
 ) {
 return list->climpl->insert_array(list, index, array, n);
 }
+static size_t cx_pl_insert_sorted(
+struct cx_list_s *list,
+const void *array,
+size_t n
+) {
+cx_pl_hack_cmpfunc(list);
+size_t result = list->climpl->insert_sorted(list, array, n);
+cx_pl_unhack_cmpfunc(list);
+return result;
+}
 static int cx_pl_insert_iter(
-struct cx_mut_iterator_s *iter,
+struct cx_iterator_s *iter,
-void const *elem,
+const void *elem,
 int prepend
 ) {
-struct cx_list_s *list = iter->src_handle;
+struct cx_list_s *list = iter->src_handle.m;
 return list->climpl->insert_iter(iter, &elem, prepend);
 }
 static int cx_pl_remove(
 struct cx_list_s *list,
 ) {
 return list->climpl->swap(list, i, j);
 }
 static void *cx_pl_at(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
 size_t index
 ) {
 void **ptr = list->climpl->at(list, index);
 return ptr == NULL ? NULL : *ptr;
 }
 static ssize_t cx_pl_find_remove(
 struct cx_list_s *list,
-void const *elem,
+const void *elem,
 bool remove
 ) {
 cx_pl_hack_cmpfunc(list);
 ssize_t ret = list->climpl->find_remove(list, &elem, remove);
 cx_pl_unhack_cmpfunc(list);
 list->climpl->sort(list);
 cx_pl_unhack_cmpfunc(list);
 }
 static int cx_pl_compare(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
-struct cx_list_s const *other
+const struct cx_list_s *other
 ) {
 cx_pl_hack_cmpfunc(list);
 int ret = list->climpl->compare(list, other);
 cx_pl_unhack_cmpfunc(list);
 return ret;
 static void cx_pl_reverse(struct cx_list_s *list) {
 list->climpl->reverse(list);
 }
-static void *cx_pl_iter_current(void const *it) {
+static void *cx_pl_iter_current(const void *it) {
-struct cx_iterator_s const *iter = it;
+const struct cx_iterator_s *iter = it;
 void **ptr = iter->base.current_impl(it);
 return ptr == NULL ? NULL : *ptr;
 }
 static struct cx_iterator_s cx_pl_iterator(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
 size_t index,
 bool backwards
 ) {
 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
 iter.base.current_impl = iter.base.current;
 static cx_list_class cx_pointer_list_class = {
 cx_pl_destructor,
 cx_pl_insert_element,
 cx_pl_insert_array,
+cx_pl_insert_sorted,
 cx_pl_insert_iter,
 cx_pl_remove,
 cx_pl_clear,
 cx_pl_swap,
 cx_pl_at,
 cx_pl_reverse,
 cx_pl_iterator,
 };
 void cxListStoreObjects(CxList *list) {
-list->store_pointer = false;
+list->collection.store_pointer = false;
 if (list->climpl != NULL) {
 list->cl = list->climpl;
 list->climpl = NULL;
 }
 }
 void cxListStorePointers(CxList *list) {
-list->item_size = sizeof(void *);
+list->collection.elem_size = sizeof(void *);
-list->store_pointer = true;
+list->collection.store_pointer = true;
 list->climpl = list->cl;
 list->cl = &cx_pointer_list_class;
 }
 // </editor-fold>
 static void cx_emptyl_noop(__attribute__((__unused__)) CxList *list) {
 // this is a noop, but MUST be implemented
 }
 static void *cx_emptyl_at(
-__attribute__((__unused__)) struct cx_list_s const *list,
+__attribute__((__unused__)) const struct cx_list_s *list,
 __attribute__((__unused__)) size_t index
 ) {
 return NULL;
 }
 static ssize_t cx_emptyl_find_remove(
 __attribute__((__unused__)) struct cx_list_s *list,
-__attribute__((__unused__)) void const *elem,
+__attribute__((__unused__)) const void *elem,
 __attribute__((__unused__)) bool remove
 ) {
 return -1;
 }
-static int cx_emptyl_compare(
+static bool cx_emptyl_iter_valid(__attribute__((__unused__)) const void *iter) {
-__attribute__((__unused__)) struct cx_list_s const *list,
-struct cx_list_s const *other
-) {
-if (other->size == 0) return 0;
-return -1;
-}
-static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) {
 return false;
 }
 static CxIterator cx_emptyl_iterator(
-struct cx_list_s const *list,
+const struct cx_list_s *list,
 size_t index,
 __attribute__((__unused__)) bool backwards
 ) {
 CxIterator iter = {0};
-iter.src_handle = list;
+iter.src_handle.c = list;
 iter.index = index;
 iter.base.valid = cx_emptyl_iter_valid;
 return iter;
 }
 cx_emptyl_noop,
 NULL,
 NULL,
 NULL,
 NULL,
+NULL,
 cx_emptyl_noop,
 NULL,
 cx_emptyl_at,
 cx_emptyl_find_remove,
 cx_emptyl_noop,
-cx_emptyl_compare,
+NULL,
 cx_emptyl_noop,
 cx_emptyl_iterator,
 };
 CxList cx_empty_list = {
-NULL,
+{
 NULL,
-0,
+NULL,
 0,
-NULL,
+0,
 NULL,
 NULL,
-false,
+NULL,
+false
+},
 &cx_empty_list_class,
 NULL
 };
 CxList *const cxEmptyList = &cx_empty_list;
 // </editor-fold>
+#define invoke_list_func(name, list, ...) \
+((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
+(list, __VA_ARGS__)
+size_t cx_list_default_insert_array(
+struct cx_list_s *list,
+size_t index,
+const void *data,
+size_t n
+) {
+size_t elem_size = list->collection.elem_size;
+const char *src = data;
+size_t i = 0;
+for (; i < n; i++) {
+if (0 != invoke_list_func(insert_element,
+list, index + i, src + (i * elem_size))) {
+return i;
+}
+}
+return i;
+}
+size_t cx_list_default_insert_sorted(
+struct cx_list_s *list,
+const void *sorted_data,
+size_t n
+) {
+// corner case
+if (n == 0) return 0;
+size_t elem_size = list->collection.elem_size;
+cx_compare_func cmp = list->collection.cmpfunc;
+const char *src = sorted_data;
+// track indices and number of inserted items
+size_t di = 0, si = 0, inserted = 0;
+// search the list for insertion points
+for (; di < list->collection.size; di++) {
+const void *list_elm = invoke_list_func(at, list, di);
+// compare current list element with first source element
+// if less or equal, skip
+if (cmp(list_elm, src) <= 0) {
+continue;
+}
+// determine number of consecutive elements that can be inserted
+size_t ins = 1;
+const char *next = src;
+while (++si < n) {
+next += elem_size;
+// once we become larger than the list elem, break
+if (cmp(list_elm, next) <= 0) {
+break;
+}
+// otherwise, we can insert one more
+ins++;
+}
+// insert the elements at location si
+if (ins == 1) {
+if (0 != invoke_list_func(insert_element,
+list, di, src))
+return inserted;
+} else {
+size_t r = invoke_list_func(insert_array, list, di, src, ins);
+if (r < ins) return inserted + r;
+}
+inserted += ins;
+di += ins;
+// everything inserted?
+if (inserted == n) return inserted;
+src = next;
+}
+// insert remaining items
+if (si < n) {
+inserted += invoke_list_func(insert_array, list, di, src, n - si);
+}
+return inserted;
+}
+void cx_list_default_sort(struct cx_list_s *list) {
+size_t elem_size = list->collection.elem_size;
+size_t list_size = list->collection.size;
+void *tmp = malloc(elem_size * list_size);
+if (tmp == NULL) abort();
+// copy elements from source array
+char *loc = tmp;
+for (size_t i = 0; i < list_size; i++) {
+void *src = invoke_list_func(at, list, i);
+memcpy(loc, src, elem_size);
+loc += elem_size;
+}
+// qsort
+qsort(tmp, list_size, elem_size,
+list->collection.cmpfunc);
+// copy elements back
+loc = tmp;
+for (size_t i = 0; i < list_size; i++) {
+void *dest = invoke_list_func(at, list, i);
+memcpy(dest, loc, elem_size);
+loc += elem_size;
+}
+free(tmp);
+}
+int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
+if (i == j) return 0;
+if (i >= list->collection.size) return 1;
+if (j >= list->collection.size) return 1;
+size_t elem_size = list->collection.elem_size;
+void *tmp = malloc(elem_size);
+if (tmp == NULL) return 1;
+void *ip = invoke_list_func(at, list, i);
+void *jp = invoke_list_func(at, list, j);
+memcpy(tmp, ip, elem_size);
+memcpy(ip, jp, elem_size);
+memcpy(jp, tmp, elem_size);
+free(tmp);
+return 0;
+}
 void cxListDestroy(CxList *list) {
 list->cl->destructor(list);
 }
 int cxListCompare(
-CxList const *list,
+const CxList *list,
-CxList const *other
+const CxList *other
 ) {
-if (
+bool cannot_optimize = false;
-// if one is storing pointers but the other is not
-(list->store_pointer ^ other->store_pointer) ||
+// if one is storing pointers but the other is not
+cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
-// if one class is wrapped but the other is not
-((list->climpl == NULL) ^ (other->climpl == NULL)) ||
+// if one class is wrapped but the other is not
+cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
-// if the resolved compare functions are not the same
-((list->climpl != NULL ? list->climpl->compare : list->cl->compare) !=
+// if the compare functions do not match or both are NULL
-(other->climpl != NULL ? other->climpl->compare : other->cl->compare))
+if (!cannot_optimize) {
-) {
+cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
+list->climpl->compare : list->cl->compare);
+cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
+other->climpl->compare : other->cl->compare);
+cannot_optimize |= list_cmp != other_cmp;
+cannot_optimize |= list_cmp == NULL;
+}
+if (cannot_optimize) {
 // lists are definitely different - cannot use internal compare function
-if (list->size == other->size) {
+if (list->collection.size == other->collection.size) {
 CxIterator left = list->cl->iterator(list, 0, false);
 CxIterator right = other->cl->iterator(other, 0, false);
-for (size_t i = 0; i < list->size; i++) {
+for (size_t i = 0; i < list->collection.size; i++) {
 void *leftValue = cxIteratorCurrent(left);
 void *rightValue = cxIteratorCurrent(right);
-int d = list->cmpfunc(leftValue, rightValue);
+int d = list->collection.cmpfunc(leftValue, rightValue);
 if (d != 0) {
 return d;
 }
 cxIteratorNext(left);
 cxIteratorNext(right);
 }
 return 0;
 } else {
-return list->size < other->size ? -1 : 1;
+return list->collection.size < other->collection.size ? -1 : 1;
 }
 } else {
 // lists are compatible
 return list->cl->compare(list, other);
 }
 }
-CxMutIterator cxListMutIteratorAt(
+CxIterator cxListMutIteratorAt(
 CxList *list,
 size_t index
 ) {
 CxIterator it = list->cl->iterator(list, index, false);
 it.base.mutating = true;
+return it;
-// we know the iterators share the same memory layout
+}
-CxMutIterator iter;
-memcpy(&iter, &it, sizeof(CxMutIterator));
+CxIterator cxListMutBackwardsIteratorAt(
-return iter;
-}
-CxMutIterator cxListMutBackwardsIteratorAt(
 CxList *list,
 size_t index
 ) {
 CxIterator it = list->cl->iterator(list, index, true);
 it.base.mutating = true;
+return it;
-// we know the iterators share the same memory layout
+}
-CxMutIterator iter;
-memcpy(&iter, &it, sizeof(CxMutIterator));
-return iter;
-}

Mercurial > hg > toolkit / file comparison

comparison: ucx/list.c

ucx/list.c