以前在一个高性能的场合，需要十分频繁的使用临时缓存。由于所需的缓存大小我事先知道，所以我索性开了一块全局缓存，不要骂我土，它背后可以一个崇高的设计哲学：奥坎姆的剃刀。
不过，后边我越看越恶心，越看越想吐，于是就想实现一个分配和释放都为常数时间的MemPool. 虽然内存池是一个老得不老再老的话题，但是我并没有找到一个能达到我要求的设计。
虽然我对C++的任何细节都毫不知情，不过还是免为其难的写了一个有诸多缺陷的XMemPool。
先说下大致思路：
1 POOL将分配划分成两种情况，小缓存分配，大缓存分配。小于4K的我把它当成小缓存。小缓存块BlockSize按8字节步长增长，大块默认按4K步长增长。每种Size的块用两个链表进行管理（free & used）。
2 分配。要是size超过了最大能分配的大小或者池容量超过限制就直接调用系统分配。计算相应块的index（如果是调用系统分配的index会置为-1）, 把free list第一个结点移到used list的第一个结点
3 释放。 如果块的index为-1直接delete。将要释放的块直接移动到free list的第一个结点。
这样的话缺点也是相当明显的：
1 用户必要从Block获取缓存
2 用户非常有必要对缓存大小事先按需求进行合理估计。
1
#ifndef _X_MEM_POOL_H_
2#define _X_MEM_POOL_H_
3
4//! (1)alloc：O(1)
5//! (2)free ：O(1)
6//! (3)not thread safe
7
8class XMemPool;
9class XMemBlock
10
{
11
public:
12 XMemBlock( const int& index, const size_t& size ):
13 _index( index ),
14 _next( 0 ),
15 _pre( 0 ),
16 _size( size )
17
{
18 _data = new char[size];
19
}
20 ~XMemBlock()
21 {
22 delete []_data;
23 }
24
25public:
26 friend class XMemPool;
27 template<class T>
28 T* getMem() const { return (T*)_data; }
29
30private:
31 const int _index;
32 const size_t _size;
33 char *_data;
34 XMemBlock *_next;
35 XMemBlock *_pre;
36
};
37
38const size_t S_MEM_THRE = 4096;//4K
39const size_t S_POOL_STEP = 8;
40const size_t LARGE_POOL_STEP = 4096;//4K
41const size_t SMAX_SUB_POOL_CAP = 128;
42const size_t LMAX_SUB_POOL_CAP = 64;
43
44class XMemPool
45{
46public:
47 /**//*
48 maxBlockSize 此内存池能分配的最大的内存
49 maxSubPoolCapability 每个子内存池的最大容量
50 poolXep 相邻子内存池之间的BlockSize的差距，即每个子内存池大小为poolXep的整数倍
51
52 这里小块的容量，大小写死了的，只有大块的可以配置
53 */
54 XMemPool( const size_t& maxBlockSize, const size_t& lmaxSubPoolCapability = LMAX_SUB_POOL_CAP,\
55 const size_t& lpoolXep = LARGE_POOL_STEP );
56 ~XMemPool();
57public:
58 XMemBlock *alloc( size_t size );
59 void free( XMemBlock* block );
60 void destroy();
61 size_t getTotalMemSize() const { return _totalMemSize; };
62
63private:
64 const size_t _maxBlockSize; //最大能分配的内存块
65 const size_t _lmaxSubPoolCapability; //每种块的最大小数（大块）
66 static const size_t\
67 _smaxSubPoolCapability = SMAX_SUB_POOL_CAP;//每种块的最大小数（小块）
68 const size_t _lpoolXep; //大块的增长步长
69 static const size_t\
70 _spoolXep = S_POOL_STEP; //小块的步长
71 XMemBlock **_ssubPool[2];//0:free 1:used 小块的链表数组
72 XMemBlock **_lsubPool[2];//大块的链表数组
73 size_t _ssubPoolNum;//小块的种类个数
74 size_t _lsubPoolNum;//大块的种类个数
75 size_t *_lsubPoolSize;//每种size大块的个数
76 size_t *_ssubPoolSize;//每种size小块的个数
77 size_t _totalMemSize;//内存池总容量
78};
79
80#endif
1XMemPool::XMemPool( const size_t& maxBlockSize, const size_t& lmaxSubPoolCapability, const size_t& lpoolXep ):\
2_maxBlockSize( maxBlockSize ),
3_lmaxSubPoolCapability( lmaxSubPoolCapability ),
4_lpoolXep( lpoolXep )
5{
6 _ssubPoolNum = ( S_MEM_THRE + _spoolXep - 1 ) / _spoolXep;
7 _lsubPoolNum = ( _maxBlockSize + _lpoolXep - 1 ) / _lpoolXep;
8 _totalMemSize = 0;
9 _ssubPoolSize = new size_t[_ssubPoolNum];
10 _lsubPoolSize = new size_t[_lsubPoolNum];
11 _ssubPool[0] = new XMemBlock*[_ssubPoolNum];
12 _ssubPool[1] = new XMemBlock*[_ssubPoolNum];
13 for( int i = 0; i < _ssubPoolNum; i++ )
14 {
15 _ssubPool[0][i] = 0;
16 _ssubPool[1][i] = 0;
17 _ssubPoolSize[i] = 0;
18 }
19 _lsubPool[0] = new XMemBlock*[_lsubPoolNum];
20 _lsubPool[1] = new XMemBlock*[_lsubPoolNum];
21 for( int i = 0; i < _lsubPoolNum; i++ )
22 {
23 _lsubPool[0][i] = 0;
24 _lsubPool[1][i] = 0;
25 _lsubPoolSize[i] = 0;
26 }
27}
28
29XMemBlock* XMemPool::alloc( size_t size ) //byte unit
30{
31 if( size <= S_MEM_THRE )
32 {
33 size_t idx = ( size + _spoolXep - 1 ) / _spoolXep - 1;
34 XMemBlock *block = 0;
35 if( _ssubPool[0][idx] )
36 {
37 block = _ssubPool[0][idx];
38 _ssubPool[0][idx] = block->_next;
39 if( _ssubPool[1][idx] )
40 _ssubPool[1][idx]->_pre = block;
41 block->_next = _ssubPool[1][idx];
42 _ssubPool[1][idx] = block;
43 _ssubPool[1][idx]->_pre = 0;
44 return block;
45 }
46 else if( _ssubPoolSize[idx] < _smaxSubPoolCapability )
47 {
48 size_t msize = (idx + 1)*_spoolXep;
49 _totalMemSize += msize;
50 block = new XMemBlock( idx, msize );
51 _ssubPoolSize[idx]++;
52 if( _ssubPool[1][idx] )
53 _ssubPool[1][idx]->_pre = block;
54 block->_next = _ssubPool[1][idx];
55 _ssubPool[1][idx] = block;
56 return block;
57 }
58 }
59 else if( size <= _maxBlockSize )
60 {
61 size_t idx = ( size + _lpoolXep - 1 ) / _lpoolXep - 1;
62 XMemBlock *block = 0;
63 if( _lsubPool[0][idx] )
64 {
65 block = _lsubPool[0][idx];
66 _lsubPool[0][idx] = block->_next;
67 if( _lsubPool[1][idx] )
68 _lsubPool[1][idx]->_pre = block;
69 block->_next = _lsubPool[1][idx];
70 _lsubPool[1][idx] = block;
71 _lsubPool[1][idx]->_pre = 0;
72 return block;
73 }
74 else if( _lsubPoolSize[idx] < _lmaxSubPoolCapability )
75 {
76 size_t msize = (idx + 1)*_lpoolXep;
77 _totalMemSize += msize;
78 block = new XMemBlock( idx, msize );
79 _lsubPoolSize[idx]++;
80 if( _lsubPool[1][idx] )
81 _lsubPool[1][idx]->_pre = block;
82 block->_next = _lsubPool[1][idx];
83 _lsubPool[1][idx] = block;
84 return block;
85 }
86 }
87
88 return (new XMemBlock( -1, size ));
89}
90
91void XMemPool::free( XMemBlock *block )
92{
93 if( block->_index < 0 )
94 {
95 delete block;
96 return;
97 }
98 if( block->_size <= S_MEM_THRE )
99 {
100 if( block->_next )
101 block->_next->_pre = block->_pre;
102 if( block->_pre )
103 block->_pre->_next = block->_next;
104 else if( !block->_next && !block->_pre )
105 _ssubPool[1][block->_index] = 0;
106 block->_next = _ssubPool[0][block->_index];
107 if( _ssubPool[0][block->_index] )
108 _ssubPool[0][block->_index]->_pre = block;
109 _ssubPool[0][block->_index] = block;
110 }
111 else
112 {
113 if( block->_next )
114 block->_next->_pre = block->_pre;
115 if( block->_pre )
116 block->_pre->_next = block->_next;
117 else if( !block->_next && !block->_pre )
118 _lsubPool[1][block->_index] = 0;
119 block->_next = _lsubPool[0][block->_index];
120 if( _lsubPool[0][block->_index] )
121 _lsubPool[0][block->_index]->_pre = block;
122 _lsubPool[0][block->_index] = block;
123 }
124}
125
126void XMemPool::destroy()
127{
128 for( int i = 0; i < _ssubPoolNum; i++ )
129 {
130 XMemBlock *block = _ssubPool[0][i], *tmp;
131 while( block )
132 {
133 tmp = block->_next;
134 delete block;
135 block = tmp;
136 }
137 _ssubPool[0][i] = 0;
138
139 block = _ssubPool[1][i];
140 while( block )
141 {
142 tmp = block->_next;
143 delete block;
144 block = tmp;
145 }
146 _ssubPool[1][i] = 0;
147 _ssubPoolSize[i] = 0;
148 }
149 for( int i = 0; i < _lsubPoolNum; i++ )
150 {
151 XMemBlock *block = _lsubPool[0][i], *tmp;
152 while( block )
153 {
154 tmp = block->_next;
155 delete block;
156 block = tmp;
157 }
158 _lsubPool[0][i] = 0;
159
160 block = _lsubPool[1][i];
161 while( block )
162 {
163 tmp = block->_next;
164 delete block;
165 block = tmp;
166 }
167 _lsubPool[1][i] = 0;
168 _lsubPoolSize[i] = 0;
169 }
170}
171
172XMemPool::~XMemPool()
173{
174 destroy();
175 delete []_ssubPoolSize;
176 delete []_lsubPoolSize;
177 delete []_ssubPool[0];
178 delete []_ssubPool[1];
179 delete []_lsubPool[0];
180 delete []_lsubPool[1];
181}
1XMemPool samplePool(4096);
2XMemBlock *sampleBlock = samplePool.alloc(sizeof(int)*100);
3int *sampleData = sampleBlock->getMem<int>();
4samplePool.free(sampleBlock);
很多细节还没考虑到，谁能为我推荐一个好的设计方案？双O(1)的