| Home | Libraries | People | FAQ | More

## Allocators, containers and memory allocation algorithms

### Introduction to Interprocess allocators

As seen, Boost.Interprocess offers raw memory allocation and object construction using managed memory segments (managed shared memory, managed mapped files...) and one of the first user requests is the use of containers in managed shared memories. To achieve this, Boost.Interprocess makes use of managed memory segment's memory allocation algorithms to build several memory allocation schemes, including general purpose and node allocators.

Boost.Interprocess STL compatible allocators are configurable via template parameters. Allocators define their `pointer` typedef based on the `void_pointer` typedef of the segment manager passed as template argument. When this `segment_manager::void_pointer` is a relative pointer, (for example, `offset_ptr<void>`) the user can place these allocators in memory mapped in different base addresses in several processes.

#### Properties of Boost.Interprocess allocators

Container allocators are normally default-constructible because the are stateless. `std::allocator` and Boost.Pool's `boost::pool_allocator`/`boost::fast_pool_allocator` are examples of default-constructible allocators.

On the other hand, Boost.Interprocess allocators need to allocate memory from a concrete memory segment and not from a system-wide memory source (like the heap). Boost.Interprocess allocators are stateful, which means that they must be configured to tell them where the shared memory or the memory mapped file is.

This information is transmitted at compile-time and run-time: The allocators receive a template parameter defining the type of the segment manager and their constructor receive a pointer to the segment manager of the managed memory segment where the user wants to allocate the values.

Boost.Interprocess allocators have no default-constructors and containers must be explicitly initialized with a configured allocator:

    //The allocators must be templatized with the segment manager type
    typedef any_interprocess_allocator
       <int, managed_shared_memory::segment_manager, ...> Allocator;

    //The allocator must be constructed with a pointer to the segment manager
    Allocator alloc_instance (segment.get_segment_manager(), ...);

    //Containers must be initialized with a configured allocator
    typedef my_list<int, Allocator> MyIntList;
    MyIntList mylist(alloc_inst);

    //This would lead to a compilation error, because
    //the allocator has no default constructor
    //MyIntList mylist;

Boost.Interprocess allocators also have a `get_segment_manager()` function that returns the underlying segment manager that they have received in the constructor:

    Allocator::segment_manager s = alloc_instance.get_segment_manager();
    AnotherType *a = s->construct<AnotherType>(anonymous_instance)(/*Parameters*/);

#### Swapping Boost.Interprocess allocators

When swapping STL containers, there is an active discussion on what to do with the allocators. Some STL implementations, for example Dinkumware from Visual .NET 2003, perform a deep swap of the whole container through a temporary when allocators are not equal. The proposed resolution to container swapping is that allocators should be swapped in a non-throwing way.

Unfortunately, this approach is not valid with shared memory. Using heap allocators, if Group1 of node allocators share a common segregated storage, and Group2 share another common segregated storage, a simple pointer swapping is needed to swap an allocator of Group1 and another allocator of Group2. But when the user wants to swap two shared memory allocators, each one placed in a different shared memory segment, this is not possible. As generally shared memory is mapped in different addresses in each process, a pointer placed in one segment can't point to any object placed in other shared memory segment, since in each process, the distance between the segments is different. However, if both shared memory allocators are in the same segment, a non-throwing swap is possible, just like heap allocators.

Until a final resolution is achieved. Boost.Interprocess allocators implement a non-throwing swap function that swaps internal pointers. If an allocator placed in a shared memory segment is swapped with other placed in a different shared memory segment, the result is undefined. But a crash is quite sure.

#### allocator: A general purpose allocator for managed memory segments

The `allocator` class defines an allocator class that uses the managed memory segment's algorithm to allocate and deallocate memory. This is achieved through the segment manager of the managed memory segment. This allocator is the equivalent for managed memory segments of the standard `std::allocator`. `allocator` is templatized with the allocated type, and the segment manager.

Equality: Two `allocator` instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are implemented as calls to the segment manager's allocation function so the allocator offers the same thread-safety as the segment manager.

To use `allocator` you must include the following header:

    #include <boost/interprocess/allocators/allocator.hpp>

`allocator` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager>
    class allocator;

    }  //namespace interprocess {
    }  //namespace boost {

The allocator just provides the needed typedefs and forwards all allocation and deallocation requests to the segment manager passed in the constructor, just like `std::allocator` forwards the requests to `operator new[]`.

Using `allocator` is straightforward:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create an allocator that allocates ints from the managed segment
       allocator<int, managed_shared_memory::segment_manager>
          allocator_instance(segment.get_segment_manager());

       //Copy constructed allocator is equal
       allocator<int, managed_shared_memory::segment_manager>
          allocator_instance2(allocator_instance);
       assert(allocator_instance2 == allocator_instance);

       //Allocate and deallocate memory for 100 ints
       allocator_instance2.deallocate(allocator_instance.allocate(100), 100);

       return 0;
    }

### Segregated storage node allocators

Variable size memory algorithms waste some space in management information for each allocation. Sometimes, usually for small objects, this is not acceptable. Memory algorithms can also fragment the managed memory segment under some allocation and deallocation schemes, reducing their performance. When allocating many objects of the same type, a simple segregated storage becomes a fast and space-friendly allocator, as explained in the Boost.Pool library.

Segregate storage node allocators allocate large memory chunks from a general purpose memory allocator and divide that chunk into several nodes. No bookkeeping information is stored in the nodes to achieve minimal memory waste: free nodes are linked using a pointer constructed in the memory of the node.

Boost.Interprocess offers 3 allocators based on this segregated storage algorithm: `node_allocator`, `private_node_allocator` and `cached_node_allocator`.

To know the details of the implementation of of the segregated storage pools see the Implementation of Boost.Interprocess segregated storage pools section.

#### Additional parameters and functions of segregated storage node allocators

`node_allocator`, `private_node_allocator` and `cached_node_allocator` implement the standard allocator interface and the functions explained in the Properties of Boost.Interprocess allocators.

All these allocators are templatized by 3 parameters:

- `class T`: The type to be allocated.
- `class SegmentManager`: The type of the segment manager that will be passed in the constructor.
- `std::size_t NodesPerChunk`: The number of nodes that a memory chunk will contain. This value will define the size of the memory the pool will request to the segment manager when the pool runs out of nodes. This parameter has a default value.

These allocators also offer the `deallocate_free_chunks()` function. This function will traverse all the memory chunks of the pool and will return to the managed memory segment the free chunks of memory. If this function is not used, deallocating the free chunks does not happen until the pool is destroyed so the only way to return memory allocated by the pool to the segment before destructing the pool is calling manually this function. This function is quite time-consuming because it has quadratic complexity (O(N^2)).

#### node_allocator: A process-shared segregated storage

For heap-memory node allocators (like Boost.Pool's `boost::fast_pool_allocator` usually a global, thread-shared singleton pool is used for each node size. This is not possible if you try to share a node allocator between processes. To achieve this sharing `node_allocator` uses the segment manager's unique type allocation service (see Unique instance construction section).

In the initialization, a `node_allocator` object searches this unique object in the segment. If it is not preset, it builds one. This way, all `node_allocator` objects built inside a memory segment share a unique memory pool.

The common segregated storage is not only shared between node_allocators of the same type, but it is also shared between all node allocators that allocate objects of the same size, for example, node_allocator<uint32> and node_allocator<float32>. This saves a lot of memory but also imposes an synchronization overhead for each node allocation.

The dynamically created common segregated storage integrates a reference count so that a `node_allocator` can know if any other `node_allocator` is attached to the same common segregated storage. When the last allocator attached to the pool is destroyed, the pool is destroyed.

Equality: Two `node_allocator` instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are implemented as calls to the shared pool. The shared pool offers the same synchronization guarantees as the segment manager.

To use `node_allocator`, you must include the following header:

    #include <boost/interprocess/allocators/node_allocator.hpp>

`node_allocator` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager, std::size_t NodesPerChunk = ...>
    class node_allocator;

    }  //namespace interprocess {
    }  //namespace boost {

An example using `node_allocator`:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/node_allocator.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create a node_allocator that allocates ints from the managed segment
       //The number of chunks per segment is the default value
       typedef node_allocator<int, managed_shared_memory::segment_manager>
          node_allocator_t;
       node_allocator_t allocator_instance(segment.get_segment_manager());

       //Create another node_allocator. Since the segment manager address
       //is the same, this node_allocator will be
       //attached to the same pool so "allocator_instance2" can deallocate
       //nodes allocated by "allocator_instance"
       node_allocator_t allocator_instance2(segment.get_segment_manager());

       //Create another node_allocator using copy-constructor. This
       //node_allocator will also be attached to the same pool
       node_allocator_t allocator_instance3(allocator_instance2);

       //All allocators are equal
       assert(allocator_instance == allocator_instance2);
       assert(allocator_instance2 == allocator_instance3);

       //So memory allocated with one can be deallocated with another
       allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
       allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

       //The common pool will be destroyed here, since no allocator is
       //attached to the pool
       return 0;
    }

#### private_node_allocator: a private segregated storage

As said, the node_allocator shares a common segregated storage between node_allocators that allocate objects of the same size and this optimizes memory usage. However, it needs a unique/named object construction feature so that this sharing can be possible. Also imposes a synchronization overhead per node allocation because of this share. Sometimes, the unique object service is not available (for example, when building index types to implement the named allocation service itself) or the synchronization overhead is not acceptable. Many times the programmer wants to make sure that the pool is destroyed when the allocator is destroyed, to free the memory as soon as possible.

So private_node_allocator uses the same segregated storage as `node_allocator`, but each private_node_allocator has its own segregated storage pool. No synchronization is used when allocating nodes, so there is far less overhead for an operation that usually involves just a few pointer operations when allocating and deallocating a node.

Equality: Two `private_node_allocator` instances never compare equal. Memory allocated with one allocator can't be deallocated with another one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use `private_node_allocator`, you must include the following header:

    #include <boost/interprocess/allocators/private_node_allocator.hpp>

`private_node_allocator` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager, std::size_t NodesPerChunk = ...>
    class private_node_allocator;

    }  //namespace interprocess {
    }  //namespace boost {

An example using `private_node_allocator`:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/private_node_allocator.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       }  remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create a private_node_allocator that allocates ints from the managed segment
       //The number of chunks per segment is the default value
       typedef private_node_allocator<int, managed_shared_memory::segment_manager>
          private_node_allocator_t;
       private_node_allocator_t allocator_instance(segment.get_segment_manager());

       //Create another private_node_allocator.
       private_node_allocator_t allocator_instance2(segment.get_segment_manager());

       //Although the segment manager address
       //is the same, this private_node_allocator will have its own pool so
       //"allocator_instance2" CAN'T deallocate nodes allocated by "allocator_instance".
       //"allocator_instance2" is NOT equal to "allocator_instance"
       assert(allocator_instance != allocator_instance2);

       //Create another node_allocator using copy-constructor.
       private_node_allocator_t allocator_instance3(allocator_instance2);

       //This allocator is also unequal to allocator_instance2
       assert(allocator_instance2 != allocator_instance3);

       //Pools are destroyed with the allocators
       return 0;
    }

#### cached_node_allocator: caching nodes to avoid overhead

The total node sharing of `node_allocator` can impose a high overhead for some applications and the minimal synchronization overhead of `private_node_allocator` can impose a unacceptable memory waste for other applications.

To solve this, Boost.Interprocess offers an allocator, `cached_node_allocator`, that allocates nodes from the common pool but caches some of them privately so that following allocations have no synchronization overhead. When the cache is full, the allocator returns some cached nodes to the common pool, and those will be available to other allocators.

Equality: Two `cached_node_allocator` instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use `cached_node_allocator`, you must include the following header:

    #include <boost/interprocess/allocators/cached_node_allocator.hpp>

`cached_node_allocator` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager, std::size_t NodesPerChunk = ...>
    class cached_node_allocator;

    }  //namespace interprocess {
    }  //namespace boost {

A `cached_node_allocator` instance and a `node_allocator` instance share the same pool if both instances receive the same template parameters. This means that nodes returned to the shared pool by one of them can be reused by the other. Please note that this does not mean that both allocators compare equal, this is just information for programmers that want to maximize the use of the pool.

`cached_node_allocator`, offers additional functions to control the cache (the cache can be controlled per instance):

- `void set_max_cached_nodes(std::size_t n)`: Sets the maximum cached nodes limit. If cached nodes reach the limit, some are returned to the shared pool.
- `std::size_t get_max_cached_nodes() const`: Returns the maximum cached nodes limit.
- `void deallocate_cache()`: Returns the cached nodes to the shared pool.

An example using `cached_node_allocator`:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/cached_node_allocator.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create a cached_node_allocator that allocates ints from the managed segment
       //The number of chunks per segment is the default value
       typedef cached_node_allocator<int, managed_shared_memory::segment_manager>
          cached_node_allocator_t;
       cached_node_allocator_t allocator_instance(segment.get_segment_manager());

       //The max cached nodes are configurable per instance
       allocator_instance.set_max_cached_nodes(3);

       //Create another cached_node_allocator. Since the segment manager address
       //is the same, this cached_node_allocator will be
       //attached to the same pool so "allocator_instance2" can deallocate
       //nodes allocated by "allocator_instance"
       cached_node_allocator_t allocator_instance2(segment.get_segment_manager());

       //The max cached nodes are configurable per instance
       allocator_instance2.set_max_cached_nodes(5);

       //Create another cached_node_allocator using copy-constructor. This
       //cached_node_allocator will also be attached to the same pool
       cached_node_allocator_t allocator_instance3(allocator_instance2);

       //We can clear the cache
       allocator_instance3.deallocate_cache();

       //All allocators are equal
       assert(allocator_instance == allocator_instance2);
       assert(allocator_instance2 == allocator_instance3);

       //So memory allocated with one can be deallocated with another
       allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
       allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

       //The common pool will be destroyed here, since no allocator is
       //attached to the pool
       return 0;
    }

### Adaptive pool node allocators

Node allocators based on simple segregated storage algorithm are both space-efficient and fast but they have a problem: they only can grow. Every allocated node avoids any payload to store additional data and that leads to the following limitation: when a node is deallocated, it's stored in a free list of nodes but memory is not returned to the segment manager so a deallocated node can be only reused by other containers using the same node pool.

This behaviour can be problematic if several containers use `boost::interprocess::node_allocator` to temporarily allocate a lot of objects but they end storing a few of them: the node pool will be full of nodes that won't be reused wasting memory from the segment.

Adaptive pool based allocators trade some space (the overhead can be as low as 1%) and performance (acceptable for many applications) with the ability to return free chunks of nodes to the memory segment, so that they can be used by any other container or managed object construction. To know the details of the implementation of of "adaptive pools" see the Implementation of Boost.Intrusive adaptive pools section.

Like with segregated storage based node allocators, Boost.Interprocess offers 3 new allocators: `adaptive_pool`, `private_adaptive_pool`, `cached_adaptive_pool`.

#### Additional parameters and functions of adaptive pool node allocators

`adaptive_pool`, `private_adaptive_pool` and `cached_adaptive_pool` implement the standard allocator interface and the functions explained in the Properties of Boost.Interprocess allocators.

All these allocators are templatized by 4 parameters:

- `class T`: The type to be allocated.
- `class SegmentManager`: The type of the segment manager that will be passed in the constructor.
- `std::size_t NodesPerChunk`: The number of nodes that a memory chunk will contain. This value will define the size of the memory the pool will request to the segment manager when the pool runs out of nodes. This parameter has a default value.
- `std::size_t MaxFreeChunks`: The maximum number of free chunks that the pool will hold. If this limit is reached the pool returns the chunks to the segment manager. This parameter has a default value.

These allocators also offer the `deallocate_free_chunks()` function. This function will traverse all the memory chunks of the pool and will return to the managed memory segment the free chunks of memory. This function is much faster than for segregated storage allocators, because the adaptive pool algorithm offers constant-time access to free chunks.

#### adaptive_pool: a process-shared adaptive pool

Just like `node_allocator` a global, process-thread pool is used for each node size. In the initialization, `adaptive_pool` searches the pool in the segment. If it is not preset, it builds one. The adaptive pool, is created using a unique name. The adaptive pool it is also shared between all node_allocators that allocate objects of the same size, for example, adaptive_pool<uint32> and adaptive_pool<float32>.

The common adaptive pool is destroyed when all the allocators attached to the pool are destroyed.

Equality: Two `adaptive_pool` instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are implemented as calls to the shared pool. The shared pool offers the same synchronization guarantees as the segment manager.

To use `adaptive_pool`, you must include the following header:

    #include <boost/interprocess/allocators/adaptive_pool.hpp>

`adaptive_pool` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager, std::size_t NodesPerChunk = ..., std::size_t MaxFreeChunks = ...>
    class adaptive_pool;

    }  //namespace interprocess {
    }  //namespace boost {

An example using `adaptive_pool`:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/adaptive_pool.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create a adaptive_pool that allocates ints from the managed segment
       //The number of chunks per segment is the default value
       typedef adaptive_pool<int, managed_shared_memory::segment_manager>
          adaptive_pool_t;
       adaptive_pool_t allocator_instance(segment.get_segment_manager());

       //Create another adaptive_pool. Since the segment manager address
       //is the same, this adaptive_pool will be
       //attached to the same pool so "allocator_instance2" can deallocate
       //nodes allocated by "allocator_instance"
       adaptive_pool_t allocator_instance2(segment.get_segment_manager());

       //Create another adaptive_pool using copy-constructor. This
       //adaptive_pool will also be attached to the same pool
       adaptive_pool_t allocator_instance3(allocator_instance2);

       //All allocators are equal
       assert(allocator_instance == allocator_instance2);
       assert(allocator_instance2 == allocator_instance3);

       //So memory allocated with one can be deallocated with another
       allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
       allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

       //The common pool will be destroyed here, since no allocator is
       //attached to the pool
       return 0;
    }

#### private_adaptive_pool: a private adaptive pool

Just like `private_node_allocator` owns a private segregated storage pool, `private_adaptive_pool` owns its own adaptive pool. If the user wants to avoid the excessive node allocation synchronization overhead in a container `private_adaptive_pool` is a good choice.

Equality: Two `private_adaptive_pool` instances never compare equal. Memory allocated with one allocator can't be deallocated with another one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use `private_adaptive_pool`, you must include the following header:

    #include <boost/interprocess/allocators/private_adaptive_pool.hpp>

`private_adaptive_pool` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager, std::size_t NodesPerChunk = ..., std::size_t MaxFreeChunks = ...>
    class private_adaptive_pool;

    }  //namespace interprocess {
    }  //namespace boost {

An example using `private_adaptive_pool`:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/private_adaptive_pool.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create a private_adaptive_pool that allocates ints from the managed segment
       //The number of chunks per segment is the default value
       typedef private_adaptive_pool<int, managed_shared_memory::segment_manager>
             private_adaptive_pool_t;
       private_adaptive_pool_t allocator_instance(segment.get_segment_manager());

       //Create another private_adaptive_pool.
       private_adaptive_pool_t allocator_instance2(segment.get_segment_manager());

       //Although the segment manager address
       //is the same, this private_adaptive_pool will have its own pool so
       //"allocator_instance2" CAN'T deallocate nodes allocated by "allocator_instance".
       //"allocator_instance2" is NOT equal to "allocator_instance"
       assert(allocator_instance != allocator_instance2);

       //Create another adaptive_pool using copy-constructor.
       private_adaptive_pool_t allocator_instance3(allocator_instance2);

       //This allocator is also unequal to allocator_instance2
       assert(allocator_instance2 != allocator_instance3);

       //Pools are destroyed with the allocators
       return 0;
    }

#### cached_adaptive_pool: Avoiding synchronization overhead

Adaptive pools have also a cached version. In this allocator the allocator caches some nodes to avoid the synchronization and bookkeeping overhead of the shared adaptive pool. `cached_adaptive_pool` allocates nodes from the common adaptive pool but caches some of them privately so that following allocations have no synchronization overhead. When the cache is full, the allocator returns some cached nodes to the common pool, and those will be available to other `cached_adaptive_pools` or `adaptive_pools` of the same managed segment.

Equality: Two `cached_adaptive_pool` instances constructed with the same segment manager compare equal. If an instance is created using copy constructor, that instance compares equal with the original one.

Allocation thread-safety: Allocation and deallocation are not thread-safe.

To use `cached_adaptive_pool`, you must include the following header:

    #include <boost/interprocess/allocators/cached_adaptive_pool.hpp>

`cached_adaptive_pool` has the following declaration:

    namespace boost {
    namespace interprocess {

    template<class T, class SegmentManager, std::size_t NodesPerChunk = ..., std::size_t MaxFreeNodes = ...>
    class cached_adaptive_pool;

    }  //namespace interprocess {
    }  //namespace boost {

A `cached_adaptive_pool` instance and an `adaptive_pool` instance share the same pool if both instances receive the same template parameters. This means that nodes returned to the shared pool by one of them can be reused by the other. Please note that this does not mean that both allocators compare equal, this is just information for programmers that want to maximize the use of the pool.

`cached_adaptive_pool`, offers additional functions to control the cache (the cache can be controlled per instance):

- `void set_max_cached_nodes(std::size_t n)`: Sets the maximum cached nodes limit. If cached nodes reach the limit, some are returned to the shared pool.
- `std::size_t get_max_cached_nodes() const`: Returns the maximum cached nodes limit.
- `void deallocate_cache()`: Returns the cached nodes to the shared pool.

An example using `cached_adaptive_pool`:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/cached_adaptive_pool.hpp>
    #include <cassert>

    using namespace boost::interprocess;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Create a cached_adaptive_pool that allocates ints from the managed segment
       //The number of chunks per segment is the default value
       typedef cached_adaptive_pool<int, managed_shared_memory::segment_manager>
          cached_adaptive_pool_t;
       cached_adaptive_pool_t allocator_instance(segment.get_segment_manager());

       //The max cached nodes are configurable per instance
       allocator_instance.set_max_cached_nodes(3);

       //Create another cached_adaptive_pool. Since the segment manager address
       //is the same, this cached_adaptive_pool will be
       //attached to the same pool so "allocator_instance2" can deallocate
       //nodes allocated by "allocator_instance"
       cached_adaptive_pool_t allocator_instance2(segment.get_segment_manager());

       //The max cached nodes are configurable per instance
       allocator_instance2.set_max_cached_nodes(5);

       //Create another cached_adaptive_pool using copy-constructor. This
       //cached_adaptive_pool will also be attached to the same pool
       cached_adaptive_pool_t allocator_instance3(allocator_instance2);

       //We can clear the cache
       allocator_instance3.deallocate_cache();

       //All allocators are equal
       assert(allocator_instance == allocator_instance2);
       assert(allocator_instance2 == allocator_instance3);

       //So memory allocated with one can be deallocated with another
       allocator_instance2.deallocate(allocator_instance.allocate(1), 1);
       allocator_instance3.deallocate(allocator_instance2.allocate(1), 1);

       //The common pool will be destroyed here, since no allocator is
       //attached to the pool
       return 0;
    }

### Interprocess and containers in managed memory segments

#### Container requirements for Boost.Interprocess allocators

Boost.Interprocess STL compatible allocators offer a STL compatible allocator interface and if they define their internal pointer typedef as a relative pointer, they can sbe used to place STL containers in shared memory, memory mapped files or in a user defined memory segment.

However, as Scott Meyers mentions in his Effective STL book, Item 10, "Be aware of allocator conventions and restrictions":

- "the Standard explicitly allows library implementers to assume that every allocator's pointer typedef is a synonym for T*"
- "the Standard says that an implementation of the STL is permitted to assume that all allocator objects of the same type are equivalent and always compare equal"

Obviously, if any STL implementation ignores pointer typedefs, no smart pointer can be used as allocator::pointer. If STL implementations assume all allocator objects of the same type compare equal, it will assume that two allocators, each one allocating from a different memory pool are equal, which is a complete disaster.

STL containers that we want to place in shared memory or memory mapped files with Boost.Interprocess can't make any of these assumptions, so:

- STL containers may not assume that memory allocated with an allocator can be deallocated with other allocators of the same type. All allocators objects must compare equal only if memory allocated with one object can be deallocated with the other one, and this can only tested with operator==() at run-time.
- Containers' internal pointers should be of the type allocator::pointer and containers may not assume allocator::pointer is a raw pointer.
- All objects must be constructed-destroyed via allocator::construct and allocator::destroy functions.

#### STL containers in managed memory segments

Unfortunately, many STL implementations use raw pointers for internal data and ignore allocator pointer typedefs and others suppose at some point that the allocator::typedef is T. This is because in practice, there wasn't need of allocators with a pointer typedef different from T for pooled/node memory allocators.

Until STL implementations handle allocator::pointer typedefs in a generic way, Boost.Interprocess offers the following classes:

- boost:interprocess::vector is the implementation of `std::vector` ready to be used in managed memory segments like shared memory. To use it include:

    #include <boost/interprocess/containers/vector.hpp>

- boost:interprocess::deque is the implementation of `std::deque` ready to be used in managed memory segments like shared memory. To use it include:

    #include <boost/interprocess/containers/deque.hpp>

- `list` is the implementation of `std::list` ready to be used in managed memory segments like shared memory. To use it include:

    #include <boost/interprocess/containers/list.hpp>

- `slist` is the implementation of SGI's `slist` container (singly linked list) ready to be used in managed memory segments like shared memory. To use it include:

    #include <boost/interprocess/containers/slist.hpp>

- `set`/ `multiset`/ `map`/ `multimap` family is the implementation of std::set/multiset/map/multimap family ready to be used in managed memory segments like shared memory. To use them include:

    #include <boost/interprocess/containers/set.hpp>
    #include <boost/interprocess/containers/map.hpp>

- `flat_set`/ `flat_multiset`/ `flat_map`/ `flat_multimap` classes are the adaptation and extension of Andrei Alexandrescu's famous AssocVector class from Loki library, ready for the shared memory. These classes offer the same functionality as `std::set/multiset/map/multimap` implemented with an ordered vector, which has faster lookups than the standard ordered associative containers based on red-black trees, but slower insertions. To use it include:

    #include <boost/interprocess/containers/flat_set.hpp>
    #include <boost/interprocess/containers/flat_map.hpp>

- `basic_string` is the implementation of `std::basic_string` ready to be used in managed memory segments like shared memory. It's implemented using a vector-like contiguous storage, so it has fast c string conversion and can be used with the vectorstream iostream formatting classes. To use it include:

    #include <boost/interprocess/containers/string.hpp>

All these containers have the same default arguments as standard containers and they can be used with other, non Boost.Interprocess allocators (std::allocator, or boost::pool_allocator, for example).

To place any of these containers in managed memory segments, we must define the allocator template parameter with a Boost.Interprocess allocator so that the container allocates the values in the managed memory segment. To place the container itself in shared memory, we construct it in the managed memory segment just like any other object with Boost.Interprocess:

    #include <boost/interprocess/containers/vector.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>
    #include <boost/interprocess/managed_shared_memory.hpp>

    int main ()
    {
       using namespace boost::interprocess;
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //A managed shared memory where we can construct objects
       //associated with a c-string
       managed_shared_memory segment(create_only,
                                     "MySharedMemory",  //segment name
                                     65536);

       //Alias an STL-like allocator of ints that allocates ints from the segment
       typedef allocator<int, managed_shared_memory::segment_manager>
          ShmemAllocator;

       //Alias a vector that uses the previous STL-like allocator
       typedef vector<int, ShmemAllocator> MyVector;

       int initVal[]        = {0, 1, 2, 3, 4, 5, 6 };
       const int *begVal    = initVal;
       const int *endVal    = initVal + sizeof(initVal)/sizeof(initVal[0]);

       //Initialize the STL-like allocator
       const ShmemAllocator alloc_inst (segment.get_segment_manager());

       //Construct the vector in the shared memory segment with the STL-like allocator
       //from a range of iterators
       MyVector *myvector =
          segment.construct<MyVector>
             ("MyVector")/*object name*/
             (begVal     /*first ctor parameter*/,
             endVal     /*second ctor parameter*/,
             alloc_inst /*third ctor parameter*/);

       //Use vector as your want
       std::sort(myvector->rbegin(), myvector->rend());
       // . . .
       //When done, destroy and delete vector from the segment
       segment.destroy<MyVector>("MyVector");
       return 0;
    }

These containers also show how easy is to create/modify an existing container making possible to place it in shared memory.

#### Where is this being allocated?

Boost.Interprocess containers are placed in shared memory/memory mapped files, etc... using two mechanisms at the same time:

- Boost.Interprocess `construct<>`, `find_or_construct<>`... functions. These functions place a C++ object in the shared memory/memory mapped file. But this places only the object, but not the memory that this object may allocate dynamically.
- Shared memory allocators. These allow allocating shared memory/memory mapped file portions so that containers can allocate dynamically fragments of memory to store newly inserted elements.

This means that to place any Boost.Interprocess container (including Boost.Interprocess strings) in shared memory or memory mapped files, containers must:

- Define their template allocator parameter to a Boost.Interprocess allocator.
- Every container constructor must take the Boost.Interprocess allocator as parameter.
- You must use construct<>/find_or_construct<>... functions to place the container in the managed memory.

If you do the first two points but you don't use `construct<>` or `find_or_construct<>` you are creating a container placed only in your process but that allocates memory for contained types from shared memory/memory mapped file.

Let's see an example:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/containers/vector.hpp>
    #include <boost/interprocess/containers/string.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>

    int main ()
    {
       using namespace boost::interprocess;
       //Typedefs
       typedef allocator<char, managed_shared_memory::segment_manager>
          CharAllocator;
       typedef basic_string<char, std::char_traits<char>, CharAllocator>
          MyShmString;
       typedef allocator<MyShmString, managed_shared_memory::segment_manager>
          StringAllocator;
       typedef vector<MyShmString, StringAllocator>
          MyShmStringVector;

       //Open shared memory
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       managed_shared_memory shm(create_only, "MySharedMemory", 10000);

       //Create allocators
       CharAllocator     charallocator  (shm.get_segment_manager());
       StringAllocator   stringallocator(shm.get_segment_manager());

       //This string is in only in this process (the pointer pointing to the
       //buffer that will hold the text is not in shared memory).
       //But the buffer that will hold "this is my text" is allocated from
       //shared memory
       MyShmString mystring(charallocator);
       mystring = "this is my text";

       //This vector is only in this process (the pointer pointing to the
       //buffer that will hold the MyShmString-s is not in shared memory).
       //But the buffer that will hold 10 MyShmString-s is allocated from
       //shared memory using StringAllocator. Since strings use a shared
       //memory allocator (CharAllocator) the 10 buffers that hold
       //"this is my text" text are also in shared memory.
       MyShmStringVector myvector(stringallocator);
       myvector.insert(myvector.begin(), 10, mystring);

       //This vector is fully constructed in shared memory. All pointers
       //buffers are constructed in the same shared memory segment
       //This vector can be safely accessed from other processes.
       MyShmStringVector *myshmvector =
          shm.construct<MyShmStringVector>("myshmvector")(stringallocator);
       myshmvector->insert(myshmvector->begin(), 10, mystring);

       //Destroy vector. This will free all strings that the vector contains
       shm.destroy_ptr(myshmvector);
       return 0;
    }

#### Move semantics in Interprocess containers

Boost.Interprocess containers support move semantics, which means that the contents of a container can be moved from a container two another one, without any copying. The contents of the source container are transferred to the target container and the source container is left in default-constructed state.

When using containers of containers, we can also use move-semantics to insert objects in the container, avoiding unnecessary copies.

To transfer the contents of a container to another one, use `boost::move()` function, as shown in the example. For more details about functions supporting move-semantics, see the reference section of Boost.Interprocess containers:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/containers/vector.hpp>
    #include <boost/interprocess/containers/string.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>
    #include <cassert>

    int main ()
    {
       using namespace boost::interprocess;

       //Typedefs
       typedef managed_shared_memory::segment_manager     SegmentManager;
       typedef allocator<char, SegmentManager>            CharAllocator;
       typedef basic_string<char, std::char_traits<char>
                            ,CharAllocator>                MyShmString;
       typedef allocator<MyShmString, SegmentManager>     StringAllocator;
       typedef vector<MyShmString, StringAllocator>       MyShmStringVector;

       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       managed_shared_memory shm(create_only, "MySharedMemory", 10000);

       //Create allocators
       CharAllocator     charallocator  (shm.get_segment_manager());
       StringAllocator   stringallocator(shm.get_segment_manager());

       //Create a vector of strings in shared memory.
       MyShmStringVector *myshmvector =
          shm.construct<MyShmStringVector>("myshmvector")(stringallocator);

       //Insert 50 strings in shared memory. The strings will be allocated
       //only once and no string copy-constructor will be called when inserting
       //strings, leading to a great performance.
       MyShmString string_to_compare(charallocator);
       string_to_compare = "this is a long, long, long, long, long, long, string...";

       myshmvector->reserve(50);
       for(int i = 0; i < 50; ++i){
          MyShmString move_me(string_to_compare);
          //In the following line, no string copy-constructor will be called.
          //"move_me"'s contents will be transferred to the string created in
          //the vector
          myshmvector->push_back(boost::interprocess::move(move_me));

          //The source string is in default constructed state
          assert(move_me.empty());

          //The newly created string will be equal to the "move_me"'s old contents
          assert(myshmvector->back() == string_to_compare);
       }

       //Now erase a string...
       myshmvector->pop_back();

       //...And insert one in the first position.
       //No string copy-constructor or assignments will be called, but
       //move constructors and move-assignments. No memory allocation
       //function will be called in this operations!!
       myshmvector->insert(myshmvector->begin(), boost::interprocess::move(string_to_compare));

       //Destroy vector. This will free all strings that the vector contains
       shm.destroy_ptr(myshmvector);
       return 0;
    }

#### Containers of containers

When creating containers of containers, each container needs an allocator. To avoid using several allocators with complex type definitions, we can take advantage of the type erasure provided by void allocators and the ability to implicitly convert void allocators in allocators that allocate other types.

Here we have an example that builds a map in shared memory. Key is a string and the mapped type is a class that stores several containers:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>
    #include <boost/interprocess/containers/map.hpp>
    #include <boost/interprocess/containers/vector.hpp>
    #include <boost/interprocess/containers/string.hpp>

    using namespace boost::interprocess;

    //Typedefs of allocators and containers
    typedef managed_shared_memory::segment_manager                       segment_manager_t;
    typedef allocator<void, segment_manager_t>                           void_allocator;
    typedef allocator<int, segment_manager_t>                            int_allocator;
    typedef vector<int, int_allocator>                                   int_vector;
    typedef allocator<int_vector, segment_manager_t>                     int_vector_allocator;
    typedef vector<int_vector, int_vector_allocator>                     int_vector_vector;
    typedef allocator<char, segment_manager_t>                           char_allocator;
    typedef basic_string<char, std::char_traits<char>, char_allocator>   char_string;

    class complex_data
    {
       int               id_;
       char_string       char_string_;
       int_vector_vector int_vector_vector_;

       public:
       //Since void_allocator is convertible to any other allocator<T>, we can simplify
       //the initialization taking just one allocator for all inner containers.
       complex_data(int id, const char *name, const void_allocator &void_alloc)
          : id_(id), char_string_(name, void_alloc), int_vector_vector_(void_alloc)
       {}
       //Other members...
    };

    //Definition of the map holding a string as key and complex_data as mapped type
    typedef std::pair<const char_string, complex_data>                      map_value_type;
    typedef std::pair<char_string, complex_data>                            movable_to_map_value_type;
    typedef allocator<map_value_type, segment_manager_t>                    map_value_type_allocator;
    typedef map< char_string, complex_data
               , std::less<char_string>, map_value_type_allocator>          complex_map_type;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,"MySharedMemory", 65536);

       //An allocator convertible to any allocator<T, segment_manager_t> type
       void_allocator alloc_inst (segment.get_segment_manager());

       //Construct the shared memory map and fill it
       complex_map_type *mymap = segment.construct<complex_map_type>
          //(object name), (first ctor parameter, second ctor parameter)
             ("MyMap")(std::less<char_string>(), alloc_inst);

       for(int i = 0; i < 100; ++i){
          //Both key(string) and value(complex_data) need an allocator in their constructors
          char_string  key_object(alloc_inst);
          complex_data mapped_object(i, "default_name", alloc_inst);
          map_value_type value(key_object, mapped_object);
          //Modify values and insert them in the map
          mymap->insert(value);
       }
       return 0;
    }

### Boost containers compatible with Boost.Interprocess

As mentioned, container developers might need to change their implementation to make them compatible with Boost.Interprocess, because implementation usually ignore allocators with smart pointers. Hopefully several Boost containers are compatible with Interprocess.

#### Boost unordered containers

Boost.Unordered containers are compatible with Interprocess, so programmers can store hash containers in shared memory and memory mapped files. Here is a small example storing `unordered_map` in shared memory:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>

    #include <boost/unordered_map.hpp>     //boost::unordered_map
    #include <functional>                  //std::equal_to
    #include <boost/functional/hash.hpp>   //boost::hash

    int main ()
    {
       using namespace boost::interprocess;
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only, "MySharedMemory", 65536);

       //Note that unordered_map<Key, MappedType>'s value_type is std::pair<const Key, MappedType>,
       //so the allocator must allocate that pair.
       typedef int    KeyType;
       typedef float  MappedType;
       typedef std::pair<const int, float> ValueType;

       //Typedef the allocator
       typedef allocator<ValueType, managed_shared_memory::segment_manager> ShmemAllocator;

       //Alias an unordered_map of ints that uses the previous STL-like allocator.
       typedef boost::unordered_map
          < KeyType               , MappedType
          , boost::hash<KeyType>  ,std::equal_to<KeyType>
          , ShmemAllocator>
       MyHashMap;

       //Construct a shared memory hash map.
       //Note that the first parameter is the initial bucket count and
       //after that, the hash function, the equality function and the allocator
       MyHashMap *myhashmap = segment.construct<MyHashMap>("MyHashMap")  //object name
          ( 3, boost::hash<int>(), std::equal_to<int>()                  //
          , segment.get_allocator<ValueType>());                         //allocator instance

       //Insert data in the hash map
       for(int i = 0; i < 100; ++i){
          myhashmap->insert(ValueType(i, (float)i));
       }
       return 0;
    }

#### Boost.MultiIndex containers

The widely used Boost.MultiIndex library is compatible with Boost.Interprocess so we can construct pretty good databases in shared memory. Constructing databases in shared memory is a bit tougher than in normal memory, usually because those databases contain strings and those strings need to be placed in shared memory. Shared memory strings require an allocator in their constructors so this usually makes object insertion a bit more complicated.

Here is an example that shows how to put a multi index container in shared memory:

    #include <boost/interprocess/managed_shared_memory.hpp>
    #include <boost/interprocess/allocators/allocator.hpp>
    #include <boost/interprocess/containers/string.hpp>

    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/member.hpp>
    #include <boost/multi_index/ordered_index.hpp>

    using namespace boost::interprocess;
    namespace bmi = boost::multi_index;

    typedef managed_shared_memory::allocator<char>::type              char_allocator;
    typedef basic_string<char, std::char_traits<char>, char_allocator>shm_string;

    //Data to insert in shared memory
    struct employee
    {
       int         id;
       int         age;
       shm_string  name;
       employee( int id_
               , int age_
               , const char *name_
               , const char_allocator &a)
          : id(id_), age(age_), name(name_, a)
       {}
    };

    //Tags
    struct id{};
    struct age{};
    struct name{};

    // Define a multi_index_container of employees with following indices:
    //   - a unique index sorted by employee::int,
    //   - a non-unique index sorted by employee::name,
    //   - a non-unique index sorted by employee::age.
    typedef bmi::multi_index_container<
      employee,
      bmi::indexed_by<
        bmi::ordered_unique
          <bmi::tag<id>,  BOOST_MULTI_INDEX_MEMBER(employee,int,id)>,
        bmi::ordered_non_unique<
          bmi::tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,shm_string,name)>,
        bmi::ordered_non_unique
          <bmi::tag<age>, BOOST_MULTI_INDEX_MEMBER(employee,int,age)> >,
      managed_shared_memory::allocator<employee>::type
    > employee_set;

    int main ()
    {
       //Remove shared memory on construction and destruction
       struct shm_remove
       {
          shm_remove() { shared_memory_object::remove("MySharedMemory"); }
          ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
       } remover;

       //Create shared memory
       managed_shared_memory segment(create_only,"MySharedMemory", 65536);

       //Construct the multi_index in shared memory
       employee_set *es = segment.construct<employee_set>
          ("My MultiIndex Container")            //Container's name in shared memory
          ( employee_set::ctor_args_list()
          , segment.get_allocator<employee>());  //Ctor parameters

       //Now insert elements
       char_allocator ca(segment.get_allocator<char>());
       es->insert(employee(0,31, "Joe", ca));
       es->insert(employee(1,27, "Robert", ca));
       es->insert(employee(2,40, "John", ca));
       return 0;
    }

### Memory allocation algorithms

#### simple_seq_fit: A simple shared memory management algorithm

The algorithm is a variation of sequential fit using singly linked list of free memory buffers. The algorithm is based on the article about shared memory titled "Taming Shared Memory" . The algorithm is as follows:

The shared memory is divided in blocks of free shared memory, each one with some control data and several bytes of memory ready to be used. The control data contains a pointer (in our case offset_ptr) to the next free block and the size of the block. The allocator consists of a singly linked list of free blocks, ordered by address. The last block, points always to the first block:

    simple_seq_fit memory layout:

        main      extra  allocated  free_block_1     allocated   free_block_2    allocated   free_block_3
        header    header  block       ctrl     usr     block      ctrl     usr     block      ctrl     usr
       _________  _____  _________  _______________  _________  _______________  _________  _______________
      |         ||     ||         ||         |     ||         ||         |     ||         ||         |     |
      |free|ctrl||extra||         ||next|size| mem ||         ||next|size| mem ||         ||next|size| mem |
      |_________||_____||_________||_________|_____||_________||_________|_____||_________||_________|_____|
          |                         | |                         |  |                       | |
          |_>_>_>_>_>_>_>_>_>_>_>_>_| |_>_>_>_>_>_>_>_>_>_>_>_>_|  |_>_>_>_>_>_>_>_>_>_>_>_| |
                                    |                                                        |
                                    |_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<__|

When a user requests N bytes of memory, the allocator traverses the free block list looking for a block large enough. If the "mem" part of the block has the same size as the requested memory, we erase the block from the list and return a pointer to the "mem" part of the block. If the "mem" part size is bigger than needed, we split the block in two blocks, one of the requested size and the other with remaining size. Now, we take the block with the exact size, erase it from list and give it to the user.

When the user deallocates a block, we traverse the list (remember that the list is ordered), and search its place depending on the block address. Once found, we try to merge the block with adjacent blocks if possible.

To ease implementation, the size of the free memory block is measured in multiples of "basic_size" bytes. The basic size will be the size of the control block aligned to machine most restrictive alignment.

This algorithm is a low size overhead algorithm suitable for simple allocation schemes. This algorithm should only be used when size is a major concern, because the performance of this algorithm suffers when the memory is fragmented. This algorithm has linear allocation and deallocation time, so when the number of allocations is high, the user should use a more performance-friendly algorithm.

In most 32 systems, with 8 byte alignment, "basic_size" is 8 bytes. This means that an allocation request of 1 byte leads to the creation of a 16 byte block, where 8 bytes are available to the user. The allocation of 8 bytes leads also to the same 16 byte block.

#### rbtree_best_fit: Best-fit logarithmic-time complexity allocation

This algorithm is an advanced algorithm using red-black trees to sort the free portions of the memory segment by size. This allows logarithmic complexity allocation. Apart from this, a doubly-linked list of all portions of memory (free and allocated) is maintained to allow constant-time access to previous and next blocks when doing merging operations.

The data used to create the red-black tree of free nodes is overwritten by the user since it's no longer used once the memory is allocated. This maintains the memory size overhead down to the doubly linked list overhead, which is pretty small (two pointers). Basically this is the scheme:

    rbtree_best_fit memory layout:

       main            allocated block   free block                        allocated block  free block
       header
      _______________  _______________  _________________________________  _______________  _________________________________
     |               ||         |     ||         |                 |     ||         |     ||         |                 |     |
     |  main header  ||next|prev| mem ||next|prev|left|right|parent| mem ||next|prev| mem ||next|prev|left|right|parent| mem |
     |_______________||_________|_____||_________|_________________|_____||_________|_____||_________|_________________|_____|

This allocation algorithm is pretty fast and scales well with big shared memory segments and big number of allocations. To form a block a minimum memory size is needed: the sum of the doubly linked list and the red-black tree control data. The size of a block is measured in multiples of the most restrictive alignment value.

In most 32 systems with 8 byte alignment the minimum size of a block is 24 byte. When a block is allocated the control data related to the red black tree is overwritten by the user (because it's only needed for free blocks).

In those systems a 1 byte allocation request means that:

- 24 bytes of memory from the segment are used to form a block.
- 16 bytes of them are usable for the user.

For really small allocations (<= 8 bytes), this algorithm wastes more memory than the simple sequential fit algorithm (8 bytes more). For allocations bigger than 8 bytes the memory overhead is exactly the same. This is the default allocation algorithm in Boost.Interprocess managed memory segments.