ReactOS 0.4.15-dev-7906-g1b85a5f
_algobase.c
Go to the documentation of this file.
1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
23 *
24 */
25#ifndef _STLP_ALGOBASE_C
26#define _STLP_ALGOBASE_C
27
28#ifndef _STLP_INTERNAL_ALGOBASE_H
29# include <stl/_algobase.h>
30#endif
31
32#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
33# include <stl/_function_base.h>
34#endif
35
37
38template <class _InputIter1, class _InputIter2>
39bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
40 _InputIter2 __first2, _InputIter2 __last2) {
41 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
42 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
43 for ( ; __first1 != __last1 && __first2 != __last2
44 ; ++__first1, ++__first2) {
45 if (*__first1 < *__first2) {
46 _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
47 return true;
48 }
49 if (*__first2 < *__first1)
50 return false;
51 }
52 return __first1 == __last1 && __first2 != __last2;
53}
54
55template <class _InputIter1, class _InputIter2, class _Compare>
56bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
57 _InputIter2 __first2, _InputIter2 __last2,
58 _Compare __comp) {
59 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
60 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
61 for ( ; __first1 != __last1 && __first2 != __last2
62 ; ++__first1, ++__first2) {
63 if (__comp(*__first1, *__first2)) {
64 _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1),
65 _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
66 return true;
67 }
68 if (__comp(*__first2, *__first1))
69 return false;
70 }
71 return __first1 == __last1 && __first2 != __last2;
72}
73
74#if !defined (_STLP_NO_EXTENSIONS)
76
77template <class _InputIter1, class _InputIter2>
78int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
79 _InputIter2 __first2, _InputIter2 __last2) {
80 while (__first1 != __last1 && __first2 != __last2) {
81 if (*__first1 < *__first2) {
82 _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
83 return -1;
84 }
85 if (*__first2 < *__first1)
86 return 1;
87 ++__first1;
88 ++__first2;
89 }
90 if (__first2 == __last2) {
91 return !(__first1 == __last1);
92 }
93 else {
94 return -1;
95 }
96}
97
99
100template <class _InputIter1, class _InputIter2>
101int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
102 _InputIter2 __first2, _InputIter2 __last2) {
103 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
104 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
105 return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
106}
107#endif
108
110
111template <class _RandomAccessIter, class _Tp>
112_STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
113 const _Tp& __val,
115 _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
116
117 for ( ; __trip_count > 0 ; --__trip_count) {
118 if (*__first == __val) return __first;
119 ++__first;
120
121 if (*__first == __val) return __first;
122 ++__first;
123
124 if (*__first == __val) return __first;
125 ++__first;
126
127 if (*__first == __val) return __first;
128 ++__first;
129 }
130
131 switch (__last - __first) {
132 case 3:
133 if (*__first == __val) return __first;
134 ++__first;
135 case 2:
136 if (*__first == __val) return __first;
137 ++__first;
138 case 1:
139 if (*__first == __val) return __first;
140 //++__first;
141 case 0:
142 default:
143 return __last;
144 }
145}
146
147inline char*
148__find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
149 void *res = memchr(__first, __val, __last - __first);
150 return res != 0 ? __STATIC_CAST(char*, res) : __last;
151}
152inline const char*
153__find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
154 const void *res = memchr(__first, __val, __last - __first);
155 return res != 0 ? __STATIC_CAST(const char*, res) : __last;
156}
157
158template <class _RandomAccessIter, class _Predicate>
159_STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
160 _Predicate __pred,
162 _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
163
164 for ( ; __trip_count > 0 ; --__trip_count) {
165 if (__pred(*__first)) return __first;
166 ++__first;
167
168 if (__pred(*__first)) return __first;
169 ++__first;
170
171 if (__pred(*__first)) return __first;
172 ++__first;
173
174 if (__pred(*__first)) return __first;
175 ++__first;
176 }
177
178 switch(__last - __first) {
179 case 3:
180 if (__pred(*__first)) return __first;
181 ++__first;
182 case 2:
183 if (__pred(*__first)) return __first;
184 ++__first;
185 case 1:
186 if (__pred(*__first)) return __first;
187 //++__first;
188 case 0:
189 default:
190 return __last;
191 }
192}
193
194template <class _InputIter, class _Tp>
195_STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
196 const _Tp& __val,
197 const input_iterator_tag &) {
198 while (__first != __last && !(*__first == __val)) ++__first;
199 return __first;
200}
201
202template <class _InputIter, class _Predicate>
203_STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _InputIter __last,
204 _Predicate __pred,
205 const input_iterator_tag &) {
206 while (__first != __last && !__pred(*__first))
207 ++__first;
208 return __first;
209}
210
212
213template <class _InputIter, class _Predicate>
214_InputIter find_if(_InputIter __first, _InputIter __last,
215 _Predicate __pred) {
216 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
217 return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
218}
219
220template <class _InputIter, class _Tp>
221_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
222 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
223 return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
224}
225
226template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
227_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
228 _ForwardIter2 __first2, _ForwardIter2 __last2,
229 _BinaryPred __pred) {
230 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
231 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
232 // Test for empty ranges
233 if (__first1 == __last1 || __first2 == __last2)
234 return __first1;
235
236 // Test for a pattern of length 1.
237 _ForwardIter2 __p1(__first2);
238
239 if ( ++__p1 == __last2 ) {
240 while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
241 ++__first1;
242 }
243 return __first1;
244 }
245
246 // General case.
247
248 for ( ; ; ) { // __first1 != __last1 will be checked below
249 while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
250 ++__first1;
251 }
252 if (__first1 == __last1) {
253 return __last1;
254 }
255 _ForwardIter2 __p = __p1;
256 _ForwardIter1 __current = __first1;
257 if (++__current == __last1) return __last1;
258
259 while (__pred(*__current, *__p)) {
260 if (++__p == __last2)
261 return __first1;
262 if (++__current == __last1)
263 return __last1;
264 }
265 ++__first1;
266 }
267 return __first1;
268}
269
271template <class _Tp>
273{ typedef __false_type _Ret; };
274
276{ typedef __true_type _Ret; };
277
279{ typedef __true_type _Ret; };
280
281# ifndef _STLP_NO_SIGNED_BUILTINS
283{ typedef __true_type _Ret; };
284# endif
285
286template <class _Tp1, class _Tp2>
287inline bool __stlp_eq(_Tp1 __val1, _Tp2 __val2)
288{ return __val1 == __val2; }
289
290#if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
291template <class _Tp>
292inline bool __stlp_eq(_Tp, _Tp)
293{ return true; }
294#endif
295
296template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
297inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1,
298 _ForwardIter __first2, _ForwardIter __last2,
299 _Tp2*, _Predicate __pred,
300 const __true_type& /* _UseStrcspnLikeAlgo */) {
301 unsigned char __hints[(UCHAR_MAX + 1) / CHAR_BIT];
302 memset(__hints, 0, sizeof(__hints) / sizeof(unsigned char));
303 for (; __first2 != __last2; ++__first2) {
304 unsigned char __tmp = (unsigned char)*__first2;
305 __hints[__tmp / CHAR_BIT] |= (1 << (__tmp % CHAR_BIT));
306 }
307
308 for (; __first1 != __last1; ++__first1) {
309 _Tp2 __tmp = (_Tp2)*__first1;
310 if (__stlp_eq(*__first1, __tmp) &&
311 __pred((__hints[(unsigned char)__tmp / CHAR_BIT] & (1 << ((unsigned char)__tmp % CHAR_BIT))) != 0))
312 break;
313 }
314 return __first1;
315}
316
317template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
318inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1,
319 _ForwardIter __first2, _ForwardIter __last2,
320 _Tp2* /* __dummy */, _Predicate /* __pred */,
321 const __false_type& /* _UseStrcspnLikeAlgo */) {
322 return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2,
323 _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));
324}
325
326template <class _InputIter, class _ForwardIter, class _Tp1, class _Tp2>
327inline _InputIter __find_first_of_aux1(_InputIter __first1, _InputIter __last1,
328 _ForwardIter __first2, _ForwardIter __last2,
329 _Tp1* __pt1, _Tp2* __pt2) {
330 typedef _STLP_TYPENAME _STLP_STD::_IsIntegral<_Tp1>::_Ret _IsIntegral;
332 typedef _STLP_TYPENAME _STLP_STD::_Land2<_IsIntegral, _IsCharLike>::_Ret _UseStrcspnLikeAlgo;
333 return _STLP_PRIV __find_first_of_aux2(__first1, __last1,
334 __first2, __last2,
335 __pt2, _Identity<bool>(), _UseStrcspnLikeAlgo());
336}
337
338template <class _InputIter, class _ForwardIter>
339inline _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
340 _ForwardIter __first2, _ForwardIter __last2) {
341 return _STLP_PRIV __find_first_of_aux1(__first1, __last1, __first2, __last2,
342 _STLP_VALUE_TYPE(__first1, _InputIter),
343 _STLP_VALUE_TYPE(__first2, _ForwardIter));
344}
345
346// find_first_of, with and without an explicitly supplied comparison function.
347template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
348_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
349 _ForwardIter __first2, _ForwardIter __last2,
350 _BinaryPredicate __comp) {
351 for ( ; __first1 != __last1; ++__first1) {
352 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
353 if (__comp(*__first1, *__iter)) {
354 return __first1;
355 }
356 }
357 }
358 return __last1;
359}
360
361// find_end, with and without an explicitly supplied comparison function.
362// Search [first2, last2) as a subsequence in [first1, last1), and return
363// the *last* possible match. Note that find_end for bidirectional iterators
364// is much faster than for forward iterators.
365
366// find_end for forward iterators.
367template <class _ForwardIter1, class _ForwardIter2,
368 class _BinaryPredicate>
369_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
370 _ForwardIter2 __first2, _ForwardIter2 __last2,
372 _BinaryPredicate __comp) {
373 if (__first2 == __last2)
374 return __last1;
375 else {
376 _ForwardIter1 __result = __last1;
377 for (;;) {
378 _ForwardIter1 __new_result = _STLP_STD::search(__first1, __last1, __first2, __last2, __comp);
379 if (__new_result == __last1)
380 return __result;
381 else {
382 __result = __new_result;
383 __first1 = __new_result;
384 ++__first1;
385 }
386 }
387 }
388}
389
391
392// find_end for bidirectional iterators. Requires partial specialization.
393#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
394
395# ifndef _STLP_INTERNAL_ITERATOR_H
397# include <stl/_iterator.h>
399# endif /*_STLP_INTERNAL_ITERATOR_H*/
400
402
403template <class _BidirectionalIter1, class _BidirectionalIter2,
404 class _BinaryPredicate>
405_BidirectionalIter1
406__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
407 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
409 _BinaryPredicate __comp) {
410 typedef _STLP_STD::reverse_iterator<_BidirectionalIter1> _RevIter1;
411 typedef _STLP_STD::reverse_iterator<_BidirectionalIter2> _RevIter2;
412
413 _RevIter1 __rlast1(__first1);
414 _RevIter2 __rlast2(__first2);
415 _RevIter1 __rresult = _STLP_STD::search(_RevIter1(__last1), __rlast1,
416 _RevIter2(__last2), __rlast2,
417 __comp);
418
419 if (__rresult == __rlast1)
420 return __last1;
421 else {
422 _BidirectionalIter1 __result = __rresult.base();
423 _STLP_STD::advance(__result, -_STLP_STD::distance(__first2, __last2));
424 return __result;
425 }
426}
427
429#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
430
431template <class _ForwardIter1, class _ForwardIter2,
432 class _BinaryPredicate>
433_ForwardIter1
434find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
435 _ForwardIter2 __first2, _ForwardIter2 __last2,
436 _BinaryPredicate __comp) {
437 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
438 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
439 return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
441 _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
442 _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
443#else
446#endif
447 __comp);
448}
449
451
452template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
453_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
454 _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
455 _Distance __len = _STLP_STD::distance(__first, __last);
456 _Distance __half;
457 _ForwardIter __middle;
458
459 while (__len > 0) {
460 __half = __len >> 1;
461 __middle = __first;
462 _STLP_STD::advance(__middle, __half);
463 if (__comp1(*__middle, __val)) {
464 _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
465 __first = __middle;
466 ++__first;
467 __len = __len - __half - 1;
468 }
469 else
470 __len = __half;
471 }
472 return __first;
473}
474
476
478
479#endif /* _STLP_ALGOBASE_C */
480
481// Local Variables:
482// mode:C++
483// End:
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_STLP_INLINE_LOOP _InputIter _Predicate __pred
Definition: _algo.h:68
_InputIter __find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2)
Definition: _algobase.c:339
bool __stlp_eq(_Tp1 __val1, _Tp2 __val2)
Definition: _algobase.c:287
_STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last, _Predicate __pred, const random_access_iterator_tag &)
Definition: _algobase.c:159
_STLP_MOVE_TO_STD_NAMESPACE int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:101
_STLP_BEGIN_NAMESPACE bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:39
_InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2, _Tp2 *, _Predicate __pred, const __true_type &)
Definition: _algobase.c:297
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __pred)
Definition: _algobase.c:227
_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, const forward_iterator_tag &, const forward_iterator_tag &, _BinaryPredicate __comp)
Definition: _algobase.c:369
_InputIter __find_first_of_aux1(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2, _Tp1 *__pt1, _Tp2 *__pt2)
Definition: _algobase.c:327
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPredicate __comp)
Definition: _algobase.c:434
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last, const _Tp &__val, const random_access_iterator_tag &)
Definition: _algobase.c:112
_STLP_MOVE_TO_PRIV_NAMESPACE int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:78
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *)
Definition: _algobase.c:453
_STLP_MOVE_TO_STD_NAMESPACE _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred)
Definition: _algobase.c:214
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439
#define _STLP_PRIV
Definition: _dm.h:70
equal_to< _Tp > __equal_to(_Tp *)
#define _STLP_DIFFERENCE_TYPE(_Iterator)
#define _STLP_VALUE_TYPE(_It, _Tp)
#define _STLP_ITERATOR_CATEGORY(_It, _Tp)
static TAGID TAGID find
Definition: db.cpp:155
unsigned char
Definition: typeof.h:29
#define CHAR_BIT
Definition: urlcache.c:62
#define _STLP_TEMPLATE_NULL
Definition: features.h:652
#define _STLP_CLASS_PARTIAL_SPECIALIZATION
Definition: features.h:120
#define _STLP_INLINE_LOOP
Definition: features.h:648
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
#define _STLP_TYPENAME
Definition: features.h:612
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
GLuint res
Definition: glext.h:9613
#define UCHAR_MAX
Definition: limits.h:25
#define memchr(s, c, n)
Definition: mkisofs.h:875
static unsigned(__cdecl *hash_bstr)(bstr_t s)
#define signed
Definition: prototyp.h:114
#define memset(x, y, z)
Definition: compat.h:39
__false_type _Ret
Definition: _algobase.c:273