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