PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
qsort_arg.c File Reference
#include "c.h"
Include dependency graph for qsort_arg.c:

Go to the source code of this file.

Macros

#define swapcode(TYPE, parmi, parmj, n)
 
#define SWAPINIT(a, es)
 
#define swap(a, b)
 
#define vecswap(a, b, n)   if ((n) > 0) swapfunc(a, b, n, swaptype)
 

Functions

static char * med3 (char *a, char *b, char *c, qsort_arg_comparator cmp, void *arg)
 
static void swapfunc (char *, char *, size_t, int)
 
void qsort_arg (void *a, size_t n, size_t es, qsort_arg_comparator cmp, void *arg)
 

Macro Definition Documentation

#define swap (   a,
 
)
Value:
if (swaptype == 0) { \
long t = *(long *)(void *)(a); \
*(long *)(void *)(a) = *(long *)(void *)(b); \
*(long *)(void *)(b) = t; \
swapfunc(a, b, es, swaptype)
static void swapfunc(char *, char *, size_t, int)
Definition: qsort_arg.c:86

Definition at line 94 of file qsort_arg.c.

Referenced by qsort_arg().

#define swapcode (   TYPE,
  parmi,
  parmj,
 
)
Value:
do { \
size_t i = (n) / sizeof (TYPE); \
TYPE *pi = (TYPE *)(void *)(parmi); \
TYPE *pj = (TYPE *)(void *)(parmj); \
do { \
TYPE t = *pi; \
*pi++ = *pj; \
*pj++ = t; \
} while (--i > 0); \
} while (0)
int i

Definition at line 70 of file qsort_arg.c.

Referenced by swapfunc().

#define SWAPINIT (   a,
  es 
)
Value:
swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
(es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1;

Definition at line 82 of file qsort_arg.c.

Referenced by qsort_arg().

#define vecswap (   a,
  b,
 
)    if ((n) > 0) swapfunc(a, b, n, swaptype)

Definition at line 102 of file qsort_arg.c.

Referenced by qsort_arg().

Function Documentation

static char * med3 ( char *  a,
char *  b,
char *  c,
qsort_arg_comparator  cmp,
void *  arg 
)
static

Definition at line 105 of file qsort_arg.c.

References cmp().

Referenced by qsort_arg().

106 {
107  return cmp(a, b, arg) < 0 ?
108  (cmp(b, c, arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
109  : (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
110 }
char * c
void * arg
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
void qsort_arg ( void *  a,
size_t  n,
size_t  es,
qsort_arg_comparator  cmp,
void *  arg 
)

Definition at line 113 of file qsort_arg.c.

References cmp(), med3(), Min, swap, SWAPINIT, and vecswap.

Referenced by _bt_sort_array_elements(), compute_range_stats(), compute_scalar_stats(), gbt_num_picksplit(), gbt_var_picksplit(), ginExtractEntries(), isort(), mcelem_array_selec(), ndistinct_for_combination(), range_gist_double_sorting_split(), range_gist_single_sorting_split(), RelationBuildPartitionDesc(), SortAndUniqItems(), spg_range_quad_picksplit(), startScanKey(), tbm_prepare_shared_iterate(), tsvectorrecv(), uniqueentry(), and uniqueifyJsonbObject().

114 {
115  char *pa,
116  *pb,
117  *pc,
118  *pd,
119  *pl,
120  *pm,
121  *pn;
122  size_t d1,
123  d2;
124  int r,
125  swaptype,
126  presorted;
127 
128 loop:SWAPINIT(a, es);
129  if (n < 7)
130  {
131  for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
132  for (pl = pm; pl > (char *) a && cmp(pl - es, pl, arg) > 0;
133  pl -= es)
134  swap(pl, pl - es);
135  return;
136  }
137  presorted = 1;
138  for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
139  {
140  if (cmp(pm - es, pm, arg) > 0)
141  {
142  presorted = 0;
143  break;
144  }
145  }
146  if (presorted)
147  return;
148  pm = (char *) a + (n / 2) * es;
149  if (n > 7)
150  {
151  pl = (char *) a;
152  pn = (char *) a + (n - 1) * es;
153  if (n > 40)
154  {
155  size_t d = (n / 8) * es;
156 
157  pl = med3(pl, pl + d, pl + 2 * d, cmp, arg);
158  pm = med3(pm - d, pm, pm + d, cmp, arg);
159  pn = med3(pn - 2 * d, pn - d, pn, cmp, arg);
160  }
161  pm = med3(pl, pm, pn, cmp, arg);
162  }
163  swap(a, pm);
164  pa = pb = (char *) a + es;
165  pc = pd = (char *) a + (n - 1) * es;
166  for (;;)
167  {
168  while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
169  {
170  if (r == 0)
171  {
172  swap(pa, pb);
173  pa += es;
174  }
175  pb += es;
176  }
177  while (pb <= pc && (r = cmp(pc, a, arg)) >= 0)
178  {
179  if (r == 0)
180  {
181  swap(pc, pd);
182  pd -= es;
183  }
184  pc -= es;
185  }
186  if (pb > pc)
187  break;
188  swap(pb, pc);
189  pb += es;
190  pc -= es;
191  }
192  pn = (char *) a + n * es;
193  d1 = Min(pa - (char *) a, pb - pa);
194  vecswap(a, pb - d1, d1);
195  d1 = Min(pd - pc, pn - pd - es);
196  vecswap(pb, pn - d1, d1);
197  d1 = pb - pa;
198  d2 = pd - pc;
199  if (d1 <= d2)
200  {
201  /* Recurse on left partition, then iterate on right partition */
202  if (d1 > es)
203  qsort_arg(a, d1 / es, es, cmp, arg);
204  if (d2 > es)
205  {
206  /* Iterate rather than recurse to save stack space */
207  /* qsort_arg(pn - d2, d2 / es, es, cmp, arg); */
208  a = pn - d2;
209  n = d2 / es;
210  goto loop;
211  }
212  }
213  else
214  {
215  /* Recurse on right partition, then iterate on left partition */
216  if (d2 > es)
217  qsort_arg(pn - d2, d2 / es, es, cmp, arg);
218  if (d1 > es)
219  {
220  /* Iterate rather than recurse to save stack space */
221  /* qsort_arg(a, d1 / es, es, cmp, arg); */
222  n = d1 / es;
223  goto loop;
224  }
225  }
226 }
#define Min(x, y)
Definition: c.h:806
void qsort_arg(void *a, size_t n, size_t es, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
#define SWAPINIT(a, es)
Definition: qsort_arg.c:82
static char * med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:105
#define vecswap(a, b, n)
Definition: qsort_arg.c:102
#define swap(a, b)
Definition: qsort_arg.c:94
void * arg
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
static void swapfunc ( char *  a,
char *  b,
size_t  n,
int  swaptype 
)
static

Definition at line 86 of file qsort_arg.c.

References swapcode.

87 {
88  if (swaptype <= 1)
89  swapcode(long, a, b, n);
90  else
91  swapcode(char, a, b, n);
92 }
#define swapcode(TYPE, parmi, parmj, n)
Definition: qsort_arg.c:70