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 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 <stdlib.h>
  23 #include <string.h>
  24 #include <unistd.h>
  25 #include <memcopy.h>
  26 #include <errno.h>
  27
  28 static void msort_with_tmp (void *b, size_t n, size_t s,
  29                             __compar_fn_t cmp, char *t);
  30
  31 static void
  32 msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp,
  33                 char *t)
  34 {
  35   char *tmp;
  36   char *b1, *b2;
  37   size_t n1, n2;
  38
  39   if (n <= 1)
  40     return;
  41
  42   n1 = n / 2;
  43   n2 = n - n1;
  44   b1 = b;
  45   b2 = (char *) b + (n1 * s);
  46
  47   msort_with_tmp (b1, n1, s, cmp, t);
  48   msort_with_tmp (b2, n2, s, cmp, t);
  49
  50   tmp = t;
  51
  52   if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
  53     /* We are operating on aligned words.  Use direct word stores.  */
  54     while (n1 > 0 && n2 > 0)
  55       {
  56         if ((*cmp) (b1, b2) <= 0)
  57           {
  58             --n1;
  59             *((op_t *) tmp) = *((op_t *) b1);
  60             tmp += sizeof (op_t);
  61             b1 += sizeof (op_t);
  62           }
  63         else
  64           {
  65             --n2;
  66             *((op_t *) tmp) = *((op_t *) b2);
  67             tmp += sizeof (op_t);
  68             b2 += sizeof (op_t);
  69           }
  70       }
  71   else
  72     while (n1 > 0 && n2 > 0)
  73       {
  74         if ((*cmp) (b1, b2) <= 0)
  75           {
  76             tmp = (char *) __mempcpy (tmp, b1, s);
  77             b1 += s;
  78             --n1;
  79           }
  80         else
  81           {
  82             tmp = (char *) __mempcpy (tmp, b2, s);
  83             b2 += s;
  84             --n2;
  85           }
  86       }
  87   if (n1 > 0)
  88     memcpy (tmp, b1, n1 * s);
  89   memcpy (b, t, (n - n2) * s);
  90 }
  91
  92 void
  93 qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
  94 {
  95   const size_t size = n * s;
  96
  97   if (size < 1024)
  98     {
  99       void *buf = __alloca (size);
 100
 101       /* The temporary array is small, so put it on the stack.  */
 102       msort_with_tmp (b, n, s, cmp, buf);
 103     }
 104   else
 105     {
 106       /* We should avoid allocating too much memory since this might
 107          have to be backed up by swap space.  */
 108       static long int phys_pages;
 109       static int pagesize;
 110
 111       if (phys_pages == 0)
 112         {
 113           phys_pages = __sysconf (_SC_PHYS_PAGES);
 114
 115           if (phys_pages == -1)
 116             /* Error while determining the memory size.  So let's
 117                assume there is enough memory.  Otherwise the
 118                implementer should provide a complete implementation of
 119                the `sysconf' function.  */
 120             phys_pages = (long int) (~0ul >> 1);
 121
 122           /* The following determines that we will never use more than
 123              a quarter of the physical memory.  */
 124           phys_pages /= 4;
 125
 126           pagesize = __sysconf (_SC_PAGESIZE);
 127         }
 128
 129       /* Just a comment here.  We cannot compute
 130            phys_pages * pagesize
 131            and compare the needed amount of memory against this value.
 132            The problem is that some systems might have more physical
 133            memory then can be represented with a `size_t' value (when
 134            measured in bytes.  */
 135
 136       /* If the memory requirements are too high don't allocate memory.  */
 137       if (size / pagesize > (size_t) phys_pages)
 138         _quicksort (b, n, s, cmp);
 139       else
 140         {
 141           /* It's somewhat large, so malloc it.  */
 142           int save = errno;
 143           char *tmp = malloc (size);
 144           if (tmp == NULL)
 145             {
 146               /* Couldn't get space, so use the slower algorithm
 147                  that doesn't need a temporary array.  */
 148               __set_errno (save);
 149               _quicksort (b, n, s, cmp);
 150             }
 151           else
 152             {
 153               __set_errno (save);
 154               msort_with_tmp (b, n, s, cmp, tmp);
 155               free (tmp);
 156             }
 157         }
 158     }
 159 }
 160 libc_hidden_def (qsort)