qsort.c

Go to the documentation of this file.

/*  Copyright (C) 2002     Manuel Novoa III
 *  From my (incomplete) stdlib library for linux and (soon) elks.
 *
 *  This 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.
 *
 *  This 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 this library; if not, see
 *  <http://www.gnu.org/licenses/>.
 */

/*  ATTENTION!   ATTENTION!   ATTENTION!   ATTENTION!   ATTENTION!
 *
 *  This code is currently under development.  Also, I plan to port
 *  it to elks which is a 16-bit environment with a fairly limited
 *  compiler.  Therefore, please refrain from modifying this code
 *  and, instead, pass any bug-fixes, etc. to me.  Thanks.  Manuel
 *
 *  ATTENTION!   ATTENTION!   ATTENTION!   ATTENTION!   ATTENTION! */

/* Oct 29, 2002
 * Fix a couple of 'restrict' bugs in mbstowcs and wcstombs.
 *
 * Nov 21, 2002
 * Add wscto{inttype} functions.
 */

#include <assert.h>
#include <unistd.h>


typedef int (*__compar_d_fn_t)(void *, void *, void *);

/* This code is derived from a public domain shell sort routine by
 * Ray Gardner and found in Bob Stout's snippets collection.  The
 * original code is included below in an #if 0/#endif block.
 *
 * I modified it to avoid the possibility of overflow in the wgap
 * calculation, as well as to reduce the generated code size with
 * bcc and gcc. */

void qsort_r(void  *base,
           size_t nel,
           size_t width,
           int (*comp)(void *, void *, void*),
           void *arg)
{
        size_t wgap, i, j, k;
        char tmp;

        if ((nel > 1) && (width > 0)) {
                assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
                wgap = 0;
                do {
                        wgap = 3 * wgap + 1;
                } while (wgap < (nel-1)/3);
                /* From the above, we know that either wgap == 1 < nel or */
                /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap <  nel. */
                wgap *= width;                  /* So this can not overflow if wnel doesn't. */
                nel *= width;                   /* Convert nel to 'wnel' */
                do {
                        i = wgap;
                        do {
                                j = i;
                                do {
                                        register char *a;
                                        register char *b;

                                        j -= wgap;
                                        a = j + ((char *)base);
                                        b = a + wgap;
                                        if ((*comp)(a, b, arg) <= 0) {
                                                break;
                                        }
                                        k = width;
                                        do {
                                                tmp = *a;
                                                *a++ = *b;
                                                *b++ = tmp;
                                        } while (--k);
                                } while (j >= wgap);
                                i += width;
                        } while (i < nel);
                        wgap = (wgap - width)/3;
                } while (wgap);
        }
}