stdlib/msort.c

   1 /* An alternative to qsort, with an identical interface.
   2    This file is part of the GNU C Library.
   3    Copyright (C) 1992,95-97,99,2000,01,02,04,07 Free Software Foundation, Inc.
   4    Written by Mike Haertel, September 1988.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #include <alloca.h>
  22 #include <stdint.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <unistd.h>
  26 #include <memcopy.h>
  27 #include <errno.h>
  28
  29 struct msort_param
  30 {
  31   size_t s;
  32   size_t var;
  33   __compar_fn_t cmp;
  34   char *t;
  35 };
  36 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
  37
  38 static void
  39 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
  40 {
  41   char *b1, *b2;
  42   size_t n1, n2;
  43
  44   if (n <= 1)
  45     return;
  46
  47   n1 = n / 2;
  48   n2 = n - n1;
  49   b1 = b;
  50   b2 = (char *) b + (n1 * p->s);
  51
  52   msort_with_tmp (p, b1, n1);
  53   msort_with_tmp (p, b2, n2);
  54
  55   char *tmp = p->t;
  56   const size_t s = p->s;
  57   __compar_fn_t cmp = p->cmp;
  58   switch (p->var)
  59     {
  60     case 0:
  61       while (n1 > 0 && n2 > 0)
  62         {
  63           if ((*cmp) (b1, b2) <= 0)
  64             {
  65               *(uint32_t *) tmp = *(uint32_t *) b1;
  66               b1 += sizeof (uint32_t);
  67               --n1;
  68             }
  69           else
  70             {
  71               *(uint32_t *) tmp = *(uint32_t *) b2;
  72               b2 += sizeof (uint32_t);
  73               --n2;
  74             }
  75           tmp += sizeof (uint32_t);
  76         }
  77       break;
  78     case 1:
  79       while (n1 > 0 && n2 > 0)
  80         {
  81           if ((*cmp) (b1, b2) <= 0)
  82             {
  83               *(uint64_t *) tmp = *(uint64_t *) b1;
  84               b1 += sizeof (uint64_t);
  85               --n1;
  86             }
  87           else
  88             {
  89               *(uint64_t *) tmp = *(uint64_t *) b2;
  90               b2 += sizeof (uint64_t);
  91               --n2;
  92             }
  93           tmp += sizeof (uint64_t);
  94         }
  95       break;
  96     case 2:
  97       while (n1 > 0 && n2 > 0)
  98         {
  99           unsigned long *tmpl = (unsigned long *) tmp;
 100           unsigned long *bl;
 101
 102           tmp += s;
 103           if ((*cmp) (b1, b2) <= 0)
 104             {
 105               bl = (unsigned long *) b1;
 106               b1 += s;
 107               --n1;
 108             }
 109           else
 110             {
 111               bl = (unsigned long *) b2;
 112               b2 += s;
 113               --n2;
 114             }
 115           while (tmpl < (unsigned long *) tmp)
 116             *tmpl++ = *bl++;
 117         }
 118       break;
 119     case 3:
 120       while (n1 > 0 && n2 > 0)
 121         {
 122           if ((*cmp) (*(const void **) b1, *(const void **) b2) <= 0)
 123             {
 124               *(void **) tmp = *(void **) b1;
 125               b1 += sizeof (void *);
 126               --n1;
 127             }
 128           else
 129             {
 130               *(void **) tmp = *(void **) b2;
 131               b2 += sizeof (void *);
 132               --n2;
 133             }
 134           tmp += sizeof (void *);
 135         }
 136       break;
 137     default:
 138       while (n1 > 0 && n2 > 0)
 139         {
 140           if ((*cmp) (b1, b2) <= 0)
 141             {
 142               tmp = (char *) __mempcpy (tmp, b1, s);
 143               b1 += s;
 144               --n1;
 145             }
 146           else
 147             {
 148               tmp = (char *) __mempcpy (tmp, b2, s);
 149               b2 += s;
 150               --n2;
 151             }
 152         }
 153       break;
 154     }
 155
 156   if (n1 > 0)
 157     memcpy (tmp, b1, n1 * s);
 158   memcpy (b, p->t, (n - n2) * s);
 159 }
 160
 161 void
 162 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
 163 {
 164   size_t size = n * s;
 165   char *tmp = NULL;
 166   struct msort_param p;
 167
 168   /* For large object sizes use indirect sorting.  */
 169   if (s > 32)
 170     size = 2 * n * sizeof (void *) + s;
 171
 172   if (size < 1024)
 173     /* The temporary array is small, so put it on the stack.  */
 174     p.t = __alloca (size);
 175   else
 176     {
 177       /* We should avoid allocating too much memory since this might
 178          have to be backed up by swap space.  */
 179       static long int phys_pages;
 180       static int pagesize;
 181
 182       if (phys_pages == 0)
 183         {
 184           phys_pages = __sysconf (_SC_PHYS_PAGES);
 185
 186           if (phys_pages == -1)
 187             /* Error while determining the memory size.  So let's
 188                assume there is enough memory.  Otherwise the
 189                implementer should provide a complete implementation of
 190                the `sysconf' function.  */
 191             phys_pages = (long int) (~0ul >> 1);
 192
 193           /* The following determines that we will never use more than
 194              a quarter of the physical memory.  */
 195           phys_pages /= 4;
 196
 197           pagesize = __sysconf (_SC_PAGESIZE);
 198         }
 199
 200       /* Just a comment here.  We cannot compute
 201            phys_pages * pagesize
 202            and compare the needed amount of memory against this value.
 203            The problem is that some systems might have more physical
 204            memory then can be represented with a `size_t' value (when
 205            measured in bytes.  */
 206
 207       /* If the memory requirements are too high don't allocate memory.  */
 208       if (size / pagesize > (size_t) phys_pages)
 209         {
 210           _quicksort (b, n, s, cmp);
 211           return;
 212         }
 213
 214       /* It's somewhat large, so malloc it.  */
 215       int save = errno;
 216       tmp = malloc (size);
 217       __set_errno (save);
 218       if (tmp == NULL)
 219         {
 220           /* Couldn't get space, so use the slower algorithm
 221              that doesn't need a temporary array.  */
 222           _quicksort (b, n, s, cmp);
 223           return;
 224         }
 225       p.t = tmp;
 226     }
 227
 228   p.s = s;
 229   p.cmp = cmp;
 230   p.var = 4;
 231
 232   if (s > 32)
 233     {
 234       /* Indirect sorting.  */
 235       char *ip = (char *) b;
 236       void **tp = (void **) (p.t + n * sizeof (void *));
 237       void **t = tp;
 238       void *tmp_storage = (void *) (tp + n);
 239
 240       while ((void *) t < tmp_storage)
 241         {
 242           *t++ = ip;
 243           ip += s;
 244         }
 245       p.s = sizeof (void *);
 246       p.var = 3;
 247       msort_with_tmp (&p, p.t + n * sizeof (void *), n);
 248
 249       /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
 250          the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
 251       char *kp;
 252       size_t i;
 253       for (i = 0, ip = (char *) b; i < n; i++, ip += s)
 254         if ((kp = tp[i]) != ip)
 255           {
 256             size_t j = i;
 257             char *jp = ip;
 258             memcpy (tmp_storage, ip, s);
 259
 260             do
 261               {
 262                 size_t k = (kp - (char *) b) / s;
 263                 tp[j] = jp;
 264                 memcpy (jp, kp, s);
 265                 j = k;
 266                 jp = kp;
 267                 kp = tp[k];
 268               }
 269             while (kp != ip);
 270
 271             tp[j] = jp;
 272             memcpy (jp, tmp_storage, s);
 273           }
 274     }
 275   else
 276     {
 277       if ((s & (sizeof (uint32_t) - 1)) == 0
 278           && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
 279         {
 280           if (s == sizeof (uint32_t))
 281             p.var = 0;
 282           else if (s == sizeof (uint64_t)
 283                    && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
 284             p.var = 1;
 285           else if ((s & (sizeof (unsigned long) - 1)) == 0
 286                    && ((char *) b - (char *) 0)
 287                       % __alignof__ (unsigned long) == 0)
 288             p.var = 2;
 289         }
 290       msort_with_tmp (&p, b, n);
 291     }
 292   free (tmp);
 293 }
 294 libc_hidden_def (qsort)