"Dinkum/allocators"
Include the header "Dinkum/allocators"
to define several
templates that help allocate and free memory blocks for
node-based containers.
// MACROS
#define ALLOCATOR_DECL(cache, sync, name) <alloc_template>
#define CACHE_CHUNKLIST <cache_class>
#define CACHE_FREELIST(max) <cache_class>
#define CACHE_SUBALLOC <cache_clsas>
#define SYNC_DEFAULT <sync_template>
namespace Dinkum {
namespace allocators {
// ALLOCATOR TEMPLATES
template <class T>
class allocator_chunklist;
template <class T>
class allocator_fixed_size;
template <class T>
class allocator_newdel;
template <class T>
class allocator_suballoc;
template <class T>
class allocator_unbounded;
template <class T>
class allocator_variable_size;
// SYNCHRONIZATION FILTERS
template <class Cache>
class sync_none;
template <class Cache>
class sync_per_container;
template <class Cache>
class sync_per_thread;
template <class Cache>
class sync_shared;
// CACHES
template <std::size_t sz>
class cache_chunklist;
template <std::size_t sz, class Max>
class cache_freelist;
template <std::size_t sz>
class cache_suballoc;
// MAX CLASSES
class max_none;
template <std::size_t max>
class max_fixed_size;
class max_unbounded;
class max_variable_size;
// SUPPORT CLASSES
template <class T, class Sync>
class allocator_base;
template <std::size_t sz, class Max>
class freelist;
template <class Cache>
class rts_alloc;
// TEMPLATE OPERATORS
template <class T, class Sync>
bool operator==(const allocator_base<T, Sync>&, const allocator_base<T, Sync>&);
template <class T, Sync>
bool operator!=(const allocator_base<T, Sync>&, const allocator_base<T, Sync>&);
} // namespace allocators
} // namespace Dinkum
allocator_base
template <class T, class Sync> class allocator_base { public: typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef T *pointer; typedef const T *const_pointer; typedef T& reference; typedef const T& const_reference; typedef T value_type; allocator_base(); template <class U> allocator_base(const allocator_base<U, Sync>& x); pointer address(reference x); const_pointer address(const_reference x); template <class U> pointer allocate(size_type n, const U *hint); pointer allocate(size_type n); 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); };
The template provides the boilerplate needed to create an allocator from a synchronization filter.
allocator_base::address
pointer address(reference x);
const_pointer address(const_reference x);
The member functions implement
allocator::address
by
returning &x
.
allocator_base::allocate
template <class U>
pointer allocate(size_type n, const U *hint = 0);
The member function implements
allocator::allocate
by
returning the result of a call to
Sync::allocate()
cast to type T*
if n == 1
, otherwise
by returning the result of a call to
operator new(n * sizeof(T))
cast to type T*
.
allocator_base::allocator_base
allocator_base();
template <class U>
allocator_base(const allocator_base<U, Sync>& x);
The first constructor constructs an allocator_base
instance. The second constructor
constructs an allocator_base
instance such that for any allocator_base<T, Sync>
instance a
, allocator_base<T, Sync>(allocator_base<U, Sync>(a)) == a
.
allocator_base::const_pointer
typedef const T *const_pointer;
The pointer type implements
allocator::const_pointer
as a typedef for const T*
.
allocator_base::const_reference
typedef const T& const_reference;
The reference type implements
allocator::const_reference
as a typedef for const T&
.
allocator_base::construct
void construct(pointer p, const T& val);
The member function implements
allocator::construct
by
calling new((void*)p T(val)
.
allocator_base::deallocate
void deallocate(pointer p, size_type n);
The member function implements
allocator::deallocate
by
calling Sync::deallocate(p)
if n == 1
, otherwise by calling operator delete(n * p)
.
allocator_base::destroy
void destroy(pointer p);
The member function implements
allocator::destroy
by
calling p->~T()
.
allocator_base::difference_type
typedef std::ptrdiff_t difference_type;
The integer type implements
allocator::difference_type
as a typedef for std::ptrdiff_t
.
allocator_base::max_size()
size_type max_size() const;
The member function implements
allocator::max_size
by returning (size_t)-1 / sizeof(T)
if
0 < (size_t)-1 / sizeof(T)
, otherwise 1
.
allocator_base::pointer
typedef T *pointer;
The pointer type implements
allocator::pointer
as a typedef for T*
.
allocator_base::reference
typedef T& reference;
The reference type implements
allocator::reference
as a typedef for T&
.
allocator_base::size_type
typedef std::size_t size_type;
The unsigned integer type implements
allocator::size_type
as a typedef for std::size_t
.
allocator_base::value_type
typedef T value_type;
The object type implements
allocator::value_type
as a typedef for T
.
allocator_base::_Charalloc
char *_Charalloc(size_type n);
The member function implements
allocator::_Charalloc
by returning Sync::allocate(n)
.
allocator_base::_Chardealloc
void _Chardealloc(void *p, size_type n);
The member function implements
allocator::_Chardealloc
by calling Sync::deallocate(p, n)
.
operator==
template <class T, class Sync>
bool operator==(const allocator_base<T, Sync>& a1, const allocator_base& T, Sync;sz>& a2);
The template operator returns a1.equals(a2)
.
operator!=
template <class T, class Sync>
bool operator!=(const allocator_base<T, Sync>& a1, const allocator_base<T, Sync>& a2);
The template operator returns !(a1 == a2)
.
ALLOCATOR_DECL
#define ALLOCATOR_DECL(cache, sync, name) <alloc_template>
The macro yields a template definition template <class T>
class name {.....}
and a specialization template <>
class name<void> {.....}
which together define an
allocator template class that uses
the synchronization filter sync
and a cache of type cache
.
For compilers that can compile rebind the resulting template definition looks like this:
template <class T> class name : public Dinkum::allocators::allocator_base<T, sync<cache > > { public: name() {} template <class U> name(const name<U>&) {} template <class U> name& operator = (const name<U>&) {return *this; } template <class U> struct rebind { /* convert a name<T> to a name<U> */ typedef name<U> other; }; };
For compilers that cannot compile rebind the resulting template definition looks like this:
template <class T< class name : public Dinkum::allocators::allocator_base<T, sync<Dinkum::allocators::rts_alloc<cache > > > { public: name() {} template <class U> name(const name<U>&) {} template <class U> name& operator = (const name<U>&) {return *this; } };
allocator_chunklist
ALLOCATOR_DECL(CACHE_CHUNKLIST, SYNC_DEFAULT, allocator_chunklist);
The allocator template class describes an object
that manages storage allocation and freeing for objects of type T
using
a cache of type
cache_chunklist.
allocator_fixed_size
ALLOCATOR_DECL( CACHE_FREELIST(Dinkum::allocators::max_fixed_size<10>), SYNC_DEFAULT, allocator_fixed_size);
The allocator template class describes an object
that manages storage allocation and freeing for objects of type T
using
a cache of type
cache_freelist with a length managed by
max_fixed_size.
allocator_newdel
ALLOCATOR_DECL( CACHE_FREELIST(Dinkum::allocators::max_none), SYNC_DEFAULT, allocator_newdel);
The template allocator_newdel
implements an
allocator that uses
operator delete
to deallocate a memory block and
operator new
to allocate a memory block.
allocator_suballoc
ALLOCATOR_DECL(CACHE_SUBALLOC, SYNC_DEFAULT, allocator_suballoc);
The allocator template class describes an object
that manages storage allocation and freeing for objects of type T
using
a cache of type
cache_suballoc.
allocator_unbounded
ALLOCATOR_DECL( CACHE_FREELIST(Dinkum::allocators::max_unbounded), SYNC_DEFAULT, allocator_unbounded);
The allocator template class describes an object
that manages storage allocation and freeing for objects of type T
using
a cache of type
cache_freelist with a length managed by
max_unbounded.
allocator_variable_size
ALLOCATOR_DECL( CACHE_FREELIST(Dinkum::allocators::max_variable_size), SYNC_DEFAULT, allocator_variable_size);
The allocator template class describes an object
that manages storage allocation and freeing for objects of type T
using
a cache of type
cache_freelist with a length managed by
max_variable_size.
CACHE_CHUNKLIST
#define CACHE_CHUNKLIST <cache_class>
The macro yields Dinkum::allocators::cache_chunklist<sizeof(T)>
.
cache_chunklist
template <std::size_t sz, std::size_t NELTS = 20> class cache_chunklist { public: cache_chunklist(); template <size_t usz> cache_chunklist(const cache_chunklist<usz>&); template <size_t usz> cache_chunklist<usz>& operator=(const cache_chunklist<usz>&); void *allocate(std::size_t); void deallocate(void *, std::size_t); };
The cache template class uses operator new
to allocate
chunks of raw memory, suballocating blocks to allocate storage for a memory block when needed;
it 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 use.
Overhead: each memory block holds sz
bytes of usable
memory and a pointer to the chunk that it belongs to.
Each chunk holds NELTS
memory blocks, three pointers, an int
and the data that operator new
and
operator delete
require.
cache_chunklist::allocate
void *allocate(std::size_t n);
The member function implements block_allocator::allocate.
cache_chunklist::cache_chunklist
cache_chunklist();
template <size_t usz>
cache_chunklist(const cache_chunklist<usz>&);
The constructors construct a cache_chunklist
object.
cache_chunklist::deallocate
void deallocate(void *, std::size_t);
The member function implements block_allocator::deallocate.
cache_chunklist::operator=
template <size_t usz> cache_chunklist<usz>& operator=(const cache_chunklist<usz>&);
The template assignment operator does nothing.
CACHE_FREELIST
#define CACHE_FREELIST(max) <cache_class>
The macro yields Dinkum::allocators::cache_freelist<sizeof(T), max>
.
cache_freelist
template <std::size_t sz, class Max> class cache_freelist { public: cache_freelist(); template <size_t usz> cache_freelist(const cache_freelist<usz>&); template <size_t usz> cache_freelist<usz>& operator=(const cache_freelist<usz>&); void *allocate(std::size_t); void deallocate(void *, std::size_t); };
The cache template class maintains a free list of memory blocks
of size sz
. When the free list is full it uses operator delete
to deallocate
memory blocks. When the free list is empty it uses operator new
to allocate
new memory blocks. The maximum size of the free list is determined by the class
max class Max
.
Overhead: each memory block holds sz
bytes of
usable memory and the data that operator new
and
operator delete
require.
cache_freelist::allocate
void *allocate(std::size_t);
The member function implements block_allocator::allocate.
cache_freelist::cache_freelist
cache_freelist();
template <size_t usz> cache_freelist(const cache_freelist<usz>&);
The constructors construct a cache_freelist
object.
cache_freelist::deallocate
void deallocate(void *, std::size_t);
The member function implements block_allocator::deallocate.
cache_freelist::operator=
template <size_t usz> cache_freelist<usz>& operator=(const cache_freelist<usz>&);
The template assignment operator does nothing.
CACHE_SUBALLOC
#define CACHE_SUBALLOC <cache_class>
The macro yields Dinkum::allocators::cache_suballoc<sizeof(T)>
.
cache_suballoc
template <std::size_t sz, size_t NELTS = 20> class cache_suballoc { public: cache_suballoc(); template <size_t usz> cache_suballoc(const cache_suballoc<usz>&); template <size_t usz> cache_suballoc<usz>& operator=(const cache_suballoc<usz>&); void *allocate(std::size_t); void deallocate(void *, std::size_t); };
The cache template class
stores deallocated memory blocks in a free list with unbounded length, using
freelist<sizeof(T),
max_unbounded>
,
and suballocates memory blocks from a larger chunk allocated with
operator new
when the free list is empty.
Overhead: each chunk holds sz * NELTS
bytes of usable
memory and the data that operator new
and operator delete
require. Allocated chunks are never freed.
cache_suballoc::allocate
void *allocate(std::size_t);
The member function implements block_allocator::allocate.
cache_suballoc::cache_suballoc
cache_suballoc();
template <size_t usz> cache_suballoc(const cache_suballoc<usz>&);
The constructors construct a cache_suballoc
object.
cache_suballoc::deallocate
void deallocate(void *, std::size_t);
The member function implements block_allocator::deallocate.
cache_suballoc::operator=
template <size_t usz> cache_suballoc<usz>& operator=(const cache_suballoc<usz>&);
The template assignment operator does nothing.
freelist
template <std::size_t sz, class Max> class freelist : public Max { public: freelist(); bool push(void *); void *pop(); };
The template class freelist
manages a list of memory blocks
of size sz
with the maximum length of the list determined by
the max class Max
.
freelist::freelist
freelist();
The constructor constructs a freelist
instance.
freelist::pop
void *pop();
The member function returns NULL
if the list is empty.
Otherwise it removes the first memory block from the list and returns
a pointer to that block.
freelist::push
bool push(void *ptr);
The member function returns false if Max::full
returns
true. Otherwise it adds the memory block pointed to by ptr
to the head of the list and returns true.
max_fixed_size
template <std::size_t max> class max_fixed_size { public: max_fixed_size() : nblocks(0) {} bool full() {return max <= nblocks; } void saved() {++nblocks; } void released() {--nblocks; } void allocated(std::size_t = 1) {} void deallocated(std::size_t = 1) {} private: unsigned long nblocks; };
The template class describes a max class object
that limits a freelist object
to a fixed maximum length max
.
max_fixed_size::allocated
void allocated(std::size_t = 1) {}
The member function does nothing.
max_fixed_size::deallocated
void deallocated(std::size_t = 1) {}
The member function does nothing.
max_fixed_size::full
bool full()
{return max <= nblocks; }
The member function returns true if max <= nblocks
.
max_fixed_size::max_fixed_size
max_fixed_size()
: nblocks(0) {}
The constructor initializes the stored value nblocks
to zero.
max_fixed_size::released
void released()
{--nblocks; }
The member function decrements the stored value nblocks
.
max_fixed_size::saved
void saved()
{++nblocks; }
The member function increments the stored value nblocks
.
max_none
template <std::size_t max> class max_none { public: bool full() {return true; } void saved() {} void released() {} void allocated(std::size_t = 1) {} void deallocated(std::size_t = 1) {} };
The template class describes a max class object that limits a freelist object to a maximum length of zero.
max_none::allocated
void allocated(std::size_t = 1) {}
The member function does nothing.
max_none::deallocated
void deallocated(std::size_t = 1) {}
The member function does nothing.
max_none::full
bool full()
{return true; }
The member function returns true.
max_none::released
void released() {}
The member function does nothing.
max_none::saved
void saved() {}
The member function does nothing.
max_unbounded
class max_unbounded { public: bool full() {return false; } void saved() {} void released() {} void allocated(std::size_t = 1) {} void deallocated(std::size_t = 1) {} };
The template class describes a max class object that does not limit the maximum length of a freelist object.
max_unbounded::allocated
void allocated(std::size_t = 1) {}
The member function does nothing.
max_unbounded::deallocated
void deallocated(std::size_t = 1) {}
The member function does nothing.
max_unbounded::full
bool full()
{return false; }
The member function returns false.
max_unbounded::released
void released() {}
The member function does nothing.
max_unbounded::saved
void saved() {}
The member function does nothing.
max_variable_size
class max_variable_size { public: max_variable_size() : nblocks(0), nallocs(0) {} bool full() {return nallocs / 16 + 16 <= nblocks; } void saved() {++nblocks; } void released() {--nblocks; } void allocated(std::size_t n = 1) {nallocs += n; } void deallocated(std::size_t n = 1); {nallocs -= n; } private: unsigned long nblocks; unsigned long nallocs; };
The template class describes a max class object that limits a freelist object to a maximum length that is roughly proportional to the number of allocated memory blocks.
max_variable_size::allocated
void allocated(std::size_t n = 1)
{nallocs += n; }
The member function adds n
to the stored value nallocs
.
max_variable_size::deallocated
void deallocated(std::size_t n = 1)
{nallocs -= n; }
The member function subtracts n
from the stored value nallocs
.
max_variable_size::full
bool full()
{return nallocs / 16 + 16 <= nblocks; }
The member function returns true if nallocs / 16 + 16 <= nblocks
.
max_variable_size::max_variable_size
max_variable_size()
: nblocks(0), nallocs(0) {}
The constructor initializes the stored values nblocks
and nallocs
to zero.
max_variable_size::released
void released()
{--nblocks; }
The member function decrements the stored value nblocks
.
max_variable_size::saved
void saved()
{++nblocks; }
The member function increments the stored value nblocks
.
rts_alloc
template <class Cache> class rts_alloc { public: void *allocate(std::size_t); void deallocate(void *, std::size_t); bool equals(const rts_alloc<Cache>&) const; private: Cache caches[COUNT]; };
The template class describes a filter
that holds an array of Cache
instances and determines which instance
to use for allocation and deallocation at runtime instead of at compile time. It is
used with compilers that cannot compile rebind.
rts_alloc::allocate
void *allocate(std::size_t n);
The member function returns cache[idx].allocate(n)
, where the
index idx
is determined by the requested block size n
,
or, if n
is too large, it returns ::operator new(n)
.
rts_alloc::deallocate
void deallocate(void *ptr, std::size_t n);
The member function calls cache[idx].deallocate(ptr, n)
, where
index idx
is determined by the requested block size n
,
or, if n
is too large, it returns ::operator delete(ptr)
.
rts_alloc::equals
bool equals(const sync<Cache>& other) const;
The member function returns cache[0].equals(other.cache[0])
.
SYNC_DEFAULT
#define SYNC_DEFAULT <sync_template>
If a compiler supports compiling both single-threaded and multi-threaded
applications, for single-threaded applications the macro yields
Dinkum::allocators::sync_none
; in all other cases it
yields Dinkum::allocators::sync_shared
.
sync_none
template <class Cache> class sync_none { public: void *allocate(std::size_t n) {return cache.allocate(n); } void deallocate(void *ptr, std::size_t n) {cache.deallocate(ptr, n); } bool equals(const sync_none<Cache>&) const {return true; } private: static Cache cache; };
The template class describes a synchronization filter that provides no synchronization.
sync_none::allocate
void *allocate(std::size_t n)
{return cache.allocate(n); }
The member function returns cache.allocate(n)
.
sync_none::deallocate
void deallocate(void *ptr, std::size_t n)
{cache.deallocate(ptr, n); }
The member function calls cache.deallocate(ptr, n)
.
sync_none::equals
bool equals(const sync<Cache>&) const
[return true; }
The member function returns true.
sync_per_container
template <class Cache> class sync_per_container : public Cache { public: bool equals(const sync_per_container<Cache>&) const {return false; } };
The template class describes a synchronization filter
that provides a separate Cache
object for each allocator object.
sync_per_container::equals
bool equals(const sync<Cache>&) const
[return false; }
The member function returns false.
sync_per_thread
template <class Cache> class sync_per_thread { public: void *allocate(std::size_t); void deallocate(void *, std::size_t); bool equals(const sync_per_thread<Cache>&) const; private: static threads::thread_specific_ptr<Cache> cache_ptr; };
The template class describes a
synchronization filter
that provides a separate Cache
object for each thread.
Caution: allocators that use sync_per_thread
can
compare equal even though blocks allocated in one thread
cannot be deallocated from another thread. When using one of these allocators memory
blocks allocated in one thread should not be made visible to other threads. In
practice this means that a container that uses one of these allocators should
only be accessed by a single thread.
sync_per_thread::allocate
void *allocate(std::size_t n);
The member function returns the result of a call to Cache::allocate(n)
on the
Cache
object belonging to the current thread. If no Cache
object
has been allocated for the current thread it first allocates one.
sync_per_thread::deallocate
void deallocate(void *ptr, std::size_t n);
The member function calls Cache::deallocate(ptr, n)
on the
Cache
object belonging to the current thread. If no Cache
object
has been allocated for the current thread it first allocates one.
sync_per_thread::equals
bool equals(const sync<Cache>& other) const;
The member function returns false if no Cache
object has been allocated
for this object or for other
in the current thread. Otherwise it returns the result
of applying operator==
to the two Cache
objects.
sync_shared
template <class Cache> class sync_shared { public: void *allocate(std::size_t); void deallocate(void *, std::size_t); bool equals(const sync_shared<Cache>&) const; private: static Cache cache; static threads::mutex mutex; };
The template class describes a synchronization filter
that uses a mutex to control access to a Cache
object that is shared by
all allocators.
sync_shared::allocate
void *allocate(std::size_t n);
The member function locks the mutex, calls cache.allocate(n)
, unlocks
the mutex, and returns the result of the earlier call to cache.allocate(n)
.
sync_shared::deallocate
void deallocate(void *ptr, std::size_t n);
The member function locks the mutex, calls cache.deallocate(ptr, n)
, and
unlocks the mutex.
sync_shared::equals
bool equals(const sync<Cache>& other) const;
The member function returns cache.equals(other.cache)
.
See also the Table of Contents and the Index.
Copyright © 1992-2013 by Dinkumware, Ltd. All rights reserved.