好 看了一天的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 野猪红 阅读(1029) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理