stdlib/msort.c

   1 /* msort -- an alternative to qsort, with an identical interface.
   2    Copyright (C) 1992, 1995 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 #include <memcopy.h>
  26 #include <errno.h>
  27
  28 static void
  29 DEFUN(msort_with_tmp, (b, n, s, cmp, t),
  30       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp AND char *t)
  31 {
  32   char *tmp;
  33   char *b1, *b2;
  34   size_t n1, n2;
  35
  36   if (n <= 1)
  37     return;
  38
  39   n1 = n / 2;
  40   n2 = n - n1;
  41   b1 = b;
  42   b2 = (char *) b + (n1 * s);
  43
  44   msort_with_tmp (b1, n1, s, cmp, t);
  45   msort_with_tmp (b2, n2, s, cmp, t);
  46
  47   tmp = t;
  48
  49   if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0)
  50     /* We are operating on aligned words.  Use direct word stores.  */
  51     while (n1 > 0 && n2 > 0)
  52       {
  53         if ((*cmp) (b1, b2) <= 0)
  54           {
  55             --n1;
  56             *((op_t *) tmp)++ = *((op_t *) b1)++;
  57           }
  58         else
  59           {
  60             --n2;
  61             *((op_t *) tmp)++ = *((op_t *) b2)++;
  62           }
  63       }
  64   else
  65     while (n1 > 0 && n2 > 0)
  66       {
  67         if ((*cmp) (b1, b2) <= 0)
  68           {
  69             memcpy (tmp, b1, s);
  70             b1 += s;
  71             --n1;
  72           }
  73         else
  74           {
  75             memcpy (tmp, b2, s);
  76             b2 += s;
  77             --n2;
  78           }
  79         tmp += s;
  80       }
  81   if (n1 > 0)
  82     memcpy (tmp, b1, n1 * s);
  83   memcpy (b, t, (n - n2) * s);
  84 }
  85
  86 void
  87 DEFUN(qsort, (b, n, s, cmp),
  88       PTR b AND size_t n AND size_t s AND __compar_fn_t cmp)
  89 {
  90   CONST size_t size = n * s;
  91
  92   if (size < 1024)
  93     /* The temporary array is small, so put it on the stack.  */
  94     msort_with_tmp (b, n, s, cmp, __alloca (size));
  95   else
  96     {
  97       /* It's somewhat large, so malloc it.  */
  98       int save = errno;
  99       char *tmp = malloc (size);
 100       if (tmp == NULL)
 101         {
 102           /* Couldn't get space, so use the slower algorithm
 103              that doesn't need a temporary array.  */
 104           extern void EXFUN(_quicksort, (PTR __base,
 105                                          size_t __nmemb, size_t __size,
 106                                          __compar_fn_t __compar));
 107           _quicksort (b, n, s, cmp);
 108         }
 109       else
 110         {
 111           msort_with_tmp (b, n, s, cmp, tmp);
 112           free (tmp);
 113         }
 114       errno = save;
 115     }
 116 }