Back to index

glibc  2.9
msort.c
Go to the documentation of this file.
00001 /* An alternative to qsort, with an identical interface.
00002    This file is part of the GNU C Library.
00003    Copyright (C) 1992,95-97,99,2000,01,02,04,07 Free Software Foundation, Inc.
00004    Written by Mike Haertel, September 1988.
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public
00008    License as published by the Free Software Foundation; either
00009    version 2.1 of the License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; if not, write to the Free
00018    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019    02111-1307 USA.  */
00020 
00021 #include <alloca.h>
00022 #include <stdint.h>
00023 #include <stdlib.h>
00024 #include <string.h>
00025 #include <unistd.h>
00026 #include <memcopy.h>
00027 #include <errno.h>
00028 
00029 struct msort_param
00030 {
00031   size_t s;
00032   size_t var;
00033   __compar_d_fn_t cmp;
00034   void *arg;
00035   char *t;
00036 };
00037 static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
00038 
00039 static void
00040 msort_with_tmp (const struct msort_param *p, void *b, size_t n)
00041 {
00042   char *b1, *b2;
00043   size_t n1, n2;
00044 
00045   if (n <= 1)
00046     return;
00047 
00048   n1 = n / 2;
00049   n2 = n - n1;
00050   b1 = b;
00051   b2 = (char *) b + (n1 * p->s);
00052 
00053   msort_with_tmp (p, b1, n1);
00054   msort_with_tmp (p, b2, n2);
00055 
00056   char *tmp = p->t;
00057   const size_t s = p->s;
00058   __compar_d_fn_t cmp = p->cmp;
00059   void *arg = p->arg;
00060   switch (p->var)
00061     {
00062     case 0:
00063       while (n1 > 0 && n2 > 0)
00064        {
00065          if ((*cmp) (b1, b2, arg) <= 0)
00066            {
00067              *(uint32_t *) tmp = *(uint32_t *) b1;
00068              b1 += sizeof (uint32_t);
00069              --n1;
00070            }
00071          else
00072            {
00073              *(uint32_t *) tmp = *(uint32_t *) b2;
00074              b2 += sizeof (uint32_t);
00075              --n2;
00076            }
00077          tmp += sizeof (uint32_t);
00078        }
00079       break;
00080     case 1:
00081       while (n1 > 0 && n2 > 0)
00082        {
00083          if ((*cmp) (b1, b2, arg) <= 0)
00084            {
00085              *(uint64_t *) tmp = *(uint64_t *) b1;
00086              b1 += sizeof (uint64_t);
00087              --n1;
00088            }
00089          else
00090            {
00091              *(uint64_t *) tmp = *(uint64_t *) b2;
00092              b2 += sizeof (uint64_t);
00093              --n2;
00094            }
00095          tmp += sizeof (uint64_t);
00096        }
00097       break;
00098     case 2:
00099       while (n1 > 0 && n2 > 0)
00100        {
00101          unsigned long *tmpl = (unsigned long *) tmp;
00102          unsigned long *bl;
00103 
00104          tmp += s;
00105          if ((*cmp) (b1, b2, arg) <= 0)
00106            {
00107              bl = (unsigned long *) b1;
00108              b1 += s;
00109              --n1;
00110            }
00111          else
00112            {
00113              bl = (unsigned long *) b2;
00114              b2 += s;
00115              --n2;
00116            }
00117          while (tmpl < (unsigned long *) tmp)
00118            *tmpl++ = *bl++;
00119        }
00120       break;
00121     case 3:
00122       while (n1 > 0 && n2 > 0)
00123        {
00124          if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
00125            {
00126              *(void **) tmp = *(void **) b1;
00127              b1 += sizeof (void *);
00128              --n1;
00129            }
00130          else
00131            {
00132              *(void **) tmp = *(void **) b2;
00133              b2 += sizeof (void *);
00134              --n2;
00135            }
00136          tmp += sizeof (void *);
00137        }
00138       break;
00139     default:
00140       while (n1 > 0 && n2 > 0)
00141        {
00142          if ((*cmp) (b1, b2, arg) <= 0)
00143            {
00144              tmp = (char *) __mempcpy (tmp, b1, s);
00145              b1 += s;
00146              --n1;
00147            }
00148          else
00149            {
00150              tmp = (char *) __mempcpy (tmp, b2, s);
00151              b2 += s;
00152              --n2;
00153            }
00154        }
00155       break;
00156     }
00157 
00158   if (n1 > 0)
00159     memcpy (tmp, b1, n1 * s);
00160   memcpy (b, p->t, (n - n2) * s);
00161 }
00162 
00163 
00164 void
00165 qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
00166 {
00167   size_t size = n * s;
00168   char *tmp = NULL;
00169   struct msort_param p;
00170 
00171   /* For large object sizes use indirect sorting.  */
00172   if (s > 32)
00173     size = 2 * n * sizeof (void *) + s;
00174 
00175   if (size < 1024)
00176     /* The temporary array is small, so put it on the stack.  */
00177     p.t = __alloca (size);
00178   else
00179     {
00180       /* We should avoid allocating too much memory since this might
00181         have to be backed up by swap space.  */
00182       static long int phys_pages;
00183       static int pagesize;
00184 
00185       if (phys_pages == 0)
00186        {
00187          phys_pages = __sysconf (_SC_PHYS_PAGES);
00188 
00189          if (phys_pages == -1)
00190            /* Error while determining the memory size.  So let's
00191               assume there is enough memory.  Otherwise the
00192               implementer should provide a complete implementation of
00193               the `sysconf' function.  */
00194            phys_pages = (long int) (~0ul >> 1);
00195 
00196          /* The following determines that we will never use more than
00197             a quarter of the physical memory.  */
00198          phys_pages /= 4;
00199 
00200          pagesize = __sysconf (_SC_PAGESIZE);
00201        }
00202 
00203       /* Just a comment here.  We cannot compute
00204           phys_pages * pagesize
00205           and compare the needed amount of memory against this value.
00206           The problem is that some systems might have more physical
00207           memory then can be represented with a `size_t' value (when
00208           measured in bytes.  */
00209 
00210       /* If the memory requirements are too high don't allocate memory.  */
00211       if (size / pagesize > (size_t) phys_pages)
00212        {
00213          _quicksort (b, n, s, cmp, arg);
00214          return;
00215        }
00216 
00217       /* It's somewhat large, so malloc it.  */
00218       int save = errno;
00219       tmp = malloc (size);
00220       __set_errno (save);
00221       if (tmp == NULL)
00222        {
00223          /* Couldn't get space, so use the slower algorithm
00224             that doesn't need a temporary array.  */
00225          _quicksort (b, n, s, cmp, arg);
00226          return;
00227        }
00228       p.t = tmp;
00229     }
00230 
00231   p.s = s;
00232   p.var = 4;
00233   p.cmp = cmp;
00234   p.arg = arg;
00235 
00236   if (s > 32)
00237     {
00238       /* Indirect sorting.  */
00239       char *ip = (char *) b;
00240       void **tp = (void **) (p.t + n * sizeof (void *));
00241       void **t = tp;
00242       void *tmp_storage = (void *) (tp + n);
00243 
00244       while ((void *) t < tmp_storage)
00245        {
00246          *t++ = ip;
00247          ip += s;
00248        }
00249       p.s = sizeof (void *);
00250       p.var = 3;
00251       msort_with_tmp (&p, p.t + n * sizeof (void *), n);
00252 
00253       /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
00254         the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
00255       char *kp;
00256       size_t i;
00257       for (i = 0, ip = (char *) b; i < n; i++, ip += s)
00258        if ((kp = tp[i]) != ip)
00259          {
00260            size_t j = i;
00261            char *jp = ip;
00262            memcpy (tmp_storage, ip, s);
00263 
00264            do
00265              {
00266               size_t k = (kp - (char *) b) / s;
00267               tp[j] = jp;
00268               memcpy (jp, kp, s);
00269               j = k;
00270               jp = kp;
00271               kp = tp[k];
00272              }
00273            while (kp != ip);
00274 
00275            tp[j] = jp;
00276            memcpy (jp, tmp_storage, s);
00277          }
00278     }
00279   else
00280     {
00281       if ((s & (sizeof (uint32_t) - 1)) == 0
00282          && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
00283        {
00284          if (s == sizeof (uint32_t))
00285            p.var = 0;
00286          else if (s == sizeof (uint64_t)
00287                  && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
00288            p.var = 1;
00289          else if ((s & (sizeof (unsigned long) - 1)) == 0
00290                  && ((char *) b - (char *) 0)
00291                     % __alignof__ (unsigned long) == 0)
00292            p.var = 2;
00293        }
00294       msort_with_tmp (&p, b, n);
00295     }
00296   free (tmp);
00297 }
00298 libc_hidden_def (qsort_r)
00299 
00300 
00301 void
00302 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
00303 {
00304   return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
00305 }
00306 libc_hidden_def (qsort)