zend_sort.c

Go to the documentation of this file.

/*
   +----------------------------------------------------------------------+
   | Zend Engine                                                          |
   +----------------------------------------------------------------------+
   | Copyright (c) Zend Technologies Ltd. (http://www.zend.com)           |
   +----------------------------------------------------------------------+
   | This source file is subject to version 2.00 of the Zend license,     |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | http://www.zend.com/license/2_00.txt.                                |
   | If you did not receive a copy of the Zend license and are unable to  |
   | obtain it through the world-wide-web, please send a note to          |
   | license@zend.com so we can mail you a copy immediately.              |
   +----------------------------------------------------------------------+
   | Authors: Xinchen Hui <laruence@php.net>                              |
   |          Sterling Hughes <sterling@php.net>                          |
   +----------------------------------------------------------------------+
*/
 
#include "zend.h"
#include "zend_sort.h"
#include <limits.h>
 
static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
    if (cmp(a, b) > 0) {
        swp(a, b);
    }
}
/* }}} */
 
static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
    if (!(cmp(a, b) > 0)) {
        if (!(cmp(b, c) > 0)) {
            return;
        }
        swp(b, c);
        if (cmp(a, b) > 0) {
            swp(a, b);
        }
        return;
    }
    if (!(cmp(c, b) > 0)) {
        swp(a, c);
        return;
    }
    swp(a, b);
    if (cmp(b, c) > 0) {
        swp(b, c);
    }
}
/* }}} */
 
static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
    zend_sort_3(a, b, c, cmp, swp);
    if (cmp(c, d) > 0) {
        swp(c, d);
        if (cmp(b, c) > 0) {
            swp(b, c);
            if (cmp(a, b) > 0) {
                swp(a, b);
            }
        }
    }
}
/* }}} */
 
static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
    zend_sort_4(a, b, c, d, cmp, swp);
    if (cmp(d, e) > 0) {
        swp(d, e);
        if (cmp(c, d) > 0) {
            swp(c, d);
            if (cmp(b, c) > 0) {
                swp(b, c);
                if (cmp(a, b) > 0) {
                    swp(a, b);
                }
            }
        }
    }
}
/* }}} */
 
ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{
    switch (nmemb) {
        case 0:
        case 1:
            break;
        case 2:
            zend_sort_2(base, (char *)base + siz, cmp, swp);
            break;
        case 3:
            zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp);
            break;
        case 4:
            {
                size_t siz2 = siz + siz;
                zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp);
            }
            break;
        case 5:
            {
                size_t siz2 = siz + siz;
                zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp);
            }
            break;
        default:
            {
                char *i, *j, *k;
                char *start = (char *)base;
                char *end = start + (nmemb * siz);
                size_t siz2= siz + siz;
                char *sentry = start + (6 * siz);
                for (i = start + siz; i < sentry; i += siz) {
                    j = i - siz;
                    if (!(cmp(j, i) > 0)) {
                        continue;
                    }
                    while (j != start) {
                        j -= siz;
                        if (!(cmp(j, i) > 0)) {
                            j += siz;
                            break;
                        }
                    }
                    for (k = i; k > j; k -= siz) {
                        swp(k, k - siz);
                    }
                }
                for (i = sentry; i < end; i += siz) {
                    j = i - siz;
                    if (!(cmp(j, i) > 0)) {
                        continue;
                    }
                    do {
                        j -= siz2;
                        if (!(cmp(j, i) > 0)) {
                            j += siz;
                            if (!(cmp(j, i) > 0)) {
                                j += siz;
                            }
                            break;
                        }
                        if (j == start) {
                            break;
                        }
                        if (j == start + siz) {
                            j -= siz;
                            if (cmp(i, j) > 0) {
                                j += siz;
                            }
                            break;
                        }
                    } while (1);
                    for (k = i; k > j; k -= siz) {
                        swp(k, k - siz);
                    }
                }
            }
            break;
    }
}
/* }}} */
 
/* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
 *
 * Derived from LLVM's libc++ implementation of std::sort.
 *
 * ===========================================================================
 * libc++ License
 * ===========================================================================
 *
 * The libc++ library is dual licensed under both the University of Illinois
 * "BSD-Like" license and the MIT license. As a user of this code you may
 * choose to use it under either license. As a contributor, you agree to allow
 * your code to be used under both.
 *
 * Full text of the relevant licenses is included below.
 *
 * ===========================================================================
 *
 * University of Illinois/NCSA
 * Open Source License
 *
 * Copyright (c) 2009-2012 by the contributors listed at
 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
 *
 * All rights reserved.
 *
 * Developed by:
 *
 *     LLVM Team
 *
 *     University of Illinois at Urbana-Champaign
 *
 *     http://llvm.org
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal with the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimers.
 *
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimers in the
 *       documentation and/or other materials provided with the distribution.
 *
 *     * Neither the names of the LLVM Team, University of Illinois at
 *       Urbana-Champaign, nor the names of its contributors may be used to
 *       endorse or promote products derived from this Software without
 *       specific prior written permission.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * WITH THE SOFTWARE.
 *
 * ===========================================================================
 *
 * Copyright (c) 2009-2012 by the contributors listed at
 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */
ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
{
    while (1) {
        if (nmemb <= 16) {
            zend_insert_sort(base, nmemb, siz, cmp, swp);
            return;
        } else {
            char *i, *j;
            char *start = (char *)base;
            char *end = start + (nmemb * siz);
            size_t offset = (nmemb >> Z_L(1));
            char *pivot = start + (offset * siz);
 
            if ((nmemb >> Z_L(10))) {
                size_t delta = (offset >> Z_L(1)) * siz;
                zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);
            } else {
                zend_sort_3(start, pivot, end - siz, cmp, swp);
            }
            swp(start + siz, pivot);
            pivot = start + siz;
            i = pivot + siz;
            j = end - siz;
            while (1) {
                while (cmp(pivot, i) > 0) {
                    i += siz;
                    if (UNEXPECTED(i == j)) {
                        goto done;
                    }
                }
                j -= siz;
                if (UNEXPECTED(j == i)) {
                    goto done;
                }
                while (cmp(j, pivot) > 0) {
                    j -= siz;
                    if (UNEXPECTED(j == i)) {
                        goto done;
                    }
                }
                swp(i, j);
                i += siz;
                if (UNEXPECTED(i == j)) {
                    goto done;
                }
            }
done:
            swp(pivot, i - siz);
            if ((i - siz) - start < end - i) {
                zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);
                base = i;
                nmemb = (end - i)/siz;
            } else {
                zend_sort(i, (end - i)/siz, siz, cmp, swp);
                nmemb = (i - start)/siz - 1;
            }
        }
    }
}
/* }}} */