Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
heap.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2008
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <cstring>
39 #include <cstdlib>
40 #include <algorithm>
41 
42 #ifdef GECODE_PEAKHEAP_MALLOC_H
43 #include <malloc.h>
44 #endif
45 
46 #ifdef GECODE_PEAKHEAP_MALLOC_MALLOC_H
47 #include <malloc/malloc.h>
48 #endif
49 
50 namespace Gecode {
51 
66  class Heap {
67  public:
69  Heap(void);
71 
72 
78  template<class T>
79  T* alloc(long unsigned int n);
86  template<class T>
87  T* alloc(long int n);
94  template<class T>
95  T* alloc(unsigned int n);
102  template<class T>
103  T* alloc(int n);
110  template<class T>
111  void free(T* b, long unsigned int n);
118  template<class T>
119  void free(T* b, long int n);
126  template<class T>
127  void free(T* b, unsigned int n);
134  template<class T>
135  void free(T* b, int n);
147  template<class T>
148  T* realloc(T* b, long unsigned int n, long unsigned int m);
160  template<class T>
161  T* realloc(T* b, long int n, long int m);
173  template<class T>
174  T* realloc(T* b, unsigned int n, unsigned int m);
186  template<class T>
187  T* realloc(T* b, int n, int m);
195  template<class T>
196  T** realloc(T** b, long unsigned int n, long unsigned int m);
204  template<class T>
205  T** realloc(T** b, long int n, long int m);
213  template<class T>
214  T** realloc(T** b, unsigned int n, unsigned int m);
222  template<class T>
223  T** realloc(T** b, int n, int m);
232  template<class T>
233  static T* copy(T* d, const T* s, long unsigned int n);
242  template<class T>
243  static T* copy(T* d, const T* s, long int n);
252  template<class T>
253  static T* copy(T* d, const T* s, unsigned int n);
262  template<class T>
263  static T* copy(T* d, const T* s, int n);
271  template<class T>
272  static T** copy(T** d, const T** s, long unsigned int n);
280  template<class T>
281  static T** copy(T** d, const T** s, long int n);
289  template<class T>
290  static T** copy(T** d, const T** s, unsigned int n);
298  template<class T>
299  static T** copy(T** d, const T** s, int n);
301 
303  void* ralloc(size_t s);
306  void rfree(void* p);
308  void rfree(void* p, size_t s);
310  void* rrealloc(void* p, size_t s);
312  private:
314  static void* operator new(size_t s) throw() { (void) s; return NULL; }
316  static void operator delete(void* p) { (void) p; };
318  Heap(const Heap&) {}
320  const Heap& operator =(const Heap&) { return *this; }
321 #ifdef GECODE_PEAKHEAP
325  size_t _peak;
327  size_t _cur;
328 public:
329  size_t peak(void);
330 #endif
331  };
332 
337  extern GECODE_SUPPORT_EXPORT
338  Heap heap;
339 
345  public:
347 
348  static void* operator new(size_t s);
351  static void operator delete(void* p);
353  };
354 
355 
356  /*
357  * Wrappers for raw allocation routines
358  *
359  */
360  forceinline void*
361  Heap::ralloc(size_t s) {
362  void* p = Support::allocator.alloc(s);
363 #ifdef GECODE_PEAKHEAP
364  _m.acquire();
365  _cur += GECODE_MSIZE(p);
366  _peak = std::max(_peak,_cur);
367  _m.release();
368 #endif
369  if (p != NULL)
370  return p;
371  throw MemoryExhausted();
372  }
373 
374  forceinline void
375  Heap::rfree(void* p) {
376 #ifdef GECODE_PEAKHEAP
377  _m.acquire();
378  _cur -= GECODE_MSIZE(p);
379  _m.release();
380 #endif
382  }
383 
384  forceinline void
385  Heap::rfree(void* p, size_t) {
386 #ifdef GECODE_PEAKHEAP
387  _m.acquire();
388  _cur -= GECODE_MSIZE(p);
389  _m.release();
390 #endif
392  }
393 
394  forceinline void*
395  Heap::rrealloc(void* p, size_t s) {
396 #ifdef GECODE_PEAKHEAP
397  _m.acquire();
398  _cur -= GECODE_MSIZE(p);
399  _m.release();
400 #endif
401  p = Support::allocator.realloc(p,s);
402 #ifdef GECODE_PEAKHEAP
403  _m.acquire();
404  _cur += GECODE_MSIZE(p);
405  _peak = std::max(_peak,_cur);
406  _m.release();
407 #endif
408  if (p != NULL || s == 0)
409  return p;
410  throw MemoryExhausted();
411  }
412 
413 
414  /*
415  * Heap allocated objects
416  *
417  */
418  forceinline void*
419  HeapAllocated::operator new(size_t s) {
420  return heap.ralloc(s);
421  }
422  forceinline void
423  HeapAllocated::operator delete(void* p) {
424  heap.rfree(p);
425  }
426 
427 
428 
429  /*
430  * Typed allocation routines
431  *
432  */
433  template<class T>
434  forceinline T*
435  Heap::alloc(long unsigned int n) {
436  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
437  for (long unsigned int i=n; i--; )
438  (void) new (p+i) T();
439  return p;
440  }
441  template<class T>
442  forceinline T*
443  Heap::alloc(long int n) {
444  assert(n >= 0);
445  return alloc<T>(static_cast<long unsigned int>(n));
446  }
447  template<class T>
448  forceinline T*
449  Heap::alloc(unsigned int n) {
450  return alloc<T>(static_cast<long unsigned int>(n));
451  }
452  template<class T>
453  forceinline T*
454  Heap::alloc(int n) {
455  assert(n >= 0);
456  return alloc<T>(static_cast<long unsigned int>(n));
457  }
458 
459  template<class T>
460  forceinline void
461  Heap::free(T* b, long unsigned int n) {
462  for (long unsigned int i=n; i--; )
463  b[i].~T();
464  rfree(b);
465  }
466  template<class T>
467  forceinline void
468  Heap::free(T* b, long int n) {
469  assert(n >= 0);
470  free<T>(b, static_cast<long unsigned int>(n));
471  }
472  template<class T>
473  forceinline void
474  Heap::free(T* b, unsigned int n) {
475  free<T>(b, static_cast<long unsigned int>(n));
476  }
477  template<class T>
478  forceinline void
479  Heap::free(T* b, int n) {
480  assert(n >= 0);
481  free<T>(b, static_cast<long unsigned int>(n));
482  }
483 
484  template<class T>
485  forceinline T*
486  Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
487  if (n == m)
488  return b;
489  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
490  for (long unsigned int i=std::min(n,m); i--; )
491  (void) new (p+i) T(b[i]);
492  for (long unsigned int i=n; i<m; i++)
493  (void) new (p+i) T();
494  free<T>(b,n);
495  return p;
496  }
497  template<class T>
498  forceinline T*
499  Heap::realloc(T* b, long int n, long int m) {
500  assert((n >= 0) && (m >= 0));
501  return realloc<T>(b,static_cast<long unsigned int>(n),
502  static_cast<long unsigned int>(m));
503  }
504  template<class T>
505  forceinline T*
506  Heap::realloc(T* b, unsigned int n, unsigned int m) {
507  return realloc<T>(b,static_cast<long unsigned int>(n),
508  static_cast<long unsigned int>(m));
509  }
510  template<class T>
511  forceinline T*
512  Heap::realloc(T* b, int n, int m) {
513  assert((n >= 0) && (m >= 0));
514  return realloc<T>(b,static_cast<long unsigned int>(n),
515  static_cast<long unsigned int>(m));
516  }
517 
518 #define GECODE_SUPPORT_REALLOC(T) \
519  template<> \
520  forceinline T* \
521  Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
522  return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
523  } \
524  template<> \
525  forceinline T* \
526  Heap::realloc<T>(T* b, long int n, long int m) { \
527  assert((n >= 0) && (m >= 0)); \
528  return realloc<T>(b,static_cast<long unsigned int>(n), \
529  static_cast<long unsigned int>(m)); \
530  } \
531  template<> \
532  forceinline T* \
533  Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
534  return realloc<T>(b,static_cast<long unsigned int>(n), \
535  static_cast<long unsigned int>(m)); \
536  } \
537  template<> \
538  forceinline T* \
539  Heap::realloc<T>(T* b, int n, int m) { \
540  assert((n >= 0) && (m >= 0)); \
541  return realloc<T>(b,static_cast<long unsigned int>(n), \
542  static_cast<long unsigned int>(m)); \
543  }
544 
546  GECODE_SUPPORT_REALLOC(signed char)
547  GECODE_SUPPORT_REALLOC(unsigned char)
548  GECODE_SUPPORT_REALLOC(signed short int)
549  GECODE_SUPPORT_REALLOC(unsigned short int)
550  GECODE_SUPPORT_REALLOC(signed int)
551  GECODE_SUPPORT_REALLOC(unsigned int)
552  GECODE_SUPPORT_REALLOC(signed long int)
553  GECODE_SUPPORT_REALLOC(unsigned long int)
555  GECODE_SUPPORT_REALLOC(double)
556 
557 #undef GECODE_SUPPORT_REALLOC
558 
559  template<class T>
560  forceinline T**
561  Heap::realloc(T** b, long unsigned int, long unsigned int m) {
562  return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
563  }
564  template<class T>
565  forceinline T**
566  Heap::realloc(T** b, long int n, long int m) {
567  assert((n >= 0) && (m >= 0));
568  return realloc<T*>(b,static_cast<long unsigned int>(n),
569  static_cast<long unsigned int>(m));
570  }
571  template<class T>
572  forceinline T**
573  Heap::realloc(T** b, unsigned int n, unsigned int m) {
574  return realloc<T*>(b,static_cast<long unsigned int>(n),
575  static_cast<long unsigned int>(m));
576  }
577  template<class T>
578  forceinline T**
579  Heap::realloc(T** b, int n, int m) {
580  assert((n >= 0) && (m >= 0));
581  return realloc<T*>(b,static_cast<long unsigned int>(n),
582  static_cast<long unsigned int>(m));
583  }
584 
585  template<class T>
586  forceinline T*
587  Heap::copy(T* d, const T* s, long unsigned int n) {
588  for (long unsigned int i=n; i--; )
589  d[i]=s[i];
590  return d;
591  }
592  template<class T>
593  forceinline T*
594  Heap::copy(T* d, const T* s, long int n) {
595  assert(n >= 0);
596  return copy<T>(d,s,static_cast<long unsigned int>(n));
597  }
598  template<class T>
599  forceinline T*
600  Heap::copy(T* d, const T* s, unsigned int n) {
601  return copy<T>(d,s,static_cast<long unsigned int>(n));
602  }
603  template<class T>
604  forceinline T*
605  Heap::copy(T* d, const T* s, int n) {
606  assert(n >= 0);
607  return copy<T>(d,s,static_cast<long unsigned int>(n));
608  }
609 
610 #define GECODE_SUPPORT_COPY(T) \
611  template<> \
612  forceinline T* \
613  Heap::copy(T* d, const T* s, long unsigned int n) { \
614  return static_cast<T*>(Support::allocator.memcpy(d,s,n*sizeof(T))); \
615  } \
616  template<> \
617  forceinline T* \
618  Heap::copy(T* d, const T* s, long int n) { \
619  assert(n >= 0); \
620  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
621  } \
622  template<> \
623  forceinline T* \
624  Heap::copy(T* d, const T* s, unsigned int n) { \
625  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
626  } \
627  template<> \
628  forceinline T* \
629  Heap::copy(T* d, const T* s, int n) { \
630  assert(n >= 0); \
631  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
632  }
633 
634  GECODE_SUPPORT_COPY(bool)
635  GECODE_SUPPORT_COPY(signed char)
636  GECODE_SUPPORT_COPY(unsigned char)
637  GECODE_SUPPORT_COPY(signed short int)
638  GECODE_SUPPORT_COPY(unsigned short int)
639  GECODE_SUPPORT_COPY(signed int)
640  GECODE_SUPPORT_COPY(unsigned int)
641  GECODE_SUPPORT_COPY(signed long int)
642  GECODE_SUPPORT_COPY(unsigned long int)
643  GECODE_SUPPORT_COPY(float)
644  GECODE_SUPPORT_COPY(double)
645 
646 #undef GECODE_SUPPORT_COPY
647 
648  template<class T>
649  forceinline T**
650  Heap::copy(T** d, const T** s, long unsigned int n) {
651  return static_cast<T**>(Support::allocator.memcpy(d,s,n*sizeof(T*)));
652  }
653  template<class T>
654  forceinline T**
655  Heap::copy(T** d, const T** s, long int n) {
656  assert(n >= 0);
657  return copy<T*>(d,s,static_cast<long unsigned int>(n));
658  }
659  template<class T>
660  forceinline T**
661  Heap::copy(T** d, const T** s, unsigned int n) {
662  return copy<T*>(d,s,static_cast<long unsigned int>(n));
663  }
664  template<class T>
665  forceinline T**
666  Heap::copy(T** d, const T** s, int n) {
667  assert(n >= 0);
668  return copy<T*>(d,s,static_cast<long unsigned int>(n));
669  }
670 
671 #ifdef GECODE_PEAKHEAP
672  forceinline size_t
673  Heap::peak(void) {
674  _m.acquire();
675  size_t ret = _peak;
676  _m.release();
677  return ret;
678  }
679 #endif
680 
681 }
682 
683 // STATISTICS: support-any
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:587
void * realloc(void *p, size_t n)
Return address of reallocated memory block p of size n.
Definition: allocator.hpp:87
#define GECODE_SUPPORT_REALLOC(T)
Definition: heap.hpp:518
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:361
Exception: Memory exhausted
Definition: exception.hpp:67
Heap(void)
Default constructor (ensuring that only a single instance is created)
Definition: heap.cpp:42
#define forceinline
Definition: config.hpp:182
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:105
Gecode::IntSet d(v, 7)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:435
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void * memcpy(void *d, const void *s, size_t n)
Copy n bytes from source s directly to d and returns d.
Definition: allocator.hpp:95
#define GECODE_SUPPORT_EXPORT
Definition: support.hh:75
Heap memory management class
Definition: heap.hpp:66
Allocator allocator
The single global default memory allocator.
Definition: allocator.cpp:42
#define GECODE_SUPPORT_COPY(T)
Definition: heap.hpp:610
void * rrealloc(void *p, size_t s)
Change memory block starting at p to size s.
Definition: heap.hpp:395
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
Heap heap
The single global heap.
Definition: heap.cpp:48
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:486
Gecode toplevel namespace
void * alloc(size_t n)
Allocate memory block of size n.
Definition: allocator.hpp:83
Base class for heap allocated objects.
Definition: heap.hpp:344
void free(void *p)
Free memory block p.
Definition: allocator.hpp:91