Blender V5.3
sort.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2013 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <cstdlib>
10
11#include "BLI_sort.hh"
12
13namespace blender {
14
15#ifdef min /* For MSVC. */
16# undef min
17#endif
18
19/* Intentional null pointer subtraction warns with: CLANG 19.1.7. */
20#ifdef __clang__
21# pragma clang diagnostic push
22# pragma clang diagnostic ignored "-Wnull-pointer-subtraction"
23#endif
24
25/* Maintained by FreeBSD. */
26/* clang-format off */
27
35inline char *med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk);
36inline void swapfunc(char *a, char *b, int n, int swaptype);
37
38#define min(a, b) (a) < (b) ? (a) : (b)
39#define swapcode(TYPE, parmi, parmj, n) \
40{ \
41 long i = (n) / sizeof(TYPE); \
42 TYPE *pi = (TYPE *) (parmi); \
43 TYPE *pj = (TYPE *) (parmj); \
44 do { \
45 TYPE t = *pi; \
46 *pi++ = *pj; \
47 *pj++ = t; \
48 } while (--i > 0); \
49}
50#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
51 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
52
53inline void swapfunc(char *a, char *b, int n, int swaptype)
54{
55 if (swaptype <= 1)
56 swapcode(long, a, b, n)
57 else
58 swapcode(char, a, b, n)
59}
60
61#define swap(a, b) \
62 if (swaptype == 0) { \
63 long t = *(long *)(a); \
64 *(long *)(a) = *(long *)(b);\
65 *(long *)(b) = t; \
66 } else \
67 swapfunc(a, b, es, swaptype)
68
69#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
70#define CMP(t, x, y) (cmp((x), (y), (t)))
71
72inline char *med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk)
73{
74 return CMP(thunk, a, b) < 0 ?
75 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) :
76 (CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
77}
78
79void BLI_qsort_r(void *a, size_t n, size_t es, BLI_sort_cmp_t cmp, void *thunk)
80{
81 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
82 int d, r, swaptype, swap_cnt;
83
84loop:
85 SWAPINIT(a, es);
86 swap_cnt = 0;
87 if (n < 7) {
88 for (pm = static_cast<char *>(a) + es; pm < static_cast<char *>(a) + n * es; pm += es) {
89 for (pl = pm;
90 pl > static_cast<char *>(a) && CMP(thunk, pl - es, pl) > 0;
91 pl -= es)
92 {
93 swap(pl, pl - es);
94 }
95 }
96 return;
97 }
98 pm = static_cast<char *>(a) + (n / 2) * es;
99 if (n > 7) {
100 pl = static_cast<char *>(a);
101 pn = static_cast<char *>(a) + (n - 1) * es;
102 if (n > 40) {
103 d = (n / 8) * es;
104 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
105 pm = med3(pm - d, pm, pm + d, cmp, thunk);
106 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
107 }
108 pm = med3(pl, pm, pn, cmp, thunk);
109 }
110 swap((char *)a, pm);
111 pa = pb = static_cast<char *>(a) + es;
112
113 pc = pd = static_cast<char *>(a) + (n - 1) * es;
114 for (;;) {
115 while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
116 if (r == 0) {
117 swap_cnt = 1;
118 swap(pa, pb);
119 pa += es;
120 }
121 pb += es;
122 }
123 while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
124 if (r == 0) {
125 swap_cnt = 1;
126 swap(pc, pd);
127 pd -= es;
128 }
129 pc -= es;
130 }
131 if (pb > pc) {
132 break;
133 }
134 swap(pb, pc);
135 swap_cnt = 1;
136 pb += es;
137 pc -= es;
138 }
139 if (swap_cnt == 0) { /* Switch to insertion sort */
140 for (pm = static_cast<char *>(a) + es; pm < static_cast<char *>(a) + n * es; pm += es) {
141 for (pl = pm;
142 pl > static_cast<char *>(a) && CMP(thunk, pl - es, pl) > 0;
143 pl -= es)
144 {
145 swap(pl, pl - es);
146 }
147 }
148 return;
149 }
150
151 pn = static_cast<char *>(a) + n * es;
152 r = min(pa - (char *)a, pb - pa);
153 vecswap((char *)a, pb - r, r);
154 r = min(pd - pc, pn - pd - es);
155 vecswap(pb, pn - r, r);
156 if ((r = pb - pa) > es) {
157 BLI_qsort_r(a, r / es, es, cmp, thunk);
158 }
159 if ((r = pd - pc) > es) {
160 /* Iterate rather than recurse to save stack space */
161 a = pn - r;
162 n = r / es;
163 goto loop;
164 }
165}
166
167/* clang-format on */
168
169#ifdef __clang__
170# pragma clang diagnostic pop
171#endif
172
173} // namespace blender
BMesh Iterators.
void swapfunc(char *a, char *b, int n, int swaptype)
Definition sort.cc:53
char * med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk)
Definition sort.cc:72
void BLI_qsort_r(void *a, size_t n, size_t es, BLI_sort_cmp_t cmp, void *thunk)
Definition sort.cc:79
int(*) BLI_sort_cmp_t(const void *a, const void *b, void *ctx)
Definition BLI_sort.hh:22
#define swap(a, b)
Definition sort.cc:61
#define vecswap(a, b, n)
Definition sort.cc:69
#define CMP(t, x, y)
Definition sort.cc:70
#define swapcode(TYPE, parmi, parmj, n)
Definition sort.cc:39
#define min(a, b)
Definition sort.cc:38
#define SWAPINIT(a, es)
Definition sort.cc:50