1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2016 Zend Technologies Ltd. (http://www.zend.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 2.00 of the Zend license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.zend.com/license/2_00.txt. |
11 | If you did not receive a copy of the Zend license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@zend.com so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Sterling Hughes <sterling@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 /* $Id$ */
20
21 #include "zend.h"
22 #include "zend_qsort.h"
23
24 #include <limits.h>
25
26 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
27
28 static void _zend_qsort_swap(void *a, void *b, size_t siz)
29 {
30 register char *tmp_a_char;
31 register char *tmp_b_char;
32 register int *tmp_a_int;
33 register int *tmp_b_int;
34 register size_t i;
35 int t_i;
36 char t_c;
37
38 tmp_a_int = (int *) a;
39 tmp_b_int = (int *) b;
40
41 for (i = sizeof(int); i <= siz; i += sizeof(int)) {
42 t_i = *tmp_a_int;
43 *tmp_a_int++ = *tmp_b_int;
44 *tmp_b_int++ = t_i;
45 }
46
47 tmp_a_char = (char *) tmp_a_int;
48 tmp_b_char = (char *) tmp_b_int;
49
50 for (i = i - sizeof(int) + 1; i <= siz; ++i) {
51 t_c = *tmp_a_char;
52 *tmp_a_char++ = *tmp_b_char;
53 *tmp_b_char++ = t_c;
54 }
55 }
56
57 ZEND_API void zend_qsort_r(void *base, size_t nmemb, size_t siz, compare_r_func_t compare, void *arg TSRMLS_DC)
58 {
59 void *begin_stack[QSORT_STACK_SIZE];
60 void *end_stack[QSORT_STACK_SIZE];
61 register char *begin;
62 register char *end;
63 register char *seg1;
64 register char *seg2;
65 register char *seg2p;
66 register int loop;
67 uint offset;
68
69 begin_stack[0] = (char *) base;
70 end_stack[0] = (char *) base + ((nmemb - 1) * siz);
71
72 for (loop = 0; loop >= 0; --loop) {
73 begin = begin_stack[loop];
74 end = end_stack[loop];
75
76 while (begin < end) {
77 offset = (end - begin) >> 1;
78 _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
79
80 seg1 = begin + siz;
81 seg2 = end;
82
83 while (1) {
84 for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC, arg) > 0;
85 seg1 += siz);
86
87 for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC, arg) > 0;
88 seg2 -= siz);
89
90 if (seg1 >= seg2)
91 break;
92
93 _zend_qsort_swap(seg1, seg2, siz);
94
95 seg1 += siz;
96 seg2 -= siz;
97 }
98
99 _zend_qsort_swap(begin, seg2, siz);
100
101 seg2p = seg2;
102
103 if ((seg2p - begin) <= (end - seg2p)) {
104 if ((seg2p + siz) < end) {
105 begin_stack[loop] = seg2p + siz;
106 end_stack[loop++] = end;
107 }
108 end = seg2p - siz;
109 }
110 else {
111 if ((seg2p - siz) > begin) {
112 begin_stack[loop] = begin;
113 end_stack[loop++] = seg2p - siz;
114 }
115 begin = seg2p + siz;
116 }
117 }
118 }
119 }
120
121 ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
122 {
123 zend_qsort_r(base, nmemb, siz, (compare_r_func_t)compare, NULL TSRMLS_CC);
124 }
125
126 /*
127 * Local Variables:
128 * c-basic-offset: 4
129 * tab-width: 4
130 * End:
131 * vim600: fdm=marker
132 * vim: noet sw=4 ts=4
133 */