## File: concepts.md

package info (click to toggle)
foonathan-memory 0.7-3
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410 # Concepts and overall requirements ## Node A *node* is the region of storage needed to hold a single object. This storage region is identified via a pointer which is the *address* of the node. The terms *node* and *address of the node* are used interchangeable. It can be described using two properties: a *size* and an *alignment*. Both are represented as values of type std::size_t. The *alignment* must be a non-negative power of two. It describes the alignment requirement of the storage region, i.e. the address is dividable by the alignment. The *size* must be any valid value of std::size_t except 0. It describes the size of the storage region, size bytes after the address are available for the node. The following requirements must be fulfilled to create an object of type T in a node, i.e. to call a placement new new(address) T(ctor-args): * The alignment of the node must be at least as big as the alignment of the type, returned by alignof(T). If it is bigger, the type is *over-aligned* in this node, otherwise, it is *normal-aligned*. * The size of the node must be at least as big as the size of the type, returned by sizeof(T). *Example:* A node returned by a call to allocate_node(sizeof(T), alignof(T)) of a [RawAllocator](#concept_rawallocator) always fulfills these requirements for the type T. ## Array of nodes An *array of nodes* is a sequence of nodes whose storage regions are consecutively in memory. The *address* of the array is simply the address of the first node in the array. The terms *array* and *address of the array* are used interchangeable. In addition to the size and alignment, it has an additional property, the *count*. The *count* is the number of nodes and must be a valid value of type std::size_t except 0. The *size* is the size of each node and has the same requirements as for a node. The *alignment* is the alignment of the first node in the array and has the same requirements as for a node. The ith node of the array is at position adress + i * size. The total memory occupied by an array is thus count * size. The size specifies the alignment of each node except the first implicit through the position. The following requirements must be fulfilled to create an array of n T objects in an array of nodes, i.e. to create an object in each node: * The count of nodes must be at least n. * The alignment of the array must be at least alignof(T). * The size of each node must be at least sizeof(T) and a multiple of alignof(T). This is required to ensure proper alignment of each node in the array. *Note:* To create over-aligned types in the nodes, the alignment must be the stricter alignment and the size must be a multiple of the stricter alignment. *Example:* An array of nodes returned by a call to allocate_array(n, sizeof(T), alignof(T)) of a [RawAllocator](#concept_rawallocator) always fulfills these requirements for the type T. A call of the form allocate_array(n, size, align) where align is a stricter alignment and size is a multiple of align bigger than sizeof(T) returns an array of nodes where each node is over-aligned. ## RawAllocator A RawAllocator is the new type of allocator used in this library. Unlike the Allocator it does not work on a certain type directly, but only in terms of nodes and arrays of nodes. Thus it is unable to specify things like pointer types or construction function. It is only responsible for allocating and deallocating memory for nodes. A RawAllocator can either be *stateful* or *stateless*. A stateful allocator has some state, i.e. member variables, that need to be stored across calls. A stateless allocator can be constructed on-the-fly for each member function call. A pointer allocated by one instance of a stateless allocator can be deallocated with any other instance. All member functions are assumed to be thread-safe and can be called without synchronization. This is not valid for stateful allocator. Most of the time stateless allocators are also empty types, although this is not required (*note:* it does not make much sense for them to be not-empty, since the values of the member variables is not required to be the same.) An additional requirement for stateless allocator is that they have a default constructor. Access to a RawAllocator is only done via the class [allocator_traits]. It can be specialized for own RawAllocator types. The requirements for such a specialization are shown in the following table, where traits is allocator_traits will be rebound to alloc. If the parameter does not provide a member function allocate_node, it will try and call the allocation function required by the Allocator concept, i.e. static_cast(alloc.allocate(size), likewise for deallocate_node which will call forward to the deallocation function alloc.deallocate(static_cast(node), size). This enables the usage of any type modelling the Allocator concept where a RawAllocator is expected. It is only enabled, however, if the Allocator does not provide custom construct()/destroy() function since they would never be called. The checking can be overriden by specializing the traits class [allocator_is_raw_allocator](\ref foonathan::memory::allocator_is_raw_allocator). Note that it does *not* use the std::allocator_traits but calls the functions directly enabling only the Allocator classes that do not have specialized the traits template. For exposition, this is the minimum required interface for a RawAllocator without an appropriate specialization: cpp struct min_raw_allocator { min_raw_allocator(min_raw_allocator&&) noexcept; ~min_raw_allocator() noexcept; min_raw_allocator& operator=(min_raw_allocator&&) noexcept; void* allocate_node(std::size_t size, std::size_t alignment); void deallocate_node(void *node, std::size_t size, std::size_t alignment) noexcept; };  *Note*: If a RawAllocator provides a member function for allocation/deallocation, it is not allowed to mix those two interfaces, i.e. allocate memory through the traits and deallocate through the member function or vice-versa. It is completely allowed that those functions do completely different things. ### Composable RawAllocator A RawAllocator can be *composable*. Access to the composable (de)allocation functions is only done through the [composable_allocator_traits]. It can be specialized for your own allocator types. The requirements for such a specialization are shown in the following table, where ctraits is composable_allocator_traits::allocator_type | just forwards to the regular traits ctraits::try_allocate_node(alloc, size, alignment) | void* | Similar to the allocate_node() function but returns nullptr on failure instead of throwing an exception. ctraits::try_allocate_array(alloc, count, size, alignment) | void* | Similar to the allocate_array() function but returns nullptr on failure instead of throwing an exception. ctraits::try_deallocate_node(alloc, node, size, alignment) | bool | Similar to the deallocate_node() function but can be called with *any* [node](#concept_node). If that node was allocated by alloc, it will be deallocated and the function returns true. Otherwise the function has no effect and returns false. ctraits::try_deallocate_array(alloc, array, count, size, alignment) | bool | Similar to the deallocate_array() function but can be called with *any* [array](#concept_array). If that array was allocated by alloc, it will be deallocated and the function returns true. Otherwise the function has no effect and returns false. Unlike the normal allocation functions, the composable allocation functions are allowed to return nullptr on failure, they must never throw an exception. The deallocation function can be called with arbitrary nodes/arrays. The allocator must be able to detect whether they were originally allocated by the allocator and only deallocate them if that is the case. You are not allowed to mix the composable and normal allocation functions. Like [allocator_traits] the default [composable_allocator_traits] specialization forwards to member functions or uses a fallback: Expression|RawAllocator|Fallback ----------|------------|-------- ctraits::allocator_type | - | allocator_traits::allocator_type ctraits::try_allocate_node(alloc, size, alignment) | alloc.try_allocate_node(size, alignment) | none, required ctraits::try_allocate_array(alloc, count, size, alignment) | alloc.try_allocate_array(count, size, alignment) | ctraits::try_allocate_node(alloc, count * size, alignment) ctraits::try_deallocate_node(alloc, node, size, alignment) | alloc.try_deallocate_node(node, size, alignment) | non, required ctraits::try_deallocate_array(alloc, array, count, size, alignment) | alloc.try_deallocate_array(array, count, size, alignment) | ctraits::try_deallocate_node(alloc, array, count * size, alignment) ## BlockAllocator Some allocator types manage huge memory blocks and returns part of them in their allocation functions. Such huge memory blocks are managed by a memory arena, implemented in the class [memory_arena]. The size and the allocation of the memory blocks is controlled by a BlockAllocator. It is responsible to allocate and deallocate those blocks. It must be nothrow moveable and a valid base class, i.e. not final. In addition, it must provide the following: Expression|Semantics ----------|--------- BlockAllocator(block_size, args)|Creates a BlockAllocator by giving it a non-zero initial block size and optionally multiple further arguments. alloc.allocate_block()|Returns a new [memory_block] object that is the next memory block. alloc.deallocate_block(block)|Deallocates a memory_block. Deallocation will be done in reverse order. calloc.next_block_size()|Returns the size of the memory_block in the next allocation. The alignments of the allocated memory blocks must be the maximum alignment. This is a sample BlockAllocator that uses new for the allocation: cpp class block_allocator { public: block_allocator(std::size_t block_size) : block_size_(block_size) {} memory_block allocate_block() { auto mem = ::operator new(block_size_); return {mem, block_size_}; } void deallocate_block(memory_block b) { ::operator delete(b.memory); } std::size_t next_block_size() const { return block_size_; } private: std::size_t block_size_; };  ## StoragePolicy A StoragePolicy stores a [RawAllocator](#concept_rawallocator) and is used with the class template [allocator_storage]. It specifies how the allocator is stored, i.e. whether it is stored directly or only a pointer to it. It must always store a RawAllocator instance. The StoragePolicy must be class that is nothrow moveable and be a valid base class, i.e. not final. In addition it must provide the following: Expression|Semantics ----------|--------- StoragePolicy::allocator_type | The type of the allocator being stored as determinted through the [allocator_traits]. For a type-erased storage, it can be the type-erased base class. StoragePolicy(args) | Creates the StoragePolicy. args can be anything. It is used to create the allocator. policy.get_allocator() | Returns a reference to the allocator_type. Must not throw. May return a const reference, if policy is const. policy.is_composable() | Returns whether or not the allocator_type is a [ComposableAllocator](#concept_composableallocator) For exposition, this is a sample StoragePolicy. Note that it is not required to be a template, although it does not make much sense otherwise. cpp template class storage_policy { public: using allocator_type = typename memory::allocator_traits::allocator_type; storage_policy(RawAllocator &&alloc) noexcept : alloc_(std::move(alloc)) {} allocator_type& get_allocator() noexcept { return alloc_; } const allocator_type& get_allocator() const noexcept { return alloc_; } bool is_composable() const noexcept { return memory::is_composable_allocator::value; } private: allocator_type alloc_; };  ## Segregatable A Segregatable stores a [RawAllocator](#concept_rawallocator) and controls for which allocations it will be used. It is used in [binary_segregator]. It must be nothrow movable and provide the following: Expression|Type|Semantics ----------|----|--------- Segregatable::allocator_type|some [RawAllocator](#concept_rawallocator)|The type of the allocator it controls. segregatable.get_allocator()|allocator_type&|A reference to the allocator object it controls. const_segregatable.get_allocator()|const allocator_type&|A const reference to the allocator object it controls. segregatable.use_allocate_node(size, alignment)|bool|Whether or not the allocator object will be used for a node allocation with this specific properties. If it returns true, allocate_node() of the allocator object with the same parameters will be called, if it returns false, it will not be used. segregatable.use_allocate_array(count, size, alignment)|bool|Whether or not the allocator object will be used for an array allocation with this specific properties. If it returns true, allocate_array() of the allocator object with the same parameters will be called, if it returns false, it will not be used. For exposition, this is a simple Segregatable that will always use the given allocator: cpp template class segregatable { public: using allocator_type = typename memory::allocator_traits::allocator_type; segregatable(RawAllocator &&alloc) noexcept : alloc_(std::move(alloc)) {} allocator_type& get_allocator() noexcept { return alloc_; } const allocator_type& get_allocator() const noexcept { return alloc_; } bool use_allocate_node(std::size_t, std::size_t) noexcept { return true; } bool use_allocate_array(std::size_t, std::size_t) noexcept { return true; } private: allocator_type alloc_; };  ## Tracker A Tracker tracks allocation and/or deallocation of a RawAllocator and is used in the class template [tracked_allocator]. It is a moveable class that can be used as base class. No operation on a Tracker may throw. The address of a Tracker can be used as a unique, runtime identifier for a certain RawAllocator. An instance tracker of it must provide the following functions: Expression|Semantics ----------|--------- tracker.on_node_allocation(node, size, alignment) | Gets called after a [node](#concept_node) with given properties has been allocated. tracker.on_node_deallocation(node, size, alignment) | Gets called before a [node](#concept_node) with given properties is deallocated. tracker.on_array_allocation(array, count, size, alignment) | Same as the [node](#concept_node) version, but for [arrays](#concept_array). tracker.on_array_deallocation(array, count, size, alignment) | Same the [node](#concept_node) version, but for [arrays](#concept_array). *Note*: Those tracking functions are also called after a succesful composable (de)allocation function. A *deep tracker* also tracks a [BlockAllocator](#concept_block_allocator) of another allocator and thus allows monitoring the often more expensive big allocations done by it. Such a Tracker must provide the following additional functions: Expression|Semantics ----------|--------- tracker.on_allocator_growth(memory, size) | Gets called after the block allocator has allocated the passed memory block of given size. tracker.on_allocator_shrinkage(memory, size) | Gets called before a given memory block of the block allocator will be deallocated. For exposition, this is a sample Tracker: cpp struct tracker { void on_node_allocation(void *mem, std::size_t size, std::size_t) noexcept { std::clog << this << " node allocated: "; std::clog << mem << " (" << size << ") " << '\n'; } void on_array_allocation(void *mem, std::size_t count, std::size_t size, std::size_t) noexcept { std::clog << this << " array allocated: "; std::clog << mem << " (" << count << " * " << size << ") " << '\n'; } void on_node_deallocation(void *ptr, std::size_t, std::size_t) noexcept { std::clog << this << " node deallocated: " << ptr << " \n"; } void on_array_deallocation(void *ptr, std::size_t, std::size_t, std::size_t) noexcept { std::clog << this << " array deallocated: " << ptr << " \n"; } };  [allocator_storage]: \ref foonathan::memory::allocator_storage [allocator_traits]: \ref foonathan::memory::allocator_traits [composable_allocator_traits]: \ref foonathan::memory::composable_allocator_traits [memory_arena]: \ref foonathan::memory::memory_arena [memory_block]: \ref foonathan::memory::memory_block [binary_segregator]: \ref foonathan::memory::binary_segregator [tracked_allocator]: \ref foonathan::memory::tracked_allocator