# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1562271795 -7200
# Node ID 6d7aa8a1a3b300d42112d57a7248d899b648cf6e
# Parent  872ae61c89457a3c09e528f7e4813650f1d19215
implements ucx_array_sort()

diff -r 872ae61c8945 -r 6d7aa8a1a3b3 src/array.c
--- a/src/array.c	Thu Jul 04 21:31:45 2019 +0200
+++ b/src/array.c	Thu Jul 04 22:23:15 2019 +0200
@@ -27,7 +27,9 @@
  */
 
 #include "ucx/array.h"
+#include "ucx/utils.h"
 
+#include <string.h>
 
 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
@@ -37,71 +39,278 @@
         UcxAllocator* allocator) {
     UcxArray array;
     
+    array.allocator = allocator;
+    array.elemsize = elemsize;
+    array.size = 0;
+    array.data = alcalloc(allocator, capacity, elemsize);
+    
+    if (array.data) {
+        array.capacity = capacity;
+    } else {
+        array.capacity = 0;
+    }
+    
     return array;
 }
 
 UcxArray ucx_array_clone(UcxArray array) {
     UcxArray clone;
     
+    clone.allocator = array.allocator;
+    clone.elemsize = array.elemsize;
+    clone.size = array.size;
+    clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);
+    
+    if (clone.data) {
+        clone.capacity = array.capacity;
+        memcpy(clone.data, array.data, array.size*array.elemsize);
+    } else {
+        clone.capacity = clone.size = 0;
+    }
+    
     return clone;
 }
 
 int ucx_array_equals(UcxArray array1, UcxArray array2,
         cmp_func cmpfnc, void* data) {
     
-    return 1;
+    if (array1.size != array2.size || array1.elemsize != array2.elemsize) {
+        return 0;
+    } else {
+        if (array1.size == 0)
+            return 1;
+        
+        if (cmpfnc == NULL) {
+            cmpfnc = ucx_cmp_mem;
+            data = &array1.elemsize;
+        }
+        
+        for (size_t i = 0 ; i < array1.size ; i++) {
+            int r = cmpfnc(
+                    ucx_array_at(array1, i),
+                    ucx_array_at(array2, i),
+                    data);
+            if (r != 0)
+                return 0;
+        }
+        return 1;
+    }
 }
 
 void ucx_array_free(UcxArray *array) {
-    
+    alfree(array->allocator, array->data);
+    array->data = NULL;
+    array->capacity = array->size = 0;
 }
 
 int ucx_array_append(UcxArray *array, void *data) {
-    return 1;
+    if (array->size == array->capacity) {
+        if (ucx_array_reserve(array, array->capacity*2)) {
+            return 1;
+        }
+    }
+    
+    void* dest = ucx_array_at(*array, array->size++);
+    if (data) {
+        memcpy(dest, data, array->elemsize);
+    } else {
+        memset(dest, 0, array->elemsize);
+    }
+    
+    return 0;
 }
 
 int ucx_array_prepend(UcxArray *array, void *data) {
-    return 1;
+    if (array->size == array->capacity) {
+        if (ucx_array_reserve(array, array->capacity*2)) {
+            return 1;
+        }
+    }
+    
+    array->size++;
+    
+    if (array->size > 1) {
+        void *dest = ucx_array_at(*array,1);
+        memmove(dest, array->data, array->elemsize*array->size);
+    }
+    
+    if (data) {
+        memcpy(array->data, data, array->elemsize);
+    } else {
+        memset(array->data, 0, array->elemsize);
+    }
+        
+    return 0;
 }
 
 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
-    return 1;
+    
+    if (array1->elemsize != array2->elemsize)
+        return 1;
+    
+    size_t capacity = array1->capacity+array2->capacity;
+        
+    if (array1->capacity < capacity) {
+        if (ucx_array_reserve(array1, capacity)) {
+            return 1;
+        }
+    }
+    
+    void* dest = ucx_array_at(*array1, array1->size);
+    memcpy(dest, array2->data, array2->size*array2->elemsize);
+    
+    array1->size += array2->size;
+    
+    return 0;
 }
 
 void *ucx_array_at(UcxArray array, size_t index) {
-    return NULL;
+    char* memory = array.data;
+    char* loc = memory + index*array.elemsize;
+    return loc;
 }
 
 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
     
-    return 0;
+    if (cmpfnc == NULL) {
+        cmpfnc = ucx_cmp_mem;
+        data = &array.elemsize;
+    }
+
+    if (array.size > 0) {
+        for (size_t i = 0 ; i < array.size ; i++) {
+            void* ptr = ucx_array_at(array, i);
+            if (cmpfnc(ptr, elem, data) == 0) {
+                return i;
+            }
+        }
+        return array.size;
+    } else {
+        return 0;
+    }
 }
 
 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
     return ucx_array_find(array, elem, cmpfnc, data) != array.size;
 }
 
-int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
-    return 1;
+static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data,
+        size_t start, size_t mid, size_t end) { 
+    
+    size_t rightstart = mid + 1; 
+  
+    if (cmpfnc(ucx_array_at(*array, mid),
+            ucx_array_at(*array, rightstart), data) <= 0) {
+        /* already sorted */
+        return;
+    }
+  
+    // we need memory for one element
+    void *value = malloc(array->elemsize);
+    
+    while (start <= mid && rightstart <= end) { 
+        if (cmpfnc(ucx_array_at(*array, start),
+                ucx_array_at(*array, rightstart), data) <= 0) { 
+            start++; 
+        } else {
+            // save the value from the right
+            memcpy(value, ucx_array_at(*array, rightstart), array->elemsize);
+                        
+            // shift all left elements one element to the right
+            size_t shiftcount = rightstart-start;
+            void *startptr = ucx_array_at(*array, start);
+            void *dest = ucx_array_at(*array, start+1);
+            memmove(dest, startptr, shiftcount*array->elemsize);
+            
+            // bring the first value from the right to the left
+            memcpy(startptr, value, array->elemsize);
+  
+            start++; 
+            mid++; 
+            rightstart++; 
+        }
+    }
+    
+    // free the temporary memory
+    free(value);
+} 
+  
+static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data,
+        size_t l, size_t r) { 
+    if (l < r) {
+        size_t m = l + (r - l) / 2; 
+  
+        ucx_array_mergesort(array, cmpfnc, data, l, m); 
+        ucx_array_mergesort(array, cmpfnc, data, m + 1, r); 
+        ucx_array_merge(array, cmpfnc, data, l, m, r);
+    } 
+}
+
+void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {   
+    ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1);
 }
 
 void ucx_array_remove(UcxArray *array, size_t index) {
-    
+    array->size--;
+    if (index < array->size) {
+        void* dest = ucx_array_at(*array, index);
+        void* src = ucx_array_at(*array, index+1);
+        memmove(dest, src, (array->size - index)*array->elemsize);
+    }
 }
 
 void ucx_array_remove_fast(UcxArray *array, size_t index) {
-    
+    array->size--;
+    if (index < array->size) {       
+        void* dest = ucx_array_at(*array, index);
+        void* src = ucx_array_at(*array, array->size);
+        memcpy(dest, src, array->elemsize);
+    }
 }
 
 int ucx_array_shrink(UcxArray* array) {
-    return 1;
+    void* newptr = alrealloc(array->allocator, array->data,
+                array->size*array->elemsize);
+    if (newptr) {
+        array->data = newptr;
+        array->capacity = array->size;
+        return 0;
+    } else {
+        return 1;
+    }
 }
 
 int ucx_array_resize(UcxArray* array, size_t capacity) {
-    return 1;
+    if (array->capacity >= capacity) {
+        void* newptr = alrealloc(array->allocator, array->data,
+                capacity*array->elemsize);
+        if (newptr) {
+            array->data = newptr;
+            array->capacity = capacity;
+            if (array->size > array->capacity) {
+                array->size = array->capacity;
+            }
+            return 0;
+        } else {
+            return 1;
+        }
+    } else {
+        return ucx_array_reserve(array, capacity);
+    }
 }
 
 int ucx_array_reserve(UcxArray* array, size_t capacity) {
-    return 1;
+    if (array->capacity > capacity) {
+        return 0;
+    } else {
+        void* newptr = alrealloc(array->allocator, array->data,
+                capacity*array->elemsize);
+        if (newptr) {
+            array->data = newptr;
+            array->capacity = capacity;
+            return 0;
+        } else {
+            return 1;
+        }
+    }
 }
-
diff -r 872ae61c8945 -r 6d7aa8a1a3b3 src/ucx/array.h
--- a/src/ucx/array.h	Thu Jul 04 21:31:45 2019 +0200
+++ b/src/ucx/array.h	Thu Jul 04 22:23:15 2019 +0200
@@ -276,17 +276,15 @@
 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data);
 
 /**
- * Sorts a UcxArray with natural merge sort.
+ * Sorts a UcxArray with an almost in-place merge sort.
  * 
- * This function uses O(n) additional temporary memory for merge operations
- * that is automatically freed after each merge.
+ * This function uses additional memory for exactly one element.
  * 
  * @param the array to sort
  * @param cmpfnc the function that shall be used to compare the element data
  * @param data additional data for the cmp_func()
- * @return zero on success, non-zero if allocation of temporary memory failed
  */
-int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data);
+void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data);
 
 /**
  * Removes an element from the array.
diff -r 872ae61c8945 -r 6d7aa8a1a3b3 test/array_tests.c
--- a/test/array_tests.c	Thu Jul 04 21:31:45 2019 +0200
+++ b/test/array_tests.c	Thu Jul 04 22:23:15 2019 +0200
@@ -151,19 +151,17 @@
     
     UCX_TEST_BEGIN
     
-    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL) == 0, "failed");
-    UCX_TEST_ASSERT(ucx_array_equals(a1, a4, ucx_cmp_int, NULL) > 0, "failed");
-    UCX_TEST_ASSERT(ucx_array_equals(a4, a1, ucx_cmp_int, NULL) < 0, "failed");
-    UCX_TEST_ASSERT(ucx_array_equals(a1, a3, ucx_cmp_int, NULL) < 0,
-            "comparing arrays of different element size failed");
-    UCX_TEST_ASSERT(ucx_array_equals(a3, a1, ucx_cmp_int, NULL) > 0,
-            "comparing arrays of different element size failed");
+    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL), "failed");
+    UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int, NULL), "failed");
+    UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int, NULL), "failed");
+    UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int, NULL),
+            "comparing arrays of different element size shall fail");
+    UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int, NULL),
+            "comparing arrays of different element size shall fail");
     
-    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL) == 0,
+    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL),
             "compare using memcmp() failed");
-    UCX_TEST_ASSERT(ucx_array_equals(a1, a4, NULL, NULL) > 0,
-            "compare using memcmp() failed");
-    UCX_TEST_ASSERT(ucx_array_equals(a4, a1, NULL, NULL) < 0,
+    UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL),
             "compare using memcmp() failed");
     
     UCX_TEST_END
@@ -337,11 +335,11 @@
     UCX_TEST_BEGIN
 
     UCX_TEST_ASSERT(array.data != copy.data, "no true copy");
-    UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed");
     UCX_TEST_ASSERT(array.size == copy.size, "size mismatch");
     UCX_TEST_ASSERT(array.capacity == copy.capacity, "capacity mismatch");
     UCX_TEST_ASSERT(array.elemsize == copy.elemsize, "element size mismatch");
     UCX_TEST_ASSERT(array.allocator == copy.allocator, "allocator mismatch");
+    UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed");
     
     UCX_TEST_END
 
@@ -369,10 +367,22 @@
 
     UCX_TEST_BEGIN
     void* original_ptr = array.data;
-    UCX_TEST_ASSERT(!ucx_array_sort(array, ucx_cmp_int, NULL), "failed");
-    UCX_TEST_ASSERT(!ucx_array_equals(array, expected, NULL, NULL), "failed");
+    ucx_array_sort(array, ucx_cmp_int, NULL);
+    UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed");
     UCX_TEST_ASSERT(array.size == 5, "size corrupted");
     UCX_TEST_ASSERT(array.data == original_ptr, "shall not reallocate");
+                
+    ucx_array_reserve(&array, 32);
+    ucx_array_reserve(&expected, 32);
+    array.size = expected.size = 32;
+    for (size_t i = 0 ; i < 32 ; i++) {
+        ucx_array_at_int(array, i) = ((i%2==0)?-1:1) * ((int) i);
+        ucx_array_at_int(expected, i) = (-30+2*i) - (i > 15 ? 1 : 0);
+    }
+    
+    ucx_array_sort(array, ucx_cmp_int, NULL);
+    UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL),
+            "failed for bigger arrays");
     UCX_TEST_END
 
     ucx_array_free(&expected);