main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
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
* Last modified:
10
* $Date: 2016-04-20 17:14:25 +0200 (Wed, 20 Apr 2016) $ by $Author: schulte $
11
* $Revision: 14972 $
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
322
Support::FastMutex
_m;
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
344
class
GECODE_SUPPORT_EXPORT
HeapAllocated
{
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
381
Support::allocator
.
free
(
p
);
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
391
Support::allocator
.
free
(
p
);
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
545
GECODE_SUPPORT_REALLOC
(
bool
)
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
)
554
GECODE_SUPPORT_REALLOC
(
float
)
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
Gecode::Support::Allocator::alloc
void * alloc(size_t n)
Allocate memory block of size n.
Definition:
allocator.hpp:83
Gecode::Heap
Heap memory management class
Definition:
heap.hpp:66
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:587
GECODE_SUPPORT_COPY
#define GECODE_SUPPORT_COPY(T)
Definition:
heap.hpp:610
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::Support::Allocator::free
void free(void *p)
Free memory block p.
Definition:
allocator.hpp:91
Gecode::Support::allocator
Allocator allocator
The single global default memory allocator.
Definition:
allocator.cpp:42
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Heap::ralloc
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition:
heap.hpp:361
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:850
Gecode::Heap::Heap
Heap(void)
Default constructor (ensuring that only a single instance is created)
Definition:
heap.cpp:42
Gecode::Heap::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition:
heap.hpp:435
Gecode
Gecode toplevel namespace
b
struct Gecode::@579::NNF::@61::@62 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:95
Gecode::HeapAllocated
Base class for heap allocated objects.
Definition:
heap.hpp:344
Gecode::heap
Heap heap
The single global heap.
Definition:
heap.cpp:48
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:461
Gecode::Heap::rrealloc
void * rrealloc(void *p, size_t s)
Change memory block starting at p to size s.
Definition:
heap.hpp:395
GECODE_SUPPORT_EXPORT
#define GECODE_SUPPORT_EXPORT
Definition:
support.hh:75
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition:
thread.hpp:99
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:238
Gecode::Heap::rfree
void rfree(void *p)
Free memory block starting at p.
Definition:
heap.hpp:375
GECODE_SUPPORT_REALLOC
#define GECODE_SUPPORT_REALLOC(T)
Definition:
heap.hpp:518
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:236
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:486
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848
Gecode::MemoryExhausted
Exception: Memory exhausted
Definition:
exception.hpp:67
Gecode::Support::Allocator::realloc
void * realloc(void *p, size_t n)
Return address of reallocated memory block p of size n.
Definition:
allocator.hpp:87