Generated on Sat Feb 7 2015 02:01:31 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2013-07-15 02:49:56 +0200 (Mon, 15 Jul 2013) $ by $Author: tack $
11  * $Revision: 13879 $
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 
335 
336  /*
337  * Wrappers for raw allocation routines
338  *
339  */
340  forceinline void*
341  Heap::ralloc(size_t s) {
342  void* p = ::malloc(s);
343 #ifdef GECODE_PEAKHEAP
344  _m.acquire();
345  _cur += GECODE_MSIZE(p);
346  _peak = std::max(_peak,_cur);
347  _m.release();
348 #endif
349  if (p != NULL)
350  return p;
351  throw MemoryExhausted();
352  }
353 
354  forceinline void
355  Heap::rfree(void* p) {
356 #ifdef GECODE_PEAKHEAP
357  _m.acquire();
358  _cur -= GECODE_MSIZE(p);
359  _m.release();
360 #endif
361  ::free(p);
362  }
363 
364  forceinline void
365  Heap::rfree(void* p, size_t) {
366 #ifdef GECODE_PEAKHEAP
367  _m.acquire();
368  _cur -= GECODE_MSIZE(p);
369  _m.release();
370 #endif
371  ::free(p);
372  }
373 
374  forceinline void*
375  Heap::rrealloc(void* p, size_t s) {
376 #ifdef GECODE_PEAKHEAP
377  _m.acquire();
378  _cur -= GECODE_MSIZE(p);
379  _m.release();
380 #endif
381  p = ::realloc(p,s);
382 #ifdef GECODE_PEAKHEAP
383  _m.acquire();
384  _cur += GECODE_MSIZE(p);
385  _peak = std::max(_peak,_cur);
386  _m.release();
387 #endif
388  if (p != NULL || s == 0)
389  return p;
390  throw MemoryExhausted();
391  }
392 
393 
394  /*
395  * Typed allocation routines
396  *
397  */
398  template<class T>
399  forceinline T*
400  Heap::alloc(long unsigned int n) {
401  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
402  for (long unsigned int i=n; i--; )
403  (void) new (p+i) T();
404  return p;
405  }
406  template<class T>
407  forceinline T*
408  Heap::alloc(long int n) {
409  assert(n >= 0);
410  return alloc<T>(static_cast<long unsigned int>(n));
411  }
412  template<class T>
413  forceinline T*
414  Heap::alloc(unsigned int n) {
415  return alloc<T>(static_cast<long unsigned int>(n));
416  }
417  template<class T>
418  forceinline T*
419  Heap::alloc(int n) {
420  assert(n >= 0);
421  return alloc<T>(static_cast<long unsigned int>(n));
422  }
423 
424  template<class T>
425  forceinline void
426  Heap::free(T* b, long unsigned int n) {
427  for (long unsigned int i=n; i--; )
428  b[i].~T();
429  rfree(b);
430  }
431  template<class T>
432  forceinline void
433  Heap::free(T* b, long int n) {
434  assert(n >= 0);
435  free<T>(b, static_cast<long unsigned int>(n));
436  }
437  template<class T>
438  forceinline void
439  Heap::free(T* b, unsigned int n) {
440  free<T>(b, static_cast<long unsigned int>(n));
441  }
442  template<class T>
443  forceinline void
444  Heap::free(T* b, int n) {
445  assert(n >= 0);
446  free<T>(b, static_cast<long unsigned int>(n));
447  }
448 
449  template<class T>
450  forceinline T*
451  Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
452  if (n == m)
453  return b;
454  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
455  for (long unsigned int i=std::min(n,m); i--; )
456  (void) new (p+i) T(b[i]);
457  for (long unsigned int i=n; i<m; i++)
458  (void) new (p+i) T();
459  free<T>(b,n);
460  return p;
461  }
462  template<class T>
463  forceinline T*
464  Heap::realloc(T* b, long int n, long int m) {
465  assert((n >= 0) && (m >= 0));
466  return realloc<T>(b,static_cast<long unsigned int>(n),
467  static_cast<long unsigned int>(m));
468  }
469  template<class T>
470  forceinline T*
471  Heap::realloc(T* b, unsigned int n, unsigned int m) {
472  return realloc<T>(b,static_cast<long unsigned int>(n),
473  static_cast<long unsigned int>(m));
474  }
475  template<class T>
476  forceinline T*
477  Heap::realloc(T* b, int n, int m) {
478  assert((n >= 0) && (m >= 0));
479  return realloc<T>(b,static_cast<long unsigned int>(n),
480  static_cast<long unsigned int>(m));
481  }
482 
483 #define GECODE_SUPPORT_REALLOC(T) \
484  template<> \
485  forceinline T* \
486  Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
487  return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
488  } \
489  template<> \
490  forceinline T* \
491  Heap::realloc<T>(T* b, long int n, long int m) { \
492  assert((n >= 0) && (m >= 0)); \
493  return realloc<T>(b,static_cast<long unsigned int>(n), \
494  static_cast<long unsigned int>(m)); \
495  } \
496  template<> \
497  forceinline T* \
498  Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
499  return realloc<T>(b,static_cast<long unsigned int>(n), \
500  static_cast<long unsigned int>(m)); \
501  } \
502  template<> \
503  forceinline T* \
504  Heap::realloc<T>(T* b, int n, int m) { \
505  assert((n >= 0) && (m >= 0)); \
506  return realloc<T>(b,static_cast<long unsigned int>(n), \
507  static_cast<long unsigned int>(m)); \
508  }
509 
511  GECODE_SUPPORT_REALLOC(signed char)
512  GECODE_SUPPORT_REALLOC(unsigned char)
513  GECODE_SUPPORT_REALLOC(signed short int)
514  GECODE_SUPPORT_REALLOC(unsigned short int)
515  GECODE_SUPPORT_REALLOC(signed int)
516  GECODE_SUPPORT_REALLOC(unsigned int)
517  GECODE_SUPPORT_REALLOC(signed long int)
518  GECODE_SUPPORT_REALLOC(unsigned long int)
520  GECODE_SUPPORT_REALLOC(double)
521 
522 #undef GECODE_SUPPORT_REALLOC
523 
524  template<class T>
525  forceinline T**
526  Heap::realloc(T** b, long unsigned int, long unsigned int m) {
527  return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
528  }
529  template<class T>
530  forceinline T**
531  Heap::realloc(T** b, long int n, long int m) {
532  assert((n >= 0) && (m >= 0));
533  return realloc<T*>(b,static_cast<long unsigned int>(n),
534  static_cast<long unsigned int>(m));
535  }
536  template<class T>
537  forceinline T**
538  Heap::realloc(T** b, unsigned int n, unsigned int m) {
539  return realloc<T*>(b,static_cast<long unsigned int>(n),
540  static_cast<long unsigned int>(m));
541  }
542  template<class T>
543  forceinline T**
544  Heap::realloc(T** b, int n, int m) {
545  assert((n >= 0) && (m >= 0));
546  return realloc<T*>(b,static_cast<long unsigned int>(n),
547  static_cast<long unsigned int>(m));
548  }
549 
550  template<class T>
551  forceinline T*
552  Heap::copy(T* d, const T* s, long unsigned int n) {
553  for (long unsigned int i=n; i--; )
554  d[i]=s[i];
555  return d;
556  }
557  template<class T>
558  forceinline T*
559  Heap::copy(T* d, const T* s, long int n) {
560  assert(n >= 0);
561  return copy<T>(d,s,static_cast<long unsigned int>(n));
562  }
563  template<class T>
564  forceinline T*
565  Heap::copy(T* d, const T* s, unsigned int n) {
566  return copy<T>(d,s,static_cast<long unsigned int>(n));
567  }
568  template<class T>
569  forceinline T*
570  Heap::copy(T* d, const T* s, int n) {
571  assert(n >= 0);
572  return copy<T>(d,s,static_cast<long unsigned int>(n));
573  }
574 
575 #define GECODE_SUPPORT_COPY(T) \
576  template<> \
577  forceinline T* \
578  Heap::copy(T* d, const T* s, long unsigned int n) { \
579  return static_cast<T*>(memcpy(d,s,n*sizeof(T))); \
580  } \
581  template<> \
582  forceinline T* \
583  Heap::copy(T* d, const T* s, long int n) { \
584  assert(n >= 0); \
585  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
586  } \
587  template<> \
588  forceinline T* \
589  Heap::copy(T* d, const T* s, unsigned int n) { \
590  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
591  } \
592  template<> \
593  forceinline T* \
594  Heap::copy(T* d, const T* s, int n) { \
595  assert(n >= 0); \
596  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
597  }
598 
599  GECODE_SUPPORT_COPY(bool)
600  GECODE_SUPPORT_COPY(signed char)
601  GECODE_SUPPORT_COPY(unsigned char)
602  GECODE_SUPPORT_COPY(signed short int)
603  GECODE_SUPPORT_COPY(unsigned short int)
604  GECODE_SUPPORT_COPY(signed int)
605  GECODE_SUPPORT_COPY(unsigned int)
606  GECODE_SUPPORT_COPY(signed long int)
607  GECODE_SUPPORT_COPY(unsigned long int)
608  GECODE_SUPPORT_COPY(float)
609  GECODE_SUPPORT_COPY(double)
610 
611 #undef GECODE_SUPPORT_COPY
612 
613  template<class T>
614  forceinline T**
615  Heap::copy(T** d, const T** s, long unsigned int n) {
616  return static_cast<T**>(memcpy(d,s,n*sizeof(T*)));
617  }
618  template<class T>
619  forceinline T**
620  Heap::copy(T** d, const T** s, long int n) {
621  assert(n >= 0);
622  return copy<T*>(d,s,static_cast<long unsigned int>(n));
623  }
624  template<class T>
625  forceinline T**
626  Heap::copy(T** d, const T** s, unsigned int n) {
627  return copy<T*>(d,s,static_cast<long unsigned int>(n));
628  }
629  template<class T>
630  forceinline T**
631  Heap::copy(T** d, const T** s, int n) {
632  assert(n >= 0);
633  return copy<T*>(d,s,static_cast<long unsigned int>(n));
634  }
635 
636 #ifdef GECODE_PEAKHEAP
637  forceinline size_t
638  Heap::peak(void) {
639  _m.acquire();
640  size_t ret = _peak;
641  _m.release();
642  return ret;
643  }
644 #endif
645 
646 }
647 
648 // 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:552
#define GECODE_SUPPORT_REALLOC(T)
Definition: heap.hpp:483
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
Exception: Memory exhausted
Definition: exception.hpp:65
Heap(void)
Default constructor (ensuring that only a single instance is created)
Definition: heap.cpp:43
Heap heap
The single global heap.
Definition: heap.cpp:49
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
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:400
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
#define GECODE_SUPPORT_EXPORT
Definition: support.hh:75
Heap memory management class
Definition: heap.hpp:66
#define GECODE_SUPPORT_COPY(T)
Definition: heap.hpp:575
void * rrealloc(void *p, size_t s)
Change memory block starting at p to size s.
Definition: heap.hpp:375
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
#define forceinline
Definition: config.hpp:132
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:451
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace