1 /******************************************************************************
2 *
3 * Copyright (C) 2006, The Gentee Group. All rights reserved.
4 * This file is part of the Gentee open source project <http://www.gentee.com>.
5 *
6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT").
7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS
8 * ACCEPTANCE OF THE AGREEMENT.
9 *
10 * qsort 20.04.2007 0.0.A.
11 *
12 * Author:
13 *
14 ******************************************************************************/
15
16 #include "../common/memory.h"
17 #include "../vm/vmrun.h"
18 #include "qsort.h"
19
20 //typedef void ( STDCALL* swapfunc)( pvoid, pvoid, uint );
21
22 //--------------------------------------------------------------------------
23
24 void STDCALL quicksort( pvoid base, uint count,
25 uint width, cmpfunc func, uint param )
26 {
27 pubyte low;
28 pubyte high;
29 pubyte middle;
30 pubyte lowguy;
31 pubyte highguy;
32 int size;
33 pubyte lowstk[30];
34 pubyte highstk[30];
35 int stkptr;
36 // swapfunc swap = ( swapfunc )( width & 3 ? mem_swap : mem_swapdw );
37
38 if ( count < 2 || width == 0 )
39 return;
40
41 stkptr = 0;
42
43 low = base;
44 high = ( pubyte )base + width * ( count-1 );
45
46 recurse:
47
48 size = ( high - low ) / width + 1;
49
50 middle = low + ( size / 2 ) * width;
51 mem_swap( middle, low, width);
52
53 lowguy = low;
54 highguy = high + width;
55
56 for (;;)
57 {
58 do {
59 lowguy += width;
60 } while (lowguy <= high && func(lowguy, low, param) < 0);
61
62 do {
63 highguy -= width;
64 } while (highguy > low && func(highguy, low, param) > 0);
65
66 if ( highguy < lowguy )
67 break;
68
69 mem_swap( lowguy, highguy, width );
70 }
71
72 mem_swap( low, highguy, width );
73
74 if ( highguy - 1 - low >= high - lowguy )
75 {
76 if (low + width < highguy)
77 {
78 lowstk[stkptr] = low;
79 highstk[stkptr] = highguy - width;
80 ++stkptr;
81 }
82
83 if (lowguy < high)
84 {
85 low = lowguy;
86 goto recurse;
87 }
88 }
89 else
90 {
91 if (lowguy < high) {
92 lowstk[stkptr] = lowguy;
93 highstk[stkptr] = high;
94 ++stkptr;
95 }
96
97 if (low + width < highguy) {
98 high = highguy - width;
99 goto recurse;
100 }
101 }
102
103 --stkptr;
104 if ( stkptr >= 0 )
105 {
106 low = lowstk[stkptr];
107 high = highstk[stkptr];
108 goto recurse;
109 }
110 else
111 return;
112 }
113 #ifndef NOGENTEE
114 //--------------------------------------------------------------------------
115
116 int STDCALL cmpvm( pvoid left, pvoid right, uint idfunc )
117 {
118 return vm_runtwo( idfunc, ( uint )left, ( uint )right );
119 }
120
121 //--------------------------------------------------------------------------
122
123 void STDCALL sort( pvoid base, uint count, uint size, uint idfunc )
124 {
125 quicksort( base, count, size, cmpvm, idfunc );
126 // quicksort( base, count, size, cmpstr, 0 );
127 // qsort( base, count, 16, cmpstrc );
128
129 }
130
131 //--------------------------------------------------------------------------
132
133 int CALLBACK cmpsortstr( pvoid left, pvoid right, uint idfunc )
134 {
135 return os_strcmp( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
136 }
137
138 //--------------------------------------------------------------------------
139
140 int CALLBACK cmpsortstri( pvoid left, pvoid right, uint idfunc )
141 {
142 return os_strcmpign( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
143 }
144
145 //--------------------------------------------------------------------------
146
147 int CALLBACK cmpsortustr( pvoid left, pvoid right, uint idfunc )
148 {
149 return os_ustrcmp( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
150 }
151
152 //--------------------------------------------------------------------------
153
154 int CALLBACK cmpsortustri( pvoid left, pvoid right, uint idfunc )
155 {
156 return os_ustrcmpign( ( pvoid )*( puint )left, ( pvoid )*( puint )right );
157 }
158 //--------------------------------------------------------------------------
159
160 int CALLBACK cmpsortuint( pvoid left, pvoid right, uint idfunc )
161 {
162 uint lval = *( puint )left;
163 uint rval = *( puint )right;
164
165 return lval < rval ? -1 : ( lval > rval ? 1 : 0 );
166 }
167
168 //--------------------------------------------------------------------------
169
170 void STDCALL fastsort( pvoid base, uint count, uint size, uint mode )
171 {
172 cmpfunc func;
173
174 switch ( mode ) {
175 case FS_STR:
176 func = cmpsortstr;
177 break;
178 case FS_STRIGNORE:
179 func = cmpsortstri;
180 break;
181 case FS_UINT:
182 func = cmpsortuint;
183 break;
184 case FS_USTR:
185 func = cmpsortustr;
186 break;
187 case FS_USTRIGNORE:
188 func = cmpsortustri;
189 break;
190 }
191 quicksort( base, count, size, func, 0 );
192 }
193 #endif
194 //--------------------------------------------------------------------------
195