diff options
Diffstat (limited to 'src/algo.c')
| -rw-r--r-- | src/algo.c | 230 |
1 files changed, 215 insertions, 15 deletions
@@ -1,34 +1,72 @@ #include <bh/algo.h> #include <string.h> -#include <stdio.h> -void bh_swap(void *lhs, - void *rhs, +/** + * \defgroup algo Algorithms + * + * Common algorithms (search, swap, heap, etc) + * \{ + */ + +/** + * Swaps \a size bytes between the object pointed to by \a src and object + * pointed to by \a dest. + * + * If the objects overlap, the behavior is undefined. + * + * If either \a src or \a dest is an invalid or null pointer, the behavior is + * undefined. + * + * \param dest Pointer to the memory location to swap to + * \param src Pointer to the memory location to swap from + * \param size Number of bytes to swap + */ +void bh_swap(void *dest, + void *src, size_t size) { int tmp; - /* Swap values in int sized chunks */ + /* Swap bytes in int-sized chunks */ while (size >= sizeof(tmp)) { - memmove(&tmp, lhs, sizeof(tmp)); - memmove(lhs, rhs, sizeof(tmp)); - memmove(rhs, &tmp, sizeof(tmp)); + memmove(&tmp, dest, sizeof(tmp)); + memmove(dest, src, sizeof(tmp)); + memmove(src, &tmp, sizeof(tmp)); - lhs = (char *)lhs + sizeof(tmp); - rhs = (char *)rhs + sizeof(tmp); + dest = (char *)dest + sizeof(tmp); + src = (char *)src + sizeof(tmp); size -= sizeof(tmp); } - /* Swap the rest */ + /* Swap the remaining size */ if (size) { - memmove(&tmp, lhs, size); - memmove(lhs, rhs, size); - memmove(rhs, &tmp, size); + memmove(&tmp, dest, size); + memmove(dest, src, size); + memmove(src, &tmp, size); } } +/** + * Partitions the \a array of \a size elements of \a element bytes, relative to + * the specified \a pivot element. Function pointed by \a equal is used for + * comparison. + * + * If the \a pivot element is part of the partitioned \a array, function will + * behaive the same way, as if \a pivot element wasn't part of the array. + * + * If \a equal indicates two elements as equivalent, their order in the + * resulting partitioned array is unspecified. + * + * \param pivot Pointer to the pivot element + * \param array Pointer to the array to partition + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + * + * \return Pointer to the first element of the second partition. + */ void *bh_partition(void *pivot, void *array, size_t size, @@ -74,6 +112,17 @@ void *bh_partition(void *pivot, return j + element; } +/** + * Sorts the \a array of \a size elements of \a element bytes. Function pointed + * by \a equal is used for comparision. + * + * This sorting does not make any gurantees about time or space complexity. + * + * \param array Pointer to the array to sort + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + */ void bh_sort(void *array, size_t size, size_t element, @@ -83,6 +132,23 @@ void bh_sort(void *array, bh_sort_intro(array, size, element, equal); } + +/** + * Sorts the \a array of \a size elements of \a element bytes with insertion + * sort. Function pointed by \a equal is used for comparision. + * + * This sorting has following time complexity: + * - best case O(n) + * - average case O(n^2) + * - worst case O(n^2) + * + * This sorting has O(1) space complexity. + * + * \param array Pointer to the array to sort + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + */ void bh_sort_insert(void *array, size_t size, size_t element, @@ -109,6 +175,20 @@ void bh_sort_insert(void *array, } +/** + * Sorts the \a array of \a size elements of \a element bytes with shell sort. + * Function pointed by \a equal is used for comparision. + * + * This sorting has the O(n log n) best cast time complexity. Average and worst + * cases are implementation dependant. + * + * This sorting has O(1) space complexity. + * + * \param array Pointer to the array to sort + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + */ void bh_sort_shell(void *array, size_t size, size_t element, @@ -118,7 +198,7 @@ void bh_sort_shell(void *array, const size_t *gap; size_t i, j; - /* Shell sort with A102549 sequence*/ + /* Shell sort with A102549 sequence */ for (gap = gaps; gap < gaps + sizeof(gaps) / sizeof(*gaps); gap++) { for (i = *gap; i < size; i++) @@ -201,6 +281,22 @@ static void bh_sort_intro_r(void *array, } } +/** + * Sorts the \a array of \a size elements of \a element bytes with insertion + * sort. Function pointed by \a equal is used for comparision. + * + * This sorting has following time complexity: + * - best case O(n log n) + * - average case O(n log n) + * - worst case O(n log n) + * + * This sorting has O(log n) space complexity. + * + * \param array Pointer to the array to sort + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + */ void bh_sort_intro(void *array, size_t size, size_t element, @@ -221,6 +317,22 @@ void bh_sort_intro(void *array, bh_sort_intro_r(array, size, element, equal, depth); } +/** + * Sorts the \a array of \a size elements of \a element bytes with insertion + * sort. Function pointed by \a equal is used for comparision. + * + * This sorting has following time complexity: + * - best case O(n) + * - average case O(n log n) + * - worst case O(n log n) + * + * This sorting has O(1) space complexity. + * + * \param array Pointer to the array to sort + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + */ void bh_sort_heap(void *array, size_t size, size_t element, @@ -232,7 +344,15 @@ void bh_sort_heap(void *array, bh_heap_remove(array, size--, element, equal); } - +/** + * Heapifes the \a array of \a size elements of \a element bytes. Function + * pointed by \a equal is used for comparision. + * + * \param array Pointer to the array to heapify + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparision function + */ void bh_heap_make(void *array, size_t size, size_t element, @@ -279,6 +399,15 @@ void bh_heap_make(void *array, } } +/** + * Removes top element from heapified \a array of \a size elements of \a + * elements bytes. Function pointed by \a equal is used for comparasion. + * + * \param array Pointer to the array to remove element from + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparasion function + */ void bh_heap_remove(void *array, size_t size, size_t element, @@ -323,6 +452,16 @@ void bh_heap_remove(void *array, } } +/** + * Inserts new element into heapified \a array of \a size elements of \a + * elements bytes. Function pointed by \a equal is used for comparasion. + * + * \param value Pointer to the value to be inserted + * \param array Pointer to the array to remove element from + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparasion function + */ void bh_heap_insert(void *value, void *array, size_t size, @@ -358,3 +497,64 @@ void bh_heap_insert(void *value, break; } } + +/** + * Replaces top element of the heapified \a array of \a size elements of \a + * elements bytes. Function pointed by \a equal is used for comparasion. + * + * This function is equal to two consecutive operations of remove and insert. + * + * \param value Pointer to the value to be inserted + * \param array Pointer to the array to remove element from + * \param size Number of elements in the array + * \param element Size of each element in the array in bytes + * \param equal Comparasion function + */ +void bh_heap_replace(void *value, + 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 * element; + current = start; + left = start + (current - start) * 2 + element; + right = left + element; + + /* Copy supplied element to the first (top) position */ + memmove(current, value, 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; + } +} + +/** + * \} + */
\ No newline at end of file |