Annotation of embedaddon/php/main/mergesort.c, revision 1.1.1.2

1.1       misho       1: /*-
                      2:  * Copyright (c) 1992, 1993
                      3:  *     The Regents of the University of California.  All rights reserved.
                      4:  *
                      5:  * This code is derived from software contributed to Berkeley by
                      6:  * Peter McIlroy.
                      7:  *
                      8:  * Redistribution and use in source and binary forms, with or without
                      9:  * modification, are permitted provided that the following conditions
                     10:  * are met:
                     11:  * 1. Redistributions of source code must retain the above copyright
                     12:  *    notice, this list of conditions and the following disclaimer.
                     13:  * 2. Redistributions in binary form must reproduce the above copyright
                     14:  *    notice, this list of conditions and the following disclaimer in the
                     15:  *    documentation and/or other materials provided with the distribution.
                     16:  * 3. All advertising materials mentioning features or use of this software
                     17:  *    must display the following acknowledgement:
                     18:  *     This product includes software developed by the University of
                     19:  *     California, Berkeley and its contributors.
                     20:  * 4. Neither the name of the University nor the names of its contributors
                     21:  *    may be used to endorse or promote products derived from this software
                     22:  *    without specific prior written permission.
                     23:  *
                     24:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     25:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     26:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     27:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     28:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     29:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     30:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     31:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     32:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     33:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     34:  * SUCH DAMAGE.
                     35:  */
                     36: 
1.1.1.2 ! misho      37: /* $Id$ */
1.1       misho      38: 
                     39: #if defined(LIBC_SCCS) && !defined(lint)
                     40: static char sccsid[] = "@(#)merge.c    8.2 (Berkeley) 2/14/94";
                     41: #endif /* LIBC_SCCS and not lint */
                     42: 
                     43: /*
                     44:  * Hybrid exponential search/linear search merge sort with hybrid
                     45:  * natural/pairwise first pass.  Requires about .3% more comparisons
                     46:  * for random data than LSMS with pairwise first pass alone.
                     47:  * It works for objects as small as two bytes.
                     48:  */
                     49: 
                     50: #define NATURAL
                     51: #define THRESHOLD 16   /* Best choice for natural merge cut-off. */
                     52: 
                     53: /* #define NATURAL to get hybrid natural merge.
                     54:  * (The default is pairwise merging.)
                     55:  */
                     56: 
                     57: #include <sys/types.h>
                     58: 
                     59: #include <errno.h>
                     60: #include <stdlib.h>
                     61: #include <string.h>
                     62: 
                     63: #include "php.h"
                     64: 
                     65: #ifdef PHP_WIN32
                     66: #include <winsock2.h> /* Includes definition for u_char */
                     67: #endif
                     68: 
                     69: 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);
                     70: static void insertionsort(u_char *a, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC);
                     71: 
                     72: #define ISIZE sizeof(int)
                     73: #define PSIZE sizeof(u_char *)
                     74: #define ICOPY_LIST(src, dst, last)                             \
                     75:        do                                                      \
                     76:        *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;    \
                     77:        while(src < last)
                     78: #define ICOPY_ELT(src, dst, i)                                 \
                     79:        do                                                      \
                     80:        *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;  \
                     81:        while (i -= ISIZE)
                     82: 
                     83: #define CCOPY_LIST(src, dst, last)             \
                     84:        do                                      \
                     85:                *dst++ = *src++;                \
                     86:        while (src < last)
                     87: #define CCOPY_ELT(src, dst, i)                 \
                     88:        do                                      \
                     89:                *dst++ = *src++;                \
                     90:        while (i -= 1)
                     91: 
                     92: /*
                     93:  * Find the next possible pointer head.  (Trickery for forcing an array
                     94:  * to do double duty as a linked list when objects do not align with word
                     95:  * boundaries.
                     96:  */
                     97: /* Assumption: PSIZE is a power of 2. */
                     98: #define EVAL(p) (u_char **)                                            \
                     99:                ((u_char *)0 +                                                  \
                    100:            (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
                    101: 
                    102: /* {{{ php_mergesort
                    103:  * Arguments are as for qsort.
                    104:  */
                    105: PHPAPI int php_mergesort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC)
                    106: {
                    107:        register unsigned int i;
                    108:        register int sense;
                    109:        int big, iflag;
                    110:        register u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
                    111:        u_char *list2, *list1, *p2, *p, *last, **p1;
                    112: 
                    113:        if (size < PSIZE / 2) {         /* Pointers must fit into 2 * size. */
                    114:                errno = EINVAL;
                    115:                return (-1);
                    116:        }
                    117: 
                    118:        if (nmemb == 0)
                    119:                return (0);
                    120: 
                    121:        /*
                    122:         * XXX
                    123:         * Stupid subtraction for the Cray.
                    124:         */
                    125:        iflag = 0;
                    126:        if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
                    127:                iflag = 1;
                    128: 
                    129:        if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
                    130:                return (-1);
                    131: 
                    132:        list1 = base;
                    133:        setup(list1, list2, nmemb, size, cmp TSRMLS_CC);
                    134:        last = list2 + nmemb * size;
                    135:        i = big = 0;
                    136:        while (*EVAL(list2) != last) {
                    137:            l2 = list1;
                    138:            p1 = EVAL(list1);
                    139:            for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
                    140:                p2 = *EVAL(p2);
                    141:                f1 = l2;
                    142:                f2 = l1 = list1 + (p2 - list2);
                    143:                if (p2 != last)
                    144:                        p2 = *EVAL(p2);
                    145:                l2 = list1 + (p2 - list2);
                    146:                while (f1 < l1 && f2 < l2) {
                    147:                        if ((*cmp)(f1, f2 TSRMLS_CC) <= 0) {
                    148:                                q = f2;
                    149:                                b = f1, t = l1;
                    150:                                sense = -1;
                    151:                        } else {
                    152:                                q = f1;
                    153:                                b = f2, t = l2;
                    154:                                sense = 0;
                    155:                        }
                    156:                        if (!big) {     /* here i = 0 */
                    157:                                while ((b += size) < t && cmp(q, b TSRMLS_CC) >sense)
                    158:                                        if (++i == 6) {
                    159:                                                big = 1;
                    160:                                                goto EXPONENTIAL;
                    161:                                        }
                    162:                        } else {
                    163: EXPONENTIAL:                   for (i = size; ; i <<= 1)
                    164:                                        if ((p = (b + i)) >= t) {
                    165:                                                if ((p = t - size) > b &&
                    166:                                                    (*cmp)(q, p TSRMLS_CC) <= sense)
                    167:                                                        t = p;
                    168:                                                else
                    169:                                                        b = p;
                    170:                                                break;
                    171:                                        } else if ((*cmp)(q, p TSRMLS_CC) <= sense) {
                    172:                                                t = p;
                    173:                                                if (i == size)
                    174:                                                        big = 0;
                    175:                                                goto FASTCASE;
                    176:                                        } else
                    177:                                                b = p;
                    178:                                while (t > b+size) {
                    179:                                        i = (((t - b) / size) >> 1) * size;
                    180:                                        if ((*cmp)(q, p = b + i TSRMLS_CC) <= sense)
                    181:                                                t = p;
                    182:                                        else
                    183:                                                b = p;
                    184:                                }
                    185:                                goto COPY;
                    186: FASTCASE:                      while (i > size)
                    187:                                        if ((*cmp)(q,
                    188:                                                p = b + (i >>= 1) TSRMLS_CC) <= sense)
                    189:                                                t = p;
                    190:                                        else
                    191:                                                b = p;
                    192: COPY:                          b = t;
                    193:                        }
                    194:                        i = size;
                    195:                        if (q == f1) {
                    196:                                if (iflag) {
                    197:                                        ICOPY_LIST(f2, tp2, b);
                    198:                                        ICOPY_ELT(f1, tp2, i);
                    199:                                } else {
                    200:                                        CCOPY_LIST(f2, tp2, b);
                    201:                                        CCOPY_ELT(f1, tp2, i);
                    202:                                }
                    203:                        } else {
                    204:                                if (iflag) {
                    205:                                        ICOPY_LIST(f1, tp2, b);
                    206:                                        ICOPY_ELT(f2, tp2, i);
                    207:                                } else {
                    208:                                        CCOPY_LIST(f1, tp2, b);
                    209:                                        CCOPY_ELT(f2, tp2, i);
                    210:                                }
                    211:                        }
                    212:                }
                    213:                if (f2 < l2) {
                    214:                        if (iflag)
                    215:                                ICOPY_LIST(f2, tp2, l2);
                    216:                        else
                    217:                                CCOPY_LIST(f2, tp2, l2);
                    218:                } else if (f1 < l1) {
                    219:                        if (iflag)
                    220:                                ICOPY_LIST(f1, tp2, l1);
                    221:                        else
                    222:                                CCOPY_LIST(f1, tp2, l1);
                    223:                }
                    224:                *p1 = l2;
                    225:            }
                    226:            tp2 = list1;        /* swap list1, list2 */
                    227:            list1 = list2;
                    228:            list2 = tp2;
                    229:            last = list2 + nmemb*size;
                    230:        }
                    231:        if (base == list2) {
                    232:                memmove(list2, list1, nmemb*size);
                    233:                list2 = list1;
                    234:        }
                    235:        free(list2);
                    236:        return (0);
                    237: }
                    238: /* }}} */
                    239: 
                    240: #define        swap(a, b) {                                    \
                    241:                s = b;                                  \
                    242:                i = size;                               \
                    243:                do {                                    \
                    244:                        tmp = *a; *a++ = *s; *s++ = tmp; \
                    245:                } while (--i);                          \
                    246:                a -= size;                              \
                    247:        }
                    248: #define reverse(bot, top) {                            \
                    249:        s = top;                                        \
                    250:        do {                                            \
                    251:                i = size;                               \
                    252:                do {                                    \
                    253:                        tmp = *bot; *bot++ = *s; *s++ = tmp; \
                    254:                } while (--i);                          \
                    255:                s -= size2;                             \
                    256:        } while(bot < s);                               \
                    257: }
                    258: 
                    259: /* {{{ setup
                    260:  * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
                    261:  * increasing order, list2 in a corresponding linked list.  Checks for runs
                    262:  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
                    263:  * is defined.  Otherwise simple pairwise merging is used.)
                    264:  */
                    265: 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)
                    266: {
                    267:        int i, length, size2, tmp, sense;
                    268:        u_char *f1, *f2, *s, *l2, *last, *p2;
                    269: 
                    270:        size2 = size*2;
                    271:        if (n <= 5) {
                    272:                insertionsort(list1, n, size, cmp TSRMLS_CC);
                    273:                *EVAL(list2) = (u_char*) list2 + n*size;
                    274:                return;
                    275:        }
                    276:        /*
                    277:         * Avoid running pointers out of bounds; limit n to evens
                    278:         * for simplicity.
                    279:         */
                    280:        i = 4 + (n & 1);
                    281:        insertionsort(list1 + (n - i) * size, i, size, cmp TSRMLS_CC);
                    282:        last = list1 + size * (n - i);
                    283:        *EVAL(list2 + (last - list1)) = list2 + n * size;
                    284: 
                    285: #ifdef NATURAL
                    286:        p2 = list2;
                    287:        f1 = list1;
                    288:        sense = (cmp(f1, f1 + size TSRMLS_CC) > 0);
                    289:        for (; f1 < last; sense = !sense) {
                    290:                length = 2;
                    291:                                        /* Find pairs with same sense. */
                    292:                for (f2 = f1 + size2; f2 < last; f2 += size2) {
                    293:                        if ((cmp(f2, f2+ size TSRMLS_CC) > 0) != sense)
                    294:                                break;
                    295:                        length += 2;
                    296:                }
                    297:                if (length < THRESHOLD) {               /* Pairwise merge */
                    298:                        do {
                    299:                                p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
                    300:                                if (sense > 0)
                    301:                                        swap (f1, f1 + size);
                    302:                        } while ((f1 += size2) < f2);
                    303:                } else {                                /* Natural merge */
                    304:                        l2 = f2;
                    305:                        for (f2 = f1 + size2; f2 < l2; f2 += size2) {
                    306:                                if ((cmp(f2-size, f2 TSRMLS_CC) > 0) != sense) {
                    307:                                        p2 = *EVAL(p2) = f2 - list1 + list2;
                    308:                                        if (sense > 0)
                    309:                                                reverse(f1, f2-size);
                    310:                                        f1 = f2;
                    311:                                }
                    312:                        }
                    313:                        if (sense > 0)
                    314:                                reverse (f1, f2-size);
                    315:                        f1 = f2;
                    316:                        if (f2 < last || cmp(f2 - size, f2 TSRMLS_CC) > 0)
                    317:                                p2 = *EVAL(p2) = f2 - list1 + list2;
                    318:                        else
                    319:                                p2 = *EVAL(p2) = list2 + n*size;
                    320:                }
                    321:        }
                    322: #else          /* pairwise merge only. */
                    323:        for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
                    324:                p2 = *EVAL(p2) = p2 + size2;
                    325:                if (cmp (f1, f1 + size TSRMLS_CC) > 0)
                    326:                        swap(f1, f1 + size);
                    327:        }
                    328: #endif /* NATURAL */
                    329: }
                    330: /* }}} */
                    331: 
                    332: /* {{{ insertionsort
                    333:  * This is to avoid out-of-bounds addresses in sorting the
                    334:  * last 4 elements.
                    335:  */
                    336: static void insertionsort(u_char *a, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC)
                    337: {
                    338:        u_char *ai, *s, *t, *u, tmp;
                    339:        int i;
                    340: 
                    341:        for (ai = a+size; --n >= 1; ai += size)
                    342:                for (t = ai; t > a; t -= size) {
                    343:                        u = t - size;
                    344:                        if (cmp(u, t TSRMLS_CC) <= 0)
                    345:                                break;
                    346:                        swap(u, t);
                    347:                }
                    348: }
                    349: /* }}} */
                    350: 
                    351: /*
                    352:  * Local variables:
                    353:  * tab-width: 4
                    354:  * c-basic-offset: 4
                    355:  * End:
                    356:  * vim600: fdm=marker
                    357:  * vim: noet sw=4 ts=4
                    358:  */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>