diff options
| -rw-r--r-- | CMakeLists.txt | 2 | ||||
| -rw-r--r-- | include/bh/algo.h | 154 | ||||
| -rw-r--r-- | src/algo.c | 360 | ||||
| -rw-r--r-- | tests/src/algo.c | 282 |
4 files changed, 798 insertions, 0 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 51d4cd1..f3c061d 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -20,11 +20,13 @@ enable_testing() # Set library code set(BHLIB_SOURCE + src/algo.c src/hashmap.c src/queue.c ) set(BHLIB_HEADER + include/bh/algo.h include/bh/hashmap.h include/bh/queue.h ) diff --git a/include/bh/algo.h b/include/bh/algo.h new file mode 100644 index 0000000..9beae6f --- /dev/null +++ b/include/bh/algo.h @@ -0,0 +1,154 @@ +#ifndef BHLIB_ALGO_H +#define BHLIB_ALGO_H + +#include "bh.h" + +/** + * @brief Swap two elements. + * + * @param lhs Pointer to the first element + * @param rhs Pointer to the second element + * @param size Element size + */ +void bh_swap(void *lhs, + void *rhs, + size_t size); + +/** + * @brief Partition the array. + * + * @param pivot Pointer to the pivot element + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + * + * @return Pointer to the first element that are greater-or-equal to pivot + * element. + * + * @warning Pivot element can be an element of the partitioned array itself. + */ +void *bh_partition(void *pivot, + void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Sort the array. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + */ +void bh_sort(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Sort the array using insert sort. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + */ +void bh_sort_insert(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Sort the array using shell sort. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + */ +void bh_sort_shell(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Sort the array using intro sort. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + */ +void bh_sort_intro(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Sort the array using heap sort. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + */ +void bh_sort_heap(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Make heap from the array. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + * + * @sa bh_heap_remove, bh_heap_insert + */ +void bh_heap_make(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Remove element from the heap. + * + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + * + * @warning Removed element is placed at the end of the array + * + * @sa bh_heap_make, bh_heap_remove + */ +void bh_heap_remove(void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +/** + * @brief Insert element to the heap. + * + * @param value Pointer to the inserted value (optional) + * @param array Pointer to the array + * @param size Array size + * @param element Element size + * @param equal Equal/compare function + * + * @warning If value is not passed, function assumes inserted element + * is already placed at the end of the array. + * + * @sa bh_heap_make, bh_heap_remove + */ +void bh_heap_insert(void *value, + void *array, + size_t size, + size_t element, + bh_equal_cb_t equal); + +#endif /* BHLIB_ALGO_H */ 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; + } +} diff --git a/tests/src/algo.c b/tests/src/algo.c new file mode 100644 index 0000000..861158b --- /dev/null +++ b/tests/src/algo.c @@ -0,0 +1,282 @@ +#include <bh/algo.h> +#include <bh/unit.h> +#include <string.h> +#include <stdlib.h> + +#define SIZE (4 * 1024) +#define MAX_VALUE 0x1000 +#define TEST_RUNS 64 + +static int int_equal(const void *lhs, const void *rhs) +{ + return *(const int*)lhs - *(const int*)rhs; +} + +static int check_partition(size_t index, int pivot, int *array, size_t size) +{ + size_t i; + + for (i = 0; i < index; i++) + if (array[i] >= pivot) + return -1; + + for (i = index; i < size; i++) + if (array[i] < pivot) + return -1; + + return 0; +} + +static int check_heap(int *array, size_t size) +{ + size_t i, left, right; + + for (i = 0; i < size; i++) + { + left = i * 2 + 1; + right = i * 2 + 2; + + if (left < size && array[i] < array[left]) + return -1; + if (right < size && array[i] < array[right]) + return -1; + } + + return 0; +} + +static void reference_sort(int *array, size_t size) +{ + size_t i, j; + int tmp; + + /* Reference sort is... buble sort! */ + for (i = 0; i < size; i++) + { + for (j = 1; j < size; j++) + { + if (array[j - 1] > array[j]) + { + tmp = array[j - 1]; + array[j - 1] = array[j]; + array[j] = tmp; + } + } + } +} + +static int partition(void) +{ + int input[SIZE], in_count[MAX_VALUE], out_count[MAX_VALUE], *middle, pivot; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + memset(in_count, 0, sizeof(in_count)); + memset(out_count, 0, sizeof(out_count)); + + /* Populate test array and count numbers */ + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + in_count[input[j]]++; + } + + /* Partition the array */ + if (i == 0) + pivot = -1; + else if (i == TEST_RUNS - 1) + pivot = MAX_VALUE; + else + pivot = MAX_VALUE / 2; + + middle = (int *)bh_partition(&pivot, input, SIZE, sizeof(int), int_equal); + + /* Count numbers in array */ + for (j = 0; j < SIZE; j++) + out_count[input[j]]++; + + /* Check partition */ + bh_unit_assert(check_partition(middle - input, pivot, input, SIZE) == 0); + + /* Verify, that array has same amount of numbers */ + for (j = 0; j < MAX_VALUE; j++) + bh_unit_assert(in_count[j] == out_count[j]); + } + + return 0; +} + +static int sort(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + } + + return 0; +} + +static int sort_insert(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_insert(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + } + + return 0; +} + +static int sort_shell(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_shell(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + } + + return 0; +} + +static int sort_heap(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_heap(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + } + + return 0; +} + +static int sort_intro(void) +{ + int input[SIZE], reference[SIZE]; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + input[j] = rand() % MAX_VALUE; + reference[j] = input[j]; + } + + reference_sort(reference, SIZE); + bh_sort_intro(input, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + qsort(reference, SIZE, sizeof(int), int_equal); + bh_unit_assert(memcmp(reference, input, sizeof(input)) == 0); + + } + + return 0; +} + +static int heap(void) +{ + int heap[SIZE], value; + size_t i, j; + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + heap[j] = rand() % MAX_VALUE; + + bh_heap_make(heap, SIZE, sizeof(int), int_equal); + bh_unit_assert(check_heap(heap, SIZE) == 0); + } + + for (i = 0; i < TEST_RUNS; i++) + { + for (j = 0; j < SIZE; j++) + { + value = rand() % MAX_VALUE; + if (i == 0) + { + heap[j] = value; + bh_heap_insert(NULL, heap, j, sizeof(int), int_equal); + } + else + { + bh_heap_insert(&value, heap, j, sizeof(int), int_equal); + } + } + + bh_unit_assert(check_heap(heap, SIZE) == 0); + } + + return 0; +} + +int main(int argc, char **argv) +{ + (void)argc; + (void)argv; + + bh_unit_add("partition", partition); + bh_unit_add("sort_insert", sort_insert); + bh_unit_add("sort_shell", sort_shell); + bh_unit_add("sort_heap", sort_heap); + bh_unit_add("sort_intro", sort_intro); + bh_unit_add("sort", sort); + bh_unit_add("heap", heap); + + return bh_unit_run(); +} |