Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
thrill::common Namespace Reference

Contains many common tools and helpers shared by higher layers. See common. More...

Namespaces

namespace  qsort_local
 

Classes

class  Aggregate
 Calculate running aggregate statistics: feed it with values, and it will keep the minimum, the maximum, the average, the value number, and the standard deviation is values. More...
 
struct  alias_cast_helper
 
class  AtomicMovable
 This is a derivative of std::atomic which enables easier and less error-prone writing of move-only classes by implementing a move constructor. More...
 
class  BinaryHeap
 
class  CmdlineParser
 Command line parser which automatically fills variables and prints nice usage messages. More...
 
class  ComponentSum
 template for computing the component-wise sum of std::array or std::vector. More...
 
class  ComponentSum< std::array< Type, N >, Operation >
 Compute the component-wise sum of two std::array<T,N> of same sizes. More...
 
class  ComponentSum< std::vector< Type >, Operation >
 Compute the component-wise sum of two std::vector<T> of same sizes. More...
 
class  CountingPtr
 High-performance smart pointer used as a wrapping reference counting pointer. More...
 
class  DefaultCountingPtrDeleter
 default deleter for CountingPtr More...
 
class  Delegate
 
class  Delegate< R(A...), Allocator >
 This is a faster replacement than std::function. More...
 
class  ErrnoException
 An Exception which is thrown on system errors and contains errno information. More...
 
struct  FunctionTraits< ReturnType(*)(Args...)>
 specialize for function pointers More...
 
struct  FunctionTraits< ReturnType(ClassType::*)(Args...) const >
 specialize for pointers to const member function More...
 
struct  FunctionTraits< ReturnType(ClassType::*)(Args...)>
 specialize for pointers to mutable member function More...
 
struct  HashCrc32Fallback
 
struct  HashDataSwitch
 Hashing helper that decides what is hashed. More...
 
struct  HashDataSwitch< std::string >
 
struct  Identity
 Identity functor, very useful for default parameters. More...
 
struct  If
 
struct  If< false, TypeTrue, TypeFalse >
 
struct  index_sequence
 
struct  IndexSaver
 
struct  is_std_array
 test if is std::array<T> More...
 
struct  is_std_array< std::array< T, N > >
 
struct  is_std_pair
 
struct  is_std_pair< std::pair< S, T > >
 
struct  is_std_tuple
 test if is a std::tuple<...> More...
 
struct  is_std_tuple< std::tuple< Ts...> >
 
struct  is_std_vector
 test if is std::vector<T> More...
 
struct  is_std_vector< std::vector< T > >
 
class  ItemReaderToolsBase
 CRTP class to enhance item/memory reader classes with Varint decoding and String decoding. More...
 
class  ItemWriterToolsBase
 CRTP class to enhance item/memory writer classes with Varint encoding and String encoding. More...
 
class  JsonBeginObj
 A special class to output verbatim text. More...
 
class  JsonEndObj
 A special class to output verbatim text. More...
 
class  JsonLine
 JsonLine is an object used to aggregate a set of key:value pairs for output into a JSON log. More...
 
struct  JsonLinePutSwitch
 
class  JsonLogger
 JsonLogger is a receiver of JSON output objects for logging. More...
 
class  JsonVerbatim
 A special class to output verbatim text. More...
 
class  Log2
 
class  Log2< 0 >
 
class  Log2< 1 >
 
class  Log2Floor
 
class  Log2Floor< 0 >
 
class  Log2Floor< 1 >
 
class  Logger
 LOG and sLOG for development and debugging. More...
 
class  LoggerVoidify
 
class  LruCache
 This is an expected O(1) LRU cache which contains a set of (key,value) elements. More...
 
class  LruCacheSet
 This is an expected O(1) LRU cache which contains a set of key-only elements. More...
 
struct  make_index_sequence
 
struct  make_index_sequence_helper
 
struct  make_index_sequence_helper< 0, Indexes...>
 
class  Matrix
 A simple m x n dense matrix for generating statistics. More...
 
class  maximum
 
class  minimum
 
struct  NoOperation
 
struct  NoOperation< void >
 Specialized noop functor which returns a void. More...
 
class  OurConcurrentBoundedQueue
 This is a queue, similar to std::queue and tbb::concurrent_bounded_queue, except that it uses mutexes for synchronization. More...
 
class  OurConcurrentQueue
 This is a queue, similar to std::queue and tbb::concurrent_queue, except that it uses mutexes for synchronization. More...
 
class  ProfileTask
 
class  ProfileTaskRegistration
 
class  ProfileThread
 
class  RadixSort
 SortAlgorithm class for use with api::Sort() which calls radix_sort_CI() if K is small enough. More...
 
class  Range
 represents a 1 dimensional range (interval) [begin,end) More...
 
class  ReferenceCount
 Provides reference counting abilities for use with CountingPtr. More...
 
class  RingBuffer
 A ring (circular) buffer of static (non-growing) size allocated. More...
 
class  RunTimer
 RIAA class for running the timer until destruction. More...
 
class  Semaphore
 
class  SharedState
 
class  Singleton
 
class  SpacingLogger
 A logging class which outputs spaces between elements pushed via operator<<. More...
 
class  SplayzTree
 
class  StatsCounter
 This class provides a statistical counter that can easily be deactivated using a boolean template switch. More...
 
class  StatsCounter< ValueType_, false >
 
class  StatsCounter< ValueType_, true >
 
class  StatsTimerBase
 This class provides a statistical stop watch timer that can easily be deactivated using a boolean template switch. More...
 
class  StatsTimerBase< false >
 
class  StatsTimerBase< true >
 
class  StatsTimerBaseStarted
 
class  StatsTimerBaseStopped
 
class  StringView
 StringView is a reference to a part of a string, consisting of only a char pointer and a length. More...
 
class  SystemException
 An Exception which is thrown on system errors. More...
 
class  TabulationHashing
 Tabulation Hashing, see https://en.wikipedia.org/wiki/Tabulation_hashing. More...
 
class  ThreadBarrierLocking
 Implements a cyclic barrier using mutex locking and condition variables that can be used to synchronize threads. More...
 
class  ThreadBarrierSpinning
 Implements a cyclic barrier using atomics and a spin lock that can be used to synchronize threads. More...
 
class  ThreadPool
 ThreadPool starts a fixed number p of std::threads which process Jobs that are enqueued into a concurrent job queue. More...
 
class  TimedCounter
 
class  UIntPair
 Construct an 40-bit or 48-bit unsigned integer stored in five or six bytes. More...
 
class  VariadicCallEnumerateImpl
 helper for VariadicCallEnumerate: general recursive case More...
 
class  VariadicCallEnumerateImpl< Index, 0, Functor >
 helper for VariadicCallEnumerate: base case More...
 
class  VariadicMapEnumerateImpl
 helper for VariadicMapEnumerate: general recursive case More...
 
class  VariadicMapEnumerateImpl< Index, 0, Functor >
 helper for VariadicMapEnumerate: base case More...
 
class  Vector
 A compile-time fixed-length D-dimensional point with double precision. More...
 
class  VectorConcat
 Compute the concatenation of two std::vector<T>s. More...
 
class  VVector
 A variable-length D-dimensional point with double precision. More...
 
class  ZipfDistribution
 A class for producing random integers distributed according to the Zipf-Mandelbrot probability mass function: More...
 

Typedefs

template<typename Type >
using Array = Type[]
 A template to make writing temporary arrays easy: Array<int>{ 1, 2, 3 }. More...
 
template<typename T >
using ConcurrentBoundedQueue = OurConcurrentBoundedQueue< T >
 
template<typename T , typename Allocator >
using ConcurrentQueue = OurConcurrentQueue< T, Allocator >
 
using FakeStatsTimer = StatsTimerBase< false >
 
using FakeStatsTimerStart = StatsTimerBaseStarted< false >
 
using FakeStatsTimerStopped = StatsTimerBaseStopped< false >
 
template<typename T >
using hash = HashCrc32< T >
 Select a hashing method. More...
 
template<typename T >
using HashCrc32 = HashCrc32Fallback< T >
 
template<typename T >
using HashTabulated = TabulationHashing< sizeof(T)>
 Tabulation hashing. More...
 
template<typename T >
using is_trivially_copyable = std::is_trivially_copyable< T >
 
template<typename Key , typename T , typename Compare = std::less<Key>>
using logger_map = std::map< Key, T, Compare, LoggerAllocator< std::pair< const Key, T > > >
 deque without malloc tracking More...
 
template<typename Type >
using LoggerAllocator = mem::FixedAllocator< Type, g_logger_mem_manager >
 
using StatsTimer = StatsTimerBase< true >
 
using StatsTimerStart = StatsTimerBaseStarted< true >
 
using StatsTimerStopped = StatsTimerBaseStopped< true >
 
using StringCount = std::pair< mem::by_string, size_t >
 
using ThreadBarrier = ThreadBarrierSpinning
 
using uint40 = UIntPair< uint8_t >
 Construct a 40-bit unsigned integer stored in five bytes. More...
 
using uint48 = UIntPair< uint16_t >
 Construct a 48-bit unsigned integer stored in six bytes. More...
 

Functions

template<typename T >
T abs_diff (const T &a, const T &b)
 absolute difference, which also works for unsigned types More...
 
template<typename IntegerType , unsigned bits = (8* sizeof(IntegerType))>
static IntegerType AddTruncToType (const IntegerType &a, const IntegerType &b)
 
template<typename To , typename From >
To & alias_cast (From &raw_data)
 
template<typename To , typename From >
const To & alias_cast (const From &raw_data)
 
template<typename Functor , typename Tuple >
auto ApplyTuple (Functor &&f, Tuple &&t)
 Call the functor f with the contents of t as arguments. More...
 
template<typename Functor , typename Tuple , std::size_t... Is>
auto ApplyTupleImpl (Functor &&f, Tuple &&t, common::index_sequence< Is...>)
 
static size_t CalcOneFactorPeer (size_t r, size_t p, size_t n)
 Calculate a Perfect Matching (1-Factor) on a Complete Graph. More...
 
static size_t CalcOneFactorSize (size_t n)
 Number of rounds in Perfect Matching (1-Factor). More...
 
static Range CalculateLocalRange (size_t global_size, size_t p, size_t i)
 
uint32_t crc32_slicing_by_8 (uint32_t crc, const void *data, size_t length)
 
template<typename... Args>
std::thread CreateThread (Args &&...args)
 create a std::thread and repeat creation if it fails More...
 
static bool EndsWith (const std::string &str, const std::string &match)
 Checks if the given match string is located at the end of this string. More...
 
std::string EscapeHtml (const std::string &str)
 Escape string using HTML entities. More...
 
template<typename Integral >
static size_t ffs (Integral x)
 ffs (find first set bit) - generic implementation More...
 
std::string FormatIecUnits (uint64_t number)
 Format number as something like 1 TiB. More...
 
void FormatNameForThisThread (std::ostream &os)
 Outputs the name of the current thread or 'unknown [id]'. More...
 
std::string FormatSiUnits (uint64_t number)
 Format number as something like 1 TB. More...
 
template<typename T >
T from_cstr (const char *nptr, char **endptr=nullptr, int base=10)
 Number parsing helpers, wraps strto{f,d,ld,l,ul,ll,ull}() via type switch. More...
 
template<>
double from_cstr< double > (const char *nptr, char **endptr, int)
 
template<>
float from_cstr< float > (const char *nptr, char **endptr, int)
 
template<>
long from_cstr< long > (const char *nptr, char **endptr, int base)
 
template<>
long double from_cstr< long double > (const char *nptr, char **endptr, int)
 
template<>
long long from_cstr< long long > (const char *nptr, char **endptr, int base)
 
template<>
unsigned long from_cstr< unsigned long > (const char *nptr, char **endptr, int base)
 
template<>
unsigned long long from_cstr< unsigned long long > (const char *nptr, char **endptr, int base)
 
template<typename Type >
static bool from_str (const std::string &str, Type &outval)
 Template transformation function which uses std::istringstream to parse any istreamable type from a std::string. More...
 
std::string GetHostname ()
 get hostname More...
 
std::string GetNameForThisThread ()
 Returns the name of the current thread or 'unknown [id]'. More...
 
static uint64_t Hash128to64 (const uint64_t upper, const uint64_t lower)
 
static uint32_t Hash64to32 (uint64_t key)
 Returns a uint32_t hash of a uint64_t. More...
 
std::string Hexdump (const void *const data, size_t size)
 Dump a (binary) string as a sequence of hexadecimal pairs. More...
 
std::string Hexdump (const std::string &str)
 Dump a (binary) string as a sequence of hexadecimal pairs. More...
 
template<typename Type >
std::string HexdumpItem (const Type &t)
 Dump a (binary) item as a sequence of hexadecimal pairs. More...
 
template<typename IntegerType >
static IntegerType IntegerDivRoundUp (const IntegerType &n, const IntegerType &k)
 calculate n div k with rounding up More...
 
template<typename IntegerType >
static unsigned int IntegerLog2Ceil (const IntegerType &i)
 calculate the log2 ceiling of an integer type (by repeated bit shifts) More...
 
template<typename IntegerType >
static unsigned int IntegerLog2Floor (IntegerType i)
 calculate the log2 floor of an integer type (by repeated bit shifts) More...
 
static bool IsPowerOfTwo (size_t i)
 does what it says. More...
 
template<typename Iterator , typename Glue >
static std::string Join (const Glue &glue, Iterator first, Iterator last)
 Join a sequence of strings by some glue string between each pair from the sequence. More...
 
template<typename Container , typename Glue >
static std::string Join (const Glue &glue, const Container &parts)
 Join a Container (like a vector) of strings using some glue string between each pair from the sequence. More...
 
void LogCmdlineParams (JsonLogger &logger)
 
template<class C , typename R , typename... A>
Delegate< R(A...)> make_delegate (C *const object_ptr, R(C::*const method_ptr)(A...)) noexcept
 constructor for wrapping a class::method with object pointer. More...
 
template<class C , typename R , typename... A>
Delegate< R(A...)> make_delegate (C &object_ptr, R(C::*const method_ptr)(A...)) noexcept
 constructor for wrapping a class::method with object reference. More...
 
template<class C , typename R , typename... A>
Delegate< R(A...)> make_delegate (C const &object_ptr, R(C::*const method_ptr)(A...) const) noexcept
 constructor for wrapping a const class::method with object reference. More...
 
template<typename Type , typename... Args>
CountingPtr< Type > MakeCounting (Args &&...args)
 
void MakePipe (int out_pipefds[2])
 create a pair of pipe file descriptors More...
 
template<typename Type , typename Functor >
auto MapVector (const std::vector< Type > &input, const Functor &f) -> std::vector< typename std::result_of< Functor(Type)>::type >
 
template<typename T >
static constexpr const Tmax (const T &a, const T &b)
 template for constexpr max, because std::max is not good enough. More...
 
template<typename T >
static constexpr const Tmin (const T &a, const T &b)
 template for constexpr min, because std::min is not good enough. More...
 
void NameThisThread (const mem::by_string &name)
 Defines a name for the current thread, only if no name was set previously. More...
 
static bool operator!= (const std::string &a, const StringView &b) noexcept
 
template<typename A >
std::ostream & operator<< (std::ostream &os, const CountingPtr< A > &c)
 print pointer More...
 
static bool operator== (const std::string &a, const StringView &b) noexcept
 
bool ParseSiIecUnits (const char *str, uint64_t &size, char default_unit)
 
void PortSetCloseOnExec (int fd)
 set FD_CLOEXEC on file descriptor (if possible) More...
 
static JsonLinePut (JsonLine &line, bool const &value)
 
static JsonLinePut (JsonLine &line, int const &value)
 
static JsonLinePut (JsonLine &line, unsigned int const &value)
 
static JsonLinePut (JsonLine &line, long const &value)
 
static JsonLinePut (JsonLine &line, unsigned long const &value)
 
static JsonLinePut (JsonLine &line, long long const &value)
 
static JsonLinePut (JsonLine &line, unsigned long long const &value)
 
static JsonLinePut (JsonLine &line, double const &value)
 
static JsonLinePut (JsonLine &line, const char *const &str)
 
static JsonLinePut (JsonLine &line, std::string const &str)
 
template<typename Type , std::size_t N>
static JsonLinePut (JsonLine &line, const Type(&arr)[N])
 
template<typename Type >
static JsonLinePut (JsonLine &line, std::initializer_list< Type > const &list)
 
template<typename Type >
static JsonLinePut (JsonLine &line, std::vector< Type > const &vec)
 
template<typename Type , std::size_t N>
static JsonLinePut (JsonLine &line, std::array< Type, N > const &arr)
 
static JsonLinePut (JsonLine &line, JsonVerbatim const &verbatim)
 
template<typename Compare , typename Iterator >
void qsort_three_pivots (Iterator left, Iterator right, Compare cmp)
 
template<typename Compare , typename Iterator >
void qsort_two_pivots_yaroslavskiy (Iterator lo, Iterator hi, Compare cmp)
 
template<size_t MaxDepth, typename Iterator , typename Char , typename Comparator = std::less<typename std::iterator_traits<Iterator>::value_type>, typename SubSorter = NoOperation<void>>
static void radix_sort_CI (Iterator begin, Iterator end, size_t K, const Comparator &cmp, const SubSorter &sub_sort, size_t depth, Char *char_cache)
 Internal helper method, use radix_sort_CI below. More...
 
template<size_t MaxDepth, typename Iterator , typename Comparator = std::less<typename std::iterator_traits<Iterator>::value_type>, typename SubSorter = NoOperation<void>>
static void radix_sort_CI (Iterator begin, Iterator end, size_t K, const Comparator &cmp=Comparator(), const SubSorter &sub_sort=SubSorter())
 Radix sort the iterator range [begin,end). More...
 
template<typename RandomEngine = std::default_random_engine>
static std::string RandomString (std::string::size_type size, RandomEngine rng, const std::string &letters="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
 Generate a random string of given length. More...
 
std::string & ReplaceAll (std::string &str, const std::string &needle, const std::string &instead)
 Replace all occurrences of needle in str. More...
 
template<typename Integral >
static Integral RoundDownToPowerOfTwo (Integral n)
 does what it says. More...
 
template<typename Integral >
static Integral RoundUpToPowerOfTwo (Integral n)
 does what it says. More...
 
void SetCpuAffinity (std::thread &thread, size_t cpu_id)
 set cpu/core affinity of a thread More...
 
void SetCpuAffinity (size_t cpu_id)
 set cpu/core affinity of current thread More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splay (const Key &k, Tree *t, const Compare &cmp)
 
template<typename Tree , typename Compare >
void splay_check (const Tree *t, const Tree *&out_tmin, const Tree *&out_tmax, const Compare &cmp)
 check the tree order, recursively calculate min and max elements More...
 
template<typename Tree , typename Compare >
void splay_check (const Tree *t, const Compare &cmp)
 check the tree order More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splay_erase (const Key &k, Tree *&t, const Compare &cmp)
 
template<typename Tree , typename Compare >
Tree * splay_erase_top (Tree *&t, const Compare &cmp)
 
template<typename Tree , typename Compare >
Tree * splay_insert (Tree *nn, Tree *t, const Compare &cmp)
 
template<typename Tree >
void splay_print (Tree *t, size_t d=0)
 print the tree More...
 
template<typename Tree , typename Functor >
void splay_traverse_preorder (const Functor &f, const Tree *t)
 traverse the tree in preorder More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splayz (const Key &k, Tree *t, const Compare &cmp)
 
template<typename Tree , typename Compare >
void splayz_check (const Tree *t, const Tree *&out_tmin, const Tree *&out_tmax, size_t &out_size, const Compare &cmp)
 check the tree order, recursively calculate min and max elements More...
 
template<typename Tree , typename Compare >
void splayz_check (const Tree *t, const Compare &cmp)
 check the tree order More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splayz_erase (const Key &k, Tree *&t, const Compare &cmp)
 
template<typename Tree , typename Compare >
Tree * splayz_erase_top (Tree *&t, const Compare &cmp)
 
template<typename Tree , typename Compare >
Tree * splayz_insert (Tree *nn, Tree *t, const Compare &cmp)
 
template<typename Tree >
void splayz_print (Tree *t, size_t d=0)
 print the tree More...
 
template<typename Tree >
Tree * splayz_rank (size_t r, Tree *t)
 
template<typename Tree >
size_t splayz_size (Tree *x)
 
template<typename Tree , typename Functor >
void splayz_traverse_preorder (const Functor &f, const Tree *t)
 traverse the tree in preorder More...
 
std::vector< std::string > Split (const std::string &str, char sep, std::string::size_type limit=std::string::npos)
 Split the given string at each separator character into distinct substrings. More...
 
std::vector< std::string > Split (const std::string &str, const std::string &sepstr, std::string::size_type limit=std::string::npos)
 Split the given string at each separator string into distinct substrings. More...
 
std::vector< std::string > Split (const std::string &str, const std::string &sep, unsigned int min_fields, unsigned int limit_fields)
 
void SplitRef (const std::string &str, char sep, std::vector< std::string > &out)
 
template<typename F >
static void SplitView (const std::string &str, char sep, F &&callback, std::string::size_type limit=std::string::npos)
 Split the given string at each separator character into distinct substrings, and call the given callback for each substring, represented by two iterators begin and end. More...
 
void StartLinuxProcStatsProfiler (ProfileThread &sched, JsonLogger &logger)
 launch profiler task More...
 
static bool StartsWith (const std::string &str, const std::string &match)
 Checks if the given match string is located at the start of this string. More...
 
template<typename String = std::string>
String str_snprintf (size_t max_size, const char *fmt,...) THRILL_ATTRIBUTE_FORMAT_PRINTF(2
 Helper for using sprintf to format into std::string and also to_string converters. More...
 
template<typename String >
String String str_snprintf (size_t max_size, const char *fmt,...)
 
template<typename String = std::string>
String str_sprintf (const char *fmt,...) THRILL_ATTRIBUTE_FORMAT_PRINTF(1
 Helper for using sprintf to format into std::string and also to_string converters. More...
 
template<typename String >
String String str_sprintf (const char *fmt,...)
 
template<typename A >
void swap (CountingPtr< A > &a1, CountingPtr< A > &a2) noexcept
 
template<typename Type >
static std::string to_str (const Type &t)
 
std::string & Trim (std::string &str, const std::string &drop=" \r\n\t")
 Trims the given string in-place on the left and right. More...
 
template<typename U >
void UNUSED (U &&)
 
template<size_t Size, typename Functor >
void VariadicCallEnumerate (Functor &&f)
 Call a generic functor (like a generic lambda) for the integers [0,Size). More...
 
template<size_t Begin, size_t End, typename Functor >
void VariadicCallEnumerate (Functor &&f)
 Call a generic functor (like a generic lambda) for the integers [Begin,End). More...
 
template<typename Functor , typename... Args>
void VariadicCallForeachIndex (Functor &&f, Args &&...args)
 
template<size_t Index, typename Functor , typename Arg >
void VariadicCallForeachIndexImpl (Functor &&f, Arg &&arg)
 helper for VariadicCallForeachIndex: base case More...
 
template<size_t Index, typename Functor , typename Arg , typename... MoreArgs>
void VariadicCallForeachIndexImpl (Functor &&f, Arg &&arg, MoreArgs &&...rest)
 helper for VariadicCallForeachIndex: general recursive case More...
 
template<size_t Size, typename Functor >
auto VariadicMapEnumerate (Functor &&f)
 
template<size_t Begin, size_t End, typename Functor >
auto VariadicMapEnumerate (Functor &&f)
 
template<typename Functor , typename... Args>
auto VariadicMapIndex (Functor &&f, Args &&...args)
 
template<size_t Index, typename Functor , typename Arg >
auto VariadicMapIndexImpl (Functor &&f, Arg &&arg)
 helper for VariadicMapIndex: base case More...
 
template<size_t Index, typename Functor , typename Arg , typename... MoreArgs>
auto VariadicMapIndexImpl (Functor &&f, Arg &&arg, MoreArgs &&...rest)
 helper for VariadicMapIndex: general recursive case More...
 
template<typename T , size_t N>
static std::string VecToStr (const std::array< T, N > &data)
 Logging helper to print arrays as [a1,a2,a3,...]. More...
 
template<typename T >
static std::string VecToStr (const std::vector< T > &data)
 Logging helper to print vectors as [a1,a2,a3,...]. More...
 

Variables

const uint32_t crc_tableil8_o32 [256]
 
const uint32_t crc_tableil8_o40 [256]
 
const uint32_t crc_tableil8_o48 [256]
 
const uint32_t crc_tableil8_o56 [256]
 
const uint32_t crc_tableil8_o64 [256]
 
const uint32_t crc_tableil8_o72 [256]
 
const uint32_t crc_tableil8_o80 [256]
 
const uint32_t crc_tableil8_o88 [256]
 
static constexpr unsigned g_cache_line_size = 64
 Finding cache line size is hard - we assume 64 byte. More...
 
static constexpr bool g_debug_mode = !g_ndebug
 debug mode is active, if NDEBUG is false. More...
 
static constexpr bool g_debug_push_file = false
 
mem::Manager g_logger_mem_manager (nullptr,"Logger")
 memory manager singleton for Logger More...
 
static constexpr bool g_ndebug = false
 global ndebug flag as a boolean, NDEBUG means no debug in Release mode. More...
 
static constexpr bool g_profile_thread = true
 global flag to enable background profiler thread More...
 
static constexpr bool g_self_verify = g_debug_mode
 
static std::mutex s_logger_mutex
 mutex for log output More...
 
static std::mutex s_mutex
 mutex for s_threads map More...
 
static logger_map
< std::thread::id, StringCount
s_threads
 map thread id -> (name, message counter) More...
 
class thrill::common::UIntPair THRILL_ATTRIBUTE_PACKED
 

Detailed Description

Contains many common tools and helpers shared by higher layers. See common.

Typedef Documentation

using Array = Type[]

A template to make writing temporary arrays easy: Array<int>{ 1, 2, 3 }.

Definition at line 62 of file json_logger.hpp.

using ConcurrentQueue = OurConcurrentQueue<T, Allocator>

Definition at line 127 of file concurrent_queue.hpp.

Definition at line 284 of file stats_timer.hpp.

Definition at line 285 of file stats_timer.hpp.

Definition at line 286 of file stats_timer.hpp.

using hash = HashCrc32<T>

Select a hashing method.

Definition at line 257 of file hash.hpp.

Definition at line 200 of file hash.hpp.

using HashTabulated = TabulationHashing<sizeof(T)>

Tabulation hashing.

Definition at line 253 of file hash.hpp.

using is_trivially_copyable = std::is_trivially_copyable<T>

Definition at line 108 of file defines.hpp.

using logger_map = std::map<Key, T, Compare, LoggerAllocator<std::pair<const Key, T> > >

deque without malloc tracking

Definition at line 41 of file logger.cpp.

Definition at line 36 of file logger.cpp.

using StatsTimer = StatsTimerBase<true>

Definition at line 280 of file stats_timer.hpp.

Definition at line 281 of file stats_timer.hpp.

Definition at line 282 of file stats_timer.hpp.

using StringCount = std::pair<mem::by_string, size_t>

Definition at line 33 of file logger.cpp.

Definition at line 165 of file thread_barrier.hpp.

using uint40 = UIntPair<uint8_t>

Construct a 40-bit unsigned integer stored in five bytes.

Definition at line 258 of file uint_types.hpp.

using uint48 = UIntPair<uint16_t>

Construct a 48-bit unsigned integer stored in six bytes.

Definition at line 261 of file uint_types.hpp.

Function Documentation

T thrill::common::abs_diff ( const T a,
const T b 
)

absolute difference, which also works for unsigned types

Definition at line 104 of file math.hpp.

Referenced by Context::Launch(), and MergeNode< ValueType, Comparator, kNumInputs >::MainOp().

To& thrill::common::alias_cast ( From &  raw_data)
const To& thrill::common::alias_cast ( const From &  raw_data)
auto thrill::common::ApplyTuple ( Functor &&  f,
Tuple &&  t 
)

Call the functor f with the contents of t as arguments.

Definition at line 71 of file meta.hpp.

References ApplyTupleImpl().

auto thrill::common::ApplyTupleImpl ( Functor &&  f,
Tuple &&  t,
common::index_sequence< Is...>   
)

Definition at line 64 of file meta.hpp.

Referenced by ApplyTuple().

static size_t thrill::common::CalcOneFactorPeer ( size_t  r,
size_t  p,
size_t  n 
)
inlinestatic

Calculate a Perfect Matching (1-Factor) on a Complete Graph.

Used by collective network algorithms.

Parameters
rround [0..n-1) of matching
prank of this processor 0..n-1
nnumber of processors (graph size)
Returns
peer processor in this round

Definition at line 200 of file math.hpp.

References CalcOneFactorSize().

Referenced by Group::OneFactorPeer().

static size_t thrill::common::CalcOneFactorSize ( size_t  n)
inlinestatic

Number of rounds in Perfect Matching (1-Factor).

Definition at line 187 of file math.hpp.

Referenced by CalcOneFactorPeer(), and Group::OneFactorSize().

static Range thrill::common::CalculateLocalRange ( size_t  global_size,
size_t  p,
size_t  i 
)
inlinestatic

given a global range [0,global_size) and p PEs to split the range, calculate the [local_begin,local_end) index range assigned to the PE i.

Definition at line 171 of file math.hpp.

References min().

Referenced by Context::CalculateLocalRange(), Context::CalculateLocalRangeOnHost(), DistributeNode< ValueType >::Execute(), DuplicateDetection::WriteEncodedHashes(), and LocationDetection< thrill::api::JoinNode::HashCount >::WriteOccurenceCounts().

uint32_t crc32_slicing_by_8 ( uint32_t  crc,
const void *  data,
size_t  length 
)
std::thread thrill::common::CreateThread ( Args &&...  args)

create a std::thread and repeat creation if it fails

Definition at line 42 of file porting.hpp.

References LOG1.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm >::MainOp(), and thrill::api::RunLoopbackThreads().

static bool thrill::common::EndsWith ( const std::string &  str,
const std::string &  match 
)
inlinestatic

Checks if the given match string is located at the end of this string.

Definition at line 67 of file string.hpp.

Referenced by thrill::vfs::IsCompressed(), thrill::vfs::OpenReadStream(), thrill::vfs::OpenWriteStream(), thrill::vfs::SysOpenReadStream(), and thrill::vfs::SysOpenWriteStream().

std::string EscapeHtml ( const std::string &  str)

Escape string using HTML entities.

Definition at line 180 of file string.cpp.

static size_t thrill::common::ffs ( Integral  x)
inlinestatic

ffs (find first set bit) - generic implementation

Definition at line 93 of file math.hpp.

Referenced by Group::BroadcastBinomialTree().

std::string FormatIecUnits ( uint64_t  number)

Format number as something like 1 TiB.

Format a byte size using IEC (Ki, Mi, Gi, Ti) suffixes (powers of two). Returns "123 Ki" or similar.

Definition at line 289 of file string.cpp.

Referenced by Context::Launch(), main(), and MemoryConfig::print().

void thrill::common::FormatNameForThisThread ( std::ostream &  os)

Outputs the name of the current thread or 'unknown [id]'.

Definition at line 56 of file logger.cpp.

References s_mutex, and s_threads.

Referenced by GetNameForThisThread(), Logger::Logger(), and SpacingLogger::SpacingLogger().

std::string FormatSiUnits ( uint64_t  number)

Format number as something like 1 TB.

Format a byte size using SI (K, M, G, T) suffixes (powers of ten). Returns "123 M" or similar.

Definition at line 270 of file string.cpp.

T thrill::common::from_cstr ( const char *  nptr,
char **  endptr = nullptr,
int  base = 10 
)

Number parsing helpers, wraps strto{f,d,ld,l,ul,ll,ull}() via type switch.

double thrill::common::from_cstr< double > ( const char *  nptr,
char **  endptr,
int   
)
inline

Definition at line 173 of file string.hpp.

float thrill::common::from_cstr< float > ( const char *  nptr,
char **  endptr,
int   
)
inline

Definition at line 166 of file string.hpp.

long thrill::common::from_cstr< long > ( const char *  nptr,
char **  endptr,
int  base 
)
inline

Definition at line 190 of file string.hpp.

long double thrill::common::from_cstr< long double > ( const char *  nptr,
char **  endptr,
int   
)
inline

Definition at line 180 of file string.hpp.

long long thrill::common::from_cstr< long long > ( const char *  nptr,
char **  endptr,
int  base 
)
inline

Definition at line 204 of file string.hpp.

unsigned long thrill::common::from_cstr< unsigned long > ( const char *  nptr,
char **  endptr,
int  base 
)
inline

Definition at line 196 of file string.hpp.

unsigned long long thrill::common::from_cstr< unsigned long long > ( const char *  nptr,
char **  endptr,
int  base 
)
inline

Definition at line 210 of file string.hpp.

static bool thrill::common::from_str ( const std::string &  str,
Type &  outval 
)
inlinestatic

Template transformation function which uses std::istringstream to parse any istreamable type from a std::string.

Returns true only if the whole string was parsed.

Definition at line 148 of file string.hpp.

std::string GetHostname ( )

get hostname

Definition at line 139 of file porting.cpp.

std::string GetNameForThisThread ( )

Returns the name of the current thread or 'unknown [id]'.

Definition at line 79 of file logger.cpp.

References FormatNameForThisThread().

static uint64_t thrill::common::Hash128to64 ( const uint64_t  upper,
const uint64_t  lower 
)
inlinestatic

This is the Hash128to64 function from Google's cityhash (available under the MIT License).

Definition at line 63 of file hash.hpp.

Referenced by ReduceByHash< Key, HashFunction >::operator()().

static uint32_t thrill::common::Hash64to32 ( uint64_t  key)
inlinestatic

Returns a uint32_t hash of a uint64_t.

This comes from http://www.concentric.net/~ttwang/tech/inthash.htm

This hash gives no guarantees on the cryptographic suitability nor the quality of randomness produced, and the mapping may change in the future.

Definition at line 82 of file hash.hpp.

std::string Hexdump ( const void *const  data,
size_t  size 
)

Dump a (binary) string as a sequence of hexadecimal pairs.

Parameters
databinary data to output in hex
sizelength of binary data
Returns
string of hexadecimal pairs

Definition at line 20 of file string.cpp.

Referenced by StreamSink::AppendPinnedBlock(), Hexdump(), HexdumpItem(), Group::MaybeHexdump(), Socket::MaybeHexdump(), MixStream::OnStreamBlock(), and CatStream::OnStreamBlock().

std::string Hexdump ( const std::string &  str)

Dump a (binary) string as a sequence of hexadecimal pairs.

Parameters
strbinary data to output in hex
Returns
string of hexadecimal pairs

Definition at line 42 of file string.cpp.

References Hexdump().

std::string thrill::common::HexdumpItem ( const Type &  t)

Dump a (binary) item as a sequence of hexadecimal pairs.

Definition at line 42 of file string.hpp.

References Hexdump().

Referenced by BlockReader< CatBlockSource >::Next().

static IntegerType thrill::common::IntegerDivRoundUp ( const IntegerType &  n,
const IntegerType &  k 
)
inlinestatic

calculate n div k with rounding up

Definition at line 123 of file math.hpp.

static unsigned int thrill::common::IntegerLog2Ceil ( const IntegerType &  i)
inlinestatic
static unsigned int thrill::common::IntegerLog2Floor ( IntegerType  i)
inlinestatic

calculate the log2 floor of an integer type (by repeated bit shifts)

Definition at line 28 of file math.hpp.

Referenced by IntegerLog2Ceil().

static bool thrill::common::IsPowerOfTwo ( size_t  i)
inlinestatic

does what it says.

Definition at line 60 of file math.hpp.

Referenced by BlockPool::AllocateByteBlock(), and Group::AllReduceSelect().

static std::string thrill::common::Join ( const Glue &  glue,
Iterator  first,
Iterator  last 
)
inlinestatic

Join a sequence of strings by some glue string between each pair from the sequence.

The sequence in given as a range between two iterators.

Parameters
gluestring to glue
firstthe beginning iterator of the range to join
lastthe ending iterator of the range to join
Returns
string constructed from the range with the glue between them.

Definition at line 266 of file string.hpp.

Referenced by Join(), thrill::data::operator<<(), examples::page_rank::PageRank(), examples::page_rank::PageRankJoin(), ByteBlock::pin_count_str(), ReadBinaryNode< ValueType >::ReadBinaryNode(), and ReadLinesNode::ReadLinesNode().

static std::string thrill::common::Join ( const Glue &  glue,
const Container &  parts 
)
inlinestatic

Join a Container (like a vector) of strings using some glue string between each pair from the sequence.

Parameters
gluestring to glue
partsthe vector of strings to join
Returns
string constructed from the vector with the glue between them.

Definition at line 290 of file string.hpp.

References Join().

void LogCmdlineParams ( JsonLogger &  logger)

try to figure out the command line options of the current process and log it to json logger

Definition at line 64 of file porting.cpp.

References ReplaceAll(), thrill::mem::to_string(), and UNUSED().

Referenced by HostContext::HostContext().

Delegate< R(A...)> make_delegate ( C *const  object_ptr,
R(C::*)(A...)  method_ptr 
)
noexcept

constructor for wrapping a class::method with object pointer.

constructor for wrapping a const class::method with object pointer.

Definition at line 427 of file delegate.hpp.

Delegate<R(A ...)> thrill::common::make_delegate ( C &  object_ptr,
R(C::*)(A...)  method_ptr 
)
noexcept

constructor for wrapping a class::method with object reference.

Definition at line 443 of file delegate.hpp.

Delegate<R(A ...)> thrill::common::make_delegate ( C const &  object_ptr,
R(C::*)(A...) const  method_ptr 
)
noexcept

constructor for wrapping a const class::method with object reference.

Definition at line 451 of file delegate.hpp.

CountingPtr<Type> thrill::common::MakeCounting ( Args &&...  args)

Definition at line 240 of file counting_ptr.hpp.

Referenced by thrill::data::ConstructDynBlockSource().

void MakePipe ( int  out_pipefds[2])

create a pair of pipe file descriptors

Definition at line 48 of file porting.cpp.

References O_BINARY, and PortSetCloseOnExec().

Referenced by SelectDispatcher::SelectDispatcher(), thrill::vfs::SysOpenReadStream(), and thrill::vfs::SysOpenWriteStream().

auto thrill::common::MapVector ( const std::vector< Type > &  input,
const Functor &  f 
) -> std::vector<typename std::result_of<Functor(Type)>::type>
inline

apply the Functor to each item in a std::vector<T> and return a new std::vector<U> with different type.

Definition at line 126 of file functional.hpp.

static constexpr const T& thrill::common::max ( const T a,
const T b 
)
inlinestatic

template for constexpr max, because std::max is not good enough.

Definition at line 93 of file functional.hpp.

Referenced by Aggregate< Type_ >::Add(), Manager::add(), BlockPool::AllocateByteBlock(), CmdlineParser::CalcOptMax(), CmdlineParser::CalcParamMax(), MemoryFile::discard(), LocationDetection< thrill::api::JoinNode::HashCount >::Flush(), MixStream::GetWriters(), CatStream::GetWriters(), UIntPair< High_ >::high_max(), Range::Invalid(), UIntPair< High_ >::low_max(), main(), BlockPool::MapExternalBlock(), UIntPair< High_ >::max(), numeric_limits< thrill::common::UIntPair< HighType > >::max(), Pool::max_size(), BlockManager::new_blocks_int(), Aggregate< Type_ >::operator+(), Aggregate< Type_ >::operator+=(), OutputSVG(), examples::select::PickPivots(), examples::suffix_sorting::PrefixDoublingDementiev(), examples::suffix_sorting::PrefixDoublingDiscardingDementiev(), examples::suffix_sorting::PrefixQuadrupling(), Context::PrintCollectiveMeanStdev(), CmdlineParser::PrintResult(), ReadBinaryNode< ValueType >::ReadBinaryNode(), RunJoinPageRankEdgePerLine(), RunPageRankEdgePerLine(), SyscallFile::serve(), WincallFile::serve(), StatsCounter< ValueType_, true >::set_max(), MemoryFile::set_size(), Select::SetException(), Select::SetRead(), Select::SetWrite(), ReduceBucketHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig, IndexFunction, KeyEqualFunction >::SpillSmallestPartition(), Connection::SyncRecv(), Connection::SyncSend(), Connection::SyncSendRecv(), and SortNode< ValueType, CompareFunction, SortAlgorithm >::wanted_sample_size().

static constexpr const T& thrill::common::min ( const T a,
const T b 
)
inlinestatic
void NameThisThread ( const mem::by_string &  name)

Defines a name for the current thread, only if no name was set previously.

Defines a name for the current thread.

Definition at line 50 of file logger.cpp.

References s_mutex, and s_threads.

Referenced by thrill::api::RunLocalSameThread(), thrill::api::RunLoopbackThreads(), and DispatcherThread::Work().

static bool thrill::common::operator!= ( const std::string &  a,
const StringView &  b 
)
inlinestaticnoexcept

Definition at line 143 of file string_view.hpp.

std::ostream& thrill::common::operator<< ( std::ostream &  os,
const CountingPtr< A > &  c 
)

print pointer

Definition at line 253 of file counting_ptr.hpp.

static bool thrill::common::operator== ( const std::string &  a,
const StringView &  b 
)
inlinestaticnoexcept

Definition at line 138 of file string_view.hpp.

Referenced by Delegate< R(A...), Allocator >::operator!=().

bool ParseSiIecUnits ( const char *  str,
uint64_t &  size,
char  default_unit 
)

Parse a string like "343KB" or " 44 GiB " into the corresponding size in bytes.

Parse a string like "343KB" or "44 GiB" into the corresponding size in bytes. Returns the number of bytes and sets ok = true if the string could be parsed correctly. If no units indicator is given, use def_unit in k/m/g/t/p (powers of ten) or in K/M/G/T/P (power of two).

Definition at line 200 of file string.cpp.

Referenced by main(), DiskConfig::parse_line(), and MemoryConfig::setup_detect().

void PortSetCloseOnExec ( int  fd)

set FD_CLOEXEC on file descriptor (if possible)

Definition at line 38 of file porting.cpp.

References UNUSED().

Referenced by MakePipe(), thrill::vfs::SysOpenReadStream(), and thrill::vfs::SysOpenWriteStream().

static JsonLine& thrill::common::Put ( JsonLine &  line,
bool const &  value 
)
inlinestatic
static JsonLine& thrill::common::Put ( JsonLine &  line,
int const &  value 
)
inlinestatic

Definition at line 283 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
unsigned int const &  value 
)
inlinestatic

Definition at line 289 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
long const &  value 
)
inlinestatic

Definition at line 295 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
unsigned long const &  value 
)
inlinestatic

Definition at line 301 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
long long const &  value 
)
inlinestatic

Definition at line 307 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
unsigned long long const &  value 
)
inlinestatic

Definition at line 313 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
double const &  value 
)
inlinestatic

Definition at line 319 of file json_logger.hpp.

References JsonLine::os_.

static JsonLine& thrill::common::Put ( JsonLine &  line,
const char *const &  str 
)
inlinestatic

Definition at line 325 of file json_logger.hpp.

References JsonLine::os_, and JsonLine::PutEscapedChar().

static JsonLine& thrill::common::Put ( JsonLine &  line,
std::string const &  str 
)
inlinestatic

Definition at line 333 of file json_logger.hpp.

References JsonLine::os_, and JsonLine::PutEscapedChar().

static JsonLine& thrill::common::Put ( JsonLine &  line,
const Type(&)  arr[N] 
)
inlinestatic

Definition at line 343 of file json_logger.hpp.

References JsonLine::os_, and Put().

static JsonLine& thrill::common::Put ( JsonLine &  line,
std::initializer_list< Type > const &  list 
)
inlinestatic

Definition at line 355 of file json_logger.hpp.

References JsonLine::os_, and Put().

static JsonLine& thrill::common::Put ( JsonLine &  line,
std::vector< Type > const &  vec 
)
inlinestatic

Definition at line 369 of file json_logger.hpp.

References JsonLine::os_, and Put().

static JsonLine& thrill::common::Put ( JsonLine &  line,
std::array< Type, N > const &  arr 
)
inlinestatic

Definition at line 383 of file json_logger.hpp.

References JsonLine::os_, and Put().

static JsonLine& thrill::common::Put ( JsonLine &  line,
JsonVerbatim const &  verbatim 
)
inlinestatic

Definition at line 396 of file json_logger.hpp.

References JsonLine::items_, JsonLine::os_, and JsonVerbatim::str_.

void thrill::common::qsort_three_pivots ( Iterator  left,
Iterator  right,
Compare  cmp 
)
void thrill::common::qsort_two_pivots_yaroslavskiy ( Iterator  lo,
Iterator  hi,
Compare  cmp 
)
static void thrill::common::radix_sort_CI ( Iterator  begin,
Iterator  end,
size_t  K,
const Comparator &  cmp,
const SubSorter &  sub_sort,
size_t  depth,
Char *  char_cache 
)
inlinestatic

Internal helper method, use radix_sort_CI below.

Definition at line 37 of file radix_sort.hpp.

References swap().

static void thrill::common::radix_sort_CI ( Iterator  begin,
Iterator  end,
size_t  K,
const Comparator &  cmp = Comparator(),
const SubSorter &  sub_sort = SubSorter() 
)
inlinestatic

Radix sort the iterator range [begin,end).

Sort unconditionally up to depth MaxDepth, then call the sub_sort method for further sorting. Small buckets are sorted using std::sort() with given comparator. Characters are extracted from items in the range using the at_radix(depth) method. All character values must be less than K (the counting array size).

Definition at line 118 of file radix_sort.hpp.

static std::string thrill::common::RandomString ( std::string::size_type  size,
RandomEngine  rng,
const std::string &  letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" 
)
inlinestatic

Generate a random string of given length.

The set of available bytes/characters is given as the second argument. Each byte is equally probable. Uses the pseudo-random number generator from stdlib; take care to seed it using srand() before calling this function.

Parameters
sizelength of result
rngRandom number generator to use, e.g. std::default_random_engine.
letterscharacter set to choose from
Returns
random string of given length

Definition at line 360 of file string.hpp.

std::string & ReplaceAll ( std::string &  str,
const std::string &  needle,
const std::string &  instead 
)

Replace all occurrences of needle in str.

Each needle will be replaced with instead, if found. The replacement is done in the given string and a reference to the same is returned.

Parameters
strthe string to process
needlestring to search for in str
insteadreplace needle with instead
Returns
reference to str

Definition at line 153 of file string.cpp.

Referenced by LogCmdlineParams().

static Integral thrill::common::RoundDownToPowerOfTwo ( Integral  n)
inlinestatic

does what it says.

Definition at line 55 of file math.hpp.

References RoundUpToPowerOfTwo().

Referenced by MixStream::GetWriters(), and CatStream::GetWriters().

static Integral thrill::common::RoundUpToPowerOfTwo ( Integral  n)
inlinestatic
void SetCpuAffinity ( std::thread &  thread,
size_t  cpu_id 
)
void SetCpuAffinity ( size_t  cpu_id)

set cpu/core affinity of current thread

Definition at line 124 of file porting.cpp.

References LOG1, and UNUSED().

Tree* thrill::common::splay ( const Key &  k,
Tree *  t,
const Compare &  cmp 
)
inline

Splay using the key i (which may or may not be in the tree.) The starting root is t, and the tree used is defined by rat size fields are maintained.

Definition at line 109 of file splay_tree.hpp.

Referenced by Pool::AllocateFreeArena(), Pool::deallocate(), splay_erase(), and splay_erase_top().

void thrill::common::splay_check ( const Tree *  t,
const Tree *&  out_tmin,
const Tree *&  out_tmax,
const Compare &  cmp 
)
inline

check the tree order, recursively calculate min and max elements

Definition at line 83 of file splay_tree.hpp.

Referenced by splay_check().

void thrill::common::splay_check ( const Tree *  t,
const Compare &  cmp 
)
inline

check the tree order

Definition at line 100 of file splay_tree.hpp.

References splay_check().

Tree* thrill::common::splay_erase ( const Key &  k,
Tree *&  t,
const Compare &  cmp 
)
inline

Erases i from the tree if it's there. Return a pointer to the resulting tree.

Definition at line 188 of file splay_tree.hpp.

References splay().

Tree* thrill::common::splay_erase_top ( Tree *&  t,
const Compare &  cmp 
)
inline

Erases i from the tree if it's there. Return a pointer to the resulting tree.

Definition at line 214 of file splay_tree.hpp.

References splay().

Referenced by Pool::deallocate().

Tree* thrill::common::splay_insert ( Tree *  nn,
Tree *  t,
const Compare &  cmp 
)
inline

Insert key i into the tree t, if it is not already there. Before calling this method, one MUST call splay() to rotate the tree to the right position. Return a pointer to the resulting tree.

Definition at line 168 of file splay_tree.hpp.

Referenced by Pool::AllocateFreeArena().

void thrill::common::splay_print ( Tree *  t,
size_t  d = 0 
)
inline

print the tree

Definition at line 73 of file splay_tree.hpp.

void thrill::common::splay_traverse_preorder ( const Functor &  f,
const Tree *  t 
)
inline

traverse the tree in preorder

Definition at line 231 of file splay_tree.hpp.

Tree* thrill::common::splayz ( const Key &  k,
Tree *  t,
const Compare &  cmp 
)
inline

Splay using the key i (which may or may not be in the tree.) The starting root is t, and the tree used is defined by rat size fields are maintained.

Definition at line 288 of file splay_tree.hpp.

References splayz_size().

Referenced by SplayzTree< Key >::exists(), SplayzTree< Key >::find(), SplayzTree< Key >::insert(), splayz_erase(), and splayz_erase_top().

void thrill::common::splayz_check ( const Tree *  t,
const Tree *&  out_tmin,
const Tree *&  out_tmax,
size_t &  out_size,
const Compare &  cmp 
)
inline

check the tree order, recursively calculate min and max elements

Definition at line 258 of file splay_tree.hpp.

Referenced by splayz_check().

void thrill::common::splayz_check ( const Tree *  t,
const Compare &  cmp 
)
inline

check the tree order

Definition at line 278 of file splay_tree.hpp.

References splayz_check().

Tree* thrill::common::splayz_erase ( const Key &  k,
Tree *&  t,
const Compare &  cmp 
)
inline

Erases i from the tree if it's there. Return a pointer to the resulting tree.

Definition at line 393 of file splay_tree.hpp.

References splayz().

Referenced by SplayzTree< Key >::erase().

Tree* thrill::common::splayz_erase_top ( Tree *&  t,
const Compare &  cmp 
)
inline

Erases i from the tree if it's there. Return a pointer to the resulting tree.

Definition at line 423 of file splay_tree.hpp.

References splayz().

Tree* thrill::common::splayz_insert ( Tree *  nn,
Tree *  t,
const Compare &  cmp 
)
inline

Insert key i into the tree t, if it is not already there. Before calling this method, one MUST call splayz() to rotate the tree to the right position. Return a pointer to the resulting tree.

Definition at line 370 of file splay_tree.hpp.

References splayz_size().

Referenced by SplayzTree< Key >::insert().

void thrill::common::splayz_print ( Tree *  t,
size_t  d = 0 
)
inline

print the tree

Definition at line 248 of file splay_tree.hpp.

Tree* thrill::common::splayz_rank ( size_t  r,
Tree *  t 
)
inline

Returns a pointer to the node in the tree with the given rank. Returns nullptr if there is no such node. Does not change the tree. To guarantee logarithmic behavior, the node found here should be splayed to the root.

Definition at line 446 of file splay_tree.hpp.

References splayz_size().

Referenced by SplayzTree< Key >::rank().

size_t thrill::common::splayz_size ( Tree *  x)
inline

Definition at line 242 of file splay_tree.hpp.

Referenced by splayz(), splayz_insert(), and splayz_rank().

void thrill::common::splayz_traverse_preorder ( const Functor &  f,
const Tree *  t 
)
inline

traverse the tree in preorder

Definition at line 466 of file splay_tree.hpp.

Referenced by SplayzTree< Key >::traverse_preorder().

std::vector< std::string > Split ( const std::string &  str,
char  sep,
std::string::size_type  limit = std::string::npos 
)

Split the given string at each separator character into distinct substrings.

Multiple consecutive separators are considered individually and will result in empty split substrings.

Parameters
strstring to split
sepseparator character
limitmaximum number of parts returned
Returns
vector containing each split substring

Definition at line 62 of file string.cpp.

Referenced by DiskConfig::parse_fileio(), and DiskConfig::parse_line().

std::vector< std::string > Split ( const std::string &  str,
const std::string &  sepstr,
std::string::size_type  limit = std::string::npos 
)

Split the given string at each separator string into distinct substrings.

Multiple consecutive separators are considered individually and will result in empty split substrings.

Parameters
strstring to split
sepstrseparator string, NOT a set of characters!
limitmaximum number of parts returned
Returns
vector containing each split substring

Definition at line 89 of file string.cpp.

std::vector< std::string > Split ( const std::string &  str,
const std::string &  sep,
unsigned int  min_fields,
unsigned int  limit_fields = std::numeric_limits< unsigned int >::max() 
)

Split a string by given separator string. Returns a vector of strings with at least min_fields and at most limit_fields

Definition at line 119 of file string.cpp.

void SplitRef ( const std::string &  str,
char  sep,
std::vector< std::string > &  out 
)

Definition at line 46 of file string.cpp.

Referenced by JoinTPCH4(), and Percentiles().

static void thrill::common::SplitView ( const std::string &  str,
char  sep,
F &&  callback,
std::string::size_type  limit = std::string::npos 
)
inlinestatic

Split the given string at each separator character into distinct substrings, and call the given callback for each substring, represented by two iterators begin and end.

Multiple consecutive separators are considered individually and will result in empty split substrings.

Parameters
strstring to split
sepseparator character
callbackcallback taking begin and end iterator of substring
limitmaximum number of parts returned

Definition at line 160 of file string_view.hpp.

Referenced by examples::word_count::HashWordCountExample(), main(), WordCount(), and examples::word_count::WordCount().

void StartLinuxProcStatsProfiler ( ProfileThread &  ,
JsonLogger &   
)

launch profiler task

Definition at line 856 of file linux_proc_stats.cpp.

Referenced by HostContext::HostContext().

static bool thrill::common::StartsWith ( const std::string &  str,
const std::string &  match 
)
inlinestatic

Checks if the given match string is located at the start of this string.

Definition at line 58 of file string.hpp.

Referenced by thrill::vfs::Glob(), thrill::vfs::IsRemoteUri(), thrill::vfs::OpenReadStream(), and thrill::vfs::OpenWriteStream().

String thrill::common::str_snprintf ( size_t  max_size,
const char *  fmt,
  ... 
)

Helper for using sprintf to format into std::string and also to_string converters.

Parameters
max_sizemaximum length of output string, longer ones are truncated.
fmtprintf format and additional parameters
String String thrill::common::str_snprintf ( size_t  max_size,
const char *  fmt,
  ... 
)

Definition at line 85 of file string.hpp.

String thrill::common::str_sprintf ( const char *  fmt,
  ... 
)

Helper for using sprintf to format into std::string and also to_string converters.

Parameters
fmtprintf format and additional parameters

Referenced by examples::suffix_sorting::ConstructWaveletTree(), RunJoinPageRankEdgePerLine(), RunPageRankEdgePerLine(), and RunPageRankJoinGenerated().

String String thrill::common::str_sprintf ( const char *  fmt,
  ... 
)

Definition at line 110 of file string.hpp.

void thrill::common::swap ( CountingPtr< A > &  a1,
CountingPtr< A > &  a2 
)
noexcept

swap enclosed object with another counting pointer (no reference counts need change)

Definition at line 247 of file counting_ptr.hpp.

Referenced by JoinNode< ValueType, FirstDIA, SecondDIA, KeyExtractor1, KeyExtractor2, JoinFunction, HashFunction, UseLocationDetection >::AddEqualKeysToVec(), File::Clear(), LoserTreeCopy< Stable, ValueType, Comparator >::delete_min_insert(), LoserTreeCopy< true, ValueType, Comparator >::delete_min_insert(), LoserTreePointer< Stable, ValueType, Comparator >::delete_min_insert(), LoserTreePointer< true, ValueType, Comparator >::delete_min_insert(), LoserTreeCopyUnguarded< Stable, ValueType, Comparator >::delete_min_insert(), LoserTreeCopyUnguarded< true, ValueType, Comparator >::delete_min_insert(), LoserTreePointerUnguarded< Stable, ValueType, Comparator >::delete_min_insert(), LoserTreePointerUnguarded< true, ValueType, Comparator >::delete_min_insert(), ConcatToDIANode< ValueType >::Dispose(), EqualToDIANode< ValueType >::Dispose(), DistributeNode< ValueType >::Dispose(), ReduceTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::Dispose(), ReduceOldProbingHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig_, IndexFunction, KeyEqualFunction >::Dispose(), ReduceBucketHashTable< TableItem, Key, Value, KeyExtractor, ReduceFunction, Emitter, VolatileKey, ReduceConfig, IndexFunction, KeyEqualFunction >::Dispose(), LocationDetection< thrill::api::JoinNode::HashCount >::Dispose(), BinaryHeap< Timer >::erase(), LocationDetection< thrill::api::JoinNode::HashCount >::Flush(), thrill::common::qsort_local::InsertionSort(), GroupToIndexNode< ValueType, KeyExtractor, GroupFunction >::MainOp(), GroupByNode< ValueType, KeyExtractor, GroupFunction, HashFunction, UseLocationDetection >::MainOp(), SortNode< ValueType, CompareFunction, SortAlgorithm >::MainOp(), BinaryHeap< Timer >::pop_heap(), qsort_three_pivots(), qsort_two_pivots_yaroslavskiy(), radix_sort_CI(), thrill::common::qsort_local::sort3(), thrill::common::qsort_local::sort4(), thrill::common::qsort_local::sort5(), Range::Swap(), CountingPtr< FileBase >::swap(), Delegate< R(A...), Allocator >::swap(), and SortNode< ValueType, CompareFunction, SortAlgorithm >::TransmitItems().

static std::string thrill::common::to_str ( const Type &  t)
inlinestatic

Use ostream to output any type as string. You generally DO NOT want to use this, instead create a larger ostringstream.

Definition at line 135 of file string.hpp.

std::string & Trim ( std::string &  str,
const std::string &  drop = " \r\n\t" 
)

Trims the given string in-place on the left and right.

Removes all characters in the given drop array, which defaults to " \r\n\t".

Parameters
strstring to process
dropremove these characters
Returns
reference to the modified string

Definition at line 165 of file string.cpp.

void thrill::common::VariadicCallEnumerate ( Functor &&  f)

Call a generic functor (like a generic lambda) for the integers [0,Size).

Definition at line 207 of file meta.hpp.

References VariadicCallEnumerateImpl< Index, Size, Functor >::Call().

void thrill::common::VariadicCallEnumerate ( Functor &&  f)

Call a generic functor (like a generic lambda) for the integers [Begin,End).

Definition at line 214 of file meta.hpp.

References VariadicCallEnumerateImpl< Index, Size, Functor >::Call().

void thrill::common::VariadicCallForeachIndex ( Functor &&  f,
Args &&...  args 
)

Call a generic functor (like a generic lambda) for each variadic template argument together with its zero-based index.

Definition at line 175 of file meta.hpp.

void thrill::common::VariadicCallForeachIndexImpl ( Functor &&  f,
Arg &&  arg 
)

helper for VariadicCallForeachIndex: base case

Definition at line 159 of file meta.hpp.

void thrill::common::VariadicCallForeachIndexImpl ( Functor &&  f,
Arg &&  arg,
MoreArgs &&...  rest 
)

helper for VariadicCallForeachIndex: general recursive case

Definition at line 165 of file meta.hpp.

auto thrill::common::VariadicMapEnumerate ( Functor &&  f)

Call a generic functor (like a generic lambda) for the integers [0,Size), and collect the return values in a generic std::tuple.

Definition at line 285 of file meta.hpp.

References VariadicMapEnumerateImpl< Index, Size, Functor >::Map().

auto thrill::common::VariadicMapEnumerate ( Functor &&  f)

Call a generic functor (like a generic lambda) for the integers [Begin,End), and collect the return values in a generic std::tuple.

Definition at line 294 of file meta.hpp.

References VariadicMapEnumerateImpl< Index, Size, Functor >::Map().

auto thrill::common::VariadicMapIndex ( Functor &&  f,
Args &&...  args 
)

Collect a generic functor (like a generic lambda) for each variadic template argument together with its zero-based index.

Definition at line 248 of file meta.hpp.

auto thrill::common::VariadicMapIndexImpl ( Functor &&  f,
Arg &&  arg 
)

helper for VariadicMapIndex: base case

Definition at line 227 of file meta.hpp.

auto thrill::common::VariadicMapIndexImpl ( Functor &&  f,
Arg &&  arg,
MoreArgs &&...  rest 
)

helper for VariadicMapIndex: general recursive case

Definition at line 235 of file meta.hpp.

static std::string thrill::common::VecToStr ( const std::vector< T > &  data)
static

Logging helper to print vectors as [a1,a2,a3,...].

Definition at line 311 of file string.hpp.

Variable Documentation

const uint32_t crc_tableil8_o32[256]

Definition at line 71 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o40[256]

Definition at line 125 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o48[256]

Definition at line 179 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o56[256]

Definition at line 233 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o64[256]

Definition at line 287 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o72[256]

Definition at line 341 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o80[256]

Definition at line 395 of file hash.cpp.

Referenced by crc32_slicing_by_8().

const uint32_t crc_tableil8_o88[256]

Definition at line 449 of file hash.cpp.

Referenced by crc32_slicing_by_8().

constexpr unsigned g_cache_line_size = 64
static

Finding cache line size is hard - we assume 64 byte.

Definition at line 38 of file config.hpp.

constexpr bool g_debug_mode = !g_ndebug
static

debug mode is active, if NDEBUG is false.

Definition at line 28 of file config.hpp.

constexpr bool g_debug_push_file = false
static

global flag to warn user when two DIANodes could push data directly via a File (skipping one data round trip) if the function stack were empty. This can be used to find lambda which could be be fused to reduce the number of data round trips.

Definition at line 44 of file config.hpp.

Referenced by ConcatNode< ValueType >::OnPreOpFile().

mem::Manager g_logger_mem_manager

memory manager singleton for Logger

Definition at line 27 of file logger.hpp.

constexpr bool g_ndebug = false
static

global ndebug flag as a boolean, NDEBUG means no debug in Release mode.

Definition at line 24 of file config.hpp.

constexpr bool g_profile_thread = true
static

global flag to enable background profiler thread

Definition at line 35 of file config.hpp.

Referenced by ProfileThread::ProfileThread(), and ProfileThread::~ProfileThread().

constexpr bool g_self_verify = g_debug_mode
static

global flag to enable code parts doing self-verification. Later this may be set false if NDEBUG is set in production mode.

Definition at line 32 of file config.hpp.

std::mutex s_logger_mutex
static

mutex for log output

Definition at line 88 of file logger.cpp.

Referenced by Logger::Output().

std::mutex s_mutex
static

mutex for s_threads map

Definition at line 44 of file logger.cpp.

Referenced by FormatNameForThisThread(), and NameThisThread().

logger_map<std::thread::id, StringCount> s_threads
static

map thread id -> (name, message counter)

Definition at line 47 of file logger.cpp.

Referenced by FormatNameForThisThread(), and NameThisThread().

class thrill::common::UIntPair THRILL_ATTRIBUTE_PACKED