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, 1995, 1996, 1997 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 Library General Public License as
   8    published by the Free Software Foundation; either version 2 of the
   9    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    Library General Public License for more details.
  15
  16    You should have received a copy of the GNU Library General Public
  17    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  18    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <memcopy.h>
  24 #include <errno.h>
  25
  26 static void msort_with_tmp __P ((void *b, size_t n, size_t s,
  27                                  __compar_fn_t cmp, char *t));
  28
  29 static void
  30 msort_with_tmp (b, n, s, cmp, t)
  31      void *b;
  32      size_t n;
  33      size_t s;
  34      __compar_fn_t cmp;
  35      char *t;
  36 {
  37   char *tmp;
  38   char *b1, *b2;
  39   size_t n1, n2;
  40
  41   if (n <= 1)
  42     return;
  43
  44   n1 = n / 2;
  45   n2 = n - n1;
  46   b1 = b;
  47   b2 = (char *) b + (n1 * s);
  48
  49   msort_with_tmp (b1, n1, s, cmp, t);
  50   msort_with_tmp (b2, n2, s, cmp, t);
  51
  52   tmp = t;
  53
  54   if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
  55     /* We are operating on aligned words.  Use direct word stores.  */
  56     while (n1 > 0 && n2 > 0)
  57       {
  58         if ((*cmp) (b1, b2) <= 0)
  59           {
  60             --n1;
  61             *((op_t *) tmp)++ = *((op_t *) b1)++;
  62           }
  63         else
  64           {
  65             --n2;
  66             *((op_t *) tmp)++ = *((op_t *) b2)++;
  67           }
  68       }
  69   else
  70     while (n1 > 0 && n2 > 0)
  71       {
  72         if ((*cmp) (b1, b2) <= 0)
  73           {
  74             tmp = (char *) __mempcpy (tmp, b1, s);
  75             b1 += s;
  76             --n1;
  77           }
  78         else
  79           {
  80             tmp = (char *) __mempcpy (tmp, b2, s);
  81             b2 += s;
  82             --n2;
  83           }
  84       }
  85   if (n1 > 0)
  86     memcpy (tmp, b1, n1 * s);
  87   memcpy (b, t, (n - n2) * s);
  88 }
  89
  90 void
  91 qsort (b, n, s, cmp)
  92      void *b;
  93      size_t n;
  94      size_t s;
  95      __compar_fn_t cmp;
  96 {
  97   const size_t size = n * s;
  98
  99   if (size < 1024)
 100     /* The temporary array is small, so put it on the stack.  */
 101     msort_with_tmp (b, n, s, cmp, __alloca (size));
 102   else
 103     {
 104       /* It's somewhat large, so malloc it.  */
 105       int save = errno;
 106       char *tmp = malloc (size);
 107       if (tmp == NULL)
 108         {
 109           /* Couldn't get space, so use the slower algorithm
 110              that doesn't need a temporary array.  */
 111           extern void _quicksort __P ((void *const __base,
 112                                        size_t __nmemb, size_t __size,
 113                                        __compar_fn_t __compar));
 114           _quicksort (b, n, s, cmp);
 115         }
 116       else
 117         {
 118           msort_with_tmp (b, n, s, cmp, tmp);
 119           free (tmp);
 120         }
 121       __set_errno (save);
 122     }
 123 }