1 /***************************************************************************
2 * include/stxxl/bits/common/utils.h
3 *
4 * Part of the STXXL. See http://stxxl.sourceforge.net
5 *
6 * Copyright (C) 2002-2006 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7 * Copyright (C) 2007-2009 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
8 * Copyright (C) 2008 Johannes Singler <singler@ira.uka.de>
9 * Copyright (C) 2013 Timo Bingmann <tb@panthema.net>
10 *
11 * Distributed under the Boost Software License, Version 1.0.
12 * (See accompanying file LICENSE_1_0.txt or copy at
13 * http://www.boost.org/LICENSE_1_0.txt)
14 **************************************************************************/
15
16 #ifndef STXXL_COMMON_UTILS_HEADER
17 #define STXXL_COMMON_UTILS_HEADER
18
19 #include <vector>
20 #include <string>
21 #include <cmath>
22 #include <cstdlib>
23 #include <algorithm>
24 #include <sstream>
25 #include <limits>
26
27 #include <stxxl/bits/config.h>
28 #include <stxxl/bits/namespace.h>
29 #include <stxxl/bits/common/types.h>
30 #include <stxxl/bits/compat/type_traits.h>
31 #include <stxxl/bits/msvc_compatibility.h>
32
33 STXXL_BEGIN_NAMESPACE
34
35 ////////////////////////////////////////////////////////////////////////////
36
37 #if defined(__GNUC__) && ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 7)))
38 # define STXXL_ATTRIBUTE_UNUSED __attribute__ ((unused))
39 #else
40 # define STXXL_ATTRIBUTE_UNUSED
41 #endif
42
43 ////////////////////////////////////////////////////////////////////////////
44
45 #if defined(__GXX_EXPERIMENTAL_CXX0X__)
46 #define STXXL_STATIC_ASSERT(x) static_assert(x, #x)
47 #else
48 #define STXXL_STATIC_ASSERT(x) { typedef int static_assert_dummy_type[(x) ? 1 : -1] STXXL_ATTRIBUTE_UNUSED; }
49 #endif
50
51 ////////////////////////////////////////////////////////////////////////////
52
53 //! Split a string by given separator string. Returns a vector of strings with
54 //! at least min_fields and at most limit_fields
55 static inline std::vector<std::string>
56 split(const std::string& str, const std::string& sep,
57 unsigned int min_fields = 0,
58 unsigned int limit_fields = std::numeric_limits<unsigned int>::max())
59 {
60 std::vector<std::string> result;
61 if (str.empty()) {
62 result.resize(min_fields);
63 return result;
64 }
65
66 std::string::size_type CurPos(0), LastPos(0);
67 while (1)
68 {
69 if (result.size() + 1 == limit_fields)
70 break;
71
72 CurPos = str.find(sep, LastPos);
73 if (CurPos == std::string::npos)
74 break;
75
76 result.push_back(
77 str.substr(LastPos,
78 std::string::size_type(CurPos - LastPos))
79 );
80
81 LastPos = CurPos + sep.size();
82 }
83
84 std::string sub = str.substr(LastPos);
85 result.push_back(sub);
86
87 if (result.size() < min_fields)
88 result.resize(min_fields);
89
90 return result;
91 }
92
93 ////////////////////////////////////////////////////////////////////////////
94
95 //! Format any ostream-able type into a string
96 template <typename Type>
to_str(const Type & t)97 std::string to_str(const Type& t)
98 {
99 std::ostringstream oss;
100 oss << t;
101 return oss.str();
102 }
103
104 ////////////////////////////////////////////////////////////////////////////
105
106 //! Parse a string like "343KB" or "44 GiB" into the corresponding size in
107 //! bytes. Returns the number of bytes and sets ok = true if the string could
108 //! be parsed correctly. If no units indicator is given, use def_unit in
109 //! k/m/g/t/p (powers of ten) or in K/M/G/T/P (power of two).
110 bool parse_SI_IEC_size(const std::string& str, uint64& size, char def_unit = 0);
111
112 //! Format a byte size using SI (K, M, G, T) suffixes (powers of ten). Returns
113 //! "123 M" or similar.
114 std::string format_SI_size(uint64 number);
115
116 //! Format a byte size using IEC (Ki, Mi, Gi, Ti) suffixes (powers of
117 //! two). Returns "123 Ki" or similar.
118 std::string format_IEC_size(uint64 number);
119
120 ////////////////////////////////////////////////////////////////////////////
121
atoi64(const char * s)122 inline stxxl::int64 atoi64(const char* s)
123 {
124 #if STXXL_MSVC
125 return _atoi64(s);
126 #else
127 return atoll(s);
128 #endif
129 }
130
131 ////////////////////////////////////////////////////////////////////////////
132
atouint64(const char * s)133 inline stxxl::uint64 atouint64(const char* s)
134 {
135 #if STXXL_MSVC
136 return _strtoui64(s, NULL, 10);
137 #else
138 return strtoull(s, NULL, 10);
139 #endif
140 }
141
142 ////////////////////////////////////////////////////////////////////////////
143
144 template <typename Type>
145 inline const Type&
STXXL_MIN(const Type & a,const Type & b)146 STXXL_MIN(const Type& a, const Type& b)
147 {
148 return std::min<Type>(a, b);
149 }
150
151 template <typename Type>
152 inline const Type&
STXXL_MAX(const Type & a,const Type & b)153 STXXL_MAX(const Type& a, const Type& b)
154 {
155 return std::max<Type>(a, b);
156 }
157
158 ////////////////////////////////////////////////////////////////////////////
159
160 //! calculate the log2 floor of an integral type using math.h
161 template <typename Integral>
log2_ceil(Integral i)162 inline Integral log2_ceil(Integral i)
163 {
164 return Integral(ceil(log2(i)));
165 }
166
167 //! calculate the log2 ceiling of an integral type using math.h
168 template <typename Integral>
log2_floor(Integral i)169 inline Integral log2_floor(Integral i)
170 {
171 return Integral(log2(i));
172 }
173
174 ////////////////////////////////////////////////////////////////////////////
175
176 //! calculate the log2 floor of an integer type (by repeated bit shifts)
177 template <typename IntegerType>
ilog2_floor(IntegerType i)178 unsigned int ilog2_floor(IntegerType i)
179 {
180 unsigned int p = 0;
181 while (i >= 256) i >>= 8, p += 8;
182 while (i >>= 1) ++p;
183 return p;
184 }
185
186 //! calculate the log2 ceiling of an integer type (by repeated bit shifts)
187 template <typename IntegerType>
ilog2_ceil(const IntegerType & i)188 unsigned int ilog2_ceil(const IntegerType& i)
189 {
190 if (i <= 1) return 0;
191 return ilog2_floor(i - 1) + 1;
192 }
193
194 ////////////////////////////////////////////////////////////////////////////
195
196 template <typename Integral, typename Integral2>
197 inline
198 typename compat::remove_const<Integral>::type
div_ceil(Integral n,Integral2 d)199 div_ceil(Integral n, Integral2 d)
200 {
201 #if 0 // ambiguous overload for std::div(unsigned_anything, unsigned_anything)
202 typedef __typeof__ (std::div(n, d)) div_type;
203 div_type result = std::div(n, d);
204 return result.quot + (result.rem != 0);
205 #else
206 return n / d + ((n % d) != 0);
207 #endif
208 }
209
210 ////////////////////////////////////////////////////////////////////////////
211
212 #ifdef __GNUC__
213 #define HAVE_BUILTIN_EXPECT
214 #endif
215
216 #ifdef HAVE_BUILTIN_EXPECT
217 #define LIKELY(c) __builtin_expect((c), 1)
218 #else
219 #define LIKELY(c) c
220 #endif
221
222 #ifdef HAVE_BUILTIN_EXPECT
223 #define UNLIKELY(c) __builtin_expect((c), 0)
224 #else
225 #define UNLIKELY(c) c
226 #endif
227
228 ////////////////////////////////////////////////////////////////////////////
229
longhash1(uint64 key_)230 inline size_t longhash1(uint64 key_)
231 {
232 key_ += ~(key_ << 32);
233 key_ ^= (key_ >> 22);
234 key_ += ~(key_ << 13);
235 key_ ^= (key_ >> 8);
236 key_ += (key_ << 3);
237 key_ ^= (key_ >> 15);
238 key_ += ~(key_ << 27);
239 key_ ^= (key_ >> 31);
240 return (size_t)key_;
241 }
242
243 ////////////////////////////////////////////////////////////////////////////
244
245 template <class Type>
swap_1D_arrays(Type * a,Type * b,unsigned_type size)246 inline void swap_1D_arrays(Type* a, Type* b, unsigned_type size)
247 {
248 for (unsigned_type i = 0; i < size; ++i)
249 std::swap(a[i], b[i]);
250 }
251
252 ////////////////////////////////////////////////////////////////////////////
253
254 //! round n up to next larger multiple of 2^power. example: (48,4) = 64, (48,3) = 48.
255 template <typename Integral>
round_up_to_power_of_two(Integral n,unsigned_type power)256 inline Integral round_up_to_power_of_two(Integral n, unsigned_type power)
257 {
258 Integral pot = Integral(1) << power, // = 0..0 1 0^power
259 mask = pot - 1; // = 0..0 0 1^power
260 if (n & mask) // n not divisible by pot
261 return (n & ~mask) + pot;
262 else
263 return n;
264 }
265
266 ////////////////////////////////////////////////////////////////////////////
267
268 template <class Container>
pop(Container & c)269 inline typename Container::value_type pop(Container& c)
270 {
271 typename Container::value_type r = c.top();
272 c.pop();
273 return r;
274 }
275
276 template <class Container>
pop_front(Container & c)277 inline typename Container::value_type pop_front(Container& c)
278 {
279 typename Container::value_type r = c.front();
280 c.pop_front();
281 return r;
282 }
283
284 template <class Container>
pop_back(Container & c)285 inline typename Container::value_type pop_back(Container& c)
286 {
287 typename Container::value_type r = c.back();
288 c.pop_back();
289 return r;
290 }
291
292 template <class Container>
pop_begin(Container & c)293 inline typename Container::value_type pop_begin(Container& c)
294 {
295 typename Container::value_type r = *c.begin();
296 c.erase(c.begin());
297 return r;
298 }
299
300 ////////////////////////////////////////////////////////////////////////////
301
302 STXXL_END_NAMESPACE
303
304 #endif // !STXXL_COMMON_UTILS_HEADER
305 // vim: et:ts=4:sw=4
306