Generated on Tue Oct 22 2013 00:49:06 for Gecode by doxygen 1.8.4
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-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
22  * $Revision: 13840 $
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 
49 #include <iostream>
50 
51 namespace Gecode {
52 
53  class Space;
54 
79  class SharedHandle {
80  public:
88  class Object {
89  friend class Space;
90  friend class SharedHandle;
91  private:
93  Object* next;
95  Object* fwd;
97  unsigned int use_cnt;
98  public:
100  Object(void);
102  virtual Object* copy(void) const = 0;
104  virtual ~Object(void);
106  static void* operator new(size_t s);
108  static void operator delete(void* p);
109  };
110  private:
112  Object* o;
114  void subscribe(void);
116  void cancel(void);
117  public:
119  SharedHandle(void);
123  SharedHandle(const SharedHandle& sh);
127  void update(Space& home, bool share, SharedHandle& sh);
129  ~SharedHandle(void);
130  protected:
132  SharedHandle::Object* object(void) const;
135  };
136 
145  typedef int ModEvent;
147 
154 
156  typedef int PropCond;
158  const PropCond PC_GEN_NONE = -1;
162 
173  typedef int ModEventDelta;
174 
175 }
176 
178 
179 namespace Gecode {
180 
183  public:
185  static const int idx_c = -1;
187  static const int idx_d = -1;
191  static const int free_bits = 0;
193  static const int med_fst = 0;
195  static const int med_lst = 0;
197  static const int med_mask = 0;
199  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
201  static bool med_update(ModEventDelta& med, ModEvent me);
202  };
203 
206  GECODE_NEVER; return 0;
207  }
208  forceinline bool
210  GECODE_NEVER; return false;
211  }
212 
213 
214  /*
215  * These are the classes of interest
216  *
217  */
218  class ActorLink;
219  class Actor;
220  class Propagator;
221  class LocalObject;
222  class Advisor;
223  class AFC;
224  class Brancher;
225  class BrancherHandle;
226  template<class A> class Council;
227  template<class A> class Advisors;
228  template<class VIC> class VarImp;
229 
230 
231  /*
232  * Variable implementations
233  *
234  */
235 
243  class VarImpBase {};
244 
252  public:
254  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
257  };
258 
265  template<class VarImp>
267  public:
269  VarImpDisposer(void);
271  virtual void dispose(Space& home, VarImpBase* x);
272  };
273 
275  class Delta {
276  template<class VIC> friend class VarImp;
277  private:
279  ModEvent me;
280  };
281 
289  template<class VIC>
290  class VarImp : public VarImpBase {
291  friend class Space;
292  friend class Propagator;
293  template<class VarImp> friend class VarImpDisposer;
294  private:
295  union {
313  } b;
314 
316  static const int idx_c = VIC::idx_c;
318  static const int idx_d = VIC::idx_d;
320  static const int free_bits = VIC::free_bits;
322  unsigned int entries;
324  unsigned int free_and_bits;
326  static const Gecode::PropCond pc_max = VIC::pc_max;
327 
328  union {
339  unsigned int idx[pc_max+1];
342  } u;
343 
345  ActorLink** actor(PropCond pc);
347  ActorLink** actorNonZero(PropCond pc);
349  unsigned int& idx(PropCond pc);
351  unsigned int idx(PropCond pc) const;
352 
359  void update(VarImp* x, ActorLink**& sub);
366  static void update(Space& home, ActorLink**& sub);
367 
369  void enter(Space& home, Propagator* p, PropCond pc);
371  void enter(Space& home, Advisor* a);
373  void resize(Space& home);
375  void remove(Space& home, Propagator* p, PropCond pc);
377  void remove(Space& home, Advisor* a);
378 
379 
380  protected:
382  void cancel(Space& home);
388  bool advise(Space& home, ModEvent me, Delta& d);
389 #ifdef GECODE_HAS_VAR_DISPOSE
390  static VarImp<VIC>* vars_d(Space& home);
393  static void vars_d(Space& home, VarImp<VIC>* x);
394 #endif
395 
396  public:
398  VarImp(Space& home);
400  VarImp(void);
401 
403 
404 
416  void subscribe(Space& home, Propagator& p, PropCond pc,
417  bool assigned, ModEvent me, bool schedule);
423  void cancel(Space& home, Propagator& p, PropCond pc,
424  bool assigned);
430  void subscribe(Space& home, Advisor& a, bool assigned);
436  void cancel(Space& home, Advisor& a, bool assigned);
437 
444  unsigned int degree(void) const;
451  double afc(const Space& home) const;
453 
455 
456  VarImp(Space& home, bool share, VarImp& x);
459  bool copied(void) const;
461  VarImp* forward(void) const;
463  VarImp* next(void) const;
465 
467 
468 
475  static void schedule(Space& home, Propagator& p, ModEvent me,
476  bool force = false);
478  static ModEvent me(const ModEventDelta& med);
480  static ModEventDelta med(ModEvent me);
482  static ModEvent me_combine(ModEvent me1, ModEvent me2);
484 
486 
487  static ModEvent modevent(const Delta& d);
490 
492 
493  unsigned int bits(void) const;
496  unsigned int& bits(void);
498 
499  protected:
501  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
502 
503  public:
505 
506  static void* operator new(size_t,Space&);
509  static void operator delete(void*,Space&);
511  static void operator delete(void*);
513  };
514 
523  enum ExecStatus {
525  ES_FAILED = -1,
526  ES_NOFIX = 0,
527  ES_OK = 0,
528  ES_FIX = 1,
531  };
532 
537  class PropCost {
538  friend class Space;
539  public:
541  enum ActualCost {
556  AC_MAX = 6
557  };
560  public:
562  enum Mod {
563  LO,
564  HI
565  };
566  private:
568  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
571  public:
573  static PropCost crazy(PropCost::Mod m, unsigned int n);
575  static PropCost crazy(PropCost::Mod m, int n);
577  static PropCost cubic(PropCost::Mod m, unsigned int n);
579  static PropCost cubic(PropCost::Mod m, int n);
581  static PropCost quadratic(PropCost::Mod m, unsigned int n);
583  static PropCost quadratic(PropCost::Mod m, int n);
585  static PropCost linear(PropCost::Mod m, unsigned int n);
587  static PropCost linear(PropCost::Mod m, int n);
589  static PropCost ternary(PropCost::Mod m);
591  static PropCost binary(PropCost::Mod m);
593  static PropCost unary(PropCost::Mod m);
594  };
595 
596 
610  AP_DISPOSE = (1 << 0),
616  AP_WEAKLY = (1 << 1)
617  };
618 
619 
627  class ActorLink {
628  friend class Actor;
629  friend class Propagator;
630  friend class Advisor;
631  friend class Brancher;
632  friend class LocalObject;
633  friend class Space;
634  template<class VIC> friend class VarImp;
635  private:
636  ActorLink* _next; ActorLink* _prev;
637  public:
639  ActorLink* prev(void) const; void prev(ActorLink*);
641  ActorLink* next(void) const; void next(ActorLink*);
642  ActorLink** next_ref(void);
644 
646  void init(void);
648  void unlink(void);
650  void head(ActorLink* al);
652  void tail(ActorLink* al);
654  bool empty(void) const;
656  template<class T> static ActorLink* cast(T* a);
658  template<class T> static const ActorLink* cast(const T* a);
659  };
660 
661 
667  friend class ActorLink;
668  friend class Space;
669  friend class Propagator;
670  friend class Advisor;
671  friend class Brancher;
672  friend class LocalObject;
673  template<class VIC> friend class VarImp;
674  template<class A> friend class Council;
675  private:
677  static Actor* cast(ActorLink* al);
679  static const Actor* cast(const ActorLink* al);
681  GECODE_KERNEL_EXPORT static Actor* sentinel;
682  public:
684  virtual Actor* copy(Space& home, bool share) = 0;
685 
687 
690  virtual size_t dispose(Space& home);
692  static void* operator new(size_t s, Space& home);
694  static void operator delete(void* p, Space& home);
695  private:
696 #ifndef __GNUC__
697  static void operator delete(void* p);
699 #endif
700  static void* operator new(size_t s);
703 #ifdef __GNUC__
704  public:
706  GECODE_KERNEL_EXPORT virtual ~Actor(void);
708  static void operator delete(void* p);
709 #endif
710  };
711 
712 
713 
717  class Home {
718  protected:
723  public:
725 
726  Home(Space& s, Propagator* p=NULL);
729  Home& operator =(const Home& h);
731  operator Space&(void);
733 
738  Propagator* propagator(void) const;
740 
742  bool failed(void) const;
745  void fail(void);
747  void notice(Actor& a, ActorProperty p, bool duplicate=false);
749  };
750 
756  friend class ActorLink;
757  friend class Space;
758  template<class VIC> friend class VarImp;
759  friend class Advisor;
760  template<class A> friend class Council;
761  private:
762  union {
766  size_t size;
769  } u;
771  GlobalAFC::Counter& gafc;
773  static Propagator* cast(ActorLink* al);
775  static const Propagator* cast(const ActorLink* al);
776  protected:
778  Propagator(Home home);
780  Propagator(Space& home, bool share, Propagator& p);
781 
782  public:
784 
785 
808  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
810  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
818  ModEventDelta modeventdelta(void) const;
855  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
857 
859  double afc(const Space& home) const;
862  };
863 
864 
872  template<class A>
873  class Council {
874  friend class Advisor;
875  friend class Advisors<A>;
876  private:
878  mutable ActorLink* advisors;
879  public:
881  Council(void);
883  Council(Space& home);
885  bool empty(void) const;
887  void update(Space& home, bool share, Council<A>& c);
889  void dispose(Space& home);
890  };
891 
892 
897  template<class A>
898  class Advisors {
899  private:
901  ActorLink* a;
902  public:
904  Advisors(const Council<A>& c);
906  bool operator ()(void) const;
908  void operator ++(void);
910  A& advisor(void) const;
911  };
912 
913 
924  class Advisor : private ActorLink {
925  template<class VIC> friend class VarImp;
926  template<class A> friend class Council;
927  template<class A> friend class Advisors;
928  private:
930  bool disposed(void) const;
932  static Advisor* cast(ActorLink* al);
934  static const Advisor* cast(const ActorLink* al);
935  protected:
937  Propagator& propagator(void) const;
938  public:
940  template<class A>
941  Advisor(Space& home, Propagator& p, Council<A>& c);
943  Advisor(Space& home, bool share, Advisor& a);
944 
946 
947  template<class A>
949  void dispose(Space& home, Council<A>& c);
951  static void* operator new(size_t s, Space& home);
953  static void operator delete(void* p, Space& home);
955  private:
956 #ifndef __GNUC__
957  static void operator delete(void* p);
959 #endif
960  static void* operator new(size_t s);
962  };
963 
964 
970  private:
972  void* nl;
973  public:
975  enum Status {
978  NONE
979  };
981  NGL(void);
983  NGL(Space& home);
985  NGL(Space& home, bool share, NGL& ngl);
987  virtual void subscribe(Space& home, Propagator& p) = 0;
989  virtual void cancel(Space& home, Propagator& p) = 0;
991  virtual NGL::Status status(const Space& home) const = 0;
993  virtual ExecStatus prune(Space& home) = 0;
995  virtual NGL* copy(Space& home, bool share) = 0;
998  virtual bool notice(void) const;
1000  virtual size_t dispose(Space& home);
1002 
1003  bool leaf(void) const;
1006  NGL* next(void) const;
1008  void leaf(bool l);
1010  void next(NGL* n);
1012  NGL* add(NGL* n, bool l);
1014 
1016  static void* operator new(size_t s, Space& home);
1019  static void operator delete(void* s, Space& home);
1021  static void operator delete(void* p);
1023  };
1024 
1035  friend class Space;
1036  private:
1037  unsigned int _id;
1038  unsigned int _alt;
1039 
1041  unsigned int id(void) const;
1042  protected:
1044  Choice(const Brancher& b, const unsigned int a);
1045  public:
1047  unsigned int alternatives(void) const;
1049  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1051  virtual size_t size(void) const = 0;
1053  static void* operator new(size_t);
1055  static void operator delete(void*);
1057  GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
1058  };
1059 
1070  friend class ActorLink;
1071  friend class Space;
1072  friend class Choice;
1073  private:
1075  unsigned int _id;
1077  static Brancher* cast(ActorLink* al);
1079  static const Brancher* cast(const ActorLink* al);
1080  protected:
1082  Brancher(Home home);
1084  Brancher(Space& home, bool share, Brancher& b);
1085  public:
1087 
1088  unsigned int id(void) const;
1098  virtual bool status(const Space& home) const = 0;
1106  virtual const Choice* choice(Space& home) = 0;
1108  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1115  virtual ExecStatus commit(Space& home, const Choice& c,
1116  unsigned int a) = 0;
1131  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1142  virtual void print(const Space& home, const Choice& c, unsigned int a,
1143  std::ostream& o) const;
1145  };
1146 
1156  private:
1158  unsigned int _id;
1159  public:
1161  BrancherHandle(void);
1163  BrancherHandle(const Brancher& b);
1165  void update(Space& home, bool share, BrancherHandle& bh);
1167  unsigned int id(void) const;
1169  bool operator ()(const Space& home) const;
1171  void kill(Space& home);
1172  };
1173 
1181  class LocalObject : public Actor {
1182  friend class ActorLink;
1183  friend class Space;
1184  friend class LocalHandle;
1185  protected:
1187  LocalObject(Home home);
1189  LocalObject(Space& home, bool share, LocalObject& l);
1191  static LocalObject* cast(ActorLink* al);
1193  static const LocalObject* cast(const ActorLink* al);
1194  private:
1196  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1197  public:
1199  LocalObject* fwd(Space& home, bool share);
1200  };
1201 
1208  class LocalHandle {
1209  private:
1211  LocalObject* o;
1212  protected:
1214  LocalHandle(void);
1216  LocalHandle(LocalObject* lo);
1218  LocalHandle(const LocalHandle& lh);
1219  public:
1221  LocalHandle& operator =(const LocalHandle& lh);
1223  void update(Space& home, bool share, LocalHandle& lh);
1225  ~LocalHandle(void);
1226  protected:
1228  LocalObject* object(void) const;
1230  void object(LocalObject* n);
1231  };
1232 
1233 
1239  protected:
1241  unsigned long int n;
1242  public:
1244  NoGoods(void);
1247  virtual void post(Space& home);
1249  unsigned long int ng(void) const;
1251  void ng(unsigned long int n);
1253  virtual ~NoGoods(void);
1254  };
1255 
1256 
1265  };
1266 
1272  public:
1274  unsigned long int propagate;
1276  bool wmp;
1278  StatusStatistics(void);
1280  void reset(void);
1285  };
1286 
1292  public:
1294  CloneStatistics(void);
1296  void reset(void);
1301  };
1302 
1308  public:
1310  CommitStatistics(void);
1312  void reset(void);
1317  };
1318 
1319 
1324  friend class Actor;
1325  friend class Propagator;
1326  friend class Brancher;
1327  friend class Advisor;
1328  template<class VIC> friend class VarImp;
1329  template<class VarImp> friend class VarImpDisposer;
1330  friend class SharedHandle;
1331  friend class LocalObject;
1332  friend class Region;
1333  friend class AFC;
1334  friend class BrancherHandle;
1335  private:
1337  SharedMemory* sm;
1339  MemoryManager mm;
1341  GlobalAFC gafc;
1343  ActorLink pl;
1345  ActorLink bl;
1351  Brancher* b_status;
1363  Brancher* b_commit;
1365  Brancher* brancher(unsigned int id);
1368  void kill_brancher(unsigned int id);
1370  static const unsigned reserved_branch_id = 0U;
1371  union {
1373  struct {
1390  unsigned int branch_id;
1392  unsigned int n_sub;
1393  } p;
1395  struct {
1404  } c;
1405  } pc;
1407  void enqueue(Propagator* p);
1412 #ifdef GECODE_HAS_VAR_DISPOSE
1413  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1416  VarImpBase* _vars_d[AllVarConf::idx_d];
1418  template<class VIC> VarImpBase* vars_d(void) const;
1420  template<class VIC> void vars_d(VarImpBase* x);
1421 #endif
1422  void update(ActorLink** sub);
1425 
1427  Actor** d_fst;
1429  Actor** d_cur;
1431  Actor** d_lst;
1432 
1444  unsigned int _wmp_afc;
1446  void afc_enable(void);
1448  bool afc_enabled(void) const;
1450  void wmp(unsigned int n);
1452  unsigned int wmp(void) const;
1453 
1455  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1457  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1459  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1460 
1479  GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
1480 
1514  void _commit(const Choice& c, unsigned int a);
1515 
1516  public:
1521  GECODE_KERNEL_EXPORT Space(void);
1526  GECODE_KERNEL_EXPORT virtual ~Space(void);
1537  GECODE_KERNEL_EXPORT Space(bool share, Space& s);
1544  virtual Space* copy(bool share) = 0;
1555  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
1570  virtual void master(unsigned long int i, const Space* s,
1571  NoGoods& ng);
1585  virtual void slave(unsigned long int i, const Space* s);
1590  static void* operator new(size_t);
1595  static void operator delete(void*);
1596 
1597 
1598  /*
1599  * Member functions for search engines
1600  *
1601  */
1602 
1615  SpaceStatus status(StatusStatistics& stat=unused_status);
1616 
1649  const Choice* choice(void);
1650 
1661  const Choice* choice(Archive& e) const;
1662 
1683  Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
1684 
1719  void commit(const Choice& c, unsigned int a,
1720  CommitStatistics& stat=unused_commit);
1742  NGL* ngl(const Choice& c, unsigned int a);
1743 
1759  void print(const Choice& c, unsigned int a, std::ostream& o) const;
1760 
1770  void notice(Actor& a, ActorProperty p, bool duplicate=false);
1779  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
1780 
1781 
1792  ExecStatus ES_SUBSUMED(Propagator& p);
1807  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
1818  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1829  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1830 
1841  template<class A>
1842  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
1853  template<class A>
1854  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
1866  template<class A>
1867  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
1868 
1876  void fail(void);
1885  bool failed(void) const;
1890  bool stable(void) const;
1897  GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
1904  GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
1905 
1907 
1908  Home operator ()(Propagator& p);
1911 
1923  template<class T>
1924  T* alloc(long unsigned int n);
1931  template<class T>
1932  T* alloc(long int n);
1939  template<class T>
1940  T* alloc(unsigned int n);
1947  template<class T>
1948  T* alloc(int n);
1958  template<class T>
1959  void free(T* b, long unsigned int n);
1969  template<class T>
1970  void free(T* b, long int n);
1980  template<class T>
1981  void free(T* b, unsigned int n);
1991  template<class T>
1992  void free(T* b, int n);
2004  template<class T>
2005  T* realloc(T* b, long unsigned int n, long unsigned int m);
2017  template<class T>
2018  T* realloc(T* b, long int n, long int m);
2030  template<class T>
2031  T* realloc(T* b, unsigned int n, unsigned int m);
2043  template<class T>
2044  T* realloc(T* b, int n, int m);
2052  template<class T>
2053  T** realloc(T** b, long unsigned int n, long unsigned int m);
2061  template<class T>
2062  T** realloc(T** b, long int n, long int m);
2070  template<class T>
2071  T** realloc(T** b, unsigned int n, unsigned int m);
2079  template<class T>
2080  T** realloc(T** b, int n, int m);
2082  void* ralloc(size_t s);
2084  void rfree(void* p, size_t s);
2086  void* rrealloc(void* b, size_t n, size_t m);
2088  template<size_t> void* fl_alloc(void);
2094  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2103  GECODE_KERNEL_EXPORT void flush(void);
2105 
2107 
2110  template<class T>
2111  T& construct(void);
2117  template<class T, typename A1>
2118  T& construct(A1 const& a1);
2124  template<class T, typename A1, typename A2>
2125  T& construct(A1 const& a1, A2 const& a2);
2131  template<class T, typename A1, typename A2, typename A3>
2132  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2138  template<class T, typename A1, typename A2, typename A3, typename A4>
2139  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2145  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2146  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2148 
2154  class Propagators {
2155  private:
2157  const Space& home;
2159  const ActorLink* q;
2161  const ActorLink* c;
2163  const ActorLink* e;
2164  public:
2166  Propagators(const Space& home);
2168  bool operator ()(void) const;
2170  void operator ++(void);
2172  const Propagator& propagator(void) const;
2173  };
2174 
2180  class Branchers {
2181  private:
2183  const ActorLink* c;
2185  const ActorLink* e;
2186  public:
2188  Branchers(const Space& home);
2190  bool operator ()(void) const;
2192  void operator ++(void);
2194  const Brancher& brancher(void) const;
2195  };
2196 
2198 
2201  void afc_decay(double d);
2203  double afc_decay(void) const;
2206  void afc_set(double a);
2208  };
2209 
2210 
2211 
2212 
2213  /*
2214  * Memory management
2215  *
2216  */
2217 
2218  // Heap allocated
2219  forceinline void*
2220  SharedHandle::Object::operator new(size_t s) {
2221  return heap.ralloc(s);
2222  }
2223  forceinline void
2224  SharedHandle::Object::operator delete(void* p) {
2225  heap.rfree(p);
2226  }
2227 
2228  forceinline void*
2229  Space::operator new(size_t s) {
2230  return heap.ralloc(s);
2231  }
2232  forceinline void
2233  Space::operator delete(void* p) {
2234  heap.rfree(p);
2235  }
2236 
2237  forceinline void
2238  Choice::operator delete(void* p) {
2239  heap.rfree(p);
2240  }
2241  forceinline void*
2242  Choice::operator new(size_t s) {
2243  return heap.ralloc(s);
2244  }
2245 
2246 
2247  // Space allocation: general space heaps and free lists
2248  forceinline void*
2249  Space::ralloc(size_t s) {
2250  return mm.alloc(sm,s);
2251  }
2252  forceinline void
2253  Space::rfree(void* p, size_t s) {
2254  return mm.reuse(p,s);
2255  }
2256  forceinline void*
2257  Space::rrealloc(void* _b, size_t n, size_t m) {
2258  char* b = static_cast<char*>(_b);
2259  if (n < m) {
2260  char* p = static_cast<char*>(ralloc(m));
2261  memcpy(p,b,n);
2262  rfree(b,n);
2263  return p;
2264  } else {
2265  rfree(b+m,m-n);
2266  return b;
2267  }
2268  }
2269 
2270  template<size_t s>
2271  forceinline void*
2273  return mm.template fl_alloc<s>(sm);
2274  }
2275  template<size_t s>
2276  forceinline void
2278  mm.template fl_dispose<s>(f,l);
2279  }
2280 
2281  /*
2282  * Typed allocation routines
2283  *
2284  */
2285  template<class T>
2286  forceinline T*
2287  Space::alloc(long unsigned int n) {
2288  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2289  for (long unsigned int i=n; i--; )
2290  (void) new (p+i) T();
2291  return p;
2292  }
2293  template<class T>
2294  forceinline T*
2295  Space::alloc(long int n) {
2296  assert(n >= 0);
2297  return alloc<T>(static_cast<long unsigned int>(n));
2298  }
2299  template<class T>
2300  forceinline T*
2301  Space::alloc(unsigned int n) {
2302  return alloc<T>(static_cast<long unsigned int>(n));
2303  }
2304  template<class T>
2305  forceinline T*
2307  assert(n >= 0);
2308  return alloc<T>(static_cast<long unsigned int>(n));
2309  }
2310 
2311  template<class T>
2312  forceinline void
2313  Space::free(T* b, long unsigned int n) {
2314  for (long unsigned int i=n; i--; )
2315  b[i].~T();
2316  rfree(b,n*sizeof(T));
2317  }
2318  template<class T>
2319  forceinline void
2320  Space::free(T* b, long int n) {
2321  assert(n >= 0);
2322  free<T>(b,static_cast<long unsigned int>(n));
2323  }
2324  template<class T>
2325  forceinline void
2326  Space::free(T* b, unsigned int n) {
2327  free<T>(b,static_cast<long unsigned int>(n));
2328  }
2329  template<class T>
2330  forceinline void
2331  Space::free(T* b, int n) {
2332  assert(n >= 0);
2333  free<T>(b,static_cast<long unsigned int>(n));
2334  }
2335 
2336  template<class T>
2337  forceinline T*
2338  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2339  if (n < m) {
2340  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2341  for (long unsigned int i=n; i--; )
2342  (void) new (p+i) T(b[i]);
2343  for (long unsigned int i=n; i<m; i++)
2344  (void) new (p+i) T();
2345  free<T>(b,n);
2346  return p;
2347  } else {
2348  free<T>(b+m,m-n);
2349  return b;
2350  }
2351  }
2352  template<class T>
2353  forceinline T*
2354  Space::realloc(T* b, long int n, long int m) {
2355  assert((n >= 0) && (m >= 0));
2356  return realloc<T>(b,static_cast<long unsigned int>(n),
2357  static_cast<long unsigned int>(m));
2358  }
2359  template<class T>
2360  forceinline T*
2361  Space::realloc(T* b, unsigned int n, unsigned int m) {
2362  return realloc<T>(b,static_cast<long unsigned int>(n),
2363  static_cast<long unsigned int>(m));
2364  }
2365  template<class T>
2366  forceinline T*
2367  Space::realloc(T* b, int n, int m) {
2368  assert((n >= 0) && (m >= 0));
2369  return realloc<T>(b,static_cast<long unsigned int>(n),
2370  static_cast<long unsigned int>(m));
2371  }
2372 
2373 #define GECODE_KERNEL_REALLOC(T) \
2374  template<> \
2375  forceinline T* \
2376  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2377  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2378  } \
2379  template<> \
2380  forceinline T* \
2381  Space::realloc<T>(T* b, long int n, long int m) { \
2382  assert((n >= 0) && (m >= 0)); \
2383  return realloc<T>(b,static_cast<long unsigned int>(n), \
2384  static_cast<long unsigned int>(m)); \
2385  } \
2386  template<> \
2387  forceinline T* \
2388  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2389  return realloc<T>(b,static_cast<long unsigned int>(n), \
2390  static_cast<long unsigned int>(m)); \
2391  } \
2392  template<> \
2393  forceinline T* \
2394  Space::realloc<T>(T* b, int n, int m) { \
2395  assert((n >= 0) && (m >= 0)); \
2396  return realloc<T>(b,static_cast<long unsigned int>(n), \
2397  static_cast<long unsigned int>(m)); \
2398  }
2399 
2400  GECODE_KERNEL_REALLOC(bool)
2401  GECODE_KERNEL_REALLOC(signed char)
2402  GECODE_KERNEL_REALLOC(unsigned char)
2403  GECODE_KERNEL_REALLOC(signed short int)
2404  GECODE_KERNEL_REALLOC(unsigned short int)
2405  GECODE_KERNEL_REALLOC(signed int)
2406  GECODE_KERNEL_REALLOC(unsigned int)
2407  GECODE_KERNEL_REALLOC(signed long int)
2408  GECODE_KERNEL_REALLOC(unsigned long int)
2409  GECODE_KERNEL_REALLOC(float)
2410  GECODE_KERNEL_REALLOC(double)
2411 
2412 #undef GECODE_KERNEL_REALLOC
2413 
2414  template<class T>
2415  forceinline T**
2416  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2417  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2418  }
2419  template<class T>
2420  forceinline T**
2421  Space::realloc(T** b, long int n, long int m) {
2422  assert((n >= 0) && (m >= 0));
2423  return realloc<T*>(b,static_cast<long unsigned int>(n),
2424  static_cast<long unsigned int>(m));
2425  }
2426  template<class T>
2427  forceinline T**
2428  Space::realloc(T** b, unsigned int n, unsigned int m) {
2429  return realloc<T*>(b,static_cast<long unsigned int>(n),
2430  static_cast<long unsigned int>(m));
2431  }
2432  template<class T>
2433  forceinline T**
2434  Space::realloc(T** b, int n, int m) {
2435  assert((n >= 0) && (m >= 0));
2436  return realloc<T*>(b,static_cast<long unsigned int>(n),
2437  static_cast<long unsigned int>(m));
2438  }
2439 
2440 
2441 #ifdef GECODE_HAS_VAR_DISPOSE
2442  template<class VIC>
2444  Space::vars_d(void) const {
2445  return _vars_d[VIC::idx_d];
2446  }
2447  template<class VIC>
2448  forceinline void
2449  Space::vars_d(VarImpBase* x) {
2450  _vars_d[VIC::idx_d] = x;
2451  }
2452 #endif
2453 
2454  // Space allocated entities: Actors, variable implementations, and advisors
2455  forceinline void
2456  Actor::operator delete(void*) {}
2457  forceinline void
2458  Actor::operator delete(void*, Space&) {}
2459  forceinline void*
2460  Actor::operator new(size_t s, Space& home) {
2461  return home.ralloc(s);
2462  }
2463 
2464  template<class VIC>
2465  forceinline void
2466  VarImp<VIC>::operator delete(void*) {}
2467  template<class VIC>
2468  forceinline void
2469  VarImp<VIC>::operator delete(void*, Space&) {}
2470  template<class VIC>
2471  forceinline void*
2472  VarImp<VIC>::operator new(size_t s, Space& home) {
2473  return home.ralloc(s);
2474  }
2475 
2476 #ifndef __GNUC__
2477  forceinline void
2478  Advisor::operator delete(void*) {}
2479 #endif
2480  forceinline void
2481  Advisor::operator delete(void*, Space&) {}
2482  forceinline void*
2483  Advisor::operator new(size_t s, Space& home) {
2484  return home.ralloc(s);
2485  }
2486 
2487  forceinline void
2488  NGL::operator delete(void*) {}
2489  forceinline void
2490  NGL::operator delete(void*, Space&) {}
2491  forceinline void*
2492  NGL::operator new(size_t s, Space& home) {
2493  return home.ralloc(s);
2494  }
2495 
2496  /*
2497  * Shared objects and handles
2498  *
2499  */
2500  forceinline
2502  : next(NULL), fwd(NULL), use_cnt(0) {}
2503  forceinline
2505  assert(use_cnt == 0);
2506  }
2507 
2509  SharedHandle::object(void) const {
2510  return o;
2511  }
2512  forceinline void
2513  SharedHandle::subscribe(void) {
2514  if (o != NULL) o->use_cnt++;
2515  }
2516  forceinline void
2517  SharedHandle::cancel(void) {
2518  if ((o != NULL) && (--o->use_cnt == 0))
2519  delete o;
2520  o=NULL;
2521  }
2522  forceinline void
2524  if (n != o) {
2525  cancel(); o=n; subscribe();
2526  }
2527  }
2528  forceinline
2529  SharedHandle::SharedHandle(void) : o(NULL) {}
2530  forceinline
2532  subscribe();
2533  }
2534  forceinline
2536  subscribe();
2537  }
2540  if (&sh != this) {
2541  cancel(); o=sh.o; subscribe();
2542  }
2543  return *this;
2544  }
2545  forceinline void
2546  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
2547  if (sh.o == NULL) {
2548  o=NULL; return;
2549  } else if (share) {
2550  o=sh.o;
2551  } else if (sh.o->fwd != NULL) {
2552  o=sh.o->fwd;
2553  } else {
2554  o = sh.o->copy();
2555  sh.o->fwd = o;
2556  sh.o->next = home.pc.c.shared;
2557  home.pc.c.shared = sh.o;
2558  }
2559  subscribe();
2560  }
2561  forceinline
2563  cancel();
2564  }
2565 
2566 
2567 
2568  /*
2569  * No-goods
2570  *
2571  */
2572  forceinline
2574  : n(0) {}
2575  forceinline unsigned long int
2576  NoGoods::ng(void) const {
2577  return n;
2578  }
2579  forceinline void
2580  NoGoods::ng(unsigned long int n0) {
2581  n=n0;
2582  }
2583  forceinline
2585 
2586 
2587  /*
2588  * ActorLink
2589  *
2590  */
2592  ActorLink::prev(void) const {
2593  return _prev;
2594  }
2595 
2597  ActorLink::next(void) const {
2598  return _next;
2599  }
2600 
2603  return &_next;
2604  }
2605 
2606  forceinline void
2608  _prev = al;
2609  }
2610 
2611  forceinline void
2613  _next = al;
2614  }
2615 
2616  forceinline void
2618  ActorLink* p = _prev; ActorLink* n = _next;
2619  p->_next = n; n->_prev = p;
2620  }
2621 
2622  forceinline void
2624  _next = this; _prev =this;
2625  }
2626 
2627  forceinline void
2629  // Inserts al at head of link-chain (that is, after this)
2630  ActorLink* n = _next;
2631  this->_next = a; a->_prev = this;
2632  a->_next = n; n->_prev = a;
2633  }
2634 
2635  forceinline void
2637  // Inserts al at tail of link-chain (that is, before this)
2638  ActorLink* p = _prev;
2639  a->_next = this; this->_prev = a;
2640  p->_next = a; a->_prev = p;
2641  }
2642 
2643  forceinline bool
2644  ActorLink::empty(void) const {
2645  return _next == this;
2646  }
2647 
2648  template<class T>
2651  // Turning al into a reference is for gcc, assume is for MSVC
2652  GECODE_NOT_NULL(a);
2653  ActorLink& t = *a;
2654  return static_cast<ActorLink*>(&t);
2655  }
2656 
2657  template<class T>
2658  forceinline const ActorLink*
2659  ActorLink::cast(const T* a) {
2660  // Turning al into a reference is for gcc, assume is for MSVC
2661  GECODE_NOT_NULL(a);
2662  const ActorLink& t = *a;
2663  return static_cast<const ActorLink*>(&t);
2664  }
2665 
2666 
2667  /*
2668  * Actor
2669  *
2670  */
2672  Actor::cast(ActorLink* al) {
2673  // Turning al into a reference is for gcc, assume is for MSVC
2674  GECODE_NOT_NULL(al);
2675  ActorLink& t = *al;
2676  return static_cast<Actor*>(&t);
2677  }
2678 
2679  forceinline const Actor*
2680  Actor::cast(const ActorLink* al) {
2681  // Turning al into a reference is for gcc, assume is for MSVC
2682  GECODE_NOT_NULL(al);
2683  const ActorLink& t = *al;
2684  return static_cast<const Actor*>(&t);
2685  }
2686 
2687  forceinline void
2688  Space::afc_enable(void) {
2689  _wmp_afc |= 1U;
2690  }
2691  forceinline bool
2692  Space::afc_enabled(void) const {
2693  return (_wmp_afc & 1U) != 0U;
2694  }
2695  forceinline void
2696  Space::wmp(unsigned int n) {
2697  _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2698  }
2699  forceinline unsigned int
2700  Space::wmp(void) const {
2701  return _wmp_afc >> 1U;
2702  }
2703 
2704  forceinline void
2705  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
2706  s.notice(a,p,duplicate);
2707  }
2708 
2710  Space::clone(bool share, CloneStatistics&) const {
2711  // Clone is only const for search engines. During cloning, several data
2712  // structures are updated (e.g. forwarding pointers), so we have to
2713  // cast away the constness.
2714  return const_cast<Space*>(this)->_clone(share);
2715  }
2716 
2717  forceinline void
2718  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
2719  _commit(c,a);
2720  }
2721 
2722  forceinline double
2723  Space::afc_decay(void) const {
2724  return gafc.decay();
2725  }
2726 
2727  forceinline size_t
2729  return sizeof(*this);
2730  }
2731 
2732 
2733  /*
2734  * Home for posting actors
2735  *
2736  */
2737  forceinline
2738  Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
2739  forceinline Home&
2741  s=h.s; p=h.p;
2742  return *this;
2743  }
2744  forceinline
2745  Home::operator Space&(void) {
2746  return s;
2747  }
2750  return Home(s,&p);
2751  }
2754  return Home(*this,&p);
2755  }
2757  Home::propagator(void) const {
2758  return p;
2759  }
2760 
2761  /*
2762  * Propagator
2763  *
2764  */
2766  Propagator::cast(ActorLink* al) {
2767  // Turning al into a reference is for gcc, assume is for MSVC
2768  GECODE_NOT_NULL(al);
2769  ActorLink& t = *al;
2770  return static_cast<Propagator*>(&t);
2771  }
2772 
2773  forceinline const Propagator*
2774  Propagator::cast(const ActorLink* al) {
2775  // Turning al into a reference is for gcc, assume is for MSVC
2776  GECODE_NOT_NULL(al);
2777  const ActorLink& t = *al;
2778  return static_cast<const Propagator*>(&t);
2779  }
2780 
2781  forceinline
2783  : gafc((home.propagator() != NULL) ?
2784  // Inherit time counter information
2785  home.propagator()->gafc :
2786  // New propagator information
2787  static_cast<Space&>(home).gafc.allocate()) {
2788  u.advisors = NULL;
2789  assert((u.med == 0) && (u.size == 0));
2790  static_cast<Space&>(home).pl.head(this);
2791  }
2792 
2793  forceinline
2795  : gafc(p.gafc) {
2796  u.advisors = NULL;
2797  assert((u.med == 0) && (u.size == 0));
2798  // Set forwarding pointer
2799  p.prev(this);
2800  }
2801 
2804  return u.med;
2805  }
2806 
2807  forceinline double
2808  Propagator::afc(const Space& home) const {
2809  return const_cast<Space&>(home).gafc.afc(gafc);
2810  }
2811 
2814  p.u.size = s;
2815  return __ES_SUBSUMED;
2816  }
2817 
2820  p.u.size = p.dispose(*this);
2821  return __ES_SUBSUMED;
2822  }
2823 
2826  p.u.med = med;
2827  assert(p.u.med != 0);
2828  return __ES_PARTIAL;
2829  }
2830 
2833  p.u.med = AllVarConf::med_combine(p.u.med,med);
2834  assert(p.u.med != 0);
2835  return __ES_PARTIAL;
2836  }
2837 
2838 
2839 
2840  /*
2841  * Brancher
2842  *
2843  */
2845  Brancher::cast(ActorLink* al) {
2846  // Turning al into a reference is for gcc, assume is for MSVC
2847  GECODE_NOT_NULL(al);
2848  ActorLink& t = *al;
2849  return static_cast<Brancher*>(&t);
2850  }
2851 
2852  forceinline const Brancher*
2853  Brancher::cast(const ActorLink* al) {
2854  // Turning al into a reference is for gcc, assume is for MSVC
2855  GECODE_NOT_NULL(al);
2856  const ActorLink& t = *al;
2857  return static_cast<const Brancher*>(&t);
2858  }
2859 
2860  forceinline
2862  _id(static_cast<Space&>(home).pc.p.branch_id++) {
2863  if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2864  throw TooManyBranchers("Brancher::Brancher");
2865  // If no brancher available, make it the first one
2866  if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2867  static_cast<Space&>(home).b_status = this;
2868  if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
2869  static_cast<Space&>(home).b_commit = this;
2870  }
2871  static_cast<Space&>(home).bl.tail(this);
2872  }
2873 
2874  forceinline
2876  : _id(b._id) {
2877  // Set forwarding pointer
2878  b.prev(this);
2879  }
2880 
2881  forceinline unsigned int
2882  Brancher::id(void) const {
2883  return _id;
2884  }
2885 
2887  Space::brancher(unsigned int id) {
2888  /*
2889  * Due to weakly monotonic propagators the following scenario might
2890  * occur: a brancher has been committed with all its available
2891  * choices. Then, propagation determines less information
2892  * than before and the brancher now will create new choices.
2893  * Later, during recomputation, all of these choices
2894  * can be used together, possibly interleaved with
2895  * choices for other branchers. That means all branchers
2896  * must be scanned to find the matching brancher for the choice.
2897  *
2898  * b_commit tries to optimize scanning as it is most likely that
2899  * recomputation does not generate new choices during recomputation
2900  * and hence b_commit is moved from newer to older branchers.
2901  */
2902  Brancher* b_old = b_commit;
2903  // Try whether we are lucky
2904  while (b_commit != Brancher::cast(&bl))
2905  if (id != b_commit->id())
2906  b_commit = Brancher::cast(b_commit->next());
2907  else
2908  return b_commit;
2909  if (b_commit == Brancher::cast(&bl)) {
2910  // We did not find the brancher, start at the beginning
2911  b_commit = Brancher::cast(bl.next());
2912  while (b_commit != b_old)
2913  if (id != b_commit->id())
2914  b_commit = Brancher::cast(b_commit->next());
2915  else
2916  return b_commit;
2917  }
2918  return NULL;
2919  }
2920 
2921  /*
2922  * Brancher handle
2923  *
2924  */
2925  forceinline
2927  : _id(Space::reserved_branch_id) {}
2928  forceinline
2930  : _id(b.id()) {}
2931  forceinline void
2933  _id = bh._id;
2934  }
2935  forceinline unsigned int
2936  BrancherHandle::id(void) const {
2937  return _id;
2938  }
2939  forceinline bool
2940  BrancherHandle::operator ()(const Space& home) const {
2941  return const_cast<Space&>(home).brancher(_id) != NULL;
2942  }
2943  forceinline void
2945  home.kill_brancher(_id);
2946  }
2947 
2948 
2949  /*
2950  * Local objects
2951  *
2952  */
2953 
2956  // Turning al into a reference is for gcc, assume is for MSVC
2957  GECODE_NOT_NULL(al);
2958  ActorLink& t = *al;
2959  return static_cast<LocalObject*>(&t);
2960  }
2961 
2962  forceinline const LocalObject*
2964  // Turning al into a reference is for gcc, assume is for MSVC
2965  GECODE_NOT_NULL(al);
2966  const ActorLink& t = *al;
2967  return static_cast<const LocalObject*>(&t);
2968  }
2969 
2970  forceinline
2972  ActorLink::cast(this)->prev(NULL);
2973  }
2974 
2975  forceinline
2977  ActorLink::cast(this)->prev(NULL);
2978  }
2979 
2981  LocalObject::fwd(Space& home, bool share) {
2982  if (prev() == NULL)
2983  fwdcopy(home,share);
2984  return LocalObject::cast(prev());
2985  }
2986 
2987  forceinline
2988  LocalHandle::LocalHandle(void) : o(NULL) {}
2989  forceinline
2991  forceinline
2992  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
2995  o = lh.o;
2996  return *this;
2997  }
2998  forceinline
3001  LocalHandle::object(void) const { return o; }
3002  forceinline void
3004  forceinline void
3005  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
3006  object(lh.object()->fwd(home,share));
3007  }
3008 
3009 
3010  /*
3011  * Choices
3012  *
3013  */
3014  forceinline
3015  Choice::Choice(const Brancher& b, const unsigned int a)
3016  : _id(b.id()), _alt(a) {}
3017 
3018  forceinline unsigned int
3019  Choice::alternatives(void) const {
3020  return _alt;
3021  }
3022 
3023  forceinline unsigned int
3024  Choice::id(void) const {
3025  return _id;
3026  }
3027 
3028  forceinline
3030 
3031 
3032 
3033  /*
3034  * No-good literal
3035  *
3036  */
3037  forceinline bool
3038  NGL::leaf(void) const {
3039  return Support::marked(nl);
3040  }
3041  forceinline NGL*
3042  NGL::next(void) const {
3043  return static_cast<NGL*>(Support::funmark(nl));
3044  }
3045  forceinline void
3046  NGL::leaf(bool l) {
3047  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3048  }
3049  forceinline void
3051  nl = Support::marked(nl) ? Support::mark(n) : n;
3052  }
3053  forceinline NGL*
3054  NGL::add(NGL* n, bool l) {
3055  nl = Support::marked(nl) ? Support::mark(n) : n;
3056  n->leaf(l);
3057  return n;
3058  }
3059 
3060  forceinline
3061  NGL::NGL(void)
3062  : nl(NULL) {}
3063  forceinline
3065  : nl(NULL) {}
3066  forceinline
3067  NGL::NGL(Space&, bool, NGL&)
3068  : nl(NULL) {}
3069  forceinline size_t
3071  return sizeof(*this);
3072  }
3073 
3074  /*
3075  * Advisor
3076  *
3077  */
3078  template<class A>
3079  forceinline
3081  // Store propagator and forwarding in prev()
3082  ActorLink::prev(&p);
3083  // Link to next advisor in next()
3084  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3085  }
3086 
3087  forceinline
3089 
3090  forceinline bool
3091  Advisor::disposed(void) const {
3092  return prev() == NULL;
3093  }
3094 
3095  forceinline Advisor*
3096  Advisor::cast(ActorLink* al) {
3097  return static_cast<Advisor*>(al);
3098  }
3099 
3100  forceinline const Advisor*
3101  Advisor::cast(const ActorLink* al) {
3102  return static_cast<const Advisor*>(al);
3103  }
3104 
3105  forceinline Propagator&
3106  Advisor::propagator(void) const {
3107  assert(!disposed());
3108  return *Propagator::cast(ActorLink::prev());
3109  }
3110 
3111  template<class A>
3112  forceinline void
3114  assert(!disposed());
3115  ActorLink::prev(NULL);
3116  // Shorten chains of disposed advisors by one, if possible
3117  Advisor* n = Advisor::cast(next());
3118  if ((n != NULL) && n->disposed())
3119  next(n->next());
3120  }
3121 
3122  template<class A>
3125  a.dispose(*this,c);
3126  return ES_FIX;
3127  }
3128 
3129  template<class A>
3132  a.dispose(*this,c);
3133  return ES_NOFIX;
3134  }
3135 
3136  template<class A>
3139  a.dispose(*this,c);
3140  return ES_NOFIX_FORCE;
3141  }
3142 
3143 
3144 
3145  /*
3146  * Advisor council
3147  *
3148  */
3149  template<class A>
3150  forceinline
3152 
3153  template<class A>
3154  forceinline
3156  : advisors(NULL) {}
3157 
3158  template<class A>
3159  forceinline bool
3160  Council<A>::empty(void) const {
3161  ActorLink* a = advisors;
3162  while ((a != NULL) && static_cast<A*>(a)->disposed())
3163  a = a->next();
3164  advisors = a;
3165  return a == NULL;
3166  }
3167 
3168  template<class A>
3169  forceinline void
3170  Council<A>::update(Space& home, bool share, Council<A>& c) {
3171  // Skip all disposed advisors
3172  {
3173  ActorLink* a = c.advisors;
3174  while ((a != NULL) && static_cast<A*>(a)->disposed())
3175  a = a->next();
3176  c.advisors = a;
3177  }
3178  // Are there any advisors to be cloned?
3179  if (c.advisors != NULL) {
3180  // The propagator in from-space
3181  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3182  // The propagator in to-space
3183  Propagator* p_t = Propagator::cast(p_f->prev());
3184  // Advisors in from-space
3185  ActorLink** a_f = &c.advisors;
3186  // Advisors in to-space
3187  A* a_t = NULL;
3188  while (*a_f != NULL) {
3189  if (static_cast<A*>(*a_f)->disposed()) {
3190  *a_f = (*a_f)->next();
3191  } else {
3192  // Run specific copying part
3193  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
3194  // Set propagator pointer
3195  a->prev(p_t);
3196  // Set forwarding pointer
3197  (*a_f)->prev(a);
3198  // Link
3199  a->next(a_t);
3200  a_t = a;
3201  a_f = (*a_f)->next_ref();
3202  }
3203  }
3204  advisors = a_t;
3205  // Enter advisor link for reset
3206  assert(p_f->u.advisors == NULL);
3207  p_f->u.advisors = c.advisors;
3208  } else {
3209  advisors = NULL;
3210  }
3211  }
3212 
3213  template<class A>
3214  forceinline void
3216  ActorLink* a = advisors;
3217  while (a != NULL) {
3218  if (!static_cast<A*>(a)->disposed())
3219  static_cast<A*>(a)->dispose(home,*this);
3220  a = a->next();
3221  }
3222  }
3223 
3224 
3225 
3226  /*
3227  * Advisor iterator
3228  *
3229  */
3230  template<class A>
3231  forceinline
3233  : a(c.advisors) {
3234  while ((a != NULL) && static_cast<A*>(a)->disposed())
3235  a = a->next();
3236  }
3237 
3238  template<class A>
3239  forceinline bool
3241  return a != NULL;
3242  }
3243 
3244  template<class A>
3245  forceinline void
3247  do {
3248  a = a->next();
3249  } while ((a != NULL) && static_cast<A*>(a)->disposed());
3250  }
3251 
3252  template<class A>
3253  forceinline A&
3254  Advisors<A>::advisor(void) const {
3255  return *static_cast<A*>(a);
3256  }
3257 
3258 
3259 
3260  /*
3261  * Space
3262  *
3263  */
3264  forceinline void
3265  Space::enqueue(Propagator* p) {
3266  ActorLink::cast(p)->unlink();
3267  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
3268  c->tail(ActorLink::cast(p));
3269  if (c > pc.p.active)
3270  pc.p.active = c;
3271  }
3272 
3273  forceinline void
3274  Space::fail(void) {
3275  /*
3276  * Now active points beyond the last queue. This is essential as
3277  * enqueuing a propagator in a failed space keeps the space
3278  * failed.
3279  */
3280  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
3281  }
3282  forceinline void
3283  Home::fail(void) {
3284  s.fail();
3285  }
3286 
3287  forceinline bool
3288  Space::failed(void) const {
3289  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
3290  }
3291  forceinline bool
3292  Home::failed(void) const {
3293  return s.failed();
3294  }
3295 
3296  forceinline bool
3297  Space::stable(void) const {
3298  return ((pc.p.active < &pc.p.queue[0]) ||
3299  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
3300  }
3301 
3302 
3303 
3304  /*
3305  * Variable implementation
3306  *
3307  */
3308  template<class VIC>
3311  assert((pc >= 0) && (pc < pc_max+2));
3312  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
3313  }
3314 
3315  template<class VIC>
3316  forceinline ActorLink**
3317  VarImp<VIC>::actorNonZero(PropCond pc) {
3318  assert((pc > 0) && (pc < pc_max+2));
3319  return b.base+u.idx[pc-1];
3320  }
3321 
3322  template<class VIC>
3323  forceinline unsigned int&
3325  assert((pc > 0) && (pc < pc_max+2));
3326  return u.idx[pc-1];
3327  }
3328 
3329  template<class VIC>
3330  forceinline unsigned int
3331  VarImp<VIC>::idx(PropCond pc) const {
3332  assert((pc > 0) && (pc < pc_max+2));
3333  return u.idx[pc-1];
3334  }
3335 
3336  template<class VIC>
3337  forceinline
3339  b.base = NULL; entries = 0;
3340  for (PropCond pc=1; pc<pc_max+2; pc++)
3341  idx(pc) = 0;
3342  free_and_bits = 0;
3343  }
3344 
3345  template<class VIC>
3346  forceinline
3348  b.base = NULL; entries = 0;
3349  for (PropCond pc=1; pc<pc_max+2; pc++)
3350  idx(pc) = 0;
3351  free_and_bits = 0;
3352  }
3353 
3354  template<class VIC>
3355  forceinline unsigned int
3356  VarImp<VIC>::degree(void) const {
3357  assert(!copied());
3358  return entries;
3359  }
3360 
3361  template<class VIC>
3362  forceinline double
3363  VarImp<VIC>::afc(const Space& home) const {
3364  double d = 0.0;
3365  // Count the afc of each propagator
3366  {
3367  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
3368  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3369  while (a < e) {
3370  d += Propagator::cast(*a)->afc(home); a++;
3371  }
3372  }
3373  // Count the afc of each advisor's propagator
3374  {
3375  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3376  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
3377  while (a < e) {
3378  d += Advisor::cast(*a)->propagator().afc(home); a++;
3379  }
3380  }
3381  return d;
3382  }
3383 
3384  template<class VIC>
3387  return d.me;
3388  }
3389 
3390  template<class VIC>
3391  forceinline unsigned int
3392  VarImp<VIC>::bits(void) const {
3393  return free_and_bits;
3394  }
3395 
3396  template<class VIC>
3397  forceinline unsigned int&
3399  return free_and_bits;
3400  }
3401 
3402 #ifdef GECODE_HAS_VAR_DISPOSE
3403  template<class VIC>
3405  VarImp<VIC>::vars_d(Space& home) {
3406  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
3407  }
3408 
3409  template<class VIC>
3410  forceinline void
3411  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
3412  home.vars_d<VIC>(x);
3413  }
3414 #endif
3415 
3416  template<class VIC>
3417  forceinline bool
3418  VarImp<VIC>::copied(void) const {
3419  return Support::marked(b.fwd);
3420  }
3421 
3422  template<class VIC>
3424  VarImp<VIC>::forward(void) const {
3425  assert(copied());
3426  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
3427  }
3428 
3429  template<class VIC>
3431  VarImp<VIC>::next(void) const {
3432  assert(copied());
3433  return u.next;
3434  }
3435 
3436  template<class VIC>
3437  forceinline
3439  VarImpBase** reg;
3440  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3441  if (x.b.base == NULL) {
3442  // Variable implementation needs no index structure
3443  reg = &home.pc.c.vars_noidx;
3444  assert(x.degree() == 0);
3445  } else {
3446  reg = &home.pc.c.vars_u[idx_c];
3447  }
3448  // Save subscriptions in copy
3449  b.base = x.b.base;
3450  entries = x.entries;
3451  for (PropCond pc=1; pc<pc_max+2; pc++)
3452  idx(pc) = x.idx(pc);
3453 
3454  // Set forwarding pointer
3455  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
3456  // Register original
3457  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
3458  }
3459 
3460  template<class VIC>
3463  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3464  }
3465 
3466  template<class VIC>
3469  return static_cast<ModEventDelta>(me << VIC::med_fst);
3470  }
3471 
3472  template<class VIC>
3475  return VIC::me_combine(me1,me2);
3476  }
3477 
3478  template<class VIC>
3479  forceinline void
3481  bool force) {
3482  if (VIC::med_update(p.u.med,me) || force)
3483  home.enqueue(&p);
3484  }
3485 
3486  template<class VIC>
3487  forceinline void
3489  ActorLink** b = actor(pc1);
3490  ActorLink** p = actorNonZero(pc2+1);
3491  while (p-- > b)
3492  schedule(home,*Propagator::cast(*p),me);
3493  }
3494 
3495  template<class VIC>
3496  forceinline void
3497  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
3498  assert(pc <= pc_max);
3499  // Count one new subscription
3500  home.pc.p.n_sub += 1;
3501  if ((free_and_bits >> free_bits) == 0)
3502  resize(home);
3503  free_and_bits -= 1 << free_bits;
3504 
3505  // Enter subscription
3506  b.base[entries] = *actorNonZero(pc_max+1);
3507  entries++;
3508  for (PropCond j = pc_max; j > pc; j--) {
3509  *actorNonZero(j+1) = *actorNonZero(j);
3510  idx(j+1)++;
3511  }
3512  *actorNonZero(pc+1) = *actor(pc);
3513  idx(pc+1)++;
3514  *actor(pc) = ActorLink::cast(p);
3515 
3516 #ifdef GECODE_AUDIT
3517  ActorLink** f = actor(pc);
3518  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
3519  if (*f == p)
3520  goto found;
3521  else
3522  f++;
3523  GECODE_NEVER;
3524  found: ;
3525 #endif
3526  }
3527 
3528  template<class VIC>
3529  forceinline void
3530  VarImp<VIC>::enter(Space& home, Advisor* a) {
3531  // Count one new subscription
3532  home.pc.p.n_sub += 1;
3533  if ((free_and_bits >> free_bits) == 0)
3534  resize(home);
3535  free_and_bits -= 1 << free_bits;
3536 
3537  // Enter subscription
3538  b.base[entries++] = *actorNonZero(pc_max+1);
3539  *actorNonZero(pc_max+1) = a;
3540  }
3541 
3542  template<class VIC>
3543  void
3544  VarImp<VIC>::resize(Space& home) {
3545  if (b.base == NULL) {
3546  assert((free_and_bits >> free_bits) == 0);
3547  // Create fresh dependency array with four entries
3548  free_and_bits += 4 << free_bits;
3549  b.base = home.alloc<ActorLink*>(4);
3550  for (int i=0; i<pc_max+1; i++)
3551  u.idx[i] = 0;
3552  } else {
3553  // Resize dependency array
3554  unsigned int n = degree();
3555  // Find out whether the area is most likely in the special area
3556  // reserved for subscriptions. If yes, just resize mildly otherwise
3557  // more agressively
3558  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
3559  unsigned int m =
3560  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
3561  (n+4) : ((n+1)*3>>1);
3562  ActorLink** prop = home.alloc<ActorLink*>(m);
3563  free_and_bits += (m-n) << free_bits;
3564  // Copy entries
3565  Heap::copy<ActorLink*>(prop, b.base, n);
3566  home.free<ActorLink*>(b.base,n);
3567  b.base = prop;
3568  }
3569  }
3570 
3571  template<class VIC>
3572  void
3574  bool assigned, ModEvent me, bool schedule) {
3575  if (assigned) {
3576  // Do not subscribe, just schedule the propagator
3577  if (schedule)
3579  } else {
3580  enter(home,&p,pc);
3581  // Schedule propagator
3582  if (schedule && (pc != PC_GEN_ASSIGNED))
3583  VarImp<VIC>::schedule(home,p,me);
3584  }
3585  }
3586 
3587  template<class VIC>
3588  forceinline void
3590  if (!assigned)
3591  enter(home,&a);
3592  }
3593 
3594  template<class VIC>
3595  forceinline void
3596  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
3597  assert(pc <= pc_max);
3598  ActorLink* a = ActorLink::cast(p);
3599  // Find actor in dependency array
3600  ActorLink** f = actor(pc);
3601 #ifdef GECODE_AUDIT
3602  while (f < actorNonZero(pc+1))
3603  if (*f == a)
3604  goto found;
3605  else
3606  f++;
3607  GECODE_NEVER;
3608  found: ;
3609 #else
3610  while (*f != a) f++;
3611 #endif
3612  // Remove actor
3613  *f = *(actorNonZero(pc+1)-1);
3614  for (PropCond j = pc+1; j< pc_max+1; j++) {
3615  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3616  idx(j)--;
3617  }
3618  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
3619  idx(pc_max+1)--;
3620  entries--;
3621  free_and_bits += 1 << free_bits;
3622  home.pc.p.n_sub -= 1;
3623  }
3624 
3625  template<class VIC>
3626  forceinline void
3627  VarImp<VIC>::remove(Space& home, Advisor* a) {
3628  // Find actor in dependency array
3629  ActorLink** f = actorNonZero(pc_max+1);
3630 #ifdef GECODE_AUDIT
3631  while (f < b.base+entries)
3632  if (*f == a)
3633  goto found;
3634  else
3635  f++;
3636  GECODE_NEVER;
3637  found: ;
3638 #else
3639  while (*f != a) f++;
3640 #endif
3641  // Remove actor
3642  *f = b.base[--entries];
3643  free_and_bits += 1 << free_bits;
3644  home.pc.p.n_sub -= 1;
3645  }
3646 
3647  template<class VIC>
3648  forceinline void
3650  if (!assigned)
3651  remove(home,&p,pc);
3652  }
3653 
3654  template<class VIC>
3655  forceinline void
3657  if (!assigned)
3658  remove(home,&a);
3659  }
3660 
3661  template<class VIC>
3662  forceinline void
3664  unsigned int n_sub = degree();
3665  home.pc.p.n_sub -= n_sub;
3666  unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3667  home.free<ActorLink*>(b.base,n);
3668  // Must be NULL such that cloning works
3669  b.base = NULL;
3670  // Must be 0 such that degree works
3671  entries = 0;
3672  }
3673 
3674  template<class VIC>
3675  forceinline bool
3677  /*
3678  * An advisor that is executed might remove itself due to subsumption.
3679  * As entries are removed from front to back, the advisors must
3680  * be iterated in forward direction.
3681  */
3682  ActorLink** la = actorNonZero(pc_max+1);
3683  ActorLink** le = b.base+entries;
3684  if (la == le)
3685  return true;
3686  d.me = me;
3687  // An advisor that is run, might be removed during execution.
3688  // As removal is done from the back the advisors have to be executed
3689  // in inverse order.
3690  do {
3691  Advisor* a = Advisor::cast(*la);
3692  assert(!a->disposed());
3693  Propagator& p = a->propagator();
3694  switch (p.advise(home,*a,d)) {
3695  case ES_FIX:
3696  break;
3697  case ES_FAILED:
3698  if (home.afc_enabled())
3699  home.gafc.fail(p.gafc);
3700  return false;
3701  case ES_NOFIX:
3702  schedule(home,p,me);
3703  break;
3704  case ES_NOFIX_FORCE:
3705  schedule(home,p,me,true);
3706  break;
3707  default:
3708  GECODE_NEVER;
3709  }
3710  } while (++la < le);
3711  return true;
3712  }
3713 
3714  template<class VIC>
3715  forceinline void
3717  // this refers to the variable to be updated (clone)
3718  // x refers to the original
3719  // Recover from copy
3720  x->b.base = b.base;
3721  x->u.idx[0] = u.idx[0];
3722  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
3723  x->u.idx[1] = u.idx[1];
3724 
3725  ActorLink** f = x->b.base;
3726  unsigned int n = x->degree();
3727  ActorLink** t = sub;
3728  sub += n;
3729  b.base = t;
3730  // Set subscriptions using actor forwarding pointers
3731  while (n >= 4) {
3732  n -= 4;
3733  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3734  t[2]=f[2]->prev(); t[3]=f[3]->prev();
3735  t += 4; f += 4;
3736  }
3737  if (n >= 2) {
3738  n -= 2;
3739  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3740  t += 2; f += 2;
3741  }
3742  if (n > 0) {
3743  t[0]=f[0]->prev();
3744  }
3745  }
3746 
3747  template<class VIC>
3748  forceinline void
3749  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3750  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
3751  while (x != NULL) {
3752  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
3753  }
3754  }
3755 
3756 
3757 
3758  /*
3759  * Variable disposer
3760  *
3761  */
3762  template<class VarImp>
3764 #ifdef GECODE_HAS_VAR_DISPOSE
3765  Space::vd[VarImp::idx_d] = this;
3766 #endif
3767  }
3768 
3769  template<class VarImp>
3770  void
3772  VarImp* x = static_cast<VarImp*>(_x);
3773  do {
3774  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
3775  } while (x != NULL);
3776  }
3777 
3778  /*
3779  * Statistics
3780  */
3781 
3782  forceinline void
3784  propagate = 0;
3785  wmp = false;
3786  }
3787  forceinline
3789  reset();
3790  }
3793  propagate += s.propagate;
3794  wmp |= s.wmp;
3795  return *this;
3796  }
3799  StatusStatistics t(s);
3800  return t += *this;
3801  }
3802 
3803  forceinline void
3805 
3806  forceinline
3808  reset();
3809  }
3812  CloneStatistics s;
3813  return s;
3814  }
3817  return *this;
3818  }
3819 
3820  forceinline void
3822 
3823  forceinline
3825  reset();
3826  }
3829  CommitStatistics s;
3830  return s;
3831  }
3834  return *this;
3835  }
3836 
3837  /*
3838  * Cost computation
3839  *
3840  */
3841 
3842  forceinline
3843  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
3844 
3845  forceinline PropCost
3846  PropCost::cost(PropCost::Mod m,
3848  unsigned int n) {
3849  if (n < 2)
3850  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3851  else if (n == 2)
3852  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3853  else if (n == 3)
3854  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3855  else
3856  return (m == LO) ? lo : hi;
3857  }
3858 
3859  forceinline PropCost
3860  PropCost::crazy(PropCost::Mod m, unsigned int n) {
3861  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
3862  }
3865  assert(n >= 0);
3866  return crazy(m,static_cast<unsigned int>(n));
3867  }
3869  PropCost::cubic(PropCost::Mod m, unsigned int n) {
3870  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
3871  }
3874  assert(n >= 0);
3875  return cubic(m,static_cast<unsigned int>(n));
3876  }
3878  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
3879  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
3880  }
3883  assert(n >= 0);
3884  return quadratic(m,static_cast<unsigned int>(n));
3885  }
3887  PropCost::linear(PropCost::Mod m, unsigned int n) {
3888  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
3889  }
3892  assert(n >= 0);
3893  return linear(m,static_cast<unsigned int>(n));
3894  }
3897  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3898  }
3901  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3902  }
3905  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3906  }
3907 
3908  /*
3909  * Iterators for propagators and branchers of a space
3910  *
3911  */
3912  forceinline
3914  : home(home0), q(home.pc.p.active) {
3915  while (q >= &home.pc.p.queue[0]) {
3916  if (q->next() != q) {
3917  c = q->next(); e = q; q--;
3918  return;
3919  }
3920  q--;
3921  }
3922  q = NULL;
3923  if (!home.pl.empty()) {
3924  c = Propagator::cast(home.pl.next());
3925  e = Propagator::cast(&home.pl);
3926  } else {
3927  c = e = NULL;
3928  }
3929  }
3930  forceinline bool
3932  return c != NULL;
3933  }
3934  forceinline void
3936  c = c->next();
3937  if (c == e) {
3938  if (q == NULL) {
3939  c = NULL;
3940  } else {
3941  while (q >= &home.pc.p.queue[0]) {
3942  if (q->next() != q) {
3943  c = q->next(); e = q; q--;
3944  return;
3945  }
3946  q--;
3947  }
3948  q = NULL;
3949  if (!home.pl.empty()) {
3950  c = Propagator::cast(home.pl.next());
3951  e = Propagator::cast(&home.pl);
3952  } else {
3953  c = NULL;
3954  }
3955  }
3956  }
3957  }
3958  forceinline const Propagator&
3960  return *Propagator::cast(c);
3961  }
3962 
3963  forceinline
3965  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
3966  forceinline bool
3968  return c != e;
3969  }
3970  forceinline void
3972  c = c->next();
3973  }
3974  forceinline const Brancher&
3976  return *Brancher::cast(c);
3977  }
3978 
3979  /*
3980  * Space construction support
3981  *
3982  */
3983  template<class T>
3984  forceinline T&
3986  return alloc<T>(1);
3987  }
3988  template<class T, typename A1>
3989  forceinline T&
3990  Space::construct(A1 const& a1) {
3991  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3992  new (&t) T(a1);
3993  return t;
3994  }
3995  template<class T, typename A1, typename A2>
3996  forceinline T&
3997  Space::construct(A1 const& a1, A2 const& a2) {
3998  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3999  new (&t) T(a1,a2);
4000  return t;
4001  }
4002  template<class T, typename A1, typename A2, typename A3>
4003  forceinline T&
4004  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
4005  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4006  new (&t) T(a1,a2,a3);
4007  return t;
4008  }
4009  template<class T, typename A1, typename A2, typename A3, typename A4>
4010  forceinline T&
4011  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
4012  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4013  new (&t) T(a1,a2,a3,a4);
4014  return t;
4015  }
4016  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
4017  forceinline T&
4018  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
4019  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4020  new (&t) T(a1,a2,a3,a4,a5);
4021  return t;
4022  }
4023 
4024 }
4025 
4026 // STATISTICS: kernel-core