Generated on Thu Feb 14 2013 20:59:45 for Gecode by doxygen 1.8.3.1
core.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  * Mikael Lagerkvist <lagerkvist@gecode.org>
7  *
8  * Contributing authors:
9  * Filip Konvicka <filip.konvicka@logis.cz>
10  *
11  * Copyright:
12  * Christian Schulte, 2002
13  * Guido Tack, 2003
14  * Mikael Lagerkvist, 2006
15  * LOGIS, s.r.o., 2009
16  *
17  * Bugfixes provided by:
18  * Alexander Samoilov <alexander_samoilov@yahoo.com>
19  *
20  * Last modified:
21  * $Date: 2012-02-22 16:18:28 +1100 (Wed, 22 Feb 2012) $ by $Author: tack $
22  * $Revision: 12538 $
23  *
24  * This file is part of Gecode, the generic constraint
25  * development environment:
26  * http://www.gecode.org
27  *
28  * Permission is hereby granted, free of charge, to any person obtaining
29  * a copy of this software and associated documentation files (the
30  * "Software"), to deal in the Software without restriction, including
31  * without limitation the rights to use, copy, modify, merge, publish,
32  * distribute, sublicense, and/or sell copies of the Software, and to
33  * permit persons to whom the Software is furnished to do so, subject to
34  * the following conditions:
35  *
36  * The above copyright notice and this permission notice shall be
37  * included in all copies or substantial portions of the Software.
38  *
39  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
41  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
43  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
44  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
45  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
46  *
47  */
48 #include <iostream>
49 namespace Gecode {
50 
51  class Space;
52 
77  class SharedHandle {
78  public:
86  class Object {
87  friend class Space;
88  friend class SharedHandle;
89  private:
91  Object* next;
93  Object* fwd;
95  unsigned int use_cnt;
96  public:
98  Object(void);
100  virtual Object* copy(void) const = 0;
102  virtual ~Object(void);
104  static void* operator new(size_t s);
106  static void operator delete(void* p);
107  };
108  private:
110  Object* o;
112  void subscribe(void);
114  void cancel(void);
115  public:
117  SharedHandle(void);
121  SharedHandle(const SharedHandle& sh);
125  void update(Space& home, bool share, SharedHandle& sh);
127  ~SharedHandle(void);
128  protected:
130  SharedHandle::Object* object(void) const;
132  void object(SharedHandle::Object* n);
133  };
134 
143 
144  typedef int ModEvent;
145 
152 
154  typedef int PropCond;
156  const PropCond PC_GEN_NONE = -1;
160 
171  typedef int ModEventDelta;
172 
173 }
174 
176 
177 namespace Gecode {
178 
181  public:
183  static const int idx_c = -1;
185  static const int idx_d = -1;
189  static const int free_bits = 0;
191  static const int med_fst = 0;
193  static const int med_lst = 0;
195  static const int med_mask = 0;
197  static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
199  static bool med_update(ModEventDelta& med, ModEvent me);
200  };
201 
204  GECODE_NEVER; return 0;
205  }
206  forceinline bool
208  GECODE_NEVER; return false;
209  }
210 
211 
212  /*
213  * These are the classes of interest
214  *
215  */
216  class ActorLink;
217  class Actor;
218  class Propagator;
219  class LocalObject;
220  class Advisor;
221  template<class A> class Council;
222  template<class A> class Advisors;
223  template<class VIC> class VarImp;
224 
225 
226  /*
227  * Variable implementations
228  *
229  */
230 
238  class VarImpBase {};
239 
247  public:
249  GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
252  };
253 
260  template<class VarImp>
262  public:
264  VarImpDisposer(void);
266  virtual void dispose(Space& home, VarImpBase* x);
267  };
268 
270  class Delta {
271  template<class VIC> friend class VarImp;
272  private:
274  ModEvent me;
275  };
276 
284  template<class VIC>
285  class VarImp : public VarImpBase {
286  friend class Space;
287  friend class Propagator;
288  template<class VarImp> friend class VarImpDisposer;
289  private:
290  union {
308  } b;
309 
311  static const int idx_c = VIC::idx_c;
313  static const int idx_d = VIC::idx_d;
315  static const int free_bits = VIC::free_bits;
317  unsigned int entries;
319  unsigned int free_and_bits;
321  static const Gecode::PropCond pc_max = VIC::pc_max;
322 
323  union {
334  unsigned int idx[pc_max+1];
337  } u;
338 
340  ActorLink** actor(PropCond pc);
342  ActorLink** actorNonZero(PropCond pc);
344  unsigned int& idx(PropCond pc);
346  unsigned int idx(PropCond pc) const;
347 
354  void update(VarImp* x, ActorLink**& sub);
361  static void update(Space& home, ActorLink**& sub);
362 
364  void enter(Space& home, Propagator* p, PropCond pc);
366  void enter(Space& home, Advisor* a);
368  void resize(Space& home);
370  void remove(Space& home, Propagator* p, PropCond pc);
372  void remove(Space& home, Advisor* a);
373 
374 
375  protected:
377  void cancel(Space& home);
383  bool advise(Space& home, ModEvent me, Delta& d);
384 #ifdef GECODE_HAS_VAR_DISPOSE
385 
386  static VarImp<VIC>* vars_d(Space& home);
388  static void vars_d(Space& home, VarImp<VIC>* x);
389 #endif
390 
391  public:
393  VarImp(Space& home);
395  VarImp(void);
396 
398 
399 
411  void subscribe(Space& home, Propagator& p, PropCond pc,
412  bool assigned, ModEvent me, bool schedule);
418  void cancel(Space& home, Propagator& p, PropCond pc,
419  bool assigned);
425  void subscribe(Space& home, Advisor& a, bool assigned);
431  void cancel(Space& home, Advisor& a, bool assigned);
432 
439  unsigned int degree(void) const;
446  double afc(void) const;
448 
450 
451 
452  VarImp(Space& home, bool share, VarImp& x);
454  bool copied(void) const;
456  VarImp* forward(void) const;
458  VarImp* next(void) const;
460 
462 
463 
470  static void schedule(Space& home, Propagator& p, ModEvent me,
471  bool force = false);
473  static ModEvent me(const ModEventDelta& med);
475  static ModEventDelta med(ModEvent me);
477  static ModEvent me_combine(ModEvent me1, ModEvent me2);
479 
481 
482 
483  static ModEvent modevent(const Delta& d);
485 
487 
488 
489  unsigned int bits(void) const;
491  unsigned int& bits(void);
493 
494  protected:
496  void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
497 
498  public:
500 
501 
502  static void* operator new(size_t,Space&);
504  static void operator delete(void*,Space&);
506  static void operator delete(void*);
508  };
509 
518  enum ExecStatus {
520  ES_FAILED = -1,
521  ES_NOFIX = 0,
522  ES_OK = 0,
523  ES_FIX = 1,
526  };
527 
532  class PropCost {
533  friend class Space;
534  public:
536  enum ActualCost {
551  AC_MAX = 6
552  };
555  public:
557  enum Mod {
558  LO,
559  HI
560  };
561  private:
563  static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
566  public:
568  static PropCost crazy(PropCost::Mod m, unsigned int n);
570  static PropCost crazy(PropCost::Mod m, int n);
572  static PropCost cubic(PropCost::Mod m, unsigned int n);
574  static PropCost cubic(PropCost::Mod m, int n);
576  static PropCost quadratic(PropCost::Mod m, unsigned int n);
578  static PropCost quadratic(PropCost::Mod m, int n);
580  static PropCost linear(PropCost::Mod m, unsigned int n);
582  static PropCost linear(PropCost::Mod m, int n);
586  static PropCost binary(PropCost::Mod m);
588  static PropCost unary(PropCost::Mod m);
589  };
590 
591 
605  AP_DISPOSE = (1 << 0),
611  AP_WEAKLY = (1 << 1)
612  };
613 
614 
622  class ActorLink {
623  friend class Actor;
624  friend class Propagator;
625  friend class Advisor;
626  friend class Brancher;
627  friend class LocalObject;
628  friend class Space;
629  template<class VIC> friend class VarImp;
630  private:
631  ActorLink* _next; ActorLink* _prev;
632  public:
634 
635  ActorLink* prev(void) const; void prev(ActorLink*);
636  ActorLink* next(void) const; void next(ActorLink*);
637  ActorLink** next_ref(void);
639 
641  void init(void);
643  void unlink(void);
645  void head(ActorLink* al);
647  void tail(ActorLink* al);
649  bool empty(void) const;
651  template<class T> static ActorLink* cast(T* a);
653  template<class T> static const ActorLink* cast(const T* a);
654  };
655 
656 
662  friend class ActorLink;
663  friend class Space;
664  friend class Propagator;
665  friend class Advisor;
666  friend class Brancher;
667  friend class LocalObject;
668  template<class VIC> friend class VarImp;
669  template<class A> friend class Council;
670  private:
672  static Actor* cast(ActorLink* al);
674  static const Actor* cast(const ActorLink* al);
675  public:
677  virtual Actor* copy(Space& home, bool share) = 0;
678 
680 
681 
683  virtual size_t allocated(void) const;
686  virtual size_t dispose(Space& home);
688  static void* operator new(size_t s, Space& home);
690  static void operator delete(void* p, Space& home);
691  private:
692 #ifndef __GNUC__
693 
694  static void operator delete(void* p);
695 #endif
696 
697  static void* operator new(size_t s);
699 #ifdef __GNUC__
700  public:
702  GECODE_KERNEL_EXPORT virtual ~Actor(void);
704  static void operator delete(void* p);
705 #endif
706  };
707 
708 
709 
713  class Home {
714  protected:
719  public:
721 
722 
723  Home(Space& s, Propagator* p=NULL);
725  operator Space&(void);
727 
728 
729 
732  Propagator* propagator(void) const;
734 
735 
736 
737  bool failed(void) const;
739  void fail(void);
741  void notice(Actor& a, ActorProperty p);
743  };
744 
750  friend class ActorLink;
751  friend class Space;
752  template<class VIC> friend class VarImp;
753  friend class Advisor;
754  template<class A> friend class Council;
755  private:
756  union {
760  size_t size;
763  } u;
765  PropInfo& pi;
767  static Propagator* cast(ActorLink* al);
769  static const Propagator* cast(const ActorLink* al);
770  protected:
772  Propagator(Home home);
774  Propagator(Space& home, bool share, Propagator& p);
775 
776  public:
778 
779 
802  virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
804  virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
812  ModEventDelta modeventdelta(void) const;
849  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
851 
852 
853 
854  double afc(void) const;
856  };
857 
858 
866  template<class A>
867  class Council {
868  friend class Advisor;
869  friend class Advisors<A>;
870  private:
872  mutable ActorLink* advisors;
873  public:
875  Council(void);
877  Council(Space& home);
879  bool empty(void) const;
881  void update(Space& home, bool share, Council<A>& c);
883  void dispose(Space& home);
884  };
885 
886 
891  template<class A>
892  class Advisors {
893  private:
895  ActorLink* a;
896  public:
898  Advisors(const Council<A>& c);
900  bool operator ()(void) const;
902  void operator ++(void);
904  A& advisor(void) const;
905  };
906 
907 
918  class Advisor : private ActorLink {
919  template<class VIC> friend class VarImp;
920  template<class A> friend class Council;
921  template<class A> friend class Advisors;
922  private:
924  bool disposed(void) const;
926  static Advisor* cast(ActorLink* al);
928  static const Advisor* cast(const ActorLink* al);
929  protected:
931  Propagator& propagator(void) const;
932  public:
934  template<class A>
935  Advisor(Space& home, Propagator& p, Council<A>& c);
937  Advisor(Space& home, bool share, Advisor& a);
938 
940 
941 
942  template<class A>
943  void dispose(Space& home, Council<A>& c);
945  static void* operator new(size_t s, Space& home);
947  static void operator delete(void* p, Space& home);
949  private:
950 #ifndef __GNUC__
951 
952  static void operator delete(void* p);
953 #endif
954 
955  static void* operator new(size_t s);
956  };
957 
958 
959  class Brancher;
970  friend class Space;
971  private:
972  unsigned int _id;
973  unsigned int _alt;
974 
976  unsigned int id(void) const;
977  protected:
979  Choice(const Brancher& b, const unsigned int a);
980  public:
982  unsigned int alternatives(void) const;
984  GECODE_KERNEL_EXPORT virtual ~Choice(void);
986  virtual size_t size(void) const = 0;
988  static void* operator new(size_t);
990  static void operator delete(void*);
992  GECODE_KERNEL_EXPORT virtual void archive(Archive& e) const;
993  };
994 
1005  friend class ActorLink;
1006  friend class Space;
1007  friend class Choice;
1008  private:
1010  unsigned int _id;
1012  static Brancher* cast(ActorLink* al);
1014  static const Brancher* cast(const ActorLink* al);
1015  protected:
1017  Brancher(Home home);
1019  Brancher(Space& home, bool share, Brancher& b);
1020  public:
1022 
1023 
1031  virtual bool status(const Space& home) const = 0;
1039  virtual const Choice* choice(Space& home) = 0;
1041  virtual const Choice* choice(const Space& home, Archive& e) = 0;
1048  virtual ExecStatus commit(Space& home, const Choice& c,
1049  unsigned int a) = 0;
1051  unsigned int id(void) const;
1053  };
1054 
1062  class LocalObject : public Actor {
1063  friend class ActorLink;
1064  friend class Space;
1065  friend class LocalHandle;
1066  protected:
1068  LocalObject(Home home);
1070  LocalObject(Space& home, bool share, LocalObject& l);
1072  static LocalObject* cast(ActorLink* al);
1074  static const LocalObject* cast(const ActorLink* al);
1075  private:
1077  GECODE_KERNEL_EXPORT void fwdcopy(Space& home, bool share);
1078  public:
1080  LocalObject* fwd(Space& home, bool share);
1081  };
1082 
1089  class LocalHandle {
1090  private:
1092  LocalObject* o;
1093  protected:
1095  LocalHandle(void);
1097  LocalHandle(LocalObject* lo);
1099  LocalHandle(const LocalHandle& lh);
1100  public:
1102  LocalHandle& operator =(const LocalHandle& lh);
1104  void update(Space& home, bool share, LocalHandle& lh);
1106  ~LocalHandle(void);
1107  protected:
1109  LocalObject* object(void) const;
1111  void object(LocalObject* n);
1112  };
1113 
1114 
1123  };
1124 
1130  public:
1132  unsigned long int propagate;
1134  bool wmp;
1136  StatusStatistics(void);
1138  void reset(void);
1143  };
1144 
1150  public:
1152  CloneStatistics(void);
1154  void reset(void);
1159  };
1160 
1166  public:
1168  CommitStatistics(void);
1170  void reset(void);
1175  };
1176 
1181  friend class Actor;
1182  friend class Propagator;
1183  friend class Brancher;
1184  friend class Advisor;
1185  template<class VIC> friend class VarImp;
1186  template<class VarImp> friend class VarImpDisposer;
1187  friend class SharedHandle;
1188  friend class LocalObject;
1189  friend class Region;
1190  private:
1192  SharedMemory* sm;
1194  MemoryManager mm;
1196  GlobalPropInfo gpi;
1198  ActorLink pl;
1200  ActorLink bl;
1206  Brancher* b_status;
1218  Brancher* b_commit;
1219  union {
1221  struct {
1238  unsigned int branch_id;
1240  unsigned int n_sub;
1241  } p;
1243  struct {
1252  } c;
1253  } pc;
1255  void enqueue(Propagator* p);
1260 #ifdef GECODE_HAS_VAR_DISPOSE
1261 
1262  GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1264  VarImpBase* _vars_d[AllVarConf::idx_d];
1266  template<class VIC> VarImpBase* vars_d(void) const;
1268  template<class VIC> void vars_d(VarImpBase* x);
1269 #endif
1270 
1271  void update(ActorLink** sub);
1273 
1275  Actor** d_fst;
1277  Actor** d_cur;
1279  Actor** d_lst;
1281  GECODE_KERNEL_EXPORT void d_resize(void);
1282 
1290  unsigned int n_wmp;
1291 
1293  GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1295  GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1297  GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1299  GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
1301  GECODE_KERNEL_EXPORT static bool unused_b;
1302 
1317  GECODE_KERNEL_EXPORT Space* _clone(bool share=true);
1318 
1352  void _commit(const Choice& c, unsigned int a);
1353 
1354  public:
1359  GECODE_KERNEL_EXPORT Space(void);
1364  GECODE_KERNEL_EXPORT virtual ~Space(void);
1375  GECODE_KERNEL_EXPORT Space(bool share, Space& s);
1382  virtual Space* copy(bool share) = 0;
1394  GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
1399  static void* operator new(size_t);
1404  static void operator delete(void*);
1405 
1406 
1407  /*
1408  * Member functions for search engines
1409  *
1410  */
1411 
1424  SpaceStatus status(StatusStatistics& stat=unused_status);
1425 
1458  const Choice* choice(void);
1459 
1470  const Choice* choice(Archive& e) const;
1471 
1489  Space* clone(bool share=true, CloneStatistics& stat=unused_clone) const;
1490 
1525  void commit(const Choice& c, unsigned int a,
1526  CommitStatistics& stat=unused_commit);
1527 
1535  void notice(Actor& a, ActorProperty p);
1543  void ignore(Actor& a, ActorProperty p);
1544 
1545 
1556  ExecStatus ES_SUBSUMED(Propagator& p);
1571  ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s);
1582  ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1593  ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med);
1594 
1605  template<class A>
1606  ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a);
1617  template<class A>
1618  ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a);
1630  template<class A>
1631  ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a);
1632 
1640  void fail(void);
1649  bool failed(void) const;
1654  bool stable(void) const;
1661  GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
1668  GECODE_KERNEL_EXPORT unsigned int branchers(void) const;
1669 
1671 
1672 
1673  Home operator ()(Propagator& p);
1675 
1687  template<class T>
1688  T* alloc(long unsigned int n);
1695  template<class T>
1696  T* alloc(long int n);
1703  template<class T>
1704  T* alloc(unsigned int n);
1711  template<class T>
1712  T* alloc(int n);
1722  template<class T>
1723  void free(T* b, long unsigned int n);
1733  template<class T>
1734  void free(T* b, long int n);
1744  template<class T>
1745  void free(T* b, unsigned int n);
1755  template<class T>
1756  void free(T* b, int n);
1768  template<class T>
1769  T* realloc(T* b, long unsigned int n, long unsigned int m);
1781  template<class T>
1782  T* realloc(T* b, long int n, long int m);
1794  template<class T>
1795  T* realloc(T* b, unsigned int n, unsigned int m);
1807  template<class T>
1808  T* realloc(T* b, int n, int m);
1816  template<class T>
1817  T** realloc(T** b, long unsigned int n, long unsigned int m);
1825  template<class T>
1826  T** realloc(T** b, long int n, long int m);
1834  template<class T>
1835  T** realloc(T** b, unsigned int n, unsigned int m);
1843  template<class T>
1844  T** realloc(T** b, int n, int m);
1846  void* ralloc(size_t s);
1848  void rfree(void* p, size_t s);
1850  void* rrealloc(void* b, size_t n, size_t m);
1852  template<size_t> void* fl_alloc(void);
1858  template<size_t> void fl_dispose(FreeList* f, FreeList* l);
1865  size_t allocated(void) const;
1875  GECODE_KERNEL_EXPORT void flush(void);
1877 
1878 
1879 
1882  template<class T>
1883  T& construct(void);
1889  template<class T, typename A1>
1890  T& construct(A1 const& a1);
1896  template<class T, typename A1, typename A2>
1897  T& construct(A1 const& a1, A2 const& a2);
1903  template<class T, typename A1, typename A2, typename A3>
1904  T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
1910  template<class T, typename A1, typename A2, typename A3, typename A4>
1911  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
1917  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
1918  T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
1920 
1926  class Propagators {
1927  private:
1929  const Space& home;
1931  const ActorLink* q;
1933  const ActorLink* c;
1935  const ActorLink* e;
1936  public:
1938  Propagators(const Space& home);
1940  bool operator ()(void) const;
1942  void operator ++(void);
1944  const Propagator& propagator(void) const;
1945  };
1946 
1952  class Branchers {
1953  private:
1955  const ActorLink* c;
1957  const ActorLink* e;
1958  public:
1960  Branchers(const Space& home);
1962  bool operator ()(void) const;
1964  void operator ++(void);
1966  const Brancher& brancher(void) const;
1967  };
1968  };
1969 
1970 
1971 
1972 
1973  /*
1974  * Memory management
1975  *
1976  */
1977 
1978  // Heap allocated
1979  forceinline void*
1980  SharedHandle::Object::operator new(size_t s) {
1981  return heap.ralloc(s);
1982  }
1983  forceinline void
1984  SharedHandle::Object::operator delete(void* p) {
1985  heap.rfree(p);
1986  }
1987 
1988  forceinline void*
1989  Space::operator new(size_t s) {
1990  return heap.ralloc(s);
1991  }
1992  forceinline void
1993  Space::operator delete(void* p) {
1994  heap.rfree(p);
1995  }
1996 
1997  forceinline void
1998  Choice::operator delete(void* p) {
1999  heap.rfree(p);
2000  }
2001  forceinline void*
2002  Choice::operator new(size_t s) {
2003  return heap.ralloc(s);
2004  }
2005 
2006  // Space allocation: general space heaps and free lists
2007  forceinline void*
2008  Space::ralloc(size_t s) {
2009  return mm.alloc(sm,s);
2010  }
2011  forceinline void
2012  Space::rfree(void* p, size_t s) {
2013  return mm.reuse(p,s);
2014  }
2015  forceinline void*
2016  Space::rrealloc(void* _b, size_t n, size_t m) {
2017  char* b = static_cast<char*>(_b);
2018  if (n < m) {
2019  char* p = static_cast<char*>(ralloc(m));
2020  memcpy(p,b,n);
2021  rfree(b,n);
2022  return p;
2023  } else {
2024  rfree(b+m,m-n);
2025  return b;
2026  }
2027  }
2028 
2029  template<size_t s>
2030  forceinline void*
2032  return mm.template fl_alloc<s>(sm);
2033  }
2034  template<size_t s>
2035  forceinline void
2037  mm.template fl_dispose<s>(f,l);
2038  }
2039 
2040  forceinline size_t
2041  Space::allocated(void) const {
2042  size_t s = mm.allocated();
2043  for (Actor** a = d_fst; a < d_cur; a++)
2044  s += (*a)->allocated();
2045  return s;
2046  }
2047 
2048  /*
2049  * Typed allocation routines
2050  *
2051  */
2052  template<class T>
2053  forceinline T*
2054  Space::alloc(long unsigned int n) {
2055  T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2056  for (long unsigned int i=n; i--; )
2057  (void) new (p+i) T();
2058  return p;
2059  }
2060  template<class T>
2061  forceinline T*
2062  Space::alloc(long int n) {
2063  assert(n >= 0);
2064  return alloc<T>(static_cast<long unsigned int>(n));
2065  }
2066  template<class T>
2067  forceinline T*
2068  Space::alloc(unsigned int n) {
2069  return alloc<T>(static_cast<long unsigned int>(n));
2070  }
2071  template<class T>
2072  forceinline T*
2073  Space::alloc(int n) {
2074  assert(n >= 0);
2075  return alloc<T>(static_cast<long unsigned int>(n));
2076  }
2077 
2078  template<class T>
2079  forceinline void
2080  Space::free(T* b, long unsigned int n) {
2081  for (long unsigned int i=n; i--; )
2082  b[i].~T();
2083  rfree(b,n*sizeof(T));
2084  }
2085  template<class T>
2086  forceinline void
2087  Space::free(T* b, long int n) {
2088  assert(n >= 0);
2089  free<T>(b,static_cast<long unsigned int>(n));
2090  }
2091  template<class T>
2092  forceinline void
2093  Space::free(T* b, unsigned int n) {
2094  free<T>(b,static_cast<long unsigned int>(n));
2095  }
2096  template<class T>
2097  forceinline void
2098  Space::free(T* b, int n) {
2099  assert(n >= 0);
2100  free<T>(b,static_cast<long unsigned int>(n));
2101  }
2102 
2103  template<class T>
2104  forceinline T*
2105  Space::realloc(T* b, long unsigned int n, long unsigned int m) {
2106  if (n < m) {
2107  T* p = static_cast<T*>(ralloc(sizeof(T)*m));
2108  for (long unsigned int i=n; i--; )
2109  (void) new (p+i) T(b[i]);
2110  for (long unsigned int i=n; i<m; i++)
2111  (void) new (p+i) T();
2112  free<T>(b,n);
2113  return p;
2114  } else {
2115  free<T>(b+m,m-n);
2116  return b;
2117  }
2118  }
2119  template<class T>
2120  forceinline T*
2121  Space::realloc(T* b, long int n, long int m) {
2122  assert((n >= 0) && (m >= 0));
2123  return realloc<T>(b,static_cast<long unsigned int>(n),
2124  static_cast<long unsigned int>(m));
2125  }
2126  template<class T>
2127  forceinline T*
2128  Space::realloc(T* b, unsigned int n, unsigned int m) {
2129  return realloc<T>(b,static_cast<long unsigned int>(n),
2130  static_cast<long unsigned int>(m));
2131  }
2132  template<class T>
2133  forceinline T*
2134  Space::realloc(T* b, int n, int m) {
2135  assert((n >= 0) && (m >= 0));
2136  return realloc<T>(b,static_cast<long unsigned int>(n),
2137  static_cast<long unsigned int>(m));
2138  }
2139 
2140 #define GECODE_KERNEL_REALLOC(T) \
2141  template<> \
2142  forceinline T* \
2143  Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2144  return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2145  } \
2146  template<> \
2147  forceinline T* \
2148  Space::realloc<T>(T* b, long int n, long int m) { \
2149  assert((n >= 0) && (m >= 0)); \
2150  return realloc<T>(b,static_cast<long unsigned int>(n), \
2151  static_cast<long unsigned int>(m)); \
2152  } \
2153  template<> \
2154  forceinline T* \
2155  Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2156  return realloc<T>(b,static_cast<long unsigned int>(n), \
2157  static_cast<long unsigned int>(m)); \
2158  } \
2159  template<> \
2160  forceinline T* \
2161  Space::realloc<T>(T* b, int n, int m) { \
2162  assert((n >= 0) && (m >= 0)); \
2163  return realloc<T>(b,static_cast<long unsigned int>(n), \
2164  static_cast<long unsigned int>(m)); \
2165  }
2166 
2167  GECODE_KERNEL_REALLOC(bool)
2168  GECODE_KERNEL_REALLOC(signed char)
2169  GECODE_KERNEL_REALLOC(unsigned char)
2170  GECODE_KERNEL_REALLOC(signed short int)
2171  GECODE_KERNEL_REALLOC(unsigned short int)
2172  GECODE_KERNEL_REALLOC(signed int)
2173  GECODE_KERNEL_REALLOC(unsigned int)
2174  GECODE_KERNEL_REALLOC(signed long int)
2175  GECODE_KERNEL_REALLOC(unsigned long int)
2176  GECODE_KERNEL_REALLOC(float)
2177  GECODE_KERNEL_REALLOC(double)
2178 
2179 #undef GECODE_KERNEL_REALLOC
2180 
2181  template<class T>
2182  forceinline T**
2183  Space::realloc(T** b, long unsigned int n, long unsigned int m) {
2184  return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
2185  }
2186  template<class T>
2187  forceinline T**
2188  Space::realloc(T** b, long int n, long int m) {
2189  assert((n >= 0) && (m >= 0));
2190  return realloc<T*>(b,static_cast<long unsigned int>(n),
2191  static_cast<long unsigned int>(m));
2192  }
2193  template<class T>
2194  forceinline T**
2195  Space::realloc(T** b, unsigned int n, unsigned int m) {
2196  return realloc<T*>(b,static_cast<long unsigned int>(n),
2197  static_cast<long unsigned int>(m));
2198  }
2199  template<class T>
2200  forceinline T**
2201  Space::realloc(T** b, int n, int m) {
2202  assert((n >= 0) && (m >= 0));
2203  return realloc<T*>(b,static_cast<long unsigned int>(n),
2204  static_cast<long unsigned int>(m));
2205  }
2206 
2207 
2208 #ifdef GECODE_HAS_VAR_DISPOSE
2209  template<class VIC>
2211  Space::vars_d(void) const {
2212  return _vars_d[VIC::idx_d];
2213  }
2214  template<class VIC>
2215  forceinline void
2216  Space::vars_d(VarImpBase* x) {
2217  _vars_d[VIC::idx_d] = x;
2218  }
2219 #endif
2220 
2221  // Space allocated entities: Actors, variable implementations, and advisors
2222  forceinline void
2223  Actor::operator delete(void*) {}
2224  forceinline void
2225  Actor::operator delete(void*, Space&) {}
2226  forceinline void*
2227  Actor::operator new(size_t s, Space& home) {
2228  return home.ralloc(s);
2229  }
2230 
2231  template<class VIC>
2232  forceinline void
2233  VarImp<VIC>::operator delete(void*) {}
2234  template<class VIC>
2235  forceinline void
2236  VarImp<VIC>::operator delete(void*, Space&) {}
2237  template<class VIC>
2238  forceinline void*
2239  VarImp<VIC>::operator new(size_t s, Space& home) {
2240  return home.ralloc(s);
2241  }
2242 
2243 #ifndef __GNUC__
2244  forceinline void
2245  Advisor::operator delete(void*) {}
2246 #endif
2247  forceinline void
2248  Advisor::operator delete(void*, Space&) {}
2249  forceinline void*
2250  Advisor::operator new(size_t s, Space& home) {
2251  return home.ralloc(s);
2252  }
2253 
2254  /*
2255  * Shared objects and handles
2256  *
2257  */
2258  forceinline
2260  : next(NULL), fwd(NULL), use_cnt(0) {}
2261  forceinline
2263  assert(use_cnt == 0);
2264  }
2265 
2267  SharedHandle::object(void) const {
2268  return o;
2269  }
2270  forceinline void
2271  SharedHandle::subscribe(void) {
2272  if (o != NULL) o->use_cnt++;
2273  }
2274  forceinline void
2275  SharedHandle::cancel(void) {
2276  if ((o != NULL) && (--o->use_cnt == 0))
2277  delete o;
2278  o=NULL;
2279  }
2280  forceinline void
2282  if (n != o) {
2283  cancel(); o=n; subscribe();
2284  }
2285  }
2286  forceinline
2287  SharedHandle::SharedHandle(void) : o(NULL) {}
2288  forceinline
2290  subscribe();
2291  }
2292  forceinline
2294  subscribe();
2295  }
2298  if (&sh != this) {
2299  cancel(); o=sh.o; subscribe();
2300  }
2301  return *this;
2302  }
2303  forceinline void
2304  SharedHandle::update(Space& home, bool share, SharedHandle& sh) {
2305  if (sh.o == NULL) {
2306  o=NULL; return;
2307  } else if (share) {
2308  o=sh.o;
2309  } else if (sh.o->fwd != NULL) {
2310  o=sh.o->fwd;
2311  } else {
2312  o = sh.o->copy();
2313  sh.o->fwd = o;
2314  sh.o->next = home.pc.c.shared;
2315  home.pc.c.shared = sh.o;
2316  }
2317  subscribe();
2318  }
2319  forceinline
2321  cancel();
2322  }
2323 
2324 
2325 
2326  /*
2327  * ActorLink
2328  *
2329  */
2331  ActorLink::prev(void) const {
2332  return _prev;
2333  }
2334 
2336  ActorLink::next(void) const {
2337  return _next;
2338  }
2339 
2342  return &_next;
2343  }
2344 
2345  forceinline void
2347  _prev = al;
2348  }
2349 
2350  forceinline void
2352  _next = al;
2353  }
2354 
2355  forceinline void
2357  ActorLink* p = _prev; ActorLink* n = _next;
2358  p->_next = n; n->_prev = p;
2359  }
2360 
2361  forceinline void
2363  _next = this; _prev =this;
2364  }
2365 
2366  forceinline void
2368  // Inserts al at head of link-chain (that is, after this)
2369  ActorLink* n = _next;
2370  this->_next = a; a->_prev = this;
2371  a->_next = n; n->_prev = a;
2372  }
2373 
2374  forceinline void
2376  // Inserts al at tail of link-chain (that is, before this)
2377  ActorLink* p = _prev;
2378  a->_next = this; this->_prev = a;
2379  p->_next = a; a->_prev = p;
2380  }
2381 
2382  forceinline bool
2383  ActorLink::empty(void) const {
2384  return _next == this;
2385  }
2386 
2387  template<class T>
2390  // Turning al into a reference is for gcc, assume is for MSVC
2391  GECODE_NOT_NULL(a);
2392  ActorLink& t = *a;
2393  return static_cast<ActorLink*>(&t);
2394  }
2395 
2396  template<class T>
2397  forceinline const ActorLink*
2398  ActorLink::cast(const T* a) {
2399  // Turning al into a reference is for gcc, assume is for MSVC
2400  GECODE_NOT_NULL(a);
2401  const ActorLink& t = *a;
2402  return static_cast<const ActorLink*>(&t);
2403  }
2404 
2405 
2406  /*
2407  * Actor
2408  *
2409  */
2411  Actor::cast(ActorLink* al) {
2412  // Turning al into a reference is for gcc, assume is for MSVC
2413  GECODE_NOT_NULL(al);
2414  ActorLink& t = *al;
2415  return static_cast<Actor*>(&t);
2416  }
2417 
2418  forceinline const Actor*
2419  Actor::cast(const ActorLink* al) {
2420  // Turning al into a reference is for gcc, assume is for MSVC
2421  GECODE_NOT_NULL(al);
2422  const ActorLink& t = *al;
2423  return static_cast<const Actor*>(&t);
2424  }
2425 
2426  forceinline void
2428  if (p & AP_DISPOSE) {
2429  if (d_cur == d_lst)
2430  d_resize();
2431  *(d_cur++) = &a;
2432  }
2433  if (p & AP_WEAKLY) {
2434  if (n_wmp == 0)
2435  n_wmp = 2;
2436  else
2437  n_wmp++;
2438  }
2439  }
2440 
2441  forceinline void
2443  s.notice(a,p);
2444  }
2445 
2446  forceinline void
2448  if (p & AP_DISPOSE) {
2449  // Check wether array has already been discarded as space
2450  // deletion is already in progress
2451  Actor** f = d_fst;
2452  if (f != NULL) {
2453  while (&a != *f)
2454  f++;
2455  *f = *(--d_cur);
2456  }
2457  }
2458  if (p & AP_WEAKLY) {
2459  assert(n_wmp > 1);
2460  n_wmp--;
2461  }
2462  }
2463 
2465  Space::clone(bool share, CloneStatistics&) const {
2466  // Clone is only const for search engines. During cloning, several data
2467  // structures are updated (e.g. forwarding pointers), so we have to
2468  // cast away the constness.
2469  return const_cast<Space*>(this)->_clone(share);
2470  }
2471 
2472  forceinline void
2473  Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
2474  _commit(c,a);
2475  }
2476 
2477  forceinline size_t
2479  return sizeof(*this);
2480  }
2481 
2482 
2483  /*
2484  * Home for posting actors
2485  *
2486  */
2487  forceinline
2488  Home::Home(Space& s0, Propagator* p0) : s(s0), p(p0) {}
2489  forceinline
2490  Home::operator Space&(void) {
2491  return s;
2492  }
2495  return Home(s,&p);
2496  }
2499  return Home(*this,&p);
2500  }
2502  Home::propagator(void) const {
2503  return p;
2504  }
2505 
2506  /*
2507  * Propagator
2508  *
2509  */
2511  Propagator::cast(ActorLink* al) {
2512  // Turning al into a reference is for gcc, assume is for MSVC
2513  GECODE_NOT_NULL(al);
2514  ActorLink& t = *al;
2515  return static_cast<Propagator*>(&t);
2516  }
2517 
2518  forceinline const Propagator*
2519  Propagator::cast(const ActorLink* al) {
2520  // Turning al into a reference is for gcc, assume is for MSVC
2521  GECODE_NOT_NULL(al);
2522  const ActorLink& t = *al;
2523  return static_cast<const Propagator*>(&t);
2524  }
2525 
2526  forceinline
2528  : pi((home.propagator() != NULL) ?
2529  // Inherit propagator information
2530  home.propagator()->pi :
2531  // New propagator information
2532  static_cast<Space&>(home).gpi.allocate()) {
2533  u.advisors = NULL;
2534  assert((u.med == 0) && (u.size == 0));
2535  static_cast<Space&>(home).pl.head(this);
2536  }
2537 
2538  forceinline
2540  : pi(p.pi) {
2541  u.advisors = NULL;
2542  assert((u.med == 0) && (u.size == 0));
2543  // Set forwarding pointer
2544  p.prev(this);
2545  }
2546 
2549  return u.med;
2550  }
2551 
2552  forceinline double
2553  Propagator::afc(void) const {
2554  return pi.afc();
2555  }
2556 
2559  p.u.size = s;
2560  return __ES_SUBSUMED;
2561  }
2562 
2565  p.u.size = p.dispose(*this);
2566  return __ES_SUBSUMED;
2567  }
2568 
2571  p.u.med = med;
2572  assert(p.u.med != 0);
2573  return __ES_PARTIAL;
2574  }
2575 
2578  p.u.med = AllVarConf::med_combine(p.u.med,med);
2579  assert(p.u.med != 0);
2580  return __ES_PARTIAL;
2581  }
2582 
2583 
2584 
2585  /*
2586  * Brancher
2587  *
2588  */
2590  Brancher::cast(ActorLink* al) {
2591  // Turning al into a reference is for gcc, assume is for MSVC
2592  GECODE_NOT_NULL(al);
2593  ActorLink& t = *al;
2594  return static_cast<Brancher*>(&t);
2595  }
2596 
2597  forceinline const Brancher*
2598  Brancher::cast(const ActorLink* al) {
2599  // Turning al into a reference is for gcc, assume is for MSVC
2600  GECODE_NOT_NULL(al);
2601  const ActorLink& t = *al;
2602  return static_cast<const Brancher*>(&t);
2603  }
2604 
2605  forceinline
2607  _id(static_cast<Space&>(home).pc.p.branch_id++) {
2608  if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2609  throw TooManyBranchers("Brancher::Brancher");
2610  // If no brancher available, make it the first one
2611  if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2612  static_cast<Space&>(home).b_status = this;
2613  if (static_cast<Space&>(home).b_commit == &static_cast<Space&>(home).bl)
2614  static_cast<Space&>(home).b_commit = this;
2615  }
2616  static_cast<Space&>(home).bl.tail(this);
2617  }
2618 
2619  forceinline
2621  : _id(b._id) {
2622  // Set forwarding pointer
2623  b.prev(this);
2624  }
2625 
2626  forceinline unsigned int
2627  Brancher::id(void) const {
2628  return _id;
2629  }
2630 
2631  /*
2632  * Local objects
2633  *
2634  */
2635 
2638  // Turning al into a reference is for gcc, assume is for MSVC
2639  GECODE_NOT_NULL(al);
2640  ActorLink& t = *al;
2641  return static_cast<LocalObject*>(&t);
2642  }
2643 
2644  forceinline const LocalObject*
2646  // Turning al into a reference is for gcc, assume is for MSVC
2647  GECODE_NOT_NULL(al);
2648  const ActorLink& t = *al;
2649  return static_cast<const LocalObject*>(&t);
2650  }
2651 
2652  forceinline
2654  ActorLink::cast(this)->prev(NULL);
2655  }
2656 
2657  forceinline
2659  ActorLink::cast(this)->prev(NULL);
2660  }
2661 
2663  LocalObject::fwd(Space& home, bool share) {
2664  if (prev() == NULL)
2665  fwdcopy(home,share);
2666  return LocalObject::cast(prev());
2667  }
2668 
2669  forceinline
2670  LocalHandle::LocalHandle(void) : o(NULL) {}
2671  forceinline
2673  forceinline
2674  LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {}
2677  o = lh.o;
2678  return *this;
2679  }
2680  forceinline
2683  LocalHandle::object(void) const { return o; }
2684  forceinline void
2686  forceinline void
2687  LocalHandle::update(Space& home, bool share, LocalHandle& lh) {
2688  object(lh.object()->fwd(home,share));
2689  }
2690 
2691 
2692  /*
2693  * Choices
2694  *
2695  */
2696  forceinline
2697  Choice::Choice(const Brancher& b, const unsigned int a)
2698  : _id(b.id()), _alt(a) {}
2699 
2700  forceinline unsigned int
2701  Choice::alternatives(void) const {
2702  return _alt;
2703  }
2704 
2705  forceinline unsigned int
2706  Choice::id(void) const {
2707  return _id;
2708  }
2709 
2710  forceinline
2712 
2713 
2714 
2715  /*
2716  * Advisor
2717  *
2718  */
2719  template<class A>
2720  forceinline
2722  // Store propagator and forwarding in prev()
2723  ActorLink::prev(&p);
2724  // Link to next advisor in next()
2725  ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
2726  }
2727 
2728  forceinline
2730 
2731  forceinline bool
2732  Advisor::disposed(void) const {
2733  return prev() == NULL;
2734  }
2735 
2736  forceinline Advisor*
2737  Advisor::cast(ActorLink* al) {
2738  return static_cast<Advisor*>(al);
2739  }
2740 
2741  forceinline const Advisor*
2742  Advisor::cast(const ActorLink* al) {
2743  return static_cast<const Advisor*>(al);
2744  }
2745 
2746  forceinline Propagator&
2747  Advisor::propagator(void) const {
2748  assert(!disposed());
2749  return *Propagator::cast(ActorLink::prev());
2750  }
2751 
2752  template<class A>
2753  forceinline void
2755  assert(!disposed());
2756  ActorLink::prev(NULL);
2757  // Shorten chains of disposed advisors by one, if possible
2758  Advisor* n = Advisor::cast(next());
2759  if ((n != NULL) && n->disposed())
2760  next(n->next());
2761  }
2762 
2763  template<class A>
2766  a.dispose(*this,c);
2767  return ES_FIX;
2768  }
2769 
2770  template<class A>
2773  a.dispose(*this,c);
2774  return ES_NOFIX;
2775  }
2776 
2777  template<class A>
2780  a.dispose(*this,c);
2781  return ES_NOFIX_FORCE;
2782  }
2783 
2784 
2785 
2786  /*
2787  * Advisor council
2788  *
2789  */
2790  template<class A>
2791  forceinline
2793 
2794  template<class A>
2795  forceinline
2797  : advisors(NULL) {}
2798 
2799  template<class A>
2800  forceinline bool
2801  Council<A>::empty(void) const {
2802  ActorLink* a = advisors;
2803  while ((a != NULL) && static_cast<A*>(a)->disposed())
2804  a = a->next();
2805  advisors = a;
2806  return a == NULL;
2807  }
2808 
2809  template<class A>
2810  forceinline void
2811  Council<A>::update(Space& home, bool share, Council<A>& c) {
2812  // Skip all disposed advisors
2813  {
2814  ActorLink* a = c.advisors;
2815  while ((a != NULL) && static_cast<A*>(a)->disposed())
2816  a = a->next();
2817  c.advisors = a;
2818  }
2819  // Are there any advisors to be cloned?
2820  if (c.advisors != NULL) {
2821  // The propagator in from-space
2822  Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
2823  // The propagator in to-space
2824  Propagator* p_t = Propagator::cast(p_f->prev());
2825  // Advisors in from-space
2826  ActorLink** a_f = &c.advisors;
2827  // Advisors in to-space
2828  A* a_t = NULL;
2829  while (*a_f != NULL) {
2830  if (static_cast<A*>(*a_f)->disposed()) {
2831  *a_f = (*a_f)->next();
2832  } else {
2833  // Run specific copying part
2834  A* a = new (home) A(home,share,*static_cast<A*>(*a_f));
2835  // Set propagator pointer
2836  a->prev(p_t);
2837  // Set forwarding pointer
2838  (*a_f)->prev(a);
2839  // Link
2840  a->next(a_t);
2841  a_t = a;
2842  a_f = (*a_f)->next_ref();
2843  }
2844  }
2845  advisors = a_t;
2846  // Enter advisor link for reset
2847  assert(p_f->u.advisors == NULL);
2848  p_f->u.advisors = c.advisors;
2849  } else {
2850  advisors = NULL;
2851  }
2852  }
2853 
2854  template<class A>
2855  forceinline void
2857  ActorLink* a = advisors;
2858  while (a != NULL) {
2859  if (!static_cast<A*>(a)->disposed())
2860  static_cast<A*>(a)->dispose(home,*this);
2861  a = a->next();
2862  }
2863  }
2864 
2865 
2866 
2867  /*
2868  * Advisor iterator
2869  *
2870  */
2871  template<class A>
2872  forceinline
2874  : a(c.advisors) {
2875  while ((a != NULL) && static_cast<A*>(a)->disposed())
2876  a = a->next();
2877  }
2878 
2879  template<class A>
2880  forceinline bool
2882  return a != NULL;
2883  }
2884 
2885  template<class A>
2886  forceinline void
2888  do {
2889  a = a->next();
2890  } while ((a != NULL) && static_cast<A*>(a)->disposed());
2891  }
2892 
2893  template<class A>
2894  forceinline A&
2895  Advisors<A>::advisor(void) const {
2896  return *static_cast<A*>(a);
2897  }
2898 
2899 
2900 
2901  /*
2902  * Space
2903  *
2904  */
2905  forceinline void
2906  Space::enqueue(Propagator* p) {
2907  ActorLink::cast(p)->unlink();
2908  ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
2909  c->tail(ActorLink::cast(p));
2910  if (c > pc.p.active)
2911  pc.p.active = c;
2912  }
2913 
2914  forceinline void
2915  Space::fail(void) {
2916  /*
2917  * Now active points beyond the last queue. This is essential as
2918  * enqueuing a propagator in a failed space keeps the space
2919  * failed.
2920  */
2921  pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
2922  }
2923  forceinline void
2924  Home::fail(void) {
2925  s.fail();
2926  }
2927 
2928  forceinline bool
2929  Space::failed(void) const {
2930  return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
2931  }
2932  forceinline bool
2933  Home::failed(void) const {
2934  return s.failed();
2935  }
2936 
2937  forceinline bool
2938  Space::stable(void) const {
2939  return ((pc.p.active < &pc.p.queue[0]) ||
2940  (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
2941  }
2942 
2943 
2944 
2945  /*
2946  * Variable implementation
2947  *
2948  */
2949  template<class VIC>
2952  assert((pc >= 0) && (pc < pc_max+2));
2953  return (pc == 0) ? b.base : b.base+u.idx[pc-1];
2954  }
2955 
2956  template<class VIC>
2957  forceinline ActorLink**
2958  VarImp<VIC>::actorNonZero(PropCond pc) {
2959  assert((pc > 0) && (pc < pc_max+2));
2960  return b.base+u.idx[pc-1];
2961  }
2962 
2963  template<class VIC>
2964  forceinline unsigned int&
2966  assert((pc > 0) && (pc < pc_max+2));
2967  return u.idx[pc-1];
2968  }
2969 
2970  template<class VIC>
2971  forceinline unsigned int
2972  VarImp<VIC>::idx(PropCond pc) const {
2973  assert((pc > 0) && (pc < pc_max+2));
2974  return u.idx[pc-1];
2975  }
2976 
2977  template<class VIC>
2978  forceinline
2980  b.base = NULL; entries = 0;
2981  for (PropCond pc=1; pc<pc_max+2; pc++)
2982  idx(pc) = 0;
2983  free_and_bits = 0;
2984  }
2985 
2986  template<class VIC>
2987  forceinline
2989  b.base = NULL; entries = 0;
2990  for (PropCond pc=1; pc<pc_max+2; pc++)
2991  idx(pc) = 0;
2992  free_and_bits = 0;
2993  }
2994 
2995  template<class VIC>
2996  forceinline unsigned int
2997  VarImp<VIC>::degree(void) const {
2998  assert(!copied());
2999  return entries;
3000  }
3001 
3002  template<class VIC>
3003  forceinline double
3004  VarImp<VIC>::afc(void) const {
3005  if (degree() == 0)
3006  return 0.0;
3007  double d = degree();
3008  // Count the afc of each propagator
3009  {
3010  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
3011  ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3012  while (a < e) {
3013  d += Propagator::cast(*a)->afc(); a++;
3014  }
3015  }
3016  // Count the afc of each advisor's propagator
3017  {
3018  ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
3019  ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
3020  while (a < e) {
3021  d += Advisor::cast(*a)->propagator().afc(); a++;
3022  }
3023  }
3024  return d;
3025  }
3026 
3027  template<class VIC>
3030  return d.me;
3031  }
3032 
3033  template<class VIC>
3034  forceinline unsigned int
3035  VarImp<VIC>::bits(void) const {
3036  return free_and_bits;
3037  }
3038 
3039  template<class VIC>
3040  forceinline unsigned int&
3042  return free_and_bits;
3043  }
3044 
3045 #ifdef GECODE_HAS_VAR_DISPOSE
3046  template<class VIC>
3048  VarImp<VIC>::vars_d(Space& home) {
3049  return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
3050  }
3051 
3052  template<class VIC>
3053  forceinline void
3054  VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
3055  home.vars_d<VIC>(x);
3056  }
3057 #endif
3058 
3059  template<class VIC>
3060  forceinline bool
3061  VarImp<VIC>::copied(void) const {
3062  return Support::marked(b.fwd);
3063  }
3064 
3065  template<class VIC>
3067  VarImp<VIC>::forward(void) const {
3068  assert(copied());
3069  return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
3070  }
3071 
3072  template<class VIC>
3074  VarImp<VIC>::next(void) const {
3075  assert(copied());
3076  return u.next;
3077  }
3078 
3079  template<class VIC>
3080  forceinline
3082  VarImpBase** reg;
3083  free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3084  if (x.b.base == NULL) {
3085  // Variable implementation needs no index structure
3086  reg = &home.pc.c.vars_noidx;
3087  assert(x.degree() == 0);
3088  } else {
3089  reg = &home.pc.c.vars_u[idx_c];
3090  }
3091  // Save subscriptions in copy
3092  b.base = x.b.base;
3093  entries = x.entries;
3094  for (PropCond pc=1; pc<pc_max+2; pc++)
3095  idx(pc) = x.idx(pc);
3096 
3097  // Set forwarding pointer
3098  x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
3099  // Register original
3100  x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
3101  }
3102 
3103  template<class VIC>
3106  return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3107  }
3108 
3109  template<class VIC>
3112  return static_cast<ModEventDelta>(me << VIC::med_fst);
3113  }
3114 
3115  template<class VIC>
3118  return VIC::me_combine(me1,me2);
3119  }
3120 
3121  template<class VIC>
3122  forceinline void
3124  bool force) {
3125  if (VIC::med_update(p.u.med,me) || force)
3126  home.enqueue(&p);
3127  }
3128 
3129  template<class VIC>
3130  forceinline void
3132  ActorLink** b = actor(pc1);
3133  ActorLink** p = actorNonZero(pc2+1);
3134  while (p-- > b)
3135  schedule(home,*Propagator::cast(*p),me);
3136  }
3137 
3138  template<class VIC>
3139  forceinline void
3140  VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
3141  assert(pc <= pc_max);
3142  // Count one new subscription
3143  home.pc.p.n_sub += 1;
3144  if ((free_and_bits >> free_bits) == 0)
3145  resize(home);
3146  free_and_bits -= 1 << free_bits;
3147 
3148  // Enter subscription
3149  b.base[entries] = *actorNonZero(pc_max+1);
3150  entries++;
3151  for (PropCond j = pc_max; j > pc; j--) {
3152  *actorNonZero(j+1) = *actorNonZero(j);
3153  idx(j+1)++;
3154  }
3155  *actorNonZero(pc+1) = *actor(pc);
3156  idx(pc+1)++;
3157  *actor(pc) = ActorLink::cast(p);
3158 
3159 #ifdef GECODE_AUDIT
3160  ActorLink** f = actor(pc);
3161  while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
3162  if (*f == p)
3163  goto found;
3164  else
3165  f++;
3166  GECODE_NEVER;
3167  found: ;
3168 #endif
3169  }
3170 
3171  template<class VIC>
3172  forceinline void
3173  VarImp<VIC>::enter(Space& home, Advisor* a) {
3174  // Count one new subscription
3175  home.pc.p.n_sub += 1;
3176  if ((free_and_bits >> free_bits) == 0)
3177  resize(home);
3178  free_and_bits -= 1 << free_bits;
3179 
3180  // Enter subscription
3181  b.base[entries++] = *actorNonZero(pc_max+1);
3182  *actorNonZero(pc_max+1) = a;
3183  }
3184 
3185  template<class VIC>
3186  void
3187  VarImp<VIC>::resize(Space& home) {
3188  if (b.base == NULL) {
3189  assert((free_and_bits >> free_bits) == 0);
3190  // Create fresh dependency array with four entries
3191  free_and_bits += 4 << free_bits;
3192  b.base = home.alloc<ActorLink*>(4);
3193  for (int i=0; i<pc_max+1; i++)
3194  u.idx[i] = 0;
3195  } else {
3196  // Resize dependency array
3197  unsigned int n = degree();
3198  // Find out whether the area is most likely in the special area
3199  // reserved for subscriptions. If yes, just resize mildly otherwise
3200  // more agressively
3201  ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
3202  unsigned int m =
3203  ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
3204  (n+4) : ((n+1)*3>>1);
3205  ActorLink** prop = home.alloc<ActorLink*>(m);
3206  free_and_bits += (m-n) << free_bits;
3207  // Copy entries
3208  Heap::copy<ActorLink*>(prop, b.base, n);
3209  home.free<ActorLink*>(b.base,n);
3210  b.base = prop;
3211  }
3212  }
3213 
3214  template<class VIC>
3215  void
3217  bool assigned, ModEvent me, bool schedule) {
3218  if (assigned) {
3219  // Do not subscribe, just schedule the propagator
3220  if (schedule)
3222  } else {
3223  enter(home,&p,pc);
3224  // Schedule propagator
3225  if (schedule && (pc != PC_GEN_ASSIGNED))
3226  VarImp<VIC>::schedule(home,p,me);
3227  }
3228  }
3229 
3230  template<class VIC>
3231  forceinline void
3233  if (!assigned)
3234  enter(home,&a);
3235  }
3236 
3237  template<class VIC>
3238  forceinline void
3239  VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
3240  assert(pc <= pc_max);
3241  ActorLink* a = ActorLink::cast(p);
3242  // Find actor in dependency array
3243  ActorLink** f = actor(pc);
3244 #ifdef GECODE_AUDIT
3245  while (f < actorNonZero(pc+1))
3246  if (*f == a)
3247  goto found;
3248  else
3249  f++;
3250  GECODE_NEVER;
3251  found: ;
3252 #else
3253  while (*f != a) f++;
3254 #endif
3255  // Remove actor
3256  *f = *(actorNonZero(pc+1)-1);
3257  for (PropCond j = pc+1; j< pc_max+1; j++) {
3258  *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3259  idx(j)--;
3260  }
3261  *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
3262  idx(pc_max+1)--;
3263  entries--;
3264  free_and_bits += 1 << free_bits;
3265  home.pc.p.n_sub -= 1;
3266  }
3267 
3268  template<class VIC>
3269  forceinline void
3270  VarImp<VIC>::remove(Space& home, Advisor* a) {
3271  // Find actor in dependency array
3272  ActorLink** f = actorNonZero(pc_max+1);
3273 #ifdef GECODE_AUDIT
3274  while (f < b.base+entries)
3275  if (*f == a)
3276  goto found;
3277  else
3278  f++;
3279  GECODE_NEVER;
3280  found: ;
3281 #else
3282  while (*f != a) f++;
3283 #endif
3284  // Remove actor
3285  *f = b.base[--entries];
3286  free_and_bits += 1 << free_bits;
3287  home.pc.p.n_sub -= 1;
3288  }
3289 
3290  template<class VIC>
3291  forceinline void
3293  if (!assigned)
3294  remove(home,&p,pc);
3295  }
3296 
3297  template<class VIC>
3298  forceinline void
3300  if (!assigned)
3301  remove(home,&a);
3302  }
3303 
3304  template<class VIC>
3305  forceinline void
3307  unsigned int n_sub = degree();
3308  home.pc.p.n_sub -= n_sub;
3309  unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3310  home.free<ActorLink*>(b.base,n);
3311  // Must be NULL such that cloning works
3312  b.base = NULL;
3313  // Must be 0 such that degree works
3314  entries = 0;
3315  }
3316 
3317  template<class VIC>
3318  forceinline bool
3320  /*
3321  * An advisor that is executed might remove itself due to subsumption.
3322  * As entries are removed from front to back, the advisors must
3323  * be iterated in forward direction.
3324  */
3325  ActorLink** la = actorNonZero(pc_max+1);
3326  ActorLink** le = b.base+entries;
3327  if (la == le)
3328  return true;
3329  d.me = me;
3330  // An advisor that is run, might be removed during execution.
3331  // As removal is done from the back the advisors have to be executed
3332  // in inverse order.
3333  do {
3334  Advisor* a = Advisor::cast(*la);
3335  assert(!a->disposed());
3336  Propagator& p = a->propagator();
3337  switch (p.advise(home,*a,d)) {
3338  case ES_FIX:
3339  break;
3340  case ES_FAILED:
3341  p.pi.fail(home.gpi);
3342  return false;
3343  case ES_NOFIX:
3344  schedule(home,p,me);
3345  break;
3346  case ES_NOFIX_FORCE:
3347  schedule(home,p,me,true);
3348  break;
3349  default:
3350  GECODE_NEVER;
3351  }
3352  } while (++la < le);
3353  return true;
3354  }
3355 
3356  template<class VIC>
3357  forceinline void
3359  // this refers to the variable to be updated (clone)
3360  // x refers to the original
3361  // Recover from copy
3362  x->b.base = b.base;
3363  x->u.idx[0] = u.idx[0];
3364  if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
3365  x->u.idx[1] = u.idx[1];
3366 
3367  ActorLink** f = x->b.base;
3368  unsigned int n = x->degree();
3369  ActorLink** t = sub;
3370  sub += n;
3371  b.base = t;
3372  // Set subscriptions using actor forwarding pointers
3373  while (n >= 4) {
3374  n -= 4;
3375  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3376  t[2]=f[2]->prev(); t[3]=f[3]->prev();
3377  t += 4; f += 4;
3378  }
3379  if (n >= 2) {
3380  n -= 2;
3381  t[0]=f[0]->prev(); t[1]=f[1]->prev();
3382  t += 2; f += 2;
3383  }
3384  if (n > 0) {
3385  t[0]=f[0]->prev();
3386  }
3387  }
3388 
3389  template<class VIC>
3390  forceinline void
3391  VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3392  VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
3393  while (x != NULL) {
3394  VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
3395  }
3396  }
3397 
3398 
3399 
3400  /*
3401  * Variable disposer
3402  *
3403  */
3404  template<class VarImp>
3406 #ifdef GECODE_HAS_VAR_DISPOSE
3407  Space::vd[VarImp::idx_d] = this;
3408 #endif
3409  }
3410 
3411  template<class VarImp>
3412  void
3414  VarImp* x = static_cast<VarImp*>(_x);
3415  do {
3416  x->dispose(home); x = static_cast<VarImp*>(x->next_d());
3417  } while (x != NULL);
3418  }
3419 
3420  /*
3421  * Statistics
3422  */
3423 
3424  forceinline void
3426  propagate = 0;
3427  wmp = false;
3428  }
3429  forceinline
3431  reset();
3432  }
3435  propagate += s.propagate;
3436  wmp |= s.wmp;
3437  return *this;
3438  }
3441  StatusStatistics t(s);
3442  return t += *this;
3443  }
3444 
3445  forceinline void
3447 
3448  forceinline
3450  reset();
3451  }
3454  CloneStatistics s;
3455  return s;
3456  }
3459  return *this;
3460  }
3461 
3462  forceinline void
3464 
3465  forceinline
3467  reset();
3468  }
3471  CommitStatistics s;
3472  return s;
3473  }
3476  return *this;
3477  }
3478 
3479  /*
3480  * Cost computation
3481  *
3482  */
3483 
3484  forceinline
3485  PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
3486 
3487  forceinline PropCost
3488  PropCost::cost(PropCost::Mod m,
3490  unsigned int n) {
3491  if (n < 2)
3492  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3493  else if (n == 2)
3494  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3495  else if (n == 3)
3496  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3497  else
3498  return (m == LO) ? lo : hi;
3499  }
3500 
3501  forceinline PropCost
3502  PropCost::crazy(PropCost::Mod m, unsigned int n) {
3503  return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
3504  }
3507  assert(n >= 0);
3508  return crazy(m,static_cast<unsigned int>(n));
3509  }
3511  PropCost::cubic(PropCost::Mod m, unsigned int n) {
3512  return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
3513  }
3516  assert(n >= 0);
3517  return cubic(m,static_cast<unsigned int>(n));
3518  }
3520  PropCost::quadratic(PropCost::Mod m, unsigned int n) {
3521  return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
3522  }
3525  assert(n >= 0);
3526  return quadratic(m,static_cast<unsigned int>(n));
3527  }
3529  PropCost::linear(PropCost::Mod m, unsigned int n) {
3530  return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
3531  }
3534  assert(n >= 0);
3535  return linear(m,static_cast<unsigned int>(n));
3536  }
3539  return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
3540  }
3543  return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
3544  }
3547  return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
3548  }
3549 
3550  /*
3551  * Iterators for propagators and branchers of a space
3552  *
3553  */
3554  forceinline
3556  : home(home0), q(home.pc.p.active) {
3557  while (q >= &home.pc.p.queue[0]) {
3558  if (q->next() != q) {
3559  c = q->next(); e = q; q--;
3560  return;
3561  }
3562  q--;
3563  }
3564  q = NULL;
3565  if (!home.pl.empty()) {
3566  c = Propagator::cast(home.pl.next());
3567  e = Propagator::cast(&home.pl);
3568  } else {
3569  c = e = NULL;
3570  }
3571  }
3572  forceinline bool
3574  return c != NULL;
3575  }
3576  forceinline void
3578  c = c->next();
3579  if (c == e) {
3580  if (q == NULL) {
3581  c = NULL;
3582  } else {
3583  while (q >= &home.pc.p.queue[0]) {
3584  if (q->next() != q) {
3585  c = q->next(); e = q; q--;
3586  return;
3587  }
3588  q--;
3589  }
3590  q = NULL;
3591  if (!home.pl.empty()) {
3592  c = Propagator::cast(home.pl.next());
3593  e = Propagator::cast(&home.pl);
3594  } else {
3595  c = NULL;
3596  }
3597  }
3598  }
3599  }
3600  forceinline const Propagator&
3602  return *Propagator::cast(c);
3603  }
3604 
3605  forceinline
3607  : c(Brancher::cast(home.bl.next())), e(&home.bl) {}
3608  forceinline bool
3610  return c != e;
3611  }
3612  forceinline void
3614  c = c->next();
3615  }
3616  forceinline const Brancher&
3618  return *Brancher::cast(c);
3619  }
3620 
3621  /*
3622  * Space construction support
3623  *
3624  */
3625  template<class T>
3626  forceinline T&
3628  return alloc<T>(1);
3629  }
3630  template<class T, typename A1>
3631  forceinline T&
3632  Space::construct(A1 const& a1) {
3633  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3634  new (&t) T(a1);
3635  return t;
3636  }
3637  template<class T, typename A1, typename A2>
3638  forceinline T&
3639  Space::construct(A1 const& a1, A2 const& a2) {
3640  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3641  new (&t) T(a1,a2);
3642  return t;
3643  }
3644  template<class T, typename A1, typename A2, typename A3>
3645  forceinline T&
3646  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
3647  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3648  new (&t) T(a1,a2,a3);
3649  return t;
3650  }
3651  template<class T, typename A1, typename A2, typename A3, typename A4>
3652  forceinline T&
3653  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
3654  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3655  new (&t) T(a1,a2,a3,a4);
3656  return t;
3657  }
3658  template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
3659  forceinline T&
3660  Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
3661  T& t = *static_cast<T*>(ralloc(sizeof(T)));
3662  new (&t) T(a1,a2,a3,a4,a5);
3663  return t;
3664  }
3665 
3666 }
3667 
3668 // STATISTICS: kernel-core