Classes
struct	Append
	Append a value to the list. More...
struct	Append< NonTypeList< vs... >, v >
class	ArenaMemoryResource
	A linear arena memory resource that allocates memory sequentially from a fixed buffer. Throws std::bad_alloc if there is insufficient space for the requested allocation. More...
class	BinaryHeap
	A binary min-heap container. Supports custom comparator and allocator. More...
class	BuddyMemoryResource
	Fixed-size buddy allocator implementing the MemoryResource interface. The min block size is 1 byte, the maximum is 1<<64 bytes. More...
class	ConcurrentFlexQueue
	A thread-safe concurrent queue with flexible push and pop operations. More...
class	ConcurrentQueue
class	CountedValueViewIterator
	Iterator that returns a constant value a fixed number of times. Useful for creating a virtual range of repeated values without overhead. More...
class	DebugClass
	Debug class to track copy/move operations. Some operations may be optimized away in release builds. More...
class	DefaultMemoryResource
	A default memory resource that wraps global ::operator new and ::operator delete. More...
class	DisjointSet
	A disjoint union set that uses path compression and union by rank. More...
class	IntegralIterator
	An iterator that can iterate through a range of integer. Useful when the search space is too big to fit into a container. More...
struct	IsNonTypeList
struct	IsNonTypeList< NonTypeList< vs... > >
class	MemoryResource
	A memory resource holder interface for the PolymorphicAllocator. Responsible for allocate and deallocate raw memory. More...
class	MultiQueueThreadPool
	A work-stealing multiqueue threadpool. Each worker thread has a thread_local task queue to reduce thread contention. More...
struct	NonTypeList
struct	NonTypeList<>
class	PolymorphicAllocator
	Polymorphic allocator wrapping a non-owning memory resource. Allocation strategy depends on the memory resource implementation. More...
class	PoolMemoryResource
	A pool memory resource that manages fixed-size memory blocks from a pre-allocated buffer. The allocation size must be less or equal to the block size. The allocation alignment must be less or equal to the block alignment. Throws std::bad_alloc if the constraint is not met or run out of memory. More...
struct	PopBack
	Remove the last element from the list. More...
struct	PopBack< NonTypeList< v > >
struct	PopBack< NonTypeList< v, vs... > >
struct	PopFront
	Remove the first element from the list. More...
struct	PopFront< NonTypeList< v, vs... > >
struct	Prepend
	Prepend a value to the list. More...
struct	Prepend< NonTypeList< vs... >, v >
class	SegmentTree
	A standard segment tree that supports O(log n) for point update and range query. The binary operation must be commutative. More...
struct	Set
	Set the element at the index to the new value in the list. More...
struct	Set< NonTypeList< v, vs... >, index, sv >
class	SimpleThreadPool
	A simple thread pool with fixed number of worker threads. All the threads poll tasks from a single queue. If all the threads are waiting, then the user must manually call runPendingTask() to resolve deadlock. More...
struct	Splice
	Splice out a list from the range [first, last). More...
struct	Splice< NonTypeList< v, vs... >, first, last >
struct	Splice< NonTypeList< vs... >, first, last >
class	StackMemoryResource
	A stack-based memory resource that allocates memory in a LIFO order from a fixed buffer. Deallocation must happen in reverse order of allocation. Throws std::bad_alloc if there is insufficient space for an allocation. More...
class	ThreadTask
	A task that can be execute by a thread. Internally, it uses type erasure to store a std::packaged_task. The memory is managed by std::unique_ptr. More...
class	Timer
	A simple timer to record timelapses. Uses steady_clock by default. More...
class	Vector
struct	VectorGrowthStrategy
class	WorkStealingQueue

Concepts
concept	GrowthStrategy

Functions
void	enableMemoryGuard ()
	Enable MSVC native memory leak checker in debug mode. Not compatible with address sanitizer.
template<std::integral T>
constexpr IntegralIterator< T >	operator+ (IntegralIterator< T > it, typename IntegralIterator< T >::difference_type n) noexcept
template<std::integral T>
constexpr IntegralIterator< T >	operator+ (typename IntegralIterator< T >::difference_type n, IntegralIterator< T > it) noexcept
template<std::integral T>
constexpr IntegralIterator< T >	operator- (IntegralIterator< T > it, typename IntegralIterator< T >::difference_type n) noexcept
template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>
OutputIt	uninitializedForward (AllocatorType &allocator, InputIt first, InputIt last, OutputIt dest)
	Forward elements from a source range to uninitialized memory.
template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>
OutputIt	uninitializedMove (AllocatorType &allocator, InputIt first, InputIt last, OutputIt dest) noexcept
	Moves elements from a source range to uninitialized memory.
template<typename AllocatorType, std::forward_iterator OutputIt, typename ... Args>
OutputIt	uninitializedEmplace (AllocatorType &allocator, OutputIt first, OutputIt last, const Args &... args)
	Constructs objects in uninitialized memory by copying arguments to their constructor. Intentional copy of arguments to prevent reuse of moved objects.
template<typename AllocatorType, std::forward_iterator OutputIt, typename T>
OutputIt	uninitializedFill (AllocatorType &allocator, OutputIt first, OutputIt last, const T &value)
	Fills uninitialized memory with copies of a value.
template<typename AllocatorType, std::forward_iterator InputIt>
void	destroyElements (AllocatorType &allocator, InputIt first, InputIt last) noexcept
	Destroys a range of constructed objects in memory.
template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>
OutputIt	uninitializedForwardN (AllocatorType &allocator, InputIt first, std::size_t count, OutputIt dest)
	Forward count elements from a source range to uninitialized memory.
template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>
OutputIt	uninitializedMoveN (AllocatorType &allocator, InputIt first, std::size_t count, OutputIt dest) noexcept
	Moves count elements from a source range to uninitialized memory.
template<typename AllocatorType, std::forward_iterator OutputIt, typename ... Args>
OutputIt	uninitializedEmplaceN (AllocatorType &allocator, OutputIt first, std::size_t count, const Args &... args)
	Constructs a specified number of objects in uninitialized memory by copying constructor arguments. Intentional copy of arguments to prevent reuse of moved objects.
template<typename AllocatorType, std::forward_iterator OutputIt, typename T>
OutputIt	uninitializedFillN (AllocatorType &allocator, OutputIt first, std::size_t count, const T &value)
	Fills count elements in uninitialized memory with a value.
template<typename AllocatorType, std::forward_iterator InputIt>
void	destroyElementsN (AllocatorType &allocator, InputIt first, std::size_t count) noexcept
	Destroys count objects in a range.
template<typename AllocatorType, typename T>
void	deleteBuffer (AllocatorType &allocator, T *buffer, std::size_t size, std::size_t capacity) noexcept
	Destroys and deallocates the buffer.
template<typename T, typename U>
std::size_t	pointerDistance (const T first, const U last)
	Calculate the distance in bytes from the first pointer to the last pointer.
template<typename Header>
Header *	alignWithHeader (std::size_t alignment, std::size_t size, void *&buffer, std::size_t &capacity) noexcept
	Align the header + buffer to their corresponding alignments. If the capacity is not big enough, returns nullptr.
template<typename T> requires std::integral<T> \|\| std::floating_point<T>
T	getRandomNumber (T lower, T upper)
	Produces a random number uniformly distributed on the closed interval [lower, upper].
template<std::random_access_iterator It>
void	shuffle (It begin, It end)
	Randomly shuffle the elements in the range [begin, end).

Function Documentation

◆ alignWithHeader()

template<typename Header>

Header * flow::alignWithHeader	(	std::size_t	alignment,
		std::size_t	size,
		void *&	buffer,
		std::size_t &	capacity )

noexcept

Align the header + buffer to their corresponding alignments. If the capacity is not big enough, returns nullptr.

Parameters

alignment	Required alignment.
size	Size of the buffer to align.
buffer	Reference to pointer to the buffer to be aligned.
capacity	Reference to the capacity of the buffer.

Returns: Aligned header pointer followed by the aligned buffer, or nullptr on failure.

Definition at line 161 of file flow_memory_algorithm.h.

                                                                                                            {
 
    // https://stackoverflow.com/questions/46457449/is-it-always-the-case-that-sizeoft-alignoft-for-all-object-types-t
    assert(size >= alignment && "size is smaller than its alignment");
    if (capacity < sizeof(Header) + size) {
      return nullptr;
    }
 
    // Set the block alignment to be at least as big as the header alignment.
    alignment = std::max(alignment, alignof(Header));
 
    // Reserve at least sizeof(Header) before the allocated block.
    void* allocatedBlock = reinterpret_cast<Header*>(buffer) + 1;
    std::size_t capacityAfterHeader = capacity - sizeof(Header);
    if (!std::align(alignment, size, allocatedBlock, capacityAfterHeader)) {
      return nullptr;
    }
 
    // Calculate the address of the header.
    Header* header = reinterpret_cast<Header*>(allocatedBlock) - 1;
    assert(reinterpret_cast<std::uintptr_t>(header) % alignof(Header) == 0 && "allocated buffer is not aligned with the header");
 
    capacity -= pointerDistance(buffer, header);
    buffer = header;
    return header;
  }

References pointerDistance().

Referenced by flow::StackMemoryResource::allocateImp(), and flow::PoolMemoryResource::PoolMemoryResource().

◆ deleteBuffer()

template<typename AllocatorType, typename T>

void flow::deleteBuffer	(	AllocatorType &	allocator,
		T *	buffer,
		std::size_t	size,
		std::size_t	capacity )

noexcept

Destroys and deallocates the buffer.

Parameters

allocator	Allocator for destruction and deallocation.
buffer	Pointer to the buffer.
size	Number of constructed elements.
capacity	Total buffer capacity.

Definition at line 138 of file flow_memory_algorithm.h.

                                                                                                      {
    destroyElementsN(allocator, buffer, size);
    std::allocator_traits<AllocatorType>::deallocate(allocator, buffer, capacity);
  }

References destroyElementsN().

Referenced by flow::Vector< T, Allocator >::updateBuffer(), and flow::Vector< T, Allocator >::~Vector().

◆ destroyElements()

template<typename AllocatorType, std::forward_iterator InputIt>

void flow::destroyElements	(	AllocatorType &	allocator,
		InputIt	first,
		InputIt	last )

noexcept

Destroys a range of constructed objects in memory.

Parameters

allocator	Allocator for destruction.
first	Start of range.
last	End of range.

Definition at line 64 of file flow_memory_algorithm.h.

                                                                                       {
    for (; first != last; ++first) {
      std::allocator_traits<AllocatorType>::destroy(allocator, std::addressof(*first));
    }
  }

Referenced by flow::Vector< T, Allocator >::erase(), and flow::Vector< T, Allocator >::resizeImp().

◆ destroyElementsN()

template<typename AllocatorType, std::forward_iterator InputIt>

void flow::destroyElementsN	(	AllocatorType &	allocator,
		InputIt	first,
		std::size_t	count )

noexcept

Destroys count objects in a range.

Parameters

allocator	Allocator for destruction.
first	Start of range.
count	Number of elements to destroy.

Definition at line 126 of file flow_memory_algorithm.h.

                                                                                           {
    for (std::size_t i = 0; i < count; ++i, ++first) {
      std::allocator_traits<AllocatorType>::destroy(allocator, std::addressof(*first));
    }
  }

Referenced by flow::Vector< T, Allocator >::clear(), and deleteBuffer().

◆ enableMemoryGuard()

void flow::enableMemoryGuard ( )

inline

Enable MSVC native memory leak checker in debug mode. Not compatible with address sanitizer.

Definition at line 15 of file flow_debug_memory.h.

                                  {
    #ifdef _CRTDBG_MAP_ALLOC
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    #endif
  }

◆ getRandomNumber()

template<typename T>
requires std::integral<T> || std::floating_point<T>

T flow::getRandomNumber	(	T	lower,
		T	upper )

Produces a random number uniformly distributed on the closed interval [lower, upper].

Parameters

lower	The lower bound of the interval.
upper	The upper bound of the interval.

Returns: A random number in the closed interval [lower, upper].

Definition at line 14 of file flow_random_algorithm.h.

                                      {
    static std::random_device device{};
    static std::mt19937_64 engine(device());
    if constexpr (std::integral<T>) {
      return std::uniform_int_distribution<T>(lower, upper)(engine);
    } else {
      return std::uniform_real_distribution<T>(lower, upper)(engine);
    }
  }

◆ operator+() [1/2]

template<std::integral T>

IntegralIterator< T > flow::operator+	(	IntegralIterator< T >	it,
		typename IntegralIterator< T >::difference_type	n )

constexprnoexcept

Definition at line 75 of file flow_integral_iterator.h.

◆ operator+() [2/2]

template<std::integral T>

IntegralIterator< T > flow::operator+	(	typename IntegralIterator< T >::difference_type	n,
		IntegralIterator< T >	it )

constexprnoexcept

Definition at line 82 of file flow_integral_iterator.h.

                                                                           {
    return it + n;
  }

◆ operator-()

template<std::integral T>

IntegralIterator< T > flow::operator-	(	IntegralIterator< T >	it,
		typename IntegralIterator< T >::difference_type	n )

constexprnoexcept

Definition at line 88 of file flow_integral_iterator.h.

◆ pointerDistance()

template<typename T, typename U>

std::size_t flow::pointerDistance	(	const T *	first,
		const U *	last )

Calculate the distance in bytes from the first pointer to the last pointer.

Parameters

first	Pointer to the first element.
last	Pointer to one-past-last element.

Returns: The address distance in bytes.

Definition at line 148 of file flow_memory_algorithm.h.

                                                           {
    assert(first <= last && "first pointer address must be smaller than the last pointer address");
    return reinterpret_cast<const std::byte*>(last) - reinterpret_cast<const std::byte*>(first);
  }

Referenced by alignWithHeader(), and flow::StackMemoryResource::deallocateImp().

◆ shuffle()

template<std::random_access_iterator It>

void flow::shuffle	(	It	begin,
		It	end )

Randomly shuffle the elements in the range [begin, end).

Parameters

begin	Iterator to the beginning of the range.
end	Iterator to one past the end of the range.

Definition at line 28 of file flow_random_algorithm.h.

                                 {
    static std::random_device device{};
    static std::mt19937_64 engine(device());
    std::shuffle(begin, end, engine);
  }

◆ uninitializedEmplace()

template<typename AllocatorType, std::forward_iterator OutputIt, typename ... Args>

OutputIt flow::uninitializedEmplace	(	AllocatorType &	allocator,
		OutputIt	first,
		OutputIt	last,
		const Args &...	args )

Constructs objects in uninitialized memory by copying arguments to their constructor. Intentional copy of arguments to prevent reuse of moved objects.

Parameters

allocator	Allocator for memory management.
first	Start of the destination range.
last	End of the destination range.
args	Constructor arguments.

Returns: One past the last constructed element.

Definition at line 41 of file flow_memory_algorithm.h.

                                                                                                              {
    for (; first != last; ++first) {
      std::allocator_traits<AllocatorType>::construct(allocator, std::addressof(*first), args...);
    }
    return first;
  }

Referenced by flow::Vector< T, Allocator >::resizeImp(), and uninitializedFill().

◆ uninitializedEmplaceN()

template<typename AllocatorType, std::forward_iterator OutputIt, typename ... Args>

OutputIt flow::uninitializedEmplaceN	(	AllocatorType &	allocator,
		OutputIt	first,
		std::size_t	count,
		const Args &...	args )

Constructs a specified number of objects in uninitialized memory by copying constructor arguments. Intentional copy of arguments to prevent reuse of moved objects.

Parameters

allocator	Allocator for memory management.
first	Start of the destination range.
count	Number of objects to construct.
args	Constructor arguments.

Returns: One past the last constructed element.

Definition at line 103 of file flow_memory_algorithm.h.

                                                                                                                 {
    for (std::size_t i = 0; i < count; ++i, ++first) {
      std::allocator_traits<AllocatorType>::construct(allocator, std::addressof(*first), args...);
    }
    return first;
  }

Referenced by uninitializedFillN().

◆ uninitializedFill()

template<typename AllocatorType, std::forward_iterator OutputIt, typename T>

OutputIt flow::uninitializedFill	(	AllocatorType &	allocator,
		OutputIt	first,
		OutputIt	last,
		const T &	value )

Fills uninitialized memory with copies of a value.

Parameters

allocator	Allocator for construction.
first	Start of destination range.
last	End of destination range.
value	Value to fill with.

Returns: One past the last constructed element.

Definition at line 55 of file flow_memory_algorithm.h.

                                                                                                      {
    return uninitializedEmplace(allocator, first, last, value);
  }

References uninitializedEmplace().

◆ uninitializedFillN()

template<typename AllocatorType, std::forward_iterator OutputIt, typename T>

OutputIt flow::uninitializedFillN	(	AllocatorType &	allocator,
		OutputIt	first,
		std::size_t	count,
		const T &	value )

Fills count elements in uninitialized memory with a value.

Parameters

allocator	Allocator for construction.
first	Start of destination range.
count	Number of elements to fill.
value	Value to fill with.

Returns: One past the last constructed element.

Definition at line 117 of file flow_memory_algorithm.h.

                                                                                                         {
    return uninitializedEmplaceN(allocator, first, count, value);
  }

References uninitializedEmplaceN().

◆ uninitializedForward()

template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>

OutputIt flow::uninitializedForward	(	AllocatorType &	allocator,
		InputIt	first,
		InputIt	last,
		OutputIt	dest )

Forward elements from a source range to uninitialized memory.

Parameters

allocator	Allocator for construction.
first	Start of source range.
last	End of source range.
dest	Start of destination range.

Returns: One past the last constructed element.

Definition at line 15 of file flow_memory_algorithm.h.

                                                                                                      {
    for (; first != last; ++first, ++dest) {
      std::allocator_traits<AllocatorType>::construct(allocator, std::addressof(*dest), *first);
    }
    return dest;
  }

Referenced by flow::Vector< T, Allocator >::insert(), uninitializedMove(), and flow::Vector< T, Allocator >::Vector().

◆ uninitializedForwardN()

template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>

OutputIt flow::uninitializedForwardN	(	AllocatorType &	allocator,
		InputIt	first,
		std::size_t	count,
		OutputIt	dest )

Forward count elements from a source range to uninitialized memory.

Parameters

allocator	Allocator for construction.
first	Start of source range.
count	Number of elements to copy.
dest	Start of destination range.

Returns: One past the last constructed element.

Definition at line 77 of file flow_memory_algorithm.h.

                                                                                                          {
    for (std::size_t i = 0; i < count; ++i, ++first, ++dest) {
      std::allocator_traits<AllocatorType>::construct(allocator, std::addressof(*dest), *first);
    }
    return dest;
  }

Referenced by flow::Vector< T, Allocator >::insert(), and uninitializedMoveN().

◆ uninitializedMove()

template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>

OutputIt flow::uninitializedMove	(	AllocatorType &	allocator,
		InputIt	first,
		InputIt	last,
		OutputIt	dest )

noexcept

Moves elements from a source range to uninitialized memory.

Parameters

allocator	Allocator for construction.
first	Start of source range.
last	End of source range.
dest	Start of destination range.

Returns: One past the last constructed element.

Definition at line 29 of file flow_memory_algorithm.h.

                                                                                                            {
    return uninitializedForward(allocator, std::move_iterator(first), std::move_iterator(last), dest);
  }

References uninitializedForward().

Referenced by flow::Vector< T, Allocator >::insert(), flow::Vector< T, Allocator >::relocateBuffer(), and flow::Vector< T, Allocator >::relocateBufferWithHoles().

◆ uninitializedMoveN()

template<typename AllocatorType, std::input_iterator InputIt, std::forward_iterator OutputIt>

OutputIt flow::uninitializedMoveN	(	AllocatorType &	allocator,
		InputIt	first,
		std::size_t	count,
		OutputIt	dest )

noexcept

Moves count elements from a source range to uninitialized memory.

Parameters

allocator	Allocator for construction.
first	Start of source range.
count	Number of elements to move.
dest	Start of destination range.

Returns: One past the last constructed element.

Definition at line 91 of file flow_memory_algorithm.h.

                                                                                                                {
    return uninitializedForwardN(allocator, std::move_iterator(first), count, dest);
  }

References uninitializedForwardN().

Classes

Concepts

Functions

Function Documentation

◆ alignWithHeader()

◆ deleteBuffer()

◆ destroyElements()

◆ destroyElementsN()

◆ enableMemoryGuard()

◆ getRandomNumber()

◆ operator+() [1/2]

◆ operator+() [2/2]

◆ operator-()

◆ pointerDistance()

◆ shuffle()

◆ uninitializedEmplace()

◆ uninitializedEmplaceN()

◆ uninitializedFill()

◆ uninitializedFillN()

◆ uninitializedForward()

◆ uninitializedForwardN()

◆ uninitializedMove()

◆ uninitializedMoveN()