|
1 // Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
2 // All rights reserved. |
|
3 // This component and the accompanying materials are made available |
|
4 // under the terms of "Eclipse Public License v1.0" |
|
5 // which accompanies this distribution, and is available |
|
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
7 // |
|
8 // Initial Contributors: |
|
9 // Nokia Corporation - initial contribution. |
|
10 // |
|
11 // Contributors: |
|
12 // |
|
13 // Description: |
|
14 // Map ANSI bsearch and qsort onto EPOC32 functions |
|
15 // |
|
16 // |
|
17 |
|
18 #include <e32std.h> |
|
19 #include <stdlib.h> |
|
20 |
|
21 NONSHARABLE_CLASS(TAnsiKey) : public TKey |
|
22 { |
|
23 public: |
|
24 TAnsiKey(const TAny* key, const TAny* base, TInt length, TInt (*compar)(const TAny*, const TAny*)) |
|
25 : iSearchKey(key), iCmp(compar) |
|
26 { SetPtr(base); iKeyLength=length; } |
|
27 |
|
28 virtual TInt Compare(TInt aLeft,TInt aRight) const; |
|
29 virtual TAny *At(TInt anIndex) const; |
|
30 private: |
|
31 const TAny* iSearchKey; |
|
32 TInt (*iCmp)(const TAny*, const TAny*); |
|
33 }; |
|
34 |
|
35 TInt TAnsiKey::Compare (TInt aLeft,TInt aRight) const |
|
36 { |
|
37 if (aRight==KIndexPtr) |
|
38 return (*iCmp)(At(aLeft),iSearchKey); |
|
39 else |
|
40 return (*iCmp)(At(aLeft),At(aRight)); |
|
41 } |
|
42 |
|
43 TAny* TAnsiKey::At (TInt aPos) const |
|
44 { |
|
45 return (TUint8*)iPtr+(aPos*iKeyLength); |
|
46 } |
|
47 |
|
48 NONSHARABLE_CLASS(TAnsiSwap) : public TSwap |
|
49 { |
|
50 public: |
|
51 TAnsiSwap(const TAny* base, TInt length) : iPtr(base), iLength(length) {} |
|
52 |
|
53 virtual void Swap(TInt aLeft,TInt aRight) const; |
|
54 private: |
|
55 TUint8* At(TInt aPos) const {return (TUint8*)iPtr+(aPos*iLength);} |
|
56 |
|
57 const TAny* iPtr; |
|
58 TInt iLength; |
|
59 }; |
|
60 |
|
61 void TAnsiSwap::Swap(TInt aLeft,TInt aRight) const |
|
62 { |
|
63 TUint8* left=At(aLeft); |
|
64 TUint8* right=At(aRight); |
|
65 TUint8 tmp; |
|
66 |
|
67 for (TInt i=iLength; i>0; i--) |
|
68 { |
|
69 tmp=*left; |
|
70 *left++=*right; |
|
71 *right++=tmp; |
|
72 } |
|
73 } |
|
74 |
|
75 extern "C" { |
|
76 |
|
77 /* |
|
78 FUNCTION |
|
79 <<bsearch>>---binary search |
|
80 |
|
81 INDEX |
|
82 bsearch |
|
83 |
|
84 ANSI_SYNOPSIS |
|
85 #include <stdlib.h> |
|
86 void *bsearch(const void *<[key]>, const void *<[base]>, |
|
87 size_t <[nmemb]>, size_t <[size]>, |
|
88 int (*<[compar]>)(const void *, const void *)); |
|
89 |
|
90 TRAD_SYNOPSIS |
|
91 #include <stdlib.h> |
|
92 char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>) |
|
93 char *<[key]>; |
|
94 char *<[base]>; |
|
95 size_t <[nmemb]>, <[size]>; |
|
96 int (*<[compar]>)(); |
|
97 |
|
98 DESCRIPTION |
|
99 <<bsearch>> searches an array beginning at <[base]> for any element |
|
100 that matches <[key]>, using binary search. <[nmemb]> is the element |
|
101 count of the array; <[size]> is the size of each element. |
|
102 |
|
103 The array must be sorted in ascending order with respect to the |
|
104 comparison function <[compar]> (which you supply as the last argument of |
|
105 <<bsearch>>). |
|
106 |
|
107 You must define the comparison function <<(*<[compar]>)>> to have two |
|
108 arguments; its result must be negative if the first argument is |
|
109 less than the second, zero if the two arguments match, and |
|
110 positive if the first argument is greater than the second (where |
|
111 ``less than'' and ``greater than'' refer to whatever arbitrary |
|
112 ordering is appropriate). |
|
113 |
|
114 RETURNS |
|
115 Returns a pointer to an element of <[array]> that matches <[key]>. If |
|
116 more than one matching element is available, the result may point to |
|
117 any of them. Returns NULL if no matching element is found. |
|
118 |
|
119 PORTABILITY |
|
120 <<bsearch>> is ANSI. |
|
121 |
|
122 No supporting OS subroutines are required. |
|
123 */ |
|
124 |
|
125 /** |
|
126 searches an array beginning at <[base]> for any element |
|
127 that matches <[key]>, using binary search |
|
128 @return a pointer to an element of <[array]> that matches <[key]>. If |
|
129 more than one matching element is available, the result may point to |
|
130 any of them. Returns NULL if no matching element is found. |
|
131 @param key |
|
132 @param base |
|
133 @param nmemb |
|
134 @param size |
|
135 */ |
|
136 EXPORT_C void* bsearch (const void* key, const void* base, size_t nmemb, size_t size, |
|
137 int (*compar)(const void*, const void*)) |
|
138 { |
|
139 TAnsiKey searchMe(key, base, size, compar); |
|
140 TInt result=KIndexPtr; |
|
141 TInt r=User::BinarySearch(nmemb, searchMe, result); |
|
142 if (r==0) |
|
143 return searchMe.At(result); |
|
144 else |
|
145 return NULL; |
|
146 } |
|
147 |
|
148 /* |
|
149 FUNCTION |
|
150 <<qsort>>---sort an array |
|
151 |
|
152 INDEX |
|
153 qsort |
|
154 |
|
155 ANSI_SYNOPSIS |
|
156 #include <stdlib.h> |
|
157 void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, |
|
158 int (*<[compar]>)(const void *, const void *) ); |
|
159 |
|
160 TRAD_SYNOPSIS |
|
161 #include <stdlib.h> |
|
162 qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) |
|
163 char *<[base]>; |
|
164 size_t <[nmemb]>; |
|
165 size_t <[size]>; |
|
166 int (*<[compar]>)(); |
|
167 |
|
168 DESCRIPTION |
|
169 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. |
|
170 <[size]> describes the size of each element of the array. |
|
171 |
|
172 You must supply a pointer to a comparison function, using the argument |
|
173 shown as <[compar]>. (This permits sorting objects of unknown |
|
174 properties.) Define the comparison function to accept two arguments, |
|
175 each a pointer to an element of the array starting at <[base]>. The |
|
176 result of <<(*<[compar]>)>> must be negative if the first argument is |
|
177 less than the second, zero if the two arguments match, and positive if |
|
178 the first argument is greater than the second (where ``less than'' and |
|
179 ``greater than'' refer to whatever arbitrary ordering is appropriate). |
|
180 |
|
181 The array is sorted in place; that is, when <<qsort>> returns, the |
|
182 array elements beginning at <[base]> have been reordered. |
|
183 |
|
184 RETURNS |
|
185 <<qsort>> does not return a result. |
|
186 |
|
187 PORTABILITY |
|
188 <<qsort>> is required by ANSI (without specifying the sorting algorithm). |
|
189 */ |
|
190 |
|
191 /** |
|
192 Sort an array. |
|
193 @param base |
|
194 @param nmemb |
|
195 @param size describes the size of each element of the array |
|
196 */ |
|
197 EXPORT_C void qsort (void* base, size_t nmemb, size_t size, |
|
198 int (*compar)(const void*, const void*)) |
|
199 { |
|
200 TAnsiKey searchMe(NULL, base, size, compar); |
|
201 TAnsiSwap swapUs(base,size); |
|
202 User::QuickSort(nmemb, searchMe, swapUs); |
|
203 return; |
|
204 } |
|
205 |
|
206 } // extern "C" |