heap.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2008 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-28 18:54:51 +0200 (Wed, 28 Apr 2010) $ by $Author: tack $ 00011 * $Revision: 10822 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 * Wrappers for raw allocation routines 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 * Typed allocation routines 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 return realloc<T*>(b,static_cast<long unsigned int>(n), 00488 static_cast<long unsigned int>(m)); 00489 } 00490 template<class T> 00491 forceinline T** 00492 Heap::realloc(T** b, int n, int m) { 00493 assert((n >= 0) && (m >= 0)); 00494 return realloc<T*>(b,static_cast<long unsigned int>(n), 00495 static_cast<long unsigned int>(m)); 00496 } 00497 00498 template<class T> 00499 forceinline T* 00500 Heap::copy(T* d, const T* s, long unsigned int n) { 00501 for (long unsigned int i=n; i--; ) 00502 d[i]=s[i]; 00503 return d; 00504 } 00505 template<class T> 00506 forceinline T* 00507 Heap::copy(T* d, const T* s, long int n) { 00508 assert(n >= 0); 00509 return copy<T>(d,s,static_cast<long unsigned int>(n)); 00510 } 00511 template<class T> 00512 forceinline T* 00513 Heap::copy(T* d, const T* s, unsigned int n) { 00514 return copy<T>(d,s,static_cast<long unsigned int>(n)); 00515 } 00516 template<class T> 00517 forceinline T* 00518 Heap::copy(T* d, const T* s, int n) { 00519 assert(n >= 0); 00520 return copy<T>(d,s,static_cast<long unsigned int>(n)); 00521 } 00522 00523 #define GECODE_SUPPORT_COPY(T) \ 00524 template<> \ 00525 forceinline T* \ 00526 Heap::copy(T* d, const T* s, long unsigned int n) { \ 00527 return static_cast<T*>(memcpy(d,s,n*sizeof(T))); \ 00528 } \ 00529 template<> \ 00530 forceinline T* \ 00531 Heap::copy(T* d, const T* s, long int n) { \ 00532 assert(n >= 0); \ 00533 return copy<T>(d,s,static_cast<long unsigned int>(n)); \ 00534 } \ 00535 template<> \ 00536 forceinline T* \ 00537 Heap::copy(T* d, const T* s, unsigned int n) { \ 00538 return copy<T>(d,s,static_cast<long unsigned int>(n)); \ 00539 } \ 00540 template<> \ 00541 forceinline T* \ 00542 Heap::copy(T* d, const T* s, int n) { \ 00543 assert(n >= 0); \ 00544 return copy<T>(d,s,static_cast<long unsigned int>(n)); \ 00545 } 00546 00547 GECODE_SUPPORT_COPY(bool) 00548 GECODE_SUPPORT_COPY(signed char) 00549 GECODE_SUPPORT_COPY(unsigned char) 00550 GECODE_SUPPORT_COPY(signed short int) 00551 GECODE_SUPPORT_COPY(unsigned short int) 00552 GECODE_SUPPORT_COPY(signed int) 00553 GECODE_SUPPORT_COPY(unsigned int) 00554 GECODE_SUPPORT_COPY(signed long int) 00555 GECODE_SUPPORT_COPY(unsigned long int) 00556 GECODE_SUPPORT_COPY(float) 00557 GECODE_SUPPORT_COPY(double) 00558 00559 #undef GECODE_SUPPORT_COPY 00560 00561 template<class T> 00562 forceinline T** 00563 Heap::copy(T** d, const T** s, long unsigned int n) { 00564 return static_cast<T**>(memcpy(d,s,n*sizeof(T*))); 00565 } 00566 template<class T> 00567 forceinline T** 00568 Heap::copy(T** d, const T** s, long int n) { 00569 assert(n >= 0); 00570 return copy<T*>(d,s,static_cast<long unsigned int>(n)); 00571 } 00572 template<class T> 00573 forceinline T** 00574 Heap::copy(T** d, const T** s, unsigned int n) { 00575 return copy<T*>(d,s,static_cast<long unsigned int>(n)); 00576 } 00577 template<class T> 00578 forceinline T** 00579 Heap::copy(T** d, const T** s, int n) { 00580 assert(n >= 0); 00581 return copy<T*>(d,s,static_cast<long unsigned int>(n)); 00582 } 00583 00584 } 00585 00586 // STATISTICS: support-any