libc/stdlib/qsort.c

   1 /* +++Date last modified: 05-Jul-1997 */\r
   2 \r
   3 /*\r
   4 **  ssort()  --  Fast, small, qsort()-compatible Shell sort\r
   5 **\r
   6 **  by Ray Gardner,  public domain   5/90\r
   7 */\r
   8 \r
   9 /*\r
  10  * Manuel Novoa III       Dec 2000\r
  11  *\r
  12  * There were several problems with the qsort code contained in uClibc.\r
  13  * It assumed sizeof(int) was 2 and sizeof(long) was 4.  It then had three\r
  14  * seperate quiicksort routines based on the width of the data passed: 2, 4,\r
  15  * or anything else <= 128.  If the width was > 128, it returned -1 (although\r
  16  * qsort should not return a value) and did no sorting.  On i386 with\r
  17  * -Os -fomit-frame-pointer -ffunction-sections, the text segment of qsort.o\r
  18  * was 1358 bytes, with an additional 4 bytes in bss.\r
  19  *\r
  20  * I decided to completely replace the existing code with a small\r
  21  * implementation of a shell sort.  It is a drop-in replacement for the\r
  22  * standard qsort and, with the same gcc flags as above, the text segment\r
  23  * size on i386 is only 183 bytes.\r
  24  *\r
  25  * Grabbed original file rg_ssort.c from snippets.org.\r
  26  * Modified original code to avoid possible overflow in wgap calculation.\r
  27  * Modified wgap calculation in loop and eliminated variables gap and wnel.\r
  28  */\r
  29 \r
  30 \r
  31 #include <stdlib.h>\r
  32 \r
  33 void qsort (void  *base,\r
  34             size_t nel,\r
  35             size_t width,\r
  36             int (*comp)(const void *, const void *))\r
  37 {\r
  38         size_t wgap, i, j, k;\r
  39         char *a, *b, tmp;\r
  40 \r
  41 #if 0\r
  42         /* Note: still conceivable that nel * width could overflow! */\r
  43         assert(width > 0);\r
  44 #endif\r
  45 \r
  46         if (nel > 1) {\r
  47                 for (wgap = 0; ++wgap < (nel-1)/3 ; wgap *= 3) {}\r
  48                 wgap *= width;\r
  49                 nel *= width;                   /* convert nel to 'wnel' */\r
  50                 do {\r
  51                         for (i = wgap; i < nel; i += width) {\r
  52                                 for (j = i - wgap; ;j -= wgap) {\r
  53                                         a = j + ((char *)base);\r
  54                                         b = a + wgap;\r
  55                                         if ( (*comp)(a, b) <= 0 ) {\r
  56                                                 break;\r
  57                                         }\r
  58                                         k = width;\r
  59                                         do {\r
  60                                                 tmp = *a;\r
  61                                                 *a++ = *b;\r
  62                                                 *b++ = tmp;\r
  63                                         } while ( --k );\r
  64                                         if (j < wgap) {\r
  65                                                 break;\r
  66                                         }\r
  67                                 }\r
  68                         }\r
  69                         wgap = (wgap - width)/3;\r
  70                 } while (wgap);\r
  71         }\r
  72 }\r