00001
00018 #ifndef node_pool_h
00019 #define node_pool_h
00020
00021 class MemPool
00022 {
00023 public :
00024
00025 MemPool(unsigned int sz) : esize(sz<sizeof(Link)? sizeof(Link) : sz) {}
00026 ~MemPool()
00027 {
00028 Chunk* n = chunks;
00029 while(n)
00030 {
00031 Chunk* p = n;
00032 n = n->next;
00033 delete p;
00034 }
00035 }
00036
00037 void* allocate()
00038 {
00039 if (head == 0) grow();
00040 Link* p = head;
00041 head = p->next;
00042 return static_cast<void*>(p);
00043 }
00044
00045 void deallocate(void* b)
00046 {
00047 Link* p = static_cast<Link*>(b);
00048 p->next = head;
00049 head = p;
00050 }
00051
00052 private :
00053
00054 void grow()
00055 {
00056 Chunk* n = new Chunk;
00057 n->next = chunks;
00058 chunks = n;
00059
00060 const int nelem = Chunk::size/esize;
00061 char* start = n->mem;
00062 char* last = &start[(nelem-1)*esize];
00063 for (char* p = start; p < last; p += esize)
00064 {
00065 reinterpret_cast<Link*>(p)->next =
00066 reinterpret_cast<Link*>(p + esize);
00067 }
00068
00069 reinterpret_cast<Link*>(last)->next = 0;
00070 head = reinterpret_cast<Link*>(start);
00071 }
00072
00073 struct Link
00074 {
00075 Link* next;
00076 };
00077
00078 struct Chunk
00079 {
00080 enum {size = 8 * 1024 - 16};
00081 Chunk* next;
00082 char mem[size];
00083 };
00084
00085 Chunk* chunks;
00086 const unsigned int esize;
00087 Link* head;
00088 };
00089
00090 template<class T>
00091 class Node_alloc
00092 {
00093 public :
00094
00095 T* allocate(void)
00096 {
00097 T* t = static_cast<T*>(mem.allocate());
00098 t = new (t) T;
00099 return t;
00100 }
00101
00102 T* construct(const T& org)
00103 {
00104 T* t = static_cast<T*>(mem.allocate());
00105 t = new (t) T(org);
00106 return t;
00107 }
00108
00109 void deallocate(T* t)
00110 {
00111 t->~T();
00112 mem.deallocate(static_cast<void*>(t));
00113 }
00114
00115 private :
00116 static MemPool mem;
00117 };
00118
00119
00120 template <class T>
00121 class Standard_alloc
00122 {
00123 public :
00124 Standard_alloc() {}
00125
00126 T* allocate(size_t arity = 1)
00127 {
00128 if (arity == 0)
00129 return 0;
00130
00131 return new T [arity];
00132 }
00133
00134 T* construct(size_t arity, T* org)
00135 {
00136 if (arity == 0)
00137 return 0;
00138
00139 T* t = new T [arity];
00140
00141 for (int i = 0; i < arity; ++i)
00142 {
00143 t = T(org[i]);
00144 }
00145 }
00146
00147 void deallocate(T* t, size_t arity = 1)
00148 {
00149 if (arity == 0)
00150 return ;
00151
00152 delete [] t;
00153 }
00154
00155 };
00156
00157 template <class T>
00158 class Standard_Node_alloc
00159 {
00160 public :
00161 Standard_Node_alloc() {}
00162
00163 T* allocate(void)
00164 {
00165 return new T;
00166 }
00167
00168 T* construct(const T& org)
00169 {
00170 return new T(org);
00171 }
00172
00173 void deallocate(T* t)
00174 {
00175 delete t;
00176 }
00177
00178 };
00179
00180 template <class T>
00181 class Tree_alloc
00182 {
00183 public :
00184 Tree_alloc() {}
00185
00186 T* allocate(size_t arity)
00187 {
00188 T* t;
00189
00190 switch(arity)
00191 {
00192
00193 case 0 : return 0;
00194 case 1 :
00195 {
00196 t = static_cast<T*>(mem1.allocate());
00197 new (t) T;
00198 break;
00199 }
00200 case 2 :
00201 {
00202 t = static_cast<T*>(mem2.allocate());
00203 new (t) T;
00204 new (&t[1]) T;
00205 break;
00206 }
00207 case 3 :
00208 {
00209 t = static_cast<T*>(mem3.allocate());
00210 new (t) T;
00211 new (&t[1]) T;
00212 new (&t[2]) T;
00213 break;
00214 }
00215 default :
00216 {
00217 return new T[arity];
00218 }
00219 }
00220
00221 return t;
00222 }
00223
00224 T* construct(size_t arity, T* org)
00225 {
00226 T* t;
00227
00228 switch(arity)
00229 {
00230
00231 case 0 : return 0;
00232 case 1 :
00233 {
00234 t = static_cast<T*>(mem1.allocate());
00235 new (t) T(*org);
00236 break;
00237 }
00238 case 2 :
00239 {
00240 t = static_cast<T*>(mem2.allocate());
00241 new (t) T(*org);
00242 new (&t[1]) T(org[1]);
00243 break;
00244 }
00245 case 3 :
00246 {
00247 t = static_cast<T*>(mem3.allocate());
00248 new (t) T(*org);
00249 new (&t[1]) T(org[1]);
00250 new (&t[1]) T(org[2]);
00251 break;
00252 }
00253 default :
00254 {
00255 t = new T[arity];
00256 for (int i = 0; i < arity; ++i)
00257 {
00258 t[i] = T(org[i]);
00259 }
00260 }
00261 }
00262
00263 return t;
00264 }
00265
00266
00267
00268 void deallocate(T* t, size_t arity)
00269 {
00270 switch(arity)
00271 {
00272 case 0: return;
00273 case 3 :
00274 {
00275 t[2].~T(); t[1].~T(); t[0].~T();
00276 mem3.deallocate(static_cast<void*>(t));
00277 return;
00278 }
00279 case 2 :
00280 {
00281 t[1].~T(); t[0].~T();
00282 mem2.deallocate(static_cast<void*>(t));
00283 return;
00284 }
00285 case 1 :
00286 {
00287 t[0].~T();
00288 mem1.deallocate(static_cast<void*>(t));
00289 return;
00290 }
00291 default :
00292 {
00293 delete [] t;
00294 return;
00295 }
00296 }
00297 }
00298
00299
00300 private :
00301 static MemPool mem1;
00302 static MemPool mem2;
00303 static MemPool mem3;
00304 };
00305
00306
00307 template <class T> MemPool Node_alloc<T>::mem = sizeof(T);
00308
00309 template <class T> MemPool Tree_alloc<T>::mem1 = sizeof(T);
00310 template <class T> MemPool Tree_alloc<T>::mem2 = sizeof(T) * 2;
00311 template <class T> MemPool Tree_alloc<T>::mem3 = sizeof(T) * 3;
00312
00313 #endif