main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Feb 8 2021 00:00:00 for Gecode by
doxygen
1.8.20
gecode
support
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
318
Support::FastMutex
_m;
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
340
class
GECODE_SUPPORT_EXPORT
HeapAllocated
{
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
377
Support::allocator
.
free
(
p
);
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
387
Support::allocator
.
free
(
p
);
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
397
p
=
Support::allocator
.
realloc
(
p
,s);
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
541
GECODE_SUPPORT_REALLOC
(
bool
)
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
)
550
GECODE_SUPPORT_REALLOC
(
float
)
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
Gecode::Support::Allocator::alloc
void * alloc(size_t n)
Allocate memory block of size n.
Definition:
allocator.hpp:79
Gecode::Heap
Heap memory management class
Definition:
heap.hpp:62
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_SUPPORT_COPY
#define GECODE_SUPPORT_COPY(T)
Definition:
heap.hpp:606
Gecode::Support::Allocator::free
void free(void *p)
Free memory block p.
Definition:
allocator.hpp:87
Gecode::Support::allocator
Allocator allocator
The single global default memory allocator.
Definition:
allocator.cpp:38
Gecode::Heap::ralloc
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition:
heap.hpp:357
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::Heap::Heap
Heap(void)
Default constructor (ensuring that only a single instance is created)
Definition:
heap.cpp:38
Gecode::Heap::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition:
heap.hpp:431
Gecode
Gecode toplevel namespace
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Support::Allocator::memcpy
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
Gecode::HeapAllocated
Base class for heap allocated objects.
Definition:
heap.hpp:340
Gecode::heap
Heap heap
The single global heap.
Definition:
heap.cpp:44
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::Heap::free
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition:
heap.hpp:457
Gecode::Heap::rrealloc
void * rrealloc(void *p, size_t s)
Change memory block starting at p to size s.
Definition:
heap.hpp:391
forceinline
#define forceinline
Definition:
config.hpp:192
GECODE_SUPPORT_EXPORT
#define GECODE_SUPPORT_EXPORT
Definition:
support.hh:71
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition:
thread.hpp:96
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::Heap::rfree
void rfree(void *p)
Free memory block starting at p.
Definition:
heap.hpp:371
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
GECODE_SUPPORT_REALLOC
#define GECODE_SUPPORT_REALLOC(T)
Definition:
heap.hpp:514
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
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::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844
Gecode::MemoryExhausted
Exception: Memory exhausted
Definition:
exception.hpp:63
Gecode::Support::Allocator::realloc
void * realloc(void *p, size_t n)
Return address of reallocated memory block p of size n.
Definition:
allocator.hpp:83