好 看了一天的object_pool 容易嘛 现在总结下
这个 什么的 继承自pool
class pool
{
details::PODptr<size_type> list;
}
这里list干什么的呢 如下所示 保存着分配的所有数据块
其中的sz不仅仅包含数据本身的大小 还包括下个数据块的指针和大小
所以 整个数据块就可以串联起来 就像名字list一样
class PODptr
{
char * ptr;
size_type sz;
}
一个pool的内存就在ptr里面了 一开始空的
1 const size_type partition_size = alloc_size();
2 const size_type POD_size = next_size * partition_size +
3 details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value + sizeof(size_type);
4 char * const ptr = UserAllocator::malloc(POD_size);
5 next_size <<= 1;
在这里就分配内存了 第一次next_size=32 然后是64,128...partition_size 大概就是我们要分配类型的字节大小
后面两个值details::pool::ct_lcm<sizeof(size_type), sizeof(void *)>::value和sizeof(size_type)
一个是指向下个内存块的指针，一个是下个内存块的大小
一般都为4个字节，加起来就是8个字节，
所以其总大小为数据块大小+8个字节
好 下面就是比较关键的 就是对这块内存块的管理
好 pool继承自simple_segregated_storage
class simple_segregated_storage
{
protected:
void * first;
}
然后嘛 first在一开始内存分配的时候就指向内存块的开始
并且采用boost大无上手法可以让内存块串联起来 不管怎么样 nextof(first)就是下一个我们的类型块，
一开始不是分配了32块那样的类型嘛，值得注意的是，
first始终是指向第一个空闲块的，每次要分配一个类型块时，取first值，返回给请求者，然后first=nextof(first)
好 那么释放怎么做的呢 事实上很简单 即把要释放的块重新用first回收起来 并且是有序的串起来 即按照内存从小到大用next()
串起来 这样有啥好处呢 在~object_pool发生时，比较方便快速，具体看代码就是了 为了每次在destroy()时保持有序：
1 void ordered_free(void * const chunk)
2 {
3 // This (slower) implementation of 'free' places the memory
4 // back in the list in its proper order.
5 // Find where "chunk" goes in the free list
6 void * const loc = find_prev(chunk);
7 // Place either at beginning or in middle/end
8 if (loc == 0)
9 free(chunk);
10 else
11 {
12 nextof(chunk) = nextof(loc);
13 nextof(loc) = chunk;
14 }
15 }
16 template <typename SizeType>
17 void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)
18 {
19 // Handle border case
20 if (first == 0 || std::greater<void *>()(first, ptr))
21 return 0;
22 void * iter = first;
23 while (true)
24 {
25 // if we're about to hit the end or
26 // if we've found where "ptr" goes
27 if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr))
28 return iter;
29 iter = nextof(iter);
30 }
31 }
很容易构造一种最坏复杂度的情况：
1 const int N = 10000;
2 Sample* a[N];
3 for( i=0; i<N; ++i)
4 a[i] = pool.cunstruct();
5 for(i=0; i<N; ++i)
6 pool.destory( a[i] );
在这种情况下，每次的find_prev会耗费O(N)时间，需要注意下。。。
posted on 2011-04-26 18:18
野猪红 阅读(1286)
评论(0) 编辑 收藏 引用 所属分类:
算法