2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-2013 Facebook, Inc. (http://www.facebook.com) |
6 | Copyright (c) 1998-2010 Zend Technologies Ltd. (http://www.zend.com) |
7 +----------------------------------------------------------------------+
8 | This source file is subject to version 2.00 of the Zend license, |
9 | that is bundled with this package in the file LICENSE, and is |
10 | available through the world-wide-web at the following url: |
11 | http://www.zend.com/license/2_00.txt. |
12 | If you did not receive a copy of the Zend license and are unable to |
13 | obtain it through the world-wide-web, please send a note to |
14 | license@zend.com so we can mail you a copy immediately. |
15 +----------------------------------------------------------------------+
18 #include "hphp/runtime/base/zend-qsort.h"
21 ///////////////////////////////////////////////////////////////////////////////
23 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
25 void _zend_qsort_swap(void *a
, void *b
, size_t siz
) {
26 register char *tmp_a_char
;
27 register char *tmp_b_char
;
28 register int *tmp_a_int
;
29 register int *tmp_b_int
;
34 tmp_a_int
= (int *) a
;
35 tmp_b_int
= (int *) b
;
37 for (i
= sizeof(int); i
<= siz
; i
+= sizeof(int)) {
39 *tmp_a_int
++ = *tmp_b_int
;
43 tmp_a_char
= (char *) tmp_a_int
;
44 tmp_b_char
= (char *) tmp_b_int
;
46 for (i
= i
- sizeof(int) + 1; i
<= siz
; ++i
) {
48 *tmp_a_char
++ = *tmp_b_char
;
53 void zend_qsort(void *base
, size_t nmemb
, size_t siz
,
54 compare_func_t compare
, void *opaque
) {
55 void *begin_stack
[QSORT_STACK_SIZE
];
56 void *end_stack
[QSORT_STACK_SIZE
];
65 begin_stack
[0] = (char *) base
;
66 end_stack
[0] = (char *) base
+ ((nmemb
- 1) * siz
);
68 for (loop
= 0; loop
>= 0; --loop
) {
69 begin
= (char*)begin_stack
[loop
];
70 end
= (char*)end_stack
[loop
];
73 offset
= (end
- begin
) >> 1;
74 _zend_qsort_swap(begin
, begin
+ (offset
- (offset
% siz
)), siz
);
80 for (; seg1
< seg2
&& compare(begin
, seg1
, opaque
) > 0;
83 for (; seg2
>= seg1
&& compare(seg2
, begin
, opaque
) > 0;
89 _zend_qsort_swap(seg1
, seg2
, siz
);
95 _zend_qsort_swap(begin
, seg2
, siz
);
99 if ((seg2p
- begin
) <= (end
- seg2p
)) {
100 if ((seg2p
+ siz
) < end
) {
101 begin_stack
[loop
] = seg2p
+ siz
;
102 end_stack
[loop
++] = end
;
107 if ((seg2p
- siz
) > begin
) {
108 begin_stack
[loop
] = begin
;
109 end_stack
[loop
++] = seg2p
- siz
;
117 ///////////////////////////////////////////////////////////////////////////////