mario::konrad
programming / C++ / sailing / nerd stuff
C++ Allocators
© 2013-03-20 / Mario Konrad

This is a demonstration how to write your own allocators to be used with standard containers. This tutorial does not show the most efficient allocator implementation but rather the principles.

alloc.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "alloc_new_delete.hpp"
#include "alloc_pool.hpp"
#include <vector>
#include <iostream>

template <class Allocator> void test(void)
{
    {
    std::vector<int, Allocator> v;

    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.push_back(10);
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.push_back(20);
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.push_back(30);
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.push_back(40);
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.push_back(50);
    v.push_back(60);
    v.push_back(70);
    v.push_back(80);
    }
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    {
    std::vector<int, Allocator> v;
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.push_back(10);
    v.push_back(20);
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    v.erase(v.begin());
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
    }
    std::cout << "=========================== " << __FUNCTION__ << ":" << __LINE__ << std::endl;
}

int main(int, char **)
{
    test<alloc_new_delete<int> >();
    test<alloc_pool<int, 16> >();
    return 0;
}

alloc_new_delete.hpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#ifndef __ALLOC_NEW_DELETE__HPP__
#define __ALLOC_NEW_DELETE__HPP__

#include <limits>
#include <cstddef>
#include <bits/allocator.h>

template <typename T> class alloc_new_delete
{
    public:
        typedef T value_type;
        typedef value_type * pointer;
        typedef const value_type * const_pointer;
        typedef value_type & reference;
        typedef const value_type const_reference;
        typedef std::size_t size_type;
        typedef std::ptrdiff_t difference_type;

    public:
        template <typename U> struct rebind
        {
            typedef alloc_new_delete<U> other;
        };

    public:
        explicit alloc_new_delete()
        {}

        ~alloc_new_delete()
        {}

        explicit alloc_new_delete(const alloc_new_delete &)
        {}

        template <typename U> explicit alloc_new_delete(alloc_new_delete<U> const &)
        {}

    public:
        pointer address(reference a)
        {
            return &a;
        }

        const_pointer address(const_reference a)
        {
            return &a;
        }

    public:
        pointer allocate(size_type n, typename std::allocator<void>::const_pointer = NULL)
        {
            return reinterpret_cast<pointer>(::operator new(n * sizeof(T)));
        }

        void deallocate(pointer p, size_type)
        {
            ::operator delete(p);
        }

    public:
        size_type max_size() const
        {
            return std::numeric_limits<size_type>::max() / sizeof(T);
        }

    public:
        void construct(pointer p, const T & t)
        {
            new(p) T(t);
        }

        void destroy(pointer p)
        {
            p->~T();
        }

    public:
        bool operator==(const alloc_new_delete &)
        {
            return true;
        }

        bool operator!=(const alloc_new_delete & a)
        {
            return !operator==(a);
        }
};

#endif

alloc_pool.hpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#ifndef __ALLOC_POOL__HPP__
#define __ALLOC_POOL__HPP__

#include <limits>
#include <cstddef>
#include <bits/allocator.h>

template <typename T, std::size_t N> class alloc_pool
{
    private:
        T data[N];
        bool state[N];

    public:
        typedef T value_type;
        typedef value_type * pointer;
        typedef const value_type * const_pointer;
        typedef value_type & reference;
        typedef const value_type const_reference;
        typedef std::size_t size_type;
        typedef std::ptrdiff_t difference_type;

    public:
        template <typename U> struct rebind
        {
            typedef alloc_pool<U, N> other;
        };

    public:
        explicit alloc_pool()
        {
            for (size_type i = 0; i < N; ++i) state[i] = false;
        }

        ~alloc_pool()
        {}

    private: // disable them for pulic use
        explicit alloc_pool(const alloc_pool &)
        {}

        template <typename U> explicit alloc_pool(alloc_pool<U, N> const &)
        {}

        alloc_pool & operator=(const alloc_pool &)
        {
            return *this;
        }

        template <typename U> alloc_pool<T,N> & operator=(const alloc_pool<U, N> &)
        {
            return *this;
        }

    public:
        pointer address(reference a)
        {
            return &a;
        }

        const_pointer address(const_reference a)
        {
            return &a;
        }

    public:
        pointer allocate(size_type n, typename std::allocator<void>::const_pointer = NULL)
        {
            pointer p;
            size_type j = 0;
            size_type num_free = 0;
            for (size_type i = 0; (i < N) && (num_free < n); ++i) {
                if (!state[i]) {
                    if (num_free == 0) {
                        p = &data[i];
                        j = i;
                    }
                    ++num_free;
                } else {
                    num_free = 0;
                }
            }
            if (num_free < n) return pointer();
            for (; num_free > 0; --num_free, ++j) state[j] = true;
            return p;
        }

        void deallocate(pointer p, size_type n)
        {
            for (size_type i = 0; i < N; ++i) {
                if (&data[i] == p) {
                    for (size_type j = 0; j < n; ++j, ++i) {
                        state[i] = false;
                    }
                    return;
                }
            }
        }

    public:
        size_type max_size() const
        {
            return N;
        }

    public:
        void construct(pointer p, const T & t)
        {
            new(p) T(t);
        }

        void destroy(pointer p)
        {
            p->~T();
        }

    public:
        bool operator==(const alloc_pool &)
        {
            return true;
        }

        bool operator!=(const alloc_pool & a)
        {
            return !operator==(a);
        }
};

#endif

Makefile:

.PHONY: all clean

CXX=g++
CXXFLAGS=-ggdb -Wall -Wextra -ansi -pedantic -O2

all : alloc

ALLOC_SRC=alloc.cpp

alloc : $(ALLOC_SRC:.cpp=.o)
    $(CXX) -o $@ $^ $(CXXFLAGS)

-include $(ALLOC_SRC:.cpp=.d)

clean :
    rm -f *.o *.d *.exe *.stackdump
    rm -f alloc

%.o : %.cpp
    $(CXX) -o $@ -c $< $(CXXFLAGS)
    $(CXX) -MM $< > $*.d