ulinux/utils/qsort.c

   1 #ifndef ULINUX_UTILS_QSORT_C
   2 #define ULINUX_UTILS_QSORT_C
   3 /*
   4  * this code is protected by the GNU affero GPLv3
   5  * author:Sylvain BERTRAND
   6  */
   7 #include <stdbool.h>
   8
   9 #include <ulinux/compiler_types.h>
  10 #include <ulinux/types.h>
  11
  12 #include <ulinux/utils/qsort.h>
  13 /*----------------------------------------------------------------------------*/
  14 /* "One Compilation Unit" support */
  15 #ifdef ULINUX_UTILS_EXTERNAL
  16 #define ULINUX_EXPORT
  17 #else
  18 #define ULINUX_EXPORT static
  19 #endif
  20 /*----------------------------------------------------------------------------*/
  21 #define loop for(;;)
  22 #define swap ulinux_qsort_swap
  23 /*----------------------------------------------------------------------------*/
  24 static void swap(void *a, void *b,  ulinux_u64 sz)
  25 {
  26         ulinux_u8 *a_byte;
  27         ulinux_u8 *b_byte;
  28
  29         a_byte = a;
  30         b_byte = b;
  31         loop {
  32                 ulinux_u8 tmp;
  33
  34                 if (sz == 0)
  35                         break;
  36
  37                 tmp = *a_byte;
  38                 *a_byte = *b_byte;
  39                 *b_byte = tmp;
  40
  41                 ++a_byte;
  42                 ++b_byte;
  43                 sz--;
  44         }
  45 }
  46
  47 #define LT ULINUX_QSORT_CMP_LT
  48 #define LT_PIVOT ULINUX_QSORT_CMP_LT
  49 #define EQ_PIVOT ULINUX_QSORT_CMP_EQ
  50 #define GT_PIVOT ULINUX_QSORT_CMP_GT
  51 ULINUX_EXPORT void ulinux_qsort(void *base, ulinux_u64 n, ulinux_u64 sz,
  52                                         ulinux_s8 (*cmp)(void *a, void *b))
  53 {
  54         ulinux_u8 *left;
  55         ulinux_u8 *right;
  56         ulinux_u8 *pivot;
  57         ulinux_u8 *last;
  58
  59         /* fast paths for the low values of n, 0 1 and 2 */
  60         if (n < 2)
  61                 return;
  62         else if (n == 2) {
  63                 if (cmp(base + sz, base) == LT)
  64                         swap(base, base + sz, sz);
  65                 return;
  66         }
  67
  68         /* from here n >= 3 */
  69
  70         last = base + (n - 1) * sz;
  71         left = base;
  72         right = last;
  73
  74         /*
  75          * setup a pivot which is the best-of-three median with the value from
  76          * the middle. Do pre-partition the values from those 3 array slots.
  77          * This setup natural bounds.
  78          */
  79         pivot = base + ((n - 1) / 2) * sz;
  80
  81         if (cmp(pivot, left) == LT_PIVOT)
  82                 swap(left, pivot, sz);
  83         if (cmp(right, pivot) == LT_PIVOT) {
  84                 swap(pivot, right, sz);
  85                 if (cmp(pivot, left) == LT_PIVOT)
  86                         swap(left, pivot, sz);
  87         }
  88
  89         /* the best-of-three median is a fast path for n = 3 */
  90         if (n == 3)
  91                 return;
  92
  93         /* from here n >= 4 */
  94
  95         /*-------------------------------------------------------------------*/
  96         /*
  97          * do partition:
  98          *  - left side LT/EQ the pivot value.
  99          *  - right side EQ/GT the pivot value.
 100          * both sides can contain slots with the pivot value.
 101          */
 102         left += sz; /* skip the pre-partitioned array left-most value */
 103         right -= sz; /* skip the pre-partitioned array righ-most value */
 104         loop {
 105                 ulinux_s8 left_cmp;
 106                 ulinux_s8 right_cmp;
 107
 108                 /*
 109                  * this loop cannot go forever, the pre-partitioned right most
 110                  * slot contains a value higher or equal to the pivot
 111                  * value, and will not change.
 112                  */
 113                 loop {
 114                         left_cmp = cmp(left, pivot);
 115                         if (left_cmp != LT_PIVOT)
 116                                 break;
 117                         left += sz;
 118                 }
 119
 120                 /* same thing than above but backward */
 121                 loop {
 122                         right_cmp = cmp(pivot, right);
 123                         if (right_cmp != LT_PIVOT)
 124                                 break;
 125                         right -= sz;
 126                 }
 127
 128                 /*
 129                  * left points on a slot which contains:
 130                  *  - the pivot value.
 131                  *  - a value higher than the pivot value.
 132                  * all slots below left contains values
 133                  * lesser than or equal to the pivot value.
 134                  *
 135                  * right points on a slot which contains:
 136                  *  - the pivot value.
 137                  *  - a value lower than the pivot value.
 138                  * all slots above right contains values
 139                  * higher than or equal to the pivot value.
 140                  */
 141
 142                 if (right <= left)
 143                         break;
 144
 145                 /* left < right */
 146
 147                 if ((left_cmp != EQ_PIVOT) || (right_cmp != EQ_PIVOT)) {
 148                         swap(left, right, sz);
 149
 150                         /*
 151                          * we must keep track of the pivot value if it is
 152                          * swapped
 153                          */
 154                         if (left == pivot)
 155                                 pivot = right;
 156                         else if (right == pivot)
 157                                 pivot = left;
 158                 }
 159
 160                 left += sz;
 161                 right -= sz;
 162         }
 163
 164         /*
 165          * if right < left rewind one slot for each which will be our
 166          * boundaries of the partitions. if left == right, then rewind only
 167          * left.
 168          */
 169         left -= sz;
 170         if (right < left)
 171                 right += sz;
 172         /*-------------------------------------------------------------------*/
 173
 174         ulinux_qsort(base, (left - (ulinux_u8*)base) / sz + 1, sz, cmp);
 175         ulinux_qsort(right, (last - right) / sz + 1, sz, cmp);
 176 }
 177 #undef LT
 178 #undef LT_PIVOT
 179 #undef EQ_PIVOT
 180 #undef GT_PIVOT
 181 /*----------------------------------------------------------------------------*/
 182 #undef loop
 183 #undef swap
 184 #endif