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 namespace Gecode {
00043
00058 class Heap {
00059 public:
00061 Heap(void);
00063
00064
00070 template<class T>
00071 T* alloc(long unsigned int n);
00078 template<class T>
00079 T* alloc(long int n);
00086 template<class T>
00087 T* alloc(unsigned int n);
00094 template<class T>
00095 T* alloc(int n);
00102 template<class T>
00103 void free(T* b, long unsigned int n);
00110 template<class T>
00111 void free(T* b, long int n);
00118 template<class T>
00119 void free(T* b, unsigned int n);
00126 template<class T>
00127 void free(T* b, int n);
00139 template<class T>
00140 T* realloc(T* b, long unsigned int n, long unsigned int m);
00152 template<class T>
00153 T* realloc(T* b, long int n, long int m);
00165 template<class T>
00166 T* realloc(T* b, unsigned int n, unsigned int m);
00178 template<class T>
00179 T* realloc(T* b, int n, int m);
00187 template<class T>
00188 T** realloc(T** b, long unsigned int n, long unsigned int m);
00196 template<class T>
00197 T** realloc(T** b, long int n, long int m);
00205 template<class T>
00206 T** realloc(T** b, unsigned int n, unsigned int m);
00214 template<class T>
00215 T** realloc(T** b, int n, int m);
00224 template<class T>
00225 static T* copy(T* d, const T* s, long unsigned int n);
00234 template<class T>
00235 static T* copy(T* d, const T* s, long int n);
00244 template<class T>
00245 static T* copy(T* d, const T* s, unsigned int n);
00254 template<class T>
00255 static T* copy(T* d, const T* s, int n);
00263 template<class T>
00264 static T** copy(T** d, const T** s, long unsigned int n);
00272 template<class T>
00273 static T** copy(T** d, const T** s, long int n);
00281 template<class T>
00282 static T** copy(T** d, const T** s, unsigned int n);
00290 template<class T>
00291 static T** copy(T** d, const T** s, int n);
00293
00294
00295
00296 void* ralloc(size_t s);
00298 void rfree(void* p);
00300 void* rrealloc(void* p, size_t s);
00302 private:
00304 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00306 static void operator delete(void* p) { (void) p; };
00308 Heap(const Heap&) {}
00310 const Heap& operator =(const Heap&) { return *this; }
00311 };
00312
00314 extern GECODE_SUPPORT_EXPORT Heap heap;
00315
00316
00317
00318
00319
00320 forceinline void*
00321 Heap::ralloc(size_t s) {
00322 void* p = ::malloc(s);
00323 if (p != NULL)
00324 return p;
00325 throw MemoryExhausted();
00326 }
00327
00328 forceinline void
00329 Heap::rfree(void* p) {
00330 ::free(p);
00331 }
00332
00333 forceinline void*
00334 Heap::rrealloc(void* p, size_t s) {
00335 p = ::realloc(p,s);
00336 if (p != NULL || s == 0)
00337 return p;
00338 throw MemoryExhausted();
00339 }
00340
00341
00342
00343
00344
00345
00346 template<class T>
00347 forceinline T*
00348 Heap::alloc(long unsigned int n) {
00349 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
00350 for (long unsigned int i=n; i--; )
00351 (void) new (p+i) T();
00352 return p;
00353 }
00354 template<class T>
00355 forceinline T*
00356 Heap::alloc(long int n) {
00357 assert(n >= 0);
00358 return alloc<T>(static_cast<long unsigned int>(n));
00359 }
00360 template<class T>
00361 forceinline T*
00362 Heap::alloc(unsigned int n) {
00363 return alloc<T>(static_cast<long unsigned int>(n));
00364 }
00365 template<class T>
00366 forceinline T*
00367 Heap::alloc(int n) {
00368 assert(n >= 0);
00369 return alloc<T>(static_cast<long unsigned int>(n));
00370 }
00371
00372 template<class T>
00373 forceinline void
00374 Heap::free(T* b, long unsigned int n) {
00375 for (long unsigned int i=n; i--; )
00376 b[i].~T();
00377 rfree(b);
00378 }
00379 template<class T>
00380 forceinline void
00381 Heap::free(T* b, long int n) {
00382 assert(n >= 0);
00383 free<T>(b, static_cast<long unsigned int>(n));
00384 }
00385 template<class T>
00386 forceinline void
00387 Heap::free(T* b, unsigned int n) {
00388 free<T>(b, static_cast<long unsigned int>(n));
00389 }
00390 template<class T>
00391 forceinline void
00392 Heap::free(T* b, int n) {
00393 assert(n >= 0);
00394 free<T>(b, static_cast<long unsigned int>(n));
00395 }
00396
00397 template<class T>
00398 forceinline T*
00399 Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
00400 if (n == m)
00401 return b;
00402 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
00403 for (long unsigned int i=std::min(n,m); i--; )
00404 (void) new (p+i) T(b[i]);
00405 for (long unsigned int i=n; i<m; i++)
00406 (void) new (p+i) T();
00407 free<T>(b,n);
00408 return p;
00409 }
00410 template<class T>
00411 forceinline T*
00412 Heap::realloc(T* b, long int n, long int m) {
00413 assert((n >= 0) && (m >= 0));
00414 return realloc<T>(b,static_cast<long unsigned int>(n),
00415 static_cast<long unsigned int>(m));
00416 }
00417 template<class T>
00418 forceinline T*
00419 Heap::realloc(T* b, unsigned int n, unsigned int m) {
00420 return realloc<T>(b,static_cast<long unsigned int>(n),
00421 static_cast<long unsigned int>(m));
00422 }
00423 template<class T>
00424 forceinline T*
00425 Heap::realloc(T* b, int n, int m) {
00426 assert((n >= 0) && (m >= 0));
00427 return realloc<T>(b,static_cast<long unsigned int>(n),
00428 static_cast<long unsigned int>(m));
00429 }
00430
00431 #define GECODE_SUPPORT_REALLOC(T) \
00432 template<> \
00433 forceinline T* \
00434 Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
00435 return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
00436 } \
00437 template<> \
00438 forceinline T* \
00439 Heap::realloc<T>(T* b, long int n, long int m) { \
00440 assert((n >= 0) && (m >= 0)); \
00441 return realloc<T>(b,static_cast<long unsigned int>(n), \
00442 static_cast<long unsigned int>(m)); \
00443 } \
00444 template<> \
00445 forceinline T* \
00446 Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
00447 return realloc<T>(b,static_cast<long unsigned int>(n), \
00448 static_cast<long unsigned int>(m)); \
00449 } \
00450 template<> \
00451 forceinline T* \
00452 Heap::realloc<T>(T* b, int n, int m) { \
00453 assert((n >= 0) && (m >= 0)); \
00454 return realloc<T>(b,static_cast<long unsigned int>(n), \
00455 static_cast<long unsigned int>(m)); \
00456 }
00457
00458 GECODE_SUPPORT_REALLOC(bool)
00459 GECODE_SUPPORT_REALLOC(signed char)
00460 GECODE_SUPPORT_REALLOC(unsigned char)
00461 GECODE_SUPPORT_REALLOC(signed short int)
00462 GECODE_SUPPORT_REALLOC(unsigned short int)
00463 GECODE_SUPPORT_REALLOC(signed int)
00464 GECODE_SUPPORT_REALLOC(unsigned int)
00465 GECODE_SUPPORT_REALLOC(signed long int)
00466 GECODE_SUPPORT_REALLOC(unsigned long int)
00467 GECODE_SUPPORT_REALLOC(float)
00468 GECODE_SUPPORT_REALLOC(double)
00469
00470 #undef GECODE_SUPPORT_REALLOC
00471
00472 template<class T>
00473 forceinline T**
00474 Heap::realloc(T** b, long unsigned int, long unsigned int m) {
00475 return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
00476 }
00477 template<class T>
00478 forceinline T**
00479 Heap::realloc(T** b, long int n, long int m) {
00480 assert((n >= 0) && (m >= 0));
00481 return realloc<T*>(b,static_cast<long unsigned int>(n),
00482 static_cast<long unsigned int>(m));
00483 }
00484 template<class T>
00485 forceinline T**
00486 Heap::realloc(T** b, unsigned int n, unsigned int m) {
00487 assert((n >= 0) && (m >= 0));
00488 return realloc<T*>(b,static_cast<long unsigned int>(n),
00489 static_cast<long unsigned int>(m));
00490 }
00491 template<class T>
00492 forceinline T**
00493 Heap::realloc(T** b, int n, int m) {
00494 assert((n >= 0) && (m >= 0));
00495 return realloc<T*>(b,static_cast<long unsigned int>(n),
00496 static_cast<long unsigned int>(m));
00497 }
00498
00499 template<class T>
00500 forceinline T*
00501 Heap::copy(T* d, const T* s, long unsigned int n) {
00502 for (long unsigned int i=n; i--; )
00503 d[i]=s[i];
00504 return d;
00505 }
00506 template<class T>
00507 forceinline T*
00508 Heap::copy(T* d, const T* s, long int n) {
00509 assert(n >= 0);
00510 return copy<T>(d,s,static_cast<long unsigned int>(n));
00511 }
00512 template<class T>
00513 forceinline T*
00514 Heap::copy(T* d, const T* s, unsigned int n) {
00515 return copy<T>(d,s,static_cast<long unsigned int>(n));
00516 }
00517 template<class T>
00518 forceinline T*
00519 Heap::copy(T* d, const T* s, int n) {
00520 assert(n >= 0);
00521 return copy<T>(d,s,static_cast<long unsigned int>(n));
00522 }
00523
00524 #define GECODE_SUPPORT_COPY(T) \
00525 template<> \
00526 forceinline T* \
00527 Heap::copy(T* d, const T* s, long unsigned int n) { \
00528 return static_cast<T*>(memcpy(d,s,n*sizeof(T))); \
00529 } \
00530 template<> \
00531 forceinline T* \
00532 Heap::copy(T* d, const T* s, long int n) { \
00533 assert(n >= 0); \
00534 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00535 } \
00536 template<> \
00537 forceinline T* \
00538 Heap::copy(T* d, const T* s, unsigned int n) { \
00539 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00540 } \
00541 template<> \
00542 forceinline T* \
00543 Heap::copy(T* d, const T* s, int n) { \
00544 assert(n >= 0); \
00545 return copy<T>(d,s,static_cast<long unsigned int>(n)); \
00546 }
00547
00548 GECODE_SUPPORT_COPY(bool)
00549 GECODE_SUPPORT_COPY(signed char)
00550 GECODE_SUPPORT_COPY(unsigned char)
00551 GECODE_SUPPORT_COPY(signed short int)
00552 GECODE_SUPPORT_COPY(unsigned short int)
00553 GECODE_SUPPORT_COPY(signed int)
00554 GECODE_SUPPORT_COPY(unsigned int)
00555 GECODE_SUPPORT_COPY(signed long int)
00556 GECODE_SUPPORT_COPY(unsigned long int)
00557 GECODE_SUPPORT_COPY(float)
00558 GECODE_SUPPORT_COPY(double)
00559
00560 #undef GECODE_SUPPORT_COPY
00561
00562 template<class T>
00563 forceinline T**
00564 Heap::copy(T** d, const T** s, long unsigned int n) {
00565 return static_cast<T**>(memcpy(d,s,n*sizeof(T*)));
00566 }
00567 template<class T>
00568 forceinline T**
00569 Heap::copy(T** d, const T** s, long int n) {
00570 assert(n >= 0);
00571 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00572 }
00573 template<class T>
00574 forceinline T**
00575 Heap::copy(T** d, const T** s, unsigned int n) {
00576 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00577 }
00578 template<class T>
00579 forceinline T**
00580 Heap::copy(T** d, const T** s, int n) {
00581 assert(n >= 0);
00582 return copy<T*>(d,s,static_cast<long unsigned int>(n));
00583 }
00584
00585 }
00586
00587