path: root/src/algo.c

#include <bh/algo.h>
#include <string.h>

/**
 * \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 bytes in int-sized chunks */
    while (size >= sizeof(tmp))
    {
        memmove(&tmp, dest, sizeof(tmp));
        memmove(dest, src, sizeof(tmp));
        memmove(src, &tmp, sizeof(tmp));

        dest = (char *)dest + sizeof(tmp);
        src = (char *)src + sizeof(tmp);
        size -= sizeof(tmp);
    }

    /* Swap the remaining size */
    if (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,
                   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;
}

/**
 * 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,
             bh_equal_cb_t equal)
{
    /* Use intro sort as default */
    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,
                    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;
        }
    }

}

/**
 * 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,
                   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--;
    }
}

/**
 * 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,
                   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);
}

/**
 * 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,
                  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);
}

/**
 * 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,
                  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;
        }
    }
}

/**
 * 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,
                    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;
    }
}

/**
 * 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,
                    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;
    }
}

/**
 * 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;
    }
}

/**
 * \}
 */