idav: comparison ucx/array

-:c3f2f16fa4b8
+:dde28a806552
 }
 return cxReallocDefault(array, n);
 }
 CxArrayReallocator cx_array_default_reallocator_impl = {
-cx_array_default_realloc, NULL, NULL, 0, 0
+cx_array_default_realloc, NULL, NULL
 };
 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
 // Stack-aware array reallocator
 errno = EOVERFLOW;
 return NULL;
 }
 // retrieve the pointer to the actual allocator
-const CxAllocator *al = alloc->ptr1;
+const CxAllocator *al = alloc->allocator;
 // check if the array is still located on the stack
 void *newmem;
-if (array == alloc->ptr2) {
+if (array == alloc->stack_ptr) {
 newmem = cxMalloc(al, n);
 if (newmem != NULL && array != NULL) {
 memcpy(newmem, array, old_capacity*elem_size);
 }
 } else {
 return newmem;
 }
 struct cx_array_reallocator_s cx_array_reallocator(
 const struct cx_allocator_s *allocator,
-const void *stackmem
+const void *stack_ptr
 ) {
 if (allocator == NULL) {
 allocator = cxDefaultAllocator;
 }
 return (struct cx_array_reallocator_s) {
 cx_array_advanced_realloc,
-(void*) allocator, (void*) stackmem,
+allocator, stack_ptr,
-0, 0
 };
 }
 // LOW LEVEL ARRAY LIST FUNCTIONS
-static size_t cx_array_align_capacity(
+/**
-size_t cap,
+* Intelligently calculates a new capacity, reserving some more
-size_t alignment,
+* elements than required to prevent too many allocations.
-size_t max
+*
-) {
+* @param current_capacity the current capacity of the array
-if (cap > max - alignment) {
+* @param needed_capacity the required capacity of the array
-return cap;
+* @param maximum_capacity the maximum capacity (given by the data type)
+* @return the new capacity
+*/
+static size_t cx_array_grow_capacity(
+size_t current_capacity,
+size_t needed_capacity,
+size_t maximum_capacity
+) {
+if (current_capacity >= needed_capacity) {
+return current_capacity;
+}
+size_t cap = needed_capacity;
+size_t alignment;
+if (cap < 128) alignment = 16;
+else if (cap < 1024) alignment = 64;
+else if (cap < 8192) alignment = 512;
+else alignment = 1024;
+if (cap - 1 > maximum_capacity - alignment) {
+return maximum_capacity;
 } else {
 return cap - (cap % alignment) + alignment;
 }
 }
 // determine new capacity
 size_t newcap = oldsize + elem_count;
 // reallocate if possible
 if (newcap > oldcap) {
-// calculate new capacity (next number divisible by 16)
-newcap = cx_array_align_capacity(newcap, 16, max_size);
-// perform reallocation
 void *newmem = reallocator->realloc(
 *array, oldcap, newcap, elem_size, reallocator
 );
 if (newmem == NULL) {
 return 1; // LCOV_EXCL_LINE
 errno = EOVERFLOW;
 return 1;
 }
 // check if resize is required
-size_t minsize = index + elem_count;
+const size_t minsize = index + elem_count;
-size_t newsize = oldsize < minsize ? minsize : oldsize;
+const size_t newsize = oldsize < minsize ? minsize : oldsize;
-// reallocate if possible
+// reallocate if necessary
-size_t newcap = oldcap;
+const size_t newcap = cx_array_grow_capacity(oldcap, newsize, max_size);
-if (newsize > oldcap) {
+if (newcap > oldcap) {
-// check, if we need to repair the src pointer
+// check if we need to repair the src pointer
 uintptr_t targetaddr = (uintptr_t) *target;
 uintptr_t srcaddr = (uintptr_t) src;
 bool repairsrc = targetaddr <= srcaddr
 && srcaddr < targetaddr + oldcap * elem_size;
-// calculate new capacity (next number divisible by 16)
-newcap = cx_array_align_capacity(newsize, 16, max_size);
-assert(newcap > newsize);
 // perform reallocation
 void *newmem = reallocator->realloc(
 *target, oldcap, newcap, elem_size, reallocator
 );
 errno = EOVERFLOW;
 return 1;
 }
 // store some counts
-size_t old_size = *size;
+const size_t old_size = *size;
-size_t old_capacity = *capacity;
+const size_t old_capacity = *capacity;
 // the necessary capacity is the worst case assumption, including duplicates
-size_t needed_capacity = old_size + elem_count;
+const size_t needed_capacity = cx_array_grow_capacity(old_capacity,
+old_size + elem_count, SIZE_MAX);
 // if we need more than we have, try a reallocation
 if (needed_capacity > old_capacity) {
-size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
 void *new_mem = reallocator->realloc(
-*target, old_capacity, new_capacity, elem_size, reallocator
+*target, old_capacity, needed_capacity, elem_size, reallocator
 );
 if (new_mem == NULL) {
 // give it up right away, there is no contract
 // that requires us to insert as much as we can
 return 1;  // LCOV_EXCL_LINE
 }
 *target = new_mem;
-*capacity = new_capacity;
+*capacity = needed_capacity;
 }
 // now we have guaranteed that we can insert everything
 size_t new_size = old_size + elem_count;
 *size = new_size;
 // get a correctly typed pointer to the list
 cx_array_list *arl = (cx_array_list *) list;
 // guarantee enough capacity
 if (arl->capacity < list->collection.size + n) {
-size_t new_capacity = list->collection.size + n;
+const size_t new_capacity = cx_array_grow_capacity(arl->capacity,
-new_capacity = new_capacity - (new_capacity % 16) + 16;
+list->collection.size + n, SIZE_MAX);
 if (cxReallocateArray(
 list->collection.allocator,
 &arl->data, new_capacity,
 list->collection.elem_size)
 ) {
 static int cx_arl_insert_iter(
 struct cx_iterator_s *iter,
 const void *elem,
 int prepend
 ) {
-struct cx_list_s *list = iter->src_handle.m;
+struct cx_list_s *list = iter->src_handle;
 if (iter->index < list->collection.size) {
 if (cx_arl_insert_element(list,
 iter->index + 1 - prepend, elem) == NULL) {
 return 1;
 }
 }
 }
 static bool cx_arl_iter_valid(const void *it) {
 const struct cx_iterator_s *iter = it;
-const struct cx_list_s *list = iter->src_handle.c;
+const struct cx_list_s *list = iter->src_handle;
 return iter->index < list->collection.size;
 }
 static void *cx_arl_iter_current(const void *it) {
 const struct cx_iterator_s *iter = it;
 static void cx_arl_iter_next(void *it) {
 struct cx_iterator_s *iter = it;
 if (iter->base.remove) {
 iter->base.remove = false;
-cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
+cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
 iter->elem_count--;
 } else {
 iter->index++;
 iter->elem_handle =
 ((char *) iter->elem_handle)
-+ ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size;
++ ((const struct cx_list_s *) iter->src_handle)->collection.elem_size;
 }
 }
 static void cx_arl_iter_prev(void *it) {
 struct cx_iterator_s *iter = it;
-const cx_array_list *list = iter->src_handle.c;
 if (iter->base.remove) {
 iter->base.remove = false;
-cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
+cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
 iter->elem_count--;
 }
 iter->index--;
+cx_array_list *list = iter->src_handle;
 if (iter->index < list->base.collection.size) {
 iter->elem_handle = ((char *) list->data)
 + iter->index * list->base.collection.elem_size;
 }
 }
+static int cx_arl_change_capacity(
+struct cx_list_s *list,
+size_t new_capacity
+) {
+cx_array_list *arl = (cx_array_list *)list;
+return cxReallocateArray(list->collection.allocator,
+&arl->data, new_capacity, list->collection.elem_size);
+}
 static struct cx_iterator_s cx_arl_iterator(
 const struct cx_list_s *list,
 size_t index,
 bool backwards
 ) {
 struct cx_iterator_s iter;
 iter.index = index;
-iter.src_handle.c = list;
+iter.src_handle = (void*)list;
 iter.elem_handle = cx_arl_at(list, index);
 iter.elem_size = list->collection.elem_size;
 iter.elem_count = list->collection.size;
 iter.base.valid = cx_arl_iter_valid;
 iter.base.current = cx_arl_iter_current;
 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
 iter.base.remove = false;
-iter.base.mutating = false;
+iter.base.allow_remove = true;
 return iter;
 }
 static cx_list_class cx_array_list_class = {
 cx_arl_at,
 cx_arl_find_remove,
 cx_arl_sort,
 cx_arl_compare,
 cx_arl_reverse,
+cx_arl_change_capacity,
 cx_arl_iterator,
 };
 CxList *cxArrayListCreate(
 const CxAllocator *allocator,

comparison: ucx/array_list.c

ucx/array_list.c

Mercurial > hg > idav / file comparison

comparison: ucx/array_list.c

ucx/array_list.c