PandA-2024.02
qsort.c
Go to the documentation of this file.
1 /* Copyright (C) 1991-2014 Free Software Foundation, Inc.
2  This file is part of the GNU C Library.
3  Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
4 
5  The GNU C Library is free software; you can redistribute it and/or
6  modify it under the terms of the GNU Lesser General Public
7  License as published by the Free Software Foundation; either
8  version 2.1 of the License, or (at your option) any later version.
9 
10  The GNU C Library is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Lesser General Public License for more details.
14 
15  You should have received a copy of the GNU Lesser General Public
16  License along with the GNU C Library; if not, see
17  <http://www.gnu.org/licenses/>. */
18 
19 /* If you consider tuning this algorithm, you should consult first:
20  Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
21  Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
22 
23 #include <limits.h>
24 #include <stdlib.h>
25 
26 /* Byte-wise swap two items of size SIZE. */
27 #define SWAP(a, b, size) \
28  do \
29  { \
30  size_t __size = (size); \
31  char *__a = (a), *__b = (b); \
32  do \
33  { \
34  char __tmp = *__a; \
35  *__a++ = *__b; \
36  *__b++ = __tmp; \
37  } while (--__size > 0); \
38  } while (0)
39 
40 /* Discontinue quicksort algorithm when partition gets below this size.
41  This particular magic number was chosen to work best on a Sun 4/260. */
42 #define MAX_THRESH 4
43 
44 /* Stack node declarations used to store unfulfilled partition obligations. */
45 typedef struct
46  {
47  char *lo;
48  char *hi;
49  } stack_node;
50 
51 /* The next 4 #defines implement a very fast in-line stack abstraction. */
52 /* The stack needs log (total_elements) entries (we could even subtract
53  log(MAX_THRESH)). Since total_elements has type size_t, we get as
54  upper bound for log (total_elements):
55  bits per byte (CHAR_BIT) * sizeof(size_t). */
56 #define STACK_SIZE (CHAR_BIT * sizeof(size_t))
57 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
58 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
59 #define STACK_NOT_EMPTY (stack < top)
60 
61 
62 /* Order size using quicksort. This implementation incorporates
63  four optimizations discussed in Sedgewick:
64 
65  1. Non-recursive, using an explicit stack of pointer that store the
66  next array partition to sort. To save time, this maximum amount
67  of space required to store an array of SIZE_MAX is allocated on the
68  stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
69  only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
70  Pretty cheap, actually.
71 
72  2. Chose the pivot element using a median-of-three decision tree.
73  This reduces the probability of selecting a bad pivot value and
74  eliminates certain extraneous comparisons.
75 
76  3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
77  insertion sort to order the MAX_THRESH items within each partition.
78  This is a big win, since insertion sort is faster for small, mostly
79  sorted array segments.
80 
81  4. The larger of the two sub-partitions is always pushed onto the
82  stack first, with the algorithm then concentrating on the
83  smaller partition. This *guarantees* no more than log (total_elems)
84  stack size is needed (actually O(1) in this case)! */
85 
86 void
87 _quicksort (void *const pbase, size_t total_elems, size_t size,
88  int (*cmp)(const void *, const void *, void *), void *arg)
89 {
90  char *base_ptr = (char *) pbase;
91 
92  const size_t max_thresh = MAX_THRESH * size;
93 
94  if (total_elems == 0)
95  /* Avoid lossage with unsigned arithmetic below. */
96  return;
97 
98  if (total_elems > MAX_THRESH)
99  {
100  char *lo = base_ptr;
101  char *hi = &lo[size * (total_elems - 1)];
103  stack_node *top = stack;
104 
105  PUSH (NULL, NULL);
106 
107  while (STACK_NOT_EMPTY)
108  {
109  char *left_ptr;
110  char *right_ptr;
111 
112  /* Select median value from among LO, MID, and HI. Rearrange
113  LO and HI so the three values are sorted. This lowers the
114  probability of picking a pathological pivot value and
115  skips a comparison for both the LEFT_PTR and RIGHT_PTR in
116  the while loops. */
117 
118  char *mid = lo + size * ((hi - lo) / size >> 1);
119 
120  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
121  SWAP (mid, lo, size);
122  if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
123  SWAP (mid, hi, size);
124  else
125  goto jump_over;
126  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
127  SWAP (mid, lo, size);
128  jump_over:;
129 
130  left_ptr = lo + size;
131  right_ptr = hi - size;
132 
133  /* Here's the famous ``collapse the walls'' section of quicksort.
134  Gotta like those tight inner loops! They are the main reason
135  that this algorithm runs much faster than others. */
136  do
137  {
138  while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
139  left_ptr += size;
140 
141  while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
142  right_ptr -= size;
143 
144  if (left_ptr < right_ptr)
145  {
146  SWAP (left_ptr, right_ptr, size);
147  if (mid == left_ptr)
148  mid = right_ptr;
149  else if (mid == right_ptr)
150  mid = left_ptr;
151  left_ptr += size;
152  right_ptr -= size;
153  }
154  else if (left_ptr == right_ptr)
155  {
156  left_ptr += size;
157  right_ptr -= size;
158  break;
159  }
160  }
161  while (left_ptr <= right_ptr);
162 
163  /* Set up pointers for next iteration. First determine whether
164  left and right partitions are below the threshold size. If so,
165  ignore one or both. Otherwise, push the larger partition's
166  bounds on the stack and continue sorting the smaller one. */
167 
168  if ((size_t) (right_ptr - lo) <= max_thresh)
169  {
170  if ((size_t) (hi - left_ptr) <= max_thresh)
171  /* Ignore both small partitions. */
172  POP (lo, hi);
173  else
174  /* Ignore small left partition. */
175  lo = left_ptr;
176  }
177  else if ((size_t) (hi - left_ptr) <= max_thresh)
178  /* Ignore small right partition. */
179  hi = right_ptr;
180  else if ((right_ptr - lo) > (hi - left_ptr))
181  {
182  /* Push larger left partition indices. */
183  PUSH (lo, right_ptr);
184  lo = left_ptr;
185  }
186  else
187  {
188  /* Push larger right partition indices. */
189  PUSH (left_ptr, hi);
190  hi = right_ptr;
191  }
192  }
193  }
194 
195  /* Once the BASE_PTR array is partially sorted by quicksort the rest
196  is completely sorted using insertion sort, since this is efficient
197  for partitions below MAX_THRESH size. BASE_PTR points to the beginning
198  of the array to sort, and END_PTR points at the very last element in
199  the array (*not* one beyond it!). */
200 
201 #define min(x, y) ((x) < (y) ? (x) : (y))
202 
203  {
204  char *const end_ptr = &base_ptr[size * (total_elems - 1)];
205  char *tmp_ptr = base_ptr;
206  char *thresh = min(end_ptr, base_ptr + max_thresh);
207  char *run_ptr;
208 
209  /* Find smallest element in first threshold and place it at the
210  array's beginning. This is the smallest array element,
211  and the operation speeds up insertion sort's inner loop. */
212 
213  for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
214  if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
215  tmp_ptr = run_ptr;
216 
217  if (tmp_ptr != base_ptr)
218  SWAP (tmp_ptr, base_ptr, size);
219 
220  /* Insertion sort, running from left-hand-side up to right-hand-side. */
221 
222  run_ptr = base_ptr + size;
223  while ((run_ptr += size) <= end_ptr)
224  {
225  tmp_ptr = run_ptr - size;
226  while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
227  tmp_ptr -= size;
228 
229  tmp_ptr += size;
230  if (tmp_ptr != run_ptr)
231  {
232  char *trav;
233 
234  trav = run_ptr + size;
235  while (--trav >= run_ptr)
236  {
237  char c = *trav;
238  char *hi, *lo;
239 
240  for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
241  *hi = *lo;
242  *hi = c;
243  }
244  }
245  }
246  }
247 }
#define NULL
void * top(node_stack *head)
Definition: tree.c:75
#define MAX_THRESH
Definition: qsort.c:42
void _quicksort(void *const pbase, size_t total_elems, size_t size, int(*cmp)(const void *, const void *, void *), void *arg)
Definition: qsort.c:87
#define POP(low, high)
Definition: qsort.c:58
Definition: tree.c:10
#define PUSH(low, high)
Definition: qsort.c:57
#define STACK_SIZE
Definition: qsort.c:56
#define STACK_NOT_EMPTY
Definition: qsort.c:59
#define min(x, y)
#define SWAP(a, b, size)
Definition: qsort.c:27

Generated on Mon Feb 12 2024 13:02:47 for PandA-2024.02 by doxygen 1.8.13