glib/gqsort.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1991, 1992, 1996, 1997,1999,2004 Free Software Foundation, Inc.
   3  * Copyright (C) 2000 Eazel, Inc.
   4  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This 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  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 /*
  23  * This file was originally part of the GNU C Library, and was modified to allow
  24  * user data to be passed in to the sorting function.
  25  *
  26  * Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
  27  * Modified by Maciej Stachowiak (mjs@eazel.com)
  28  *
  29  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  30  * file for a list of people on the GLib Team.  See the ChangeLog
  31  * files for a list of changes.  These files are distributed with GLib
  32  * at ftp://ftp.gtk.org/pub/gtk/.
  33  */
  34
  35 #include "config.h"
  36
  37 #define _GNU_SOURCE
  38 #include <limits.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41
  42 #include "gqsort.h"
  43
  44 #include "gtestutils.h"
  45
  46 #ifdef HAVE_QSORT_R
  47
  48 /**
  49  * g_qsort_with_data:
  50  * @pbase: start of array to sort
  51  * @total_elems: elements in the array
  52  * @size: size of each element
  53  * @compare_func: function to compare elements
  54  * @user_data: data to pass to @compare_func
  55  *
  56  * This is just like the standard C qsort() function, but
  57  * the comparison routine accepts a user data argument.
  58  */
  59 void
  60 g_qsort_with_data (gconstpointer    pbase,
  61                    gint             total_elems,
  62                    gsize            size,
  63                    GCompareDataFunc compare_func,
  64                    gpointer         user_data)
  65 {
  66   qsort_r (pbase, total_elems, size, compare_func, user_data);
  67 }
  68
  69 #else
  70
  71 /* Byte-wise swap two items of size SIZE. */
  72 #define SWAP(a, b, size)                                                      \
  73   do                                                                          \
  74     {                                                                         \
  75       register size_t __size = (size);                                        \
  76       register char *__a = (a), *__b = (b);                                   \
  77       do                                                                      \
  78         {                                                                     \
  79           char __tmp = *__a;                                                  \
  80           *__a++ = *__b;                                                      \
  81           *__b++ = __tmp;                                                     \
  82         } while (--__size > 0);                                               \
  83     } while (0)
  84
  85 /* Discontinue quicksort algorithm when partition gets below this size.
  86    This particular magic number was chosen to work best on a Sun 4/260. */
  87 #define MAX_THRESH 4
  88
  89 /* Stack node declarations used to store unfulfilled partition obligations. */
  90 typedef struct
  91   {
  92     char *lo;
  93     char *hi;
  94   } stack_node;
  95
  96 /* The next 4 #defines implement a very fast in-line stack abstraction. */
  97 /* The stack needs log (total_elements) entries (we could even subtract
  98    log(MAX_THRESH)).  Since total_elements has type size_t, we get as
  99    upper bound for log (total_elements):
 100    bits per byte (CHAR_BIT) * sizeof(size_t).  */
 101 #define STACK_SIZE      (CHAR_BIT * sizeof(size_t))
 102 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
 103 #define POP(low, high)  ((void) (--top, (low = top->lo), (high = top->hi)))
 104 #define STACK_NOT_EMPTY (stack < top)
 105
 106
 107 /* Order size using quicksort.  This implementation incorporates
 108    four optimizations discussed in Sedgewick:
 109
 110    1. Non-recursive, using an explicit stack of pointer that store the
 111       next array partition to sort.  To save time, this maximum amount
 112       of space required to store an array of SIZE_MAX is allocated on the
 113       stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
 114       only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
 115       Pretty cheap, actually.
 116
 117    2. Chose the pivot element using a median-of-three decision tree.
 118       This reduces the probability of selecting a bad pivot value and
 119       eliminates certain extraneous comparisons.
 120
 121    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
 122       insertion sort to order the MAX_THRESH items within each partition.
 123       This is a big win, since insertion sort is faster for small, mostly
 124       sorted array segments.
 125
 126    4. The larger of the two sub-partitions is always pushed onto the
 127       stack first, with the algorithm then concentrating on the
 128       smaller partition.  This *guarantees* no more than log (total_elems)
 129       stack size is needed (actually O(1) in this case)!  */
 130
 131 void
 132 g_qsort_with_data (gconstpointer    pbase,
 133                    gint             total_elems,
 134                    gsize            size,
 135                    GCompareDataFunc compare_func,
 136                    gpointer         user_data)
 137 {
 138   register char *base_ptr = (char *) pbase;
 139
 140   const size_t max_thresh = MAX_THRESH * size;
 141
 142   g_return_if_fail (total_elems >= 0);
 143   g_return_if_fail (pbase != NULL || total_elems == 0);
 144   g_return_if_fail (compare_func != NULL);
 145
 146   if (total_elems == 0)
 147     /* Avoid lossage with unsigned arithmetic below.  */
 148     return;
 149
 150   if (total_elems > MAX_THRESH)
 151     {
 152       char *lo = base_ptr;
 153       char *hi = &lo[size * (total_elems - 1)];
 154       stack_node stack[STACK_SIZE];
 155       stack_node *top = stack;
 156
 157       PUSH (NULL, NULL);
 158
 159       while (STACK_NOT_EMPTY)
 160         {
 161           char *left_ptr;
 162           char *right_ptr;
 163
 164           /* Select median value from among LO, MID, and HI. Rearrange
 165              LO and HI so the three values are sorted. This lowers the
 166              probability of picking a pathological pivot value and
 167              skips a comparison for both the LEFT_PTR and RIGHT_PTR in
 168              the while loops. */
 169
 170           char *mid = lo + size * ((hi - lo) / size >> 1);
 171
 172           if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
 173             SWAP (mid, lo, size);
 174           if ((*compare_func) ((void *) hi, (void *) mid, user_data) < 0)
 175             SWAP (mid, hi, size);
 176           else
 177             goto jump_over;
 178           if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
 179             SWAP (mid, lo, size);
 180         jump_over:;
 181
 182           left_ptr  = lo + size;
 183           right_ptr = hi - size;
 184
 185           /* Here's the famous ``collapse the walls'' section of quicksort.
 186              Gotta like those tight inner loops!  They are the main reason
 187              that this algorithm runs much faster than others. */
 188           do
 189             {
 190               while ((*compare_func) ((void *) left_ptr, (void *) mid, user_data) < 0)
 191                 left_ptr += size;
 192
 193               while ((*compare_func) ((void *) mid, (void *) right_ptr, user_data) < 0)
 194                 right_ptr -= size;
 195
 196               if (left_ptr < right_ptr)
 197                 {
 198                   SWAP (left_ptr, right_ptr, size);
 199                   if (mid == left_ptr)
 200                     mid = right_ptr;
 201                   else if (mid == right_ptr)
 202                     mid = left_ptr;
 203                   left_ptr += size;
 204                   right_ptr -= size;
 205                 }
 206               else if (left_ptr == right_ptr)
 207                 {
 208                   left_ptr += size;
 209                   right_ptr -= size;
 210                   break;
 211                 }
 212             }
 213           while (left_ptr <= right_ptr);
 214
 215           /* Set up pointers for next iteration.  First determine whether
 216              left and right partitions are below the threshold size.  If so,
 217              ignore one or both.  Otherwise, push the larger partition's
 218              bounds on the stack and continue sorting the smaller one. */
 219
 220           if ((size_t) (right_ptr - lo) <= max_thresh)
 221             {
 222               if ((size_t) (hi - left_ptr) <= max_thresh)
 223                 /* Ignore both small partitions. */
 224                 POP (lo, hi);
 225               else
 226                 /* Ignore small left partition. */
 227                 lo = left_ptr;
 228             }
 229           else if ((size_t) (hi - left_ptr) <= max_thresh)
 230             /* Ignore small right partition. */
 231             hi = right_ptr;
 232           else if ((right_ptr - lo) > (hi - left_ptr))
 233             {
 234               /* Push larger left partition indices. */
 235               PUSH (lo, right_ptr);
 236               lo = left_ptr;
 237             }
 238           else
 239             {
 240               /* Push larger right partition indices. */
 241               PUSH (left_ptr, hi);
 242               hi = right_ptr;
 243             }
 244         }
 245     }
 246
 247   /* Once the BASE_PTR array is partially sorted by quicksort the rest
 248      is completely sorted using insertion sort, since this is efficient
 249      for partitions below MAX_THRESH size. BASE_PTR points to the beginning
 250      of the array to sort, and END_PTR points at the very last element in
 251      the array (*not* one beyond it!). */
 252
 253 #define min(x, y) ((x) < (y) ? (x) : (y))
 254
 255   {
 256     char *const end_ptr = &base_ptr[size * (total_elems - 1)];
 257     char *tmp_ptr = base_ptr;
 258     char *thresh = min(end_ptr, base_ptr + max_thresh);
 259     register char *run_ptr;
 260
 261     /* Find smallest element in first threshold and place it at the
 262        array's beginning.  This is the smallest array element,
 263        and the operation speeds up insertion sort's inner loop. */
 264
 265     for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
 266       if ((*compare_func) ((void *) run_ptr, (void *) tmp_ptr, user_data) < 0)
 267         tmp_ptr = run_ptr;
 268
 269     if (tmp_ptr != base_ptr)
 270       SWAP (tmp_ptr, base_ptr, size);
 271
 272     /* Insertion sort, running from left-hand-side up to right-hand-side.  */
 273
 274     run_ptr = base_ptr + size;
 275     while ((run_ptr += size) <= end_ptr)
 276       {
 277         tmp_ptr = run_ptr - size;
 278         while ((*compare_func) ((void *) run_ptr, (void *) tmp_ptr, user_data) < 0)
 279           tmp_ptr -= size;
 280
 281         tmp_ptr += size;
 282         if (tmp_ptr != run_ptr)
 283           {
 284             char *trav;
 285
 286             trav = run_ptr + size;
 287             while (--trav >= run_ptr)
 288               {
 289                 char c = *trav;
 290                 char *hi, *lo;
 291
 292                 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
 293                   *hi = *lo;
 294                 *hi = c;
 295               }
 296           }
 297       }
 298   }
 299 }
 300
 301 #endif /* HAVE_QSORT_R */