Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
core.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  * Guido Tack <tack@gecode.org>
6  * Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  * Contributing authors:
9  * Filip Konvicka <filip.konvicka@logis.cz>
10  *
11  * Copyright:
12  * Christian Schulte, 2002
13  * Guido Tack, 2003
14  * Mikael Lagerkvist, 2006
15  * LOGIS, s.r.o., 2009
16  *
17  * Bugfixes provided by:
18  * Alexander Samoilov <alexander_samoilov@yahoo.com>
19  *
20  * Last modified:
21  * $Date: 2013-03-05 15:37:20 +0100 (Tue, 05 Mar 2013) $ by $Author: schulte $
22  * $Revision: 13437 $
23  *
24  * This file is part of Gecode, the generic constraint
25  * development environment:
26  * http://www.gecode.org
27  *
28  * Permission is hereby granted, free of charge, to any person obtaining
29  * a copy of this software and associated documentation files (the
30  * "Software"), to deal in the Software without restriction, including
31  * without limitation the rights to use, copy, modify, merge, publish,
32  * distribute, sublicense, and/or sell copies of the Software, and to
33  * permit persons to whom the Software is furnished to do so, subject to
34  * the following conditions:
35  *
36  * The above copyright notice and this permission notice shall be
37  * included in all copies or substantial portions of the Software.
38  *
39  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
41  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
43  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
44  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
45  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
46  *
47  */
48 #include <iostream>
49 namespace Gecode {
50 
51  class Space;
52 
77  class SharedHandle {
78  public:
86  class Object {
87  friend class Space;
88  friend class SharedHandle;
89  private:
91  Object* next;
93  Object* fwd;
95  unsigned int use_cnt;
96  public:
98  Object(void);
100  virtual Object* copy(void) const = 0;
102  virtual ~Object(void);
104  static void* operator new(size_t s);
106  static void operator delete(void* p);
107  };
108  private:
110  Object* o;
112  void subscribe(void);
114  void cancel(void);
115  public:
117  SharedHandle(void);
121  SharedHandle(const SharedHandle& sh);
125  void update(Space& home, bool share, SharedHandle& sh);
127  ~SharedHandle(void);
128  protected:
130  SharedHandle::Object* object(void) const;
133  };
134 
143 
144  typedef int ModEvent;
145 
152 
154  typedef int PropCond;
156  const PropCond PC_GEN_NONE = -1;
160 
171  typedef int ModEventDelta;
172 
173 }
174 
176 
177 namespace Gecode {
178 
181  public:
183  static const int idx_c = -1;
185  static const int idx_d = -1;
189  static const int free_bits = 0;
191  static const int med_fst = 0;
193  static const int med_lst = 0;
195  static const int med_mask = 0;
197  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
199  static bool med_update(ModEventDelta& med, ModEvent me);
200  };
201 
204  GECODE_NEVER; return 0;
205  }
206  forceinline bool
208  GECODE_NEVER; return false;
209  }
210 
211 
212  /*
213  * These are the classes of interest
214  *
215  */
216  class ActorLink;
217  class Actor;
218  class Propagator;
219  class LocalObject;
220  class Advisor;
221  class AFC;
222  class Brancher;
223  class BrancherHandle;
224  template<class A> class Council;
225  template<class A> class Advisors;
226  template<class VIC> class VarImp;
227 
228 
229  /*
230  * Variable implementations
231  *
232  */
233 
241  class VarImpBase {};
242 
250  public:
252  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
255  };
256 
263  template<class VarImp>
265  public:
267  VarImpDisposer(void);
269  virtual void dispose(Space& home, VarImpBase* x);
270  };
271 
273  class Delta {
274  template<class VIC> friend class VarImp;
275  private:
277  ModEvent me;
278  };
279 
287  template<class VIC>
288  class VarImp : public VarImpBase {
289  friend class Space;
290  friend class Propagator;
291  template<class VarImp> friend class VarImpDisposer;
292  private:
293  union {
311  } b;
312 
314  static const int idx_c = VIC::idx_c;
316  static const int idx_d = VIC::idx_d;
318  static const int free_bits = VIC::free_bits;
320  unsigned int entries;
322  unsigned int free_and_bits;
324  static const Gecode::PropCond pc_max = VIC::pc_max;
325 
326  union {
337  unsigned int idx[pc_max+1];
340  } u;
341 
343  ActorLink** actor(PropCond pc);
345  ActorLink** actorNonZero(PropCond pc);
347  unsigned int& idx(PropCond pc);
349  unsigned int idx(PropCond pc) const;
350 
357  void update(VarImp* x, ActorLink**& sub);
364  static void update(Space& home, ActorLink**& sub);
365 
367  void enter(Space& home, Propagator* p, PropCond pc);
369  void enter(Space& home, Advisor* a);
371  void resize(Space& home);
373  void remove(Space& home, Propagator* p, PropCond pc);
375  void remove(Space& home, Advisor* a);
376 
377 
378  protected:
380  void cancel(Space& home);
386  bool advise(Space& home, ModEvent me, Delta& d);
387 #ifdef GECODE_HAS_VAR_DISPOSE
388 
389  static VarImp<VIC>* vars_d(Space& home);
391  static void vars_d(Space& home, VarImp<VIC>* x);
392 #endif
393 
394  public:
396  VarImp(Space& home);
398  VarImp(void);
399 
401 
402 
414  void subscribe(Space& home, Propagator& p, PropCond pc,
415  bool assigned, ModEvent me, bool schedule);
421  void cancel(Space& home, Propagator& p, PropCond pc,
422  bool assigned);
428  void subscribe(Space& home, Advisor& a, bool assigned);
434  void cancel(Space& home, Advisor& a, bool assigned);
435 
442  unsigned int degree(void) const;
449  double afc(const Space& home) const;
451 
453 
454 
455  VarImp(Space& home, bool share, VarImp& x);
457  bool copied(void) const;
459  VarImp* forward(void) const;
461  VarImp* next(void) const;
463 
465 
466 
473  static void schedule(Space& home, Propagator& p, ModEvent me,
474  bool force = false);
476  static ModEvent me(const ModEventDelta& med);
478  static ModEventDelta med(ModEvent me);
480  static ModEvent me_combine(ModEvent me1, ModEvent me2);
482 
484 
485 
486  static ModEvent modevent(const Delta& d);
488 
490 
491 
492  unsigned int bits(void) const;
494  unsigned int& bits(void);
496 
497  protected:
499  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
500 
501  public:
503 
504 
505  static void* operator new(size_t,Space&);
507  static void operator delete(void*,Space&);
509  static void operator delete(void*);
511  };
512 
521  enum ExecStatus {
523  ES_FAILED = -1,
524  ES_NOFIX = 0,
525  ES_OK = 0,
526  ES_FIX = 1,
529  };
530 
535  class PropCost {
536  friend class Space;
537  public:
539  enum ActualCost {
554  AC_MAX = 6
555  };
558  public:
560  enum Mod {
561  LO,
562  HI
563  };
564  private:
566  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
569  public:
571  static PropCost crazy(PropCost::Mod m, unsigned int n);
573  static PropCost crazy(PropCost::Mod m, int n);
575  static PropCost cubic(PropCost::Mod m, unsigned int n);
577  static PropCost cubic(PropCost::Mod m, int n);
579  static PropCost quadratic(PropCost::Mod m, unsigned int n);
581  static PropCost quadratic(PropCost::Mod m, int n);
583  static PropCost linear(PropCost::Mod m, unsigned int n);
585  static PropCost linear(PropCost::Mod m, int n);
587  static PropCost ternary(PropCost::Mod m);
589  static PropCost binary(PropCost::Mod m);
591  static PropCost unary(PropCost::Mod m);
592  };
593 
594 
608  AP_DISPOSE = (1 << 0),
614  AP_WEAKLY = (1 << 1)
615  };
616 
617 
625  class ActorLink {
626  friend class Actor;
627  friend class Propagator;
628  friend class Advisor;
629  friend class Brancher;
630  friend class LocalObject;
631  friend class Space;
632  template<class VIC> friend class VarImp;
633  private:
634  ActorLink* _next; ActorLink* _prev;
635  public:
637 
638  ActorLink* prev(void) const; void prev(ActorLink*);
639  ActorLink* next(void) const; void next(ActorLink*);
640  ActorLink** next_ref(void);
642 
644  void init(void);
646  void unlink(void);
648  void head(ActorLink* al);
650  void tail(ActorLink* al);
652  bool empty(void) const;
654  template<class T> static ActorLink* cast(T* a);
656  template<class T> static const ActorLink* cast(const T* a);
657  };
658 
659 
665  friend class ActorLink;
666  friend class Space;
667  friend class Propagator;
668  friend class Advisor;
669  friend class Brancher;
670  friend class LocalObject;
671  template<class VIC> friend class VarImp;
672  template<class A> friend class Council;
673  private:
675  static Actor* cast(ActorLink* al);
677  static const Actor* cast(const ActorLink* al);
679  GECODE_KERNEL_EXPORT static Actor* sentinel;
680  public:
682  virtual Actor* copy(Space& home, bool share) = 0;
683 
685 
686 
688  virtual size_t allocated(void) const;
691  virtual size_t dispose(Space& home);
693  static void* operator new(size_t s, Space& home);
695  static void operator delete(void* p, Space& home);
696  private:
697 #ifndef __GNUC__
698 
699  static void operator delete(void* p);
700 #endif
701 
702  static void* operator new(size_t s);
704 #ifdef __GNUC__
705  public:
707  GECODE_KERNEL_EXPORT virtual ~Actor(void);
709  static void operator delete(void* p);
710 #endif
711  };
712 
713 
714 
718  class Home {
719  protected:
724  public:
726 
727 
728  Home(Space& s, Propagator* p=NULL);
730  Home& operator =(const Home& h);
732  operator Space&(void);
734 
735 
736 
739  Propagator* propagator(void) const;
741 
742 
743 
744  bool failed(void) const;
746  void fail(void);
748  void notice(Actor& a, ActorProperty p);
750  };
751 
757  friend class ActorLink;
758  friend class Space;
759  template<class VIC> friend class VarImp;
760  friend class Advisor;
761  template<class A> friend class Council;
762  private:
763  union {
767  size_t size;
770  } u;
772  GlobalAFC::Counter& gafc;
774  static Propagator* cast(ActorLink* al);
776  static const Propagator* cast(const ActorLink* al);
777  protected:
779  Propagator(Home home);
781  Propagator(Space& home, bool share, Propagator& p);
782 
783  public:
785 
786 
809  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
811  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
819  ModEventDelta modeventdelta(void) const;
856  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
858 
859 
860 
861  double afc(const Space& home) const;
863  };
864 
865 
873  template<class A>
874  class Council {
875  friend class Advisor;
876  friend class Advisors<A>;
877  private:
879  mutable ActorLink* advisors;
880  public:
882  Council(void);
884  Council(Space& home);
886  bool empty(void) const;
888  void update(Space& home, bool share, Council<A>& c);
890  void dispose(Space& home);
891  };
892 
893 
898  template<class A>
899  class Advisors {
900  private:
902  ActorLink* a;
903  public:
905  Advisors(const Council<A>& c);
907  bool operator ()(void) const;
909  void operator ++(void);
911  A& advisor(void) const;
912  };
913 
914 
925  class Advisor : private ActorLink {
926  template<class VIC> friend class VarImp;
927  template<class A> friend class Council;
928  template<class A> friend class Advisors;
929  private:
931  bool disposed(void) const;
933  static Advisor* cast(ActorLink* al);
935  static const Advisor* cast(const ActorLink* al);
936  protected:
938  Propagator& propagator(void) const;
939  public:
941  template<class A>
942  Advisor(Space& home, Propagator& p, Council<A>& c);
944  Advisor(Space& home, bool share, Advisor& a);
945 
947 
948 
949  template<class A>
950  void dispose(Space& home, Council<A>& c);
952  static void* operator new(size_t s, Space& home);
954  static void operator delete(void* p, Space& home);
956  private:
957 #ifndef __GNUC__
958 
959  static void operator delete(void* p);
960 #endif
961 
962  static void* operator new(size_t s);
963  };
964 
965 
976  friend class Space;
977  private:
978  unsigned int _id;
979  unsigned int _alt;
980 
982  unsigned int id(void) const;
983  protected:
985  Choice(const Brancher& b, const unsigned int a);
986  public:
988  unsigned int alternatives(void) const;
990  GECODE_KERNEL_EXPORT virtual ~Choice(void);
992  virtual size_t size(void) const = 0;
994  static void* operator new(size_t);
996  static void operator delete(void*);
998  GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
999  };
1000 
1011  friend class ActorLink;
1012  friend class Space;
1013  friend class Choice;
1014  private:
1016  unsigned int _id;
1018  static Brancher* cast(ActorLink* al);
1020  static const Brancher* cast(const ActorLink* al);
1021  protected:
1023  Brancher(Home home);
1025  Brancher(Space& home, bool share, Brancher& b);
1026  public:
1028 
1029 
1037  virtual bool status(const Space& home) const = 0;
1045  virtual const Choice* choice(Space& home) = 0;
1047  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1054  virtual ExecStatus commit(Space& home, const Choice& c,
1055  unsigned int a) = 0;
1057  unsigned int id(void) const;
1059  };
1060 
1070  private:
1072  unsigned int _id;
1073  public:
1075  BrancherHandle(void);
1077  BrancherHandle(const Brancher& b);
1079  void update(Space& home, bool share, BrancherHandle& bh);
1081  unsigned int id(void) const;
1083  bool operator ()(const Space& home) const;
1085  void kill(Space& home);
1086  };
1087 
1095  class LocalObject : public Actor {
1096  friend class ActorLink;
1097  friend class Space;
1098  friend class LocalHandle;
1099  protected:
1101  LocalObject(Home home);
1103  LocalObject(Space& home, bool share, LocalObject& l);
1105  static LocalObject* cast(ActorLink* al);
1107  static const LocalObject* cast(const ActorLink* al);
1108  private:
1110  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1111  public:
1113  LocalObject* fwd(Space& home, bool share);
1114  };
1115 
1122  class LocalHandle {
1123  private:
1125  LocalObject* o;
1126  protected:
1128  LocalHandle(void);
1130  LocalHandle(LocalObject* lo);
1132  LocalHandle(const LocalHandle& lh);
1133  public:
1135  LocalHandle& operator =(const LocalHandle& lh);
1137  void update(Space& home, bool share, LocalHandle& lh);
1139  ~LocalHandle(void);
1140  protected:
1142  LocalObject* object(void) const;
1144  void object(LocalObject* n);
1145  };
1146 
1147 
1156  };
1157 
1163  public:
1165  unsigned long int propagate;
1167  bool wmp;
1169  StatusStatistics(void);
1171  void reset(void);
1176  };
1177 
1183  public:
1185  CloneStatistics(void);
1187  void reset(void);
1192  };
1193 
1199  public:
1201  CommitStatistics(void);
1203  void reset(void);
1208  };
1209 
1210 
1215  friend class Actor;
1216  friend class Propagator;
1217  friend class Brancher;
1218  friend class Advisor;
1219  template<class VIC> friend class VarImp;
1220  template<class VarImp> friend class VarImpDisposer;
1221  friend class SharedHandle;
1222  friend class LocalObject;
1223  friend class Region;
1224  friend class AFC;
1225  friend class BrancherHandle;
1226  private:
1228  SharedMemory* sm;
1230  MemoryManager mm;
1232  GlobalAFC gafc;
1234  ActorLink pl;
1236  ActorLink bl;
1242  Brancher* b_status;
1254  Brancher* b_commit;
1256  Brancher* brancher(unsigned int id);
1259  void kill_brancher(unsigned int id);
1261  static const unsigned reserved_branch_id = 0U;
1262  union {
1264  struct {
1281  unsigned int branch_id;
1283  unsigned int n_sub;
1284  } p;
1286  struct {
1295  } c;
1296  } pc;
1298  void enqueue(Propagator* p);
1303 #ifdef GECODE_HAS_VAR_DISPOSE
1304 
1305  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1307  VarImpBase* _vars_d[AllVarConf::idx_d];
1309  template<class VIC> VarImpBase* vars_d(void) const;
1311  template<class VIC> void vars_d(VarImpBase* x);
1312 #endif
1313 
1314  void update(ActorLink** sub);
1316 
1318  Actor** d_fst;
1320  Actor** d_cur;
1322  Actor** d_lst;
1324  GECODE_KERNEL_EXPORT void d_resize(void);
1325 
1337  unsigned int _wmp_afc;
1339  void afc_enable(void);
1341  bool afc_enabled(void) const;
1343  void wmp(unsigned int n);
1345  unsigned int wmp(void) const;
1346 
1348  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1350  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1352  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1353 
1372  GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
1373 
1407  void _commit(const Choice& c, unsigned int a);
1408 
1411  void afc_decay(double d);
1413  double afc_decay(void) const;
1414  public:
1419  GECODE_KERNEL_EXPORT Space(void);
1424  GECODE_KERNEL_EXPORT virtual ~Space(void);
1435  GECODE_KERNEL_EXPORT Space(bool share, Space& s);
1442  virtual Space* copy(bool share) = 0;
1453  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
1467  virtual void master(unsigned long int i, const Space* s);
1481  virtual void slave(unsigned long int i, const Space* s);
1486  static void* operator new(size_t);
1491  static void operator delete(void*);
1492 
1493 
1494  /*
1495  * Member functions for search engines
1496  *
1497  */
1498 
1511  SpaceStatus status(StatusStatistics& stat=unused_status);
1512 
1545  const Choice* choice(void);
1546 
1557  const Choice* choice(Archive& e) const;
1558 
1579  Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
1580 
1615  void commit(const Choice& c, unsigned int a,
1616  CommitStatistics& stat=unused_commit);
1617 
1625  void notice(Actor& a, ActorProperty p);
1633  void ignore(Actor& a, ActorProperty p);
1634 
1635 
1646  ExecStatus ES_SUBSUMED(Propagator& p);
1661  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
1672  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1683  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1684 
1695  template<class A>
1696  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
1707  template<class A>
1708  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
1720  template<class A>
1721  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
1722 
1730  void fail(void);
1739  bool failed(void) const;
1744  bool stable(void) const;
1751  GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
1758  GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
1759 
1761 
1762 
1763  Home operator ()(Propagator& p);
1765 
1777  template<class T>
1778  T* alloc(long unsigned int n);
1785  template<class T>
1786  T* alloc(long int n);
1793  template<class T>
1794  T* alloc(unsigned int n);
1801  template<class T>
1802  T* alloc(int n);
1812  template<class T>
1813  void free(T* b, long unsigned int n);
1823  template<class T>
1824  void free(T* b, long int n);
1834  template<class T>
1835  void free(T* b, unsigned int n);
1845  template<class T>
1846  void free(T* b, int n);
1858  template<class T>
1859  T* realloc(T* b, long unsigned int n, long unsigned int m);
1871  template<class T>
1872  T* realloc(T* b, long int n, long int m);
1884  template<class T>
1885  T* realloc(T* b, unsigned int n, unsigned int m);
1897  template<class T>
1898  T* realloc(T* b, int n, int m);
1906  template<class T>
1907  T** realloc(T** b, long unsigned int n, long unsigned int m);
1915  template<class T>
1916  T** realloc(T** b, long int n, long int m);
1924  template<class T>
1925  T** realloc(T** b, unsigned int n, unsigned int m);
1933  template<class T>
1934  T** realloc(T** b, int n, int m);
1936  void* ralloc(size_t s);
1938  void rfree(void* p, size_t s);
1940  void* rrealloc(void* b, size_t n, size_t m);
1942  template<size_t> void* fl_alloc(void);
1948  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
1955  size_t allocated(void) const;
1964  GECODE_KERNEL_EXPORT void flush(void);
1966 
1967 
1968 
1971  template<class T>
1972  T& construct(void);
1978  template<class T, typename A1>
1979  T& construct(A1 const& a1);
1985  template<class T, typename A1, typename A2>
1986  T& construct(A1 const& a1, A2 const& a2);
1992  template<class T, typename A1, typename A2, typename A3>
1993  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
1999  template<class T, typename A1, typename A2, typename A3, typename A4>
2000  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2006  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2007  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2009 
2015  class Propagators {
2016  private:
2018  const Space& home;
2020  const ActorLink* q;
2022  const ActorLink* c;
2024  const ActorLink* e;
2025  public:
2027  Propagators(const Space& home);
2029  bool operator ()(void) const;
2031  void operator ++(void);
2033  const Propagator& propagator(void) const;
2034  };
2035 
2041  class Branchers {
2042  private:
2044  const ActorLink* c;
2046  const ActorLink* e;
2047  public:
2049  Branchers(const Space& home);
2051  bool operator ()(void) const;
2053  void operator ++(void);
2055  const Brancher& brancher(void) const;
2056  };
2057  };
2058 
2059 
2060 
2061 
2062  /*
2063  * Memory management
2064  *
2065  */
2066 
2067  // Heap allocated
2068  forceinline void*
2069  SharedHandle::Object::operator new(size_t s) {
2070  return heap.ralloc(s);
2071  }
2072  forceinline void
2073  SharedHandle::Object::operator delete(void* p) {
2074  heap.rfree(p);
2075  }
2076 
2077  forceinline void*
2078  Space::operator new(size_t s) {
2079  return heap.ralloc(s);
2080  }
2081  forceinline void
2082  Space::operator delete(void* p) {
2083  heap.rfree(p);
2084  }
2085 
2086  forceinline void
2087  Choice::operator delete(void* p) {
2088  heap.rfree(p);
2089  }
2090  forceinline void*
2091  Choice::operator new(size_t s) {
2092  return heap.ralloc(s);
2093  }
2094 
2095  // Space allocation: general space heaps and free lists
2096  forceinline void*
2097  Space::ralloc(size_t s) {
2098  return mm.alloc(sm,s);
2099  }
2100  forceinline void
2101  Space::rfree(void* p, size_t s) {
2102  return mm.reuse(p,s);
2103  }
2104  forceinline void*
2105  Space::rrealloc(void* _b, size_t n, size_t m) {
2106  char* b = static_cast<char*>(_b);
2107  if (n < m) {
2108  char* p = static_cast<char*>(ralloc(m));
2109  memcpy(p,b,n);
2110  rfree(b,n);
2111  return p;
2112  } else {
2113  rfree(b+m,m-n);
2114  return b;
2115  }
2116  }
2117 
2118  template<size_t s>
2119  forceinline void*
2121  return mm.template fl_alloc<s>(sm);
2122  }
2123  template<size_t s>
2124  forceinline void
2126  mm.template fl_dispose<s>(f,l);
2127  }
2128 
2129  forceinline size_t
2130  Space::allocated(void) const {
2131  size_t s = mm.allocated();
2132  for (Actor** a = d_fst; a < d_cur; a++)
2133  s += (*a)->allocated();
2134  return s;
2135  }
2136 
2137  /*
2138  * Typed allocation routines
2139  *
2140  */
2141  template<class T>
2142  forceinline T*
2143  Space::alloc(long unsigned int n) {
2144  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2145  for (long unsigned int i=n; i--; )
2146  (void) new (p+i) T();
2147  return p;
2148  }
2149  template<class T>
2150  forceinline T*
2151  Space::alloc(long int n) {
2152  assert(n >= 0);
2153  return alloc<T>(static_cast<long unsigned int>(n));
2154  }
2155  template<class T>
2156  forceinline T*
2157  Space::alloc(unsigned int n) {
2158  return alloc<T>(static_cast<long unsigned int>(n));
2159  }
2160  template<class T>
2161  forceinline T*
2163  assert(n >= 0);
2164  return alloc<T>(static_cast<long unsigned int>(n));
2165  }
2166 
2167  template<class T>
2168  forceinline void
2169  Space::free(T* b, long unsigned int n) {
2170  for (long unsigned int i=n; i--; )
2171  b[i].~T();
2172  rfree(b,n*sizeof(T));
2173  }
2174  template<class T>
2175  forceinline void
2176  Space::free(T* b, long int n) {
2177  assert(n >= 0);
2178  free<T>(b,static_cast<long unsigned int>(n));
2179  }
2180  template<class T>
2181  forceinline void
2182  Space::free(T* b, unsigned int n) {
2183  free<T>(b,static_cast<long unsigned int>(n));
2184  }
2185  template<class T>
2186  forceinline void
2187  Space::free(T* b, int n) {
2188  assert(n >= 0);
2189  free<T>(b,static_cast<long unsigned int>(n));
2190  }
2191 
2192  template<class T>
2193  forceinline T*
2194  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2195  if (n < m) {
2196  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2197  for (long unsigned int i=n; i--; )
2198  (void) new (p+i) T(b[i]);
2199  for (long unsigned int i=n; i<m; i++)
2200  (void) new (p+i) T();
2201  free<T>(b,n);
2202  return p;
2203  } else {
2204  free<T>(b+m,m-n);
2205  return b;
2206  }
2207  }
2208  template<class T>
2209  forceinline T*
2210  Space::realloc(T* b, long int n, long int m) {
2211  assert((n >= 0) && (m >= 0));
2212  return realloc<T>(b,static_cast<long unsigned int>(n),
2213  static_cast<long unsigned int>(m));
2214  }
2215  template<class T>
2216  forceinline T*
2217  Space::realloc(T* b, unsigned int n, unsigned int m) {
2218  return realloc<T>(b,static_cast<long unsigned int>(n),
2219  static_cast<long unsigned int>(m));
2220  }
2221  template<class T>
2222  forceinline T*
2223  Space::realloc(T* b, int n, int m) {
2224  assert((n >= 0) && (m >= 0));
2225  return realloc<T>(b,static_cast<long unsigned int>(n),
2226  static_cast<long unsigned int>(m));
2227  }
2228 
2229 #define GECODE_KERNEL_REALLOC(T) \
2230  template<> \
2231  forceinline T* \
2232  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2233  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2234  } \
2235  template<> \
2236  forceinline T* \
2237  Space::realloc<T>(T* b, long int n, long int m) { \
2238  assert((n >= 0) && (m >= 0)); \
2239  return realloc<T>(b,static_cast<long unsigned int>(n), \
2240  static_cast<long unsigned int>(m)); \
2241  } \
2242  template<> \
2243  forceinline T* \
2244  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2245  return realloc<T>(b,static_cast<long unsigned int>(n), \
2246  static_cast<long unsigned int>(m)); \
2247  } \
2248  template<> \
2249  forceinline T* \
2250  Space::realloc<T>(T* b, int n, int m) { \
2251  assert((n >= 0) && (m >= 0)); \
2252  return realloc<T>(b,static_cast<long unsigned int>(n), \
2253  static_cast<long unsigned int>(m)); \
2254  }
2255 
2256  GECODE_KERNEL_REALLOC(bool)
2257  GECODE_KERNEL_REALLOC(signed char)
2258  GECODE_KERNEL_REALLOC(unsigned char)
2259  GECODE_KERNEL_REALLOC(signed short int)
2260  GECODE_KERNEL_REALLOC(unsigned short int)
2261  GECODE_KERNEL_REALLOC(signed int)
2262  GECODE_KERNEL_REALLOC(unsigned int)
2263  GECODE_KERNEL_REALLOC(signed long int)
2264  GECODE_KERNEL_REALLOC(unsigned long int)
2265  GECODE_KERNEL_REALLOC(float)
2266  GECODE_KERNEL_REALLOC(double)
2267 
2268 #undef GECODE_KERNEL_REALLOC
2269 
2270  template<class T>
2271  forceinline T**
2272  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2273  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2274  }
2275  template<class T>
2276  forceinline T**
2277  Space::realloc(T** b, long int n, long int m) {
2278  assert((n >= 0) && (m >= 0));
2279  return realloc<T*>(b,static_cast<long unsigned int>(n),
2280  static_cast<long unsigned int>(m));
2281  }
2282  template<class T>
2283  forceinline T**
2284  Space::realloc(T** b, unsigned int n, unsigned int m) {
2285  return realloc<T*>(b,static_cast<long unsigned int>(n),
2286  static_cast<long unsigned int>(m));
2287  }
2288  template<class T>
2289  forceinline T**
2290  Space::realloc(T** b, int n, int m) {
2291  assert((n >= 0) && (m >= 0));
2292  return realloc<T*>(b,static_cast<long unsigned int>(n),
2293  static_cast<long unsigned int>(m));
2294  }
2295 
2296 
2297 #ifdef GECODE_HAS_VAR_DISPOSE
2298  template<class VIC>
2300  Space::vars_d(void) const {
2301  return _vars_d[VIC::idx_d];
2302  }
2303  template<class VIC>
2304  forceinline void
2305  Space::vars_d(VarImpBase* x) {
2306  _vars_d[VIC::idx_d] = x;
2307  }
2308 #endif
2309 
2310  // Space allocated entities: Actors, variable implementations, and advisors
2311  forceinline void
2312  Actor::operator delete(void*) {}
2313  forceinline void
2314  Actor::operator delete(void*, Space&) {}
2315  forceinline void*
2316  Actor::operator new(size_t s, Space& home) {
2317  return home.ralloc(s);
2318  }
2319 
2320  template<class VIC>
2321  forceinline void
2322  VarImp<VIC>::operator delete(void*) {}
2323  template<class VIC>
2324  forceinline void
2325  VarImp<VIC>::operator delete(void*, Space&) {}
2326  template<class VIC>
2327  forceinline void*
2328  VarImp<VIC>::operator new(size_t s, Space& home) {
2329  return home.ralloc(s);
2330  }
2331 
2332 #ifndef __GNUC__
2333  forceinline void
2334  Advisor::operator delete(void*) {}
2335 #endif
2336  forceinline void
2337  Advisor::operator delete(void*, Space&) {}
2338  forceinline void*
2339  Advisor::operator new(size_t s, Space& home) {
2340  return home.ralloc(s);
2341  }
2342 
2343  /*
2344  * Shared objects and handles
2345  *
2346  */
2347  forceinline
2349  : next(NULL), fwd(NULL), use_cnt(0) {}
2350  forceinline
2352  assert(use_cnt == 0);
2353  }
2354 
2356  SharedHandle::object(void) const {
2357  return o;
2358  }
2359  forceinline void
2360  SharedHandle::subscribe(void) {
2361  if (o != NULL) o->use_cnt++;
2362  }
2363  forceinline void
2364  SharedHandle::cancel(void) {
2365  if ((o != NULL) && (--o->use_cnt == 0))
2366  delete o;
2367  o=NULL;
2368  }
2369  forceinline void
2371  if (n != o) {
2372  cancel(); o=n; subscribe();
2373  }
2374  }
2375  forceinline
2376  SharedHandle::SharedHandle(void) : o(NULL) {}
2377  forceinline
2379  subscribe();
2380  }
2381  forceinline
2383  subscribe();
2384  }
2387  if (&sh != this) {
2388  cancel(); o=sh.o; subscribe();
2389  }
2390  return *this;
2391  }
2392  forceinline void
2393  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
2394  if (sh.o == NULL) {
2395  o=NULL; return;
2396  } else if (share) {
2397  o=sh.o;
2398  } else if (sh.o->fwd != NULL) {
2399  o=sh.o->fwd;
2400  } else {
2401  o = sh.o->copy();
2402  sh.o->fwd = o;
2403  sh.o->next = home.pc.c.shared;
2404  home.pc.c.shared = sh.o;
2405  }
2406  subscribe();
2407  }
2408  forceinline
2410  cancel();
2411  }
2412 
2413 
2414 
2415  /*
2416  * ActorLink
2417  *
2418  */
2420  ActorLink::prev(void) const {
2421  return _prev;
2422  }
2423 
2425  ActorLink::next(void) const {
2426  return _next;
2427  }
2428 
2431  return &_next;
2432  }
2433 
2434  forceinline void
2436  _prev = al;
2437  }
2438 
2439  forceinline void
2441  _next = al;
2442  }
2443 
2444  forceinline void
2446  ActorLink* p = _prev; ActorLink* n = _next;
2447  p->_next = n; n->_prev = p;
2448  }
2449 
2450  forceinline void
2452  _next = this; _prev =this;
2453  }
2454 
2455  forceinline void
2457  // Inserts al at head of link-chain (that is, after this)
2458  ActorLink* n = _next;
2459  this->_next = a; a->_prev = this;
2460  a->_next = n; n->_prev = a;
2461  }
2462 
2463  forceinline void
2465  // Inserts al at tail of link-chain (that is, before this)
2466  ActorLink* p = _prev;
2467  a->_next = this; this->_prev = a;
2468  p->_next = a; a->_prev = p;
2469  }
2470 
2471  forceinline bool
2472  ActorLink::empty(void) const {
2473  return _next == this;
2474  }
2475 
2476  template<class T>
2479  // Turning al into a reference is for gcc, assume is for MSVC
2480  GECODE_NOT_NULL(a);
2481  ActorLink& t = *a;
2482  return static_cast<ActorLink*>(&t);
2483  }
2484 
2485  template<class T>
2486  forceinline const ActorLink*
2487  ActorLink::cast(const T* a) {
2488  // Turning al into a reference is for gcc, assume is for MSVC
2489  GECODE_NOT_NULL(a);
2490  const ActorLink& t = *a;
2491  return static_cast<const ActorLink*>(&t);
2492  }
2493 
2494 
2495  /*
2496  * Actor
2497  *
2498  */
2500  Actor::cast(ActorLink* al) {
2501  // Turning al into a reference is for gcc, assume is for MSVC
2502  GECODE_NOT_NULL(al);
2503  ActorLink& t = *al;
2504  return static_cast<Actor*>(&t);
2505  }
2506 
2507  forceinline const Actor*
2508  Actor::cast(const ActorLink* al) {
2509  // Turning al into a reference is for gcc, assume is for MSVC
2510  GECODE_NOT_NULL(al);
2511  const ActorLink& t = *al;
2512  return static_cast<const Actor*>(&t);
2513  }
2514 
2515  forceinline void
2516  Space::afc_enable(void) {
2517  _wmp_afc |= 1U;
2518  }
2519  forceinline bool
2520  Space::afc_enabled(void) const {
2521  return (_wmp_afc & 1U) != 0U;
2522  }
2523  forceinline void
2524  Space::wmp(unsigned int n) {
2525  _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2526  }
2527  forceinline unsigned int
2528  Space::wmp(void) const {
2529  return _wmp_afc >> 1U;
2530  }
2531 
2532  forceinline void
2534  if (p & AP_DISPOSE) {
2535  if (d_cur == d_lst)
2536  d_resize();
2537  *(d_cur++) = &a;
2538  }
2539  if (p & AP_WEAKLY) {
2540  if (wmp() == 0)
2541  wmp(2);
2542  else
2543  wmp(wmp()+1);
2544  }
2545  }
2546 
2547  forceinline void
2549  s.notice(a,p);
2550  }
2551 
2552  forceinline void
2554  if (p & AP_DISPOSE) {
2555  // Check wether array has already been discarded as space
2556  // deletion is already in progress
2557  Actor** f = d_fst;
2558  if (f != NULL) {
2559  while (&a != *f)
2560  f++;
2561  *f = *(--d_cur);
2562  }
2563  }
2564  if (p & AP_WEAKLY) {
2565  assert(wmp() > 1U);
2566  wmp(wmp()-1);
2567  }
2568  }
2569 
2571  Space::clone(bool share, CloneStatistics&) const {
2572  // Clone is only const for search engines. During cloning, several data
2573  // structures are updated (e.g. forwarding pointers), so we have to
2574  // cast away the constness.
2575  return const_cast<Space*>(this)->_clone(share);
2576  }
2577 
2578  forceinline void
2579  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
2580  _commit(c,a);
2581  }
2582 
2583  forceinline double
2584  Space::afc_decay(void) const {
2585  return gafc.decay();
2586  }
2587 
2588  forceinline size_t
2590  return sizeof(*this);
2591  }
2592 
2593 
2594  /*
2595  * Home for posting actors
2596  *
2597  */
2598  forceinline
2599  Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
2600  forceinline Home&
2602  s=h.s; p=h.p;
2603  return *this;
2604  }
2605  forceinline
2606  Home::operator Space&(void) {
2607  return s;
2608  }
2611  return Home(s,&p);
2612  }
2615  return Home(*this,&p);
2616  }
2618  Home::propagator(void) const {
2619  return p;
2620  }
2621 
2622  /*
2623  * Propagator
2624  *
2625  */
2627  Propagator::cast(ActorLink* al) {
2628  // Turning al into a reference is for gcc, assume is for MSVC
2629  GECODE_NOT_NULL(al);
2630  ActorLink& t = *al;
2631  return static_cast<Propagator*>(&t);
2632  }
2633 
2634  forceinline const Propagator*
2635  Propagator::cast(const ActorLink* al) {
2636  // Turning al into a reference is for gcc, assume is for MSVC
2637  GECODE_NOT_NULL(al);
2638  const ActorLink& t = *al;
2639  return static_cast<const Propagator*>(&t);
2640  }
2641 
2642  forceinline
2644  : gafc((home.propagator() != NULL) ?
2645  // Inherit time counter information
2646  home.propagator()->gafc :
2647  // New propagator information
2648  static_cast<Space&>(home).gafc.allocate()) {
2649  u.advisors = NULL;
2650  assert((u.med == 0) && (u.size == 0));
2651  static_cast<Space&>(home).pl.head(this);
2652  }
2653 
2654  forceinline
2656  : gafc(p.gafc) {
2657  u.advisors = NULL;
2658  assert((u.med == 0) && (u.size == 0));
2659  // Set forwarding pointer
2660  p.prev(this);
2661  }
2662 
2665  return u.med;
2666  }
2667 
2668  forceinline double
2669  Propagator::afc(const Space& home) const {
2670  return const_cast<Space&>(home).gafc.afc(gafc);
2671  }
2672 
2675  p.u.size = s;
2676  return __ES_SUBSUMED;
2677  }
2678 
2681  p.u.size = p.dispose(*this);
2682  return __ES_SUBSUMED;
2683  }
2684 
2687  p.u.med = med;
2688  assert(p.u.med != 0);
2689  return __ES_PARTIAL;
2690  }
2691 
2694  p.u.med = AllVarConf::med_combine(p.u.med,med);
2695  assert(p.u.med != 0);
2696  return __ES_PARTIAL;
2697  }
2698 
2699 
2700 
2701  /*
2702  * Brancher
2703  *
2704  */
2706  Brancher::cast(ActorLink* al) {
2707  // Turning al into a reference is for gcc, assume is for MSVC
2708  GECODE_NOT_NULL(al);
2709  ActorLink& t = *al;
2710  return static_cast<Brancher*>(&t);
2711  }
2712 
2713  forceinline const Brancher*
2714  Brancher::cast(const ActorLink* al) {
2715  // Turning al into a reference is for gcc, assume is for MSVC
2716  GECODE_NOT_NULL(al);
2717  const ActorLink& t = *al;
2718  return static_cast<const Brancher*>(&t);
2719  }
2720 
2721  forceinline
2723  _id(static_cast<Space&>(home).pc.p.branch_id++) {
2724  if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2725  throw TooManyBranchers("Brancher::Brancher");
2726  // If no brancher available, make it the first one
2727  if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2728  static_cast<Space&>(home).b_status = this;
2729  if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
2730  static_cast<Space&>(home).b_commit = this;
2731  }
2732  static_cast<Space&>(home).bl.tail(this);
2733  }
2734 
2735  forceinline
2737  : _id(b._id) {
2738  // Set forwarding pointer
2739  b.prev(this);
2740  }
2741 
2742  forceinline unsigned int
2743  Brancher::id(void) const {
2744  return _id;
2745  }
2746 
2748  Space::brancher(unsigned int id) {
2749  /*
2750  * Due to weakly monotonic propagators the following scenario might
2751  * occur: a brancher has been committed with all its available
2752  * choices. Then, propagation determines less information
2753  * than before and the brancher now will create new choices.
2754  * Later, during recomputation, all of these choices
2755  * can be used together, possibly interleaved with
2756  * choices for other branchers. That means all branchers
2757  * must be scanned to find the matching brancher for the choice.
2758  *
2759  * b_commit tries to optimize scanning as it is most likely that
2760  * recomputation does not generate new choices during recomputation
2761  * and hence b_commit is moved from newer to older branchers.
2762  */
2763  Brancher* b_old = b_commit;
2764  // Try whether we are lucky
2765  while (b_commit != Brancher::cast(&bl))
2766  if (id != b_commit->id())
2767  b_commit = Brancher::cast(b_commit->next());
2768  else
2769  return b_commit;
2770  if (b_commit == Brancher::cast(&bl)) {
2771  // We did not find the brancher, start at the beginning
2772  b_commit = Brancher::cast(bl.next());
2773  while (b_commit != b_old)
2774  if (id != b_commit->id())
2775  b_commit = Brancher::cast(b_commit->next());
2776  else
2777  return b_commit;
2778  }
2779  return NULL;
2780  }
2781 
2782  /*
2783  * Brancher handle
2784  *
2785  */
2786  forceinline
2788  : _id(Space::reserved_branch_id) {}
2789  forceinline
2791  : _id(b.id()) {}
2792  forceinline void
2794  _id = bh._id;
2795  }
2796  forceinline unsigned int
2797  BrancherHandle::id(void) const {
2798  return _id;
2799  }
2800  forceinline bool
2801  BrancherHandle::operator ()(const Space& home) const {
2802  return const_cast<Space&>(home).brancher(_id) != NULL;
2803  }
2804  forceinline void
2806  home.kill_brancher(_id);
2807  }
2808 
2809 
2810  /*
2811  * Local objects
2812  *
2813  */
2814 
2817  // Turning al into a reference is for gcc, assume is for MSVC
2818  GECODE_NOT_NULL(al);
2819  ActorLink& t = *al;
2820  return static_cast<LocalObject*>(&t);
2821  }
2822 
2823  forceinline const LocalObject*
2825  // Turning al into a reference is for gcc, assume is for MSVC
2826  GECODE_NOT_NULL(al);
2827  const ActorLink& t = *al;
2828  return static_cast<const LocalObject*>(&t);
2829  }
2830 
2831  forceinline
2833  ActorLink::cast(this)->prev(NULL);
2834  }
2835 
2836  forceinline
2838  ActorLink::cast(this)->prev(NULL);
2839  }
2840 
2842  LocalObject::fwd(Space& home, bool share) {
2843  if (prev() == NULL)
2844  fwdcopy(home,share);
2845  return LocalObject::cast(prev());
2846  }
2847 
2848  forceinline
2849  LocalHandle::LocalHandle(void) : o(NULL) {}
2850  forceinline
2852  forceinline
2853  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
2856  o = lh.o;
2857  return *this;
2858  }
2859  forceinline
2862  LocalHandle::object(void) const { return o; }
2863  forceinline void
2865  forceinline void
2866  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
2867  object(lh.object()->fwd(home,share));
2868  }
2869 
2870 
2871  /*
2872  * Choices
2873  *
2874  */
2875  forceinline
2876  Choice::Choice(const Brancher& b, const unsigned int a)
2877  : _id(b.id()), _alt(a) {}
2878 
2879  forceinline unsigned int
2880  Choice::alternatives(void) const {
2881  return _alt;
2882  }
2883 
2884  forceinline unsigned int
2885  Choice::id(void) const {
2886  return _id;
2887  }
2888 
2889  forceinline
2891 
2892 
2893 
2894  /*
2895  * Advisor
2896  *
2897  */
2898  template<class A>
2899  forceinline
2901  // Store propagator and forwarding in prev()
2902  ActorLink::prev(&p);
2903  // Link to next advisor in next()
2904  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
2905  }
2906 
2907  forceinline
2909 
2910  forceinline bool
2911  Advisor::disposed(void) const {
2912  return prev() == NULL;
2913  }
2914 
2915  forceinline Advisor*
2916  Advisor::cast(ActorLink* al) {
2917  return static_cast<Advisor*>(al);
2918  }
2919 
2920  forceinline const Advisor*
2921  Advisor::cast(const ActorLink* al) {
2922  return static_cast<const Advisor*>(al);
2923  }
2924 
2925  forceinline Propagator&
2926  Advisor::propagator(void) const {
2927  assert(!disposed());
2928  return *Propagator::cast(ActorLink::prev());
2929  }
2930 
2931  template<class A>
2932  forceinline void
2934  assert(!disposed());
2935  ActorLink::prev(NULL);
2936  // Shorten chains of disposed advisors by one, if possible
2937  Advisor* n = Advisor::cast(next());
2938  if ((n != NULL) && n->disposed())
2939  next(n->next());
2940  }
2941 
2942  template<class A>
2945  a.dispose(*this,c);
2946  return ES_FIX;
2947  }
2948 
2949  template<class A>
2952  a.dispose(*this,c);
2953  return ES_NOFIX;
2954  }
2955 
2956  template<class A>
2959  a.dispose(*this,c);
2960  return ES_NOFIX_FORCE;
2961  }
2962 
2963 
2964 
2965  /*
2966  * Advisor council
2967  *
2968  */
2969  template<class A>
2970  forceinline
2972 
2973  template<class A>
2974  forceinline
2976  : advisors(NULL) {}
2977 
2978  template<class A>
2979  forceinline bool
2980  Council<A>::empty(void) const {
2981  ActorLink* a = advisors;
2982  while ((a != NULL) && static_cast<A*>(a)->disposed())
2983  a = a->next();
2984  advisors = a;
2985  return a == NULL;
2986  }
2987 
2988  template<class A>
2989  forceinline void
2990  Council<A>::update(Space& home, bool share, Council<A>& c) {
2991  // Skip all disposed advisors
2992  {
2993  ActorLink* a = c.advisors;
2994  while ((a != NULL) && static_cast<A*>(a)->disposed())
2995  a = a->next();
2996  c.advisors = a;
2997  }
2998  // Are there any advisors to be cloned?
2999  if (c.advisors != NULL) {
3000  // The propagator in from-space
3001  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3002  // The propagator in to-space
3003  Propagator* p_t = Propagator::cast(p_f->prev());
3004  // Advisors in from-space
3005  ActorLink** a_f = &c.advisors;
3006  // Advisors in to-space
3007  A* a_t = NULL;
3008  while (*a_f != NULL) {
3009  if (static_cast<A*>(*a_f)->disposed()) {
3010  *a_f = (*a_f)->next();
3011  } else {
3012  // Run specific copying part
3013  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
3014  // Set propagator pointer
3015  a->prev(p_t);
3016  // Set forwarding pointer
3017  (*a_f)->prev(a);
3018  // Link
3019  a->next(a_t);
3020  a_t = a;
3021  a_f = (*a_f)->next_ref();
3022  }
3023  }
3024  advisors = a_t;
3025  // Enter advisor link for reset
3026  assert(p_f->u.advisors == NULL);
3027  p_f->u.advisors = c.advisors;
3028  } else {
3029  advisors = NULL;
3030  }
3031  }
3032 
3033  template<class A>
3034  forceinline void
3036  ActorLink* a = advisors;
3037  while (a != NULL) {
3038  if (!static_cast<A*>(a)->disposed())
3039  static_cast<A*>(a)->dispose(home,*this);
3040  a = a->next();
3041  }
3042  }
3043 
3044 
3045 
3046  /*
3047  * Advisor iterator
3048  *
3049  */
3050  template<class A>
3051  forceinline
3053  : a(c.advisors) {
3054  while ((a != NULL) && static_cast<A*>(a)->disposed())
3055  a = a->next();
3056  }
3057 
3058  template<class A>
3059  forceinline bool
3061  return a != NULL;
3062  }
3063 
3064  template<class A>
3065  forceinline void
3067  do {
3068  a = a->next();
3069  } while ((a != NULL) && static_cast<A*>(a)->disposed());
3070  }
3071 
3072  template<class A>
3073  forceinline A&
3074  Advisors<A>::advisor(void) const {
3075  return *static_cast<A*>(a);
3076  }
3077 
3078 
3079 
3080  /*
3081  * Space
3082  *
3083  */
3084  forceinline void
3085  Space::enqueue(Propagator* p) {
3086  ActorLink::cast(p)->unlink();
3087  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
3088  c->tail(ActorLink::cast(p));
3089  if (c > pc.p.active)
3090  pc.p.active = c;
3091  }
3092 
3093  forceinline void
3094  Space::fail(void) {
3095  /*
3096  * Now active points beyond the last queue. This is essential as
3097  * enqueuing a propagator in a failed space keeps the space
3098  * failed.
3099  */
3100  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
3101  }
3102  forceinline void
3103  Home::fail(void) {
3104  s.fail();
3105  }
3106 
3107  forceinline bool
3108  Space::failed(void) const {
3109  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
3110  }
3111  forceinline bool
3112  Home::failed(void) const {
3113  return s.failed();
3114  }
3115 
3116  forceinline bool
3117  Space::stable(void) const {
3118  return ((pc.p.active < &pc.p.queue[0]) ||
3119  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
3120  }
3121 
3122 
3123 
3124  /*
3125  * Variable implementation
3126  *
3127  */
3128  template<class VIC>
3131  assert((pc >= 0) && (pc < pc_max+2));
3132  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
3133  }
3134 
3135  template<class VIC>
3136  forceinline ActorLink**
3137  VarImp<VIC>::actorNonZero(PropCond pc) {
3138  assert((pc > 0) && (pc < pc_max+2));
3139  return b.base+u.idx[pc-1];
3140  }
3141 
3142  template<class VIC>
3143  forceinline unsigned int&
3145  assert((pc > 0) && (pc < pc_max+2));
3146  return u.idx[pc-1];
3147  }
3148 
3149  template<class VIC>
3150  forceinline unsigned int
3151  VarImp<VIC>::idx(PropCond pc) const {
3152  assert((pc > 0) && (pc < pc_max+2));
3153  return u.idx[pc-1];
3154  }
3155 
3156  template<class VIC>
3157  forceinline
3159  b.base = NULL; entries = 0;
3160  for (PropCond pc=1; pc<pc_max+2; pc++)
3161  idx(pc) = 0;
3162  free_and_bits = 0;
3163  }
3164 
3165  template<class VIC>
3166  forceinline
3168  b.base = NULL; entries = 0;
3169  for (PropCond pc=1; pc<pc_max+2; pc++)
3170  idx(pc) = 0;
3171  free_and_bits = 0;
3172  }
3173 
3174  template<class VIC>
3175  forceinline unsigned int
3176  VarImp<VIC>::degree(void) const {
3177  assert(!copied());
3178  return entries;
3179  }
3180 
3181  template<class VIC>
3182  forceinline double
3183  VarImp<VIC>::afc(const Space& home) const {
3184  double d = 0.0;
3185  // Count the afc of each propagator
3186  {
3187  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
3188  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3189  while (a < e) {
3190  d += Propagator::cast(*a)->afc(home); a++;
3191  }
3192  }
3193  // Count the afc of each advisor's propagator
3194  {
3195  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3196  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
3197  while (a < e) {
3198  d += Advisor::cast(*a)->propagator().afc(home); a++;
3199  }
3200  }
3201  return d;
3202  }
3203 
3204  template<class VIC>
3207  return d.me;
3208  }
3209 
3210  template<class VIC>
3211  forceinline unsigned int
3212  VarImp<VIC>::bits(void) const {
3213  return free_and_bits;
3214  }
3215 
3216  template<class VIC>
3217  forceinline unsigned int&
3219  return free_and_bits;
3220  }
3221 
3222 #ifdef GECODE_HAS_VAR_DISPOSE
3223  template<class VIC>
3225  VarImp<VIC>::vars_d(Space& home) {
3226  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
3227  }
3228 
3229  template<class VIC>
3230  forceinline void
3231  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
3232  home.vars_d<VIC>(x);
3233  }
3234 #endif
3235 
3236  template<class VIC>
3237  forceinline bool
3238  VarImp<VIC>::copied(void) const {
3239  return Support::marked(b.fwd);
3240  }
3241 
3242  template<class VIC>
3244  VarImp<VIC>::forward(void) const {
3245  assert(copied());
3246  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
3247  }
3248 
3249  template<class VIC>
3251  VarImp<VIC>::next(void) const {
3252  assert(copied());
3253  return u.next;
3254  }
3255 
3256  template<class VIC>
3257  forceinline
3259  VarImpBase** reg;
3260  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3261  if (x.b.base == NULL) {
3262  // Variable implementation needs no index structure
3263  reg = &home.pc.c.vars_noidx;
3264  assert(x.degree() == 0);
3265  } else {
3266  reg = &home.pc.c.vars_u[idx_c];
3267  }
3268  // Save subscriptions in copy
3269  b.base = x.b.base;
3270  entries = x.entries;
3271  for (PropCond pc=1; pc<pc_max+2; pc++)
3272  idx(pc) = x.idx(pc);
3273 
3274  // Set forwarding pointer
3275  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
3276  // Register original
3277  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
3278  }
3279 
3280  template<class VIC>
3283  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3284  }
3285 
3286  template<class VIC>
3289  return static_cast<ModEventDelta>(me << VIC::med_fst);
3290  }
3291 
3292  template<class VIC>
3295  return VIC::me_combine(me1,me2);
3296  }
3297 
3298  template<class VIC>
3299  forceinline void
3301  bool force) {
3302  if (VIC::med_update(p.u.med,me) || force)
3303  home.enqueue(&p);
3304  }
3305 
3306  template<class VIC>
3307  forceinline void
3309  ActorLink** b = actor(pc1);
3310  ActorLink** p = actorNonZero(pc2+1);
3311  while (p-- > b)
3312  schedule(home,*Propagator::cast(*p),me);
3313  }
3314 
3315  template<class VIC>
3316  forceinline void
3317  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
3318  assert(pc <= pc_max);
3319  // Count one new subscription
3320  home.pc.p.n_sub += 1;
3321  if ((free_and_bits >> free_bits) == 0)
3322  resize(home);
3323  free_and_bits -= 1 << free_bits;
3324 
3325  // Enter subscription
3326  b.base[entries] = *actorNonZero(pc_max+1);
3327  entries++;
3328  for (PropCond j = pc_max; j > pc; j--) {
3329  *actorNonZero(j+1) = *actorNonZero(j);
3330  idx(j+1)++;
3331  }
3332  *actorNonZero(pc+1) = *actor(pc);
3333  idx(pc+1)++;
3334  *actor(pc) = ActorLink::cast(p);
3335 
3336 #ifdef GECODE_AUDIT
3337  ActorLink** f = actor(pc);
3338  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
3339  if (*f == p)
3340  goto found;
3341  else
3342  f++;
3343  GECODE_NEVER;
3344  found: ;
3345 #endif
3346  }
3347 
3348  template<class VIC>
3349  forceinline void
3350  VarImp<VIC>::enter(Space& home, Advisor* a) {
3351  // Count one new subscription
3352  home.pc.p.n_sub += 1;
3353  if ((free_and_bits >> free_bits) == 0)
3354  resize(home);
3355  free_and_bits -= 1 << free_bits;
3356 
3357  // Enter subscription
3358  b.base[entries++] = *actorNonZero(pc_max+1);
3359  *actorNonZero(pc_max+1) = a;
3360  }
3361 
3362  template<class VIC>
3363  void
3364  VarImp<VIC>::resize(Space& home) {
3365  if (b.base == NULL) {
3366  assert((free_and_bits >> free_bits) == 0);
3367  // Create fresh dependency array with four entries
3368  free_and_bits += 4 << free_bits;
3369  b.base = home.alloc<ActorLink*>(4);
3370  for (int i=0; i<pc_max+1; i++)
3371  u.idx[i] = 0;
3372  } else {
3373  // Resize dependency array
3374  unsigned int n = degree();
3375  // Find out whether the area is most likely in the special area
3376  // reserved for subscriptions. If yes, just resize mildly otherwise
3377  // more agressively
3378  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
3379  unsigned int m =
3380  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
3381  (n+4) : ((n+1)*3>>1);
3382  ActorLink** prop = home.alloc<ActorLink*>(m);
3383  free_and_bits += (m-n) << free_bits;
3384  // Copy entries
3385  Heap::copy<ActorLink*>(prop, b.base, n);
3386  home.free<ActorLink*>(b.base,n);
3387  b.base = prop;
3388  }
3389  }
3390 
3391  template<class VIC>
3392  void
3394  bool assigned, ModEvent me, bool schedule) {
3395  if (assigned) {
3396  // Do not subscribe, just schedule the propagator
3397  if (schedule)
3399  } else {
3400  enter(home,&p,pc);
3401  // Schedule propagator
3402  if (schedule && (pc != PC_GEN_ASSIGNED))
3403  VarImp<VIC>::schedule(home,p,me);
3404  }
3405  }
3406 
3407  template<class VIC>
3408  forceinline void
3410  if (!assigned)
3411  enter(home,&a);
3412  }
3413 
3414  template<class VIC>
3415  forceinline void
3416  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
3417  assert(pc <= pc_max);
3418  ActorLink* a = ActorLink::cast(p);
3419  // Find actor in dependency array
3420  ActorLink** f = actor(pc);
3421 #ifdef GECODE_AUDIT
3422  while (f < actorNonZero(pc+1))
3423  if (*f == a)
3424  goto found;
3425  else
3426  f++;
3427  GECODE_NEVER;
3428  found: ;
3429 #else
3430  while (*f != a) f++;
3431 #endif
3432  // Remove actor
3433  *f = *(actorNonZero(pc+1)-1);
3434  for (PropCond j = pc+1; j< pc_max+1; j++) {
3435  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3436  idx(j)--;
3437  }
3438  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
3439  idx(pc_max+1)--;
3440  entries--;
3441  free_and_bits += 1 << free_bits;
3442  home.pc.p.n_sub -= 1;
3443  }
3444 
3445  template<class VIC>
3446  forceinline void
3447  VarImp<VIC>::remove(Space& home, Advisor* a) {
3448  // Find actor in dependency array
3449  ActorLink** f = actorNonZero(pc_max+1);
3450 #ifdef GECODE_AUDIT
3451  while (f < b.base+entries)
3452  if (*f == a)
3453  goto found;
3454  else
3455  f++;
3456  GECODE_NEVER;
3457  found: ;
3458 #else
3459  while (*f != a) f++;
3460 #endif
3461  // Remove actor
3462  *f = b.base[--entries];
3463  free_and_bits += 1 << free_bits;
3464  home.pc.p.n_sub -= 1;
3465  }
3466 
3467  template<class VIC>
3468  forceinline void
3470  if (!assigned)
3471  remove(home,&p,pc);
3472  }
3473 
3474  template<class VIC>
3475  forceinline void
3477  if (!assigned)
3478  remove(home,&a);
3479  }
3480 
3481  template<class VIC>
3482  forceinline void
3484  unsigned int n_sub = degree();
3485  home.pc.p.n_sub -= n_sub;
3486  unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3487  home.free<ActorLink*>(b.base,n);
3488  // Must be NULL such that cloning works
3489  b.base = NULL;
3490  // Must be 0 such that degree works
3491  entries = 0;
3492  }
3493 
3494  template<class VIC>
3495  forceinline bool
3497  /*
3498  * An advisor that is executed might remove itself due to subsumption.
3499  * As entries are removed from front to back, the advisors must
3500  * be iterated in forward direction.
3501  */
3502  ActorLink** la = actorNonZero(pc_max+1);
3503  ActorLink** le = b.base+entries;
3504  if (la == le)
3505  return true;
3506  d.me = me;
3507  // An advisor that is run, might be removed during execution.
3508  // As removal is done from the back the advisors have to be executed
3509  // in inverse order.
3510  do {
3511  Advisor* a = Advisor::cast(*la);
3512  assert(!a->disposed());
3513  Propagator& p = a->propagator();
3514  switch (p.advise(home,*a,d)) {
3515  case ES_FIX:
3516  break;
3517  case ES_FAILED:
3518  if (home.afc_enabled())
3519  home.gafc.fail(p.gafc);
3520  return false;
3521  case ES_NOFIX:
3522  schedule(home,p,me);
3523  break;
3524  case ES_NOFIX_FORCE:
3525  schedule(home,p,me,true);
3526  break;
3527  default:
3528  GECODE_NEVER;
3529  }
3530  } while (++la < le);
3531  return true;
3532  }
3533 
3534  template<class VIC>
3535  forceinline void
3537  // this refers to the variable to be updated (clone)
3538  // x refers to the original
3539  // Recover from copy
3540  x->b.base = b.base;
3541  x->u.idx[0] = u.idx[0];
3542  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
3543  x->u.idx[1] = u.idx[1];
3544 
3545  ActorLink** f = x->b.base;
3546  unsigned int n = x->degree();
3547  ActorLink** t = sub;
3548  sub += n;
3549  b.base = t;
3550  // Set subscriptions using actor forwarding pointers
3551  while (n >= 4) {
3552  n -= 4;
3553  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3554  t[2]=f[2]->prev(); t[3]=f[3]->prev();
3555  t += 4; f += 4;
3556  }
3557  if (n >= 2) {
3558  n -= 2;
3559  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3560  t += 2; f += 2;
3561  }
3562  if (n > 0) {
3563  t[0]=f[0]->prev();
3564  }
3565  }
3566 
3567  template<class VIC>
3568  forceinline void
3569  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3570  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
3571  while (x != NULL) {
3572  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
3573  }
3574  }
3575 
3576 
3577 
3578  /*
3579  * Variable disposer
3580  *
3581  */
3582  template<class VarImp>
3584 #ifdef GECODE_HAS_VAR_DISPOSE
3585  Space::vd[VarImp::idx_d] = this;
3586 #endif
3587  }
3588 
3589  template<class VarImp>
3590  void
3592  VarImp* x = static_cast<VarImp*>(_x);
3593  do {
3594  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
3595  } while (x != NULL);
3596  }
3597 
3598  /*
3599  * Statistics
3600  */
3601 
3602  forceinline void
3604  propagate = 0;
3605  wmp = false;
3606  }
3607  forceinline
3609  reset();
3610  }
3613  propagate += s.propagate;
3614  wmp |= s.wmp;
3615  return *this;
3616  }
3619  StatusStatistics t(s);
3620  return t += *this;
3621  }
3622 
3623  forceinline void
3625 
3626  forceinline
3628  reset();
3629  }
3632  CloneStatistics s;
3633  return s;
3634  }
3637  return *this;
3638  }
3639 
3640  forceinline void
3642 
3643  forceinline
3645  reset();
3646  }
3649  CommitStatistics s;
3650  return s;
3651  }
3654  return *this;
3655  }
3656 
3657  /*
3658  * Cost computation
3659  *
3660  */
3661 
3662  forceinline
3663  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
3664 
3665  forceinline PropCost
3666  PropCost::cost(PropCost::Mod m,
3668  unsigned int n) {
3669  if (n < 2)
3670  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3671  else if (n == 2)
3672  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3673  else if (n == 3)
3674  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3675  else
3676  return (m == LO) ? lo : hi;
3677  }
3678 
3679  forceinline PropCost
3680  PropCost::crazy(PropCost::Mod m, unsigned int n) {
3681  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
3682  }
3685  assert(n >= 0);
3686  return crazy(m,static_cast<unsigned int>(n));
3687  }
3689  PropCost::cubic(PropCost::Mod m, unsigned int n) {
3690  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
3691  }
3694  assert(n >= 0);
3695  return cubic(m,static_cast<unsigned int>(n));
3696  }
3698  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
3699  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
3700  }
3703  assert(n >= 0);
3704  return quadratic(m,static_cast<unsigned int>(n));
3705  }
3707  PropCost::linear(PropCost::Mod m, unsigned int n) {
3708  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
3709  }
3712  assert(n >= 0);
3713  return linear(m,static_cast<unsigned int>(n));
3714  }
3717  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3718  }
3721  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3722  }
3725  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3726  }
3727 
3728  /*
3729  * Iterators for propagators and branchers of a space
3730  *
3731  */
3732  forceinline
3734  : home(home0), q(home.pc.p.active) {
3735  while (q >= &home.pc.p.queue[0]) {
3736  if (q->next() != q) {
3737  c = q->next(); e = q; q--;
3738  return;
3739  }
3740  q--;
3741  }
3742  q = NULL;
3743  if (!home.pl.empty()) {
3744  c = Propagator::cast(home.pl.next());
3745  e = Propagator::cast(&home.pl);
3746  } else {
3747  c = e = NULL;
3748  }
3749  }
3750  forceinline bool
3752  return c != NULL;
3753  }
3754  forceinline void
3756  c = c->next();
3757  if (c == e) {
3758  if (q == NULL) {
3759  c = NULL;
3760  } else {
3761  while (q >= &home.pc.p.queue[0]) {
3762  if (q->next() != q) {
3763  c = q->next(); e = q; q--;
3764  return;
3765  }
3766  q--;
3767  }
3768  q = NULL;
3769  if (!home.pl.empty()) {
3770  c = Propagator::cast(home.pl.next());
3771  e = Propagator::cast(&home.pl);
3772  } else {
3773  c = NULL;
3774  }
3775  }
3776  }
3777  }
3778  forceinline const Propagator&
3780  return *Propagator::cast(c);
3781  }
3782 
3783  forceinline
3785  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
3786  forceinline bool
3788  return c != e;
3789  }
3790  forceinline void
3792  c = c->next();
3793  }
3794  forceinline const Brancher&
3796  return *Brancher::cast(c);
3797  }
3798 
3799  /*
3800  * Space construction support
3801  *
3802  */
3803  template<class T>
3804  forceinline T&
3806  return alloc<T>(1);
3807  }
3808  template<class T, typename A1>
3809  forceinline T&
3810  Space::construct(A1 const& a1) {
3811  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3812  new (&t) T(a1);
3813  return t;
3814  }
3815  template<class T, typename A1, typename A2>
3816  forceinline T&
3817  Space::construct(A1 const& a1, A2 const& a2) {
3818  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3819  new (&t) T(a1,a2);
3820  return t;
3821  }
3822  template<class T, typename A1, typename A2, typename A3>
3823  forceinline T&
3824  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
3825  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3826  new (&t) T(a1,a2,a3);
3827  return t;
3828  }
3829  template<class T, typename A1, typename A2, typename A3, typename A4>
3830  forceinline T&
3831  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
3832  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3833  new (&t) T(a1,a2,a3,a4);
3834  return t;
3835  }
3836  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
3837  forceinline T&
3838  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
3839  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3840  new (&t) T(a1,a2,a3,a4,a5);
3841  return t;
3842  }
3843 
3844 }
3845 
3846 // STATISTICS: kernel-core