this repo has no description
dekker.one
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
48 /**
49 * \defgroup FuncMemHeap %Heap memory management
50 *
51 * \ingroup FuncMem
52 */
53
54
55 /**
56 * \brief %Heap memory management class
57 *
58 * All routines throw an exception of MemoryExhausted, if a request
59 * cannot be fulfilled.
60 * \ingroup FuncMemHeap
61 */
62 class Heap {
63 public:
64 /// Default constructor (ensuring that only a single instance is created)
65 Heap(void);
66 /// \name Typed allocation routines
67 //@{
68 /**
69 * \brief Allocate block of \a n objects of type \a T from heap
70 *
71 * Note that this function implements C++ semantics: the default
72 * constructor of \a T is run for all \a n objects.
73 */
74 template<class T>
75 T* alloc(long unsigned int n);
76 /**
77 * \brief Allocate block of \a n objects of type \a T from heap
78 *
79 * Note that this function implements C++ semantics: the default
80 * constructor of \a T is run for all \a n objects.
81 */
82 template<class T>
83 T* alloc(long int n);
84 /**
85 * \brief Allocate block of \a n objects of type \a T from heap
86 *
87 * Note that this function implements C++ semantics: the default
88 * constructor of \a T is run for all \a n objects.
89 */
90 template<class T>
91 T* alloc(unsigned int n);
92 /**
93 * \brief Allocate block of \a n objects of type \a T from heap
94 *
95 * Note that this function implements C++ semantics: the default
96 * constructor of \a T is run for all \a n objects.
97 */
98 template<class T>
99 T* alloc(int n);
100 /**
101 * \brief Delete \a n objects starting at \a b
102 *
103 * Note that this function implements C++ semantics: the destructor
104 * of \a T is run for all \a n objects.
105 */
106 template<class T>
107 void free(T* b, long unsigned int n);
108 /**
109 * \brief Delete \a n objects starting at \a b
110 *
111 * Note that this function implements C++ semantics: the destructor
112 * of \a T is run for all \a n objects.
113 */
114 template<class T>
115 void free(T* b, long int n);
116 /**
117 * \brief Delete \a n objects starting at \a b
118 *
119 * Note that this function implements C++ semantics: the destructor
120 * of \a T is run for all \a n objects.
121 */
122 template<class T>
123 void free(T* b, unsigned int n);
124 /**
125 * \brief Delete \a n objects starting at \a b
126 *
127 * Note that this function implements C++ semantics: the destructor
128 * of \a T is run for all \a n objects.
129 */
130 template<class T>
131 void free(T* b, int n);
132 /**
133 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from heap
134 *
135 * Note that this function implements C++ semantics: the copy constructor
136 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
137 * constructor of \a T is run for all remaining
138 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
139 * run for all \a n objects in \a b.
140 *
141 * Returns the address of the new block.
142 */
143 template<class T>
144 T* realloc(T* b, long unsigned int n, long unsigned int m);
145 /**
146 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from heap
147 *
148 * Note that this function implements C++ semantics: the copy constructor
149 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
150 * constructor of \a T is run for all remaining
151 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
152 * run for all \a n objects in \a b.
153 *
154 * Returns the address of the new block.
155 */
156 template<class T>
157 T* realloc(T* b, long int n, long int m);
158 /**
159 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from heap
160 *
161 * Note that this function implements C++ semantics: the copy constructor
162 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
163 * constructor of \a T is run for all remaining
164 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
165 * run for all \a n objects in \a b.
166 *
167 * Returns the address of the new block.
168 */
169 template<class T>
170 T* realloc(T* b, unsigned int n, unsigned int m);
171 /**
172 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from heap
173 *
174 * Note that this function implements C++ semantics: the copy constructor
175 * of \a T is run for all \f$\min(n,m)\f$ objects, the default
176 * constructor of \a T is run for all remaining
177 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is
178 * run for all \a n objects in \a b.
179 *
180 * Returns the address of the new block.
181 */
182 template<class T>
183 T* realloc(T* b, int n, int m);
184 /**
185 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from heap
186 *
187 * Returns the address of the new block.
188 *
189 * This is a specialization for performance.
190 */
191 template<class T>
192 T** realloc(T** b, long unsigned int n, long unsigned int m);
193 /**
194 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from heap
195 *
196 * Returns the address of the new block.
197 *
198 * This is a specialization for performance.
199 */
200 template<class T>
201 T** realloc(T** b, long int n, long int m);
202 /**
203 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from heap
204 *
205 * Returns the address of the new block.
206 *
207 * This is a specialization for performance.
208 */
209 template<class T>
210 T** realloc(T** b, unsigned int n, unsigned int m);
211 /**
212 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from heap
213 *
214 * Returns the address of the new block.
215 *
216 * This is a specialization for performance.
217 */
218 template<class T>
219 T** realloc(T** b, int n, int m);
220 /**
221 * \brief Copy \a n objects starting at \a s to \a d
222 *
223 * Note that this function implements C++ semantics: the assignment
224 * operator of \a T is run for all \a n objects.
225 *
226 * Returns \a d.
227 */
228 template<class T>
229 static T* copy(T* d, const T* s, long unsigned int n);
230 /**
231 * \brief Copy \a n objects starting at \a s to \a d
232 *
233 * Note that this function implements C++ semantics: the assignment
234 * operator of \a T is run for all \a n objects.
235 *
236 * Returns \a d.
237 */
238 template<class T>
239 static T* copy(T* d, const T* s, long int n);
240 /**
241 * \brief Copy \a n objects starting at \a s to \a d
242 *
243 * Note that this function implements C++ semantics: the assignment
244 * operator of \a T is run for all \a n objects.
245 *
246 * Returns \a d.
247 */
248 template<class T>
249 static T* copy(T* d, const T* s, unsigned int n);
250 /**
251 * \brief Copy \a n objects starting at \a s to \a d
252 *
253 * Note that this function implements C++ semantics: the assignment
254 * operator of \a T is run for all \a n objects.
255 *
256 * Returns \a d.
257 */
258 template<class T>
259 static T* copy(T* d, const T* s, int n);
260 /**
261 * \brief Copy \a n pointers starting at \a s to \a d
262 *
263 * Returns \a d.
264 *
265 * This is a specialization for performance.
266 */
267 template<class T>
268 static T** copy(T** d, const T** s, long unsigned int n);
269 /**
270 * \brief Copy \a n pointers starting at \a s to \a d
271 *
272 * Returns \a d.
273 *
274 * This is a specialization for performance.
275 */
276 template<class T>
277 static T** copy(T** d, const T** s, long int n);
278 /**
279 * \brief Copy \a n pointers starting at \a s to \a d
280 *
281 * Returns \a d.
282 *
283 * This is a specialization for performance.
284 */
285 template<class T>
286 static T** copy(T** d, const T** s, unsigned int n);
287 /**
288 * \brief Copy \a n pointers starting at \a s to \a d
289 *
290 * Returns \a d.
291 *
292 * This is a specialization for performance.
293 */
294 template<class T>
295 static T** copy(T** d, const T** s, int n);
296 //@}
297 /// \name Raw allocation routines
298 //@{
299 /// Allocate \a s bytes from heap
300 void* ralloc(size_t s);
301 /// Free memory block starting at \a p
302 void rfree(void* p);
303 /// Free memory block starting at \a p with size \a s
304 void rfree(void* p, size_t s);
305 /// Change memory block starting at \a p to size \a s
306 void* rrealloc(void* p, size_t s);
307 //@}
308#ifdef GECODE_PEAKHEAP
309 private:
310 /// Mutex for accessing heap size
311 Support::FastMutex _m;
312 /// Peak heap size
313 size_t _peak;
314 /// Current heap size
315 size_t _cur;
316public:
317 size_t peak(void);
318#endif
319 /// Allocate memory from heap (disabled)
320 static void* operator new(size_t s) = delete;
321 /// Free memory allocated from heap (disabled)
322 static void operator delete(void* p) = delete;
323 /// Copy constructor (disabled)
324 Heap(const Heap&) = delete;
325 /// Assignment operator (disabled)
326 const Heap& operator =(const Heap&) = delete;
327 };
328
329 /**
330 * \brief The single global heap
331 * \ingroup FuncMemHeap
332 */
333 extern GECODE_SUPPORT_EXPORT
334 Heap heap;
335
336 /**
337 * \brief Base class for heap allocated objects
338 * \ingroup FuncMemHeap
339 */
340 class GECODE_SUPPORT_EXPORT HeapAllocated {
341 public:
342 /// Memory management
343 //@{
344 /// Allocate memory from heap
345 static void* operator new(size_t s);
346 /// Free memory allocated from heap
347 static void operator delete(void* p);
348 //@}
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 != nullptr)
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 != nullptr || 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