Generated on Sat Feb 7 2015 02:01:28 for Gecode by doxygen 1.8.9.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: 2015-01-05 07:32:41 +0100 (Mon, 05 Jan 2015) $ by $Author: tack $
22  * $Revision: 14336 $
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 
149  const ModEvent ME_GEN_FAILED = -1;
151  const ModEvent ME_GEN_NONE = 0;
153  const ModEvent ME_GEN_ASSIGNED = 1;
154 
156  typedef int PropCond;
158  const PropCond PC_GEN_NONE = -1;
160  const PropCond PC_GEN_ASSIGNED = 0;
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);
570  PropCost(ActualCost ac);
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);
782  Propagator* fwd(void) const;
783 
784  public:
786 
787 
810  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
812  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
820  ModEventDelta modeventdelta(void) const;
857  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
859 
861  double afc(const Space& home) const;
864  };
865 
866 
874  template<class A>
875  class Council {
876  friend class Advisor;
877  friend class Advisors<A>;
878  private:
880  mutable ActorLink* advisors;
881  public:
883  Council(void);
885  Council(Space& home);
887  bool empty(void) const;
889  void update(Space& home, bool share, Council<A>& c);
891  void dispose(Space& home);
892  };
893 
894 
899  template<class A>
900  class Advisors {
901  private:
903  ActorLink* a;
904  public:
906  Advisors(const Council<A>& c);
908  bool operator ()(void) const;
910  void operator ++(void);
912  A& advisor(void) const;
913  };
914 
915 
926  class Advisor : private ActorLink {
927  template<class VIC> friend class VarImp;
928  template<class A> friend class Council;
929  template<class A> friend class Advisors;
930  private:
932  bool disposed(void) const;
934  static Advisor* cast(ActorLink* al);
936  static const Advisor* cast(const ActorLink* al);
937  protected:
939  Propagator& propagator(void) const;
940  public:
942  template<class A>
943  Advisor(Space& home, Propagator& p, Council<A>& c);
945  Advisor(Space& home, bool share, Advisor& a);
946 
948 
949  template<class A>
951  void dispose(Space& home, Council<A>& c);
953  static void* operator new(size_t s, Space& home);
955  static void operator delete(void* p, Space& home);
957  private:
958 #ifndef __GNUC__
959  static void operator delete(void* p);
961 #endif
962  static void* operator new(size_t s);
964  };
965 
966 
972  private:
974  void* nl;
975  public:
977  enum Status {
980  NONE
981  };
983  NGL(void);
985  NGL(Space& home);
987  NGL(Space& home, bool share, NGL& ngl);
989  virtual void subscribe(Space& home, Propagator& p) = 0;
991  virtual void cancel(Space& home, Propagator& p) = 0;
993  virtual NGL::Status status(const Space& home) const = 0;
995  virtual ExecStatus prune(Space& home) = 0;
997  virtual NGL* copy(Space& home, bool share) = 0;
1000  virtual bool notice(void) const;
1002  virtual size_t dispose(Space& home);
1004 
1005  bool leaf(void) const;
1008  NGL* next(void) const;
1010  void leaf(bool l);
1012  void next(NGL* n);
1014  NGL* add(NGL* n, bool l);
1016 
1018  static void* operator new(size_t s, Space& home);
1021  static void operator delete(void* s, Space& home);
1023  static void operator delete(void* p);
1025  };
1026 
1037  friend class Space;
1038  private:
1039  unsigned int _id;
1040  unsigned int _alt;
1041 
1043  unsigned int id(void) const;
1044  protected:
1046  Choice(const Brancher& b, const unsigned int a);
1047  public:
1049  unsigned int alternatives(void) const;
1051  GECODE_KERNEL_EXPORT virtual ~Choice(void);
1053  virtual size_t size(void) const = 0;
1055  static void* operator new(size_t);
1057  static void operator delete(void*);
1059  GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
1060  };
1061 
1072  friend class ActorLink;
1073  friend class Space;
1074  friend class Choice;
1075  private:
1077  unsigned int _id;
1079  static Brancher* cast(ActorLink* al);
1081  static const Brancher* cast(const ActorLink* al);
1082  protected:
1084  Brancher(Home home);
1086  Brancher(Space& home, bool share, Brancher& b);
1087  public:
1089 
1090  unsigned int id(void) const;
1100  virtual bool status(const Space& home) const = 0;
1108  virtual const Choice* choice(Space& home) = 0;
1110  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1117  virtual ExecStatus commit(Space& home, const Choice& c,
1118  unsigned int a) = 0;
1133  virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1144  virtual void print(const Space& home, const Choice& c, unsigned int a,
1145  std::ostream& o) const;
1147  };
1148 
1158  private:
1160  unsigned int _id;
1161  public:
1163  BrancherHandle(void);
1165  BrancherHandle(const Brancher& b);
1167  void update(Space& home, bool share, BrancherHandle& bh);
1169  unsigned int id(void) const;
1171  bool operator ()(const Space& home) const;
1173  void kill(Space& home);
1174  };
1175 
1183  class LocalObject : public Actor {
1184  friend class ActorLink;
1185  friend class Space;
1186  friend class LocalHandle;
1187  protected:
1189  LocalObject(Home home);
1191  LocalObject(Space& home, bool share, LocalObject& l);
1193  static LocalObject* cast(ActorLink* al);
1195  static const LocalObject* cast(const ActorLink* al);
1196  private:
1198  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1199  public:
1201  LocalObject* fwd(Space& home, bool share);
1202  };
1203 
1210  class LocalHandle {
1211  private:
1213  LocalObject* o;
1214  protected:
1216  LocalHandle(void);
1218  LocalHandle(LocalObject* lo);
1220  LocalHandle(const LocalHandle& lh);
1221  public:
1223  LocalHandle& operator =(const LocalHandle& lh);
1225  void update(Space& home, bool share, LocalHandle& lh);
1227  ~LocalHandle(void);
1228  protected:
1230  LocalObject* object(void) const;
1232  void object(LocalObject* n);
1233  };
1234 
1235 
1241  protected:
1243  unsigned long int n;
1244  public:
1246  NoGoods(void);
1249  virtual void post(Space& home) const;
1251  unsigned long int ng(void) const;
1253  void ng(unsigned long int n);
1255  virtual ~NoGoods(void);
1258  static NoGoods eng;
1259  };
1260 
1266  protected:
1268  const unsigned long int r;
1270  const unsigned long int s;
1272  const unsigned long int f;
1274  const Space* l;
1276  const NoGoods& ng;
1277  public:
1279  CRI(unsigned long int r,
1280  unsigned long int s,
1281  unsigned long int f,
1282  const Space* l,
1283  NoGoods& ng);
1285  unsigned long int restart(void) const;
1287  unsigned long int solution(void) const;
1289  unsigned long int fail(void) const;
1291  const Space* last(void) const;
1293  const NoGoods& nogoods(void) const;
1294  };
1295 
1304  };
1305 
1311  public:
1313  unsigned long int propagate;
1315  bool wmp;
1317  StatusStatistics(void);
1319  void reset(void);
1324  };
1325 
1331  public:
1333  CloneStatistics(void);
1335  void reset(void);
1340  };
1341 
1347  public:
1349  CommitStatistics(void);
1351  void reset(void);
1356  };
1357 
1358 
1363  friend class Actor;
1364  friend class Propagator;
1365  friend class Brancher;
1366  friend class Advisor;
1367  template<class VIC> friend class VarImp;
1368  template<class VarImp> friend class VarImpDisposer;
1369  friend class SharedHandle;
1370  friend class LocalObject;
1371  friend class Region;
1372  friend class AFC;
1373  friend class BrancherHandle;
1374  private:
1376  SharedMemory* sm;
1378  MemoryManager mm;
1380  GlobalAFC gafc;
1382  ActorLink pl;
1384  ActorLink bl;
1390  Brancher* b_status;
1402  Brancher* b_commit;
1404  Brancher* brancher(unsigned int id);
1407  void kill_brancher(unsigned int id);
1409  static const unsigned reserved_branch_id = 0U;
1410  union {
1412  struct {
1429  unsigned int branch_id;
1431  unsigned int n_sub;
1432  } p;
1434  struct {
1443  } c;
1444  } pc;
1446  void enqueue(Propagator* p);
1451 #ifdef GECODE_HAS_VAR_DISPOSE
1452  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1455  VarImpBase* _vars_d[AllVarConf::idx_d];
1457  template<class VIC> VarImpBase* vars_d(void) const;
1459  template<class VIC> void vars_d(VarImpBase* x);
1460 #endif
1461  void update(ActorLink** sub);
1464 
1466  Actor** d_fst;
1468  Actor** d_cur;
1470  Actor** d_lst;
1471 
1483  unsigned int _wmp_afc;
1485  void afc_enable(void);
1487  bool afc_enabled(void) const;
1489  void wmp(unsigned int n);
1491  unsigned int wmp(void) const;
1492 
1494  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1496  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1498  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1499 
1518  GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
1519 
1553  void _commit(const Choice& c, unsigned int a);
1554 
1586  void _trycommit(const Choice& c, unsigned int a);
1587 
1588  public:
1593  GECODE_KERNEL_EXPORT Space(void);
1598  GECODE_KERNEL_EXPORT virtual ~Space(void);
1609  GECODE_KERNEL_EXPORT Space(bool share, Space& s);
1616  virtual Space* copy(bool share) = 0;
1627  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
1643  virtual bool master(const CRI& cri);
1663  virtual bool slave(const CRI& cri);
1668  static void* operator new(size_t);
1673  static void operator delete(void*);
1674 
1675 
1676  /*
1677  * Member functions for search engines
1678  *
1679  */
1680 
1693  SpaceStatus status(StatusStatistics& stat=unused_status);
1694 
1727  const Choice* choice(void);
1728 
1739  const Choice* choice(Archive& e) const;
1740 
1761  Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
1762 
1797  void commit(const Choice& c, unsigned int a,
1798  CommitStatistics& stat=unused_commit);
1831  void trycommit(const Choice& c, unsigned int a,
1832  CommitStatistics& stat=unused_commit);
1852  NGL* ngl(const Choice& c, unsigned int a);
1853 
1869  void print(const Choice& c, unsigned int a, std::ostream& o) const;
1870 
1880  void notice(Actor& a, ActorProperty p, bool duplicate=false);
1889  void ignore(Actor& a, ActorProperty p, bool duplicate=false);
1890 
1891 
1902  ExecStatus ES_SUBSUMED(Propagator& p);
1917  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
1928  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1939  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1940 
1951  template<class A>
1952  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
1963  template<class A>
1964  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
1976  template<class A>
1977  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
1978 
1986  void fail(void);
1995  bool failed(void) const;
2000  bool stable(void) const;
2007  GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
2014  GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
2015 
2017 
2018  Home operator ()(Propagator& p);
2021 
2033  template<class T>
2034  T* alloc(long unsigned int n);
2041  template<class T>
2042  T* alloc(long int n);
2049  template<class T>
2050  T* alloc(unsigned int n);
2057  template<class T>
2058  T* alloc(int n);
2068  template<class T>
2069  void free(T* b, long unsigned int n);
2079  template<class T>
2080  void free(T* b, long int n);
2090  template<class T>
2091  void free(T* b, unsigned int n);
2101  template<class T>
2102  void free(T* b, int n);
2114  template<class T>
2115  T* realloc(T* b, long unsigned int n, long unsigned int m);
2127  template<class T>
2128  T* realloc(T* b, long int n, long int m);
2140  template<class T>
2141  T* realloc(T* b, unsigned int n, unsigned int m);
2153  template<class T>
2154  T* realloc(T* b, int n, int m);
2162  template<class T>
2163  T** realloc(T** b, long unsigned int n, long unsigned int m);
2171  template<class T>
2172  T** realloc(T** b, long int n, long int m);
2180  template<class T>
2181  T** realloc(T** b, unsigned int n, unsigned int m);
2189  template<class T>
2190  T** realloc(T** b, int n, int m);
2192  void* ralloc(size_t s);
2194  void rfree(void* p, size_t s);
2196  void* rrealloc(void* b, size_t n, size_t m);
2198  template<size_t> void* fl_alloc(void);
2204  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2213  GECODE_KERNEL_EXPORT void flush(void);
2215 
2217 
2220  template<class T>
2221  T& construct(void);
2227  template<class T, typename A1>
2228  T& construct(A1 const& a1);
2234  template<class T, typename A1, typename A2>
2235  T& construct(A1 const& a1, A2 const& a2);
2241  template<class T, typename A1, typename A2, typename A3>
2242  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2248  template<class T, typename A1, typename A2, typename A3, typename A4>
2249  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2255  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2256  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2258 
2264  class Propagators {
2265  private:
2267  const Space& home;
2269  const ActorLink* q;
2271  const ActorLink* c;
2273  const ActorLink* e;
2274  public:
2276  Propagators(const Space& home);
2278  bool operator ()(void) const;
2280  void operator ++(void);
2282  const Propagator& propagator(void) const;
2283  };
2284 
2290  class Branchers {
2291  private:
2293  const ActorLink* c;
2295  const ActorLink* e;
2296  public:
2298  Branchers(const Space& home);
2300  bool operator ()(void) const;
2302  void operator ++(void);
2304  const Brancher& brancher(void) const;
2305  };
2306 
2308 
2311  void afc_decay(double d);
2313  double afc_decay(void) const;
2316  void afc_set(double a);
2318  };
2319 
2320 
2321 
2322 
2323  /*
2324  * Memory management
2325  *
2326  */
2327 
2328  // Heap allocated
2329  forceinline void*
2330  SharedHandle::Object::operator new(size_t s) {
2331  return heap.ralloc(s);
2332  }
2333  forceinline void
2334  SharedHandle::Object::operator delete(void* p) {
2335  heap.rfree(p);
2336  }
2337 
2338  forceinline void*
2339  Space::operator new(size_t s) {
2340  return heap.ralloc(s);
2341  }
2342  forceinline void
2343  Space::operator delete(void* p) {
2344  heap.rfree(p);
2345  }
2346 
2347  forceinline void
2348  Choice::operator delete(void* p) {
2349  heap.rfree(p);
2350  }
2351  forceinline void*
2352  Choice::operator new(size_t s) {
2353  return heap.ralloc(s);
2354  }
2355 
2356 
2357  // Space allocation: general space heaps and free lists
2358  forceinline void*
2359  Space::ralloc(size_t s) {
2360  return mm.alloc(sm,s);
2361  }
2362  forceinline void
2363  Space::rfree(void* p, size_t s) {
2364  return mm.reuse(p,s);
2365  }
2366  forceinline void*
2367  Space::rrealloc(void* _b, size_t n, size_t m) {
2368  char* b = static_cast<char*>(_b);
2369  if (n < m) {
2370  char* p = static_cast<char*>(ralloc(m));
2371  memcpy(p,b,n);
2372  rfree(b,n);
2373  return p;
2374  } else {
2375  rfree(b+m,m-n);
2376  return b;
2377  }
2378  }
2379 
2380  template<size_t s>
2381  forceinline void*
2383  return mm.template fl_alloc<s>(sm);
2384  }
2385  template<size_t s>
2386  forceinline void
2388  mm.template fl_dispose<s>(f,l);
2389  }
2390 
2391  /*
2392  * Typed allocation routines
2393  *
2394  */
2395  template<class T>
2396  forceinline T*
2397  Space::alloc(long unsigned int n) {
2398  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2399  for (long unsigned int i=n; i--; )
2400  (void) new (p+i) T();
2401  return p;
2402  }
2403  template<class T>
2404  forceinline T*
2405  Space::alloc(long int n) {
2406  assert(n >= 0);
2407  return alloc<T>(static_cast<long unsigned int>(n));
2408  }
2409  template<class T>
2410  forceinline T*
2411  Space::alloc(unsigned int n) {
2412  return alloc<T>(static_cast<long unsigned int>(n));
2413  }
2414  template<class T>
2415  forceinline T*
2417  assert(n >= 0);
2418  return alloc<T>(static_cast<long unsigned int>(n));
2419  }
2420 
2421  template<class T>
2422  forceinline void
2423  Space::free(T* b, long unsigned int n) {
2424  for (long unsigned int i=n; i--; )
2425  b[i].~T();
2426  rfree(b,n*sizeof(T));
2427  }
2428  template<class T>
2429  forceinline void
2430  Space::free(T* b, long int n) {
2431  assert(n >= 0);
2432  free<T>(b,static_cast<long unsigned int>(n));
2433  }
2434  template<class T>
2435  forceinline void
2436  Space::free(T* b, unsigned int n) {
2437  free<T>(b,static_cast<long unsigned int>(n));
2438  }
2439  template<class T>
2440  forceinline void
2441  Space::free(T* b, int n) {
2442  assert(n >= 0);
2443  free<T>(b,static_cast<long unsigned int>(n));
2444  }
2445 
2446  template<class T>
2447  forceinline T*
2448  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2449  if (n < m) {
2450  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2451  for (long unsigned int i=n; i--; )
2452  (void) new (p+i) T(b[i]);
2453  for (long unsigned int i=n; i<m; i++)
2454  (void) new (p+i) T();
2455  free<T>(b,n);
2456  return p;
2457  } else {
2458  free<T>(b+m,m-n);
2459  return b;
2460  }
2461  }
2462  template<class T>
2463  forceinline T*
2464  Space::realloc(T* b, long int n, long int m) {
2465  assert((n >= 0) && (m >= 0));
2466  return realloc<T>(b,static_cast<long unsigned int>(n),
2467  static_cast<long unsigned int>(m));
2468  }
2469  template<class T>
2470  forceinline T*
2471  Space::realloc(T* b, unsigned int n, unsigned int m) {
2472  return realloc<T>(b,static_cast<long unsigned int>(n),
2473  static_cast<long unsigned int>(m));
2474  }
2475  template<class T>
2476  forceinline T*
2477  Space::realloc(T* b, int n, int m) {
2478  assert((n >= 0) && (m >= 0));
2479  return realloc<T>(b,static_cast<long unsigned int>(n),
2480  static_cast<long unsigned int>(m));
2481  }
2482 
2483 #define GECODE_KERNEL_REALLOC(T) \
2484  template<> \
2485  forceinline T* \
2486  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2487  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2488  } \
2489  template<> \
2490  forceinline T* \
2491  Space::realloc<T>(T* b, long int n, long int m) { \
2492  assert((n >= 0) && (m >= 0)); \
2493  return realloc<T>(b,static_cast<long unsigned int>(n), \
2494  static_cast<long unsigned int>(m)); \
2495  } \
2496  template<> \
2497  forceinline T* \
2498  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2499  return realloc<T>(b,static_cast<long unsigned int>(n), \
2500  static_cast<long unsigned int>(m)); \
2501  } \
2502  template<> \
2503  forceinline T* \
2504  Space::realloc<T>(T* b, int n, int m) { \
2505  assert((n >= 0) && (m >= 0)); \
2506  return realloc<T>(b,static_cast<long unsigned int>(n), \
2507  static_cast<long unsigned int>(m)); \
2508  }
2509 
2510  GECODE_KERNEL_REALLOC(bool)
2511  GECODE_KERNEL_REALLOC(signed char)
2512  GECODE_KERNEL_REALLOC(unsigned char)
2513  GECODE_KERNEL_REALLOC(signed short int)
2514  GECODE_KERNEL_REALLOC(unsigned short int)
2515  GECODE_KERNEL_REALLOC(signed int)
2516  GECODE_KERNEL_REALLOC(unsigned int)
2517  GECODE_KERNEL_REALLOC(signed long int)
2518  GECODE_KERNEL_REALLOC(unsigned long int)
2519  GECODE_KERNEL_REALLOC(float)
2520  GECODE_KERNEL_REALLOC(double)
2521 
2522 #undef GECODE_KERNEL_REALLOC
2523 
2524  template<class T>
2525  forceinline T**
2526  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2527  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2528  }
2529  template<class T>
2530  forceinline T**
2531  Space::realloc(T** b, long int n, long int m) {
2532  assert((n >= 0) && (m >= 0));
2533  return realloc<T*>(b,static_cast<long unsigned int>(n),
2534  static_cast<long unsigned int>(m));
2535  }
2536  template<class T>
2537  forceinline T**
2538  Space::realloc(T** b, unsigned int n, unsigned int m) {
2539  return realloc<T*>(b,static_cast<long unsigned int>(n),
2540  static_cast<long unsigned int>(m));
2541  }
2542  template<class T>
2543  forceinline T**
2544  Space::realloc(T** b, int n, int m) {
2545  assert((n >= 0) && (m >= 0));
2546  return realloc<T*>(b,static_cast<long unsigned int>(n),
2547  static_cast<long unsigned int>(m));
2548  }
2549 
2550 
2551 #ifdef GECODE_HAS_VAR_DISPOSE
2552  template<class VIC>
2554  Space::vars_d(void) const {
2555  return _vars_d[VIC::idx_d];
2556  }
2557  template<class VIC>
2558  forceinline void
2559  Space::vars_d(VarImpBase* x) {
2560  _vars_d[VIC::idx_d] = x;
2561  }
2562 #endif
2563 
2564  // Space allocated entities: Actors, variable implementations, and advisors
2565  forceinline void
2566  Actor::operator delete(void*) {}
2567  forceinline void
2568  Actor::operator delete(void*, Space&) {}
2569  forceinline void*
2570  Actor::operator new(size_t s, Space& home) {
2571  return home.ralloc(s);
2572  }
2573 
2574  template<class VIC>
2575  forceinline void
2576  VarImp<VIC>::operator delete(void*) {}
2577  template<class VIC>
2578  forceinline void
2579  VarImp<VIC>::operator delete(void*, Space&) {}
2580  template<class VIC>
2581  forceinline void*
2582  VarImp<VIC>::operator new(size_t s, Space& home) {
2583  return home.ralloc(s);
2584  }
2585 
2586 #ifndef __GNUC__
2587  forceinline void
2588  Advisor::operator delete(void*) {}
2589 #endif
2590  forceinline void
2591  Advisor::operator delete(void*, Space&) {}
2592  forceinline void*
2593  Advisor::operator new(size_t s, Space& home) {
2594  return home.ralloc(s);
2595  }
2596 
2597  forceinline void
2598  NGL::operator delete(void*) {}
2599  forceinline void
2600  NGL::operator delete(void*, Space&) {}
2601  forceinline void*
2602  NGL::operator new(size_t s, Space& home) {
2603  return home.ralloc(s);
2604  }
2605 
2606  /*
2607  * Shared objects and handles
2608  *
2609  */
2610  forceinline
2612  : next(NULL), fwd(NULL), use_cnt(0) {}
2613  forceinline
2615  assert(use_cnt == 0);
2616  }
2617 
2619  SharedHandle::object(void) const {
2620  return o;
2621  }
2622  forceinline void
2623  SharedHandle::subscribe(void) {
2624  if (o != NULL) o->use_cnt++;
2625  }
2626  forceinline void
2627  SharedHandle::cancel(void) {
2628  if ((o != NULL) && (--o->use_cnt == 0))
2629  delete o;
2630  o=NULL;
2631  }
2632  forceinline void
2634  if (n != o) {
2635  cancel(); o=n; subscribe();
2636  }
2637  }
2638  forceinline
2639  SharedHandle::SharedHandle(void) : o(NULL) {}
2640  forceinline
2642  subscribe();
2643  }
2644  forceinline
2646  subscribe();
2647  }
2650  if (&sh != this) {
2651  cancel(); o=sh.o; subscribe();
2652  }
2653  return *this;
2654  }
2655  forceinline void
2656  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
2657  if (sh.o == NULL) {
2658  o=NULL; return;
2659  } else if (share) {
2660  o=sh.o;
2661  } else if (sh.o->fwd != NULL) {
2662  o=sh.o->fwd;
2663  } else {
2664  o = sh.o->copy();
2665  sh.o->fwd = o;
2666  sh.o->next = home.pc.c.shared;
2667  home.pc.c.shared = sh.o;
2668  }
2669  subscribe();
2670  }
2671  forceinline
2673  cancel();
2674  }
2675 
2676 
2677 
2678  /*
2679  * No-goods
2680  *
2681  */
2682  forceinline
2684  : n(0) {}
2685  forceinline unsigned long int
2686  NoGoods::ng(void) const {
2687  return n;
2688  }
2689  forceinline void
2690  NoGoods::ng(unsigned long int n0) {
2691  n=n0;
2692  }
2693  forceinline
2695 
2696 
2697  /*
2698  * Current restart information
2699  */
2700  forceinline
2701  CRI::CRI(unsigned long int r0,
2702  unsigned long int s0,
2703  unsigned long int f0,
2704  const Space* l0,
2705  NoGoods& ng0)
2706  : r(r0), s(s0), f(f0), l(l0), ng(ng0) {}
2707 
2708  forceinline unsigned long int
2709  CRI::restart(void) const {
2710  return r;
2711  }
2712  forceinline unsigned long int
2713  CRI::solution(void) const {
2714  return s;
2715  }
2716  forceinline unsigned long int
2717  CRI::fail(void) const {
2718  return f;
2719  }
2720  forceinline const Space*
2721  CRI::last(void) const {
2722  return l;
2723  }
2724  forceinline const NoGoods&
2725  CRI::nogoods(void) const {
2726  return ng;
2727  }
2728 
2729 
2730 
2731  /*
2732  * ActorLink
2733  *
2734  */
2736  ActorLink::prev(void) const {
2737  return _prev;
2738  }
2739 
2741  ActorLink::next(void) const {
2742  return _next;
2743  }
2744 
2747  return &_next;
2748  }
2749 
2750  forceinline void
2752  _prev = al;
2753  }
2754 
2755  forceinline void
2757  _next = al;
2758  }
2759 
2760  forceinline void
2762  ActorLink* p = _prev; ActorLink* n = _next;
2763  p->_next = n; n->_prev = p;
2764  }
2765 
2766  forceinline void
2768  _next = this; _prev =this;
2769  }
2770 
2771  forceinline void
2773  // Inserts al at head of link-chain (that is, after this)
2774  ActorLink* n = _next;
2775  this->_next = a; a->_prev = this;
2776  a->_next = n; n->_prev = a;
2777  }
2778 
2779  forceinline void
2781  // Inserts al at tail of link-chain (that is, before this)
2782  ActorLink* p = _prev;
2783  a->_next = this; this->_prev = a;
2784  p->_next = a; a->_prev = p;
2785  }
2786 
2787  forceinline bool
2788  ActorLink::empty(void) const {
2789  return _next == this;
2790  }
2791 
2792  template<class T>
2795  // Turning al into a reference is for gcc, assume is for MSVC
2796  GECODE_NOT_NULL(a);
2797  ActorLink& t = *a;
2798  return static_cast<ActorLink*>(&t);
2799  }
2800 
2801  template<class T>
2802  forceinline const ActorLink*
2803  ActorLink::cast(const T* a) {
2804  // Turning al into a reference is for gcc, assume is for MSVC
2805  GECODE_NOT_NULL(a);
2806  const ActorLink& t = *a;
2807  return static_cast<const ActorLink*>(&t);
2808  }
2809 
2810 
2811  /*
2812  * Actor
2813  *
2814  */
2816  Actor::cast(ActorLink* al) {
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<Actor*>(&t);
2821  }
2822 
2823  forceinline const Actor*
2824  Actor::cast(const ActorLink* al) {
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 Actor*>(&t);
2829  }
2830 
2831  forceinline void
2832  Space::afc_enable(void) {
2833  _wmp_afc |= 1U;
2834  }
2835  forceinline bool
2836  Space::afc_enabled(void) const {
2837  return (_wmp_afc & 1U) != 0U;
2838  }
2839  forceinline void
2840  Space::wmp(unsigned int n) {
2841  _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2842  }
2843  forceinline unsigned int
2844  Space::wmp(void) const {
2845  return _wmp_afc >> 1U;
2846  }
2847 
2848  forceinline void
2849  Home::notice(Actor& a, ActorProperty p, bool duplicate) {
2850  s.notice(a,p,duplicate);
2851  }
2852 
2854  Space::clone(bool share, CloneStatistics&) const {
2855  // Clone is only const for search engines. During cloning, several data
2856  // structures are updated (e.g. forwarding pointers), so we have to
2857  // cast away the constness.
2858  return const_cast<Space*>(this)->_clone(share);
2859  }
2860 
2861  forceinline void
2862  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
2863  _commit(c,a);
2864  }
2865 
2866  forceinline void
2867  Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
2868  _trycommit(c,a);
2869  }
2870 
2871  forceinline double
2872  Space::afc_decay(void) const {
2873  return gafc.decay();
2874  }
2875 
2876  forceinline size_t
2878  return sizeof(*this);
2879  }
2880 
2881 
2882  /*
2883  * Home for posting actors
2884  *
2885  */
2886  forceinline
2887  Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
2888  forceinline Home&
2890  s=h.s; p=h.p;
2891  return *this;
2892  }
2893  forceinline
2894  Home::operator Space&(void) {
2895  return s;
2896  }
2899  return Home(s,&p);
2900  }
2903  return Home(*this,&p);
2904  }
2906  Home::propagator(void) const {
2907  return p;
2908  }
2909 
2910  /*
2911  * Propagator
2912  *
2913  */
2915  Propagator::cast(ActorLink* al) {
2916  // Turning al into a reference is for gcc, assume is for MSVC
2917  GECODE_NOT_NULL(al);
2918  ActorLink& t = *al;
2919  return static_cast<Propagator*>(&t);
2920  }
2921 
2922  forceinline const Propagator*
2923  Propagator::cast(const ActorLink* al) {
2924  // Turning al into a reference is for gcc, assume is for MSVC
2925  GECODE_NOT_NULL(al);
2926  const ActorLink& t = *al;
2927  return static_cast<const Propagator*>(&t);
2928  }
2929 
2930  forceinline Propagator*
2931  Propagator::fwd(void) const {
2932  return static_cast<Propagator*>(prev());
2933  }
2934 
2935  forceinline
2937  : gafc((home.propagator() != NULL) ?
2938  // Inherit time counter information
2939  home.propagator()->gafc :
2940  // New propagator information
2941  static_cast<Space&>(home).gafc.allocate()) {
2942  u.advisors = NULL;
2943  assert((u.med == 0) && (u.size == 0));
2944  static_cast<Space&>(home).pl.head(this);
2945  }
2946 
2947  forceinline
2949  : gafc(p.gafc) {
2950  u.advisors = NULL;
2951  assert((u.med == 0) && (u.size == 0));
2952  // Set forwarding pointer
2953  p.prev(this);
2954  }
2955 
2958  return u.med;
2959  }
2960 
2961  forceinline double
2962  Propagator::afc(const Space& home) const {
2963  return const_cast<Space&>(home).gafc.afc(gafc);
2964  }
2965 
2968  p.u.size = s;
2969  return __ES_SUBSUMED;
2970  }
2971 
2974  p.u.size = p.dispose(*this);
2975  return __ES_SUBSUMED;
2976  }
2977 
2980  p.u.med = med;
2981  assert(p.u.med != 0);
2982  return __ES_PARTIAL;
2983  }
2984 
2987  p.u.med = AllVarConf::med_combine(p.u.med,med);
2988  assert(p.u.med != 0);
2989  return __ES_PARTIAL;
2990  }
2991 
2992 
2993 
2994  /*
2995  * Brancher
2996  *
2997  */
2999  Brancher::cast(ActorLink* al) {
3000  // Turning al into a reference is for gcc, assume is for MSVC
3001  GECODE_NOT_NULL(al);
3002  ActorLink& t = *al;
3003  return static_cast<Brancher*>(&t);
3004  }
3005 
3006  forceinline const Brancher*
3007  Brancher::cast(const ActorLink* al) {
3008  // Turning al into a reference is for gcc, assume is for MSVC
3009  GECODE_NOT_NULL(al);
3010  const ActorLink& t = *al;
3011  return static_cast<const Brancher*>(&t);
3012  }
3013 
3014  forceinline
3016  _id(static_cast<Space&>(home).pc.p.branch_id++) {
3017  if (static_cast<Space&>(home).pc.p.branch_id == 0U)
3018  throw TooManyBranchers("Brancher::Brancher");
3019  // If no brancher available, make it the first one
3020  if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
3021  static_cast<Space&>(home).b_status = this;
3022  if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
3023  static_cast<Space&>(home).b_commit = this;
3024  }
3025  static_cast<Space&>(home).bl.tail(this);
3026  }
3027 
3028  forceinline
3030  : _id(b._id) {
3031  // Set forwarding pointer
3032  b.prev(this);
3033  }
3034 
3035  forceinline unsigned int
3036  Brancher::id(void) const {
3037  return _id;
3038  }
3039 
3041  Space::brancher(unsigned int id) {
3042  /*
3043  * Due to weakly monotonic propagators the following scenario might
3044  * occur: a brancher has been committed with all its available
3045  * choices. Then, propagation determines less information
3046  * than before and the brancher now will create new choices.
3047  * Later, during recomputation, all of these choices
3048  * can be used together, possibly interleaved with
3049  * choices for other branchers. That means all branchers
3050  * must be scanned to find the matching brancher for the choice.
3051  *
3052  * b_commit tries to optimize scanning as it is most likely that
3053  * recomputation does not generate new choices during recomputation
3054  * and hence b_commit is moved from newer to older branchers.
3055  */
3056  Brancher* b_old = b_commit;
3057  // Try whether we are lucky
3058  while (b_commit != Brancher::cast(&bl))
3059  if (id != b_commit->id())
3060  b_commit = Brancher::cast(b_commit->next());
3061  else
3062  return b_commit;
3063  if (b_commit == Brancher::cast(&bl)) {
3064  // We did not find the brancher, start at the beginning
3065  b_commit = Brancher::cast(bl.next());
3066  while (b_commit != b_old)
3067  if (id != b_commit->id())
3068  b_commit = Brancher::cast(b_commit->next());
3069  else
3070  return b_commit;
3071  }
3072  return NULL;
3073  }
3074 
3075  /*
3076  * Brancher handle
3077  *
3078  */
3079  forceinline
3081  : _id(Space::reserved_branch_id) {}
3082  forceinline
3084  : _id(b.id()) {}
3085  forceinline void
3087  _id = bh._id;
3088  }
3089  forceinline unsigned int
3090  BrancherHandle::id(void) const {
3091  return _id;
3092  }
3093  forceinline bool
3094  BrancherHandle::operator ()(const Space& home) const {
3095  return const_cast<Space&>(home).brancher(_id) != NULL;
3096  }
3097  forceinline void
3099  home.kill_brancher(_id);
3100  }
3101 
3102 
3103  /*
3104  * Local objects
3105  *
3106  */
3107 
3110  // Turning al into a reference is for gcc, assume is for MSVC
3111  GECODE_NOT_NULL(al);
3112  ActorLink& t = *al;
3113  return static_cast<LocalObject*>(&t);
3114  }
3115 
3116  forceinline const LocalObject*
3118  // Turning al into a reference is for gcc, assume is for MSVC
3119  GECODE_NOT_NULL(al);
3120  const ActorLink& t = *al;
3121  return static_cast<const LocalObject*>(&t);
3122  }
3123 
3124  forceinline
3126  ActorLink::cast(this)->prev(NULL);
3127  }
3128 
3129  forceinline
3131  ActorLink::cast(this)->prev(NULL);
3132  }
3133 
3135  LocalObject::fwd(Space& home, bool share) {
3136  if (prev() == NULL)
3137  fwdcopy(home,share);
3138  return LocalObject::cast(prev());
3139  }
3140 
3141  forceinline
3142  LocalHandle::LocalHandle(void) : o(NULL) {}
3143  forceinline
3145  forceinline
3146  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
3149  o = lh.o;
3150  return *this;
3151  }
3152  forceinline
3155  LocalHandle::object(void) const { return o; }
3156  forceinline void
3158  forceinline void
3159  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
3160  object(lh.object()->fwd(home,share));
3161  }
3162 
3163 
3164  /*
3165  * Choices
3166  *
3167  */
3168  forceinline
3169  Choice::Choice(const Brancher& b, const unsigned int a)
3170  : _id(b.id()), _alt(a) {}
3171 
3172  forceinline unsigned int
3173  Choice::alternatives(void) const {
3174  return _alt;
3175  }
3176 
3177  forceinline unsigned int
3178  Choice::id(void) const {
3179  return _id;
3180  }
3181 
3182  forceinline
3184 
3185 
3186 
3187  /*
3188  * No-good literal
3189  *
3190  */
3191  forceinline bool
3192  NGL::leaf(void) const {
3193  return Support::marked(nl);
3194  }
3195  forceinline NGL*
3196  NGL::next(void) const {
3197  return static_cast<NGL*>(Support::funmark(nl));
3198  }
3199  forceinline void
3200  NGL::leaf(bool l) {
3201  nl = l ? Support::fmark(nl) : Support::funmark(nl);
3202  }
3203  forceinline void
3205  nl = Support::marked(nl) ? Support::mark(n) : n;
3206  }
3207  forceinline NGL*
3208  NGL::add(NGL* n, bool l) {
3209  nl = Support::marked(nl) ? Support::mark(n) : n;
3210  n->leaf(l);
3211  return n;
3212  }
3213 
3214  forceinline
3215  NGL::NGL(void)
3216  : nl(NULL) {}
3217  forceinline
3219  : nl(NULL) {}
3220  forceinline
3221  NGL::NGL(Space&, bool, NGL&)
3222  : nl(NULL) {}
3223  forceinline size_t
3225  return sizeof(*this);
3226  }
3227 
3228  /*
3229  * Advisor
3230  *
3231  */
3232  template<class A>
3233  forceinline
3235  // Store propagator and forwarding in prev()
3236  ActorLink::prev(&p);
3237  // Link to next advisor in next()
3238  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
3239  }
3240 
3241  forceinline
3243 
3244  forceinline bool
3245  Advisor::disposed(void) const {
3246  return prev() == NULL;
3247  }
3248 
3249  forceinline Advisor*
3250  Advisor::cast(ActorLink* al) {
3251  return static_cast<Advisor*>(al);
3252  }
3253 
3254  forceinline const Advisor*
3255  Advisor::cast(const ActorLink* al) {
3256  return static_cast<const Advisor*>(al);
3257  }
3258 
3259  forceinline Propagator&
3260  Advisor::propagator(void) const {
3261  assert(!disposed());
3262  return *Propagator::cast(ActorLink::prev());
3263  }
3264 
3265  template<class A>
3266  forceinline void
3268  assert(!disposed());
3269  ActorLink::prev(NULL);
3270  // Shorten chains of disposed advisors by one, if possible
3271  Advisor* n = Advisor::cast(next());
3272  if ((n != NULL) && n->disposed())
3273  next(n->next());
3274  }
3275 
3276  template<class A>
3279  a.dispose(*this,c);
3280  return ES_FIX;
3281  }
3282 
3283  template<class A>
3286  a.dispose(*this,c);
3287  return ES_NOFIX;
3288  }
3289 
3290  template<class A>
3293  a.dispose(*this,c);
3294  return ES_NOFIX_FORCE;
3295  }
3296 
3297 
3298 
3299  /*
3300  * Advisor council
3301  *
3302  */
3303  template<class A>
3304  forceinline
3306 
3307  template<class A>
3308  forceinline
3310  : advisors(NULL) {}
3311 
3312  template<class A>
3313  forceinline bool
3314  Council<A>::empty(void) const {
3315  ActorLink* a = advisors;
3316  while ((a != NULL) && static_cast<A*>(a)->disposed())
3317  a = a->next();
3318  advisors = a;
3319  return a == NULL;
3320  }
3321 
3322  template<class A>
3323  forceinline void
3324  Council<A>::update(Space& home, bool share, Council<A>& c) {
3325  // Skip all disposed advisors
3326  {
3327  ActorLink* a = c.advisors;
3328  while ((a != NULL) && static_cast<A*>(a)->disposed())
3329  a = a->next();
3330  c.advisors = a;
3331  }
3332  // Are there any advisors to be cloned?
3333  if (c.advisors != NULL) {
3334  // The propagator in from-space
3335  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
3336  // The propagator in to-space
3337  Propagator* p_t = Propagator::cast(p_f->prev());
3338  // Advisors in from-space
3339  ActorLink** a_f = &c.advisors;
3340  // Advisors in to-space
3341  A* a_t = NULL;
3342  while (*a_f != NULL) {
3343  if (static_cast<A*>(*a_f)->disposed()) {
3344  *a_f = (*a_f)->next();
3345  } else {
3346  // Run specific copying part
3347  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
3348  // Set propagator pointer
3349  a->prev(p_t);
3350  // Set forwarding pointer
3351  (*a_f)->prev(a);
3352  // Link
3353  a->next(a_t);
3354  a_t = a;
3355  a_f = (*a_f)->next_ref();
3356  }
3357  }
3358  advisors = a_t;
3359  // Enter advisor link for reset
3360  assert(p_f->u.advisors == NULL);
3361  p_f->u.advisors = c.advisors;
3362  } else {
3363  advisors = NULL;
3364  }
3365  }
3366 
3367  template<class A>
3368  forceinline void
3370  ActorLink* a = advisors;
3371  while (a != NULL) {
3372  if (!static_cast<A*>(a)->disposed())
3373  static_cast<A*>(a)->dispose(home,*this);
3374  a = a->next();
3375  }
3376  }
3377 
3378 
3379 
3380  /*
3381  * Advisor iterator
3382  *
3383  */
3384  template<class A>
3385  forceinline
3387  : a(c.advisors) {
3388  while ((a != NULL) && static_cast<A*>(a)->disposed())
3389  a = a->next();
3390  }
3391 
3392  template<class A>
3393  forceinline bool
3395  return a != NULL;
3396  }
3397 
3398  template<class A>
3399  forceinline void
3401  do {
3402  a = a->next();
3403  } while ((a != NULL) && static_cast<A*>(a)->disposed());
3404  }
3405 
3406  template<class A>
3407  forceinline A&
3408  Advisors<A>::advisor(void) const {
3409  return *static_cast<A*>(a);
3410  }
3411 
3412 
3413 
3414  /*
3415  * Space
3416  *
3417  */
3418  forceinline void
3419  Space::enqueue(Propagator* p) {
3420  ActorLink::cast(p)->unlink();
3421  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
3422  c->tail(ActorLink::cast(p));
3423  if (c > pc.p.active)
3424  pc.p.active = c;
3425  }
3426 
3427  forceinline void
3428  Space::fail(void) {
3429  /*
3430  * Now active points beyond the last queue. This is essential as
3431  * enqueuing a propagator in a failed space keeps the space
3432  * failed.
3433  */
3434  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
3435  }
3436  forceinline void
3437  Home::fail(void) {
3438  s.fail();
3439  }
3440 
3441  forceinline bool
3442  Space::failed(void) const {
3443  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
3444  }
3445  forceinline bool
3446  Home::failed(void) const {
3447  return s.failed();
3448  }
3449 
3450  forceinline bool
3451  Space::stable(void) const {
3452  return ((pc.p.active < &pc.p.queue[0]) ||
3453  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
3454  }
3455 
3456 
3457 
3458  /*
3459  * Variable implementation
3460  *
3461  */
3462  template<class VIC>
3465  assert((pc >= 0) && (pc < pc_max+2));
3466  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
3467  }
3468 
3469  template<class VIC>
3470  forceinline ActorLink**
3471  VarImp<VIC>::actorNonZero(PropCond pc) {
3472  assert((pc > 0) && (pc < pc_max+2));
3473  return b.base+u.idx[pc-1];
3474  }
3475 
3476  template<class VIC>
3477  forceinline unsigned int&
3479  assert((pc > 0) && (pc < pc_max+2));
3480  return u.idx[pc-1];
3481  }
3482 
3483  template<class VIC>
3484  forceinline unsigned int
3485  VarImp<VIC>::idx(PropCond pc) const {
3486  assert((pc > 0) && (pc < pc_max+2));
3487  return u.idx[pc-1];
3488  }
3489 
3490  template<class VIC>
3491  forceinline
3493  b.base = NULL; entries = 0;
3494  for (PropCond pc=1; pc<pc_max+2; pc++)
3495  idx(pc) = 0;
3496  free_and_bits = 0;
3497  }
3498 
3499  template<class VIC>
3500  forceinline
3502  b.base = NULL; entries = 0;
3503  for (PropCond pc=1; pc<pc_max+2; pc++)
3504  idx(pc) = 0;
3505  free_and_bits = 0;
3506  }
3507 
3508  template<class VIC>
3509  forceinline unsigned int
3510  VarImp<VIC>::degree(void) const {
3511  assert(!copied());
3512  return entries;
3513  }
3514 
3515  template<class VIC>
3516  forceinline double
3517  VarImp<VIC>::afc(const Space& home) const {
3518  double d = 0.0;
3519  // Count the afc of each propagator
3520  {
3521  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
3522  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3523  while (a < e) {
3524  d += Propagator::cast(*a)->afc(home); a++;
3525  }
3526  }
3527  // Count the afc of each advisor's propagator
3528  {
3529  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3530  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
3531  while (a < e) {
3532  d += Advisor::cast(*a)->propagator().afc(home); a++;
3533  }
3534  }
3535  return d;
3536  }
3537 
3538  template<class VIC>
3541  return d.me;
3542  }
3543 
3544  template<class VIC>
3545  forceinline unsigned int
3546  VarImp<VIC>::bits(void) const {
3547  return free_and_bits;
3548  }
3549 
3550  template<class VIC>
3551  forceinline unsigned int&
3553  return free_and_bits;
3554  }
3555 
3556 #ifdef GECODE_HAS_VAR_DISPOSE
3557  template<class VIC>
3559  VarImp<VIC>::vars_d(Space& home) {
3560  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
3561  }
3562 
3563  template<class VIC>
3564  forceinline void
3565  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
3566  home.vars_d<VIC>(x);
3567  }
3568 #endif
3569 
3570  template<class VIC>
3571  forceinline bool
3572  VarImp<VIC>::copied(void) const {
3573  return Support::marked(b.fwd);
3574  }
3575 
3576  template<class VIC>
3578  VarImp<VIC>::forward(void) const {
3579  assert(copied());
3580  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
3581  }
3582 
3583  template<class VIC>
3585  VarImp<VIC>::next(void) const {
3586  assert(copied());
3587  return u.next;
3588  }
3589 
3590  template<class VIC>
3591  forceinline
3593  VarImpBase** reg;
3594  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3595  if (x.b.base == NULL) {
3596  // Variable implementation needs no index structure
3597  reg = &home.pc.c.vars_noidx;
3598  assert(x.degree() == 0);
3599  } else {
3600  reg = &home.pc.c.vars_u[idx_c];
3601  }
3602  // Save subscriptions in copy
3603  b.base = x.b.base;
3604  entries = x.entries;
3605  for (PropCond pc=1; pc<pc_max+2; pc++)
3606  idx(pc) = x.idx(pc);
3607 
3608  // Set forwarding pointer
3609  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
3610  // Register original
3611  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
3612  }
3613 
3614  template<class VIC>
3617  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3618  }
3619 
3620  template<class VIC>
3623  return static_cast<ModEventDelta>(me << VIC::med_fst);
3624  }
3625 
3626  template<class VIC>
3629  return VIC::me_combine(me1,me2);
3630  }
3631 
3632  template<class VIC>
3633  forceinline void
3635  bool force) {
3636  if (VIC::med_update(p.u.med,me) || force)
3637  home.enqueue(&p);
3638  }
3639 
3640  template<class VIC>
3641  forceinline void
3643  ActorLink** b = actor(pc1);
3644  ActorLink** p = actorNonZero(pc2+1);
3645  while (p-- > b)
3646  schedule(home,*Propagator::cast(*p),me);
3647  }
3648 
3649  template<class VIC>
3650  forceinline void
3651  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
3652  assert(pc <= pc_max);
3653  // Count one new subscription
3654  home.pc.p.n_sub += 1;
3655  if ((free_and_bits >> free_bits) == 0)
3656  resize(home);
3657  free_and_bits -= 1 << free_bits;
3658 
3659  // Enter subscription
3660  b.base[entries] = *actorNonZero(pc_max+1);
3661  entries++;
3662  for (PropCond j = pc_max; j > pc; j--) {
3663  *actorNonZero(j+1) = *actorNonZero(j);
3664  idx(j+1)++;
3665  }
3666  *actorNonZero(pc+1) = *actor(pc);
3667  idx(pc+1)++;
3668  *actor(pc) = ActorLink::cast(p);
3669 
3670 #ifdef GECODE_AUDIT
3671  ActorLink** f = actor(pc);
3672  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
3673  if (*f == p)
3674  goto found;
3675  else
3676  f++;
3677  GECODE_NEVER;
3678  found: ;
3679 #endif
3680  }
3681 
3682  template<class VIC>
3683  forceinline void
3684  VarImp<VIC>::enter(Space& home, Advisor* a) {
3685  // Count one new subscription
3686  home.pc.p.n_sub += 1;
3687  if ((free_and_bits >> free_bits) == 0)
3688  resize(home);
3689  free_and_bits -= 1 << free_bits;
3690 
3691  // Enter subscription
3692  b.base[entries++] = *actorNonZero(pc_max+1);
3693  *actorNonZero(pc_max+1) = a;
3694  }
3695 
3696  template<class VIC>
3697  void
3698  VarImp<VIC>::resize(Space& home) {
3699  if (b.base == NULL) {
3700  assert((free_and_bits >> free_bits) == 0);
3701  // Create fresh dependency array with four entries
3702  free_and_bits += 4 << free_bits;
3703  b.base = home.alloc<ActorLink*>(4);
3704  for (int i=0; i<pc_max+1; i++)
3705  u.idx[i] = 0;
3706  } else {
3707  // Resize dependency array
3708  unsigned int n = degree();
3709  // Find out whether the area is most likely in the special area
3710  // reserved for subscriptions. If yes, just resize mildly otherwise
3711  // more agressively
3712  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
3713  unsigned int m =
3714  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
3715  (n+4) : ((n+1)*3>>1);
3716  ActorLink** prop = home.alloc<ActorLink*>(m);
3717  free_and_bits += (m-n) << free_bits;
3718  // Copy entries
3719  Heap::copy<ActorLink*>(prop, b.base, n);
3720  home.free<ActorLink*>(b.base,n);
3721  b.base = prop;
3722  }
3723  }
3724 
3725  template<class VIC>
3726  void
3728  bool assigned, ModEvent me, bool schedule) {
3729  if (assigned) {
3730  // Do not subscribe, just schedule the propagator
3731  if (schedule)
3733  } else {
3734  enter(home,&p,pc);
3735  // Schedule propagator
3736  if (schedule && (pc != PC_GEN_ASSIGNED))
3737  VarImp<VIC>::schedule(home,p,me);
3738  }
3739  }
3740 
3741  template<class VIC>
3742  forceinline void
3744  if (!assigned)
3745  enter(home,&a);
3746  }
3747 
3748  template<class VIC>
3749  forceinline void
3750  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
3751  assert(pc <= pc_max);
3752  ActorLink* a = ActorLink::cast(p);
3753  // Find actor in dependency array
3754  ActorLink** f = actor(pc);
3755 #ifdef GECODE_AUDIT
3756  while (f < actorNonZero(pc+1))
3757  if (*f == a)
3758  goto found;
3759  else
3760  f++;
3761  GECODE_NEVER;
3762  found: ;
3763 #else
3764  while (*f != a) f++;
3765 #endif
3766  // Remove actor
3767  *f = *(actorNonZero(pc+1)-1);
3768  for (PropCond j = pc+1; j< pc_max+1; j++) {
3769  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3770  idx(j)--;
3771  }
3772  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
3773  idx(pc_max+1)--;
3774  entries--;
3775  free_and_bits += 1 << free_bits;
3776  home.pc.p.n_sub -= 1;
3777  }
3778 
3779  template<class VIC>
3780  forceinline void
3781  VarImp<VIC>::remove(Space& home, Advisor* a) {
3782  // Find actor in dependency array
3783  ActorLink** f = actorNonZero(pc_max+1);
3784 #ifdef GECODE_AUDIT
3785  while (f < b.base+entries)
3786  if (*f == a)
3787  goto found;
3788  else
3789  f++;
3790  GECODE_NEVER;
3791  found: ;
3792 #else
3793  while (*f != a) f++;
3794 #endif
3795  // Remove actor
3796  *f = b.base[--entries];
3797  free_and_bits += 1 << free_bits;
3798  home.pc.p.n_sub -= 1;
3799  }
3800 
3801  template<class VIC>
3802  forceinline void
3804  if (!assigned)
3805  remove(home,&p,pc);
3806  }
3807 
3808  template<class VIC>
3809  forceinline void
3811  if (!assigned)
3812  remove(home,&a);
3813  }
3814 
3815  template<class VIC>
3816  forceinline void
3818  unsigned int n_sub = degree();
3819  home.pc.p.n_sub -= n_sub;
3820  unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3821  home.free<ActorLink*>(b.base,n);
3822  // Must be NULL such that cloning works
3823  b.base = NULL;
3824  // Must be 0 such that degree works
3825  entries = 0;
3826  }
3827 
3828  template<class VIC>
3829  forceinline bool
3831  /*
3832  * An advisor that is executed might remove itself due to subsumption.
3833  * As entries are removed from front to back, the advisors must
3834  * be iterated in forward direction.
3835  */
3836  ActorLink** la = actorNonZero(pc_max+1);
3837  ActorLink** le = b.base+entries;
3838  if (la == le)
3839  return true;
3840  d.me = me;
3841  // An advisor that is run, might be removed during execution.
3842  // As removal is done from the back the advisors have to be executed
3843  // in inverse order.
3844  do {
3845  Advisor* a = Advisor::cast(*la);
3846  assert(!a->disposed());
3847  Propagator& p = a->propagator();
3848  switch (p.advise(home,*a,d)) {
3849  case ES_FIX:
3850  break;
3851  case ES_FAILED:
3852  if (home.afc_enabled())
3853  home.gafc.fail(p.gafc);
3854  return false;
3855  case ES_NOFIX:
3856  schedule(home,p,me);
3857  break;
3858  case ES_NOFIX_FORCE:
3859  schedule(home,p,me,true);
3860  break;
3861  default:
3862  GECODE_NEVER;
3863  }
3864  } while (++la < le);
3865  return true;
3866  }
3867 
3868  template<class VIC>
3869  forceinline void
3871  // this refers to the variable to be updated (clone)
3872  // x refers to the original
3873  // Recover from copy
3874  x->b.base = b.base;
3875  x->u.idx[0] = u.idx[0];
3876  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
3877  x->u.idx[1] = u.idx[1];
3878 
3879  ActorLink** f = x->b.base;
3880  unsigned int n = x->degree();
3881  ActorLink** t = sub;
3882  sub += n;
3883  b.base = t;
3884  // Set subscriptions using actor forwarding pointers
3885  while (n >= 4) {
3886  n -= 4;
3887  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3888  t[2]=f[2]->prev(); t[3]=f[3]->prev();
3889  t += 4; f += 4;
3890  }
3891  if (n >= 2) {
3892  n -= 2;
3893  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3894  t += 2; f += 2;
3895  }
3896  if (n > 0) {
3897  t[0]=f[0]->prev();
3898  }
3899  }
3900 
3901  template<class VIC>
3902  forceinline void
3903  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3904  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
3905  while (x != NULL) {
3906  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
3907  }
3908  }
3909 
3910 
3911 
3912  /*
3913  * Variable disposer
3914  *
3915  */
3916  template<class VarImp>
3918 #ifdef GECODE_HAS_VAR_DISPOSE
3919  Space::vd[VarImp::idx_d] = this;
3920 #endif
3921  }
3922 
3923  template<class VarImp>
3924  void
3926  VarImp* x = static_cast<VarImp*>(_x);
3927  do {
3928  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
3929  } while (x != NULL);
3930  }
3931 
3932  /*
3933  * Statistics
3934  */
3935 
3936  forceinline void
3938  propagate = 0;
3939  wmp = false;
3940  }
3941  forceinline
3943  reset();
3944  }
3947  propagate += s.propagate;
3948  wmp |= s.wmp;
3949  return *this;
3950  }
3953  StatusStatistics t(s);
3954  return t += *this;
3955  }
3956 
3957  forceinline void
3959 
3960  forceinline
3962  reset();
3963  }
3966  CloneStatistics s;
3967  return s;
3968  }
3971  return *this;
3972  }
3973 
3974  forceinline void
3976 
3977  forceinline
3979  reset();
3980  }
3983  CommitStatistics s;
3984  return s;
3985  }
3988  return *this;
3989  }
3990 
3991  /*
3992  * Cost computation
3993  *
3994  */
3995 
3996  forceinline
3997  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
3998 
3999  forceinline PropCost
4000  PropCost::cost(PropCost::Mod m,
4002  unsigned int n) {
4003  if (n < 2)
4004  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4005  else if (n == 2)
4006  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4007  else if (n == 3)
4008  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4009  else
4010  return (m == LO) ? lo : hi;
4011  }
4012 
4013  forceinline PropCost
4014  PropCost::crazy(PropCost::Mod m, unsigned int n) {
4015  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
4016  }
4019  assert(n >= 0);
4020  return crazy(m,static_cast<unsigned int>(n));
4021  }
4023  PropCost::cubic(PropCost::Mod m, unsigned int n) {
4024  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
4025  }
4028  assert(n >= 0);
4029  return cubic(m,static_cast<unsigned int>(n));
4030  }
4032  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
4033  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
4034  }
4037  assert(n >= 0);
4038  return quadratic(m,static_cast<unsigned int>(n));
4039  }
4041  PropCost::linear(PropCost::Mod m, unsigned int n) {
4042  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
4043  }
4046  assert(n >= 0);
4047  return linear(m,static_cast<unsigned int>(n));
4048  }
4051  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
4052  }
4055  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
4056  }
4059  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
4060  }
4061 
4062  /*
4063  * Iterators for propagators and branchers of a space
4064  *
4065  */
4066  forceinline
4068  : home(home0), q(home.pc.p.active) {
4069  while (q >= &home.pc.p.queue[0]) {
4070  if (q->next() != q) {
4071  c = q->next(); e = q; q--;
4072  return;
4073  }
4074  q--;
4075  }
4076  q = NULL;
4077  if (!home.pl.empty()) {
4078  c = Propagator::cast(home.pl.next());
4079  e = Propagator::cast(&home.pl);
4080  } else {
4081  c = e = NULL;
4082  }
4083  }
4084  forceinline bool
4086  return c != NULL;
4087  }
4088  forceinline void
4090  c = c->next();
4091  if (c == e) {
4092  if (q == NULL) {
4093  c = NULL;
4094  } else {
4095  while (q >= &home.pc.p.queue[0]) {
4096  if (q->next() != q) {
4097  c = q->next(); e = q; q--;
4098  return;
4099  }
4100  q--;
4101  }
4102  q = NULL;
4103  if (!home.pl.empty()) {
4104  c = Propagator::cast(home.pl.next());
4105  e = Propagator::cast(&home.pl);
4106  } else {
4107  c = NULL;
4108  }
4109  }
4110  }
4111  }
4112  forceinline const Propagator&
4114  return *Propagator::cast(c);
4115  }
4116 
4117  forceinline
4119  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
4120  forceinline bool
4122  return c != e;
4123  }
4124  forceinline void
4126  c = c->next();
4127  }
4128  forceinline const Brancher&
4130  return *Brancher::cast(c);
4131  }
4132 
4133  /*
4134  * Space construction support
4135  *
4136  */
4137  template<class T>
4138  forceinline T&
4140  return alloc<T>(1);
4141  }
4142  template<class T, typename A1>
4143  forceinline T&
4144  Space::construct(A1 const& a1) {
4145  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4146  new (&t) T(a1);
4147  return t;
4148  }
4149  template<class T, typename A1, typename A2>
4150  forceinline T&
4151  Space::construct(A1 const& a1, A2 const& a2) {
4152  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4153  new (&t) T(a1,a2);
4154  return t;
4155  }
4156  template<class T, typename A1, typename A2, typename A3>
4157  forceinline T&
4158  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
4159  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4160  new (&t) T(a1,a2,a3);
4161  return t;
4162  }
4163  template<class T, typename A1, typename A2, typename A3, typename A4>
4164  forceinline T&
4165  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
4166  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4167  new (&t) T(a1,a2,a3,a4);
4168  return t;
4169  }
4170  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
4171  forceinline T&
4172  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
4173  T& t = *static_cast<T*>(ralloc(sizeof(T)));
4174  new (&t) T(a1,a2,a3,a4,a5);
4175  return t;
4176  }
4177 
4178 }
4179 
4180 // STATISTICS: kernel-core
static const int med_lst
End of bits for modification event delta.
Definition: core.hpp:195
virtual Object * copy(void) const =0
Return fresh copy for update.
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
unsigned long int ng(void) const
Return number of no-goods posted.
Definition: core.hpp:2686
void reset(void)
Reset information.
Definition: core.hpp:3958
bool operator()(void) const
Test whether there are branchers left.
Definition: core.hpp:4121
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:158
bool marked(void *p)
Check whether p is marked.
Council of advisors
Definition: core.hpp:226
SharedHandle(void)
Create shared handle with no object pointing to.
Definition: core.hpp:2639
Base-class for variable implementations.
Definition: core.hpp:228
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Space must be branched (at least one brancher left)
Definition: core.hpp:1303
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4032
The shared handle.
Definition: core.hpp:79
Three variables, expensive.
Definition: core.hpp:550
Propagators(const Space &home)
Initialize.
Definition: core.hpp:4067
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
unsigned int branch_id
Id of next brancher to be created.
Definition: core.hpp:1429
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
LocalObject(Home home)
Constructor for creation.
Definition: core.hpp:3125
const Propagator & propagator(void) const
Return propagator.
Definition: core.hpp:4113
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
VarImp(void)
Creation of static instances.
Definition: core.hpp:3501
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
void update(Space &home, bool share, Council< A > &c)
Update during cloning (copies all advisors)
Definition: core.hpp:3324
VarImpDisposer(void)
Constructor (registers disposer with kernel)
Definition: core.hpp:3917
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition: core.hpp:341
unsigned long int fail(void) const
Return number of failures since last restart.
Definition: core.hpp:2717
NGL * next(void) const
Return pointer to next literal.
Definition: core.hpp:3196
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
Actor must always be disposed.
Definition: core.hpp:610
double afc(const Space &home) const
Return accumulated failure count (plus degree)
Definition: core.hpp:3517
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:768
Three variables, cheap.
Definition: core.hpp:552
NGL(void)
Constructor for creation.
Definition: core.hpp:3215
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:84
static const int free_bits
Freely available bits.
Definition: core.hpp:191
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2854
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:2872
SpaceStatus
Space status
Definition: core.hpp:1300
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition: core.hpp:2986
Handle for brancher.
Definition: core.hpp:1157
Manage memory for space.
Branchers(const Space &home)
Initialize.
Definition: core.hpp:4118
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from the space heap...
Definition: core.hpp:2448
Quadratic complexity, expensive.
Definition: core.hpp:547
friend class ActorLink
Definition: core.hpp:667
Statistics for execution of commit
Definition: core.hpp:1346
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:153
AFC afc
Definition: afc.cpp:139
Local (space-shared) object.
Definition: core.hpp:1183
friend class ActorLink
Definition: core.hpp:1072
Status
The status of a no-good literal.
Definition: core.hpp:977
A & advisor(void) const
Return advisor.
Definition: core.hpp:3408
int ModEvent
Type for modification events.
Definition: core.hpp:146
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Definition: core.hpp:3634
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: core.hpp:3540
Base-class for propagators.
Definition: core.hpp:755
Internal: propagator is subsumed, do not use.
Definition: core.hpp:524
Expensive.
Definition: core.hpp:564
virtual ~Choice(void)
Destructor.
Definition: core.hpp:3183
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
T & construct(void)
Construction routines.
Definition: core.hpp:4139
Base-class for advisors.
Definition: core.hpp:926
Quadratic complexity, cheap.
Definition: core.hpp:546
static const int idx_d
Index for disposal.
Definition: core.hpp:187
bool wmp
Whether a weakly monotonic propagator might have been executed.
Definition: core.hpp:1315
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:3622
LocalObject * object(void) const
Access to the local object.
Definition: core.hpp:3155
ActorLink ** base
Subscribed actors.
Definition: core.hpp:303
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition: core.hpp:3285
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition: core.hpp:339
Class to iterate over advisors of a council.
Definition: core.hpp:227
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3173
Handle to region.
Definition: region.hpp:61
void reuse(void *p, size_t s)
Store for reusal, if of sufficient size for free list.
void * mark(void *p)
Return marked pointer for p.
Base-class for variable implementations.
Definition: core.hpp:243
LocalObject * local
Linked list of local objects.
Definition: core.hpp:1442
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1313
Propagation has computed fixpoint.
Definition: core.hpp:528
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
const Space * l
Last solution found.
Definition: core.hpp:1274
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition: core.hpp:4058
Current restart information during search.
Definition: core.hpp:1265
Computation spaces.
Definition: core.hpp:1362
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:245
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition: core.hpp:3148
Two variables, cheap.
Definition: core.hpp:553
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3442
void * rrealloc(void *b, size_t n, size_t m)
Reallocate memory block starting at b from size n to size s.
Definition: core.hpp:2367
Linear complexity, expensive.
Definition: core.hpp:548
Base-class for both propagators and branchers.
Definition: core.hpp:666
Statistics for execution of status
Definition: core.hpp:1310
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition: core.hpp:3817
Heap heap
The single global heap.
Definition: heap.cpp:49
void fail(Counter &c)
Increment failure count.
Definition: global-afc.hpp:317
Gecode::IntSet d(v, 7)
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3090
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition: core.hpp:3965
bool operator()(const Space &home) const
Check whether brancher is still active.
Definition: core.hpp:3094
const unsigned long int r
Number of restarts.
Definition: core.hpp:1268
The literal is subsumed.
Definition: core.hpp:979
Gecode::FloatVal c(-8, 8)
bool operator()(void) const
Test whether there are propagators left.
Definition: core.hpp:4085
Exponential complexity, cheap.
Definition: core.hpp:542
Configuration class for variable implementations without index structure.
Definition: core.hpp:182
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Handles for local (space-shared) objects.
Definition: core.hpp:1210
Class to iterate over branchers of a space.
Definition: core.hpp:2290
double afc(const Space &home) const
Return the accumlated failure count.
Definition: core.hpp:2962
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1071
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:2721
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:44
bool copied(void) const
Is variable already copied.
Definition: core.hpp:3572
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition: core.hpp:2931
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition: core.hpp:3970
void reset(void)
Reset information.
Definition: core.hpp:3975
unsigned long int solution(void) const
Return number of solutions since last restart.
Definition: core.hpp:2713
void reset(void)
Reset information.
Definition: core.hpp:3937
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:3616
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer)
Definition: core.hpp:3109
Execution has resulted in failure.
Definition: core.hpp:525
StatusStatistics(void)
Initialize.
Definition: core.hpp:3942
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Statistics for execution of clone
Definition: core.hpp:1330
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:74
virtual ~NoGoods(void)
Destructor.
Definition: core.hpp:2694
SharedHandle & operator=(const SharedHandle &sh)
Assignment operator maintaining reference count.
Definition: core.hpp:2649
const unsigned long int f
Number of failures since last restart.
Definition: core.hpp:1272
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:764
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:2862
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1431
void fail(void)
Fail space.
Definition: core.hpp:3428
static const int idx_c
Index for update.
Definition: core.hpp:185
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition: core.hpp:205
friend class ActorLink
Definition: core.hpp:756
static const int med_mask
Bitmask for modification event delta.
Definition: core.hpp:197
unsigned int size(I &i)
Size of all ranges of range iterator i.
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition: core.hpp:2967
CloneStatistics(void)
Initialize.
Definition: core.hpp:3961
LocalHandle(void)
Create local handle pointing to NULL object.
Definition: core.hpp:3142
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition: core.hpp:160
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:3451
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.hpp:3925
Propagator & propagator(void) const
Return the advisor's propagator.
Definition: core.hpp:3260
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:766
bool operator()(void) const
Test whether there advisors left.
Definition: core.hpp:3394
struct Gecode::Space::@52::@53 p
Data only available during propagation.
Council(void)
Default constructor.
Definition: core.hpp:3305
Only single variable, expensive.
Definition: core.hpp:555
LocalObject * fwd(Space &home, bool share)
Return forwarding pointer.
Definition: core.hpp:3135
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition: core.hpp:3278
void * alloc(SharedMemory *sm, size_t s)
Allocate memory of size s.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
Home & operator=(const Home &h)
Assignment operator.
Definition: core.hpp:2889
Class for storing timed-decay value.
Definition: global-afc.hpp:46
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition: core.hpp:2957
unsigned long int restart(void) const
Return number of restarts.
Definition: core.hpp:2709
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition: core.hpp:3169
Exception: too many branchers
Definition: exception.hpp:83
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition: core.hpp:2979
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
Single _b(1, 4)
const unsigned long int s
Number of solutions since last restart.
Definition: core.hpp:1270
struct Gecode::Space::@52::@54 c
Data available only during copying.
~SharedHandle(void)
Destructor that maintains reference count.
Definition: core.hpp:2672
void update(Space &home, bool share, LocalHandle &lh)
Updating during cloning.
Definition: core.hpp:3159
Advisor forces rescheduling of propagator.
Definition: core.hpp:529
NoGoods(void)
Initialize.
Definition: core.hpp:2683
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2423
Class to iterate over propagators of a space.
Definition: core.hpp:2264
Mod
Propagation cost modifier.
Definition: core.hpp:562
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
Globally shared object for propagator information.
Definition: global-afc.hpp:43
BrancherHandle bh
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:2656
void update(Space &home, bool share, BrancherHandle &bh)
Update during cloning.
Definition: core.hpp:3086
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition: print.hpp:67
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors)
Definition: core.hpp:3510
void * ralloc(size_t s)
Allocate memory on space heap.
Definition: core.hpp:2359
Linear complexity, cheap.
Definition: core.hpp:549
bool empty(void) const
Test whether council has advisor left.
Definition: core.hpp:3314
ActualCost ac
Actual cost.
Definition: core.hpp:559
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition: core.hpp:2898
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4023
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition: core.hpp:3982
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
const NoGoods & ng
No-goods from restart.
Definition: core.hpp:1276
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
Brancher(Home home)
Constructor for creation.
Definition: core.hpp:3015
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition: core.hpp:2902
virtual ~Object(void)
Delete shared object.
Definition: core.hpp:2614
VarImp * next(void) const
Return next copied variable.
Choice for performing commit
Definition: core.hpp:1036
Cubic complexity, expensive.
Definition: core.hpp:545
The literal is failed.
Definition: core.hpp:978
No-goods recorded from restarts.
Definition: core.hpp:1240
SharedHandle::Object * object(void) const
Access to the shared object.
Definition: core.hpp:2619
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition: core.hpp:3267
Propagation cost.
Definition: core.hpp:537
void operator++(void)
Move iterator to next advisor.
Definition: core.hpp:3400
Archive representation
Definition: archive.hpp:45
#define GECODE_KERNEL_REALLOC(T)
Definition: core.hpp:2483
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition: core.hpp:3234
ExecStatus
Definition: core.hpp:523
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition: var-type.hpp:889
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition: core.hpp:3987
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
void operator++(void)
Move iterator to next propagator.
Definition: core.hpp:4089
CRI(unsigned long int r, unsigned long int s, unsigned long int f, const Space *l, NoGoods &ng)
Constructor.
Definition: core.hpp:2701
#define forceinline
Definition: config.hpp:132
const Brancher & brancher(void) const
Return propagator.
Definition: core.hpp:4129
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition: core.hpp:4014
Two variables, expensive.
Definition: core.hpp:551
SharedHandle::Object * shared
Linked list of shared objects.
Definition: core.hpp:1440
Space & s
The space where the propagator is to be posted.
Definition: core.hpp:720
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1258
static const PropCond pc_max
Maximal propagation condition.
Definition: core.hpp:189
void operator++(void)
Move iterator to next brancher.
Definition: core.hpp:4125
Base-class for freelist-managed objects.
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition: core.hpp:2867
Advisors(const Council< A > &c)
Initialize.
Definition: core.hpp:3386
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:530
Variable implementation disposer
Definition: core.hpp:266
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2387
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition: core.hpp:151
The shared object.
Definition: core.hpp:88
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
VarImp< VIC > * fwd
Forwarding pointer.
Definition: core.hpp:312
Execution is okay.
Definition: core.hpp:527
virtual size_t dispose(Space &home)
Dispose.
Definition: core.hpp:3224
Propagation has not computed fixpoint.
Definition: core.hpp:526
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition: core.hpp:722
void fail(void)
Mark space as failed.
Definition: core.hpp:3437
Maximal cost value.
Definition: core.hpp:556
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition: core.hpp:3208
unsigned int bits(void) const
Provide access to free bits.
Definition: core.hpp:3546
Propagator * propagator(void) const
Return propagator (or NULL) for currently rewritten propagator.
Definition: core.hpp:2906
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition: core.hpp:3952
#define GECODE_NOT_NULL(p)
Assert that a pointer is never NULL.
Definition: macros.hpp:79
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition: core.hpp:4050
unsigned int id(void) const
Return unsigned brancher id.
Definition: core.hpp:3036
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:2725
Propagator(Home home)
Constructor for posting.
Definition: core.hpp:2936
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition: core.hpp:3628
bool leaf(void) const
Test whether literal is a leaf.
Definition: core.hpp:3192
BrancherHandle(void)
Create handle as unitialized.
Definition: core.hpp:3080
ActorLink * active
Cost level with next propagator to be executed.
Definition: core.hpp:1425
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition: core.hpp:1438
ActualCost
The actual cost values that are used.
Definition: core.hpp:541
ActorProperty
Actor properties.
Definition: core.hpp:601
Only single variable, cheap.
Definition: core.hpp:554
Space is failed
Definition: core.hpp:1301
unsigned long int n
Number of no-goods.
Definition: core.hpp:1243
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition: core.hpp:2382
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
Home class for posting propagators
Definition: core.hpp:717
void dispose(Space &home)
Dispose council.
Definition: core.hpp:3369
static const int med_fst
Start of bits for modification event delta.
Definition: core.hpp:193
void kill(Space &home)
Kill the brancher.
Definition: core.hpp:3098
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition: core.hpp:4054
Shared object for several memory areas.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Object(void)
Initialize.
Definition: core.hpp:2611
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition: core.hpp:209
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition: core.hpp:3946
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool advise(Space &home, ModEvent me, Delta &d)
Run advisors when variable implementation has been modified with modification event me and domain cha...
Definition: core.hpp:3830
CommitStatistics(void)
Initialize.
Definition: core.hpp:3978
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:3578
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition: core.hpp:149
Base class for Variable type disposer.
Definition: core.hpp:251
ExecStatus ES_NOFIX_DISPOSE_FORCE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be forcefully rescheduled
Definition: core.hpp:3292
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:93
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2363
Home(Space &s, Propagator *p=NULL)
Initialize the home with space s and propagator p.
Definition: core.hpp:2887
Cubic complexity, cheap.
Definition: core.hpp:544
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: core.hpp:3727
void decay(double d)
Set decay factor to d.
Definition: global-afc.hpp:353
Exponential complexity, expensive.
Definition: core.hpp:543
Space is solved (no brancher left)
Definition: core.hpp:1302
No-good literal recorded during search.
Definition: core.hpp:971
~LocalHandle(void)
Destructor.
Definition: core.hpp:3153