![]() |
![]() |
![]() |
GSK Reference Manual | ![]() |
---|---|---|---|---|
Top | Description |
#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)
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 }
#define GSK_QSORT_STACK_MAX_SIZE
Maximum stack size to use for QSORT. Only should be changed if stack-space is very limited.
#define GSK_INSERTION_SORT_THRESHOLD
Maximum number of elements for which insertion sort is preferred to quicksort.
#define GSK_QSORT(array, type, n_elements, compare)
Sort an array.
|
The array of values to sort. |
|
The type of an element of the array. |
|
The number of elements in array to sort.
|
|
A comparator macro. |
#define GSK_QSORT_DEBUG(array, type, n_elements, compare)
Quicksort, with stack-checking.
|
The array of values to sort. |
|
The type of an element of the array. |
|
The number of elements in array to sort.
|
|
A comparator macro. |
#define GSK_QSORT_FULL(array, type, n_elements, compare, isort_threshold, stack_size, ss_assertion)
Quicksort, with a bit more configurability.
|
the array |
|
the type of elements in the array. |
|
the number of elements in the array. |
|
comparator macro |
|
maximum size of array to insertion-sort instead of quicksort. |
|
maximum number of stack required. |
|
a macro which can do the stack-guard assertion. Should be blank or GSK_QSORT_ASSERT_STACK_SIZE. |
#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.
|
the array |
|
the type of elements in the array. |
|
the number of elements in the array. |
|
the number of elements to get in the sorted part. |
|
comparator macro |
|
maximum size of array to insertion-sort instead of quicksort. |
|
maximum number of stack required. |
|
a macro which can do the stack-guard assertion. Should be blank or 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.
|
#define GSK_INSERTION_SORT(array, type, length, compare)
An insertion-sort implementation, which is used by the quicksort in the case of small arrays.
|
The array of values to sort. |
|
The type of an element of the array. |
|
The number elements in array .
|
|
comparator macro |