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 #include <cstring>
00035 #include <cstdlib>
00036 #include <algorithm>
00037
00038 #ifdef GECODE_PEAKHEAP_MALLOC_H
00039 #include <malloc.h>
00040 #endif
00041
00042 #ifdef GECODE_PEAKHEAP_MALLOC_MALLOC_H
00043 #include <malloc/malloc.h>
00044 #endif
00045
00046 namespace Gecode {
00047
00062 class Heap {
00063 public:
00065 Heap(void);
00067
00068
00074 template<class T>
00075 T* alloc(long unsigned int n);
00082 template<class T>
00083 T* alloc(long int n);
00090 template<class T>
00091 T* alloc(unsigned int n);
00098 template<class T>
00099 T* alloc(int n);
00106 template<class T>
00107 void free(T* b, long unsigned int n);
00114 template<class T>
00115 void free(T* b, long int n);
00122 template<class T>
00123 void free(T* b, unsigned int n);
00130 template<class T>
00131 void free(T* b, int n);
00143 template<class T>
00144 T* realloc(T* b, long unsigned int n, long unsigned int m);
00156 template<class T>
00157 T* realloc(T* b, long int n, long int m);
00169 template<class T>
00170 T* realloc(T* b, unsigned int n, unsigned int m);
00182 template<class T>
00183 T* realloc(T* b, int n, int m);
00191 template<class T>
00192 T** realloc(T** b, long unsigned int n, long unsigned int m);
00200 template<class T>
00201 T** realloc(T** b, long int n, long int m);
00209 template<class T>
00210 T** realloc(T** b, unsigned int n, unsigned int m);
00218 template<class T>
00219 T** realloc(T** b, int n, int m);
00228 template<class T>
00229 static T* copy(T* d, const T* s, long unsigned int n);
00238 template<class T>
00239 static T* copy(T* d, const T* s, long int n);
00248 template<class T>
00249 static T* copy(T* d, const T* s, unsigned int n);
00258 template<class T>
00259 static T* copy(T* d, const T* s, int n);
00267 template<class T>
00268 static T** copy(T** d, const T** s, long unsigned int n);
00276 template<class T>
00277 static T** copy(T** d, const T** s, long int n);
00285 template<class T>
00286 static T** copy(T** d, const T** s, unsigned int n);
00294 template<class T>
00295 static T** copy(T** d, const T** s, int n);
00297
00298
00299
00300 void* ralloc(size_t s);
00302 void rfree(void* p);
00304 void rfree(void* p, size_t s);
00306 void* rrealloc(void* p, size_t s);
00308 private:
00310 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00312 static void operator delete(void* p) { (void) p; };
00314 Heap(const Heap&) {}
00316 const Heap& operator =(const Heap&) { return *this; }
00317 #ifdef GECODE_PEAKHEAP
00318
00319 Support::FastMutex _m;
00321 size_t _peak;
00323 size_t _cur;
00324 public:
00325 size_t peak(void);
00326 #endif
00327 };
00328
00333 extern GECODE_SUPPORT_EXPORT
00334 Heap heap;
00335
00340 class GECODE_SUPPORT_EXPORT HeapAllocated {
00341 public:
00343
00344
00345 static void* operator new(size_t s);
00347 static void operator delete(void* p);
00349 };
00350
00351
00352
00353
00354
00355
00356 forceinline void*
00357 Heap::ralloc(size_t s) {
00358 void* p = Support::allocator.alloc(s);
00359 #ifdef GECODE_PEAKHEAP
00360 _m.acquire();
00361 _cur += GECODE_MSIZE(p);
00362 _peak = std::max(_peak,_cur);
00363 _m.release();
00364 #endif
00365 if (p != NULL)
00366 return p;
00367 throw MemoryExhausted();
00368 }
00369
00370 forceinline void
00371 Heap::rfree(void* p) {
00372 #ifdef GECODE_PEAKHEAP
00373 _m.acquire();
00374 _cur -= GECODE_MSIZE(p);
00375 _m.release();
00376 #endif
00377 Support::allocator.free(p);
00378 }
00379
00380 forceinline void
00381 Heap::rfree(void* p, size_t) {
00382 #ifdef GECODE_PEAKHEAP
00383 _m.acquire();
00384 _cur -= GECODE_MSIZE(p);
00385 _m.release();
00386 #endif
00387 Support::allocator.free(p);
00388 }
00389
00390 forceinline void*
00391 Heap::rrealloc(void* p, size_t s) {
00392 #ifdef GECODE_PEAKHEAP
00393 _m.acquire();
00394 _cur -= GECODE_MSIZE(p);
00395 _m.release();
00396 #endif
00397 p = Support::allocator.realloc(p,s);
00398 #ifdef GECODE_PEAKHEAP
00399 _m.acquire();
00400 _cur += GECODE_MSIZE(p);
00401 _peak = std::max(_peak,_cur);
00402 _m.release();
00403 #endif
00404 if (p != NULL || s == 0)
00405 return p;
00406 throw MemoryExhausted();
00407 }
00408
00409
00410
00411
00412
00413
00414 forceinline void*
00415 HeapAllocated::operator new(size_t s) {
00416 return heap.ralloc(s);
00417 }
00418 forceinline void
00419 HeapAllocated::operator delete(void* p) {
00420 heap.rfree(p);
00421 }
00422
00423
00424
00425
00426
00427
00428
00429 template<class T>
00430 forceinline T*
00431 Heap::alloc(long unsigned int n) {
00432 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
00433 for (long unsigned int i=0U; i<n; i++)
00434 (void) new (p+i) T();
00435 return p;
00436 }
00437 template<class T>
00438 forceinline T*
00439 Heap::alloc(long int n) {
00440 assert(n >= 0);
00441 return alloc<T>(static_cast<long unsigned int>(n));
00442 }
00443 template<class T>
00444 forceinline T*
00445 Heap::alloc(unsigned int n) {
00446 return alloc<T>(static_cast<long unsigned int>(n));
00447 }
00448 template<class T>
00449 forceinline T*
00450 Heap::alloc(int n) {
00451 assert(n >= 0);
00452 return alloc<T>(static_cast<long unsigned int>(n));
00453 }
00454
00455 template<class T>
00456 forceinline void
00457 Heap::free(T* b, long unsigned int n) {
00458 for (long unsigned int i=0U; i<n; i++)
00459 b[i].~T();
00460 rfree(b);
00461 }
00462 template<class T>
00463 forceinline void
00464 Heap::free(T* b, long int n) {
00465 assert(n >= 0);
00466 free<T>(b, static_cast<long unsigned int>(n));
00467 }
00468 template<class T>
00469 forceinline void
00470 Heap::free(T* b, unsigned int n) {
00471 free<T>(b, static_cast<long unsigned int>(n));
00472 }
00473 template<class T>
00474 forceinline void
00475 Heap::free(T* b, int n) {
00476 assert(n >= 0);
00477 free<T>(b, static_cast<long unsigned int>(n));
00478 }
00479
00480 template<class T>
00481 forceinline T*
00482 Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
00483 if (n == m)
00484 return b;
00485 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
00486 for (long unsigned int i=0U; i<std::min(n,m); i++)
00487 (void) new (p+i) T(b[i]);
00488 for (long unsigned int i=n; i<m; i++)
00489 (void) new (p+i) T();
00490 free<T>(b,n);
00491 return p;
00492 }
00493 template<class T>
00494 forceinline T*
00495 Heap::realloc(T* b, long int n, long int m) {
00496 assert((n >= 0) && (m >= 0));
00497 return realloc<T>(b,static_cast<long unsigned int>(n),
00498 static_cast<long unsigned int>(m));
00499 }
00500 template<class T>
00501 forceinline T*
00502 Heap::realloc(T* b, unsigned int n, unsigned int m) {
00503 return realloc<T>(b,static_cast<long unsigned int>(n),
00504 static_cast<long unsigned int>(m));
00505 }
00506 template<class T>
00507 forceinline T*
00508 Heap::realloc(T* b, int n, int m) {
00509 assert((n >= 0) && (m >= 0));
00510 return realloc<T>(b,static_cast<long unsigned int>(n),
00511 static_cast<long unsigned int>(m));
00512 }
00513
00514 #define GECODE_SUPPORT_REALLOC(T) \
00515 template<> \
00516 forceinline T* \
00517 Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
00518 return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
00519 } \
00520 template<> \
00521 forceinline T* \
00522 Heap::realloc<T>(T* b, long int n, long int m) { \
00523 assert((n >= 0) && (m >= 0)); \
00524 return realloc<T>(b,static_cast<long unsigned int>(n), \
00525 static_cast<long unsigned int>(m)); \
00526 } \
00527 template<> \
00528 forceinline T* \
00529 Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
00530 return realloc<T>(b,static_cast<long unsigned int>(n), \
00531 static_cast<long unsigned int>(m)); \
00532 } \
00533 template<> \
00534 forceinline T* \
00535 Heap::realloc<T>(T* b, int n, int m) { \
00536 assert((n >= 0) && (m >= 0)); \
00537 return realloc<T>(b,static_cast<long unsigned int>(n), \
00538 static_cast<long unsigned int>(m)); \
00539 }
00540
00541 GECODE_SUPPORT_REALLOC(bool)
00542 GECODE_SUPPORT_REALLOC(signed char)
00543 GECODE_SUPPORT_REALLOC(unsigned char)
00544 GECODE_SUPPORT_REALLOC(signed short int)
00545 GECODE_SUPPORT_REALLOC(unsigned short int)
00546 GECODE_SUPPORT_REALLOC(signed int)
00547 GECODE_SUPPORT_REALLOC(unsigned int)
00548 GECODE_SUPPORT_REALLOC(signed long int)
00549 GECODE_SUPPORT_REALLOC(unsigned long int)
00550 GECODE_SUPPORT_REALLOC(float)
00551 GECODE_SUPPORT_REALLOC(double)
00552
00553 #undef GECODE_SUPPORT_REALLOC
00554
00555 template<class T>
00556 forceinline T**
00557 Heap::realloc(T** b, long unsigned int, long unsigned int m) {
00558 return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
00559 }
00560 template<class T>
00561 forceinline T**
00562 Heap::realloc(T** b, long int n, long int m) {
00563 assert((n >= 0) && (m >= 0));
00564 return realloc<T*>(b,static_cast<long unsigned int>(n),
00565 static_cast<long unsigned int>(m));
00566 }
00567 template<class T>
00568 forceinline T**
00569 Heap::realloc(T** b, unsigned int n, unsigned int m) {
00570 return realloc<T*>(b,static_cast<long unsigned int>(n),
00571 static_cast<long unsigned int>(m));
00572 }
00573 template<class T>
00574 forceinline T**
00575 Heap::realloc(T** b, int n, int m) {
00576 assert((n >= 0) && (m >= 0));
00577 return realloc<T*>(b,static_cast<long unsigned int>(n),
00578 static_cast<long unsigned int>(m));
00579 }
00580
00581 template<class T>
00582 forceinline T*
00583 Heap::copy(T* d, const T* s, long unsigned int n) {
00584 for (long unsigned int i=0U; i<n; i++)
00585 d[i]=s[i];
00586 return d;
00587 }
00588 template<class T>
00589 forceinline T*
00590 Heap::copy(T* d, const T* s, long int n) {
00591 assert(n >= 0);
00592 return copy<T>(d,s,static_cast<long unsigned int>(n));
00593 }
00594 template<class T>
00595 forceinline T*
00596 Heap::copy(T* d, const T* s, unsigned int n) {
00597 return copy<T>(d,s,static_cast<long unsigned int>(n));
00598 }
00599 template<class T>
00600 forceinline T*
00601 Heap::copy(T* d, const T* s, int n) {
00602 assert(n >= 0);
00603 return copy<T>(d,s,static_cast<long unsigned int>(n));
00604 }
00605
00606 #define GECODE_SUPPORT_COPY(T) \
00607 template<> \
00608 forceinline T* \
00609 Heap::copy(T* d, const T* s, long unsigned int n) { \
00610 return static_cast<T*>(Support::allocator.memcpy(d,s,n*sizeof(T))); \
00611 } \
00612 template<> \
00613 forceinline T* \
00614 Heap::copy(T* d, const T* s, long int n) { \
00615 assert(n >= 0); \
00616 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00617 } \
00618 template<> \
00619 forceinline T* \
00620 Heap::copy(T* d, const T* s, unsigned int n) { \
00621 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00622 } \
00623 template<> \
00624 forceinline T* \
00625 Heap::copy(T* d, const T* s, int n) { \
00626 assert(n >= 0); \
00627 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00628 }
00629
00630 GECODE_SUPPORT_COPY(bool)
00631 GECODE_SUPPORT_COPY(signed char)
00632 GECODE_SUPPORT_COPY(unsigned char)
00633 GECODE_SUPPORT_COPY(signed short int)
00634 GECODE_SUPPORT_COPY(unsigned short int)
00635 GECODE_SUPPORT_COPY(signed int)
00636 GECODE_SUPPORT_COPY(unsigned int)
00637 GECODE_SUPPORT_COPY(signed long int)
00638 GECODE_SUPPORT_COPY(unsigned long int)
00639 GECODE_SUPPORT_COPY(float)
00640 GECODE_SUPPORT_COPY(double)
00641
00642 #undef GECODE_SUPPORT_COPY
00643
00644 template<class T>
00645 forceinline T**
00646 Heap::copy(T** d, const T** s, long unsigned int n) {
00647 return static_cast<T**>(Support::allocator.memcpy(d,s,n*sizeof(T*)));
00648 }
00649 template<class T>
00650 forceinline T**
00651 Heap::copy(T** d, const T** s, long int n) {
00652 assert(n >= 0);
00653 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00654 }
00655 template<class T>
00656 forceinline T**
00657 Heap::copy(T** d, const T** s, unsigned int n) {
00658 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00659 }
00660 template<class T>
00661 forceinline T**
00662 Heap::copy(T** d, const T** s, int n) {
00663 assert(n >= 0);
00664 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00665 }
00666
00667 #ifdef GECODE_PEAKHEAP
00668 forceinline size_t
00669 Heap::peak(void) {
00670 _m.acquire();
00671 size_t ret = _peak;
00672 _m.release();
00673 return ret;
00674 }
00675 #endif
00676
00677 }
00678
00679