Logo Search packages:      
Sourcecode: pan version File versions  Download package

msort.c

/*
 *  This is included in Pan to provide a stable sorting mechanism.  This is
 *  used, for example, in the articlelist, where sorting by one column, and
 *  then a second, provides an quick & easy way to get a two-key sort.
 *  This isn't possible without a stable sorter.
 *
 */

/* An alternative to qsort, with an identical interface.
   This file is part of the GNU C Library.
   Copyright (C) 1992, 1995, 1996, 1997 Free Software Foundation, Inc.
   Written by Mike Haertel, September 1988.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with the GNU C Library; see the file COPYING.LIB.  If not,
   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <pan/base/pan-glib-extensions.h>

static void
msort_with_tmp (
      void *b,
      size_t n,
      size_t s,
      int(*cmp)(const void*,const void*),
      char* t)
{
      char *tmp;
      char *b1, *b2;
      size_t n1, n2;
      const int opsiz = sizeof(unsigned long int);

      if (n <= 1)
            return;

      n1 = n / 2;
      n2 = n - n1;
      b1 = b;
      b2 = (char *) b + (n1 * s);

      msort_with_tmp (b1, n1, s, cmp, t);
      msort_with_tmp (b2, n2, s, cmp, t);

      tmp = t;

      if (s == opsiz && (b1 - (char *) 0) % opsiz == 0)
            /* operating on aligned words.  Use direct word stores. */
            while (n1 > 0 && n2 > 0)
            {
                  if ((*cmp) (b1, b2) <= 0)
                  {
                        --n1;
                        *((unsigned long int *) tmp)++ =
                              *((unsigned long int *) b1)++;
                  }
                  else
                  {
                        --n2;
                        *((unsigned long int *) tmp)++ =
                              *((unsigned long int *) b2)++;
                  }
            }
      else
            while (n1 > 0 && n2 > 0)
            {
                  if ((*cmp) (b1, b2) <= 0)
                  {
                        memcpy (tmp, b1, s);
                        tmp += s;
                        b1 += s;
                        --n1;
                  }
                  else
                  {
                        memcpy (tmp, b2, s);
                        tmp += s;
                        b2 += s;
                        --n2;
                  }
            }
      if (n1 > 0)
            memcpy (tmp, b1, n1 * s);
      memcpy (b, t, (n - n2) * s);
}

void
msort (void *b, size_t n, size_t s, int(*cmp)(const void *, const void*))
{
      const size_t size = n * s;

      int save = errno;
      char *tmp = malloc (size);
      if (tmp == NULL)
      {
            /* Couldn't get space, so fall back to the system sorter */
            qsort (b, n, s, cmp);
      }
      else
      {
            msort_with_tmp (b, n, s, cmp, tmp);
            free (tmp);
      }
      errno = save;
}

Generated by  Doxygen 1.6.0   Back to index