Stxxl
1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/common/utils.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002-2006 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2007, 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 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 // STXXL_VERBOSE0 should be used for current debugging activity only, 00094 // and afterwards be replaced by STXXL_VERBOSE1 or higher. 00095 // Code that actively uses STXXL_VERBOSE0 should never get into a release. 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 //STXXL_VERBOSE0(" TMP:"<< dir.c_str() <<":"<< prefix.c_str()); 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 //#define HAVE_BUILTIN_EXPECT 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 // designed for typed_block (to use with std::vector ) 00374 template <class T> 00375 class new_alloc { 00376 public: 00377 // type definitions 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 // rebind allocator to type U, use new_alloc only if U == T 00387 template <class U> 00388 struct rebind { 00389 typedef typename new_alloc_rebind<T, U>::other other; 00390 }; 00391 00392 // return address of values 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 // return maximum number of elements that can be allocated 00416 size_type max_size() const throw () 00417 { 00418 return (std::numeric_limits<std::size_t>::max) () / sizeof(T); 00419 } 00420 00421 // allocate but don't initialize num elements of type T 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 // initialize elements of allocated storage p with value value 00429 void construct(pointer p, const T & value) 00430 { 00431 // initialize memory with placement new 00432 new ((void *)p)T(value); 00433 } 00434 00435 // destroy elements of initialized storage p 00436 void destroy(pointer p) 00437 { 00438 // destroy objects by calling their destructor 00439 p->~T(); 00440 } 00441 00442 // deallocate storage p of deleted elements 00443 void deallocate(pointer p, size_type /*num*/) 00444 { 00445 T::operator delete ((void *)p); 00446 } 00447 }; 00448 00449 // return that all specializations of this allocator are interchangeable 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