+++ /dev/null
-/* $Id: qsort.c,v 1.3 2003/04/11 12:31:46 mjt Exp $
- * Adopted from GNU glibc by Mjt.
- * See stdlib/qsort.c in glibc */
-
-/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
- This file is part of the GNU C Library.
- Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
-
- The GNU C Library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
-
- The GNU C Library is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with the GNU C Library; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307 USA. */
-
-/* Usage:
- * first, define the following:
- * QSORT_TYPE - type of array elements
- * QSORT_BASE - pointer to array
- * QSORT_NELT - number of elements in the array (must not be 0)
- * QSORT_LT - QSORT_LT(a,b) should return true if *a < *b
- * and second, just #include this file into the place you want it.
- * Some C code will be inserted into that place, to sort array defined
- * by QSORT_TYPE, QSORT_BASE, QSORT_NELT and comparision routine QSORT_LT.
- */
-
-/* Swap two items pointed to by A and B using temporary buffer t. */
-#define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
-
-/* Discontinue quicksort algorithm when partition gets below this size.
- This particular magic number was chosen to work best on a Sun 4/260. */
-#define _QSORT_MAX_THRESH 4
-
-/* Stack node declarations used to store unfulfilled partition obligations
- * (inlined in QSORT).
-typedef struct {
- TYPE *_lo, *_hi;
-} qsort_stack_node;
- */
-
-/* The next 4 #defines implement a very fast in-line stack abstraction. */
-/* The stack needs log (total_elements) entries (we could even subtract
- log(MAX_THRESH)). Since total_elements has type unsigned, we get as
- upper bound for log (total_elements):
- bits per byte (CHAR_BIT) * sizeof(unsigned). */
-#define _QSORT_STACK_SIZE (8 * sizeof(unsigned))
-#define _QSORT_PUSH(top, low, high) \
- (((top->_lo = (low)), (top->_hi = (high)), ++top))
-#define _QSORT_POP(low, high, top) \
- ((--top, (low = top->_lo), (high = top->_hi)))
-#define _QSORT_STACK_NOT_EMPTY (_stack < _top)
-
-
-/* Order size using quicksort. This implementation incorporates
- four optimizations discussed in Sedgewick:
-
- 1. Non-recursive, using an explicit stack of pointer that store the
- next array partition to sort. To save time, this maximum amount
- of space required to store an array of SIZE_MAX is allocated on the
- stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
- only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
- Pretty cheap, actually.
-
- 2. Chose the pivot element using a median-of-three decision tree.
- This reduces the probability of selecting a bad pivot value and
- eliminates certain extraneous comparisons.
-
- 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
- insertion sort to order the MAX_THRESH items within each partition.
- This is a big win, since insertion sort is faster for small, mostly
- sorted array segments.
-
- 4. The larger of the two sub-partitions is always pushed onto the
- stack first, with the algorithm then concentrating on the
- smaller partition. This *guarantees* no more than log (total_elems)
- stack size is needed (actually O(1) in this case)! */
-
-
-{
- QSORT_TYPE *const _base = (QSORT_BASE);
- const unsigned _elems = (QSORT_NELT);
- QSORT_TYPE _hold;
-
- if (_elems > _QSORT_MAX_THRESH) {
- QSORT_TYPE *_lo = _base;
- QSORT_TYPE *_hi = _lo + _elems - 1;
- struct {
- QSORT_TYPE *_hi, *_lo;
- } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;
-
- while (_QSORT_STACK_NOT_EMPTY) {
- QSORT_TYPE *_left_ptr, *_right_ptr;
-
- /* Select median value from among LO, MID, and HI. Rearrange
- LO and HI so the three values are sorted. This lowers the
- probability of picking a pathological pivot value and
- skips a comparison for both the LEFT_PTR and RIGHT_PTR in
- the while loops. */
-
- QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);
-
- if (QSORT_LT (_mid, _lo))
- _QSORT_SWAP (_mid, _lo, _hold);
- if (QSORT_LT (_hi, _mid))
- _QSORT_SWAP (_mid, _hi, _hold);
- else
- goto _jump_over;
- if (QSORT_LT (_mid, _lo))
- _QSORT_SWAP (_mid, _lo, _hold);
- _jump_over:;
-
- _left_ptr = _lo + 1;
- _right_ptr = _hi - 1;
-
- /* Here's the famous ``collapse the walls'' section of quicksort.
- Gotta like those tight inner loops! They are the main reason
- that this algorithm runs much faster than others. */
- do {
- while (QSORT_LT (_left_ptr, _mid))
- ++_left_ptr;
-
- while (QSORT_LT (_mid, _right_ptr))
- --_right_ptr;
-
- if (_left_ptr < _right_ptr) {
- _QSORT_SWAP (_left_ptr, _right_ptr, _hold);
- if (_mid == _left_ptr)
- _mid = _right_ptr;
- else if (_mid == _right_ptr)
- _mid = _left_ptr;
- ++_left_ptr;
- --_right_ptr;
- }
- else if (_left_ptr == _right_ptr) {
- ++_left_ptr;
- --_right_ptr;
- break;
- }
- } while (_left_ptr <= _right_ptr);
-
- /* Set up pointers for next iteration. First determine whether
- left and right partitions are below the threshold size. If so,
- ignore one or both. Otherwise, push the larger partition's
- bounds on the stack and continue sorting the smaller one. */
-
- if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {
- if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
- /* Ignore both small partitions. */
- _QSORT_POP (_lo, _hi, _top);
- else
- /* Ignore small left partition. */
- _lo = _left_ptr;
- }
- else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
- /* Ignore small right partition. */
- _hi = _right_ptr;
- else if (_right_ptr - _lo > _hi - _left_ptr) {
- /* Push larger left partition indices. */
- _QSORT_PUSH (_top, _lo, _right_ptr);
- _lo = _left_ptr;
- }
- else {
- /* Push larger right partition indices. */
- _QSORT_PUSH (_top, _left_ptr, _hi);
- _hi = _right_ptr;
- }
- }
- }
-
- /* Once the BASE array is partially sorted by quicksort the rest
- is completely sorted using insertion sort, since this is efficient
- for partitions below MAX_THRESH size. BASE points to the
- beginning of the array to sort, and END_PTR points at the very
- last element in the array (*not* one beyond it!). */
-
-
- {
- QSORT_TYPE *const _end_ptr = _base + _elems - 1;
- QSORT_TYPE *_tmp_ptr = _base;
- register QSORT_TYPE *_run_ptr;
- QSORT_TYPE *_thresh;
-
- _thresh = _base + _QSORT_MAX_THRESH;
- if (_thresh > _end_ptr)
- _thresh = _end_ptr;
-
- /* Find smallest element in first threshold and place it at the
- array's beginning. This is the smallest array element,
- and the operation speeds up insertion sort's inner loop. */
-
- for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)
- if (QSORT_LT (_run_ptr, _tmp_ptr))
- _tmp_ptr = _run_ptr;
-
- if (_tmp_ptr != _base)
- _QSORT_SWAP (_tmp_ptr, _base, _hold);
-
- /* Insertion sort, running from left-hand-side
- * up to right-hand-side. */
-
- _run_ptr = _base + 1;
- while (++_run_ptr <= _end_ptr) {
- _tmp_ptr = _run_ptr - 1;
- while (QSORT_LT (_run_ptr, _tmp_ptr))
- --_tmp_ptr;
-
- ++_tmp_ptr;
- if (_tmp_ptr != _run_ptr) {
- QSORT_TYPE *_trav = _run_ptr + 1;
- while (--_trav >= _run_ptr) {
- QSORT_TYPE *_hi, *_lo;
- _hold = *_trav;
-
- for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo)
- *_hi = *_lo;
- *_hi = _hold;
- }
- }
- }
- }
-}
projects / apps / pfixtools.git / blobdiff