qsort.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
3  *
4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5  *
6  * This file contains Original Code and/or Modifications of Original Code
7  * as defined in and that are subject to the Apple Public Source License
8  * Version 2.0 (the 'License'). You may not use this file except in
9  * compliance with the License. The rights granted to you under the License
10  * may not be used to create, or enable the creation or redistribution of,
11  * unlawful or unlicensed copies of an Apple operating system, or to
12  * circumvent, violate, or enable the circumvention or violation of, any
13  * terms of an Apple operating system software license agreement.
14  *
15  * Please obtain a copy of the License at
16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
17  *
18  * The Original Code and all software distributed under the License are
19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23  * Please see the License for the specific language governing rights and
24  * limitations under the License.
25  *
26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27  */
28 /*
29  * Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved
30  *
31  * Copyright (c) 1992, 1993
32  * The Regents of the University of California. All rights reserved.
33  *
34  * Redistribution and use in source and binary forms, with or without
35  * modification, are permitted provided that the following conditions
36  * are met:
37  * 1. Redistributions of source code must retain the above copyright
38  * notice, this list of conditions and the following disclaimer.
39  * 2. Redistributions in binary form must reproduce the above copyright
40  * notice, this list of conditions and the following disclaimer in the
41  * documentation and/or other materials provided with the distribution.
42  * 3. All advertising materials mentioning features or use of this software
43  * must display the following acknowledgement:
44  * This product includes software developed by the University of
45  * California, Berkeley and its contributors.
46  * 4. Neither the name of the University nor the names of its contributors
47  * may be used to endorse or promote products derived from this software
48  * without specific prior written permission.
49  *
50  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
51  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
52  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
53  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
54  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
55  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
56  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
57  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
58  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
59  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
60  * SUCH DAMAGE.
61  *
62  * @(#)qsort.c 8.1 (Berkeley) 6/4/93
63  */
64 
65 /*
66  * Grabbed from XNU source code with minor modifications:
67  * https://opensource.apple.com/source/xnu/xnu-3248.60.10/bsd/kern/qsort.c
68  */
69 #ifndef CS_QSORT_H
70 #define CS_QSORT_H
71 
72 #include <libkern/libkern.h>
73 
74 #pragma clang diagnostic push
75 #pragma clang diagnostic ignored "-Wshorten-64-to-32"
76 
77 void
78 qsort(void *a, size_t n, size_t es, int (*cmp)(const void *, const void *));
79 
80 static inline char *med3(char *, char *, char *, int (*)(const void *, const void *));
81 static inline void swapfunc(char *, char *, int, int);
82 
83 #define min(a, b) (a) < (b) ? a : b
84 
85 /*
86  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
87  */
88 #define swapcode(TYPE, parmi, parmj, n) { \
89  long i = (n) / sizeof (TYPE); \
90  TYPE *pi = (TYPE *) (parmi); \
91  TYPE *pj = (TYPE *) (parmj); \
92  do { \
93  TYPE t = *pi; \
94  *pi++ = *pj; \
95  *pj++ = t; \
96  } while (--i > 0); \
97 }
98 
99 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
100  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
101 
102 static inline void
103 swapfunc(char *a, char *b, int n, int swaptype)
104 {
105  if(swaptype <= 1)
106  swapcode(long, a, b, n)
107  else
108  swapcode(char, a, b, n)
109 }
110 
111 #define swap(a, b) \
112  if (swaptype == 0) { \
113  long t = *(long *)(a); \
114  *(long *)(a) = *(long *)(b); \
115  *(long *)(b) = t; \
116  } else \
117  swapfunc(a, b, es, swaptype)
118 
119 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
120 
121 static inline char *
122 med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
123 {
124  return cmp(a, b) < 0 ?
125  (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
126  :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
127 }
128 
129 void
130 qsort(void *a, size_t n, size_t es, int (*cmp)(const void *, const void *))
131 {
132  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
133  int d, swaptype, swap_cnt;
134  int r;
135 
136 loop: SWAPINIT(a, es);
137  swap_cnt = 0;
138  if (n < 7) {
139  for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
140  for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
141  pl -= es)
142  swap(pl, pl - es);
143  return;
144  }
145  pm = (char *)a + (n / 2) * es;
146  if (n > 7) {
147  pl = a;
148  pn = (char *)a + (n - 1) * es;
149  if (n > 40) {
150  d = (n / 8) * es;
151  pl = med3(pl, pl + d, pl + 2 * d, cmp);
152  pm = med3(pm - d, pm, pm + d, cmp);
153  pn = med3(pn - 2 * d, pn - d, pn, cmp);
154  }
155  pm = med3(pl, pm, pn, cmp);
156  }
157  swap(a, pm);
158  pa = pb = (char *)a + es;
159 
160  pc = pd = (char *)a + (n - 1) * es;
161  for (;;) {
162  while (pb <= pc && (r = cmp(pb, a)) <= 0) {
163  if (r == 0) {
164  swap_cnt = 1;
165  swap(pa, pb);
166  pa += es;
167  }
168  pb += es;
169  }
170  while (pb <= pc && (r = cmp(pc, a)) >= 0) {
171  if (r == 0) {
172  swap_cnt = 1;
173  swap(pc, pd);
174  pd -= es;
175  }
176  pc -= es;
177  }
178  if (pb > pc)
179  break;
180  swap(pb, pc);
181  swap_cnt = 1;
182  pb += es;
183  pc -= es;
184  }
185  if (swap_cnt == 0) { /* Switch to insertion sort */
186  for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
187  for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
188  pl -= es)
189  swap(pl, pl - es);
190  return;
191  }
192 
193  pn = (char *)a + n * es;
194  r = min(pa - (char *)a, pb - pa);
195  vecswap(a, pb - r, r);
196  r = min((size_t)(pd - pc), pn - pd - es);
197  vecswap(pb, pn - r, r);
198  if ((size_t)(r = pb - pa) > es)
199  qsort(a, r / es, es, cmp);
200  if ((size_t)(r = pd - pc) > es) {
201  /* Iterate rather than recurse to save stack space */
202  a = pn - r;
203  n = r / es;
204  goto loop;
205  }
206 /* qsort(pn - r, r / es, es, cmp);*/
207 }
208 
209 #pragma clang diagnostic pop
210 
211 #endif
async_greeter_server_with_graceful_shutdown.loop
loop
Definition: async_greeter_server_with_graceful_shutdown.py:59
a
int a
Definition: abseil-cpp/absl/container/internal/hash_policy_traits_test.cc:88
swapfunc
static void swapfunc(char *, char *, int, int)
Definition: qsort.h:103
SWAPINIT
#define SWAPINIT(a, es)
Definition: qsort.h:99
c
void c(T a)
Definition: miscompile_with_no_unique_address_test.cc:40
swap
#define swap(a, b)
Definition: qsort.h:111
med3
static char * med3(char *, char *, char *, int(*)(const void *, const void *))
Definition: qsort.h:122
tests.google.protobuf.internal.message_test.cmp
cmp
Definition: bloaty/third_party/protobuf/python/compatibility_tests/v2.5.0/tests/google/protobuf/internal/message_test.py:61
min
#define min(a, b)
Definition: qsort.h:83
b
uint64_t b
Definition: abseil-cpp/absl/container/internal/layout_test.cc:53
d
static const fe d
Definition: curve25519_tables.h:19
qsort
void qsort(void *a, size_t n, size_t es, int(*cmp)(const void *, const void *))
Definition: qsort.h:130
n
int n
Definition: abseil-cpp/absl/container/btree_test.cc:1080
vecswap
#define vecswap(a, b, n)
Definition: qsort.h:119
fix_build_deps.r
r
Definition: fix_build_deps.py:491
swapcode
#define swapcode(TYPE, parmi, parmj, n)
Definition: qsort.h:88

grpc
Author(s):
autogenerated on Thu Mar 13 2025 03:00:59