以前在一個高性能的場合，需要十分頻繁的使用臨時緩存。由于所需的緩存大小我事先知道，所以我索性開了一塊全局緩存，不要罵我土，它背后可以一個崇高的設計哲學：奧坎姆的剃刀。
不過，后邊我越看越惡心，越看越想吐，于是就想實現一個分配和釋放都為常數時間的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)的