lib/util/stable_sort.c

   1 /*
   2    Stable sort routines
   3
   4    Copyright © Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
   5
   6      ** NOTE! The following LGPL license applies to this file which is used by
   7      ** the ldb library. This does NOT imply that all of Samba is released
   8      ** under the LGPL.
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 3 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include <talloc.h>
  29 #include "replace.h"
  30 #include "stable_sort.h"
  31
  32 static void sort_few(char *array, char *aux,
  33                      size_t n,
  34                      size_t s,
  35                      samba_compare_with_context_fn_t cmpfn,
  36                      void *opaque)
  37 {
  38         /* a kind of insertion sort for small n. */
  39         int i, j, dist;
  40         int cmp;
  41         char *a, *b;
  42
  43         for (i = 1; i < n; i++) {
  44                 a = &array[i * s];
  45                 /* leftwards is sorted. look until we find this one's place */
  46                 for (j = i - 1; j >= 0; j--) {
  47                         b = &array[j * s];
  48                         cmp = cmpfn(a, b, opaque);
  49                         if (cmp >= 0) {
  50                                 break;
  51                         }
  52                 }
  53                 dist = i - 1 - j;
  54                 if (dist == 0) {
  55                         /* a is already in the right place */
  56                         continue;
  57                 }
  58
  59                 b = &array[(i - dist) * s];
  60                 memcpy(aux, a, s);
  61                 memmove(b + s, b, s * dist);
  62                 memcpy(b, aux, s);
  63         }
  64 }
  65
  66
  67 static void merge(char *dest,
  68                   char *a, size_t alen,
  69                   char *b, size_t blen,
  70                   size_t s,
  71                   samba_compare_with_context_fn_t cmpfn,
  72                   void *opaque)
  73 {
  74         size_t ai = 0;
  75         size_t bi = 0;
  76         size_t di = 0;
  77         while (ai < alen && bi < blen) {
  78                 int cmp = cmpfn(&a[ai * s], &b[bi * s], opaque);
  79                 if (cmp <= 0) {
  80                         memcpy(&dest[di * s], &a[ai * s], s);
  81                         ai++;
  82                 } else {
  83                         memcpy(&dest[di * s], &b[bi * s], s);
  84                         bi++;
  85                 }
  86                 di++;
  87         }
  88         if (ai < alen) {
  89                 memcpy(&dest[di * s], &a[ai * s], s * (alen - ai));
  90         } else if (bi < blen) {
  91                 memcpy(&dest[di * s], &b[bi * s], s * (blen - bi));
  92         }
  93 }
  94
  95
  96 bool stable_sort_r(void *array, void *aux,
  97                    size_t n,
  98                    size_t s,
  99                    samba_compare_with_context_fn_t cmpfn,
 100                    void * opaque)
 101 {
 102         char *src = array, *dest = aux, *tmp = NULL;
 103         size_t i, j, k;
 104         size_t runsize;
 105         if (array == NULL || aux == NULL) {
 106                 return false;
 107         }
 108
 109         if (n < 20) {
 110                 sort_few(array, aux, n, s, cmpfn, opaque);
 111                 return true;
 112         }
 113
 114         if (n > SIZE_MAX / s) {
 115                 /*
 116                  * We will have an integer overflow if we continue.
 117                  *
 118                  * This means that the *supposed* size of the allocated buffer
 119                  * is greater than SIZE_MAX, which is not possible in theory
 120                  * or practice, and is a sign the caller has got very
 121                  * confused.
 122                  */
 123                 return false;
 124         }
 125
 126         /*
 127          * This is kind of a bottom-up merge sort.
 128          *
 129          * We start but sorting into a whole lot of little runs, using an
 130          * insertion sort which is efficient for small numbers. Empirically,
 131          * on 2 machines, a run size of around 8 seems optimal, but the peak
 132          * is wide, and it seems worth adapting the size to avoid an
 133          * unbalanced final merge at the top. That is, if we pick the right
 134          * runsize now, we will finish with a merge of roughly n/2:n/2, and
 135          * not have to follow that with an merge of roughly n:[a few], which
 136          * we would sometimes do with a fixed size at the lowest level.
 137          *
 138          * The aim is a runsize of n / (a power of 2) rounded up, in the
 139          * target range.
 140          */
 141
 142         runsize = n;
 143         while (runsize > 10) {
 144                 runsize++;
 145                 runsize >>= 1;
 146         }
 147
 148         for (i = 0; i < n; i += runsize) {
 149                 size_t nn = MIN(n - i, runsize);
 150                 sort_few(&src[i * s], aux, nn, s, cmpfn, opaque);
 151         }
 152
 153         while (runsize < n) {
 154                 for (i = 0; i < n; i += runsize * 2) {
 155                         j = i + runsize;
 156                         if (j >= n) {
 157                                 /*
 158                                  * first run doesn't fit, meaning this chunk
 159                                  * is already sorted. We just need to copy
 160                                  * it.
 161                                  */
 162                                 size_t nn = n - i;
 163                                 memcpy(&dest[i * s], &src[i * s], nn * s);
 164                                 break;
 165                         }
 166                         k = j + runsize;
 167                         if (k > n) {
 168                                 merge(&dest[i * s],
 169                                       &src[i * s], runsize,
 170                                       &src[j * s], n - j,
 171                                       s,
 172                                       cmpfn, opaque);
 173                         } else {
 174                                 merge(&dest[i * s],
 175                                       &src[i * s], runsize,
 176                                       &src[j * s], runsize,
 177                                       s,
 178                                       cmpfn, opaque);
 179                         }
 180                 }
 181
 182                 tmp = src;
 183                 src = dest;
 184                 dest = tmp;
 185                 runsize *= 2;
 186         }
 187         /*
 188          * We have sorted the array into src, which is either array or aux.
 189          */
 190         if (src != array) {
 191                 memcpy(array, src, n * s);
 192         }
 193         return true;
 194 }
 195
 196
 197
 198 /*
 199  * A wrapper that allocates (and frees) the temporary buffer if necessary.
 200  *
 201  * returns false on allocation error, true otherwise.
 202  */
 203
 204 bool stable_sort_talloc_r(TALLOC_CTX *mem_ctx,
 205                           void *array,
 206                           size_t n,
 207                           size_t s,
 208                           samba_compare_with_context_fn_t cmpfn,
 209                           void *opaque)
 210 {
 211         bool ok;
 212         char *mem = talloc_array_size(mem_ctx, s, n);
 213         if (mem == NULL) {
 214                 return false;
 215         }
 216         ok = stable_sort_r(array, mem, n, s, cmpfn, opaque);
 217         talloc_free(mem);
 218         return ok;
 219 }
 220
 221
 222 bool stable_sort(void *array, void *aux,
 223                  size_t n,
 224                  size_t s,
 225                  samba_compare_fn_t cmpfn)
 226 {
 227         /*
 228          * What is this magic, casting cmpfn into a different type that takes
 229          * an extra parameter? Is that allowed?
 230          *
 231          * A: Yes. It's fine. The extra argument will be passed on the stack
 232          * or (more likely) a register, and the cmpfn will remain blissfully
 233          * unaware.
 234          */
 235         return stable_sort_r(array, aux, n, s,
 236                              (samba_compare_with_context_fn_t)cmpfn,
 237                              NULL);
 238 }
 239
 240
 241 bool stable_sort_talloc(TALLOC_CTX *mem_ctx,
 242                         void *array,
 243                         size_t n,
 244                         size_t s,
 245                         samba_compare_fn_t cmpfn)
 246 {
 247         return stable_sort_talloc_r(mem_ctx, array, n, s,
 248                                     (samba_compare_with_context_fn_t)cmpfn,
 249                                     NULL);
 250 }