aboutsummaryrefslogtreecommitdiff
path: root/src/algo.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/algo.c')
-rw-r--r--src/algo.c360
1 files changed, 360 insertions, 0 deletions
diff --git a/src/algo.c b/src/algo.c
new file mode 100644
index 0000000..7f3287d
--- /dev/null
+++ b/src/algo.c
@@ -0,0 +1,360 @@
+#include <bh/algo.h>
+#include <string.h>
+#include <stdio.h>
+
+void bh_swap(void *lhs,
+ void *rhs,
+ size_t size)
+{
+ int tmp;
+
+ /* Swap values in int sized chunks */
+ while (size >= sizeof(tmp))
+ {
+ memmove(&tmp, lhs, sizeof(tmp));
+ memmove(lhs, rhs, sizeof(tmp));
+ memmove(rhs, &tmp, sizeof(tmp));
+
+ lhs = (char *)lhs + sizeof(tmp);
+ rhs = (char *)rhs + sizeof(tmp);
+ size -= sizeof(tmp);
+ }
+
+ /* Swap the rest */
+ if (size)
+ {
+ memmove(&tmp, lhs, size);
+ memmove(lhs, rhs, size);
+ memmove(rhs, &tmp, size);
+ }
+}
+
+void *bh_partition(void *pivot,
+ void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ char *start, *end, *i, *j;
+
+ /* Calculate start, end and item pointers */
+ start = (char *)array;
+ end = start + size * element;
+ i = start;
+ j = start + (size - 1) * element;
+
+ /* Iterate over array */
+ while (1)
+ {
+ /* Find first element from the left that are bigger then pivot */
+ while (i < end && equal(i, pivot) < 0)
+ i += element;
+
+ /* Find first element from the right that are less then pivot*/
+ while (j >= start && equal(j, pivot) >= 0)
+ j -= element;
+
+ /* If item elemetns passed each other - we are done */
+ if (i >= j)
+ break;
+
+ /* Special case when pivot is actually part of the array */
+ if (pivot == i)
+ pivot = j;
+ else if (pivot == j)
+ pivot = i;
+
+ /* Swap elements and continue */
+ bh_swap(i, j, element);
+ i += element;
+ j -= element;
+ }
+
+ /* Return pointer to the middle of the partition */
+ return j + element;
+}
+
+void bh_sort(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ /* Use intro sort as default */
+ bh_sort_intro(array, size, element, equal);
+}
+
+void bh_sort_insert(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ size_t i, j;
+
+ /* Standard insert sort */
+ for (i = 1; i < size; i++)
+ {
+ for (j = i; j >= 1; j -= 1)
+ {
+ char *lhs, *rhs;
+
+ lhs = (char *)array + j * element;
+ rhs = (char *)array + (j - 1) * element;
+
+ if (equal(lhs, rhs) < 0)
+ bh_swap(lhs, rhs, element);
+ else
+ break;
+ }
+ }
+
+}
+
+void bh_sort_shell(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ static const size_t gaps[9] = {1750, 701, 301, 132, 57, 23, 10, 4, 1};
+ const size_t *gap;
+ size_t i, j;
+
+ /* Shell sort with A102549 sequence*/
+ for (gap = gaps; gap < gaps + sizeof(gaps) / sizeof(*gaps); gap++)
+ {
+ for (i = *gap; i < size; i++)
+ {
+ for (j = i; j >= *gap; j -= *gap)
+ {
+ char *lhs, *rhs;
+
+ lhs = (char *)array + j * element;
+ rhs = (char *)array + (j - *gap) * element;
+
+ if (equal(lhs, rhs) < 0)
+ bh_swap(lhs, rhs, element);
+ else
+ break;
+ }
+ }
+ }
+}
+
+static void bh_sort_intro_r(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal,
+ size_t depth)
+{
+ /* Introsort (with manual tail call optimization) */
+ while (1)
+ {
+ char *start, *middle, *end, *pivot;
+
+ if (size < 16)
+ {
+ /* There are less then 16 elements left - use Shell/Insert sort */
+ bh_sort_shell(array, size, element, equal);
+ return;
+ }
+ else if (!depth)
+ {
+ /* Max depth reached - use heap sort */
+ bh_sort_heap(array, size, element, equal);
+ return;
+ }
+
+ /* Calculate start, middle and end pointers */
+ start = (char *)array;
+ middle = start + (size / 2) * element;
+ end = start + (size - 1) * element;
+
+ /* Select middle element */
+ if (equal(start, middle) > 0)
+ {
+ if (equal(middle, end) > 0)
+ pivot = middle;
+ else if (equal(start, end) > 0)
+ pivot = end;
+ else
+ pivot = start;
+ }
+ else
+ {
+ if (equal(start, end) > 0)
+ pivot = start;
+ else if (equal(middle, end) > 0)
+ pivot = end;
+ else
+ pivot = middle;
+ }
+
+ /* Partition the array */
+ middle = bh_partition(pivot, array, size, element, equal);
+
+ /* Recursive call into first half */
+ bh_sort_intro_r(array, (middle - start) / element, element, equal, depth - 1);
+
+ /* Setup array and size for the second half */
+ array = middle;
+ size = size - (middle - start) / element;
+ depth--;
+ }
+}
+
+void bh_sort_intro(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ size_t depth, depth_log;
+
+ /* Calculate max depth */
+ depth = 0;
+ depth_log = 1;
+ while (depth_log < size)
+ {
+ depth++;
+ depth_log <<= 1;
+ }
+
+ /* Call main sorting function */
+ bh_sort_intro_r(array, size, element, equal, depth);
+}
+
+void bh_sort_heap(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ /* Use heap_make and heap_remove for sorting */
+ bh_heap_make(array, size, element, equal);
+ while (size)
+ bh_heap_remove(array, size--, element, equal);
+}
+
+
+void bh_heap_make(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ char *start, *end;
+ size_t i;
+
+ /* Calculate start and end pointers of the array */
+ start = (char *)array;
+ end = start + size * element;
+
+ /* Bottom up heapify algorithm */
+ for (i = size / 2 + 1; i; --i)
+ {
+ char *current, *left, *right;
+
+ /* Calculate current and children pointers */
+ current = start + (i - 1) * element;
+ left = start + (current - start) * 2 + element;
+ right = left + element;
+
+ while (left < end)
+ {
+ char *biggest;
+
+ /* Determine biggest child */
+ biggest = left;
+ if (right < end && equal(left, right) < 0)
+ biggest = right;
+
+ /* Compare biggest child with current */
+ if (equal(current, biggest) < 0)
+ {
+ /* Swap content and recalculate children pointers */
+ bh_swap(current, biggest, element);
+ current = biggest;
+ left = start + (current - start) * 2 + element;
+ right = left + element;
+ }
+ else
+ break;
+ }
+ }
+}
+
+void bh_heap_remove(void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ char *start, *end, *current, *left, *right;
+
+ if (size <= 1)
+ return;
+
+ /* Calculate start, end and children pointers */
+ start = (char *)array;
+ end = start + (size - 1) * element;
+ current = start;
+ left = start + (current - start) * 2 + element;
+ right = left + element;
+
+ /* Swap first and last element */
+ bh_swap(current, end, element);
+
+ /* Iterate until we reach the end */
+ while (left < end)
+ {
+ char *biggest;
+
+ /* Determine biggest child */
+ biggest = left;
+ if (right < end && equal(left, right) < 0)
+ biggest = right;
+
+ /* Compare biggest child with current */
+ if (equal(current, biggest) < 0)
+ {
+ /* Swap content and recalculate children pointers */
+ bh_swap(current, biggest, element);
+ current = biggest;
+ left = start + (current - start) * 2 + element;
+ right = left + element;
+ }
+ else
+ break;
+ }
+}
+
+void bh_heap_insert(void *value,
+ void *array,
+ size_t size,
+ size_t element,
+ bh_equal_cb_t equal)
+{
+ char *start, *end, *current;
+
+ /* Calculate begin and end pointers */
+ start = (char *)array;
+ end = start + size * element;
+ current = end;
+
+ /* Copy value into array */
+ if (value)
+ memmove(current, value, element);
+
+ while (current > start)
+ {
+ char *parent;
+
+ /* Calculate parent pointer */
+ parent = start + (((current - start) / element - 1) / 2) * element;
+
+ /* Compare current and parent */
+ if (equal(parent, current) < 0)
+ {
+ /* Swap current and parent */
+ bh_swap(parent, current, element);
+ current = parent;
+ }
+ else
+ break;
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-01 01:41:32 +0000