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 #include <cstring>
00039 #include <cstdlib>
00040 #include <algorithm>
00041
00042 #ifdef GECODE_PEAKHEAP_MALLOC_H
00043 #include <malloc.h>
00044 #endif
00045
00046 #ifdef GECODE_PEAKHEAP_MALLOC_MALLOC_H
00047 #include <malloc/malloc.h>
00048 #endif
00049
00050 namespace Gecode {
00051
00066 class Heap {
00067 public:
00069 Heap(void);
00071
00072
00078 template<class T>
00079 T* alloc(long unsigned int n);
00086 template<class T>
00087 T* alloc(long int n);
00094 template<class T>
00095 T* alloc(unsigned int n);
00102 template<class T>
00103 T* alloc(int n);
00110 template<class T>
00111 void free(T* b, long unsigned int n);
00118 template<class T>
00119 void free(T* b, long int n);
00126 template<class T>
00127 void free(T* b, unsigned int n);
00134 template<class T>
00135 void free(T* b, int n);
00147 template<class T>
00148 T* realloc(T* b, long unsigned int n, long unsigned int m);
00160 template<class T>
00161 T* realloc(T* b, long int n, long int m);
00173 template<class T>
00174 T* realloc(T* b, unsigned int n, unsigned int m);
00186 template<class T>
00187 T* realloc(T* b, int n, int m);
00195 template<class T>
00196 T** realloc(T** b, long unsigned int n, long unsigned int m);
00204 template<class T>
00205 T** realloc(T** b, long int n, long int m);
00213 template<class T>
00214 T** realloc(T** b, unsigned int n, unsigned int m);
00222 template<class T>
00223 T** realloc(T** b, int n, int m);
00232 template<class T>
00233 static T* copy(T* d, const T* s, long unsigned int n);
00242 template<class T>
00243 static T* copy(T* d, const T* s, long int n);
00252 template<class T>
00253 static T* copy(T* d, const T* s, unsigned int n);
00262 template<class T>
00263 static T* copy(T* d, const T* s, int n);
00271 template<class T>
00272 static T** copy(T** d, const T** s, long unsigned int n);
00280 template<class T>
00281 static T** copy(T** d, const T** s, long int n);
00289 template<class T>
00290 static T** copy(T** d, const T** s, unsigned int n);
00298 template<class T>
00299 static T** copy(T** d, const T** s, int n);
00301
00302
00303
00304 void* ralloc(size_t s);
00306 void rfree(void* p);
00308 void rfree(void* p, size_t s);
00310 void* rrealloc(void* p, size_t s);
00312 private:
00314 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00316 static void operator delete(void* p) { (void) p; };
00318 Heap(const Heap&) {}
00320 const Heap& operator =(const Heap&) { return *this; }
00321 #ifdef GECODE_PEAKHEAP
00322
00323 Support::FastMutex _m;
00325 size_t _peak;
00327 size_t _cur;
00328 public:
00329 size_t peak(void);
00330 #endif
00331 };
00332
00334 extern GECODE_SUPPORT_EXPORT Heap heap;
00335
00336
00337
00338
00339
00340 forceinline void*
00341 Heap::ralloc(size_t s) {
00342 void* p = ::malloc(s);
00343 #ifdef GECODE_PEAKHEAP
00344 _m.acquire();
00345 _cur += GECODE_MSIZE(p);
00346 _peak = std::max(_peak,_cur);
00347 _m.release();
00348 #endif
00349 if (p != NULL)
00350 return p;
00351 throw MemoryExhausted();
00352 }
00353
00354 forceinline void
00355 Heap::rfree(void* p) {
00356 #ifdef GECODE_PEAKHEAP
00357 _m.acquire();
00358 _cur -= GECODE_MSIZE(p);
00359 _m.release();
00360 #endif
00361 ::free(p);
00362 }
00363
00364 forceinline void
00365 Heap::rfree(void* p, size_t) {
00366 #ifdef GECODE_PEAKHEAP
00367 _m.acquire();
00368 _cur -= GECODE_MSIZE(p);
00369 _m.release();
00370 #endif
00371 ::free(p);
00372 }
00373
00374 forceinline void*
00375 Heap::rrealloc(void* p, size_t s) {
00376 #ifdef GECODE_PEAKHEAP
00377 _m.acquire();
00378 _cur -= GECODE_MSIZE(p);
00379 _m.release();
00380 #endif
00381 p = ::realloc(p,s);
00382 #ifdef GECODE_PEAKHEAP
00383 _m.acquire();
00384 _cur += GECODE_MSIZE(p);
00385 _peak = std::max(_peak,_cur);
00386 _m.release();
00387 #endif
00388 if (p != NULL || s == 0)
00389 return p;
00390 throw MemoryExhausted();
00391 }
00392
00393
00394
00395
00396
00397
00398 template<class T>
00399 forceinline T*
00400 Heap::alloc(long unsigned int n) {
00401 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
00402 for (long unsigned int i=n; i--; )
00403 (void) new (p+i) T();
00404 return p;
00405 }
00406 template<class T>
00407 forceinline T*
00408 Heap::alloc(long int n) {
00409 assert(n >= 0);
00410 return alloc<T>(static_cast<long unsigned int>(n));
00411 }
00412 template<class T>
00413 forceinline T*
00414 Heap::alloc(unsigned int n) {
00415 return alloc<T>(static_cast<long unsigned int>(n));
00416 }
00417 template<class T>
00418 forceinline T*
00419 Heap::alloc(int n) {
00420 assert(n >= 0);
00421 return alloc<T>(static_cast<long unsigned int>(n));
00422 }
00423
00424 template<class T>
00425 forceinline void
00426 Heap::free(T* b, long unsigned int n) {
00427 for (long unsigned int i=n; i--; )
00428 b[i].~T();
00429 rfree(b);
00430 }
00431 template<class T>
00432 forceinline void
00433 Heap::free(T* b, long int n) {
00434 assert(n >= 0);
00435 free<T>(b, static_cast<long unsigned int>(n));
00436 }
00437 template<class T>
00438 forceinline void
00439 Heap::free(T* b, unsigned int n) {
00440 free<T>(b, static_cast<long unsigned int>(n));
00441 }
00442 template<class T>
00443 forceinline void
00444 Heap::free(T* b, int n) {
00445 assert(n >= 0);
00446 free<T>(b, static_cast<long unsigned int>(n));
00447 }
00448
00449 template<class T>
00450 forceinline T*
00451 Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
00452 if (n == m)
00453 return b;
00454 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
00455 for (long unsigned int i=std::min(n,m); i--; )
00456 (void) new (p+i) T(b[i]);
00457 for (long unsigned int i=n; i<m; i++)
00458 (void) new (p+i) T();
00459 free<T>(b,n);
00460 return p;
00461 }
00462 template<class T>
00463 forceinline T*
00464 Heap::realloc(T* b, long int n, long int m) {
00465 assert((n >= 0) && (m >= 0));
00466 return realloc<T>(b,static_cast<long unsigned int>(n),
00467 static_cast<long unsigned int>(m));
00468 }
00469 template<class T>
00470 forceinline T*
00471 Heap::realloc(T* b, unsigned int n, unsigned int m) {
00472 return realloc<T>(b,static_cast<long unsigned int>(n),
00473 static_cast<long unsigned int>(m));
00474 }
00475 template<class T>
00476 forceinline T*
00477 Heap::realloc(T* b, int n, int m) {
00478 assert((n >= 0) && (m >= 0));
00479 return realloc<T>(b,static_cast<long unsigned int>(n),
00480 static_cast<long unsigned int>(m));
00481 }
00482
00483 #define GECODE_SUPPORT_REALLOC(T) \
00484 template<> \
00485 forceinline T* \
00486 Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
00487 return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
00488 } \
00489 template<> \
00490 forceinline T* \
00491 Heap::realloc<T>(T* b, long int n, long int m) { \
00492 assert((n >= 0) && (m >= 0)); \
00493 return realloc<T>(b,static_cast<long unsigned int>(n), \
00494 static_cast<long unsigned int>(m)); \
00495 } \
00496 template<> \
00497 forceinline T* \
00498 Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
00499 return realloc<T>(b,static_cast<long unsigned int>(n), \
00500 static_cast<long unsigned int>(m)); \
00501 } \
00502 template<> \
00503 forceinline T* \
00504 Heap::realloc<T>(T* b, int n, int m) { \
00505 assert((n >= 0) && (m >= 0)); \
00506 return realloc<T>(b,static_cast<long unsigned int>(n), \
00507 static_cast<long unsigned int>(m)); \
00508 }
00509
00510 GECODE_SUPPORT_REALLOC(bool)
00511 GECODE_SUPPORT_REALLOC(signed char)
00512 GECODE_SUPPORT_REALLOC(unsigned char)
00513 GECODE_SUPPORT_REALLOC(signed short int)
00514 GECODE_SUPPORT_REALLOC(unsigned short int)
00515 GECODE_SUPPORT_REALLOC(signed int)
00516 GECODE_SUPPORT_REALLOC(unsigned int)
00517 GECODE_SUPPORT_REALLOC(signed long int)
00518 GECODE_SUPPORT_REALLOC(unsigned long int)
00519 GECODE_SUPPORT_REALLOC(float)
00520 GECODE_SUPPORT_REALLOC(double)
00521
00522 #undef GECODE_SUPPORT_REALLOC
00523
00524 template<class T>
00525 forceinline T**
00526 Heap::realloc(T** b, long unsigned int, long unsigned int m) {
00527 return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
00528 }
00529 template<class T>
00530 forceinline T**
00531 Heap::realloc(T** b, long int n, long int m) {
00532 assert((n >= 0) && (m >= 0));
00533 return realloc<T*>(b,static_cast<long unsigned int>(n),
00534 static_cast<long unsigned int>(m));
00535 }
00536 template<class T>
00537 forceinline T**
00538 Heap::realloc(T** b, unsigned int n, unsigned int m) {
00539 return realloc<T*>(b,static_cast<long unsigned int>(n),
00540 static_cast<long unsigned int>(m));
00541 }
00542 template<class T>
00543 forceinline T**
00544 Heap::realloc(T** b, int n, int m) {
00545 assert((n >= 0) && (m >= 0));
00546 return realloc<T*>(b,static_cast<long unsigned int>(n),
00547 static_cast<long unsigned int>(m));
00548 }
00549
00550 template<class T>
00551 forceinline T*
00552 Heap::copy(T* d, const T* s, long unsigned int n) {
00553 for (long unsigned int i=n; i--; )
00554 d[i]=s[i];
00555 return d;
00556 }
00557 template<class T>
00558 forceinline T*
00559 Heap::copy(T* d, const T* s, long int n) {
00560 assert(n >= 0);
00561 return copy<T>(d,s,static_cast<long unsigned int>(n));
00562 }
00563 template<class T>
00564 forceinline T*
00565 Heap::copy(T* d, const T* s, unsigned int n) {
00566 return copy<T>(d,s,static_cast<long unsigned int>(n));
00567 }
00568 template<class T>
00569 forceinline T*
00570 Heap::copy(T* d, const T* s, int n) {
00571 assert(n >= 0);
00572 return copy<T>(d,s,static_cast<long unsigned int>(n));
00573 }
00574
00575 #define GECODE_SUPPORT_COPY(T) \
00576 template<> \
00577 forceinline T* \
00578 Heap::copy(T* d, const T* s, long unsigned int n) { \
00579 return static_cast<T*>(memcpy(d,s,n*sizeof(T))); \
00580 } \
00581 template<> \
00582 forceinline T* \
00583 Heap::copy(T* d, const T* s, long int n) { \
00584 assert(n >= 0); \
00585 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00586 } \
00587 template<> \
00588 forceinline T* \
00589 Heap::copy(T* d, const T* s, unsigned int n) { \
00590 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00591 } \
00592 template<> \
00593 forceinline T* \
00594 Heap::copy(T* d, const T* s, int n) { \
00595 assert(n >= 0); \
00596 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00597 }
00598
00599 GECODE_SUPPORT_COPY(bool)
00600 GECODE_SUPPORT_COPY(signed char)
00601 GECODE_SUPPORT_COPY(unsigned char)
00602 GECODE_SUPPORT_COPY(signed short int)
00603 GECODE_SUPPORT_COPY(unsigned short int)
00604 GECODE_SUPPORT_COPY(signed int)
00605 GECODE_SUPPORT_COPY(unsigned int)
00606 GECODE_SUPPORT_COPY(signed long int)
00607 GECODE_SUPPORT_COPY(unsigned long int)
00608 GECODE_SUPPORT_COPY(float)
00609 GECODE_SUPPORT_COPY(double)
00610
00611 #undef GECODE_SUPPORT_COPY
00612
00613 template<class T>
00614 forceinline T**
00615 Heap::copy(T** d, const T** s, long unsigned int n) {
00616 return static_cast<T**>(memcpy(d,s,n*sizeof(T*)));
00617 }
00618 template<class T>
00619 forceinline T**
00620 Heap::copy(T** d, const T** s, long int n) {
00621 assert(n >= 0);
00622 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00623 }
00624 template<class T>
00625 forceinline T**
00626 Heap::copy(T** d, const T** s, unsigned int n) {
00627 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00628 }
00629 template<class T>
00630 forceinline T**
00631 Heap::copy(T** d, const T** s, int n) {
00632 assert(n >= 0);
00633 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00634 }
00635
00636 #ifdef GECODE_PEAKHEAP
00637 forceinline size_t
00638 Heap::peak(void) {
00639 _m.acquire();
00640 size_t ret = _peak;
00641 _m.release();
00642 return ret;
00643 }
00644 #endif
00645
00646 }
00647
00648