Back to index

php5  5.3.10
mergesort.c
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1992, 1993
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Peter McIlroy.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. All advertising materials mentioning features or use of this software
00017  *    must display the following acknowledgement:
00018  *     This product includes software developed by the University of
00019  *     California, Berkeley and its contributors.
00020  * 4. Neither the name of the University nor the names of its contributors
00021  *    may be used to endorse or promote products derived from this software
00022  *    without specific prior written permission.
00023  *
00024  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00025  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00026  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00027  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00028  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00029  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00030  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00031  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00032  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00033  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00034  * SUCH DAMAGE.
00035  */
00036 
00037 /* $Id: mergesort.c 265279 2008-08-22 12:59:46Z helly $ */
00038 
00039 #if defined(LIBC_SCCS) && !defined(lint)
00040 static char sccsid[] = "@(#)merge.c       8.2 (Berkeley) 2/14/94";
00041 #endif /* LIBC_SCCS and not lint */
00042 
00043 /*
00044  * Hybrid exponential search/linear search merge sort with hybrid
00045  * natural/pairwise first pass.  Requires about .3% more comparisons
00046  * for random data than LSMS with pairwise first pass alone.
00047  * It works for objects as small as two bytes.
00048  */
00049 
00050 #define NATURAL
00051 #define THRESHOLD 16 /* Best choice for natural merge cut-off. */
00052 
00053 /* #define NATURAL to get hybrid natural merge.
00054  * (The default is pairwise merging.)
00055  */
00056 
00057 #include <sys/types.h>
00058 
00059 #include <errno.h>
00060 #include <stdlib.h>
00061 #include <string.h>
00062 
00063 #include "php.h"
00064 
00065 #ifdef PHP_WIN32
00066 #include <winsock2.h> /* Includes definition for u_char */
00067 #endif
00068 
00069 static void setup(u_char *list1, u_char *list2, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC);
00070 static void insertionsort(u_char *a, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC);
00071 
00072 #define ISIZE sizeof(int)
00073 #define PSIZE sizeof(u_char *)
00074 #define ICOPY_LIST(src, dst, last)                      \
00075        do                                               \
00076        *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;    \
00077        while(src < last)
00078 #define ICOPY_ELT(src, dst, i)                                 \
00079        do                                               \
00080        *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;  \
00081        while (i -= ISIZE)
00082 
00083 #define CCOPY_LIST(src, dst, last)        \
00084        do                                 \
00085               *dst++ = *src++;            \
00086        while (src < last)
00087 #define CCOPY_ELT(src, dst, i)                   \
00088        do                                 \
00089               *dst++ = *src++;            \
00090        while (i -= 1)
00091 
00092 /*
00093  * Find the next possible pointer head.  (Trickery for forcing an array
00094  * to do double duty as a linked list when objects do not align with word
00095  * boundaries.
00096  */
00097 /* Assumption: PSIZE is a power of 2. */
00098 #define EVAL(p) (u_char **)                                    \
00099               ((u_char *)0 +                                                 \
00100            (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
00101 
00102 /* {{{ php_mergesort
00103  * Arguments are as for qsort.
00104  */
00105 PHPAPI int php_mergesort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC)
00106 {
00107        register unsigned int i;
00108        register int sense;
00109        int big, iflag;
00110        register u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
00111        u_char *list2, *list1, *p2, *p, *last, **p1;
00112 
00113        if (size < PSIZE / 2) {            /* Pointers must fit into 2 * size. */
00114               errno = EINVAL;
00115               return (-1);
00116        }
00117 
00118        if (nmemb == 0)
00119               return (0);
00120 
00121        /*
00122         * XXX
00123         * Stupid subtraction for the Cray.
00124         */
00125        iflag = 0;
00126        if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
00127               iflag = 1;
00128 
00129        if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
00130               return (-1);
00131 
00132        list1 = base;
00133        setup(list1, list2, nmemb, size, cmp TSRMLS_CC);
00134        last = list2 + nmemb * size;
00135        i = big = 0;
00136        while (*EVAL(list2) != last) {
00137            l2 = list1;
00138            p1 = EVAL(list1);
00139            for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
00140               p2 = *EVAL(p2);
00141               f1 = l2;
00142               f2 = l1 = list1 + (p2 - list2);
00143               if (p2 != last)
00144                      p2 = *EVAL(p2);
00145               l2 = list1 + (p2 - list2);
00146               while (f1 < l1 && f2 < l2) {
00147                      if ((*cmp)(f1, f2 TSRMLS_CC) <= 0) {
00148                             q = f2;
00149                             b = f1, t = l1;
00150                             sense = -1;
00151                      } else {
00152                             q = f1;
00153                             b = f2, t = l2;
00154                             sense = 0;
00155                      }
00156                      if (!big) {   /* here i = 0 */
00157                             while ((b += size) < t && cmp(q, b TSRMLS_CC) >sense)
00158                                    if (++i == 6) {
00159                                           big = 1;
00160                                           goto EXPONENTIAL;
00161                                    }
00162                      } else {
00163 EXPONENTIAL:                for (i = size; ; i <<= 1)
00164                                    if ((p = (b + i)) >= t) {
00165                                           if ((p = t - size) > b &&
00166                                               (*cmp)(q, p TSRMLS_CC) <= sense)
00167                                                  t = p;
00168                                           else
00169                                                  b = p;
00170                                           break;
00171                                    } else if ((*cmp)(q, p TSRMLS_CC) <= sense) {
00172                                           t = p;
00173                                           if (i == size)
00174                                                  big = 0;
00175                                           goto FASTCASE;
00176                                    } else
00177                                           b = p;
00178                             while (t > b+size) {
00179                                    i = (((t - b) / size) >> 1) * size;
00180                                    if ((*cmp)(q, p = b + i TSRMLS_CC) <= sense)
00181                                           t = p;
00182                                    else
00183                                           b = p;
00184                             }
00185                             goto COPY;
00186 FASTCASE:                   while (i > size)
00187                                    if ((*cmp)(q,
00188                                           p = b + (i >>= 1) TSRMLS_CC) <= sense)
00189                                           t = p;
00190                                    else
00191                                           b = p;
00192 COPY:                       b = t;
00193                      }
00194                      i = size;
00195                      if (q == f1) {
00196                             if (iflag) {
00197                                    ICOPY_LIST(f2, tp2, b);
00198                                    ICOPY_ELT(f1, tp2, i);
00199                             } else {
00200                                    CCOPY_LIST(f2, tp2, b);
00201                                    CCOPY_ELT(f1, tp2, i);
00202                             }
00203                      } else {
00204                             if (iflag) {
00205                                    ICOPY_LIST(f1, tp2, b);
00206                                    ICOPY_ELT(f2, tp2, i);
00207                             } else {
00208                                    CCOPY_LIST(f1, tp2, b);
00209                                    CCOPY_ELT(f2, tp2, i);
00210                             }
00211                      }
00212               }
00213               if (f2 < l2) {
00214                      if (iflag)
00215                             ICOPY_LIST(f2, tp2, l2);
00216                      else
00217                             CCOPY_LIST(f2, tp2, l2);
00218               } else if (f1 < l1) {
00219                      if (iflag)
00220                             ICOPY_LIST(f1, tp2, l1);
00221                      else
00222                             CCOPY_LIST(f1, tp2, l1);
00223               }
00224               *p1 = l2;
00225            }
00226            tp2 = list1;     /* swap list1, list2 */
00227            list1 = list2;
00228            list2 = tp2;
00229            last = list2 + nmemb*size;
00230        }
00231        if (base == list2) {
00232               memmove(list2, list1, nmemb*size);
00233               list2 = list1;
00234        }
00235        free(list2);
00236        return (0);
00237 }
00238 /* }}} */
00239 
00240 #define       swap(a, b) {                              \
00241               s = b;                             \
00242               i = size;                          \
00243               do {                               \
00244                      tmp = *a; *a++ = *s; *s++ = tmp; \
00245               } while (--i);                            \
00246               a -= size;                         \
00247        }
00248 #define reverse(bot, top) {                      \
00249        s = top;                                  \
00250        do {                                      \
00251               i = size;                          \
00252               do {                               \
00253                      tmp = *bot; *bot++ = *s; *s++ = tmp; \
00254               } while (--i);                            \
00255               s -= size2;                        \
00256        } while(bot < s);                         \
00257 }
00258 
00259 /* {{{ setup
00260  * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
00261  * increasing order, list2 in a corresponding linked list.  Checks for runs
00262  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
00263  * is defined.  Otherwise simple pairwise merging is used.)
00264  */
00265 static void setup(u_char *list1, u_char *list2, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC)
00266 {
00267        int i, length, size2, tmp, sense;
00268        u_char *f1, *f2, *s, *l2, *last, *p2;
00269 
00270        size2 = size*2;
00271        if (n <= 5) {
00272               insertionsort(list1, n, size, cmp TSRMLS_CC);
00273               *EVAL(list2) = (u_char*) list2 + n*size;
00274               return;
00275        }
00276        /*
00277         * Avoid running pointers out of bounds; limit n to evens
00278         * for simplicity.
00279         */
00280        i = 4 + (n & 1);
00281        insertionsort(list1 + (n - i) * size, i, size, cmp TSRMLS_CC);
00282        last = list1 + size * (n - i);
00283        *EVAL(list2 + (last - list1)) = list2 + n * size;
00284 
00285 #ifdef NATURAL
00286        p2 = list2;
00287        f1 = list1;
00288        sense = (cmp(f1, f1 + size TSRMLS_CC) > 0);
00289        for (; f1 < last; sense = !sense) {
00290               length = 2;
00291                                    /* Find pairs with same sense. */
00292               for (f2 = f1 + size2; f2 < last; f2 += size2) {
00293                      if ((cmp(f2, f2+ size TSRMLS_CC) > 0) != sense)
00294                             break;
00295                      length += 2;
00296               }
00297               if (length < THRESHOLD) {          /* Pairwise merge */
00298                      do {
00299                             p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
00300                             if (sense > 0)
00301                                    swap (f1, f1 + size);
00302                      } while ((f1 += size2) < f2);
00303               } else {                           /* Natural merge */
00304                      l2 = f2;
00305                      for (f2 = f1 + size2; f2 < l2; f2 += size2) {
00306                             if ((cmp(f2-size, f2 TSRMLS_CC) > 0) != sense) {
00307                                    p2 = *EVAL(p2) = f2 - list1 + list2;
00308                                    if (sense > 0)
00309                                           reverse(f1, f2-size);
00310                                    f1 = f2;
00311                             }
00312                      }
00313                      if (sense > 0)
00314                             reverse (f1, f2-size);
00315                      f1 = f2;
00316                      if (f2 < last || cmp(f2 - size, f2 TSRMLS_CC) > 0)
00317                             p2 = *EVAL(p2) = f2 - list1 + list2;
00318                      else
00319                             p2 = *EVAL(p2) = list2 + n*size;
00320               }
00321        }
00322 #else         /* pairwise merge only. */
00323        for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
00324               p2 = *EVAL(p2) = p2 + size2;
00325               if (cmp (f1, f1 + size TSRMLS_CC) > 0)
00326                      swap(f1, f1 + size);
00327        }
00328 #endif /* NATURAL */
00329 }
00330 /* }}} */
00331 
00332 /* {{{ insertionsort
00333  * This is to avoid out-of-bounds addresses in sorting the
00334  * last 4 elements.
00335  */
00336 static void insertionsort(u_char *a, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC)
00337 {
00338        u_char *ai, *s, *t, *u, tmp;
00339        int i;
00340 
00341        for (ai = a+size; --n >= 1; ai += size)
00342               for (t = ai; t > a; t -= size) {
00343                      u = t - size;
00344                      if (cmp(u, t TSRMLS_CC) <= 0)
00345                             break;
00346                      swap(u, t);
00347               }
00348 }
00349 /* }}} */
00350 
00351 /*
00352  * Local variables:
00353  * tab-width: 4
00354  * c-basic-offset: 4
00355  * End:
00356  * vim600: fdm=marker
00357  * vim: noet sw=4 ts=4
00358  */