Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <cstring>
35 #include <cstdlib>
36 #include <algorithm>
37 
38 #ifdef GECODE_PEAKHEAP_MALLOC_H
39 #include <malloc.h>
40 #endif
41 
42 #ifdef GECODE_PEAKHEAP_MALLOC_MALLOC_H
43 #include <malloc/malloc.h>
44 #endif
45 
46 namespace Gecode {
47 
62  class Heap {
63  public:
65  Heap(void);
67 
68 
74  template<class T>
75  T* alloc(long unsigned int n);
82  template<class T>
83  T* alloc(long int n);
90  template<class T>
91  T* alloc(unsigned int n);
98  template<class T>
99  T* alloc(int n);
106  template<class T>
107  void free(T* b, long unsigned int n);
114  template<class T>
115  void free(T* b, long int n);
122  template<class T>
123  void free(T* b, unsigned int n);
130  template<class T>
131  void free(T* b, int n);
143  template<class T>
144  T* realloc(T* b, long unsigned int n, long unsigned int m);
156  template<class T>
157  T* realloc(T* b, long int n, long int m);
169  template<class T>
170  T* realloc(T* b, unsigned int n, unsigned int m);
182  template<class T>
183  T* realloc(T* b, int n, int m);
191  template<class T>
192  T** realloc(T** b, long unsigned int n, long unsigned int m);
200  template<class T>
201  T** realloc(T** b, long int n, long int m);
209  template<class T>
210  T** realloc(T** b, unsigned int n, unsigned int m);
218  template<class T>
219  T** realloc(T** b, int n, int m);
228  template<class T>
229  static T* copy(T* d, const T* s, long unsigned int n);
238  template<class T>
239  static T* copy(T* d, const T* s, long int n);
248  template<class T>
249  static T* copy(T* d, const T* s, unsigned int n);
258  template<class T>
259  static T* copy(T* d, const T* s, int n);
267  template<class T>
268  static T** copy(T** d, const T** s, long unsigned int n);
276  template<class T>
277  static T** copy(T** d, const T** s, long int n);
285  template<class T>
286  static T** copy(T** d, const T** s, unsigned int n);
294  template<class T>
295  static T** copy(T** d, const T** s, int n);
297 
299  void* ralloc(size_t s);
302  void rfree(void* p);
304  void rfree(void* p, size_t s);
306  void* rrealloc(void* p, size_t s);
308  private:
310  static void* operator new(size_t s) throw() { (void) s; return NULL; }
312  static void operator delete(void* p) { (void) p; };
314  Heap(const Heap&) {}
316  const Heap& operator =(const Heap&) { return *this; }
317 #ifdef GECODE_PEAKHEAP
321  size_t _peak;
323  size_t _cur;
324 public:
325  size_t peak(void);
326 #endif
327  };
328 
333  extern GECODE_SUPPORT_EXPORT
334  Heap heap;
335 
341  public:
343 
344  static void* operator new(size_t s);
347  static void operator delete(void* p);
349  };
350 
351 
352  /*
353  * Wrappers for raw allocation routines
354  *
355  */
356  forceinline void*
357  Heap::ralloc(size_t s) {
358  void* p = Support::allocator.alloc(s);
359 #ifdef GECODE_PEAKHEAP
360  _m.acquire();
361  _cur += GECODE_MSIZE(p);
362  _peak = std::max(_peak,_cur);
363  _m.release();
364 #endif
365  if (p != NULL)
366  return p;
367  throw MemoryExhausted();
368  }
369 
370  forceinline void
371  Heap::rfree(void* p) {
372 #ifdef GECODE_PEAKHEAP
373  _m.acquire();
374  _cur -= GECODE_MSIZE(p);
375  _m.release();
376 #endif
378  }
379 
380  forceinline void
381  Heap::rfree(void* p, size_t) {
382 #ifdef GECODE_PEAKHEAP
383  _m.acquire();
384  _cur -= GECODE_MSIZE(p);
385  _m.release();
386 #endif
388  }
389 
390  forceinline void*
391  Heap::rrealloc(void* p, size_t s) {
392 #ifdef GECODE_PEAKHEAP
393  _m.acquire();
394  _cur -= GECODE_MSIZE(p);
395  _m.release();
396 #endif
398 #ifdef GECODE_PEAKHEAP
399  _m.acquire();
400  _cur += GECODE_MSIZE(p);
401  _peak = std::max(_peak,_cur);
402  _m.release();
403 #endif
404  if (p != NULL || s == 0)
405  return p;
406  throw MemoryExhausted();
407  }
408 
409 
410  /*
411  * Heap allocated objects
412  *
413  */
414  forceinline void*
415  HeapAllocated::operator new(size_t s) {
416  return heap.ralloc(s);
417  }
418  forceinline void
419  HeapAllocated::operator delete(void* p) {
420  heap.rfree(p);
421  }
422 
423 
424 
425  /*
426  * Typed allocation routines
427  *
428  */
429  template<class T>
430  forceinline T*
431  Heap::alloc(long unsigned int n) {
432  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
433  for (long unsigned int i=0U; i<n; i++)
434  (void) new (p+i) T();
435  return p;
436  }
437  template<class T>
438  forceinline T*
439  Heap::alloc(long int n) {
440  assert(n >= 0);
441  return alloc<T>(static_cast<long unsigned int>(n));
442  }
443  template<class T>
444  forceinline T*
445  Heap::alloc(unsigned int n) {
446  return alloc<T>(static_cast<long unsigned int>(n));
447  }
448  template<class T>
449  forceinline T*
450  Heap::alloc(int n) {
451  assert(n >= 0);
452  return alloc<T>(static_cast<long unsigned int>(n));
453  }
454 
455  template<class T>
456  forceinline void
457  Heap::free(T* b, long unsigned int n) {
458  for (long unsigned int i=0U; i<n; i++)
459  b[i].~T();
460  rfree(b);
461  }
462  template<class T>
463  forceinline void
464  Heap::free(T* b, long int n) {
465  assert(n >= 0);
466  free<T>(b, static_cast<long unsigned int>(n));
467  }
468  template<class T>
469  forceinline void
470  Heap::free(T* b, unsigned int n) {
471  free<T>(b, static_cast<long unsigned int>(n));
472  }
473  template<class T>
474  forceinline void
475  Heap::free(T* b, int n) {
476  assert(n >= 0);
477  free<T>(b, static_cast<long unsigned int>(n));
478  }
479 
480  template<class T>
481  forceinline T*
482  Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
483  if (n == m)
484  return b;
485  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
486  for (long unsigned int i=0U; i<std::min(n,m); i++)
487  (void) new (p+i) T(b[i]);
488  for (long unsigned int i=n; i<m; i++)
489  (void) new (p+i) T();
490  free<T>(b,n);
491  return p;
492  }
493  template<class T>
494  forceinline T*
495  Heap::realloc(T* b, long int n, long int m) {
496  assert((n >= 0) && (m >= 0));
497  return realloc<T>(b,static_cast<long unsigned int>(n),
498  static_cast<long unsigned int>(m));
499  }
500  template<class T>
501  forceinline T*
502  Heap::realloc(T* b, unsigned int n, unsigned int m) {
503  return realloc<T>(b,static_cast<long unsigned int>(n),
504  static_cast<long unsigned int>(m));
505  }
506  template<class T>
507  forceinline T*
508  Heap::realloc(T* b, int n, int m) {
509  assert((n >= 0) && (m >= 0));
510  return realloc<T>(b,static_cast<long unsigned int>(n),
511  static_cast<long unsigned int>(m));
512  }
513 
514 #define GECODE_SUPPORT_REALLOC(T) \
515  template<> \
516  forceinline T* \
517  Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
518  return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
519  } \
520  template<> \
521  forceinline T* \
522  Heap::realloc<T>(T* b, long int n, long int m) { \
523  assert((n >= 0) && (m >= 0)); \
524  return realloc<T>(b,static_cast<long unsigned int>(n), \
525  static_cast<long unsigned int>(m)); \
526  } \
527  template<> \
528  forceinline T* \
529  Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
530  return realloc<T>(b,static_cast<long unsigned int>(n), \
531  static_cast<long unsigned int>(m)); \
532  } \
533  template<> \
534  forceinline T* \
535  Heap::realloc<T>(T* b, int n, int m) { \
536  assert((n >= 0) && (m >= 0)); \
537  return realloc<T>(b,static_cast<long unsigned int>(n), \
538  static_cast<long unsigned int>(m)); \
539  }
540 
542  GECODE_SUPPORT_REALLOC(signed char)
543  GECODE_SUPPORT_REALLOC(unsigned char)
544  GECODE_SUPPORT_REALLOC(signed short int)
545  GECODE_SUPPORT_REALLOC(unsigned short int)
546  GECODE_SUPPORT_REALLOC(signed int)
547  GECODE_SUPPORT_REALLOC(unsigned int)
548  GECODE_SUPPORT_REALLOC(signed long int)
549  GECODE_SUPPORT_REALLOC(unsigned long int)
551  GECODE_SUPPORT_REALLOC(double)
552 
553 #undef GECODE_SUPPORT_REALLOC
554 
555  template<class T>
556  forceinline T**
557  Heap::realloc(T** b, long unsigned int, long unsigned int m) {
558  return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
559  }
560  template<class T>
561  forceinline T**
562  Heap::realloc(T** b, long int n, long int m) {
563  assert((n >= 0) && (m >= 0));
564  return realloc<T*>(b,static_cast<long unsigned int>(n),
565  static_cast<long unsigned int>(m));
566  }
567  template<class T>
568  forceinline T**
569  Heap::realloc(T** b, unsigned int n, unsigned int m) {
570  return realloc<T*>(b,static_cast<long unsigned int>(n),
571  static_cast<long unsigned int>(m));
572  }
573  template<class T>
574  forceinline T**
575  Heap::realloc(T** b, int n, int m) {
576  assert((n >= 0) && (m >= 0));
577  return realloc<T*>(b,static_cast<long unsigned int>(n),
578  static_cast<long unsigned int>(m));
579  }
580 
581  template<class T>
582  forceinline T*
583  Heap::copy(T* d, const T* s, long unsigned int n) {
584  for (long unsigned int i=0U; i<n; i++)
585  d[i]=s[i];
586  return d;
587  }
588  template<class T>
589  forceinline T*
590  Heap::copy(T* d, const T* s, long int n) {
591  assert(n >= 0);
592  return copy<T>(d,s,static_cast<long unsigned int>(n));
593  }
594  template<class T>
595  forceinline T*
596  Heap::copy(T* d, const T* s, unsigned int n) {
597  return copy<T>(d,s,static_cast<long unsigned int>(n));
598  }
599  template<class T>
600  forceinline T*
601  Heap::copy(T* d, const T* s, int n) {
602  assert(n >= 0);
603  return copy<T>(d,s,static_cast<long unsigned int>(n));
604  }
605 
606 #define GECODE_SUPPORT_COPY(T) \
607  template<> \
608  forceinline T* \
609  Heap::copy(T* d, const T* s, long unsigned int n) { \
610  return static_cast<T*>(Support::allocator.memcpy(d,s,n*sizeof(T))); \
611  } \
612  template<> \
613  forceinline T* \
614  Heap::copy(T* d, const T* s, long int n) { \
615  assert(n >= 0); \
616  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
617  } \
618  template<> \
619  forceinline T* \
620  Heap::copy(T* d, const T* s, unsigned int n) { \
621  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
622  } \
623  template<> \
624  forceinline T* \
625  Heap::copy(T* d, const T* s, int n) { \
626  assert(n >= 0); \
627  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
628  }
629 
630  GECODE_SUPPORT_COPY(bool)
631  GECODE_SUPPORT_COPY(signed char)
632  GECODE_SUPPORT_COPY(unsigned char)
633  GECODE_SUPPORT_COPY(signed short int)
634  GECODE_SUPPORT_COPY(unsigned short int)
635  GECODE_SUPPORT_COPY(signed int)
636  GECODE_SUPPORT_COPY(unsigned int)
637  GECODE_SUPPORT_COPY(signed long int)
638  GECODE_SUPPORT_COPY(unsigned long int)
639  GECODE_SUPPORT_COPY(float)
640  GECODE_SUPPORT_COPY(double)
641 
642 #undef GECODE_SUPPORT_COPY
643 
644  template<class T>
645  forceinline T**
646  Heap::copy(T** d, const T** s, long unsigned int n) {
647  return static_cast<T**>(Support::allocator.memcpy(d,s,n*sizeof(T*)));
648  }
649  template<class T>
650  forceinline T**
651  Heap::copy(T** d, const T** s, long int n) {
652  assert(n >= 0);
653  return copy<T*>(d,s,static_cast<long unsigned int>(n));
654  }
655  template<class T>
656  forceinline T**
657  Heap::copy(T** d, const T** s, unsigned int n) {
658  return copy<T*>(d,s,static_cast<long unsigned int>(n));
659  }
660  template<class T>
661  forceinline T**
662  Heap::copy(T** d, const T** s, int n) {
663  assert(n >= 0);
664  return copy<T*>(d,s,static_cast<long unsigned int>(n));
665  }
666 
667 #ifdef GECODE_PEAKHEAP
668  forceinline size_t
669  Heap::peak(void) {
670  _m.acquire();
671  size_t ret = _peak;
672  _m.release();
673  return ret;
674  }
675 #endif
676 
677 }
678 
679 // STATISTICS: support-any
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Base class for heap allocated objects.
Definition: heap.hpp:340
Heap memory management class
Definition: heap.hpp:62
Heap(void)
Default constructor (ensuring that only a single instance is created)
Definition: heap.cpp:38
void * rrealloc(void *p, size_t s)
Change memory block starting at p to size s.
Definition: heap.hpp:391
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
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:583
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:457
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:431
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:357
Exception: Memory exhausted
Definition: exception.hpp:63
void free(void *p)
Free memory block p.
Definition: allocator.hpp:87
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:91
void * alloc(size_t n)
Allocate memory block of size n.
Definition: allocator.hpp:79
void * realloc(void *p, size_t n)
Return address of reallocated memory block p of size n.
Definition: allocator.hpp:83
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
Heap heap
The single global heap.
Definition: heap.cpp:44
Allocator allocator
The single global default memory allocator.
Definition: allocator.cpp:38
#define GECODE_SUPPORT_REALLOC(T)
Definition: heap.hpp:514
#define GECODE_SUPPORT_COPY(T)
Definition: heap.hpp:606
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
#define forceinline
Definition: config.hpp:194
#define GECODE_SUPPORT_EXPORT
Definition: support.hh:71