1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2013 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
23 #include <limits.h>
24
25 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
26
_zend_qsort_swap(void * a,void * b,size_t siz)27 static void _zend_qsort_swap(void *a, void *b, size_t siz)
28 {
29 register char *tmp_a_char;
30 register char *tmp_b_char;
31 register int *tmp_a_int;
32 register int *tmp_b_int;
33 register size_t i;
34 int t_i;
35 char t_c;
36
37 tmp_a_int = (int *) a;
38 tmp_b_int = (int *) b;
39
40 for (i = sizeof(int); i <= siz; i += sizeof(int)) {
41 t_i = *tmp_a_int;
42 *tmp_a_int++ = *tmp_b_int;
43 *tmp_b_int++ = t_i;
44 }
45
46 tmp_a_char = (char *) tmp_a_int;
47 tmp_b_char = (char *) tmp_b_int;
48
49 for (i = i - sizeof(int) + 1; i <= siz; ++i) {
50 t_c = *tmp_a_char;
51 *tmp_a_char++ = *tmp_b_char;
52 *tmp_b_char++ = t_c;
53 }
54 }
55
zend_qsort(void * base,size_t nmemb,size_t siz,compare_func_t compare TSRMLS_DC)56 ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
57 {
58 void *begin_stack[QSORT_STACK_SIZE];
59 void *end_stack[QSORT_STACK_SIZE];
60 register char *begin;
61 register char *end;
62 register char *seg1;
63 register char *seg2;
64 register char *seg2p;
65 register int loop;
66 uint offset;
67
68 begin_stack[0] = (char *) base;
69 end_stack[0] = (char *) base + ((nmemb - 1) * siz);
70
71 for (loop = 0; loop >= 0; --loop) {
72 begin = begin_stack[loop];
73 end = end_stack[loop];
74
75 while (begin < end) {
76 offset = (end - begin) >> 1;
77 _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
78
79 seg1 = begin + siz;
80 seg2 = end;
81
82 while (1) {
83 for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
84 seg1 += siz);
85
86 for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
87 seg2 -= siz);
88
89 if (seg1 >= seg2)
90 break;
91
92 _zend_qsort_swap(seg1, seg2, siz);
93
94 seg1 += siz;
95 seg2 -= siz;
96 }
97
98 _zend_qsort_swap(begin, seg2, siz);
99
100 seg2p = seg2;
101
102 if ((seg2p - begin) <= (end - seg2p)) {
103 if ((seg2p + siz) < end) {
104 begin_stack[loop] = seg2p + siz;
105 end_stack[loop++] = end;
106 }
107 end = seg2p - siz;
108 }
109 else {
110 if ((seg2p - siz) > begin) {
111 begin_stack[loop] = begin;
112 end_stack[loop++] = seg2p - siz;
113 }
114 begin = seg2p + siz;
115 }
116 }
117 }
118 }
119
120 /*
121 * Local Variables:
122 * c-basic-offset: 4
123 * tab-width: 4
124 * End:
125 * vim600: fdm=marker
126 * vim: noet sw=4 ts=4
127 */
128
