Dinkum Allocators Library


A C++ program can specialize a number of templates from the Dinkum Allocators Library, a portable library for managing memory for node-based containers.


Allocators Table of Contents

"Dinkum/allocators"

Overview · Using the Allocator Templates · Writing Custom Allocators · Allocator Interface · Block Allocators · Max Classes · Support Classes


Overview

The Dinkum Allocators Library provides six allocator templates that can be used to select memory-management strategies for node-based containers. It also provides several different synchronization filters, for use with these templates, to tailor the memory-management strategy to a variety of different multithreading schemes (including none). Matching a memory management strategy to the known memory usage patterns, and synchronization requirements, of a particular application can often increase the speed or reduce the overall memory requirements of an application. All code for this library is in the header "allocators".

The allocator templates are implemented with reusable components that can be customized or replaced to provide additional memory-management strategies.

The node-based containers in the Standard C++ library -- list, set, multiset, map and multimap -- store their elements in individual nodes. All the nodes for a particular container type are the same size, so the flexibility of a general-purpose memory manager is not needed. Because the size of each memory block is known at compile time, the memory manager can be much simpler and faster.

The allocator templates in the Dinkum Allocators Library are designed to be used with node-based containers. When used with other forms of containers (such as the Standard C++ library containers vector deque, and basic_string) they will work correctly, but are not likely to provide any performance improvement over the default allocator.

Using the Allocator Templates

An allocator is a template class that describes an object that manages storage allocation and freeing for objects and arrays of objects of a designated type. Allocator objects are used by several container template classes in the Standard C++ library.

The allocators in the Dinkum Allocators Library are all templates of the form

template<class T>
    class allocator;

where the template argument T is the type managed by the allocator instance. The Standard C++ library provides a default allocator, template class allocator, which is defined in <memory>. The Dinkum Allocator Library provides the following allocators:

Use an appropriate instantiation of an allocator as the second type argument when creating a container, as in:

#include <list>
#include "Dinkum/allocators"

std::list<int, Dinkum::allocators::allocator_chunklist<int> > list0;

list0 allocates nodes with allocator_chunklist and the default synchronization filter.

Use the macro ALLOCATOR_DECL to create allocator templates with synchronization filters other than the default:

#include <list>
#include "Dinkum/allocators"

ALLOCATOR_DECL(CACHE_CHUNKLIST, Dinkum::allocators::sync_per_thread, alloc);

std::list<int, alloc<int> > list1;

list1 allocates nodes with allocator_chunklist and the sync_per_thread synchronization filter.

Writing Custom Allocators

The component-based design of the library makes customization of allocators straightforward. Allocator components can be replaced when an application imposes requirements that the allocators in the library do not support.

A class that meets the requirements for a filter can be used to define an allocator's synchronization policy:

#include <list>
#include "Dinkum/allocators"

class my_sync
    {
public:
    void *allocate(std::size_t);
    void deallocate(void *, std::size_t);
    bool equals(const my_sync&);
    };

ALLOCATOR_DECL(CACHE_NEWDEL, my_sync, allocator_my_sync);

std::list<int, allocator_my_sync<int> > list2;

A class that meets the requirements for a cache can be used to create an allocator template that meets application-specific size and speed requirements:

#include <list>
#include "Dinkum/allocators"

class my_cache
    {
public:
    void *allocate(std::size_t);
    void deallocate(void *, std::size_t);
    bool equals(const my_cache&);
    };

ALLOCATOR_DECL(my_cache, SYNC_DEFAULT, allocator_my_cache);

std::list<int, allocator_my_cache<int> > list3;

A class that meets the requirements for a max class can be combined with the cache_freelist template, using the CACHE_FREELIST macro, to create an allocator template based on a free list whose size is determined in an application-specific manner:

#include <list>
#include "Dinkum/allocators"

class my_max_class
    {
public:
    bool full() const;
    void saved();
    void released();
    void allocated(std::size_t = 1);
    void deallocated(std::size_t = 1);
    };

ALLOCATOR_DECL(CACHE_FREELIST(my_max_class), SYNC_DEFAULT, allocator_my_max);

std::list<int, allocator_my_max<int> > list4;

Allocator Interface

Each allocator template provides the following members, either directly or through inheritance:

template<class T,
    class Sync = sync_default>
    class allocator
    {
public:
    typedef ui-type size_type;
    typedef i-type difference_type;
    typedef p-type pointer;
    typedef p-type const_pointer;
    typedef r-type reference;
    typedef r-type const_reference;
    typedef T value_type;
    pointer address(reference x) const;
    const_pointer address(const_reference x) const;
    template<class U>
        struct rebind;
    allocator();
    template<class U>
        allocator(const allocator<U, Sync>& x);
    template<class U>
        allocator& operator=(const allocator<U, Sync>& x);
    template<class U>
        pointer allocate(size_type n, const U *hint = 0);
    void deallocate(pointer p, size_type n);
    void construct(pointer p, const T& val);
    void destroy(pointer p);
    size_type max_size() const;

    char *_Charalloc(size_type n);
    void _Chardealloc(void *p, size_type n);
    };

Each allocator template also supports the following operators:

template<class T,
    class Sync>
    bool operator==(allocator<T, Sync> lhs,
        allocator<T, Sync> rhs);
template<class T,
    class Sync>
    bool operator!=(allocator<T, Sync> lhs,
        allocator<T, Sync> rhs);

allocator::address

pointer address(reference x) const;
const_pointer address(const_reference x) const;

The member functions return the address of x, in the form that pointers must take for allocated elements.

allocator::allocate

template<class U>
    pointer allocate(size_type n, const U *hint = 0);

The member function allocates storage for an array of n elements of type T. It returns a pointer to the allocated object. The hint argument helps some allocators in improving locality of reference -- a valid choice is the address of an object earlier allocated by the same allocator object, and not yet deallocated. To supply no hint, use a null pointer argument instead.

allocator::allocator

allocator();
template<class U>
    allocator(const allocator<U, Sync>& x);

The first constructor constructs an allocator instance. The second constructor constructs an allocator instance such that for any allocator<T> instance a, allocator<T>(allocator<U>(a)) == a.

allocator::const_pointer

typedef p-type const_pointer;

The pointer type describes an object p that can designate, via the expression *p, any const object that an object of template class allocator can allocate.

allocator::const_reference

typedef r-type const_reference;

The reference type describes an object x that can designate any const object that an object of template class allocator can allocate.

allocator::construct

void construct(pointer p, const T& val);

The member function constructs an object of type T at p by evaluating the placement new expression new ((void *)p) T(val).

allocator::deallocate

void deallocate(pointer p, size_type n);

The member function frees storage for the array of n objects of type T beginning at p. The pointer p must have been earlier returned by a call to allocate for an allocator object that compares equal to *this, allocating an array object of the same size and type. deallocate never throws an exception.

allocator::destroy

void destroy(pointer p)

The member function destroys the object designated by p, by calling the destructor p->T::~T().

allocator::difference_type

typedef i-type difference_type;

The signed integer type describes an object that can represent the difference between the addresses of any two elements in a sequence that an object of template class allocator can allocate.

allocator::max_size

size_type max_size() const

The member function returns the length of the longest sequence of elements of type T that an object of class allocator might be able to allocate.

allocator::operator=

template<class T>
    allocator& operator=(const allocator<U>& x);

The template operator modifies the contents of the object such that for an allocator<T> instance a and an allocator<U> instance b, after the assignment b = a, allocator<T>(b) == a.

allocator::pointer

typedef p-type const_pointer;

The pointer type describes an object p that can designate, via the expression *p, any object that an object of template class allocator can allocate.

allocator::rebind

template<class U>
    struct rebind {
    typedef allocator<U> other;
    };

The member template class defines the type other. Its sole purpose is to provide the type name allocator<U> given the type name allocator<T>. It is not present when compiled with a compiler that cannot compile rebind.

For example, given an allocator object al of type A, you can allocate an object of type U with the expression:

A::rebind<U>::other(al).allocate(1, (U *)0)

Or, you can simply name its pointer type by writing the type:

A::rebind<U>::other::pointer

Some compilers cannot compile rebind. With those compilers the library requires workarounds for some features. These workarounds are marked as such, throughout this document, by a link to this paragraph.

allocator::reference

typedef r-type reference;

The reference type describes an object x that can designate any object that an object of template class allocator can allocate.

allocator::size_type

typedef ui-type size_type;

The unsigned integer type describes an object that can represent the length of any sequence that an object of template class allocator can allocate.

allocator::value_type

typedef T value_type;

The type is a synonym for the template parameter T.

allocator::_Charalloc

char *_Charalloc(size_type n);

The member function is used by containers when compiled with a compiler that cannot compile rebind. It allocates storage for an array of n elements of type char. It returns a pointer to the allocated object.

allocator::_Chardealloc

void _Charalloc(void *p, size_type n);

The member function is used by containers when compiled with a compiler that cannot compile rebind. It frees storage for the array of n elements of type char beginning at p. The pointer p must have been earlier returned by a call to _Charalloc for an allocator object that compares equal to *this, allocating an array object of the same size and type. _Chardealloc never throws an exception.

operator==

template<class T, class Sync>
    bool operator==(allocator<T, Sync> lhs,
        allocator<T, Sync> rhs);

The template operator returns true only if memory blocks allocated by lhs can be deallocated by rhs and vice versa.

operator!=

template<class T, class Sync>
    bool operator!=(allocator<T, Sync> lhs,
        allocator<T, Sync> rhs);

The template operator returns !(lhs == rhs).

Block Allocators

A block allocator is a cache or a filter. It provides the following member functions:

void *allocate(std::size_t);
void deallocate(void*, std::size_t);
bool equals(const MyType&);

block_allocator::allocate

void *allocate(std::size_t sz);

The member function allocates a memory block whose size is no less than sz bytes, suitably aligned for any type.

block_allocator::deallocate

void deallocate(void *p, std::size_t sz);

The member function frees storage for the memory block beginning p. The pointer p must have been returned by an earlier call to allocate for a block allocator that compares equal to *this, with a requested memory block of size sz.

block_allocator::equals

bool equals(const MyType& other);

The member function returns true only if memory blocks allocated by other can be deallocated by *this and vice versa.

A cache is a template class that takes one argument of type std::size_t. It defines a block allocator that allocates and deallocates memory blocks of a single size. It must obtain memory using operator new, but it need not make a separate call to operator new for each block. It may, for example, suballocate from a larger block or cache deallocated blocks for subsequent reallocation.

With a compiler that cannot compile rebind the value of the std::size_t argument used when the template was instantiated is not necessarily the value of the argument sz passed to a cache's member functions allocate and deallocate.

The library provides the following cache templates:

A filter is a block allocator that implements its member functions using another block allocator which is passed to it as a template argument. The most common form of filter is a synchronization filter, which applies a synchronization policy to control access to the member functions of an instance of another block allocator. The library provides the following synchronization filters:

The library also provides the filter rts_alloc, which holds multiple block allocator instances and determines which instance to use for allocation or deallocation at runtime instead of at compile time. It is used with compilers that cannot compile rebind.

A synchronization policy determines how an allocator instance handles simultaneous allocation and deallocation requests from multiple threads. The simplest policy is to pass all requests directly through to the underlying cache object, leaving synchronization management to the user. A more complex policy could be to use a mutex to serialize access to the underlying cache object.

If a compiler supports compiling both single-threaded and multi-threaded applications, the library's default synchronization filter for single-threaded applications is sync_none; for all other cases it is sync_shared.

Max Classes

The cache template cache_freelist takes a max class argument which determines the maximum number of elements to be stored in the free list. A max class must provide the following member functions:

class max_class {
public:
    bool full() const;
    void saved();
    void released();
    void allocated(size_t = 1);
    void deallocated(size_t = 1);
    };

The member function full returns true when no more memory blocks should be put on the free list. The member functions saved and released can be used to keep track of the number of memory blocks on the free list. The member functions allocated and deallocated can be used to keep track of the number of memory blocks in use by the application.

max_class::allocated

void allocated(size_t n = 1);

The member function is called after each successful call by cache_freelist::allocate to operator new. The argument n is the number of memory blocks in the chunk allocated by operator new.

max_class::deallocated

void deallocated(size_t n = 1);

The member function is called after each call by cache_freelist::deallocate to operator delete. The argument n is the number of memory blocks in the chunk deallocated by operator delete.

max_class::full

bool full() const;

The member function is called by cache_freelist::deallocate. If the call returns true deallocate puts the memory block on the free list; if it returns false deallocate calls operator delete to deallocate the block.

max_class::released

void released();

The member function is called by cache_freelist::allocate whenever it removes a memory block from the free list.

max_class::saved

void saved();

The member function is called by cache_freelist::deallocate whenever it puts a memory block on the free list.

The library provides the following max classes:

Support Classes

The library provides two support classes that can be used when implementing custom allocators. They are:


See also the Table of Contents and the Index.

Copyright © 1992-2013 by Dinkumware, Ltd. All rights reserved.