|
1 /* |
|
2 * Copyright (c) 2001-2006 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 the License "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: EAP and WLAN authentication protocols. |
|
15 * |
|
16 */ |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 #if !defined(_EAP_SORT_H_) |
|
22 #define _EAP_SORT_H_ |
|
23 |
|
24 #include "eap_am_memory.h" |
|
25 #include "eap_tools.h" |
|
26 #include "eap_am_tools.h" |
|
27 #include "eap_automatic_variable.h" |
|
28 |
|
29 /** @file */ |
|
30 |
|
31 //-------------------------------------------------- |
|
32 |
|
33 /** |
|
34 * This template function copies array of objects from first to last |
|
35 * to array of objects ending to result. |
|
36 * Parameter first point to the first object of the source array. |
|
37 * Parameter last points the next address after the last object of source array. |
|
38 * Parameter result points the next address after the last object of the result array. |
|
39 */ |
|
40 template <class Type> |
|
41 void eap_sort_copy_backward( |
|
42 const Type * const first, |
|
43 const Type *last, |
|
44 Type *result ) |
|
45 { |
|
46 while (first != last) |
|
47 { |
|
48 *--result = *--last; |
|
49 } |
|
50 } |
|
51 |
|
52 //-------------------------------------------------- |
|
53 |
|
54 /** |
|
55 * |
|
56 */ |
|
57 template <class Type> |
|
58 void eap_sort_unguarded_linear_insert( |
|
59 Type *last, |
|
60 const Type inserted_object, |
|
61 bool (*compare_first_is_smaller)( |
|
62 const Type * const first, |
|
63 const Type * const second, |
|
64 abs_eap_am_tools_c * const m_am_tools), |
|
65 abs_eap_am_tools_c * const m_am_tools) |
|
66 { |
|
67 Type *next = last; |
|
68 |
|
69 --next; |
|
70 |
|
71 while(compare_first_is_smaller(&inserted_object, next, m_am_tools) == true) |
|
72 { |
|
73 *last = *next; |
|
74 last = next--; |
|
75 } |
|
76 |
|
77 *last = inserted_object; |
|
78 } |
|
79 |
|
80 //-------------------------------------------------- |
|
81 |
|
82 template <class Type> |
|
83 void eap_sort_linear_insert( |
|
84 Type * const first, |
|
85 Type * const last, |
|
86 bool (*compare_first_is_smaller)( |
|
87 const Type * const first, |
|
88 const Type * const second, |
|
89 abs_eap_am_tools_c * const m_am_tools), |
|
90 abs_eap_am_tools_c * const m_am_tools) |
|
91 { |
|
92 const Type value = *last; |
|
93 |
|
94 if(compare_first_is_smaller(&value, first, m_am_tools) == true) |
|
95 { |
|
96 eap_sort_copy_backward(first, last, last+1); |
|
97 *first = value; |
|
98 } |
|
99 else |
|
100 { |
|
101 eap_sort_unguarded_linear_insert(last, value, compare_first_is_smaller, m_am_tools); |
|
102 } |
|
103 } |
|
104 |
|
105 //-------------------------------------------------- |
|
106 |
|
107 template <class Type> |
|
108 void eap_sort_insert_sort_area( |
|
109 Type * const first, |
|
110 const Type *last, |
|
111 bool (*compare_first_is_smaller)( |
|
112 const Type * const first, |
|
113 const Type * const second, |
|
114 abs_eap_am_tools_c * const m_am_tools), |
|
115 abs_eap_am_tools_c * const m_am_tools) |
|
116 { |
|
117 Type *tmp; |
|
118 |
|
119 ++last; |
|
120 |
|
121 for( tmp = first+1; tmp < last; tmp++ ) |
|
122 { |
|
123 eap_sort_linear_insert( first, tmp, compare_first_is_smaller, m_am_tools); |
|
124 } |
|
125 } |
|
126 |
|
127 //------------------------------------------------------------ |
|
128 |
|
129 |
|
130 template <class Type> |
|
131 Type *eap_sort_divide_area( |
|
132 Type *start, |
|
133 Type *finish, |
|
134 bool (*compare_first_is_smaller)( |
|
135 const Type * const first, |
|
136 const Type * const second, |
|
137 abs_eap_am_tools_c * const m_am_tools), |
|
138 abs_eap_am_tools_c * const m_am_tools) |
|
139 { |
|
140 // selects the boundary object. |
|
141 const Type boundary = *(start+((finish - start)/2)); |
|
142 Type change; |
|
143 |
|
144 start--; |
|
145 finish++; |
|
146 |
|
147 // Boundary is used as a middle object. |
|
148 for(;;) |
|
149 { |
|
150 // Examine from begin to end is ++start smaller than boundary. |
|
151 while(compare_first_is_smaller(++start, &boundary, m_am_tools) == true) |
|
152 { |
|
153 // Nothing to do. |
|
154 } |
|
155 |
|
156 // Examine from end to begin is --finish bigger than boundary. |
|
157 while(compare_first_is_smaller(&boundary, --finish, m_am_tools) == true) |
|
158 { |
|
159 // Nothing to do. |
|
160 } |
|
161 |
|
162 |
|
163 if( start < finish ) |
|
164 { |
|
165 // In case boundary isn't reached, it intent that two |
|
166 // atom mutual side of boundary are in wrong order, |
|
167 // so swap them. |
|
168 change = *start; |
|
169 *start = *finish; |
|
170 *finish = change; |
|
171 } |
|
172 else |
|
173 { |
|
174 // Start and finish pointers are overlapping. |
|
175 // Terminate loop and return pointer to finish. |
|
176 return( finish ); |
|
177 } |
|
178 } // for() |
|
179 |
|
180 } |
|
181 |
|
182 //-------------------------------------------------- |
|
183 |
|
184 /** |
|
185 * This function does quick-sort with non-recurvive alorithm. |
|
186 * Parameter array is pointer to array including objects of type Type. |
|
187 * Parameter object_count is count of objects in the array. |
|
188 * Parameter compare_first_is_smaller is pointer to a function that compares objects of type Type. |
|
189 */ |
|
190 template <class Type> |
|
191 eap_status_e eap_sort_array( |
|
192 Type * const array, |
|
193 const u32_t object_count, |
|
194 bool (*compare_first_is_smaller)( |
|
195 const Type * const first, |
|
196 const Type * const second, |
|
197 abs_eap_am_tools_c * const m_am_tools), |
|
198 abs_eap_am_tools_c * const m_am_tools) |
|
199 { |
|
200 EAP_TRACE_BEGIN(m_am_tools, TRACE_FLAGS_DEFAULT); |
|
201 |
|
202 eap_status_e status = eap_status_ok; // Note original_array may be empty or it includes only one object, then sort will not be run. |
|
203 |
|
204 if (object_count < 2ul) |
|
205 { |
|
206 EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT); |
|
207 return EAP_STATUS_RETURN(m_am_tools, status); |
|
208 } |
|
209 |
|
210 const u32_t quicksort_finish = 10ul; |
|
211 |
|
212 // When there are atoms in the array fewer than quicksort_finish, |
|
213 // then the array is sorted directly by eap_sort_insert_sort_area() function. |
|
214 if (object_count >= quicksort_finish) |
|
215 { |
|
216 Type ** const sort_array = new Type *[object_count+1]; |
|
217 eap_automatic_array_variable_c<Type *> automatic_sort_array(m_am_tools, sort_array); |
|
218 if (sort_array == 0) |
|
219 { |
|
220 EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT); |
|
221 return EAP_STATUS_RETURN(m_am_tools, eap_status_allocation_error); |
|
222 } |
|
223 |
|
224 // first atom |
|
225 Type *start = array; |
|
226 // last point to the first address after the last atom. |
|
227 Type *last = array+object_count; |
|
228 Type *finish = last - 1; |
|
229 sort_array[finish-array] = finish; |
|
230 |
|
231 // We continue until start come real array's end. |
|
232 while (last != start) |
|
233 { |
|
234 if (static_cast<u32_t>(finish - start) > quicksort_finish) |
|
235 { |
|
236 Type *upper = eap_sort_divide_area(start, finish , compare_first_is_smaller, m_am_tools); |
|
237 |
|
238 // When is at least two unit in beginning. |
|
239 // Divide sorting area under upper address. |
|
240 // Upper areas end points are saved to sort_array. |
|
241 sort_array[upper+1-array] = finish; |
|
242 |
|
243 // New sorting area. |
|
244 // New start address is the same as start pointer of previous sort area. |
|
245 // New finish address is preceding address of upper address. |
|
246 finish = upper; |
|
247 } |
|
248 else |
|
249 { |
|
250 eap_sort_insert_sort_area(start, finish , compare_first_is_smaller, m_am_tools); |
|
251 |
|
252 start = ++finish; |
|
253 finish = sort_array[start-array]; |
|
254 } |
|
255 } // while ( last != start ) |
|
256 } |
|
257 else |
|
258 { |
|
259 eap_sort_insert_sort_area(array, array+(object_count-1), compare_first_is_smaller, m_am_tools); |
|
260 } |
|
261 |
|
262 EAP_TRACE_END(m_am_tools, TRACE_FLAGS_DEFAULT); |
|
263 return EAP_STATUS_RETURN(m_am_tools, status); |
|
264 } |
|
265 |
|
266 //-------------------------------------------------- |
|
267 |
|
268 #endif //#if !defined(_EAP_SORT_H_) |
|
269 |
|
270 |
|
271 //-------------------------------------------------- |
|
272 |
|
273 |
|
274 |
|
275 // End. |