git.sur5r.net Git - cc65/blob - libsrc/common/qsort.c

   1 /*
   2 ** qsort.c
   3 **
   4 ** 1998.12.09, Ullrich von Bassewitz
   5 ** 2015-06-21, Greg King
   6 */
   7
   8
   9
  10 #include <stdlib.h>
  11
  12
  13
  14 static void QuickSort (register unsigned char* Base, int Lo, int Hi,
  15                        register size_t Size,
  16                        int __fastcall__ (* Compare) (const void*, const void*))
  17 /* Internal recursive function. Works with ints, but this shouldn't be
  18 ** a problem.
  19 */
  20 {
  21     int I, J;
  22
  23     /* Quicksort */
  24     while (Hi > Lo) {
  25         I = Lo + Size;
  26         J = Hi;
  27         while (I <= J) {
  28             while (I <= J && Compare (Base + Lo, Base + I) >= 0) {
  29                 I += Size;
  30             }
  31             while (I <= J && Compare (Base + Lo, Base + J) < 0) {
  32                 J -= Size;
  33             }
  34             if (I <= J) {
  35                 _swap (Base + I, Base + J, Size);
  36                 I += Size;
  37                 J -= Size;
  38             }
  39         }
  40         if (J != Lo) {
  41             _swap (Base + J, Base + Lo, Size);
  42         }
  43         if (((unsigned) J) * 2 > (Hi + Lo)) {
  44             QuickSort (Base, J + Size, Hi, Size, Compare);
  45             Hi = J - Size;
  46         } else {
  47             QuickSort (Base, Lo, J - Size, Size, Compare);
  48             Lo = J + Size;
  49         }
  50     }
  51 }
  52
  53
  54
  55 void __fastcall__ qsort (void* base, size_t nmemb, size_t size,
  56                          int __fastcall__ (* compare) (const void*, const void*))
  57 /* Quicksort implementation */
  58 {
  59     if (nmemb > 1) {
  60         QuickSort (base, 0, (nmemb-1) * size, size, compare);
  61     }
  62 }
  63
  64
  65