ReactOS 0.4.16-dev-289-g096a551
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(), __remainder_piby2(), __remainder_piby2f(), __write_formatted_timeT(), _bdf_list_ensure(), _bdf_parse_glyphs(), _bdf_readstream(), _lrotl(), _lrotr(), _mm_movpi64_epi64(), _svcauth_des(), _svcauth_unix(), _tzset(), access_virt_barray(), access_virt_sarray(), CInternetToolbar::AddString(), adler32_combine_(), TrimRegion::advance(), APICCalibrateTimer(), BDF_Face_Init(), bit_read_long(), bmap(), CC_MouseCheckColorGraph(), CC_PaintCross(), CC_PaintTriangle(), check_file(), chm_openW(), convert_1970_to_filetime(), convert_utf16bom(), __debug_alloc< _Alloc >::deallocate(), decode_header(), DefineDosDeviceW(), deflateSetDictionary(), DGifDecompressInput(), DGifGetImageDesc(), do_barray_io(), do_div(), do_sarray_io(), doflag(), DrawStarField(), empty(), EndLog(), ext4_ext_rm_leaf(), fill_window(), fillbytes(), floor(), FT_FixedFromFIXED(), FT_Stream_Open(), generic_head_read(), TrimRegion::getGridExtent(), GetHostByName(), CInternetToolbar::GetState(), gettimeofday(), handle_apetag(), 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(), PrPhilBar(), CConsole::ReadLine(), ReadUnalignedU32(), ReadUnalignedU64(), realize_virt_arrays(), remainder(), rsa_exptmod(), Subdivider::samplingSplit(), SelectSetInit(), set_pointer(), Arc::setside(), START_TEST(), strtol(), strtoull(), synth_ntom_set_step(), test_assign(), transdecode_master_selection(), TRIO_ARGS2(), UDFInitializeFunctionPointers(), ui_create_colourmap(), vio_modern_query_vq_alloc(), 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(), 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; \
} else \
swapfunc(a, b, es, swaptype)
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:440

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); \
}
TYPE
Definition: eventcreate.c:652
GLdouble n
Definition: glext.h:7729
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 refpint_t pi[]
Definition: server.c:96

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

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}
const GLubyte * c
Definition: glext.h:8905
#define a
Definition: ke_i.h:78
#define c
Definition: ke_i.h:80
#define b
Definition: ke_i.h:79
#define CMP(x, y)
Definition: qsort.c:73

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
99loop: 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}
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define d
Definition: ke_i.h:81
static LPMONITOREX pm
Definition: localmon.c:45
#define cmp(status, error)
Definition: error.c:114
static int pints_t pn[]
Definition: server.c:129
static int ** pa
Definition: server.c:126
void __cdecl qsort(void *a, size_t n, size_t es, int(__cdecl *cmp)(const void *, const void *))
Definition: qsort.c:93
#define swap(a, b)
Definition: qsort.c:63
static __inline char * med3(char *a, char *b, char *c, int(__cdecl *cmp)(const void *, const void *))
Definition: qsort.c:76
#define vecswap(a, b, n)
Definition: qsort.c:71
#define min(a, b)
Definition: qsort.c:35
#define SWAPINIT(a, es)
Definition: qsort.c:51
int intptr_t
Definition: vcruntime.h:134

Referenced by qsort().

◆ 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}
#define swapcode(TYPE, parmi, parmj, n)
Definition: qsort.c:40