A C++ program can specialize a number of templates from the Dinkum Allocators Library, a portable library for managing memory for node-based containers.
Overview · Using the Allocator Templates · Writing Custom Allocators · Allocator Interface · Block Allocators · Max Classes · Support Classes
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.
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:
operator delete
to deallocate a memory block and
operator new
to allocate a memory blockoperator new
to allocate a memory block when the
free list is emptyoperator delete
to deallocate a memory block when the free list is full,
and uses operator new
to allocate a
memory block when the free list is emptyoperator delete
to deallocate a memory block when the free list is full,
and uses operator new
to allocate a memory block when the
free list is emptyoperator new
when the free list is emptyoperator new
to allocate chunks of raw memory, suballocating from a
chunk to allocate storage for a memory block when needed; stores deallocated
memory blocks in a separate free list for each chunk, and uses
operator delete
to deallocate a chunk when none of its memory
blocks is in useUse 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.
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;
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)
.
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.
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:
max_none
never puts memory blocks on the free list.cache_freelist
with max class max_unbounded
always puts deallocated memory blocks on the free list.cache_freelist
with max class max_fixed_size<max>
puts no more than max
memory blocks on the free list.cache_freelist
with max class max_variable_size
puts memory blocks on the free list when the number of blocks on the free list is
less than roughly one sixteenth of the number of blocks in use.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.