1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1991, 1992, 1996, 1997 Free Software Foundation, Inc.
3 * Copyright (C) 2000 Eazel, Inc.
4 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the
18 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
23 * This file was originally part of the GNU C Library, and was modified to allow
24 * user data to be passed in to the sorting function.
26 * Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
27 * Modified by Maciej Stachowiak (mjs@eazel.com)
29 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
30 * file for a list of people on the GLib Team. See the ChangeLog
31 * files for a list of changes. These files are distributed with GLib
32 * at ftp://ftp.gtk.org/pub/gtk/.
39 /* Byte-wise swap two items of size SIZE. */
40 #define SWAP(a, b, size) \
43 register size_t __size = (size); \
44 register char *__a = (a), *__b = (b); \
50 } while (--__size > 0); \
53 /* Discontinue quicksort algorithm when partition gets below this size.
54 This particular magic number was chosen to work best on a Sun 4/260. */
57 /* Stack node declarations used to store unfulfilled partition obligations. */
65 /* The next 4 #defines implement a very fast in-line stack abstraction. */
66 #define STACK_SIZE (8 * sizeof(unsigned long int))
67 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
68 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
69 #define STACK_NOT_EMPTY (stack < top)
72 /* Order size using quicksort. This implementation incorporates
73 * four optimizations discussed in Sedgewick:
75 * 1. Non-recursive, using an explicit stack of pointer that store the next
76 * array partition to sort. To save time, this maximum amount of space
77 * required to store an array of MAX_INT is allocated on the stack. Assuming
78 * a 32-bit integer, this needs only 32 * sizeof(stack_node) == 136 bits.
79 * Pretty cheap, actually.
81 * 2. Chose the pivot element using a median-of-three decision tree. This
82 * reduces the probability of selecting a bad pivot value and eliminates
83 * certain * extraneous comparisons.
85 * 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving insertion
86 * sort to order the MAX_THRESH items within each partition. This is a big
87 * win, since insertion sort is faster for small, mostly sorted array
90 * 4. The larger of the two sub-partitions is always pushed onto the stack
91 * first, with the algorithm then concentrating on the smaller partition.
92 * This *guarantees* no more than log (n) stack size is needed (actually O(1)
98 * @pbase: start of array to sort
99 * @total_elems: elements in the array
100 * @size: size of each element
101 * @compare_func: function to compare elements
102 * @user_data: data to pass to @compare_func
104 * This is just like the standard C qsort() function, but
105 * the comparison routine accepts a user data argument.
109 g_qsort_with_data (gconstpointer pbase
,
112 GCompareDataFunc compare_func
,
115 register char *base_ptr
= (char *) pbase
;
117 /* Allocating SIZE bytes for a pivot buffer facilitates a better
118 * algorithm below since we can do comparisons directly on the pivot.
120 char *pivot_buffer
= (char *) alloca (size
);
121 const size_t max_thresh
= MAX_THRESH
* size
;
123 g_return_if_fail (total_elems
> 0);
124 g_return_if_fail (pbase
!= NULL
);
125 g_return_if_fail (compare_func
!= NULL
);
127 if (total_elems
> MAX_THRESH
)
130 char *hi
= &lo
[size
* (total_elems
- 1)];
131 /* Largest size needed for 32-bit int!!! */
132 stack_node stack
[STACK_SIZE
];
133 stack_node
*top
= stack
+ 1;
135 while (STACK_NOT_EMPTY
)
140 char *pivot
= pivot_buffer
;
142 /* Select median value from among LO, MID, and HI. Rearrange
143 * LO and HI so the three values are sorted. This lowers the
144 * probability of picking a pathological pivot value and
145 * skips a comparison for both the LEFT_PTR and RIGHT_PTR. */
147 char *mid
= lo
+ size
* ((hi
- lo
) / size
>> 1);
149 if ((*compare_func
) ((void *) mid
, (void *) lo
, user_data
) < 0)
150 SWAP (mid
, lo
, size
);
151 if ((*compare_func
) ((void *) hi
, (void *) mid
, user_data
) < 0)
152 SWAP (mid
, hi
, size
);
155 if ((*compare_func
) ((void *) mid
, (void *) lo
, user_data
) < 0)
156 SWAP (mid
, lo
, size
);
158 memcpy (pivot
, mid
, size
);
159 pivot
= pivot_buffer
;
161 left_ptr
= lo
+ size
;
162 right_ptr
= hi
- size
;
164 /* Here's the famous ``collapse the walls'' section of quicksort.
165 * Gotta like those tight inner loops! They are the main reason
166 * that this algorithm runs much faster than others. */
169 while ((*compare_func
)
170 ((void *) left_ptr
, (void *) pivot
,
174 while ((*compare_func
)
175 ((void *) pivot
, (void *) right_ptr
,
179 if (left_ptr
< right_ptr
)
181 SWAP (left_ptr
, right_ptr
, size
);
185 else if (left_ptr
== right_ptr
)
192 while (left_ptr
<= right_ptr
);
194 /* Set up pointers for next iteration. First determine whether
195 * left and right partitions are below the threshold size. If so,
196 * ignore one or both. Otherwise, push the larger partition's
197 * bounds on the stack and continue sorting the smaller one. */
199 if ((size_t) (right_ptr
- lo
) <= max_thresh
)
201 if ((size_t) (hi
- left_ptr
) <= max_thresh
)
202 /* Ignore both small partitions. */
205 /* Ignore small left partition. */
208 else if ((size_t) (hi
- left_ptr
) <= max_thresh
)
209 /* Ignore small right partition. */
211 else if ((right_ptr
- lo
) > (hi
- left_ptr
))
213 /* Push larger left partition indices. */
214 PUSH (lo
, right_ptr
);
220 /* Push larger right partition indices. */
227 /* Once the BASE_PTR array is partially sorted by quicksort the rest
228 * is completely sorted using insertion sort, since this is efficient
229 * for partitions below MAX_THRESH size. BASE_PTR points to the beginning
230 * of the array to sort, and END_PTR points at the very last element in
231 * the array (*not* one beyond it!). */
234 char *const end_ptr
= &base_ptr
[size
* (total_elems
- 1)];
235 char *tmp_ptr
= base_ptr
;
236 char *thresh
= MIN (end_ptr
, base_ptr
+ max_thresh
);
237 register char *run_ptr
;
239 /* Find smallest element in first threshold and place it at the
240 * array's beginning. This is the smallest array element,
241 * and the operation speeds up insertion sort's inner loop. */
243 for (run_ptr
= tmp_ptr
+ size
; run_ptr
<= thresh
;
245 size
) if ((*compare_func
) ((void *) run_ptr
, (void *) tmp_ptr
,
249 if (tmp_ptr
!= base_ptr
)
250 SWAP (tmp_ptr
, base_ptr
, size
);
252 /* Insertion sort, running from left-hand-side up to right-hand-side. */
254 run_ptr
= base_ptr
+ size
;
255 while ((run_ptr
+= size
) <= end_ptr
)
257 tmp_ptr
= run_ptr
- size
;
258 while ((*compare_func
)
259 ((void *) run_ptr
, (void *) tmp_ptr
,
264 if (tmp_ptr
!= run_ptr
)
268 trav
= run_ptr
+ size
;
269 while (--trav
>= run_ptr
)
275 (lo
-= size
) >= tmp_ptr
; hi
= lo
)