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 #include <limits.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41 #include "glib.h"
  42 #include "galias.h"
  43
  44 /* Byte-wise swap two items of size SIZE. */
  45 #define SWAP(a, b, size)                                                      \
  46   do                                                                          \
  47     {                                                                         \
  48       register size_t __size = (size);                                        \
  49       register char *__a = (a), *__b = (b);                                   \
  50       do                                                                      \
  51         {                                                                     \
  52           char __tmp = *__a;                                                  \
  53           *__a++ = *__b;                                                      \
  54           *__b++ = __tmp;                                                     \
  55         } while (--__size > 0);                                               \
  56     } while (0)
  57
  58 /* Discontinue quicksort algorithm when partition gets below this size.
  59    This particular magic number was chosen to work best on a Sun 4/260. */
  60 #define MAX_THRESH 4
  61
  62 /* Stack node declarations used to store unfulfilled partition obligations. */
  63 typedef struct
  64   {
  65     char *lo;
  66     char *hi;
  67   } stack_node;
  68
  69 /* The next 4 #defines implement a very fast in-line stack abstraction. */
  70 /* The stack needs log (total_elements) entries (we could even subtract
  71    log(MAX_THRESH)).  Since total_elements has type size_t, we get as
  72    upper bound for log (total_elements):
  73    bits per byte (CHAR_BIT) * sizeof(size_t).  */
  74 #define STACK_SIZE      (CHAR_BIT * sizeof(size_t))
  75 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
  76 #define POP(low, high)  ((void) (--top, (low = top->lo), (high = top->hi)))
  77 #define STACK_NOT_EMPTY (stack < top)
  78
  79
  80 /* Order size using quicksort.  This implementation incorporates
  81    four optimizations discussed in Sedgewick:
  82
  83    1. Non-recursive, using an explicit stack of pointer that store the
  84       next array partition to sort.  To save time, this maximum amount
  85       of space required to store an array of SIZE_MAX is allocated on the
  86       stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
  87       only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
  88       Pretty cheap, actually.
  89
  90    2. Chose the pivot element using a median-of-three decision tree.
  91       This reduces the probability of selecting a bad pivot value and
  92       eliminates certain extraneous comparisons.
  93
  94    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
  95       insertion sort to order the MAX_THRESH items within each partition.
  96       This is a big win, since insertion sort is faster for small, mostly
  97       sorted array segments.
  98
  99    4. The larger of the two sub-partitions is always pushed onto the
 100       stack first, with the algorithm then concentrating on the
 101       smaller partition.  This *guarantees* no more than log (total_elems)
 102       stack size is needed (actually O(1) in this case)!  */
 103
 104 /**
 105  * g_qsort_with_data:
 106  * @pbase: start of array to sort
 107  * @total_elems: elements in the array
 108  * @size: size of each element
 109  * @compare_func: function to compare elements
 110  * @user_data: data to pass to @compare_func
 111  *
 112  * This is just like the standard C qsort() function, but
 113  * the comparison routine accepts a user data argument.
 114  *
 115  **/
 116 void
 117 g_qsort_with_data (gconstpointer    pbase,
 118                    gint             total_elems,
 119                    gsize            size,
 120                    GCompareDataFunc compare_func,
 121                    gpointer         user_data)
 122 {
 123   register char *base_ptr = (char *) pbase;
 124
 125   const size_t max_thresh = MAX_THRESH * size;
 126
 127   g_return_if_fail (total_elems >= 0);
 128   g_return_if_fail (pbase != NULL || total_elems == 0);
 129   g_return_if_fail (compare_func != NULL);
 130
 131   if (total_elems == 0)
 132     /* Avoid lossage with unsigned arithmetic below.  */
 133     return;
 134
 135   if (total_elems > MAX_THRESH)
 136     {
 137       char *lo = base_ptr;
 138       char *hi = &lo[size * (total_elems - 1)];
 139       stack_node stack[STACK_SIZE];
 140       stack_node *top = stack;
 141
 142       PUSH (NULL, NULL);
 143
 144       while (STACK_NOT_EMPTY)
 145         {
 146           char *left_ptr;
 147           char *right_ptr;
 148
 149           /* Select median value from among LO, MID, and HI. Rearrange
 150              LO and HI so the three values are sorted. This lowers the
 151              probability of picking a pathological pivot value and
 152              skips a comparison for both the LEFT_PTR and RIGHT_PTR in
 153              the while loops. */
 154
 155           char *mid = lo + size * ((hi - lo) / size >> 1);
 156
 157           if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
 158             SWAP (mid, lo, size);
 159           if ((*compare_func) ((void *) hi, (void *) mid, user_data) < 0)
 160             SWAP (mid, hi, size);
 161           else
 162             goto jump_over;
 163           if ((*compare_func) ((void *) mid, (void *) lo, user_data) < 0)
 164             SWAP (mid, lo, size);
 165         jump_over:;
 166
 167           left_ptr  = lo + size;
 168           right_ptr = hi - size;
 169
 170           /* Here's the famous ``collapse the walls'' section of quicksort.
 171              Gotta like those tight inner loops!  They are the main reason
 172              that this algorithm runs much faster than others. */
 173           do
 174             {
 175               while ((*compare_func) ((void *) left_ptr, (void *) mid, user_data) < 0)
 176                 left_ptr += size;
 177
 178               while ((*compare_func) ((void *) mid, (void *) right_ptr, user_data) < 0)
 179                 right_ptr -= size;
 180
 181               if (left_ptr < right_ptr)
 182                 {
 183                   SWAP (left_ptr, right_ptr, size);
 184                   if (mid == left_ptr)
 185                     mid = right_ptr;
 186                   else if (mid == right_ptr)
 187                     mid = left_ptr;
 188                   left_ptr += size;
 189                   right_ptr -= size;
 190                 }
 191               else if (left_ptr == right_ptr)
 192                 {
 193                   left_ptr += size;
 194                   right_ptr -= size;
 195                   break;
 196                 }
 197             }
 198           while (left_ptr <= right_ptr);
 199
 200           /* Set up pointers for next iteration.  First determine whether
 201              left and right partitions are below the threshold size.  If so,
 202              ignore one or both.  Otherwise, push the larger partition's
 203              bounds on the stack and continue sorting the smaller one. */
 204
 205           if ((size_t) (right_ptr - lo) <= max_thresh)
 206             {
 207               if ((size_t) (hi - left_ptr) <= max_thresh)
 208                 /* Ignore both small partitions. */
 209                 POP (lo, hi);
 210               else
 211                 /* Ignore small left partition. */
 212                 lo = left_ptr;
 213             }
 214           else if ((size_t) (hi - left_ptr) <= max_thresh)
 215             /* Ignore small right partition. */
 216             hi = right_ptr;
 217           else if ((right_ptr - lo) > (hi - left_ptr))
 218             {
 219               /* Push larger left partition indices. */
 220               PUSH (lo, right_ptr);
 221               lo = left_ptr;
 222             }
 223           else
 224             {
 225               /* Push larger right partition indices. */
 226               PUSH (left_ptr, hi);
 227               hi = right_ptr;
 228             }
 229         }
 230     }
 231
 232   /* Once the BASE_PTR array is partially sorted by quicksort the rest
 233      is completely sorted using insertion sort, since this is efficient
 234      for partitions below MAX_THRESH size. BASE_PTR points to the beginning
 235      of the array to sort, and END_PTR points at the very last element in
 236      the array (*not* one beyond it!). */
 237
 238 #define min(x, y) ((x) < (y) ? (x) : (y))
 239
 240   {
 241     char *const end_ptr = &base_ptr[size * (total_elems - 1)];
 242     char *tmp_ptr = base_ptr;
 243     char *thresh = min(end_ptr, base_ptr + max_thresh);
 244     register char *run_ptr;
 245
 246     /* Find smallest element in first threshold and place it at the
 247        array's beginning.  This is the smallest array element,
 248        and the operation speeds up insertion sort's inner loop. */
 249
 250     for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
 251       if ((*compare_func) ((void *) run_ptr, (void *) tmp_ptr, user_data) < 0)
 252         tmp_ptr = run_ptr;
 253
 254     if (tmp_ptr != base_ptr)
 255       SWAP (tmp_ptr, base_ptr, size);
 256
 257     /* Insertion sort, running from left-hand-side up to right-hand-side.  */
 258
 259     run_ptr = base_ptr + size;
 260     while ((run_ptr += size) <= end_ptr)
 261       {
 262         tmp_ptr = run_ptr - size;
 263         while ((*compare_func) ((void *) run_ptr, (void *) tmp_ptr, user_data) < 0)
 264           tmp_ptr -= size;
 265
 266         tmp_ptr += size;
 267         if (tmp_ptr != run_ptr)
 268           {
 269             char *trav;
 270
 271             trav = run_ptr + size;
 272             while (--trav >= run_ptr)
 273               {
 274                 char c = *trav;
 275                 char *hi, *lo;
 276
 277                 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
 278                   *hi = *lo;
 279                 *hi = c;
 280               }
 281           }
 282       }
 283   }
 284 }
 285
 286 #define __G_QSORT_C__
 287 #include "galiasdef.c"