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).