面向自由编程

c++内存管理系列：bitmap-allocator

Posted on Edited on In
Symbols count in article: 1.5k Reading time ≈ 1 mins.

allocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename _Tp>
class bitmap_allocator: private free_list{
    pointer 
    allocate(size_type __n)
    {
        if (__n > this->max_size())
            std::__throw_bad_alloc();

        if (__builtin_expect(__n == 1, true))//如果数量为1个,则调用_M_allocate_single_object()
            return this->_M_allocate_single_object();
        else	//如果申请的数量大于1个,则直接调用operator new
        { 
            const size_type __b = __n * sizeof(value_type);
            return reinterpret_cast<pointer>(::operator new(__b));
        }
    }
}

图解形式：

首先是64个blocks，每一个对象占用1个block，64个blocks加上bitmap[1]和bitmap[0]再加上use count形成一个super block。即super block = 64block + bitmap[1] + bitmap[0];
use count表示64个block已经用了几个，如果某一个block被使用了，那么bitmap[1]和bitmap[0]相应bit的数字变为0，bitmap[1]和bitmap[0]均为unsigned int，所以两个加起来共有64比特，也就可以表示64个block的使用情况。
在最前面还有一个数字，表示super block的大小，上图中的大小为：4(use count)+4 * 2(bitmap)+648(单个对象大小)=524字节。单个对象的大小只能是8的倍数。

多个super block是通过__mini_vector管理的，__mini_vector是一个vector，但不是标准库的vector，而是自己写的一个vector，但它与标准库中的vector拥有同样的特性——两倍增长。也就是说，如果64个block用光了，下次会分配128个block。
__mini_vector有3个用来管理内存的成员变量。

1
2
3
4
private:
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;

当64个block用光时，会再申请128个，然后bitmap变为4个。和vector的成长一样，会申请另一块内存然后将现在的搬过去：



每次都这样成长两倍，2的幂次方级别地成长。

deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename _Tp>
class bitmap_allocator: private free_list{
    void 
    deallocate(pointer __p, size_type __n) throw()
    {
        if (__builtin_expect(__p != 0, true))
        {
            if (__builtin_expect(__n == 1, true))//如果数量为1,则调用_M_deallocate_single_object()释放
                this->_M_deallocate_single_object(__p);
            else
                ::operator delete(__p);//数量大于1使用operator delete释放
        }
    }
}