xref: /PHP-5.5/Zend/zend_qsort.c (revision 73c1be26)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine                                                          |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1998-2015 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 
_zend_qsort_swap(void * a,void * b,size_t siz)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 
zend_qsort_r(void * base,size_t nmemb,size_t siz,compare_r_func_t compare,void * arg TSRMLS_DC)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 
zend_qsort(void * base,size_t nmemb,size_t siz,compare_func_t compare TSRMLS_DC)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  */
134