Blender  V3.3
sort.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2013 Blender Foundation. All rights reserved. */
3 
8 #include <stdlib.h>
9 
10 #if defined(__GLIBC__) && (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8))
11 /* do nothing! */
12 #else
13 
14 # include "BLI_utildefines.h"
15 
16 # include "BLI_sort.h"
17 
18 # ifdef min /* For MSVC. */
19 # undef min
20 # endif
21 
22 /* Maintained by FreeBSD. */
23 /* clang-format off */
24 
32 BLI_INLINE char *med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk);
33 BLI_INLINE void swapfunc(char *a, char *b, int n, int swaptype);
34 
35 #define min(a, b) (a) < (b) ? (a) : (b)
36 #define swapcode(TYPE, parmi, parmj, n) \
37 { \
38  long i = (n) / sizeof(TYPE); \
39  TYPE *pi = (TYPE *) (parmi); \
40  TYPE *pj = (TYPE *) (parmj); \
41  do { \
42  TYPE t = *pi; \
43  *pi++ = *pj; \
44  *pj++ = t; \
45  } while (--i > 0); \
46 }
47 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
48  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
49 
50 BLI_INLINE void swapfunc(char *a, char *b, int n, int swaptype)
51 {
52  if (swaptype <= 1)
53  swapcode(long, a, b, n)
54  else
55  swapcode(char, a, b, n)
56 }
57 
58 #define swap(a, b) \
59  if (swaptype == 0) { \
60  long t = *(long *)(a); \
61  *(long *)(a) = *(long *)(b);\
62  *(long *)(b) = t; \
63  } else \
64  swapfunc(a, b, es, swaptype)
65 
66 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
67 #define CMP(t, x, y) (cmp((x), (y), (t)))
68 
69 BLI_INLINE char *med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk)
70 {
71  return CMP(thunk, a, b) < 0 ?
72  (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) :
73  (CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
74 }
75 
79 void 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 
84 loop:
85  SWAPINIT(a, es);
86  swap_cnt = 0;
87  if (n < 7) {
88  for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) {
89  for (pl = pm;
90  pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
91  pl -= es)
92  {
93  swap(pl, pl - es);
94  }
95  }
96  return;
97  }
98  pm = (char *)a + (n / 2) * es;
99  if (n > 7) {
100  pl = (char *)a;
101  pn = (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 = (char *)a + es;
112 
113  pc = pd = (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 = (char *)a + es; pm < (char *)a + n * es; pm += es) {
141  for (pl = pm;
142  pl > (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 = (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 #endif /* __GLIBC__ */
#define BLI_INLINE
int(* BLI_sort_cmp_t)(const void *a, const void *b, void *ctx)
Definition: BLI_sort.h:18
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
static unsigned c
Definition: RandGen.cpp:83
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
BLI_INLINE void swapfunc(char *a, char *b, int n, int swaptype)
Definition: sort.c:50
#define swap(a, b)
Definition: sort.c:58
#define vecswap(a, b, n)
Definition: sort.c:66
#define CMP(t, x, y)
Definition: sort.c:67
#define swapcode(TYPE, parmi, parmj, n)
Definition: sort.c:36
#define min(a, b)
Definition: sort.c:35
BLI_INLINE char * med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk)
Definition: sort.c:69
#define SWAPINIT(a, es)
Definition: sort.c:47
void BLI_qsort_r(void *a, size_t n, size_t es, BLI_sort_cmp_t cmp, void *thunk)
Definition: sort.c:79