Generated on Sun Feb 17 15:24:31 2019 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <cstring>
00035 #include <cstdlib>
00036 #include <algorithm>
00037 
00038 #ifdef GECODE_PEAKHEAP_MALLOC_H
00039 #include <malloc.h>
00040 #endif
00041 
00042 #ifdef GECODE_PEAKHEAP_MALLOC_MALLOC_H
00043 #include <malloc/malloc.h>
00044 #endif
00045 
00046 namespace Gecode {
00047 
00062   class Heap {
00063   public:
00065     Heap(void);
00067 
00068 
00074     template<class T>
00075     T* alloc(long unsigned int n);
00082     template<class T>
00083     T* alloc(long int n);
00090     template<class T>
00091     T* alloc(unsigned int n);
00098     template<class T>
00099     T* alloc(int n);
00106     template<class T>
00107     void free(T* b, long unsigned int n);
00114     template<class T>
00115     void free(T* b, long int n);
00122     template<class T>
00123     void free(T* b, unsigned int n);
00130     template<class T>
00131     void free(T* b, int n);
00143     template<class T>
00144     T* realloc(T* b, long unsigned int n, long unsigned int m);
00156     template<class T>
00157     T* realloc(T* b, long int n, long int m);
00169     template<class T>
00170     T* realloc(T* b, unsigned int n, unsigned int m);
00182     template<class T>
00183     T* realloc(T* b, int n, int m);
00191     template<class T>
00192     T** realloc(T** b, long unsigned int n, long unsigned int m);
00200     template<class T>
00201     T** realloc(T** b, long int n, long int m);
00209     template<class T>
00210     T** realloc(T** b, unsigned int n, unsigned int m);
00218     template<class T>
00219     T** realloc(T** b, int n, int m);
00228     template<class T>
00229     static T* copy(T* d, const T* s, long unsigned int n);
00238     template<class T>
00239     static T* copy(T* d, const T* s, long int n);
00248     template<class T>
00249     static T* copy(T* d, const T* s, unsigned int n);
00258     template<class T>
00259     static T* copy(T* d, const T* s, int n);
00267     template<class T>
00268     static T** copy(T** d, const T** s, long unsigned int n);
00276     template<class T>
00277     static T** copy(T** d, const T** s, long int n);
00285     template<class T>
00286     static T** copy(T** d, const T** s, unsigned int n);
00294     template<class T>
00295     static T** copy(T** d, const T** s, int n);
00297 
00298 
00299 
00300     void* ralloc(size_t s);
00302     void  rfree(void* p);
00304     void  rfree(void* p, size_t s);
00306     void* rrealloc(void* p, size_t s);
00308   private:
00310     static void* operator new(size_t s) throw() { (void) s; return NULL; }
00312     static void  operator delete(void* p) { (void) p; };
00314     Heap(const Heap&) {}
00316     const Heap& operator =(const Heap&) { return *this; }
00317 #ifdef GECODE_PEAKHEAP
00318 
00319     Support::FastMutex _m;
00321     size_t _peak;
00323     size_t _cur;
00324 public:
00325     size_t peak(void);
00326 #endif
00327   };
00328 
00333   extern GECODE_SUPPORT_EXPORT
00334   Heap heap;
00335 
00340   class GECODE_SUPPORT_EXPORT HeapAllocated {
00341   public:
00343 
00344 
00345     static void* operator new(size_t s);
00347     static void  operator delete(void* p);
00349   };
00350 
00351 
00352   /*
00353    * Wrappers for raw allocation routines
00354    *
00355    */
00356   forceinline void*
00357   Heap::ralloc(size_t s) {
00358     void* p = Support::allocator.alloc(s);
00359 #ifdef GECODE_PEAKHEAP
00360     _m.acquire();
00361     _cur += GECODE_MSIZE(p);
00362     _peak = std::max(_peak,_cur);
00363     _m.release();
00364 #endif
00365     if (p != NULL)
00366       return p;
00367     throw MemoryExhausted();
00368   }
00369 
00370   forceinline void
00371   Heap::rfree(void* p) {
00372 #ifdef GECODE_PEAKHEAP
00373     _m.acquire();
00374     _cur -= GECODE_MSIZE(p);
00375     _m.release();
00376 #endif
00377     Support::allocator.free(p);
00378   }
00379 
00380   forceinline void
00381   Heap::rfree(void* p, size_t) {
00382 #ifdef GECODE_PEAKHEAP
00383     _m.acquire();
00384     _cur -= GECODE_MSIZE(p);
00385     _m.release();
00386 #endif
00387     Support::allocator.free(p);
00388   }
00389 
00390   forceinline void*
00391   Heap::rrealloc(void* p, size_t s) {
00392 #ifdef GECODE_PEAKHEAP
00393     _m.acquire();
00394     _cur -= GECODE_MSIZE(p);
00395     _m.release();
00396 #endif
00397     p = Support::allocator.realloc(p,s);
00398 #ifdef GECODE_PEAKHEAP
00399     _m.acquire();
00400     _cur += GECODE_MSIZE(p);
00401     _peak = std::max(_peak,_cur);
00402     _m.release();
00403 #endif
00404     if (p != NULL || s == 0)
00405       return p;
00406     throw MemoryExhausted();
00407   }
00408 
00409 
00410   /*
00411    * Heap allocated objects
00412    *
00413    */
00414   forceinline void*
00415   HeapAllocated::operator new(size_t s) {
00416     return heap.ralloc(s);
00417   }
00418   forceinline void
00419   HeapAllocated::operator delete(void* p) {
00420     heap.rfree(p);
00421   }
00422 
00423 
00424 
00425   /*
00426    * Typed allocation routines
00427    *
00428    */
00429   template<class T>
00430   forceinline T*
00431   Heap::alloc(long unsigned int n) {
00432     T* p = static_cast<T*>(ralloc(sizeof(T)*n));
00433     for (long unsigned int i=0U; i<n; i++)
00434       (void) new (p+i) T();
00435     return p;
00436   }
00437   template<class T>
00438   forceinline T*
00439   Heap::alloc(long int n) {
00440     assert(n >= 0);
00441     return alloc<T>(static_cast<long unsigned int>(n));
00442   }
00443   template<class T>
00444   forceinline T*
00445   Heap::alloc(unsigned int n) {
00446     return alloc<T>(static_cast<long unsigned int>(n));
00447   }
00448   template<class T>
00449   forceinline T*
00450   Heap::alloc(int n) {
00451     assert(n >= 0);
00452     return alloc<T>(static_cast<long unsigned int>(n));
00453   }
00454 
00455   template<class T>
00456   forceinline void
00457   Heap::free(T* b, long unsigned int n) {
00458     for (long unsigned int i=0U; i<n; i++)
00459       b[i].~T();
00460     rfree(b);
00461   }
00462   template<class T>
00463   forceinline void
00464   Heap::free(T* b, long int n) {
00465     assert(n >= 0);
00466     free<T>(b, static_cast<long unsigned int>(n));
00467   }
00468   template<class T>
00469   forceinline void
00470   Heap::free(T* b, unsigned int n) {
00471     free<T>(b, static_cast<long unsigned int>(n));
00472   }
00473   template<class T>
00474   forceinline void
00475   Heap::free(T* b, int n) {
00476     assert(n >= 0);
00477     free<T>(b, static_cast<long unsigned int>(n));
00478   }
00479 
00480   template<class T>
00481   forceinline T*
00482   Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
00483     if (n == m)
00484       return b;
00485     T* p = static_cast<T*>(ralloc(sizeof(T)*m));
00486     for (long unsigned int i=0U; i<std::min(n,m); i++)
00487       (void) new (p+i) T(b[i]);
00488     for (long unsigned int i=n; i<m; i++)
00489       (void) new (p+i) T();
00490     free<T>(b,n);
00491     return p;
00492   }
00493   template<class T>
00494   forceinline T*
00495   Heap::realloc(T* b, long int n, long int m) {
00496     assert((n >= 0) && (m >= 0));
00497     return realloc<T>(b,static_cast<long unsigned int>(n),
00498                       static_cast<long unsigned int>(m));
00499   }
00500   template<class T>
00501   forceinline T*
00502   Heap::realloc(T* b, unsigned int n, unsigned int m) {
00503     return realloc<T>(b,static_cast<long unsigned int>(n),
00504                       static_cast<long unsigned int>(m));
00505   }
00506   template<class T>
00507   forceinline T*
00508   Heap::realloc(T* b, int n, int m) {
00509     assert((n >= 0) && (m >= 0));
00510     return realloc<T>(b,static_cast<long unsigned int>(n),
00511                       static_cast<long unsigned int>(m));
00512   }
00513 
00514 #define GECODE_SUPPORT_REALLOC(T)                                       \
00515   template<>                                                            \
00516   forceinline T*                                                        \
00517   Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) {      \
00518     return static_cast<T*>(rrealloc(b,m*sizeof(T)));                    \
00519   }                                                                     \
00520   template<>                                                            \
00521   forceinline T*                                                        \
00522   Heap::realloc<T>(T* b, long int n, long int m) {                      \
00523     assert((n >= 0) && (m >= 0));                                       \
00524     return realloc<T>(b,static_cast<long unsigned int>(n),              \
00525                       static_cast<long unsigned int>(m));               \
00526   }                                                                     \
00527   template<>                                                            \
00528   forceinline T*                                                        \
00529   Heap::realloc<T>(T* b, unsigned int n, unsigned int m) {              \
00530     return realloc<T>(b,static_cast<long unsigned int>(n),              \
00531                       static_cast<long unsigned int>(m));               \
00532   }                                                                     \
00533   template<>                                                            \
00534   forceinline T*                                                        \
00535   Heap::realloc<T>(T* b, int n, int m) {                                \
00536     assert((n >= 0) && (m >= 0));                                       \
00537     return realloc<T>(b,static_cast<long unsigned int>(n),              \
00538                       static_cast<long unsigned int>(m));               \
00539   }
00540 
00541   GECODE_SUPPORT_REALLOC(bool)
00542   GECODE_SUPPORT_REALLOC(signed char)
00543   GECODE_SUPPORT_REALLOC(unsigned char)
00544   GECODE_SUPPORT_REALLOC(signed short int)
00545   GECODE_SUPPORT_REALLOC(unsigned short int)
00546   GECODE_SUPPORT_REALLOC(signed int)
00547   GECODE_SUPPORT_REALLOC(unsigned int)
00548   GECODE_SUPPORT_REALLOC(signed long int)
00549   GECODE_SUPPORT_REALLOC(unsigned long int)
00550   GECODE_SUPPORT_REALLOC(float)
00551   GECODE_SUPPORT_REALLOC(double)
00552 
00553 #undef GECODE_SUPPORT_REALLOC
00554 
00555   template<class T>
00556   forceinline T**
00557   Heap::realloc(T** b, long unsigned int, long unsigned int m) {
00558     return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
00559   }
00560   template<class T>
00561   forceinline T**
00562   Heap::realloc(T** b, long int n, long int m) {
00563     assert((n >= 0) && (m >= 0));
00564     return realloc<T*>(b,static_cast<long unsigned int>(n),
00565                        static_cast<long unsigned int>(m));
00566   }
00567   template<class T>
00568   forceinline T**
00569   Heap::realloc(T** b, unsigned int n, unsigned int m) {
00570     return realloc<T*>(b,static_cast<long unsigned int>(n),
00571                        static_cast<long unsigned int>(m));
00572   }
00573   template<class T>
00574   forceinline T**
00575   Heap::realloc(T** b, int n, int m) {
00576     assert((n >= 0) && (m >= 0));
00577     return realloc<T*>(b,static_cast<long unsigned int>(n),
00578                        static_cast<long unsigned int>(m));
00579   }
00580 
00581   template<class T>
00582   forceinline T*
00583   Heap::copy(T* d, const T* s, long unsigned int n) {
00584     for (long unsigned int i=0U; i<n; i++)
00585       d[i]=s[i];
00586     return d;
00587   }
00588   template<class T>
00589   forceinline T*
00590   Heap::copy(T* d, const T* s, long int n) {
00591     assert(n >= 0);
00592     return copy<T>(d,s,static_cast<long unsigned int>(n));
00593   }
00594   template<class T>
00595   forceinline T*
00596   Heap::copy(T* d, const T* s, unsigned int n) {
00597     return copy<T>(d,s,static_cast<long unsigned int>(n));
00598   }
00599   template<class T>
00600   forceinline T*
00601   Heap::copy(T* d, const T* s, int n) {
00602     assert(n >= 0);
00603     return copy<T>(d,s,static_cast<long unsigned int>(n));
00604   }
00605 
00606 #define GECODE_SUPPORT_COPY(T)                                          \
00607   template<>                                                            \
00608   forceinline T*                                                        \
00609   Heap::copy(T* d, const T* s, long unsigned int n) {                   \
00610     return static_cast<T*>(Support::allocator.memcpy(d,s,n*sizeof(T))); \
00611   }                                                                     \
00612   template<>                                                            \
00613   forceinline T*                                                        \
00614   Heap::copy(T* d, const T* s, long int n) {                            \
00615     assert(n >= 0);                                                     \
00616     return copy<T>(d,s,static_cast<long unsigned int>(n));              \
00617   }                                                                     \
00618   template<>                                                            \
00619   forceinline T*                                                        \
00620   Heap::copy(T* d, const T* s, unsigned int n) {                        \
00621     return copy<T>(d,s,static_cast<long unsigned int>(n));              \
00622   }                                                                     \
00623   template<>                                                            \
00624   forceinline T*                                                        \
00625   Heap::copy(T* d, const T* s, int n) {                                 \
00626     assert(n >= 0);                                                     \
00627     return copy<T>(d,s,static_cast<long unsigned int>(n));              \
00628   }
00629 
00630   GECODE_SUPPORT_COPY(bool)
00631   GECODE_SUPPORT_COPY(signed char)
00632   GECODE_SUPPORT_COPY(unsigned char)
00633   GECODE_SUPPORT_COPY(signed short int)
00634   GECODE_SUPPORT_COPY(unsigned short int)
00635   GECODE_SUPPORT_COPY(signed int)
00636   GECODE_SUPPORT_COPY(unsigned int)
00637   GECODE_SUPPORT_COPY(signed long int)
00638   GECODE_SUPPORT_COPY(unsigned long int)
00639   GECODE_SUPPORT_COPY(float)
00640   GECODE_SUPPORT_COPY(double)
00641 
00642 #undef GECODE_SUPPORT_COPY
00643 
00644   template<class T>
00645   forceinline T**
00646   Heap::copy(T** d, const T** s, long unsigned int n) {
00647     return static_cast<T**>(Support::allocator.memcpy(d,s,n*sizeof(T*)));
00648   }
00649   template<class T>
00650   forceinline T**
00651   Heap::copy(T** d, const T** s, long int n) {
00652     assert(n >= 0);
00653     return copy<T*>(d,s,static_cast<long unsigned int>(n));
00654   }
00655   template<class T>
00656   forceinline T**
00657   Heap::copy(T** d, const T** s, unsigned int n) {
00658     return copy<T*>(d,s,static_cast<long unsigned int>(n));
00659   }
00660   template<class T>
00661   forceinline T**
00662   Heap::copy(T** d, const T** s, int n) {
00663     assert(n >= 0);
00664     return copy<T*>(d,s,static_cast<long unsigned int>(n));
00665   }
00666 
00667 #ifdef GECODE_PEAKHEAP
00668   forceinline size_t
00669   Heap::peak(void) {
00670     _m.acquire();
00671     size_t ret = _peak;
00672     _m.release();
00673     return ret;
00674   }
00675 #endif
00676 
00677 }
00678 
00679 // STATISTICS: support-any