ReactOS  0.4.13-dev-551-gf37fb1f
qsort.c File Reference
#include <stdlib.h>
#include <search.h>
Include dependency graph for qsort.c:

Go to the source code of this file.

Macros

#define long   intptr_t
 
#define min(a, b)   (a) < (b) ? (a) : (b)
 
#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)
 
#define CMP(x, y)   (cmp((x), (y)))
 

Functions

static __inline void swapfunc (char *a, char *b, intptr_t n, int swaptype)
 
static __inline charmed3 (char *a, char *b, char *c, int(__cdecl *cmp)(const void *, const void *))
 
void __cdecl qsort (void *a, size_t n, size_t es, int(__cdecl *cmp)(const void *, const void *))
 

Macro Definition Documentation

◆ CMP

#define CMP (   x,
  y 
)    (cmp((x), (y)))

Definition at line 73 of file qsort.c.

◆ long

typedef void unsigned long   intptr_t

Definition at line 33 of file qsort.c.

Referenced by __do_global_ctors(), __debug_alloc< _Alloc >::__extra_after_chunk(), __debug_alloc< _Alloc >::__extra_before_chunk(), __write_formatted_timeT(), _bdf_list_ensure(), _bdf_parse_glyphs(), _bdf_readstream(), _lrotl(), _lrotr(), _svcauth_des(), _svcauth_unix(), _tr_tally(), _tzset(), access_virt_barray(), access_virt_sarray(), CInternetToolbar::AddString(), adler32_combine_(), TrimRegion::advance(), APICCalibrateTimer(), BDF_Face_Init(), bit_read_long(), bmap(), boolean(), CC_MouseCheckColorGraph(), CC_PaintCross(), CC_PaintTriangle(), check_file(), chm_openW(), conv_s16_to_u16(), convert_1970_to_filetime(), convert_utf16bom(), valarray< bool >::cshift(), __debug_alloc< _Alloc >::deallocate(), decode_header(), DefineDosDeviceW(), deflateSetDictionary(), DGifDecompressInput(), DGifGetImageDesc(), do_barray_io(), do_div(), do_sarray_io(), doflag(), DrawStarField(), dwarf2_compute_location_attr(), dwarf2_parse_udt_member(), empty(), EndLog(), ext4_ext_rm_leaf(), fill_window(), fillbytes(), FT_FixedFromFIXED(), FT_Stream_Open(), generic_head_read(), TrimRegion::getGridExtent(), GetHostByName(), CInternetToolbar::GetState(), gettimeofday(), GraphCtrl_DrawPoint(), ide_seek(), inflate_fast(), inflateMark(), Varray::init(), Uarray::init(), init_waitqueue_entry(), init_waitqueue_head(), initial_setup(), jinit_c_coef_controller(), jinit_c_main_controller(), jinit_compress_master(), jinit_d_coef_controller(), jinit_d_post_controller(), jinit_upsampler(), journal_bmap(), jpeg_add_quant_table(), jpeg_calc_output_dimensions(), jpeg_finish_compress(), jpeg_read_raw_data(), jpeg_read_scanlines(), jpeg_write_raw_data(), jpeg_write_scanlines(), main(), master_selection(), MCIQTZ_mciSetAudio(), movebytes(), mpg123_getpar(), mpg123_getstate(), output_pass_setup(), parse_arguments(), parse_new_id3(), per_scan_setup(), profPop(), PrPhilBar(), CConsole::ReadLine(), realize_virt_arrays(), rsa_exptmod(), Subdivider::samplingSplit(), SelectSetInit(), Arc::setside(), skip_input_data(), strtol(), strtoull(), symt_fill_sym_info(), synth_ntom_set_step(), test_assign(), transdecode_master_selection(), TRIO_ARGS2(), TRIO_ARGS5(), TRIO_ARGS6(), UDFInitializeFunctionPointers(), ui_create_colourmap(), WaitResponse(), wave_out_set_format(), wcstol(), wcstoul(), win32_tell_file_func(), xdr_int(), xdr_int16_t(), xdr_int32_t(), xdr_putint32(), xdr_short(), xdrrec_getlong(), xdrstdio_getlong(), xdrstdio_putlong(), xmlDictComputeFastQKey(), xmlHashComputeKey(), xmlHashComputeQKey(), xmlMemDisplayLast(), xsltGenerateIdFunction(), and zerobytes().

◆ min

#define min (   a,
  b 
)    (a) < (b) ? (a) : (b)

Definition at line 35 of file qsort.c.

◆ swap

#define swap (   a,
  b 
)
Value:
if (swaptype == 0) { \
long t = *(long *)(a); \
*(long *)(a) = *(long *)(b); \
*(long *)(b) = t; \
swapfunc(a, b, es, swaptype)
static __inline void swapfunc(char *a, char *b, intptr_t n, int swaptype)
Definition: qsort.c:55
GLdouble GLdouble t
Definition: gl.h:2047
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define es
Definition: i386-dis.c:431

Definition at line 63 of file qsort.c.

◆ swapcode

#define swapcode (   TYPE,
  parmi,
  parmj,
  n 
)
Value:
{ \
long i = (n) / sizeof (TYPE); \
register TYPE *pi = (TYPE *) (parmi); \
register TYPE *pj = (TYPE *) (parmj); \
do { \
register TYPE t = *pi; \
*pi++ = *pj; \
*pj++ = t; \
} while (--i > 0); \
}
GLdouble n
Definition: glext.h:7729
GLdouble GLdouble t
Definition: gl.h:2047
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static DWORD pi
Definition: protocol.c:150
TYPE
Definition: eventcreate.c:651

Definition at line 40 of file qsort.c.

◆ SWAPINIT

#define SWAPINIT (   a,
  es 
)
Value:
swaptype = ((char *)a - (char *)0) % sizeof(long) || \
es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
#define long
Definition: qsort.c:33
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define es
Definition: i386-dis.c:431

Definition at line 51 of file qsort.c.

◆ vecswap

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

Definition at line 71 of file qsort.c.

Function Documentation

◆ med3()

static __inline char* med3 ( char a,
char b,
char c,
int(__cdecl *cmp)(const void *, const void *)   
)
static

Definition at line 76 of file qsort.c.

77 {
78  return CMP(a, b) < 0 ?
79  (CMP(b, c) < 0 ? b : (CMP(a, c) < 0 ? c : a ))
80  :(CMP(b, c) > 0 ? b : (CMP(a, c) < 0 ? a : c ));
81 }
#define a
Definition: ke_i.h:78
#define b
Definition: ke_i.h:79
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define CMP(x, y)
Definition: qsort.c:73
const GLubyte * c
Definition: glext.h:8905
#define c
Definition: ke_i.h:80
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by qsort().

◆ qsort()

void __cdecl qsort ( void a,
size_t  n,
size_t  es,
int(__cdecl *cmp)(const void *, const void *)   
)

Definition at line 93 of file qsort.c.

94 {
95  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
96  int swaptype, swap_cnt;
97  intptr_t d, r;
98 
99 loop: SWAPINIT(a, es);
100  swap_cnt = 0;
101  if (n < 7) {
102  for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
103  for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
104  pl -= es)
105  swap(pl, pl - es);
106  return;
107  }
108  pm = (char *)a + (n / 2) * es;
109  if (n > 7) {
110  pl = a;
111  pn = (char *)a + (n - 1) * es;
112  if (n > 40) {
113  d = (n / 8) * es;
114  pl = med3(pl, pl + d, pl + 2 * d, cmp);
115  pm = med3(pm - d, pm, pm + d, cmp);
116  pn = med3(pn - 2 * d, pn - d, pn, cmp);
117  }
118  pm = med3(pl, pm, pn, cmp);
119  }
120  swap(a, pm);
121  pa = pb = (char *)a + es;
122 
123  pc = pd = (char *)a + (n - 1) * es;
124  for (;;) {
125  while (pb <= pc && (r = CMP(pb, a)) <= 0) {
126  if (r == 0) {
127  swap_cnt = 1;
128  swap(pa, pb);
129  pa += es;
130  }
131  pb += es;
132  }
133  while (pb <= pc && (r = CMP(pc, a)) >= 0) {
134  if (r == 0) {
135  swap_cnt = 1;
136  swap(pc, pd);
137  pd -= es;
138  }
139  pc -= es;
140  }
141  if (pb > pc)
142  break;
143  swap(pb, pc);
144  swap_cnt = 1;
145  pb += es;
146  pc -= es;
147  }
148  if (swap_cnt == 0) { /* Switch to insertion sort */
149  for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
150  for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
151  pl -= es)
152  swap(pl, pl - es);
153  return;
154  }
155 
156  pn = (char *)a + n * es;
157  r = min(pa - (char *)a, pb - pa);
158  vecswap(a, pb - r, r);
159  r = min(pd - pc, pn - pd - es);
160  vecswap(pb, pn - r, r);
161  if ((r = pb - pa) > es)
162  qsort(a, r / es, es, cmp);
163  if ((r = pd - pc) > es) {
164  /* Iterate rather than recurse to save stack space */
165  a = pn - r;
166  n = r / es;
167  goto loop;
168  }
169 }
#define swap(a, b)
Definition: qsort.c:63
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
static LPMONITOREX pm
Definition: localmon.c:42
GLdouble n
Definition: glext.h:7729
#define cmp(status, error)
Definition: error.c:114
#define SWAPINIT(a, es)
Definition: qsort.c:51
#define a
Definition: ke_i.h:78
#define CMP(x, y)
Definition: qsort.c:73
#define d
Definition: ke_i.h:81
int intptr_t
Definition: crtdefs.h:283
static __inline char * med3(char *a, char *b, char *c, int(__cdecl *cmp)(const void *, const void *))
Definition: qsort.c:76
void __cdecl qsort(void *a, size_t n, size_t es, int(__cdecl *cmp)(const void *, const void *))
Definition: qsort.c:93
#define vecswap(a, b, n)
Definition: qsort.c:71
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define es
Definition: i386-dis.c:431
#define min(a, b)
Definition: qsort.c:35

◆ swapfunc()

static __inline void swapfunc ( char a,
char b,
intptr_t  n,
int  swaptype 
)
static

Definition at line 55 of file qsort.c.

56 {
57  if(swaptype <= 1)
58  swapcode(long, a, b, n)
59  else
60  swapcode(char, a, b, n)
61 }
GLdouble n
Definition: glext.h:7729
#define swapcode(TYPE, parmi, parmj, n)
Definition: qsort.c:40
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204