Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
46namespace 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
300 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;
324public:
325 size_t peak(void);
326#endif
327 };
328
334 Heap heap;
335
341 public:
343
344
345 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*
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)
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
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)
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::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
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
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_SUPPORT_EXPORT
Definition support.hh:71