heap.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2008
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <cstring>
#include <cstdlib>
#include <algorithm>
#ifdef GECODE_PEAKHEAP_MALLOC_H
#include <malloc.h>
#endif
#ifdef GECODE_PEAKHEAP_MALLOC_MALLOC_H
#include <malloc/malloc.h>
#endif
namespace Gecode {
class Heap {
public:
Heap(void);
template<class T>
T* alloc(long unsigned int n);
template<class T>
T* alloc(long int n);
template<class T>
T* alloc(unsigned int n);
template<class T>
T* alloc(int n);
template<class T>
void free(T* b, long unsigned int n);
template<class T>
void free(T* b, long int n);
template<class T>
void free(T* b, unsigned int n);
template<class T>
void free(T* b, int n);
template<class T>
T* realloc(T* b, long unsigned int n, long unsigned int m);
template<class T>
T* realloc(T* b, long int n, long int m);
template<class T>
T* realloc(T* b, unsigned int n, unsigned int m);
template<class T>
T* realloc(T* b, int n, int m);
template<class T>
T** realloc(T** b, long unsigned int n, long unsigned int m);
template<class T>
T** realloc(T** b, long int n, long int m);
template<class T>
T** realloc(T** b, unsigned int n, unsigned int m);
template<class T>
T** realloc(T** b, int n, int m);
template<class T>
static T* copy(T* d, const T* s, long unsigned int n);
template<class T>
static T* copy(T* d, const T* s, long int n);
template<class T>
static T* copy(T* d, const T* s, unsigned int n);
template<class T>
static T* copy(T* d, const T* s, int n);
template<class T>
static T** copy(T** d, const T** s, long unsigned int n);
template<class T>
static T** copy(T** d, const T** s, long int n);
template<class T>
static T** copy(T** d, const T** s, unsigned int n);
template<class T>
static T** copy(T** d, const T** s, int n);
void* ralloc(size_t s);
void rfree(void* p);
void rfree(void* p, size_t s);
void* rrealloc(void* p, size_t s);
private:
static void* operator new(size_t s) throw() { (void) s; return NULL; }
static void operator delete(void* p) { (void) p; };
Heap(const Heap&) {}
const Heap& operator =(const Heap&) { return *this; }
#ifdef GECODE_PEAKHEAP
Support::FastMutex _m;
size_t _peak;
size_t _cur;
public:
size_t peak(void);
#endif
};
extern GECODE_SUPPORT_EXPORT
Heap heap;
class GECODE_SUPPORT_EXPORT HeapAllocated {
public:
static void* operator new(size_t s);
static void operator delete(void* p);
};
/*
* Wrappers for raw allocation routines
*
*/
forceinline void*
Heap::ralloc(size_t s) {
void* p = Support::allocator.alloc(s);
#ifdef GECODE_PEAKHEAP
_m.acquire();
_cur += GECODE_MSIZE(p);
_peak = std::max(_peak,_cur);
_m.release();
#endif
if (p != NULL)
return p;
throw MemoryExhausted();
}
forceinline void
Heap::rfree(void* p) {
#ifdef GECODE_PEAKHEAP
_m.acquire();
_cur -= GECODE_MSIZE(p);
_m.release();
#endif
Support::allocator.free(p);
}
forceinline void
Heap::rfree(void* p, size_t) {
#ifdef GECODE_PEAKHEAP
_m.acquire();
_cur -= GECODE_MSIZE(p);
_m.release();
#endif
Support::allocator.free(p);
}
forceinline void*
Heap::rrealloc(void* p, size_t s) {
#ifdef GECODE_PEAKHEAP
_m.acquire();
_cur -= GECODE_MSIZE(p);
_m.release();
#endif
p = Support::allocator.realloc(p,s);
#ifdef GECODE_PEAKHEAP
_m.acquire();
_cur += GECODE_MSIZE(p);
_peak = std::max(_peak,_cur);
_m.release();
#endif
if (p != NULL || s == 0)
return p;
throw MemoryExhausted();
}
/*
* Heap allocated objects
*
*/
forceinline void*
HeapAllocated::operator new(size_t s) {
return heap.ralloc(s);
}
forceinline void
HeapAllocated::operator delete(void* p) {
heap.rfree(p);
}
/*
* Typed allocation routines
*
*/
template<class T>
forceinline T*
Heap::alloc(long unsigned int n) {
T* p = static_cast<T*>(ralloc(sizeof(T)*n));
for (long unsigned int i=0U; i<n; i++)
(void) new (p+i) T();
return p;
}
template<class T>
forceinline T*
Heap::alloc(long int n) {
assert(n >= 0);
return alloc<T>(static_cast<long unsigned int>(n));
}
template<class T>
forceinline T*
Heap::alloc(unsigned int n) {
return alloc<T>(static_cast<long unsigned int>(n));
}
template<class T>
forceinline T*
Heap::alloc(int n) {
assert(n >= 0);
return alloc<T>(static_cast<long unsigned int>(n));
}
template<class T>
forceinline void
Heap::free(T* b, long unsigned int n) {
for (long unsigned int i=0U; i<n; i++)
b[i].~T();
rfree(b);
}
template<class T>
forceinline void
Heap::free(T* b, long int n) {
assert(n >= 0);
free<T>(b, static_cast<long unsigned int>(n));
}
template<class T>
forceinline void
Heap::free(T* b, unsigned int n) {
free<T>(b, static_cast<long unsigned int>(n));
}
template<class T>
forceinline void
Heap::free(T* b, int n) {
assert(n >= 0);
free<T>(b, static_cast<long unsigned int>(n));
}
template<class T>
forceinline T*
Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
if (n == m)
return b;
T* p = static_cast<T*>(ralloc(sizeof(T)*m));
for (long unsigned int i=0U; i<std::min(n,m); i++)
(void) new (p+i) T(b[i]);
for (long unsigned int i=n; i<m; i++)
(void) new (p+i) T();
free<T>(b,n);
return p;
}
template<class T>
forceinline T*
Heap::realloc(T* b, long int n, long int m) {
assert((n >= 0) && (m >= 0));
return realloc<T>(b,static_cast<long unsigned int>(n),
static_cast<long unsigned int>(m));
}
template<class T>
forceinline T*
Heap::realloc(T* b, unsigned int n, unsigned int m) {
return realloc<T>(b,static_cast<long unsigned int>(n),
static_cast<long unsigned int>(m));
}
template<class T>
forceinline T*
Heap::realloc(T* b, int n, int m) {
assert((n >= 0) && (m >= 0));
return realloc<T>(b,static_cast<long unsigned int>(n),
static_cast<long unsigned int>(m));
}
#define GECODE_SUPPORT_REALLOC(T) \
template<> \
forceinline T* \
Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
} \
template<> \
forceinline T* \
Heap::realloc<T>(T* b, long int n, long int m) { \
assert((n >= 0) && (m >= 0)); \
return realloc<T>(b,static_cast<long unsigned int>(n), \
static_cast<long unsigned int>(m)); \
} \
template<> \
forceinline T* \
Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
return realloc<T>(b,static_cast<long unsigned int>(n), \
static_cast<long unsigned int>(m)); \
} \
template<> \
forceinline T* \
Heap::realloc<T>(T* b, int n, int m) { \
assert((n >= 0) && (m >= 0)); \
return realloc<T>(b,static_cast<long unsigned int>(n), \
static_cast<long unsigned int>(m)); \
}
GECODE_SUPPORT_REALLOC(bool)
GECODE_SUPPORT_REALLOC(signed char)
GECODE_SUPPORT_REALLOC(unsigned char)
GECODE_SUPPORT_REALLOC(signed short int)
GECODE_SUPPORT_REALLOC(unsigned short int)
GECODE_SUPPORT_REALLOC(signed int)
GECODE_SUPPORT_REALLOC(unsigned int)
GECODE_SUPPORT_REALLOC(signed long int)
GECODE_SUPPORT_REALLOC(unsigned long int)
GECODE_SUPPORT_REALLOC(float)
GECODE_SUPPORT_REALLOC(double)
#undef GECODE_SUPPORT_REALLOC
template<class T>
forceinline T**
Heap::realloc(T** b, long unsigned int, long unsigned int m) {
return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
}
template<class T>
forceinline T**
Heap::realloc(T** b, long int n, long int m) {
assert((n >= 0) && (m >= 0));
return realloc<T*>(b,static_cast<long unsigned int>(n),
static_cast<long unsigned int>(m));
}
template<class T>
forceinline T**
Heap::realloc(T** b, unsigned int n, unsigned int m) {
return realloc<T*>(b,static_cast<long unsigned int>(n),
static_cast<long unsigned int>(m));
}
template<class T>
forceinline T**
Heap::realloc(T** b, int n, int m) {
assert((n >= 0) && (m >= 0));
return realloc<T*>(b,static_cast<long unsigned int>(n),
static_cast<long unsigned int>(m));
}
template<class T>
forceinline T*
Heap::copy(T* d, const T* s, long unsigned int n) {
for (long unsigned int i=0U; i<n; i++)
d[i]=s[i];
return d;
}
template<class T>
forceinline T*
Heap::copy(T* d, const T* s, long int n) {
assert(n >= 0);
return copy<T>(d,s,static_cast<long unsigned int>(n));
}
template<class T>
forceinline T*
Heap::copy(T* d, const T* s, unsigned int n) {
return copy<T>(d,s,static_cast<long unsigned int>(n));
}
template<class T>
forceinline T*
Heap::copy(T* d, const T* s, int n) {
assert(n >= 0);
return copy<T>(d,s,static_cast<long unsigned int>(n));
}
#define GECODE_SUPPORT_COPY(T) \
template<> \
forceinline T* \
Heap::copy(T* d, const T* s, long unsigned int n) { \
return static_cast<T*>(Support::allocator.memcpy(d,s,n*sizeof(T))); \
} \
template<> \
forceinline T* \
Heap::copy(T* d, const T* s, long int n) { \
assert(n >= 0); \
return copy<T>(d,s,static_cast<long unsigned int>(n)); \
} \
template<> \
forceinline T* \
Heap::copy(T* d, const T* s, unsigned int n) { \
return copy<T>(d,s,static_cast<long unsigned int>(n)); \
} \
template<> \
forceinline T* \
Heap::copy(T* d, const T* s, int n) { \
assert(n >= 0); \
return copy<T>(d,s,static_cast<long unsigned int>(n)); \
}
GECODE_SUPPORT_COPY(bool)
GECODE_SUPPORT_COPY(signed char)
GECODE_SUPPORT_COPY(unsigned char)
GECODE_SUPPORT_COPY(signed short int)
GECODE_SUPPORT_COPY(unsigned short int)
GECODE_SUPPORT_COPY(signed int)
GECODE_SUPPORT_COPY(unsigned int)
GECODE_SUPPORT_COPY(signed long int)
GECODE_SUPPORT_COPY(unsigned long int)
GECODE_SUPPORT_COPY(float)
GECODE_SUPPORT_COPY(double)
#undef GECODE_SUPPORT_COPY
template<class T>
forceinline T**
Heap::copy(T** d, const T** s, long unsigned int n) {
return static_cast<T**>(Support::allocator.memcpy(d,s,n*sizeof(T*)));
}
template<class T>
forceinline T**
Heap::copy(T** d, const T** s, long int n) {
assert(n >= 0);
return copy<T*>(d,s,static_cast<long unsigned int>(n));
}
template<class T>
forceinline T**
Heap::copy(T** d, const T** s, unsigned int n) {
return copy<T*>(d,s,static_cast<long unsigned int>(n));
}
template<class T>
forceinline T**
Heap::copy(T** d, const T** s, int n) {
assert(n >= 0);
return copy<T*>(d,s,static_cast<long unsigned int>(n));
}
#ifdef GECODE_PEAKHEAP
forceinline size_t
Heap::peak(void) {
_m.acquire();
size_t ret = _peak;
_m.release();
return ret;
}
#endif
}
// STATISTICS: support-any
Gecode::HeapAllocated
Base class for heap allocated objects.
Definition heap.hpp:340
Gecode::Heap
Heap memory management class
Definition heap.hpp:62
Gecode::Heap::Heap
Heap(void)
Default constructor (ensuring that only a single instance is created).
Definition heap.cpp:38
Gecode::Heap::rrealloc
void * rrealloc(void *p, size_t s)
Change memory block starting at p to size s.
Definition heap.hpp:391
Gecode::Heap::realloc
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from heap.
Definition heap.hpp:482
Gecode::Heap::copy
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:583
Gecode::Heap::free
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition heap.hpp:457
Gecode::Heap::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition heap.hpp:431
Gecode::Heap::rfree
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
Gecode::Heap::ralloc
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
Gecode::MemoryExhausted
Exception: Memory exhausted
Definition exception.hpp:63
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Support::allocator
Allocator allocator
The single global default memory allocator.
Definition allocator.cpp:38
GECODE_SUPPORT_REALLOC
#define GECODE_SUPPORT_REALLOC(T)
Definition heap.hpp:514
GECODE_SUPPORT_COPY
#define GECODE_SUPPORT_COPY(T)
Definition heap.hpp:606
Gecode::Support::FastMutex
Mutex FastMutex
Definition thread.hpp:140
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_SUPPORT_EXPORT
#define GECODE_SUPPORT_EXPORT
Definition support.hh:71