Generated on Fri Aug 24 2012 04:52:14 for Gecode by doxygen 1.8.1.2
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: 2010-07-26 20:53:58 +1000 (Mon, 26 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11279 $
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 namespace Gecode {
43 
58  class Heap {
59  public:
61  Heap(void);
63 
64 
70  template<class T>
71  T* alloc(long unsigned int n);
78  template<class T>
79  T* alloc(long int n);
86  template<class T>
87  T* alloc(unsigned int n);
94  template<class T>
95  T* alloc(int n);
102  template<class T>
103  void free(T* b, long unsigned int n);
110  template<class T>
111  void free(T* b, long int n);
118  template<class T>
119  void free(T* b, unsigned int n);
126  template<class T>
127  void free(T* b, int n);
139  template<class T>
140  T* realloc(T* b, long unsigned int n, long unsigned int m);
152  template<class T>
153  T* realloc(T* b, long int n, long int m);
165  template<class T>
166  T* realloc(T* b, unsigned int n, unsigned int m);
178  template<class T>
179  T* realloc(T* b, int n, int m);
187  template<class T>
188  T** realloc(T** b, long unsigned int n, long unsigned int m);
196  template<class T>
197  T** realloc(T** b, long int n, long int m);
205  template<class T>
206  T** realloc(T** b, unsigned int n, unsigned int m);
214  template<class T>
215  T** realloc(T** b, int n, int m);
224  template<class T>
225  static T* copy(T* d, const T* s, long unsigned int n);
234  template<class T>
235  static T* copy(T* d, const T* s, long int n);
244  template<class T>
245  static T* copy(T* d, const T* s, unsigned int n);
254  template<class T>
255  static T* copy(T* d, const T* s, int n);
263  template<class T>
264  static T** copy(T** d, const T** s, long unsigned int n);
272  template<class T>
273  static T** copy(T** d, const T** s, long int n);
281  template<class T>
282  static T** copy(T** d, const T** s, unsigned int n);
290  template<class T>
291  static T** copy(T** d, const T** s, int n);
293 
294 
295 
296  void* ralloc(size_t s);
298  void rfree(void* p);
300  void rfree(void* p, size_t s);
302  void* rrealloc(void* p, size_t s);
304  private:
306  static void* operator new(size_t s) throw() { (void) s; return NULL; }
308  static void operator delete(void* p) { (void) p; };
310  Heap(const Heap&) {}
312  const Heap& operator =(const Heap&) { return *this; }
313  };
314 
317 
318  /*
319  * Wrappers for raw allocation routines
320  *
321  */
322  forceinline void*
323  Heap::ralloc(size_t s) {
324  void* p = ::malloc(s);
325  if (p != NULL)
326  return p;
327  throw MemoryExhausted();
328  }
329 
330  forceinline void
331  Heap::rfree(void* p) {
332  ::free(p);
333  }
334 
335  forceinline void
336  Heap::rfree(void* p, size_t) {
337  ::free(p);
338  }
339 
340  forceinline void*
341  Heap::rrealloc(void* p, size_t s) {
342  p = ::realloc(p,s);
343  if (p != NULL || s == 0)
344  return p;
345  throw MemoryExhausted();
346  }
347 
348 
349  /*
350  * Typed allocation routines
351  *
352  */
353  template<class T>
354  forceinline T*
355  Heap::alloc(long unsigned int n) {
356  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
357  for (long unsigned int i=n; i--; )
358  (void) new (p+i) T();
359  return p;
360  }
361  template<class T>
362  forceinline T*
363  Heap::alloc(long int n) {
364  assert(n >= 0);
365  return alloc<T>(static_cast<long unsigned int>(n));
366  }
367  template<class T>
368  forceinline T*
369  Heap::alloc(unsigned int n) {
370  return alloc<T>(static_cast<long unsigned int>(n));
371  }
372  template<class T>
373  forceinline T*
374  Heap::alloc(int n) {
375  assert(n >= 0);
376  return alloc<T>(static_cast<long unsigned int>(n));
377  }
378 
379  template<class T>
380  forceinline void
381  Heap::free(T* b, long unsigned int n) {
382  for (long unsigned int i=n; i--; )
383  b[i].~T();
384  rfree(b);
385  }
386  template<class T>
387  forceinline void
388  Heap::free(T* b, long int n) {
389  assert(n >= 0);
390  free<T>(b, static_cast<long unsigned int>(n));
391  }
392  template<class T>
393  forceinline void
394  Heap::free(T* b, unsigned int n) {
395  free<T>(b, static_cast<long unsigned int>(n));
396  }
397  template<class T>
398  forceinline void
399  Heap::free(T* b, int n) {
400  assert(n >= 0);
401  free<T>(b, static_cast<long unsigned int>(n));
402  }
403 
404  template<class T>
405  forceinline T*
406  Heap::realloc(T* b, long unsigned int n, long unsigned int m) {
407  if (n == m)
408  return b;
409  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
410  for (long unsigned int i=std::min(n,m); i--; )
411  (void) new (p+i) T(b[i]);
412  for (long unsigned int i=n; i<m; i++)
413  (void) new (p+i) T();
414  free<T>(b,n);
415  return p;
416  }
417  template<class T>
418  forceinline T*
419  Heap::realloc(T* b, long int n, long int m) {
420  assert((n >= 0) && (m >= 0));
421  return realloc<T>(b,static_cast<long unsigned int>(n),
422  static_cast<long unsigned int>(m));
423  }
424  template<class T>
425  forceinline T*
426  Heap::realloc(T* b, unsigned int n, unsigned int m) {
427  return realloc<T>(b,static_cast<long unsigned int>(n),
428  static_cast<long unsigned int>(m));
429  }
430  template<class T>
431  forceinline T*
432  Heap::realloc(T* b, int n, int m) {
433  assert((n >= 0) && (m >= 0));
434  return realloc<T>(b,static_cast<long unsigned int>(n),
435  static_cast<long unsigned int>(m));
436  }
437 
438 #define GECODE_SUPPORT_REALLOC(T) \
439  template<> \
440  forceinline T* \
441  Heap::realloc<T>(T* b, long unsigned int, long unsigned int m) { \
442  return static_cast<T*>(rrealloc(b,m*sizeof(T))); \
443  } \
444  template<> \
445  forceinline T* \
446  Heap::realloc<T>(T* b, long int n, long int m) { \
447  assert((n >= 0) && (m >= 0)); \
448  return realloc<T>(b,static_cast<long unsigned int>(n), \
449  static_cast<long unsigned int>(m)); \
450  } \
451  template<> \
452  forceinline T* \
453  Heap::realloc<T>(T* b, unsigned int n, unsigned int m) { \
454  return realloc<T>(b,static_cast<long unsigned int>(n), \
455  static_cast<long unsigned int>(m)); \
456  } \
457  template<> \
458  forceinline T* \
459  Heap::realloc<T>(T* b, int n, int m) { \
460  assert((n >= 0) && (m >= 0)); \
461  return realloc<T>(b,static_cast<long unsigned int>(n), \
462  static_cast<long unsigned int>(m)); \
463  }
464 
466  GECODE_SUPPORT_REALLOC(signed char)
467  GECODE_SUPPORT_REALLOC(unsigned char)
468  GECODE_SUPPORT_REALLOC(signed short int)
469  GECODE_SUPPORT_REALLOC(unsigned short int)
470  GECODE_SUPPORT_REALLOC(signed int)
471  GECODE_SUPPORT_REALLOC(unsigned int)
472  GECODE_SUPPORT_REALLOC(signed long int)
473  GECODE_SUPPORT_REALLOC(unsigned long int)
475  GECODE_SUPPORT_REALLOC(double)
476 
477 #undef GECODE_SUPPORT_REALLOC
478 
479  template<class T>
480  forceinline T**
481  Heap::realloc(T** b, long unsigned int, long unsigned int m) {
482  return static_cast<T**>(rrealloc(b,m*sizeof(T*)));
483  }
484  template<class T>
485  forceinline T**
486  Heap::realloc(T** b, long int n, long int m) {
487  assert((n >= 0) && (m >= 0));
488  return realloc<T*>(b,static_cast<long unsigned int>(n),
489  static_cast<long unsigned int>(m));
490  }
491  template<class T>
492  forceinline T**
493  Heap::realloc(T** b, unsigned int n, unsigned int m) {
494  return realloc<T*>(b,static_cast<long unsigned int>(n),
495  static_cast<long unsigned int>(m));
496  }
497  template<class T>
498  forceinline T**
499  Heap::realloc(T** b, int n, 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 
505  template<class T>
506  forceinline T*
507  Heap::copy(T* d, const T* s, long unsigned int n) {
508  for (long unsigned int i=n; i--; )
509  d[i]=s[i];
510  return d;
511  }
512  template<class T>
513  forceinline T*
514  Heap::copy(T* d, const T* s, long int n) {
515  assert(n >= 0);
516  return copy<T>(d,s,static_cast<long unsigned int>(n));
517  }
518  template<class T>
519  forceinline T*
520  Heap::copy(T* d, const T* s, unsigned int n) {
521  return copy<T>(d,s,static_cast<long unsigned int>(n));
522  }
523  template<class T>
524  forceinline T*
525  Heap::copy(T* d, const T* s, int n) {
526  assert(n >= 0);
527  return copy<T>(d,s,static_cast<long unsigned int>(n));
528  }
529 
530 #define GECODE_SUPPORT_COPY(T) \
531  template<> \
532  forceinline T* \
533  Heap::copy(T* d, const T* s, long unsigned int n) { \
534  return static_cast<T*>(memcpy(d,s,n*sizeof(T))); \
535  } \
536  template<> \
537  forceinline T* \
538  Heap::copy(T* d, const T* s, long int n) { \
539  assert(n >= 0); \
540  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
541  } \
542  template<> \
543  forceinline T* \
544  Heap::copy(T* d, const T* s, unsigned int n) { \
545  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
546  } \
547  template<> \
548  forceinline T* \
549  Heap::copy(T* d, const T* s, int n) { \
550  assert(n >= 0); \
551  return copy<T>(d,s,static_cast<long unsigned int>(n)); \
552  }
553 
554  GECODE_SUPPORT_COPY(bool)
555  GECODE_SUPPORT_COPY(signed char)
556  GECODE_SUPPORT_COPY(unsigned char)
557  GECODE_SUPPORT_COPY(signed short int)
558  GECODE_SUPPORT_COPY(unsigned short int)
559  GECODE_SUPPORT_COPY(signed int)
560  GECODE_SUPPORT_COPY(unsigned int)
561  GECODE_SUPPORT_COPY(signed long int)
562  GECODE_SUPPORT_COPY(unsigned long int)
563  GECODE_SUPPORT_COPY(float)
564  GECODE_SUPPORT_COPY(double)
565 
566 #undef GECODE_SUPPORT_COPY
567 
568  template<class T>
569  forceinline T**
570  Heap::copy(T** d, const T** s, long unsigned int n) {
571  return static_cast<T**>(memcpy(d,s,n*sizeof(T*)));
572  }
573  template<class T>
574  forceinline T**
575  Heap::copy(T** d, const T** s, long int n) {
576  assert(n >= 0);
577  return copy<T*>(d,s,static_cast<long unsigned int>(n));
578  }
579  template<class T>
580  forceinline T**
581  Heap::copy(T** d, const T** s, unsigned int n) {
582  return copy<T*>(d,s,static_cast<long unsigned int>(n));
583  }
584  template<class T>
585  forceinline T**
586  Heap::copy(T** d, const T** s, int n) {
587  assert(n >= 0);
588  return copy<T*>(d,s,static_cast<long unsigned int>(n));
589  }
590 
591 }
592 
593 // STATISTICS: support-any