text: /*
     +----------------------------------------------------------------------+
     | 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;
  			}
  		}
  	}
  }
  /* }}} */
  