1 /******************************************************************************/
2 /* postlicyd: a postfix policy daemon with a lot of features */
4 /* ________________________________________________________________________ */
6 /* Redistribution and use in source and binary forms, with or without */
7 /* modification, are permitted provided that the following conditions */
10 /* 1. Redistributions of source code must retain the above copyright */
11 /* notice, this list of conditions and the following disclaimer. */
12 /* 2. Redistributions in binary form must reproduce the above copyright */
13 /* notice, this list of conditions and the following disclaimer in the */
14 /* documentation and/or other materials provided with the distribution. */
15 /* 3. The names of its contributors may not be used to endorse or promote */
16 /* products derived from this software without specific prior written */
19 /* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND */
20 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE */
21 /* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
22 /* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS */
23 /* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR */
24 /* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF */
25 /* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS */
26 /* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN */
27 /* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) */
28 /* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF */
29 /* THE POSSIBILITY OF SUCH DAMAGE. */
30 /******************************************************************************/
32 /* $Id: qsort.c,v 1.3 2003/04/11 12:31:46 mjt Exp $
33 * Adopted from GNU glibc by Mjt.
34 * See stdlib/qsort.c in glibc */
36 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
37 This file is part of the GNU C Library.
38 Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
40 The GNU C Library is free software; you can redistribute it and/or
41 modify it under the terms of the GNU Lesser General Public
42 License as published by the Free Software Foundation; either
43 version 2.1 of the License, or (at your option) any later version.
45 The GNU C Library is distributed in the hope that it will be useful,
46 but WITHOUT ANY WARRANTY; without even the implied warranty of
47 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
48 Lesser General Public License for more details.
50 You should have received a copy of the GNU Lesser General Public
51 License along with the GNU C Library; if not, write to the Free
52 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
56 * first, define the following:
57 * QSORT_TYPE - type of array elements
58 * QSORT_BASE - pointer to array
59 * QSORT_NELT - number of elements in the array (must not be 0)
60 * QSORT_LT - QSORT_LT(a,b) should return true if *a < *b
61 * and second, just #include this file into the place you want it.
62 * Some C code will be inserted into that place, to sort array defined
63 * by QSORT_TYPE, QSORT_BASE, QSORT_NELT and comparision routine QSORT_LT.
66 /* Swap two items pointed to by A and B using temporary buffer t. */
67 #define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
69 /* Discontinue quicksort algorithm when partition gets below this size.
70 This particular magic number was chosen to work best on a Sun 4/260. */
71 #define _QSORT_MAX_THRESH 4
73 /* Stack node declarations used to store unfulfilled partition obligations
80 /* The next 4 #defines implement a very fast in-line stack abstraction. */
81 /* The stack needs log (total_elements) entries (we could even subtract
82 log(MAX_THRESH)). Since total_elements has type unsigned, we get as
83 upper bound for log (total_elements):
84 bits per byte (CHAR_BIT) * sizeof(unsigned). */
85 #define _QSORT_STACK_SIZE (8 * sizeof(unsigned))
86 #define _QSORT_PUSH(top, low, high) \
87 (((top->_lo = (low)), (top->_hi = (high)), ++top))
88 #define _QSORT_POP(low, high, top) \
89 ((--top, (low = top->_lo), (high = top->_hi)))
90 #define _QSORT_STACK_NOT_EMPTY (_stack < _top)
93 /* Order size using quicksort. This implementation incorporates
94 four optimizations discussed in Sedgewick:
96 1. Non-recursive, using an explicit stack of pointer that store the
97 next array partition to sort. To save time, this maximum amount
98 of space required to store an array of SIZE_MAX is allocated on the
99 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
100 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
101 Pretty cheap, actually.
103 2. Chose the pivot element using a median-of-three decision tree.
104 This reduces the probability of selecting a bad pivot value and
105 eliminates certain extraneous comparisons.
107 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
108 insertion sort to order the MAX_THRESH items within each partition.
109 This is a big win, since insertion sort is faster for small, mostly
110 sorted array segments.
112 4. The larger of the two sub-partitions is always pushed onto the
113 stack first, with the algorithm then concentrating on the
114 smaller partition. This *guarantees* no more than log (total_elems)
115 stack size is needed (actually O(1) in this case)! */
119 QSORT_TYPE *const _base = (QSORT_BASE);
120 const unsigned _elems = (QSORT_NELT);
123 if (_elems > _QSORT_MAX_THRESH) {
124 QSORT_TYPE *_lo = _base;
125 QSORT_TYPE *_hi = _lo + _elems - 1;
127 QSORT_TYPE *_hi, *_lo;
128 } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;
130 while (_QSORT_STACK_NOT_EMPTY) {
131 QSORT_TYPE *_left_ptr, *_right_ptr;
133 /* Select median value from among LO, MID, and HI. Rearrange
134 LO and HI so the three values are sorted. This lowers the
135 probability of picking a pathological pivot value and
136 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
139 QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);
141 if (QSORT_LT (_mid, _lo))
142 _QSORT_SWAP (_mid, _lo, _hold);
143 if (QSORT_LT (_hi, _mid))
144 _QSORT_SWAP (_mid, _hi, _hold);
147 if (QSORT_LT (_mid, _lo))
148 _QSORT_SWAP (_mid, _lo, _hold);
152 _right_ptr = _hi - 1;
154 /* Here's the famous ``collapse the walls'' section of quicksort.
155 Gotta like those tight inner loops! They are the main reason
156 that this algorithm runs much faster than others. */
158 while (QSORT_LT (_left_ptr, _mid))
161 while (QSORT_LT (_mid, _right_ptr))
164 if (_left_ptr < _right_ptr) {
165 _QSORT_SWAP (_left_ptr, _right_ptr, _hold);
166 if (_mid == _left_ptr)
168 else if (_mid == _right_ptr)
173 else if (_left_ptr == _right_ptr) {
178 } while (_left_ptr <= _right_ptr);
180 /* Set up pointers for next iteration. First determine whether
181 left and right partitions are below the threshold size. If so,
182 ignore one or both. Otherwise, push the larger partition's
183 bounds on the stack and continue sorting the smaller one. */
185 if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {
186 if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
187 /* Ignore both small partitions. */
188 _QSORT_POP (_lo, _hi, _top);
190 /* Ignore small left partition. */
193 else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
194 /* Ignore small right partition. */
196 else if (_right_ptr - _lo > _hi - _left_ptr) {
197 /* Push larger left partition indices. */
198 _QSORT_PUSH (_top, _lo, _right_ptr);
202 /* Push larger right partition indices. */
203 _QSORT_PUSH (_top, _left_ptr, _hi);
209 /* Once the BASE array is partially sorted by quicksort the rest
210 is completely sorted using insertion sort, since this is efficient
211 for partitions below MAX_THRESH size. BASE points to the
212 beginning of the array to sort, and END_PTR points at the very
213 last element in the array (*not* one beyond it!). */
217 QSORT_TYPE *const _end_ptr = _base + _elems - 1;
218 QSORT_TYPE *_tmp_ptr = _base;
219 register QSORT_TYPE *_run_ptr;
222 _thresh = _base + _QSORT_MAX_THRESH;
223 if (_thresh > _end_ptr)
226 /* Find smallest element in first threshold and place it at the
227 array's beginning. This is the smallest array element,
228 and the operation speeds up insertion sort's inner loop. */
230 for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)
231 if (QSORT_LT (_run_ptr, _tmp_ptr))
234 if (_tmp_ptr != _base)
235 _QSORT_SWAP (_tmp_ptr, _base, _hold);
237 /* Insertion sort, running from left-hand-side
238 * up to right-hand-side. */
240 _run_ptr = _base + 1;
241 while (++_run_ptr <= _end_ptr) {
242 _tmp_ptr = _run_ptr - 1;
243 while (QSORT_LT (_run_ptr, _tmp_ptr))
247 if (_tmp_ptr != _run_ptr) {
248 QSORT_TYPE *_trav = _run_ptr + 1;
249 while (--_trav >= _run_ptr) {
250 QSORT_TYPE *_hi, *_lo;
253 for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo)