00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 namespace Gecode {
00043
00044 namespace Memory {
00049 namespace Config {
00053 const size_t hcsz_min = 2 * 1024;
00061 const size_t hcsz_max = 64 * 1024;
00068 const int hcsz_inc_ratio = 8;
00078 const int hcsz_dec_ratio = 2;
00079
00091 const int fl_unit_size = ((sizeof(void*) == 4) ? 2 : 3);
00100 const int fl_size_min = ((sizeof(void*) == 4) ? 3 : 2);
00109 const int fl_size_max = ((sizeof(void*) == 4) ? 3 : 3);
00117 const int fl_refill = 8;
00125 #ifndef GECODE_MEMORY_ALIGNMENT
00126 #define GECODE_MEMORY_ALIGNMENT 8
00127 #endif
00128 }
00129 }
00130
00139 class FreeList {
00140 protected:
00142 FreeList* _next;
00143 public:
00145 FreeList(void);
00147 FreeList(FreeList* n);
00149 FreeList* next(void) const;
00151 void next(FreeList* n);
00152 };
00153
00155 class MemoryManager {
00156 private:
00158 class HeapChunk {
00159 public:
00161 HeapChunk* next;
00163 double area[1];
00164 };
00165 public:
00167 MemoryManager(void);
00169 MemoryManager(MemoryManager& mm, size_t s_sub);
00171 ~MemoryManager(void);
00172
00173 private:
00174 size_t cur_hcsz;
00175 HeapChunk* cur_hc;
00176 size_t requested;
00177
00178 char* start;
00179 size_t lsz;
00180
00182 GECODE_KERNEL_EXPORT
00183 void alloc_refill(size_t s);
00185 void alloc_fill(size_t s, bool first);
00186
00187 public:
00189 void* alloc(size_t s);
00191 size_t allocated(void) const;
00193 void* subscriptions(void) const;
00194
00195 private:
00197 FreeList* fl[Memory::Config::fl_size_max-Memory::Config::fl_size_min+1];
00199 template <size_t> void fl_refill(void);
00201 static size_t sz2i(size_t);
00203 static size_t i2sz(size_t);
00204
00205 public:
00207 template <size_t s>
00208 void* fl_alloc(void);
00210 template <size_t> void fl_dispose(FreeList* f, FreeList* l);
00211
00212 private:
00214 class ReuseChunk {
00215 public:
00217 size_t size;
00219 ReuseChunk* next;
00220 };
00222 ReuseChunk* slack;
00223 public:
00225 void reuse(void* p, size_t s);
00226 };
00227
00228
00229
00230
00231
00232
00233
00234 forceinline
00235 FreeList::FreeList(void) {}
00236
00237 forceinline
00238 FreeList::FreeList(FreeList* n)
00239 : _next(n) {}
00240
00241 forceinline FreeList*
00242 FreeList::next(void) const {
00243 return _next;
00244 }
00245
00246 forceinline void
00247 FreeList::next(FreeList* n) {
00248 _next = n;
00249 }
00250
00251 forceinline size_t
00252 MemoryManager::sz2i(size_t s) {
00253 assert(s >= (Memory::Config::fl_size_min << Memory::Config::fl_unit_size));
00254 assert(s <= (Memory::Config::fl_size_max << Memory::Config::fl_unit_size));
00255 return (s >> Memory::Config::fl_unit_size) - Memory::Config::fl_size_min;
00256 }
00257
00258 forceinline size_t
00259 MemoryManager::i2sz(size_t i) {
00260 return (i + Memory::Config::fl_size_min) << Memory::Config::fl_unit_size;
00261 }
00262
00263
00264
00265
00266
00267
00268
00269 forceinline size_t
00270 MemoryManager::allocated(void) const {
00271 return requested;
00272 }
00273
00274 forceinline void*
00275 MemoryManager::alloc(size_t sz) {
00276
00277 assert((sz > 0) && ((sz % 4) == 0));
00278 #if GECODE_MEMORY_ALIGNMENT == 8
00279
00280 sz += sz & 4;
00281 #endif
00282
00283 if (sz > lsz)
00284 alloc_refill(sz);
00285 lsz -= sz;
00286 return start + lsz;
00287 }
00288
00289 forceinline void*
00290 MemoryManager::subscriptions(void) const {
00291 return &cur_hc->area[0];
00292 }
00293
00294 forceinline void
00295 MemoryManager::alloc_fill(size_t sz, bool first) {
00296
00297 if (((requested > Memory::Config::hcsz_inc_ratio*cur_hcsz) ||
00298 (sz > cur_hcsz)) &&
00299 (cur_hcsz < Memory::Config::hcsz_max)) {
00300 cur_hcsz <<= 1;
00301 }
00302
00303 size_t overhead = sizeof(HeapChunk) - sizeof(double);
00304 sz += overhead;
00305
00306 size_t allocate = ((sz > cur_hcsz) ?
00307 (((size_t) (sz / cur_hcsz)) + 1) * cur_hcsz : cur_hcsz);
00308
00309 HeapChunk* hc = static_cast<HeapChunk*>(Memory::malloc(allocate));
00310 start = Support::ptr_cast<char*>(&hc->area[0]);
00311 lsz = allocate - overhead;
00312
00313 if (first) {
00314 requested = allocate;
00315 hc->next = NULL; cur_hc = hc;
00316 } else {
00317 requested += allocate;
00318 hc->next = cur_hc->next; cur_hc->next = hc;
00319 }
00320 #ifdef GECODE_MEMORY_CHECK
00321 for (char* c = start; c < (start+lsz); c++)
00322 *c = 0;
00323 #endif
00324 }
00325
00326 forceinline
00327 MemoryManager::MemoryManager(void)
00328 : cur_hcsz(Memory::Config::hcsz_min), requested(0), slack(NULL) {
00329 alloc_fill(cur_hcsz,true);
00330 for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00331 i--; )
00332 fl[i] = NULL;
00333 }
00334
00335 forceinline
00336 MemoryManager::MemoryManager(MemoryManager& mm, size_t s_sub)
00337 : cur_hcsz(mm.cur_hcsz), requested(0), slack(NULL) {
00338 #if GECODE_MEMORY_ALIGNMENT == 8
00339 s_sub += s_sub & 4;
00340 #endif
00341 if ((mm.requested < Memory::Config::hcsz_dec_ratio*mm.cur_hcsz) &&
00342 (cur_hcsz > Memory::Config::hcsz_min) &&
00343 (s_sub*2 < cur_hcsz))
00344 cur_hcsz >>= 1;
00345 alloc_fill(cur_hcsz+s_sub,true);
00346
00347 lsz -= s_sub;
00348 start += s_sub;
00349 for (size_t i = Memory::Config::fl_size_max-Memory::Config::fl_size_min+1;
00350 i--; )
00351 fl[i] = NULL;
00352 }
00353
00354 forceinline
00355 MemoryManager::~MemoryManager(void) {
00356
00357 HeapChunk* hc = cur_hc;
00358 do {
00359 HeapChunk* t = hc; hc = hc->next;
00360 Memory::free(t);
00361 } while (hc != NULL);
00362 }
00363
00364
00365
00366
00367
00368
00369
00370 forceinline void
00371 MemoryManager::reuse(void* p, size_t s) {
00372 #ifdef GECODE_MEMORY_CHECK
00373 {
00374 char* c = static_cast<char*>(p);
00375 char* e = c + s;
00376 while (c < e) {
00377 *c = 0; c++;
00378 }
00379 }
00380 #endif
00381 if (s < (Memory::Config::fl_size_min<<Memory::Config::fl_unit_size))
00382 return;
00383 if (s > (Memory::Config::fl_size_max<<Memory::Config::fl_unit_size)) {
00384 ReuseChunk* rc = static_cast<ReuseChunk*>(p);
00385 rc->next = slack;
00386 rc->size = s;
00387 slack = rc;
00388 } else {
00389 size_t i = sz2i(s);
00390 FreeList* f = static_cast<FreeList*>(p);
00391 f->next(fl[i]); fl[i]=f;
00392 }
00393 }
00394
00395
00396
00397
00398
00399
00400
00401 template <size_t s>
00402 forceinline void*
00403 MemoryManager::fl_alloc(void) {
00404 size_t i = sz2i(s);
00405 FreeList* f = fl[i];
00406 if (f == NULL) {
00407 fl_refill<s>(); f = fl[i];
00408 }
00409 FreeList* n = f->next();
00410 fl[i] = n;
00411 return f;
00412 }
00413
00414 template <size_t s>
00415 forceinline void
00416 MemoryManager::fl_dispose(FreeList* f, FreeList* l) {
00417 size_t i = sz2i(s);
00418 l->next(fl[i]); fl[i] = f;
00419 }
00420
00421 template <size_t sz>
00422 void
00423 MemoryManager::fl_refill(void) {
00424
00425 if (slack != NULL) {
00426 ReuseChunk* m = slack;
00427 slack = NULL;
00428 do {
00429 char* block = Support::ptr_cast<char*>(m);
00430 size_t s = m->size;
00431 assert(s >= sz);
00432 m = m->next;
00433 fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block);
00434 while (s >= 2*sz) {
00435 Support::ptr_cast<FreeList*>(block)->next
00436 (Support::ptr_cast<FreeList*>(block+sz));
00437 block += sz;
00438 s -= sz;
00439 }
00440 Support::ptr_cast<FreeList*>(block)->next(NULL);
00441 } while (m != NULL);
00442 } else {
00443 char* block = static_cast<char*>(alloc(Memory::Config::fl_refill*sz));
00444 fl[sz2i(sz)] = Support::ptr_cast<FreeList*>(block);
00445 int i = Memory::Config::fl_refill-2;
00446 do {
00447 Support::ptr_cast<FreeList*>(block+i*sz)->next
00448 (Support::ptr_cast<FreeList*>(block+(i+1)*sz));
00449 } while (--i >= 0);
00450 Support::ptr_cast<FreeList*>(block+
00451 (Memory::Config::fl_refill-1)*sz)->next
00452 (Support::ptr_cast<FreeList*>(NULL));
00453 }
00454 }
00455
00456 }
00457
00458