Stxxl  1.2.1
utils.h
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, 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_UTILS_HEADER
15 #define STXXL_UTILS_HEADER
16 
17 #include <iostream>
18 #include <sstream>
19 #include <algorithm>
20 #include <vector>
21 #include <string>
22 #include <limits>
23 
24 #include <cassert>
25 #include <cstdio>
26 #include <cerrno>
27 #include <cstring>
28 #include <cstdlib>
29 #include <cmath>
30 #include <sys/types.h>
31 #include <sys/stat.h>
32 
33 #ifdef STXXL_BOOST_CONFIG
34  #include <boost/config.hpp>
35 #endif
36 
37 #ifdef STXXL_BOOST_FILESYSTEM
38  #include <boost/filesystem/operations.hpp>
39 #endif
40 
41 #include <stxxl/bits/namespace.h>
42 #include <stxxl/bits/common/log.h>
43 #include <stxxl/bits/common/exceptions.h>
44 #include <stxxl/bits/common/types.h>
45 #include <stxxl/bits/common/timer.h>
46 #include <stxxl/bits/common/is_sorted.h>
47 
48 
49 __STXXL_BEGIN_NAMESPACE
50 
51 template <typename U>
52 inline void UNUSED(const U &)
53 { }
54 
55 #ifdef BOOST_MSVC
56  #define __STXXL_DEPRECATED(x) __declspec(deprecated) x
57 #else
58  #define __STXXL_DEPRECATED(x) x __attribute__ ((__deprecated__))
59 #endif
60 
62 
63 #define __STXXL_STRING(x) # x
64 
65 
66 #define _STXXL_PRINT(label, outstream, log_stream, message) \
67  { std::ostringstream str_; \
68  str_ << "[" label "] " << message << std::endl; \
69  outstream << str_.str() << std::flush; \
70  stxxl::logger::get_instance()->log_stream() << str_.str() << std::flush; \
71  }
72 
73 #define STXXL_MSG(x) _STXXL_PRINT("STXXL-MSG", std::cout, log_stream, x)
74 
75 #define STXXL_ERRMSG(x) _STXXL_PRINT("STXXL-ERRMSG", std::cerr, errlog_stream, x)
76 
77 
78 #ifdef STXXL_FORCE_VERBOSE_LEVEL
79 #undef STXXL_VERBOSE_LEVEL
80 #define STXXL_VERBOSE_LEVEL STXXL_FORCE_VERBOSE_LEVEL
81 #endif
82 
83 #ifdef STXXL_DEFAULT_VERBOSE_LEVEL
84 #ifndef STXXL_VERBOSE_LEVEL
85 #define STXXL_VERBOSE_LEVEL STXXL_DEFAULT_VERBOSE_LEVEL
86 #endif
87 #endif
88 
89 #ifndef STXXL_VERBOSE_LEVEL
90 #define STXXL_VERBOSE_LEVEL -1
91 #endif
92 
93 // STXXL_VERBOSE0 should be used for current debugging activity only,
94 // and afterwards be replaced by STXXL_VERBOSE1 or higher.
95 // Code that actively uses STXXL_VERBOSE0 should never get into a release.
96 
97 #if STXXL_VERBOSE_LEVEL > -1
98  #define STXXL_VERBOSE0(x) _STXXL_PRINT("STXXL-VERBOSE0", std::cout, log_stream, x)
99 #else
100  #define STXXL_VERBOSE0(x)
101 #endif
102 
103 #if STXXL_VERBOSE_LEVEL > 0
104  #define STXXL_VERBOSE1(x) _STXXL_PRINT("STXXL-VERBOSE1", std::cout, log_stream, x)
105 #else
106  #define STXXL_VERBOSE1(x)
107 #endif
108 
109 #define STXXL_VERBOSE(x) STXXL_VERBOSE1(x)
110 
111 #if STXXL_VERBOSE_LEVEL > 1
112  #define STXXL_VERBOSE2(x) _STXXL_PRINT("STXXL-VERBOSE2", std::cout, log_stream, x)
113 #else
114  #define STXXL_VERBOSE2(x)
115 #endif
116 
117 #if STXXL_VERBOSE_LEVEL > 2
118  #define STXXL_VERBOSE3(x) _STXXL_PRINT("STXXL-VERBOSE3", std::cout, log_stream, x)
119 #else
120  #define STXXL_VERBOSE3(x)
121 #endif
122 
124 
125 #ifdef BOOST_MSVC
126  #define STXXL_PRETTY_FUNCTION_NAME __FUNCTION__
127 #else
128  #define STXXL_PRETTY_FUNCTION_NAME __PRETTY_FUNCTION__
129 #endif
130 
131 #define STXXL_FORMAT_ERROR_MSG(str_, errmsg_) \
132  std::ostringstream str_; str_ << "Error in " << errmsg_
133 
134 #define STXXL_THROW(exception_type, location, error_message) \
135  { \
136  std::ostringstream msg_; \
137  msg_ << "Error in " << location << ": " << error_message; \
138  throw exception_type(msg_.str()); \
139  }
140 
141 #define STXXL_THROW2(exception_type, error_message) \
142  STXXL_THROW(exception_type, "function " << STXXL_PRETTY_FUNCTION_NAME, \
143  "Info: " << error_message << " " << strerror(errno))
144 
145 template <typename E>
146 inline void stxxl_util_function_error(const char * func_name, const char * expr = 0, const char * error = 0)
147 {
148  std::ostringstream str_;
149  str_ << "Error in function " << func_name << " " << (expr ? expr : strerror(errno));
150  if (error)
151  str_ << " " << error;
152  throw E(str_.str());
153 }
154 
155 #define stxxl_function_error(exception_type) \
156  stxxl::stxxl_util_function_error<exception_type>(STXXL_PRETTY_FUNCTION_NAME)
157 
158 template <typename E>
159 inline bool helper_check_success(bool success, const char * func_name, const char * expr = 0, const char * error = 0)
160 {
161  if (!success)
162  stxxl_util_function_error<E>(func_name, expr, error);
163  return success;
164 }
165 
166 template <typename E, typename INT>
167 inline bool helper_check_eq_0(INT res, const char * func_name, const char * expr, bool res_2_strerror = false)
168 {
169  return helper_check_success<E>(res == 0, func_name, expr, res_2_strerror ? strerror(res) : 0);
170 }
171 
172 #define check_pthread_call(expr) \
173  stxxl::helper_check_eq_0<stxxl::resource_error>(expr, STXXL_PRETTY_FUNCTION_NAME, __STXXL_STRING(expr), true)
174 
175 template <typename E, typename INT>
176 inline bool helper_check_ge_0(INT res, const char * func_name)
177 {
178  return helper_check_success<E>(res >= 0, func_name);
179 }
180 
181 #define stxxl_check_ge_0(expr, exception_type) \
182  stxxl::helper_check_ge_0<exception_type>(expr, STXXL_PRETTY_FUNCTION_NAME)
183 
184 template <typename E, typename INT>
185 inline bool helper_check_ne_0(INT res, const char * func_name)
186 {
187  return helper_check_success<E>(res != 0, func_name);
188 }
189 
190 #define stxxl_check_ne_0(expr, exception_type) \
191  stxxl::helper_check_ne_0<exception_type>(expr, STXXL_PRETTY_FUNCTION_NAME)
192 
193 #ifdef BOOST_MSVC
194 
195 #define stxxl_win_lasterror_exit(errmsg, exception_type) \
196  { \
197  TCHAR szBuf[80]; \
198  LPVOID lpMsgBuf; \
199  DWORD dw = GetLastError(); \
200  FormatMessage( \
201  FORMAT_MESSAGE_ALLOCATE_BUFFER | \
202  FORMAT_MESSAGE_FROM_SYSTEM, \
203  NULL, \
204  dw, \
205  MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), \
206  (LPTSTR)&lpMsgBuf, \
207  0, NULL); \
208  std::ostringstream str_; \
209  str_ << "Error in " << errmsg << ", error code " << dw << ": " << ((char *)lpMsgBuf); \
210  LocalFree(lpMsgBuf); \
211  throw exception_type(str_.str()); \
212  }
213 
214 #endif
215 
217 
218 inline std::string
219 stxxl_tmpfilename(std::string dir, std::string prefix)
220 {
221  //STXXL_VERBOSE0(" TMP:"<< dir.c_str() <<":"<< prefix.c_str());
222  int rnd;
223  char buffer[1024];
224  std::string result;
225 
226 #ifndef STXXL_BOOST_FILESYSTEM
227  struct stat st;
228 #endif
229 
230  do
231  {
232  rnd = rand();
233  sprintf(buffer, "%d", rnd);
234  result = dir + prefix + buffer;
235  }
236 #ifdef STXXL_BOOST_FILESYSTEM
237  while (boost::filesystem::exists(result));
238 
239  return result;
240 #else
241  while (!lstat(result.c_str(), &st));
242 
243  if (errno != ENOENT)
244  stxxl_function_error(io_error);
245 
246  return result;
247 #endif
248 }
249 
251 
252 inline std::vector<std::string>
253 split(const std::string & str, const std::string & sep)
254 {
255  std::vector<std::string> result;
256  if (str.empty())
257  return result;
258 
259  std::string::size_type CurPos(0), LastPos(0);
260  while (1)
261  {
262  CurPos = str.find(sep, LastPos);
263  if (CurPos == std::string::npos)
264  break;
265 
266  std::string sub =
267  str.substr(LastPos,
268  std::string::size_type(CurPos -
269  LastPos));
270  if (sub.size())
271  result.push_back(sub);
272 
273  LastPos = CurPos + sep.size();
274  }
275 
276  std::string sub = str.substr(LastPos);
277  if (sub.size())
278  result.push_back(sub);
279 
280  return result;
281 }
282 
284 
285 #define str2int(str) atoi(str.c_str())
286 
287 inline std::string int2str(int i)
288 {
289  char buf[32];
290  sprintf(buf, "%d", i);
291  return std::string(buf);
292 }
293 
294 inline stxxl::int64 atoint64(const char * s)
295 {
296 #ifdef BOOST_MSVC
297  return _atoi64(s);
298 #else
299  return atoll(s);
300 #endif
301 }
302 
304 
305 #define STXXL_MIN(a, b) ((std::min)(a, b))
306 #define STXXL_MAX(a, b) ((std::max)(a, b))
307 
308 #define STXXL_L2_SIZE (512 * 1024)
309 
310 #define div_and_round_up(a, b) ((a) / (b) + !(!((a) % (b))))
311 
312 #define log2(x) (log(x) / log(2.))
313 
315 
316 //#define HAVE_BUILTIN_EXPECT
317 
318 #ifdef HAVE_BUILTIN_EXPECT
319  #define LIKELY(c) __builtin_expect((c), 1)
320 #else
321  #define LIKELY(c) c
322 #endif
323 
324 #ifdef HAVE_BUILTIN_EXPECT
325  #define UNLIKELY(c) __builtin_expect((c), 0)
326 #else
327  #define UNLIKELY(c) c
328 #endif
329 
331 
332 inline uint64 longhash1(uint64 key_)
333 {
334  key_ += ~(key_ << 32);
335  key_ ^= (key_ >> 22);
336  key_ += ~(key_ << 13);
337  key_ ^= (key_ >> 8);
338  key_ += (key_ << 3);
339  key_ ^= (key_ >> 15);
340  key_ += ~(key_ << 27);
341  key_ ^= (key_ >> 31);
342  return key_;
343 }
344 
346 
347 template <class T>
348 inline void swap_1D_arrays(T * a, T * b, unsigned_type size)
349 {
350  for (unsigned_type i = 0; i < size; ++i)
351  std::swap(a[i], b[i]);
352 }
353 
355 
356 template <class T>
357 class new_alloc;
358 
359 template <typename T, typename U>
360 struct new_alloc_rebind;
361 
362 template <typename T>
363 struct new_alloc_rebind<T, T>{
364  typedef new_alloc<T> other;
365 };
366 
367 template <typename T, typename U>
368 struct new_alloc_rebind {
369  typedef std::allocator<U> other;
370 };
371 
372 
373 // designed for typed_block (to use with std::vector )
374 template <class T>
375 class new_alloc {
376 public:
377  // type definitions
378  typedef T value_type;
379  typedef T * pointer;
380  typedef const T * const_pointer;
381  typedef T & reference;
382  typedef const T & const_reference;
383  typedef std::size_t size_type;
384  typedef std::ptrdiff_t difference_type;
385 
386  // rebind allocator to type U, use new_alloc only if U == T
387  template <class U>
388  struct rebind {
389  typedef typename new_alloc_rebind<T, U>::other other;
390  };
391 
392  // return address of values
393  pointer address(reference value) const
394  {
395  return &value;
396  }
397  const_pointer address(const_reference value) const
398  {
399  return &value;
400  }
401 
402  new_alloc() throw () { }
403  new_alloc(const new_alloc &) throw () { }
404  template <class U>
405  new_alloc(const new_alloc<U> &) throw () { }
406  ~new_alloc() throw () { }
407 
408  template <class U>
409  operator std::allocator<U>()
410  {
411  static std::allocator<U> helper_allocator;
412  return helper_allocator;
413  }
414 
415  // return maximum number of elements that can be allocated
416  size_type max_size() const throw ()
417  {
418  return (std::numeric_limits<std::size_t>::max) () / sizeof(T);
419  }
420 
421  // allocate but don't initialize num elements of type T
422  pointer allocate(size_type num, const void * = 0)
423  {
424  pointer ret = (pointer)(T::operator new (num * sizeof(T)));
425  return ret;
426  }
427 
428  // initialize elements of allocated storage p with value value
429  void construct(pointer p, const T & value)
430  {
431  // initialize memory with placement new
432  new ((void *)p)T(value);
433  }
434 
435  // destroy elements of initialized storage p
436  void destroy(pointer p)
437  {
438  // destroy objects by calling their destructor
439  p->~T();
440  }
441 
442  // deallocate storage p of deleted elements
443  void deallocate(pointer p, size_type /*num*/)
444  {
445  T::operator delete ((void *)p);
446  }
447 };
448 
449 // return that all specializations of this allocator are interchangeable
450 template <class T1, class T2>
451 inline bool operator == (const new_alloc<T1> &,
452  const new_alloc<T2> &) throw ()
453 {
454  return true;
455 }
456 
457 template <class T1, class T2>
458 inline bool operator != (const new_alloc<T1> &,
459  const new_alloc<T2> &) throw ()
460 {
461  return false;
462 }
463 
464 __STXXL_END_NAMESPACE
465 
466 #endif // !STXXL_UTILS_HEADER