stdlib/msort.c

   1 /* msort -- an alternative to qsort, with an identical interface.
   2    Copyright (C) 1992 Free Software Foundation, Inc.
   3    Written by Mike Haertel, September 1988.
   4
   5 This file is part of the GNU C Library.
   6
   7 The GNU C Library is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU Library General Public License as
   9 published by the Free Software Foundation; either version 2 of the
  10 License, or (at your option) any later version.
  11
  12 The GNU C Library is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 Library General Public License for more details.
  16
  17 You should have received a copy of the GNU Library General Public
  18 License along with the GNU C Library; see the file COPYING.LIB.  If
  19 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  20 Cambridge, MA 02139, USA.  */
  21
  22 #include <ansidecl.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #define MEMCPY(dst, src, s)                     \
  27   ((s) == sizeof (int)                          \
  28    ? (*(int *) (dst) = *(int *) (src), (dst))   \
  29    : memcpy (dst, src, s))
  30
  31 static void
  32 DEFUN(msort_with_tmp, (b, n, s, cmp, t),
  33       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND 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   while (n1 > 0 && n2 > 0)
  53     {
  54       if ((*cmp) (b1, b2) <= 0)
  55         {
  56           MEMCPY (tmp, b1, s);
  57           b1 += s;
  58           --n1;
  59         }
  60       else
  61         {
  62           MEMCPY (tmp, b2, s);
  63           b2 += s;
  64           --n2;
  65         }
  66       tmp += s;
  67     }
  68   if (n1 > 0)
  69     memcpy (tmp, b1, n1 * s);
  70   memcpy (b, t, (n - n2) * s);
  71 }
  72
  73 void
  74 DEFUN(qsort, (b, n, s, cmp),
  75       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp)
  76 {
  77   CONST size_t size = n * s;
  78
  79   if (size < 1024)
  80     /* The temporary array is small, so put it on the stack.  */
  81     msort_with_tmp (b, n, s, cmp, __alloca (size));
  82   else
  83     {
  84       /* It's somewhat large, so malloc it.  */
  85       int save = errno;
  86       char *tmp = malloc (size);
  87       if (tmp == NULL)
  88         {
  89           /* Couldn't get space, so use the slower algorithm
  90              that doesn't need a temporary array.  */
  91           extern void EXFUN(_quicksort, (PTR __base,
  92                                          size_t __nmemb, size_t __size,
  93                                          __compar_fn_t __compar));
  94           _quicksort (b, n, s, cmp);
  95         }
  96       else
  97         {
  98           msort_with_tmp (b, n, s, cmp, tmp);
  99           free (tmp);
 100         }
 101       errno = save;
 102     }
 103 }