## gskqsortmacro

gskqsortmacro — inline qsort macro

## Synopsis

    #define             GSK_QSORT_STACK_MAX_SIZE
    #define             GSK_INSERTION_SORT_THRESHOLD
    #define             GSK_QSORT                           (array, type, n_elements, compare)
    #define             GSK_QSORT_DEBUG                     (array, type, n_elements, compare)
    #define             GSK_QSORT_FULL                      (array, type, n_elements, compare, isort_threshold, stack_size, ss_assertion)
    #define             GSK_QSELECT_FULL                    (array, type, n_elements, n_select, compare, isort_threshold, stack_size, ss_assertion)
    #define             GSK_QSORT_ASSERT_STACK_SIZE         (stack_alloced)
    #define             GSK_INSERTION_SORT                  (array, type, length, compare)
    #define             GSK_QSORT_SIMPLE_COMPARATOR         (a,b,compare_rv)

## Description

This is an implementation of qsort that avoids recursion and uses a fixed-length stack. As such, it is suitable for a macro implementation.

Please note that usually `qsort()` or `g_qsort_with_data()` is nicer to use than the macro version: it will compile to less code, for example. However, the macro-based version is often faster, and can be more convenient to use than the other routines. For example, since the macro is lexically inlined, the comparator can use local variables.

Here is an example: this qsorts an array of integers, considering only the least n_bits bits:

     static void
     qsort_least_significant_bits (guint  array_len,
                                   guint *array,
    			       guint  n_bits)
     {
       guint mask = (1 << n_bits) - 1;
    #define COMPARE(a,b,rv)       \
      { guint tmp_a = mask & a;   \
        guint tmp_b = mask & b;   \
        rv = (tmp_a < tmp_b) ? -1 \
           : (tmp_a > tmp_b) ? +1 \
           0; }
      GSK_QSORT (array, guint, array_len, COMPARE);
    #undef COMPARE
     }

## Details

### GSK_QSORT_STACK_MAX_SIZE

    #define             GSK_QSORT_STACK_MAX_SIZE

Maximum stack size to use for QSORT. Only should be changed if stack-space is very limited.

### GSK_INSERTION_SORT_THRESHOLD

    #define             GSK_INSERTION_SORT_THRESHOLD

Maximum number of elements for which insertion sort is preferred to quicksort.

### GSK_QSORT()

    #define             GSK_QSORT(array, type, n_elements, compare)

Sort an array.

`array` : | The array of values to sort.
`type` : | The type of an element of the array.
`n_elements` : | The number of elements in `array` to sort.
`compare` : | A comparator macro.

### GSK_QSORT_DEBUG()

    #define             GSK_QSORT_DEBUG(array, type, n_elements, compare)

Quicksort, with stack-checking.

`array` : | The array of values to sort.
`type` : | The type of an element of the array.
`n_elements` : | The number of elements in `array` to sort.
`compare` : | A comparator macro.

### GSK_QSORT_FULL()

    #define             GSK_QSORT_FULL(array, type, n_elements, compare, isort_threshold, stack_size, ss_assertion)

Quicksort, with a bit more configurability.

`array` : | the array
`type` : | the type of elements in the array.
`n_elements` : | the number of elements in the array.
`compare` : | comparator macro
`isort_threshold` : | maximum size of array to insertion-sort instead of quicksort.
`stack_size` : | maximum number of stack required.
`ss_assertion` : | a macro which can do the stack-guard assertion. Should be blank or GSK_QSORT_ASSERT_STACK_SIZE.

### GSK_QSELECT_FULL()

    #define             GSK_QSELECT_FULL(array, type, n_elements, n_select, compare, isort_threshold, stack_size, ss_assertion)

Computes the top `n_select` elements of an array which has `n_elements` elements in it. The top `n_select` elements will be sorted.

`array` : | the array
`type` : | the type of elements in the array.
`n_elements` : | the number of elements in the array.
`n_select` : | the number of elements to get in the sorted part.
`compare` : | comparator macro
`isort_threshold` : | maximum size of array to insertion-sort instead of quicksort.
`stack_size` : | maximum number of stack required.
`ss_assertion` : | a macro which can do the stack-guard assertion. Should be blank or GSK_QSORT_ASSERT_STACK_SIZE.

### GSK_QSORT_ASSERT_STACK_SIZE()

    #define             GSK_QSORT_ASSERT_STACK_SIZE(stack_alloced)

Macro to verify that the stack is not overflowed. The stack can overflow if the comparator is invalid.

`stack_alloced` : |

### GSK_INSERTION_SORT()

    #define             GSK_INSERTION_SORT(array, type, length, compare)

An insertion-sort implementation, which is used by the quicksort in the case of small arrays.

`array` : | The array of values to sort.
`type` : | The type of an element of the array.
`length` : | The number elements in `array`.
`compare` : | comparator macro

### GSK_QSORT_SIMPLE_COMPARATOR()

    #define             GSK_QSORT_SIMPLE_COMPARATOR(a,b,compare_rv)

A comparator macro that just uses the normal operators <, > and ==.

`a` : | the first element
`b` : | the second element
`compare_rv` : | set to -1, 0, 1 if `a` is less than, equal to, or greater than `b`.

## See Also

The gskrbtreemacros, which can maintain a set in sorted order, so that the set can be walked in O(N) time, and each insert, delete or lookup is O(log N).