common/stdc/qsort.c

   1 /*
   2  * Copyright (c) 2017 Jiri Svoboda
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup libc
  30  * @{
  31  */
  32
  33 /**
  34  * @file
  35  * @brief Quicksort.
  36  */
  37
  38 #include <qsort.h>
  39 #include <stdbool.h>
  40 #include <stddef.h>
  41
  42 /** Quicksort spec */
  43 typedef struct {
  44         void *base;
  45         size_t nmemb;
  46         size_t size;
  47         int (*compar)(const void *, const void *, void *);
  48         void *arg;
  49 } qs_spec_t;
  50
  51 /** Comparison function wrapper.
  52  *
  53  * Performs qsort_r comparison using qsort comparison function
  54  *
  55  * @param a First element
  56  * @param b Second element
  57  * @param arg qsort comparison function
  58  */
  59 static int compar_wrap(const void *a, const void *b, void *arg)
  60 {
  61         int (*compar)(const void *, const void *) =
  62             (int (*)(const void *, const void *))arg;
  63
  64         return compar(a, b);
  65 }
  66
  67 /** Determine if one element is less-than another element.
  68  *
  69  * @param qs Quicksort spec
  70  * @param i First element index
  71  * @param j Second element index
  72  */
  73 static bool elem_lt(qs_spec_t *qs, size_t i, size_t j)
  74 {
  75         const void *a;
  76         const void *b;
  77         int r;
  78
  79         a = qs->base + i * qs->size;
  80         b = qs->base + j * qs->size;
  81
  82         r = qs->compar(a, b, qs->arg);
  83
  84         return r < 0;
  85 }
  86
  87 /** Swap two elements.
  88  *
  89  * @param qs Quicksort spec
  90  * @param i First element index
  91  * @param j Second element index
  92  */
  93 static void elem_swap(qs_spec_t *qs, size_t i, size_t j)
  94 {
  95         char *a;
  96         char *b;
  97         char t;
  98         size_t k;
  99
 100         a = qs->base + i * qs->size;
 101         b = qs->base + j * qs->size;
 102
 103         for (k = 0; k < qs->size; k++) {
 104                 t = a[k];
 105                 a[k] = b[k];
 106                 b[k] = t;
 107         }
 108 }
 109
 110 /** Partition a range of indices.
 111  *
 112  * @param qs Quicksort spec
 113  * @param lo Lower bound (inclusive)
 114  * @param hi Upper bound (inclusive)
 115  * @return Pivot index
 116  */
 117 static size_t partition(qs_spec_t *qs, size_t lo, size_t hi)
 118 {
 119         size_t pivot;
 120         size_t i, j;
 121
 122         pivot = lo + (hi - lo) / 2;
 123         i = lo;
 124         j = hi;
 125         while (true) {
 126                 while (elem_lt(qs, i, pivot))
 127                         ++i;
 128                 while (elem_lt(qs, pivot, j))
 129                         --j;
 130
 131                 if (i >= j)
 132                         return j;
 133
 134                 elem_swap(qs, i, j);
 135
 136                 /* Need to follow pivot movement */
 137                 if (i == pivot)
 138                         pivot = j;
 139                 else if (j == pivot)
 140                         pivot = i;
 141
 142                 i++;
 143                 j--;
 144         }
 145 }
 146
 147 /** Sort a range of indices.
 148  *
 149  * @param qs Quicksort spec
 150  * @param lo Lower bound (inclusive)
 151  * @param hi Upper bound (inclusive)
 152  */
 153 static void quicksort(qs_spec_t *qs, size_t lo, size_t hi)
 154 {
 155         size_t p;
 156
 157         if (lo < hi) {
 158                 p = partition(qs, lo, hi);
 159                 quicksort(qs, lo, p);
 160                 quicksort(qs, p + 1, hi);
 161         }
 162 }
 163
 164 /** Quicksort.
 165  *
 166  * @param base Array to sort
 167  * @param nmemb Number of array members
 168  * @param size Size of member in bytes
 169  * @param compar Comparison function
 170  */
 171 void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *,
 172     const void *))
 173 {
 174         qs_spec_t qs;
 175
 176         if (nmemb == 0)
 177                 return;
 178
 179         qs.base = base;
 180         qs.nmemb = nmemb;
 181         qs.size = size;
 182         qs.compar = compar_wrap;
 183         qs.arg = compar;
 184
 185         quicksort(&qs, 0, nmemb - 1);
 186 }
 187
 188 /** Quicksort with extra argument to comparison function.
 189  *
 190  * @param base Array to sort
 191  * @param nmemb Number of array members
 192  * @param size Size of member in bytes
 193  * @param compar Comparison function
 194  * @param arg Argument to comparison function
 195  */
 196 void qsort_r(void *base, size_t nmemb, size_t size, int (*compar)(const void *,
 197     const void *, void *), void *arg)
 198 {
 199         qs_spec_t qs;
 200
 201         if (nmemb == 0)
 202                 return;
 203
 204         qs.base = base;
 205         qs.nmemb = nmemb;
 206         qs.size = size;
 207         qs.compar = compar;
 208         qs.arg = arg;
 209
 210         quicksort(&qs, 0, nmemb - 1);
 211 }
 212
 213 /** @}
 214  */