Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 107 lines (87 sloc) 3.045 kB
3bdddb4 MFZE1
Sebastian Bergmann authored
1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2001 Zend Technologies Ltd. (http://www.zend.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 0.92 of the Zend license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available at through the world-wide-web at |
10 | http://www.zend.com/license/0_92.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 #include "zend.h"
20
21 #include <limits.h>
22
23 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
24
25 static void _zend_qsort_swap(void *a, void *b, size_t siz)
26 {
27 register size_t i;
28 register int t_i;
29 register char t_c;
30
31 for (i = sizeof(int); i <= siz; i += sizeof(int)) {
32 t_i = *(int *) a;
33 *((int *) a)++ = *(int *) b;
34 *((int *) b)++ = t_i;
35 }
36
37 for (i = i - sizeof(int) + 1; i <= siz; ++i) {
38 t_c = *(char *) a;
39 *((char *) a)++ = *(char *) b;
40 *((char *) b)++ = t_c;
41 }
42 }
43
44 ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
45 {
46 void *begin_stack[QSORT_STACK_SIZE];
47 void *end_stack[QSORT_STACK_SIZE];
48 register char *begin;
49 register char *end;
50 register char *seg1;
51 register char *seg2;
52 register char *seg2p;
53 register int loop;
54 uint offset;
55
56 begin_stack[0] = (char *) base;
57 end_stack[0] = (char *) base + ((nmemb - 1) * siz);
58
59 for (loop = 0; loop >= 0; --loop) {
60 begin = begin_stack[loop];
61 end = end_stack[loop];
62
63 while (begin < end) {
64 offset = (end - begin) >> 1;
65 _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
66
67 seg1 = begin + siz;
68 seg2 = end;
69
70 while (1) {
71 for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
72 seg1 += siz);
73
74 for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
75 seg2 -= siz);
76
77 if (seg1 >= seg2)
78 break;
79
80 _zend_qsort_swap(seg1, seg2, siz);
81
82 seg1 += siz;
83 seg2 -= siz;
84 }
85
86 _zend_qsort_swap(begin, seg2, siz);
87
88 seg2p = seg2;
89
90 if ((seg2p - begin) <= (end - seg2p)) {
91 if ((seg2p + siz) < end) {
92 begin_stack[loop] = seg2p + siz;
93 end_stack[loop++] = end;
94 }
95 end = seg2p - siz;
96 }
97 else {
98 if ((seg2p - siz) > begin) {
99 begin_stack[loop] = begin;
100 end_stack[loop++] = seg2p - siz;
101 }
102 begin = seg2p + siz;
103 }
104 }
105 }
106 }
Something went wrong with that request. Please try again.