reactos/lib/kjs/src/mrgsort.c

   1 /*
   2  * Re-entrant mergesort.
   3  * Copyright (c) 1998 New Generation Software (NGS) Oy
   4  *
   5  * Author: Markku Rossi <mtr@ngs.fi>
   6  */
   7
   8 /*
   9  * This library is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Library General Public
  11  * License as published by the Free Software Foundation; either
  12  * version 2 of the License, or (at your option) any later version.
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Library General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Library General Public
  20  * License along with this library; if not, write to the Free
  21  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  22  * MA 02111-1307, USA
  23  */
  24
  25 /*
  26  * $Source: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/kjs/src/mrgsort.c,v $
  27  * $Id$
  28  */
  29
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <assert.h>
  33
  34 #include "mrgsort.h"
  35
  36 /*
  37  * Types and definitions.
  38  */
  39
  40 #define COPY(buf1, idx1, buf2, idx2)    \
  41   memcpy ((buf1) + (idx1) * size, (buf2) + (idx2) * size, size);
  42
  43 /*
  44  * Static functions.
  45  */
  46
  47 static void
  48 do_mergesort (unsigned char *base, unsigned int size, unsigned char *tmp,
  49               unsigned int l, unsigned int r,
  50               MergesortCompFunc func, void *func_ctx)
  51 {
  52   unsigned int i, j, k, m;
  53
  54   if (r <= l)
  55     return;
  56
  57   m = (r + l) / 2;
  58   do_mergesort (base, size, tmp, l, m, func, func_ctx);
  59   do_mergesort (base, size, tmp, m + 1, r, func, func_ctx);
  60
  61   memcpy (tmp + l * size, base + l * size, (r - l + 1) * size);
  62
  63   i = l;
  64   j = m + 1;
  65   k = l;
  66
  67   /* Merge em. */
  68   while (i <= m && j <= r)
  69     {
  70       if ((*func) (tmp + i * size, tmp + j * size, func_ctx) <= 0)
  71         {
  72           COPY (base, k, tmp, i);
  73           i++;
  74         }
  75       else
  76         {
  77           COPY (base, k, tmp, j);
  78           j++;
  79         }
  80       k++;
  81     }
  82
  83   /* Copy left-overs.  Only one of the following will be executed. */
  84   for (; i <= m; i++)
  85     {
  86       COPY (base, k, tmp, i);
  87       k++;
  88     }
  89   for (; j <= r; j++)
  90     {
  91       COPY (base, k, tmp, j);
  92       k++;
  93     }
  94 }
  95
  96
  97 /*
  98  * Global functions.
  99  */
 100
 101 void
 102 mergesort_r (void *base, unsigned int number_of_elements,
 103              unsigned int size, MergesortCompFunc comparison_func,
 104              void *comparison_func_context)
 105 {
 106   void *tmp;
 107
 108   if (number_of_elements == 0)
 109     return;
 110
 111   /* Allocate tmp buffer. */
 112   tmp = malloc (number_of_elements * size);
 113   assert (tmp != NULL);
 114
 115   do_mergesort (base, size, tmp, 0, number_of_elements - 1, comparison_func,
 116                 comparison_func_context);
 117
 118   free (tmp);
 119 }