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-07-26 12:53:58 +0200 (Mon, 26 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11279 $ 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 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 * Wrappers for raw allocation routines 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 * Typed allocation routines 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 // STATISTICS: support-any