19682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* qsort.c 29682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * (c) 1998 Gareth McCaughan 39682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 49682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * This is a drop-in replacement for the C library's |qsort()| routine. 59682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 69682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * Features: 79682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - Median-of-three pivoting (and more) 89682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - Truncation and final polishing by a single insertion sort 99682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - Early truncation when no swaps needed in pivoting step 109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - Explicit recursion, guaranteed not to overflow 119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - A few little wrinkles stolen from the GNU |qsort()|. 129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - separate code for non-aligned / aligned / word-size objects 139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * This code may be reproduced freely provided 159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - this file is retained unaltered apart from minor 169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * changes for portability and efficiency 179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - no changes are made to this comment 189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - any changes that *are* made are clearly flagged 199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - the _ID string below is altered by inserting, after 209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * the date, the string " altered" followed at your option 219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * by other material. (Exceptions: you may change the name 229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * of the exported routine without changing the ID string. 239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * You may change the values of the macros TRUNC_* and 249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * PIVOT_THRESHOLD without changing the ID string, provided 259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * they remain constants with TRUNC_nonaligned, TRUNC_aligned 269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and TRUNC_words/WORD_BYTES between 8 and 24, and 279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * PIVOT_THRESHOLD between 32 and 200.) 289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * You may use it in anything you like; you may make money 309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * out of it; you may distribute it in object form or as 319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * part of an executable without including source code; 329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * you don't have to credit me. (But it would be nice if 339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * you did.) 349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * If you find problems with this code, or find ways of 369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * making it significantly faster, please let me know! 379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * My e-mail address, valid as of early 1998 and certainly 389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * OK for at least the next 18 months, is 399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * gjm11@dpmms.cam.ac.uk 409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * Thanks! 419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * Gareth McCaughan Peterhouse Cambridge 1998 439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include "SDL_config.h" 459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* 479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <assert.h> 489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <stdlib.h> 499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <string.h> 509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall*/ 519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include "SDL_stdinc.h" 529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef assert 549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#undef assert 559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define assert(X) 579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef malloc 589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#undef malloc 599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define malloc SDL_malloc 619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef free 629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#undef free 639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define free SDL_free 659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef memcpy 669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#undef memcpy 679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define memcpy SDL_memcpy 699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef memmove 709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#undef memmove 719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define memmove SDL_memmove 739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef qsort 749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#undef qsort 759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define qsort SDL_qsort 779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifndef HAVE_QSORT 809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstatic char _ID[]="<qsort.c gjm 1.12 1998-03-19>"; 829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* How many bytes are there per word? (Must be a power of 2, 849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and must in fact equal sizeof(int).) 859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define WORD_BYTES sizeof(int) 879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* How big does our stack need to be? Answer: one entry per 899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * bit in a |size_t|. 909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define STACK_SIZE (8*sizeof(size_t)) 929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* Different situations have slightly different requirements, 949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and we make life epsilon easier by using different truncation 959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * points for the three different cases. 969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * So far, I have tuned TRUNC_words and guessed that the same 979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * value might work well for the other two cases. Of course 989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * what works well on my machine might work badly on yours. 999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 1009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define TRUNC_nonaligned 12 1019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define TRUNC_aligned 12 1029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ 1039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* We use a simple pivoting algorithm for shortish sub-arrays 1059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and a more complicated one for larger ones. The threshold 1069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * is PIVOT_THRESHOLD. 1079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 1089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define PIVOT_THRESHOLD 40 1099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Halltypedef struct { char * first; char * last; } stack_entry; 1119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} 1129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} 1139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define doLeft {first=ffirst;llast=last;continue;} 1149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define doRight {ffirst=first;last=llast;continue;} 1159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define pop {if (--stacktop<0) break;\ 1169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first=ffirst=stack[stacktop].first;\ 1179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall last=llast=stack[stacktop].last;\ 1189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall continue;} 1199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* Some comments on the implementation. 1219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 1. When we finish partitioning the array into "low" 1229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and "high", we forget entirely about short subarrays, 1239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * because they'll be done later by insertion sort. 1249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * Doing lots of little insertion sorts might be a win 1259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * on large datasets for locality-of-reference reasons, 1269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * but it makes the code much nastier and increases 1279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * bookkeeping overhead. 1289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 2. We always save the shorter and get to work on the 1299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * longer. This guarantees that every time we push 1309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * an item onto the stack its size is <= 1/2 of that 1319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * of its parent; so the stack can't need more than 1329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * log_2(max-array-size) entries. 1339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 3. We choose a pivot by looking at the first, last 1349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and middle elements. We arrange them into order 1359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * because it's easy to do that in conjunction with 1369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * choosing the pivot, and it makes things a little 1379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * easier in the partitioning step. Anyway, the pivot 1389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * is the middle of these three. It's still possible 1399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * to construct datasets where the algorithm takes 1409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * time of order n^2, but it simply never happens in 1419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * practice. 1429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 3' Newsflash: On further investigation I find that 1439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * it's easy to construct datasets where median-of-3 1449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * simply isn't good enough. So on large-ish subarrays 1459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * we do a more sophisticated pivoting: we take three 1469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * sets of 3 elements, find their medians, and then 1479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * take the median of those. 1489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 4. We copy the pivot element to a separate place 1499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * because that way we can always do our comparisons 1509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * directly against a pointer to that separate place, 1519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and don't have to wonder "did we move the pivot 1529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * element?". This makes the inner loop better. 1539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 5. It's possible to make the pivoting even more 1549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * reliable by looking at more candidates when n 1559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * is larger. (Taking this to its logical conclusion 1569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * results in a variant of quicksort that doesn't 1579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * have that n^2 worst case.) However, the overhead 1589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * from the extra bookkeeping means that it's just 1599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * not worth while. 1609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 6. This is pretty clean and portable code. Here are 1619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * all the potential portability pitfalls and problems 1629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * I know of: 1639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - In one place (the insertion sort) I construct 1649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * a pointer that points just past the end of the 1659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * supplied array, and assume that (a) it won't 1669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * compare equal to any pointer within the array, 1679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and (b) it will compare equal to a pointer 1689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * obtained by stepping off the end of the array. 1699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * These might fail on some segmented architectures. 1709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - I assume that there are 8 bits in a |char| when 1719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * computing the size of stack needed. This would 1729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * fail on machines with 9-bit or 16-bit bytes. 1739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - I assume that if |((int)base&(sizeof(int)-1))==0| 1749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * and |(size&(sizeof(int)-1))==0| then it's safe to 1759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * get at array elements via |int*|s, and that if 1769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * actually |size==sizeof(int)| as well then it's 1779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * safe to treat the elements as |int|s. This might 1789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * fail on systems that convert pointers to integers 1799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * in non-standard ways. 1809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * - I assume that |8*sizeof(size_t)<=INT_MAX|. This 1819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * would be false on a machine with 8-bit |char|s, 1829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * 16-bit |int|s and 4096-bit |size_t|s. :-) 1839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 1849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* The recursion logic is the same in each case: */ 1869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define Recurse(Trunc) \ 1879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { size_t l=last-ffirst,r=llast-first; \ 1889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (l<Trunc) { \ 1899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (r>=Trunc) doRight \ 1909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else pop \ 1919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } \ 1929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else if (l<=r) { pushLeft; doRight } \ 1939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else if (r>=Trunc) { pushRight; doLeft }\ 1949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else doLeft \ 1959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 1969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 1979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* and so is the pivoting logic: */ 1989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define Pivot(swapper,sz) \ 1999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ 2009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else { \ 2019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (compare(first,mid)<0) { \ 2029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (compare(mid,last)>0) { \ 2039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall swapper(mid,last); \ 2049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (compare(first,mid)>0) swapper(first,mid);\ 2059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } \ 2069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } \ 2079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else { \ 2089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (compare(mid,last)>0) swapper(first,last)\ 2099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else { \ 2109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall swapper(first,mid); \ 2119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (compare(mid,last)>0) swapper(mid,last);\ 2129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } \ 2139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } \ 2149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first+=sz; last-=sz; \ 2159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 2189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <stdio.h> 2199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 2209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* and so is the partitioning logic: */ 2229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define Partition(swapper,sz) { \ 2239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int swapped=0; \ 2249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall do { \ 2259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall while (compare(first,pivot)<0) first+=sz; \ 2269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall while (compare(pivot,last)<0) last-=sz; \ 2279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (first<last) { \ 2289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall swapper(first,last); swapped=1; \ 2299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first+=sz; last-=sz; } \ 2309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else if (first==last) { first+=sz; last-=sz; break; }\ 2319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } while (first<=last); \ 2329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (!swapped) pop \ 2339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 2349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* and so is the pre-insertion-sort operation of putting 2369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * the smallest element into place as a sentinel. 2379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * Doing this makes the inner loop nicer. I got this 2389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * idea from the GNU implementation of qsort(). 2399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall */ 2409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define PreInsertion(swapper,limit,sz) \ 2419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first=base; \ 2429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall last=first + (nmemb>limit ? limit : nmemb-1)*sz;\ 2439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall while (last!=base) { \ 2449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (compare(first,last)>0) first=last; \ 2459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall last-=sz; } \ 2469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (first!=base) swapper(first,(char*)base); 2479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* and so is the insertion sort, in the first two cases: */ 2499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define Insertion(swapper) \ 2509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall last=((char*)base)+nmemb*size; \ 2519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall for (first=((char*)base)+size;first!=last;first+=size) { \ 2529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *test; \ 2539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Find the right place for |first|. \ 2549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * My apologies for var reuse. */ \ 2559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall for (test=first-size;compare(test,first)>0;test-=size) ; \ 2569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall test+=size; \ 2579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (test!=first) { \ 2589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Shift everything in [test,first) \ 2599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * up by one, and place |first| \ 2609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall * where |test| is. */ \ 2619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall memcpy(pivot,first,size); \ 2629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall memmove(test+size,test,first-test); \ 2639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall memcpy(test,pivot,size); \ 2649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } \ 2659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define SWAP_nonaligned(a,b) { \ 2689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall register char *aa=(a),*bb=(b); \ 2699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall register size_t sz=size; \ 2709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); } 2719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define SWAP_aligned(a,b) { \ 2739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall register int *aa=(int*)(a),*bb=(int*)(b); \ 2749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall register size_t sz=size; \ 2759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); } 2769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define SWAP_words(a,b) { \ 2789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } 2799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* ---------------------------------------------------------------------- */ 2819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 2829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstatic char * pivot_big(char *first, char *mid, char *last, size_t size, 2839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int compare(const void *, const void *)) { 2849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall size_t d=(((last-first)/size)>>3)*size; 2859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *m1,*m2,*m3; 2869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { char *a=first, *b=first+d, *c=first+2*d; 2879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 2889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallfprintf(stderr,"< %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); 2899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 2909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall m1 = compare(a,b)<0 ? 2919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 2929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 2939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 2949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { char *a=mid-d, *b=mid, *c=mid+d; 2959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 2969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallfprintf(stderr,". %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); 2979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 2989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall m2 = compare(a,b)<0 ? 2999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 3009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 3019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { char *a=last-2*d, *b=last-d, *c=last; 3039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 3049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallfprintf(stderr,"> %d %d %d\n",*(int*)a,*(int*)b,*(int*)c); 3059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 3069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall m3 = compare(a,b)<0 ? 3079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 3089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 3099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 3119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallfprintf(stderr,"-> %d %d %d\n",*(int*)m1,*(int*)m2,*(int*)m3); 3129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 3139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return compare(m1,m2)<0 ? 3149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) 3159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); 3169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 3179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* ---------------------------------------------------------------------- */ 3199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstatic void qsort_nonaligned(void *base, size_t nmemb, size_t size, 3219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int (*compare)(const void *, const void *)) { 3229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall stack_entry stack[STACK_SIZE]; 3249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int stacktop=0; 3259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *first,*last; 3269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *pivot=malloc(size); 3279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall size_t trunc=TRUNC_nonaligned*size; 3289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(pivot!=0); 3299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first=(char*)base; last=first+(nmemb-1)*size; 3319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if ((size_t)(last-first)>trunc) { 3339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *ffirst=first, *llast=last; 3349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall while (1) { 3359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Select pivot */ 3369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { char * mid=first+size*((last-first)/size >> 1); 3379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Pivot(SWAP_nonaligned,size); 3389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall memcpy(pivot,mid,size); 3399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Partition. */ 3419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Partition(SWAP_nonaligned,size); 3429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Prepare to recurse/iterate. */ 3439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Recurse(trunc) 3449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); 3479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Insertion(SWAP_nonaligned); 3489682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall free(pivot); 3499682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 3509682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3519682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstatic void qsort_aligned(void *base, size_t nmemb, size_t size, 3529682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int (*compare)(const void *, const void *)) { 3539682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3549682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall stack_entry stack[STACK_SIZE]; 3559682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int stacktop=0; 3569682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *first,*last; 3579682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *pivot=malloc(size); 3589682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall size_t trunc=TRUNC_aligned*size; 3599682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(pivot!=0); 3609682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3619682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first=(char*)base; last=first+(nmemb-1)*size; 3629682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3639682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if ((size_t)(last-first)>trunc) { 3649682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *ffirst=first,*llast=last; 3659682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall while (1) { 3669682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Select pivot */ 3679682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { char * mid=first+size*((last-first)/size >> 1); 3689682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Pivot(SWAP_aligned,size); 3699682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall memcpy(pivot,mid,size); 3709682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3719682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Partition. */ 3729682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Partition(SWAP_aligned,size); 3739682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Prepare to recurse/iterate. */ 3749682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Recurse(trunc) 3759682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3769682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 3779682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall PreInsertion(SWAP_aligned,TRUNC_aligned,size); 3789682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Insertion(SWAP_aligned); 3799682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall free(pivot); 3809682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 3819682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3829682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallstatic void qsort_words(void *base, size_t nmemb, 3839682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int (*compare)(const void *, const void *)) { 3849682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3859682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall stack_entry stack[STACK_SIZE]; 3869682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int stacktop=0; 3879682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *first,*last; 3889682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *pivot=malloc(WORD_BYTES); 3899682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall assert(pivot!=0); 3909682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3919682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall first=(char*)base; last=first+(nmemb-1)*WORD_BYTES; 3929682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 3939682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (last-first>TRUNC_words) { 3949682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall char *ffirst=first, *llast=last; 3959682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall while (1) { 3969682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 3979682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallfprintf(stderr,"Doing %d:%d: ", 3989682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall (first-(char*)base)/WORD_BYTES, 3999682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall (last-(char*)base)/WORD_BYTES); 4009682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 4019682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Select pivot */ 4029682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES)); 4039682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Pivot(SWAP_words,WORD_BYTES); 4049682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall *(int*)pivot=*(int*)mid; 4059682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 4069682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifdef DEBUG_QSORT 4079682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallfprintf(stderr,"pivot=%d\n",*(int*)pivot); 4089682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif 4099682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Partition. */ 4109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Partition(SWAP_words,WORD_BYTES); 4119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Prepare to recurse/iterate. */ 4129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall Recurse(TRUNC_words) 4139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 4149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 4159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); 4169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Now do insertion sort. */ 4179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall last=((char*)base)+nmemb*WORD_BYTES; 4189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { 4199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall /* Find the right place for |first|. My apologies for var reuse */ 4209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first; 4219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall *(int*)pivot=*(int*)first; 4229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall for (;compare(pl,pivot)>0;pr=pl,--pl) { 4239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall *pr=*pl; } 4249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (pr!=(int*)first) *pr=*(int*)pivot; 4259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall } 4269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall free(pivot); 4279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 4289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 4299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall/* ---------------------------------------------------------------------- */ 4309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 4319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallvoid qsort(void *base, size_t nmemb, size_t size, 4329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall int (*compare)(const void *, const void *)) { 4339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 4349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (nmemb<=1) return; 4359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall if (((uintptr_t)base|size)&(WORD_BYTES-1)) 4369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall qsort_nonaligned(base,nmemb,size,compare); 4379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else if (size!=WORD_BYTES) 4389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall qsort_aligned(base,nmemb,size,compare); 4399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall else 4409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall qsort_words(base,nmemb,compare); 4419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 4429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 4439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif /* !HAVE_QSORT */ 444