• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#ifdef __cplusplus
2
3/*
4 *
5 * Copyright (c) 1994
6 * Hewlett-Packard Company
7 *
8 * Permission to use, copy, modify, distribute and sell this software
9 * and its documentation for any purpose is hereby granted without fee,
10 * provided that the above copyright notice appear in all copies and
11 * that both that copyright notice and this permission notice appear
12 * in supporting documentation.  Hewlett-Packard Company makes no
13 * representations about the suitability of this software for any
14 * purpose.  It is provided "as is" without express or implied warranty.
15 *
16 *
17 * Copyright (c) 1996-1998
18 * Silicon Graphics Computer Systems, Inc.
19 *
20 * Permission to use, copy, modify, distribute and sell this software
21 * and its documentation for any purpose is hereby granted without fee,
22 * provided that the above copyright notice appear in all copies and
23 * that both that copyright notice and this permission notice appear
24 * in supporting documentation.  Silicon Graphics makes no
25 * representations about the suitability of this software for any
26 * purpose.  It is provided "as is" without express or implied warranty.
27 */
28
29 // extracted from stl_algobase.h
30 // full STL is not compatible with the ARM build
31 // a limited number of STL functions is used by webkit: swap, max, and min are
32 // included below for webkit compatibility
33
34#ifdef __GLIBCPP_INTERNAL_ALGOBASE_H
35#error "real STL defined"
36#endif
37
38#ifndef __ANDROID_ALGORITHM
39#define __ANDROID_ALGORITHM
40
41#ifndef __ANDROID_LIMITS
42#include <limits>
43#endif
44
45#ifndef _CPP_UTILITY
46#include <utility>
47#endif
48
49#include <SkScalar.h> // for SK_ScalarNaN
50#ifdef PREFIX_FOR_WEBCORE
51#include <SkTSearch.h>
52#endif
53
54#include <float.h>
55#include <math.h>
56#include <stdint.h>
57#include <stddef.h>
58
59#ifndef WCHAR_MAX
60	#define WCHAR_MAX	0xFFFF
61#endif
62
63namespace std
64{
65  template<typename _Tp>
66    inline void
67    swap(_Tp& __a, _Tp& __b)
68    {
69      _Tp __tmp = __a;
70      __a = __b;
71      __b = __tmp;
72    }
73
74  template<typename _Tp>
75    inline void
76    reverse(_Tp* __first, _Tp* __last)
77    {
78      while(true)
79      {
80        if (__first == __last || __first == --__last)
81          return;
82        else
83        {
84          _Tp __tmp = *__first;
85          *__first = *__last;
86          *__last = __tmp;
87        }
88        ++__first;
89      }
90    }
91
92  #undef min
93  #undef max
94
95  template<typename _Tp>
96    inline const _Tp&
97    min(const _Tp& __a, const _Tp& __b)
98    {
99      return __b < __a ? __b : __a;
100    }
101
102  template<typename _Tp>
103    inline const _Tp&
104    max(const _Tp& __a, const _Tp& __b)
105    {
106      return  __a < __b ? __b : __a;
107    }
108
109template <class _InputIter, class _OutputIter>
110inline _OutputIter copy(_InputIter __first, _InputIter __last,
111                        _OutputIter __result)
112{
113  for (size_t __n = __last - __first; __n > 0; --__n) {
114    *__result = *__first;
115    ++__first;
116    ++__result;
117  }
118  return __result;
119}
120
121template <class _ForwardIter, class _Tp>
122void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
123  for ( ; __first != __last; ++__first)
124    *__first = __value;
125}
126
127#ifndef UINTPTR_MAX
128#define UINTPTR_MAX	UINT32_MAX
129#endif
130
131#ifndef UINT32_MAX
132#define UINT32_MAX    (0xffffffff)
133#endif
134
135template <typename T>
136struct numeric_limits {
137    /// Returns the minimum value for type T.
138    static inline T min (void)		{ return (T(0)); }
139    /// Returns the minimum value for type T.
140    static inline T max (void)		{ return (T(0)); }
141    static const bool is_signed = false;	///< True if the type is signed.
142    static const bool is_integer = false;	///< True if stores an exact value.
143    static const bool is_integral = false;	///< True if fixed size and cast-copyable.
144};
145
146template <typename T>
147struct numeric_limits<T*> {
148    static inline T* min (void)	{ return (NULL); }
149    static inline T* max (void)	{ return (UINTPTR_MAX); }
150    static const bool is_signed = false;
151    static const bool is_integer = true;
152    static const bool is_integral = true;
153};
154
155#define _NUMERIC_LIMITS(type, minVal, maxVal, quietNaN, bSigned, bInteger, bIntegral)	\
156template <>							\
157struct numeric_limits<type> {					\
158    static inline type infinity (void)	{ return (maxVal); }	\
159    static inline type min (void)	{ return (minVal); }	\
160    static inline type max (void)	{ return (maxVal); }	\
161    static inline type quiet_NaN() { return (quietNaN); } \
162    static const bool is_signed = bSigned;			\
163    static const bool is_integer = bInteger;			\
164    static const bool is_integral = bIntegral;			\
165}
166
167//--------------------------------------------------------------------------------------
168//		         type		    min		    max		    NaN     signed	integer	integral
169//--------------------------------------------------------------------------------------
170_NUMERIC_LIMITS (bool,		    false,		true,		0,      false,	true,	true);
171_NUMERIC_LIMITS (char,		    SCHAR_MIN,	SCHAR_MAX,	0,      true,	true,	true);
172_NUMERIC_LIMITS (int,		    INT_MIN,	INT_MAX,	0,      true,	true,	true);
173_NUMERIC_LIMITS (short,		    SHRT_MIN,	SHRT_MAX,	0,      true,	true,	true);
174_NUMERIC_LIMITS (long,		    LONG_MIN,	LONG_MAX,	0,      true,	true,	true);
175#if HAVE_THREE_CHAR_TYPES
176_NUMERIC_LIMITS (signed char,	SCHAR_MIN,	SCHAR_MAX,	0,      true,	true,	true);
177#endif
178_NUMERIC_LIMITS (unsigned char,	0,		    UCHAR_MAX,	0,      false,	true,	true);
179_NUMERIC_LIMITS (unsigned int,	0,		    UINT_MAX,	0,      false,	true,	true);
180_NUMERIC_LIMITS (unsigned short,0,		    USHRT_MAX,	0,      false,	true,	true);
181_NUMERIC_LIMITS (unsigned long,	0,		    ULONG_MAX,	0,      false,	true,	true);
182_NUMERIC_LIMITS (wchar_t,	    0,		    WCHAR_MAX,	0,      false,	true,	true);
183_NUMERIC_LIMITS (float,		    FLT_MIN,	FLT_MAX,  SK_ScalarNaN, true,	false,	true);
184_NUMERIC_LIMITS (double,	    DBL_MIN,	DBL_MAX,  SK_ScalarNaN, true,	false,	true);
185_NUMERIC_LIMITS (long double,	LDBL_MIN,	LDBL_MAX, SK_ScalarNaN, true,	false,	true);
186#ifdef HAVE_LONG_LONG
187_NUMERIC_LIMITS (long long,	    LLONG_MIN,	LLONG_MAX,	0,      true,	true,	true);
188_NUMERIC_LIMITS (unsigned long long,	0,	ULLONG_MAX,	0,      false,	true,	true);
189#endif
190//--------------------------------------------------------------------------------------
191
192using ::ptrdiff_t;
193
194typedef bool (* Comparator)(const void*, const void*);
195extern void sort(const void** start, const void** end, Comparator comp);
196
197#ifdef PREFIX_FOR_WEBCORE
198    typedef const void* sortType;
199
200    inline bool binary_search(const unsigned short* const base,
201                              const unsigned short* const end,
202                              short target)
203    {
204        return SkTSearch<unsigned short>(base, end - base, target, sizeof(unsigned short)) >= 0;
205    }
206
207
208    template<typename P> inline void sort (P** start, P**end,
209        bool (* comp)(const P*, const P*))
210    {
211        sort((const void**) start, (const void**) end, (Comparator) comp);
212    }
213
214    template<typename P> void sort(P* start, P* end,
215            bool (* comp)(const P&, const P&)) {
216        stable_sort(start, end, *comp);
217    }
218
219    template<typename P> inline void stable_sort(P** start, P** end,
220       bool (* comp)(P*, P*))
221    {
222        sort((const void**) start, (const void**) end, (Comparator) comp);
223    }
224
225    template<typename P> inline void stable_sort(P** start, P** end,
226       bool (& comp)(const P*, const P*))
227    {
228        sort((const void**) start, (const void**) end, (Comparator) &comp);
229    }
230
231    template<typename P> void stable_sort(P* start, P* end, P* temp,
232            bool (& comp)(const P&, const P&)) {
233        size_t endlen = end - start;
234        size_t midlen = endlen / 2;
235        P* mid = start + midlen;
236        if (midlen > 1)
237            stable_sort(start, mid, temp, comp);
238        if (end - mid > 1)
239            stable_sort(mid, end, temp, comp);
240        memcpy(temp, start, midlen * sizeof(*start));
241        size_t i = 0;
242        size_t j = midlen;
243        size_t off = 0;
244        while (i < midlen && j < endlen) {
245            P* dst = (comp)(start[j], temp[i]) ? &start[j++] : &temp[i++];
246            memcpy(&start[off++], dst, sizeof(*start));
247        }
248        if (i < midlen)
249            memcpy(&start[off], &temp[i], (midlen - i) * sizeof(*start));
250    }
251
252    template<typename P> void stable_sort(P* start, P* end,
253            bool (& comp)(const P&, const P&)) {
254        if (end - start > 1) {
255            size_t count = (end - start) / 2;
256            P* temp = static_cast<P*>(malloc(count * sizeof(P)));
257            stable_sort(start, end, temp, comp);
258            free(temp);
259        }
260    }
261
262    template<typename P> void stable_sort(P* start, P* end,
263            bool (& comp)(P, P)) {
264	stable_sort(start, end, (bool (&)(const P&, const P&))(comp));
265    }
266
267    class ostream {
268        int this_class_intentionally_left_empty;
269    };
270#endif
271
272}
273
274#endif
275
276#endif // __cplusplus
277
278