Generated on Mon Nov 30 23:53:37 2009 for Gecode by doxygen 1.6.1

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: 2009-03-03 10:25:58 +0100 (Tue, 03 Mar 2009) $ by $Author: schulte $
00011  *     $Revision: 8345 $
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     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 // STATISTICS: support-any