00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #ifndef STXXL_UTILS_HEADER
00015 #define STXXL_UTILS_HEADER
00016
00017 #include <iostream>
00018 #include <sstream>
00019 #include <algorithm>
00020 #include <vector>
00021 #include <string>
00022 #include <limits>
00023
00024 #include <cassert>
00025 #include <cstdio>
00026 #include <cerrno>
00027 #include <cstring>
00028 #include <cstdlib>
00029 #include <cmath>
00030 #include <sys/types.h>
00031 #include <sys/stat.h>
00032
00033 #ifdef STXXL_BOOST_CONFIG
00034 #include <boost/config.hpp>
00035 #endif
00036
00037 #ifdef STXXL_BOOST_FILESYSTEM
00038 #include <boost/filesystem/operations.hpp>
00039 #endif
00040
00041 #include <stxxl/bits/namespace.h>
00042 #include <stxxl/bits/common/log.h>
00043 #include <stxxl/bits/common/exceptions.h>
00044 #include <stxxl/bits/common/types.h>
00045 #include <stxxl/bits/common/timer.h>
00046 #include <stxxl/bits/common/is_sorted.h>
00047
00048
00049 __STXXL_BEGIN_NAMESPACE
00050
00051 template <typename U>
00052 inline void UNUSED(const U &)
00053 { }
00054
00055 #ifdef BOOST_MSVC
00056 #define __STXXL_DEPRECATED(x) __declspec(deprecated) x
00057 #else
00058 #define __STXXL_DEPRECATED(x) x __attribute__ ((__deprecated__))
00059 #endif
00060
00062
00063 #define __STXXL_STRING(x) # x
00064
00065
00066 #define _STXXL_PRINT(label, outstream, log_stream, message) \
00067 { std::ostringstream str_; \
00068 str_ << "[" label "] " << message << std::endl; \
00069 outstream << str_.str() << std::flush; \
00070 stxxl::logger::get_instance()->log_stream() << str_.str() << std::flush; \
00071 }
00072
00073 #define STXXL_MSG(x) _STXXL_PRINT("STXXL-MSG", std::cout, log_stream, x)
00074
00075 #define STXXL_ERRMSG(x) _STXXL_PRINT("STXXL-ERRMSG", std::cerr, errlog_stream, x)
00076
00077
00078 #ifdef STXXL_FORCE_VERBOSE_LEVEL
00079 #undef STXXL_VERBOSE_LEVEL
00080 #define STXXL_VERBOSE_LEVEL STXXL_FORCE_VERBOSE_LEVEL
00081 #endif
00082
00083 #ifdef STXXL_DEFAULT_VERBOSE_LEVEL
00084 #ifndef STXXL_VERBOSE_LEVEL
00085 #define STXXL_VERBOSE_LEVEL STXXL_DEFAULT_VERBOSE_LEVEL
00086 #endif
00087 #endif
00088
00089 #ifndef STXXL_VERBOSE_LEVEL
00090 #define STXXL_VERBOSE_LEVEL -1
00091 #endif
00092
00093
00094
00095
00096
00097 #if STXXL_VERBOSE_LEVEL > -1
00098 #define STXXL_VERBOSE0(x) _STXXL_PRINT("STXXL-VERBOSE0", std::cout, log_stream, x)
00099 #else
00100 #define STXXL_VERBOSE0(x)
00101 #endif
00102
00103 #if STXXL_VERBOSE_LEVEL > 0
00104 #define STXXL_VERBOSE1(x) _STXXL_PRINT("STXXL-VERBOSE1", std::cout, log_stream, x)
00105 #else
00106 #define STXXL_VERBOSE1(x)
00107 #endif
00108
00109 #define STXXL_VERBOSE(x) STXXL_VERBOSE1(x)
00110
00111 #if STXXL_VERBOSE_LEVEL > 1
00112 #define STXXL_VERBOSE2(x) _STXXL_PRINT("STXXL-VERBOSE2", std::cout, log_stream, x)
00113 #else
00114 #define STXXL_VERBOSE2(x)
00115 #endif
00116
00117 #if STXXL_VERBOSE_LEVEL > 2
00118 #define STXXL_VERBOSE3(x) _STXXL_PRINT("STXXL-VERBOSE3", std::cout, log_stream, x)
00119 #else
00120 #define STXXL_VERBOSE3(x)
00121 #endif
00122
00124
00125 #ifdef BOOST_MSVC
00126 #define STXXL_PRETTY_FUNCTION_NAME __FUNCTION__
00127 #else
00128 #define STXXL_PRETTY_FUNCTION_NAME __PRETTY_FUNCTION__
00129 #endif
00130
00131 #define STXXL_FORMAT_ERROR_MSG(str_, errmsg_) \
00132 std::ostringstream str_; str_ << "Error in " << errmsg_
00133
00134 #define STXXL_THROW(exception_type, location, error_message) \
00135 { \
00136 std::ostringstream msg_; \
00137 msg_ << "Error in " << location << ": " << error_message; \
00138 throw exception_type(msg_.str()); \
00139 }
00140
00141 #define STXXL_THROW2(exception_type, error_message) \
00142 STXXL_THROW(exception_type, "function " << STXXL_PRETTY_FUNCTION_NAME, \
00143 "Info: " << error_message << " " << strerror(errno))
00144
00145 template <typename E>
00146 inline void stxxl_util_function_error(const char * func_name, const char * expr = 0, const char * error = 0)
00147 {
00148 std::ostringstream str_;
00149 str_ << "Error in function " << func_name << " " << (expr ? expr : strerror(errno));
00150 if (error)
00151 str_ << " " << error;
00152 throw E(str_.str());
00153 }
00154
00155 #define stxxl_function_error(exception_type) \
00156 stxxl::stxxl_util_function_error<exception_type>(STXXL_PRETTY_FUNCTION_NAME)
00157
00158 template <typename E>
00159 inline bool helper_check_success(bool success, const char * func_name, const char * expr = 0, const char * error = 0)
00160 {
00161 if (!success)
00162 stxxl_util_function_error<E>(func_name, expr, error);
00163 return success;
00164 }
00165
00166 template <typename E, typename INT>
00167 inline bool helper_check_eq_0(INT res, const char * func_name, const char * expr, bool res_2_strerror = false)
00168 {
00169 return helper_check_success<E>(res == 0, func_name, expr, res_2_strerror ? strerror(res) : 0);
00170 }
00171
00172 #define check_pthread_call(expr) \
00173 stxxl::helper_check_eq_0<stxxl::resource_error>(expr, STXXL_PRETTY_FUNCTION_NAME, __STXXL_STRING(expr), true)
00174
00175 template <typename E, typename INT>
00176 inline bool helper_check_ge_0(INT res, const char * func_name)
00177 {
00178 return helper_check_success<E>(res >= 0, func_name);
00179 }
00180
00181 #define stxxl_check_ge_0(expr, exception_type) \
00182 stxxl::helper_check_ge_0<exception_type>(expr, STXXL_PRETTY_FUNCTION_NAME)
00183
00184 template <typename E, typename INT>
00185 inline bool helper_check_ne_0(INT res, const char * func_name)
00186 {
00187 return helper_check_success<E>(res != 0, func_name);
00188 }
00189
00190 #define stxxl_check_ne_0(expr, exception_type) \
00191 stxxl::helper_check_ne_0<exception_type>(expr, STXXL_PRETTY_FUNCTION_NAME)
00192
00193 #ifdef BOOST_MSVC
00194
00195 #define stxxl_win_lasterror_exit(errmsg, exception_type) \
00196 { \
00197 TCHAR szBuf[80]; \
00198 LPVOID lpMsgBuf; \
00199 DWORD dw = GetLastError(); \
00200 FormatMessage( \
00201 FORMAT_MESSAGE_ALLOCATE_BUFFER | \
00202 FORMAT_MESSAGE_FROM_SYSTEM, \
00203 NULL, \
00204 dw, \
00205 MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), \
00206 (LPTSTR)&lpMsgBuf, \
00207 0, NULL); \
00208 std::ostringstream str_; \
00209 str_ << "Error in " << errmsg << ", error code " << dw << ": " << ((char *)lpMsgBuf); \
00210 LocalFree(lpMsgBuf); \
00211 throw exception_type(str_.str()); \
00212 }
00213
00214 #endif
00215
00217
00218 inline std::string
00219 stxxl_tmpfilename(std::string dir, std::string prefix)
00220 {
00221
00222 int rnd;
00223 char buffer[1024];
00224 std::string result;
00225
00226 #ifndef STXXL_BOOST_FILESYSTEM
00227 struct stat st;
00228 #endif
00229
00230 do
00231 {
00232 rnd = rand();
00233 sprintf(buffer, "%d", rnd);
00234 result = dir + prefix + buffer;
00235 }
00236 #ifdef STXXL_BOOST_FILESYSTEM
00237 while (boost::filesystem::exists(result));
00238
00239 return result;
00240 #else
00241 while (!lstat(result.c_str(), &st));
00242
00243 if (errno != ENOENT)
00244 stxxl_function_error(io_error);
00245
00246 return result;
00247 #endif
00248 }
00249
00251
00252 inline std::vector<std::string>
00253 split(const std::string & str, const std::string & sep)
00254 {
00255 std::vector<std::string> result;
00256 if (str.empty())
00257 return result;
00258
00259 std::string::size_type CurPos(0), LastPos(0);
00260 while (1)
00261 {
00262 CurPos = str.find(sep, LastPos);
00263 if (CurPos == std::string::npos)
00264 break;
00265
00266 std::string sub =
00267 str.substr(LastPos,
00268 std::string::size_type(CurPos -
00269 LastPos));
00270 if (sub.size())
00271 result.push_back(sub);
00272
00273 LastPos = CurPos + sep.size();
00274 }
00275
00276 std::string sub = str.substr(LastPos);
00277 if (sub.size())
00278 result.push_back(sub);
00279
00280 return result;
00281 }
00282
00284
00285 #define str2int(str) atoi(str.c_str())
00286
00287 inline std::string int2str(int i)
00288 {
00289 char buf[32];
00290 sprintf(buf, "%d", i);
00291 return std::string(buf);
00292 }
00293
00294 inline stxxl::int64 atoint64(const char * s)
00295 {
00296 #ifdef BOOST_MSVC
00297 return _atoi64(s);
00298 #else
00299 return atoll(s);
00300 #endif
00301 }
00302
00304
00305 #define STXXL_MIN(a, b) ((std::min)(a, b))
00306 #define STXXL_MAX(a, b) ((std::max)(a, b))
00307
00308 #define STXXL_L2_SIZE (512 * 1024)
00309
00310 #define div_and_round_up(a, b) ((a) / (b) + !(!((a) % (b))))
00311
00312 #define log2(x) (log(x) / log(2.))
00313
00315
00316
00317
00318 #ifdef HAVE_BUILTIN_EXPECT
00319 #define LIKELY(c) __builtin_expect((c), 1)
00320 #else
00321 #define LIKELY(c) c
00322 #endif
00323
00324 #ifdef HAVE_BUILTIN_EXPECT
00325 #define UNLIKELY(c) __builtin_expect((c), 0)
00326 #else
00327 #define UNLIKELY(c) c
00328 #endif
00329
00331
00332 inline uint64 longhash1(uint64 key_)
00333 {
00334 key_ += ~(key_ << 32);
00335 key_ ^= (key_ >> 22);
00336 key_ += ~(key_ << 13);
00337 key_ ^= (key_ >> 8);
00338 key_ += (key_ << 3);
00339 key_ ^= (key_ >> 15);
00340 key_ += ~(key_ << 27);
00341 key_ ^= (key_ >> 31);
00342 return key_;
00343 }
00344
00346
00347 template <class T>
00348 inline void swap_1D_arrays(T * a, T * b, unsigned_type size)
00349 {
00350 for (unsigned_type i = 0; i < size; ++i)
00351 std::swap(a[i], b[i]);
00352 }
00353
00355
00356 template <class T>
00357 class new_alloc;
00358
00359 template <typename T, typename U>
00360 struct new_alloc_rebind;
00361
00362 template <typename T>
00363 struct new_alloc_rebind<T, T>{
00364 typedef new_alloc<T> other;
00365 };
00366
00367 template <typename T, typename U>
00368 struct new_alloc_rebind {
00369 typedef std::allocator<U> other;
00370 };
00371
00372
00373
00374 template <class T>
00375 class new_alloc {
00376 public:
00377
00378 typedef T value_type;
00379 typedef T * pointer;
00380 typedef const T * const_pointer;
00381 typedef T & reference;
00382 typedef const T & const_reference;
00383 typedef std::size_t size_type;
00384 typedef std::ptrdiff_t difference_type;
00385
00386
00387 template <class U>
00388 struct rebind {
00389 typedef typename new_alloc_rebind<T, U>::other other;
00390 };
00391
00392
00393 pointer address(reference value) const
00394 {
00395 return &value;
00396 }
00397 const_pointer address(const_reference value) const
00398 {
00399 return &value;
00400 }
00401
00402 new_alloc() throw () { }
00403 new_alloc(const new_alloc &) throw () { }
00404 template <class U>
00405 new_alloc(const new_alloc<U> &) throw () { }
00406 ~new_alloc() throw () { }
00407
00408 template <class U>
00409 operator std::allocator<U>()
00410 {
00411 static std::allocator<U> helper_allocator;
00412 return helper_allocator;
00413 }
00414
00415
00416 size_type max_size() const throw ()
00417 {
00418 return (std::numeric_limits<std::size_t>::max) () / sizeof(T);
00419 }
00420
00421
00422 pointer allocate(size_type num, const void * = 0)
00423 {
00424 pointer ret = (pointer)(T::operator new (num * sizeof(T)));
00425 return ret;
00426 }
00427
00428
00429 void construct(pointer p, const T & value)
00430 {
00431
00432 new ((void *)p)T(value);
00433 }
00434
00435
00436 void destroy(pointer p)
00437 {
00438
00439 p->~T();
00440 }
00441
00442
00443 void deallocate(pointer p, size_type )
00444 {
00445 T::operator delete ((void *)p);
00446 }
00447 };
00448
00449
00450 template <class T1, class T2>
00451 inline bool operator == (const new_alloc<T1> &,
00452 const new_alloc<T2> &) throw ()
00453 {
00454 return true;
00455 }
00456
00457 template <class T1, class T2>
00458 inline bool operator != (const new_alloc<T1> &,
00459 const new_alloc<T2> &) throw ()
00460 {
00461 return false;
00462 }
00463
00464 __STXXL_END_NAMESPACE
00465
00466 #endif // !STXXL_UTILS_HEADER