301 
301 
((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))

302 
302 

303 
303 
typedef int (cmpfunc_t)(const void*, const void*, void*);


304 


305 
static void


306 
ruby_isort(char *l, char *r, cmpfunc_t *cmp, void *d, const size_t size)


307 
{


308 
char *p, *q, *v;


309 
size_t i;


310 


311 
v = ALLOCA_N(char, size);


312 


313 
for(p = l + size; p <= r; p += size) {


314 
if (cmp(p  size, p, d) <= 0)


315 
continue;


316 


317 
memcpy(v, p, size);


318 
i = 1;


319 
for (q = p  2 * size; q >= l && cmp(q, v, d) > 0; q = size) {


320 
i++;


321 
}


322 
memmove(q + 2 * size, q + size, i * size);


323 
memcpy(q + size, v, size);


324 
}


325 
}


326 

304 
327 
void

305 
328 
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)

306 
329 
{

...  ...  
308 
331 
register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */

309 
332 
char *L = base; /* left end of current region */

310 
333 
char *R = (char*)base + size*(nel1); /* right end of current region */

311 

size_t chklim = 63; /* threshold of ordering element check */


334 
size_t chklim = 9; /* threshold of ordering element check */

312 
335 
stack_node stack[32], *top = stack; /* 32 is enough for 32bit CPU */

313 
336 
int mmkind;

314 
337 
size_t high, low, n;

...  ...  
327 
350 
if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;

328 
351 
}

329 
352 


353 
n = (R  L + size) / size; /* number of elements */


354 
if (n < chklim) { /* Sort small sub problems (9 is empirical) with insertion sort */


355 
ruby_isort(L, R, cmp, d, size);


356 
goto nxt;


357 
}

330 
358 
l = L; r = R;

331 

n = (r  l + size) / size; /* number of elements */

332 
359 
m = l + size * (n >> 1); /* calculate median value */

333 
360 

334 
361 
if (n >= 60) {

...  ...  
366 
393 
fail: goto loopA; /*357*/

367 
394 
}

368 
395 
if (t > 0) {

369 

if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*354*/


396 
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*354*/

370 
397 
mmrot3(r,m,l); goto loopA; /*352*/

371 
398 
}

372 
399 
goto loopB; /*355*/

...  ...  
374 
401 

375 
402 
if (t > 0) { /*75?*/

376 
403 
if ((t = (*cmp)(m,r,d)) > 0) { /*753*/

377 

if (chklim && nel >= chklim) { /* check if already ascending order */


404 
if (chklim && nel >= chklim) { /* check if already descending order */

378 
405 
char *p;

379 
406 
chklim = 0;

380 
407 
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
