Faster sorting algo

1 files changed, 377 insertions, 0 deletions

diff --git a/Zend/zend_sort.c b/Zend/zend_sort.c
new file mode 100644
index 0000000000..fcd97f46af
--- /dev/null
+++ b/Zend/zend_sort.c
@@ -0,0 +1,377 @@
+/*
+   +----------------------------------------------------------------------+
+   | Zend Engine                                                          |
+   +----------------------------------------------------------------------+
+   | Copyright (c) 1998-2014 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: Sterling Hughes <sterling@php.net>                          |
+   +----------------------------------------------------------------------+
+*/
+
+/* $Id$ */
+
+#include "zend.h"
+#include "zend_sort.h"
+#include <limits.h>
+
+#define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
+
+ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare, swap_func_t swp) /* {{{ */
+{
+	void           *begin_stack[QSORT_STACK_SIZE];
+	void           *end_stack[QSORT_STACK_SIZE];
+	register char  *begin;
+	register char  *end;
+	register char  *seg1;
+	register char  *seg2;
+	register char  *seg2p;
+	register int    loop;
+	uint            offset;
+
+	begin_stack[0] = (char *) base;
+	end_stack[0]   = (char *) base + ((nmemb - 1) * siz);
+
+	for (loop = 0; loop >= 0; --loop) {
+		begin = begin_stack[loop];
+		end   = end_stack[loop];
+
+		while (begin < end) {
+			offset = (end - begin) >> Z_L(1);
+			swp(begin, begin + (offset - (offset % siz)));
+
+			seg1 = begin + siz;
+			seg2 = end;
+
+			while (1) {
+				for (; seg1 < seg2 && compare(begin, seg1) > 0;
+				     seg1 += siz);
+
+				for (; seg2 >= seg1 && compare(seg2, begin) > 0;
+				     seg2 -= siz);
+
+				if (seg1 >= seg2)
+					break;
+
+				swp(seg1, seg2);
+
+				seg1 += siz;
+				seg2 -= siz;
+			}
+
+			swp(begin, seg2);
+
+			seg2p = seg2;
+
+			if ((seg2p - begin) <= (end - seg2p)) {
+				if ((seg2p + siz) < end) {
+					begin_stack[loop] = seg2p + siz;
+					end_stack[loop++] = end;
+				}
+				end = seg2p - siz;
+			}
+			else {
+				if ((seg2p - siz) > begin) {
+					begin_stack[loop] = begin;
+					end_stack[loop++] = seg2p - siz;
+				}
+				begin = seg2p + siz;
+			}
+		}
+	}
+}
+/* }}} */
+
+static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
+	if (cmp(a, b) <= 0) {
+		return;
+	}
+	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(b, c) >= 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, base + siz, cmp, swp);
+			break;
+		case 3:
+			zend_sort_3(base, base + siz, base + siz + siz, cmp, swp);
+			break;
+		case 4:
+			zend_sort_4(base, base + siz, base + siz + siz, base + siz + siz + siz, cmp, swp);
+			break;
+		case 5:
+			zend_sort_5(base, base + siz, base + siz + siz, base + siz + siz + siz, base + (siz * 4), cmp, swp);
+			break;
+		default:
+			{
+				char *i, *j, *k;
+				char *start = (char *)base;
+				char *end = start + (nmemb * 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 -= siz * 2;
+						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(j, i) < 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) {
+			return zend_insert_sort(base, nmemb, siz, cmp, swp);
+		} 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(i, pivot) < 0) {
+					i += siz;
+					if (UNEXPECTED(i == j)) {
+						goto done;
+					}
+				}
+				j -= siz;
+				if (UNEXPECTED(j == i)) {
+					goto done;
+				}
+				while (cmp(pivot, j) < 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;
+			}
+		}
+	}
+}
+/* }}} */
+
+/*
+ * Local Variables:
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ * vim600: fdm=marker
+ * vim: noet sw=4 ts=4
+ */