"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.