density
C++11 library for paged memory management, function queues, heterogeneous queues and lifo memory management
Classes | Typedefs | Enumerations | Functions | Variables
density Namespace Reference

Classes

struct  add_cv_qual
 
class  basic_default_allocator
 
class  conc_function_queue
 
class  conc_heter_queue
 
struct  cv_qual_of
 
class  default_busy_wait
 
class  dynamic_reference
 
class  f_alignment
 
class  f_copy_assign
 
class  f_copy_construct
 
class  f_default_construct
 
class  f_destroy
 
class  f_equal
 
class  f_hash
 
class  f_istream
 
class  f_less
 
class  f_move_assign
 
struct  f_move_construct
 
struct  f_none
 
class  f_ostream
 
class  f_rtti
 
class  f_size
 
struct  feature_list
 
class  function_queue
 
struct  has_features
 
class  heter_queue
 
struct  is_dynamic_reference
 
class  lf_function_queue
 
class  lf_heter_queue
 
class  lifo_allocator
 
class  lifo_array
 
class  lifo_buffer
 
class  runtime_type
 
class  sp_function_queue
 
class  sp_heter_queue
 

Typedefs

using default_allocator = basic_default_allocator< default_page_capacity >
 
using data_stack_underlying_allocator = basic_default_allocator< default_page_capacity >
 
template<typename TYPE >
using optional = builtin_optional< TYPE >
 
template<typename TYPE , cv_qual CV>
using add_cv_qual_t = typename add_cv_qual< TYPE, CV >::type
 
template<typename RUNTIME_TYPE = runtime_type<>>
using const_dynamic_reference = dynamic_reference< RUNTIME_TYPE, cv_qual::const_qual >
 
template<typename RUNTIME_TYPE = runtime_type<>>
using volatile_dynamic_reference = dynamic_reference< RUNTIME_TYPE, cv_qual::volatile_qual >
 
template<typename RUNTIME_TYPE = runtime_type<>>
using const_volatile_dynamic_reference = dynamic_reference< RUNTIME_TYPE, cv_qual::const_volatile_qual >
 
using default_type_features = feature_list< f_size, f_alignment, f_copy_construct, f_move_construct, f_rtti, f_destroy >
 

Enumerations

enum  concurrency_cardinality { concurrency_single, concurrency_multiple }
 
enum  consistency_model { consistency_relaxed, consistency_sequential }
 
enum  progress_guarantee { progress_blocking, progress_obstruction_free, progress_lock_free, progress_wait_free }
 
enum  function_type_erasure { function_standard_erasure, function_manual_clear }
 
enum  cv_qual { no_qual = 0, const_qual = 1, volatile_qual = 2, const_volatile_qual = 3 }
 

Functions

constexpr bool is_power_of_2 (size_t i_number) noexcept
 
bool address_is_aligned (const void *i_address, size_t i_alignment) noexcept
 
template<typename UINT >
bool uint_is_aligned (UINT i_uint, UINT i_alignment) noexcept
 
void * address_add (void *i_address, size_t i_offset) noexcept
 
const void * address_add (const void *i_address, size_t i_offset) noexcept
 
void * address_sub (void *i_address, size_t i_offset) noexcept
 
const void * address_sub (const void *i_address, size_t i_offset) noexcept
 
uintptr_t address_diff (const void *i_end_address, const void *i_start_address) noexcept
 
void * address_lower_align (void *i_address, size_t i_alignment) noexcept
 
const void * address_lower_align (const void *i_address, size_t i_alignment) noexcept
 
void * address_lower_align (void *i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
 
const void * address_lower_align (const void *i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
 
void * address_upper_align (void *i_address, size_t i_alignment) noexcept
 
const void * address_upper_align (const void *i_address, size_t i_alignment) noexcept
 
template<typename UINT >
constexpr UINT uint_upper_align (UINT i_uint, size_t i_alignment) noexcept
 
template<typename UINT >
constexpr UINT uint_lower_align (UINT i_uint, size_t i_alignment) noexcept
 
void * address_upper_align (void *i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
 
const void * address_upper_align (const void *i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
 
void * aligned_allocate (size_t i_size, size_t i_alignment, size_t i_alignment_offset=0)
 
void * try_aligned_allocate (size_t i_size, size_t i_alignment, size_t i_alignment_offset=0) noexcept
 
void aligned_deallocate (void *i_block, size_t i_size, size_t i_alignment, size_t i_alignment_offset=0) noexcept
 
constexpr bool is_less_or_equal_cv_qualified (cv_qual i_first, cv_qual i_second) noexcept
 
constexpr bool is_less_cv_qualified (cv_qual i_first, cv_qual i_second) noexcept
 
template<typename... FEATURES, typename = typename std::enable_if<has_features<feature_list<FEATURES...>, f_istream>::value>::type>
std::istream & operator>> (std::istream &i_source_stream, const dynamic_reference< runtime_type< FEATURES... >> &i_ptr)
 
template<typename... FEATURES, typename = typename std::enable_if<has_features<feature_list<FEATURES...>, f_ostream>::value>::type>
std::ostream & operator<< (std::ostream &i_dest_stream, const dynamic_reference< runtime_type< FEATURES... >> &i_ref)
 
template<typename TYPE >
TYPE raw_atomic_load (TYPE const *i_atomic, std::memory_order i_memory_order=std::memory_order_seq_cst) noexcept=delete
 
template<typename TYPE >
void raw_atomic_store (TYPE *i_atomic, TYPE i_value, std::memory_order i_memory_order=std::memory_order_seq_cst) noexcept=delete
 
template<typename TYPE >
bool raw_atomic_compare_exchange_strong (TYPE *i_atomic, TYPE *i_expected, TYPE i_desired, std::memory_order i_success, std::memory_order i_failure) noexcept=delete
 
template<typename TYPE >
bool raw_atomic_compare_exchange_weak (TYPE *i_atomic, TYPE *i_expected, TYPE i_desired, std::memory_order i_success, std::memory_order i_failure) noexcept=delete
 
template<typename TYPE >
bool raw_atomic_compare_exchange_strong (TYPE *i_atomic, TYPE *i_expected, TYPE i_desired, std::memory_order i_memory_order=std::memory_order_seq_cst) noexcept
 
template<typename TYPE >
bool raw_atomic_compare_exchange_weak (TYPE *i_atomic, TYPE *i_expected, TYPE i_desired, std::memory_order i_memory_order=std::memory_order_seq_cst) noexcept
 

Variables

constexpr char version [] = "2.0.0"
 
constexpr size_t destructive_interference_size = 64
 
constexpr size_t default_page_capacity = 1024 * 64
 
constexpr bool enable_relaxed_atomics = false
 

Detailed Description

namespace density

Typedef Documentation

Specialization of basic_default_allocator that uses density::default_page_capacity as page capacity.

Allocator type the data stack is built upon. It must satisfy the requirements of both UntypedAllocator and PagedAllocator

using optional = builtin_optional<TYPE>

Alias to an implementation of optional. By default a minimal implementation of optional is used, but it can be replaced by the C++17 standard one, if available.

using add_cv_qual_t = typename add_cv_qual<TYPE, CV>::type

Adds a cv-qualification to a type. Alias for add_cv_qual.

Example:

static_assert(std::is_same<add_cv_qual_t<int, cv_qual::no_qual>, int>::value, "");
static_assert(std::is_same<add_cv_qual_t<int *, cv_qual::const_qual>, int * const>::value, "");
static_assert(std::is_same<add_cv_qual_t<int &, cv_qual::const_qual>, int &>::value, "");
static_assert(std::is_same<add_cv_qual_t<const int, cv_qual::const_qual>, const int>::value, "");
static_assert(std::is_same<add_cv_qual_t<const int, cv_qual::volatile_qual>, const volatile int>::value, "");

Type alias template for the class template that sets the qv-qualification to cv_qual::const_qual.

Type alias template for the class template that sets the qv-qualification to cv_qual::volatile_qual.

Type alias template for the class template that sets the qv-qualification to cv_qual::const_volatile_qual.

feature_list used by default by runtime_type

Enumeration Type Documentation

Specifies whether a set of functions actually support concurrency

Enumerator
concurrency_single 

Functions with this concurrent cardinality can be called by only one thread, or by multiple threads if externally synchronized.

concurrency_multiple 

Multiple threads can call the functions with this concurrent cardinality without external synchronization.

Specifies which guarantee is provided on the order in which actions on a data structure are observable.

Enumerator
consistency_relaxed 

The order in which actions happens (or are observable) is not defined and may vary from one thread to another. A single thread may observe its own actions out of order.

consistency_sequential 

A total ordering exists of all actions on a data structure. Given three actions A, B and C, if A happens before B, and B happens before C, the A happens before C.

Specifies which guarantee an algorithm on a concurrent data struct provides about the progress and the completion of the work.

Members are sorted so that lower values specifies weaker guarantee. Progress guarantees are cumulative: the guarantee G provides all the guarantees less than G.

Dead locks and priority inversion may happen only in blocking algorithms.

See https://en.wikipedia.org/wiki/Non-blocking_algorithm.

Enumerator
progress_blocking 

The calling thread may wait for other threads to finish their work. Blocking algorithms usually protects shared data with a mutex.

progress_obstruction_free 

If all other threads are suspended, the calling thread is guaranteed to finish its work in a finite number of steps.

progress_lock_free 

In case of contention, in a finite number of steps at least one thread finishes the work.

progress_wait_free 

The calling thread completes the work in a finite number of steps, independently from the other threads.

Specifies a set of features provided by the built-in type erasure system for callable objects

Enumerator
function_standard_erasure 

Callable objects can be invoked-destroyed (i.e. consumed), and just destroyed (i.e. discarded). No copy or move is supported.

function_manual_clear 

Callable objects only support invoke-destroy (i.e. consume). Destruction without invocation is not supported.

enum cv_qual
strong

Defines a cv-qualification, that describes if a type is const, volatile, both or none.

Enumerator
no_qual 

no qualification

const_qual 

const qualification

volatile_qual 

volatile qualification

const_volatile_qual 

const and volatile qualification

Function Documentation

constexpr bool density::is_power_of_2 ( size_t  i_number)
noexcept

Returns true whether the given unsigned integer number is a power of 2 (1, 2, 4, 8, ...)

Parameters
i_numbermust be > 0, otherwise the behavior is undefined
bool density::address_is_aligned ( const void *  i_address,
size_t  i_alignment 
)
inlinenoexcept

Returns true whether the given address has the specified alignment

Parameters
i_addressaddress to be checked
i_alignmentmust be > 0 and a power of 2
bool density::uint_is_aligned ( UINT  i_uint,
UINT  i_alignment 
)
inlinenoexcept

Returns true whether the given unsigned integer has the specified alignment

Parameters
i_uintinteger to be checked
i_alignmentmust be > 0 and a power of 2
void* density::address_add ( void *  i_address,
size_t  i_offset 
)
inlinenoexcept

Adds an offset to a pointer.

Parameters
i_addresssource address
i_offsetnumber to add to the address
Returns
i_address plus i_offset
const void* density::address_add ( const void *  i_address,
size_t  i_offset 
)
inlinenoexcept

Adds an offset to a pointer.

Parameters
i_addresssource address
i_offsetnumber to add to the address
Returns
i_address plus i_offset
void* density::address_sub ( void *  i_address,
size_t  i_offset 
)
inlinenoexcept

Subtracts an offset from a pointer

Parameters
i_addresssource address
i_offsetnumber to subtract from the address
Returns
i_address minus i_offset
const void* density::address_sub ( const void *  i_address,
size_t  i_offset 
)
inlinenoexcept

Subtracts an offset from a pointer

Parameters
i_addresssource address
i_offsetnumber to subtract from the address
Returns
i_address minus i_offset
uintptr_t density::address_diff ( const void *  i_end_address,
const void *  i_start_address 
)
inlinenoexcept

Computes the unsigned difference between two pointers. The first must be above or equal to the second.

Parameters
i_end_addressfirst address
i_start_addresssecond address
Returns
i_end_address minus i_start_address
void* density::address_lower_align ( void *  i_address,
size_t  i_alignment 
)
inlinenoexcept

Returns the biggest aligned address lesser than or equal to a given address

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2.
Returns
the aligned address
const void* density::address_lower_align ( const void *  i_address,
size_t  i_alignment 
)
inlinenoexcept

Returns the biggest aligned address lesser than or equal to a given address

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2.
Returns
the aligned address
void* density::address_lower_align ( void *  i_address,
size_t  i_alignment,
size_t  i_alignment_offset 
)
inlinenoexcept

Returns the biggest address lesser than the first parameter, such that i_address + i_alignment_offset is aligned

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2
i_alignment_offsetalignment offset
Returns
the result address
const void* density::address_lower_align ( const void *  i_address,
size_t  i_alignment,
size_t  i_alignment_offset 
)
inlinenoexcept

Returns the biggest address lesser than the first parameter, such that i_address + i_alignment_offset is aligned

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2
i_alignment_offsetalignment offset
Returns
the result address
void* density::address_upper_align ( void *  i_address,
size_t  i_alignment 
)
inlinenoexcept

Returns the smallest aligned address greater than or equal to a given address

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2.
Returns
the aligned address
const void* density::address_upper_align ( const void *  i_address,
size_t  i_alignment 
)
inlinenoexcept

Returns the smallest aligned address greater than or equal to a given address

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2.
Returns
the aligned address
constexpr UINT density::uint_upper_align ( UINT  i_uint,
size_t  i_alignment 
)
noexcept

Returns the smallest aligned integer greater than or equal to a given address

Parameters
i_uintinteger to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2.
Returns
the aligned address
constexpr UINT density::uint_lower_align ( UINT  i_uint,
size_t  i_alignment 
)
noexcept

Returns the biggest aligned address lesser than or equal to a given address

Parameters
i_uintinteger to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2.
Returns
the aligned address
void* density::address_upper_align ( void *  i_address,
size_t  i_alignment,
size_t  i_alignment_offset 
)
inlinenoexcept

Returns the smallest address greater than the first parameter, such that i_address + i_alignment_offset is aligned

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2
i_alignment_offsetalignment offset
Returns
the result address
const void* density::address_upper_align ( const void *  i_address,
size_t  i_alignment,
size_t  i_alignment_offset 
)
inlinenoexcept

Returns the smallest address greater than the first parameter, such that i_address + i_alignment_offset is aligned

Parameters
i_addressaddress to be aligned
i_alignmentalignment required from the pointer. It must be an integer power of 2
i_alignment_offsetalignment offset
Returns
the result address
void* density::aligned_allocate ( size_t  i_size,
size_t  i_alignment,
size_t  i_alignment_offset = 0 
)
inline

Uses the global operator new to allocate a memory block with at least the specified size and alignment

Parameters
i_sizesize of the requested memory block, in bytes
i_alignmentalignment of the requested memory block, in bytes
i_alignment_offsetoffset of the block to be aligned, in bytes. The alignment is guaranteed only at i_alignment_offset from the beginning of the block.
Returns
address of the new memory block
Precondition
The behavior is undefined if either:
  • i_alignment is zero or it is not an integer power of 2
  • i_size is not a multiple of i_alignment
  • i_alignment_offset is greater than i_size

A violation of any precondition results in undefined behavior.


Throws: std::bad_alloc if the allocation fails
Progress guarantee: the same of the built-in operator new (usually blocking)

The content of the newly allocated block is undefined.

void* density::try_aligned_allocate ( size_t  i_size,
size_t  i_alignment,
size_t  i_alignment_offset = 0 
)
inlinenoexcept

Uses the global operator new to try to allocate a memory block with at least the specified size and alignment. Returns nullptr in case of failure.

Parameters
i_sizesize of the requested memory block, in bytes
i_alignmentalignment of the requested memory block, in bytes
i_alignment_offsetoffset of the block to be aligned, in bytes. The alignment is guaranteed only at i_alignment_offset from the beginning of the block.
Returns
address of the new memory block, or nullptr in case of failure
Precondition
The behavior is undefined if either:
  • i_alignment is zero or it is not an integer power of 2
  • i_size is not a multiple of i_alignment
  • i_alignment_offset is greater than i_size

A violation of any precondition results in undefined behavior.


Throws: nothing
Progress guarantee: the same of the built-in operator new (usually blocking)

The content of the newly allocated block is undefined.

void density::aligned_deallocate ( void *  i_block,
size_t  i_size,
size_t  i_alignment,
size_t  i_alignment_offset = 0 
)
inlinenoexcept

Deallocates a memory block allocated by aligned_allocate, using the global operator delete. After the call any access to the memory block results in undefined behavior.

Parameters
i_blockblock to deallocate, or nullptr.
i_sizesize of the block to deallocate, in bytes.
i_alignmentalignment of the memory block.
i_alignment_offsetoffset of the alignment
Precondition
The behavior is undefined if either:
  • i_block is not a memory block allocated by the function allocate
  • i_size, i_alignment and i_alignment_offset are not the same specified when the block was allocated


Throws: nothing
Progress guarantee: the same of the built-in operator delete (usually blocking)

If i_block is nullptr, the call has no effect.

constexpr bool density::is_less_or_equal_cv_qualified ( cv_qual  i_first,
cv_qual  i_second 
)
noexcept

Returns true if the first operand is less than or equal to the second one according to the partial ordering of cv qualifications.

  • If the two operands are equal the return value is true
  • if the first is const and the second one is not, the return value is false.
  • if the first is volatile and the second one is not, the return value is false.

Given two reference types T1 and T2, this function can be used to determine whether a variable of type T1 can be initialized with an expression of type T2:

static_assert(std::is_constructible<T1, T2>::value ==
cv_qual_of<typename std::remove_reference<T2>::type>::value,
cv_qual_of<typename std::remove_reference<T1>::type>::value), "");

Example:

constexpr bool density::is_less_cv_qualified ( cv_qual  i_first,
cv_qual  i_second 
)
noexcept

Returns true if the first operand is less than the second one according to the partial ordering of cv qualifications.

  • If the two operands are equal the return value is false
  • if the first is const and the second one is not, the return value is false.
  • if the first is volatile and the second one is not, the return value is false.

Example:

std::istream& density::operator>> ( std::istream &  i_source_stream,
const dynamic_reference< runtime_type< FEATURES... >> &  i_ptr 
)
inline

Reads the target object of a dynamic_reference that supports the feature f_ostream from an std::istream. If the feature f_ostream is supported by the runtime_type, this function does not participate in overload in overload resolution. Note: the dynamic_reference must be bound to a valid target of the correct type before the function is called.

Example:

std::istringstream source("1");
int t = 2;
dynamic_reference<RT> r(t);
source >> r;
assert(t == 1);

Throws: unspecified

std::ostream& density::operator<< ( std::ostream &  i_dest_stream,
const dynamic_reference< runtime_type< FEATURES... >> &  i_ref 
)
inline

Writes the target object of a dynamic_reference that supports the feature f_ostream to an std::ostream. If the feature f_ostream is supported by the runtime_type, this function does not participate in overload in overload resolution.

Example:

std::ostringstream dest;
int t = 1;
dynamic_reference<RT> r(t);
dest << r;
assert(dest.str() == "1");

Throws: unspecified

TYPE density::raw_atomic_load ( TYPE const *  i_atomic,
std::memory_order  i_memory_order = std::memory_order_seq_cst 
)
deletenoexcept

Similar to std::atomic_load but operates on fundamental types. This function has a limited support: availability depends on the compiler, the target architecture, and the type of the variable.
Overloads not available are declared as deleted.

Availability
Compiler Platform Types
msc x86 uint32_t
msc x64 uint32_t, uint64_t
g++/clang any uintptr_t
void density::raw_atomic_store ( TYPE *  i_atomic,
TYPE  i_value,
std::memory_order  i_memory_order = std::memory_order_seq_cst 
)
deletenoexcept

Similar to std::atomic_store but operates on fundamental types. This function has a limited support: availability depends on the compiler, the target architecture, and the type of the variable.
Overloads not available are declared as deleted.

Availability
Compiler Platform Types
msc x86 uint32_t
msc x64 uint32_t, uint64_t
g++/clang any uintptr_t
bool density::raw_atomic_compare_exchange_strong ( TYPE *  i_atomic,
TYPE *  i_expected,
TYPE  i_desired,
std::memory_order  i_success,
std::memory_order  i_failure 
)
deletenoexcept

Similar to std::atomic_compare_exchange_strong but operates on fundamental types. This function has a limited support: availability depends on the compiler, the target architecture, and the type of the variable.
Overloads not available are declared as deleted.

Availability
Compiler Platform Types
msc x86 uint32_t
msc x64 uint32_t, uint64_t
g++/clang any uintptr_t
bool density::raw_atomic_compare_exchange_weak ( TYPE *  i_atomic,
TYPE *  i_expected,
TYPE  i_desired,
std::memory_order  i_success,
std::memory_order  i_failure 
)
deletenoexcept

Similar to std::atomic_compare_exchange_weak but operates on fundamental types. This function has a limited support: availability depends on the compiler, the target architecture, and the type of the variable.
Overloads not available are declared as deleted.

Availability
Compiler Platform Types
msc x86 uint32_t
msc x64 uint32_t, uint64_t
g++/clang any uintptr_t
bool density::raw_atomic_compare_exchange_strong ( TYPE *  i_atomic,
TYPE *  i_expected,
TYPE  i_desired,
std::memory_order  i_memory_order = std::memory_order_seq_cst 
)
noexcept

Similar to std::atomic_compare_exchange_strong but operates on fundamental types. This function has a limited support: availability depends on the compiler, the target architecture, and the type of the variable.
Overloads not available are declared as deleted.

Availability
Compiler Platform Types
msc x86 uint32_t
msc x64 uint32_t, uint64_t
g++/clang any uintptr_t
bool density::raw_atomic_compare_exchange_weak ( TYPE *  i_atomic,
TYPE *  i_expected,
TYPE  i_desired,
std::memory_order  i_memory_order = std::memory_order_seq_cst 
)
noexcept

Similar to std::atomic_compare_exchange_weak but operates on fundamental types. This function has a limited support: availability depends on the compiler, the target architecture, and the type of the variable.
Overloads not available are declared as deleted.

Availability
Compiler Platform Types
msc x86 uint32_t
msc x64 uint32_t, uint64_t
g++/clang any uintptr_t

Variable Documentation

constexpr char version[] = "2.0.0"

string decimal variant of DENSITY_VERSION. The length of this string may change between versions. Example of value: "7.240.22"

constexpr size_t destructive_interference_size = 64

Alignment used by some concurrent data structure to avoid false sharing of cache lines. It must be a power of 2.

This is a configuration variable, intended to be customized by the user of the library. The default value is 64.

If a C++17 compiler is available, this constant may be defined as std::hardware_destructive_interference_size.

constexpr size_t default_page_capacity = 1024 * 64

Capacity (in bytes) of the pages managed by density::default_allocator. Note: the actual usable size is slightly smaller. This constant must be a power of 2.

This is a configuration variable, intended to be customized by the user of the library. The default value is 1024 * 64.

constexpr bool enable_relaxed_atomics = false

In this version of the library relaxed atomic operations are disabled. Concurrently data structures has been tested on x86-x64, but not on architectures with weak memory ordering. If you want to contribute to density, running the tests on other architectures, you can change this constant.