1 /* |
|
2 * Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * Map ANSI bsearch and qsort onto EPOC32 functions |
|
16 */ |
|
17 |
|
18 #include <e32std.h> |
|
19 #include "openc.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 /* |
|
76 FUNCTION |
|
77 <<bsearch>>---binary search |
|
78 |
|
79 INDEX |
|
80 bsearch |
|
81 |
|
82 ANSI_SYNOPSIS |
|
83 #include <stdlib.h> |
|
84 void *bsearch(const void *<[key]>, const void *<[base]>, |
|
85 size_t <[nmemb]>, size_t <[size]>, |
|
86 int (*<[compar]>)(const void *, const void *)); |
|
87 |
|
88 TRAD_SYNOPSIS |
|
89 #include <stdlib.h> |
|
90 char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>) |
|
91 char *<[key]>; |
|
92 char *<[base]>; |
|
93 size_t <[nmemb]>, <[size]>; |
|
94 int (*<[compar]>)(); |
|
95 |
|
96 DESCRIPTION |
|
97 <<bsearch>> searches an array beginning at <[base]> for any element |
|
98 that matches <[key]>, using binary search. <[nmemb]> is the element |
|
99 count of the array; <[size]> is the size of each element. |
|
100 |
|
101 The array must be sorted in ascending order with respect to the |
|
102 comparison function <[compar]> (which you supply as the last argument of |
|
103 <<bsearch>>). |
|
104 |
|
105 You must define the comparison function <<(*<[compar]>)>> to have two |
|
106 arguments; its result must be negative if the first argument is |
|
107 less than the second, zero if the two arguments match, and |
|
108 positive if the first argument is greater than the second (where |
|
109 ``less than'' and ``greater than'' refer to whatever arbitrary |
|
110 ordering is appropriate). |
|
111 |
|
112 RETURNS |
|
113 Returns a pointer to an element of <[array]> that matches <[key]>. If |
|
114 more than one matching element is available, the result may point to |
|
115 any of them. Returns NULL if no matching element is found. |
|
116 |
|
117 PORTABILITY |
|
118 <<bsearch>> is ANSI. |
|
119 |
|
120 No supporting OS subroutines are required. |
|
121 */ |
|
122 |
|
123 /** |
|
124 searches an array beginning at <[base]> for any element |
|
125 that matches <[key]>, using binary search |
|
126 @return a pointer to an element of <[array]> that matches <[key]>. If |
|
127 more than one matching element is available, the result may point to |
|
128 any of them. Returns NULL if no matching element is found. |
|
129 @param key |
|
130 @param base |
|
131 @param nmemb |
|
132 @param size |
|
133 */ |
|
134 void* bsearch (const void* key, const void* base, TUint32 nmemb, TUint32 size, |
|
135 int (*compar)(const void*, const void*)) |
|
136 { |
|
137 TAnsiKey searchMe(key, base, size, compar); |
|
138 TInt result=KIndexPtr; |
|
139 TInt r=User::BinarySearch(nmemb, searchMe, result); |
|
140 if (r==0) |
|
141 return searchMe.At(result); |
|
142 else |
|
143 return NULL; |
|
144 } |
|
145 |
|
146 /* |
|
147 FUNCTION |
|
148 <<qsort>>---sort an array |
|
149 |
|
150 INDEX |
|
151 qsort |
|
152 |
|
153 ANSI_SYNOPSIS |
|
154 #include <stdlib.h> |
|
155 void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, |
|
156 int (*<[compar]>)(const void *, const void *) ); |
|
157 |
|
158 TRAD_SYNOPSIS |
|
159 #include <stdlib.h> |
|
160 qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) |
|
161 char *<[base]>; |
|
162 size_t <[nmemb]>; |
|
163 size_t <[size]>; |
|
164 int (*<[compar]>)(); |
|
165 |
|
166 DESCRIPTION |
|
167 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. |
|
168 <[size]> describes the size of each element of the array. |
|
169 |
|
170 You must supply a pointer to a comparison function, using the argument |
|
171 shown as <[compar]>. (This permits sorting objects of unknown |
|
172 properties.) Define the comparison function to accept two arguments, |
|
173 each a pointer to an element of the array starting at <[base]>. The |
|
174 result of <<(*<[compar]>)>> must be negative if the first argument is |
|
175 less than the second, zero if the two arguments match, and positive if |
|
176 the first argument is greater than the second (where ``less than'' and |
|
177 ``greater than'' refer to whatever arbitrary ordering is appropriate). |
|
178 |
|
179 The array is sorted in place; that is, when <<qsort>> returns, the |
|
180 array elements beginning at <[base]> have been reordered. |
|
181 |
|
182 RETURNS |
|
183 <<qsort>> does not return a result. |
|
184 |
|
185 PORTABILITY |
|
186 <<qsort>> is required by ANSI (without specifying the sorting algorithm). |
|
187 */ |
|
188 |
|
189 /** |
|
190 Sort an array. |
|
191 @param base |
|
192 @param nmemb |
|
193 @param size describes the size of each element of the array |
|
194 */ |
|
195 void qsort (void* base, TUint32 nmemb, TUint32 size, |
|
196 int (*compar)(const void*, const void*)) |
|
197 { |
|
198 TAnsiKey searchMe(NULL, base, size, compar); |
|
199 TAnsiSwap swapUs(base,size); |
|
200 User::QuickSort(nmemb, searchMe, swapUs); |
|
201 return; |
|
202 } |
|
203 |
|