Generated on for Gecode by doxygen 1.17.0
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.dev>
5 * Guido Tack <tack@gecode.dev>
6 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
7 *
8 * Contributing authors:
9 * Filip Konvicka <filip.konvicka@logis.cz>
10 * Kris Coester <kris.coester@sap.com>
11 * Alexander Shepil <alexander.shepil@sap.com>
12 * Samuel Gagnon <samuel.gagnon92@gmail.com>
13 *
14 * Copyright:
15 * Christian Schulte, 2002
16 * Guido Tack, 2003
17 * Mikael Zayenz Lagerkvist, 2006, 2026
18 * Kris Coester, 2024
19 * Alexander Shepil, 2024
20 * LOGIS, s.r.o., 2009
21 * Samuel Gagnon, 2018
22 *
23 * Bugfixes provided by:
24 * Alexander Samoilov <alexander_samoilov@yahoo.com>
25 *
26 * This file is part of Gecode, the generic constraint
27 * development environment:
28 * http://www.gecode.dev
29 *
30 * Permission is hereby granted, free of charge, to any person obtaining
31 * a copy of this software and associated documentation files (the
32 * "Software"), to deal in the Software without restriction, including
33 * without limitation the rights to use, copy, modify, merge, publish,
34 * distribute, sublicense, and/or sell copies of the Software, and to
35 * permit persons to whom the Software is furnished to do so, subject to
36 * the following conditions:
37 *
38 * The above copyright notice and this permission notice shall be
39 * included in all copies or substantial portions of the Software.
40 *
41 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
42 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
43 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
44 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
45 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
46 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
47 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
48 *
49 */
50
51#include <atomic>
52#include <iostream>
53
54namespace Gecode {
55
56 class Space;
57
66
67 typedef int ModEvent;
68
75
77 typedef int PropCond;
83
94 typedef int ModEventDelta;
95
96}
97
99
100namespace Gecode {
101
104 public:
106 static const int idx_c = -1;
108 static const int idx_d = -1;
112 static const int free_bits = 0;
114 static const int med_fst = 0;
116 static const int med_lst = 0;
118 static const int med_mask = 0;
122 static bool med_update(ModEventDelta& med, ModEvent me);
123 };
124
129 forceinline bool
133
134
135 /*
136 * These are the classes of interest
137 *
138 */
139 class ActorLink;
140 class Actor;
141 class Propagator;
143 class LocalObject;
144 class Advisor;
145 class AFC;
146 class Choice;
147 class Brancher;
148 class Group;
149 class PropagatorGroup;
150 class BrancherGroup;
151 class PostInfo;
152 class ViewTraceInfo;
153 class PropagateTraceInfo;
154 class CommitTraceInfo;
155 class PostTraceInfo;
156 class TraceRecorder;
157 class TraceFilter;
158 class Tracer;
159
160 template<class A> class Council;
161 template<class A> class Advisors;
162 template<class VIC> class VarImp;
163
164
165 /*
166 * Variable implementations
167 *
168 */
169
177 class VarImpBase {};
178
186 public:
188 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x);
191 };
192
199 template<class VarImp>
201 public:
203 VarImpDisposer(void);
205 virtual void dispose(Space& home, VarImpBase* x);
206 };
207
209 class Delta {
210 template<class VIC> friend class VarImp;
211 private:
213 ModEvent me;
214 };
215
223 template<class VIC>
224 class VarImp : public VarImpBase {
225 friend class Space;
226 friend class Propagator;
227 template<class VarImp> friend class VarImpDisposer;
229 private:
230 union {
248 } b;
249
251 static const int idx_c = VIC::idx_c;
253 static const int idx_d = VIC::idx_d;
255 static const int free_bits = VIC::free_bits;
257 unsigned int entries;
259 unsigned int free_and_bits;
261 static const Gecode::PropCond pc_max = VIC::pc_max;
262#ifdef GECODE_HAS_CBS
264 const unsigned var_id;
265#endif
266
267 union {
278 unsigned int idx[pc_max+1];
281 } u;
282
284 ActorLink** actor(PropCond pc);
286 ActorLink** actorNonZero(PropCond pc);
288 unsigned int& idx(PropCond pc);
290 unsigned int idx(PropCond pc) const;
291
298 void update(VarImp* x, ActorLink**& sub);
305 static void update(Space& home, ActorLink**& sub);
307 static void recover(Space& home, ActorLink**& sub);
308
310 void enter(Space& home, Propagator* p, PropCond pc);
312 void enter(Space& home, ActorLink* a);
314 void resize(Space& home);
316 void remove(Space& home, Propagator* p, PropCond pc);
318 void remove(Space& home, ActorLink* a);
319
320
321 protected:
323 void cancel(Space& home);
329 bool advise(Space& home, ModEvent me, Delta& d);
330 private:
332 void _fail(Space& home);
333 protected:
336#ifdef GECODE_HAS_VAR_DISPOSE
338 static VarImp<VIC>* vars_d(Space& home);
340 static void vars_d(Space& home, VarImp<VIC>* x);
341#endif
342
343 public:
345 VarImp(Space& home);
347 VarImp(void);
348
349#ifdef GECODE_HAS_CBS
351 unsigned int id(void) const;
352#endif
353
355
356
368 void subscribe(Space& home, Propagator& p, PropCond pc,
369 bool assigned, ModEvent me, bool schedule);
371 void cancel(Space& home, Propagator& p, PropCond pc);
380 void subscribe(Space& home, Advisor& a, bool assigned, bool fail);
382 void cancel(Space& home, Advisor& a, bool fail);
383
390 unsigned int degree(void) const;
397 double afc(void) const;
399
401
402
403 VarImp(Space& home, VarImp& x);
405 bool copied(void) const;
407 VarImp* forward(void) const;
409 VarImp* next(void) const;
411
413
414
421 static void schedule(Space& home, Propagator& p, ModEvent me,
422 bool force = false);
430 static void reschedule(Space& home, Propagator& p, PropCond pc,
431 bool assigned, ModEvent me);
433 static ModEvent me(const ModEventDelta& med);
439
441
442
443 static ModEvent modevent(const Delta& d);
445
447
448
449 unsigned int bits(void) const;
451 unsigned int& bits(void);
453
454 protected:
456 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me);
457
458 public:
460
461
462 static void* operator new(size_t,Space&);
464 static void operator delete(void*,Space&);
466 static void operator delete(void*);
468 };
469
470
488
493 class PropCost {
494 friend class Space;
495 public:
515
517 public:
519 enum Mod {
522 };
523 private:
525 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n);
528 public:
530 static PropCost record(void);
532 static PropCost crazy(PropCost::Mod m, unsigned int n);
534 static PropCost crazy(PropCost::Mod m, int n);
536 static PropCost cubic(PropCost::Mod m, unsigned int n);
538 static PropCost cubic(PropCost::Mod m, int n);
540 static PropCost quadratic(PropCost::Mod m, unsigned int n);
542 static PropCost quadratic(PropCost::Mod m, int n);
544 static PropCost linear(PropCost::Mod m, unsigned int n);
546 static PropCost linear(PropCost::Mod m, int n);
550 static PropCost binary(PropCost::Mod m);
552 static PropCost unary(PropCost::Mod m);
553 };
554
555
569 AP_DISPOSE = (1 << 0),
575 AP_WEAKLY = (1 << 1),
580 AP_VIEW_TRACE = (1 << 2),
585 AP_TRACE = (1 << 3)
586 };
587
588
596 class ActorLink {
597 friend class Actor;
598 friend class Propagator;
599 friend class Advisor;
600 friend class Brancher;
601 friend class LocalObject;
602 friend class Space;
603 template<class VIC> friend class VarImp;
604 private:
605 ActorLink* _next; ActorLink* _prev;
606 public:
608
609 ActorLink* prev(void) const; void prev(ActorLink*);
610 ActorLink* next(void) const; void next(ActorLink*);
611 ActorLink** next_ref(void);
613
615 void init(void);
617 void unlink(void);
619 void head(ActorLink* al);
621 void tail(ActorLink* al);
623 bool empty(void) const;
625 template<class T> static ActorLink* cast(T* a);
627 template<class T> static const ActorLink* cast(const T* a);
628 };
629
630
636 friend class ActorLink;
637 friend class Space;
638 friend class Propagator;
639 friend class Advisor;
640 friend class Brancher;
641 friend class LocalObject;
642 template<class VIC> friend class VarImp;
643 template<class A> friend class Council;
644 private:
646 static Actor* cast(ActorLink* al);
648 static const Actor* cast(const ActorLink* al);
650 GECODE_KERNEL_EXPORT static Actor* sentinel;
651 public:
653 virtual Actor* copy(Space& home) = 0;
654
656
657
659 virtual size_t dispose(Space& home);
661 static void* operator new(size_t s, Space& home);
663 static void operator delete(void* p, Space& home);
665 public:
667 GECODE_KERNEL_EXPORT virtual ~Actor(void);
669 static void* operator new(size_t s);
671 static void operator delete(void* p);
672 };
673
674 class Home;
675
680 class Group {
681 friend class Home;
682 friend class Propagator;
683 friend class Brancher;
684 friend class ViewTraceInfo;
685 friend class PropagateTraceInfo;
686 friend class CommitTraceInfo;
687 friend class PostTraceInfo;
688 protected:
690 static const unsigned int GROUPID_ALL = 0U;
692 static const unsigned int GROUPID_DEF = 1U;
694 static const unsigned int GROUPID_MAX = UINT_MAX >> 2;
696 unsigned int gid;
699 static unsigned int next;
704 Group(unsigned int gid0);
705 public:
707
708
710 Group(void);
712 Group(const Group& g);
714 Group& operator =(const Group& g);
716 unsigned int id(void) const;
718 bool in(Group a) const;
720 bool in(void) const;
722
724 static Group all;
727 static Group def;
728 };
729
734 class PropagatorGroup : public Group {
735 friend class Propagator;
736 friend class ViewTraceInfo;
737 friend class PropagateTraceInfo;
738 friend class PostTraceInfo;
739 protected:
741 PropagatorGroup(unsigned int gid);
742 public:
744
745
746 PropagatorGroup(void);
752 Home operator ()(Space& home);
754
756
768 PropagatorGroup& move(Space& home, unsigned int id);
770
772
773 bool operator ==(PropagatorGroup g) const;
775 bool operator !=(PropagatorGroup g) const;
778 unsigned int size(Space& home) const;
781 void kill(Space& home);
784 void disable(Space& home);
792 void enable(Space& home, bool s=true);
794
800 };
801
806 class BrancherGroup : public Group {
807 friend class Brancher;
808 protected:
810 BrancherGroup(unsigned int gid);
811 public:
813
814
815 BrancherGroup(void);
821 Home operator ()(Space& home);
823
825
829 BrancherGroup& move(Space& home, Brancher& b);
837 BrancherGroup& move(Space& home, unsigned int id);
839
841
842 bool operator ==(BrancherGroup g) const;
844 bool operator !=(BrancherGroup g) const;
847 unsigned int size(Space& home) const;
850 void kill(Space& home);
852
858 };
859
863 class Home {
864 friend class PostInfo;
865 protected:
874 public:
876
877
878 Home(Space& s, Propagator* p=nullptr,
882 Home(const Home& h);
884 Home& operator =(const Home& h);
886 operator Space&(void);
888
890
897 Propagator* propagator(void) const;
901 BrancherGroup branchergroup(void) const;
903
905
906 bool failed(void) const;
908 void fail(void);
910 void notice(Actor& a, ActorProperty p, bool duplicate=false);
912 };
913
918 friend class Space;
919 friend class PostInfo;
920 public:
922 enum What {
928 POST = 2,
931 };
932 protected:
936 void propagator(Propagator& p);
938 void brancher(Brancher& b);
940 void post(PropagatorGroup g);
942 void other(void);
943 public:
945 What what(void) const;
947 const Propagator& propagator(void) const;
949 const Brancher& brancher(void) const;
951 PropagatorGroup post(void) const;
952 };
953
957 class PostInfo {
958 friend class Space;
959 protected:
965 unsigned int pid;
967 bool nested;
968 public:
970 PostInfo(Home home);
972 ~PostInfo(void);
973 };
974
979 friend class Space;
980 public:
988 protected:
990 unsigned int i;
994 const Propagator* p;
999 const Propagator* p, Status s);
1000 public:
1002 unsigned int id(void) const;
1004 PropagatorGroup group(void) const;
1006 const Propagator* propagator(void) const;
1008 Status status(void) const;
1009 };
1010
1015 friend class Space;
1016 protected:
1018 const Brancher& b;
1020 const Choice& c;
1022 unsigned int a;
1024 CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a);
1025 public:
1027 unsigned int id(void) const;
1029 BrancherGroup group(void) const;
1031 const Brancher& brancher(void) const;
1033 const Choice& choice(void) const;
1035 unsigned int alternative(void) const;
1036 };
1037
1042 friend class Space;
1043 friend class PostInfo;
1044 public:
1051 protected:
1057 unsigned int n;
1059 PostTraceInfo(PropagatorGroup g, Status s, unsigned int n);
1060 public:
1062 Status status(void) const;
1064 PropagatorGroup group(void) const;
1066 unsigned int propagators(void) const;
1067 };
1068
1074 friend class ActorLink;
1075 friend class Space;
1076 template<class VIC> friend class VarImp;
1077 friend class Advisor;
1078 template<class A> friend class Council;
1080 friend class PropagatorGroup;
1081 private:
1082 union {
1086 size_t size;
1089 } u;
1096 void* gpi_disabled;
1098 static Propagator* cast(ActorLink* al);
1100 static const Propagator* cast(const ActorLink* al);
1102 bool local_info(void) const;
1104 void disable(Space& home);
1106 void enable(Space& home);
1107 protected:
1109 Propagator(Home home);
1111 Propagator(Space& home, Propagator& p);
1113 Propagator* fwd(void) const;
1115 Kernel::GPI::Info& gpi(void);
1116
1117 public:
1119
1120
1128 virtual void reschedule(Space& home) = 0;
1152 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0;
1154 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0;
1162 ModEventDelta modeventdelta(void) const;
1199 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
1202 virtual void advise(Space& home, Advisor& a);
1204
1206
1207 double afc(void) const;
1209#ifdef GECODE_HAS_CBS
1211
1212
1219 typedef std::function<void(unsigned int prop_id, unsigned int var_id,
1220 int val, double dens)> SendMarginal;
1221 virtual void solndistrib(Space& home, SendMarginal send) const;
1230 typedef std::function<bool(unsigned int var_id)> InDecision;
1231 virtual void domainsizesum(InDecision in, unsigned int& size,
1232 unsigned int& size_b) const;
1234#endif
1236
1237
1238 unsigned int id(void) const;
1240 PropagatorGroup group(void) const;
1242 void group(PropagatorGroup g);
1244 bool disabled(void) const;
1246 };
1247
1248
1256 template<class A>
1257 class Council {
1258 friend class Advisor;
1259 friend class Advisors<A>;
1260 private:
1262 mutable ActorLink* advisors;
1263 public:
1265 Council(void);
1267 Council(Space& home);
1269 bool empty(void) const;
1271 void update(Space& home, Council<A>& c);
1273 void dispose(Space& home);
1274 };
1275
1276
1281 template<class A>
1282 class Advisors {
1283 private:
1285 ActorLink* a;
1286 public:
1288 Advisors(const Council<A>& c);
1290 bool operator ()(void) const;
1292 void operator ++(void);
1294 A& advisor(void) const;
1295 };
1296
1297
1308 class Advisor : private ActorLink {
1309 template<class VIC> friend class VarImp;
1310 template<class A> friend class Council;
1311 template<class A> friend class Advisors;
1313 private:
1315 bool disposed(void) const;
1317 static Advisor* cast(ActorLink* al);
1319 static const Advisor* cast(const ActorLink* al);
1321 static ActorLink* link(Advisor& a);
1322 protected:
1324 Propagator& propagator(void) const;
1325 public:
1327 template<class A>
1328 Advisor(Space& home, Propagator& p, Council<A>& c);
1330 Advisor(Space& home, Advisor& a);
1332 const ViewTraceInfo& operator ()(const Space& home) const;
1333
1335
1336
1337 template<class A>
1338 void dispose(Space& home, Council<A>& c);
1340 static void* operator new(size_t s, Space& home);
1342 static void operator delete(void* p, Space& home);
1344 private:
1345#ifndef __GNUC__
1347 static void operator delete(void* p);
1348#endif
1350 static void* operator new(size_t s);
1351 };
1352
1353
1359 private:
1361 void* nl;
1362 public:
1369
1370 NGL(void);
1372 NGL(Space& home);
1374 NGL(Space& home, NGL& ngl);
1376 virtual void subscribe(Space& home, Propagator& p) = 0;
1378 virtual void cancel(Space& home, Propagator& p) = 0;
1380 virtual void reschedule(Space& home, Propagator& p) = 0;
1382 virtual NGL::Status status(const Space& home) const = 0;
1384 virtual ExecStatus prune(Space& home) = 0;
1386 virtual NGL* copy(Space& home) = 0;
1389 virtual bool notice(void) const;
1391 virtual size_t dispose(Space& home);
1393
1394
1395 bool leaf(void) const;
1397 NGL* next(void) const;
1399 void leaf(bool l);
1401 void next(NGL* n);
1403 NGL* add(NGL* n, bool l);
1405
1407
1408 static void* operator new(size_t s, Space& home);
1410 static void operator delete(void* s, Space& home);
1412 static void operator delete(void* p);
1414 public:
1416 GECODE_KERNEL_EXPORT virtual ~NGL(void);
1418 static void* operator new(size_t s);
1419 };
1420
1431 friend class Space;
1432 private:
1433 unsigned int bid;
1434 unsigned int alt;
1435
1437 unsigned int id(void) const;
1438 protected:
1440 Choice(const Brancher& b, const unsigned int a);
1441 public:
1443 unsigned int alternatives(void) const;
1445 GECODE_KERNEL_EXPORT virtual ~Choice(void);
1448 virtual void archive(Archive& e) const;
1449 };
1450
1461 friend class ActorLink;
1462 friend class Space;
1463 friend class Choice;
1464 private:
1466 unsigned int bid;
1468 unsigned int gid;
1470 static Brancher* cast(ActorLink* al);
1472 static const Brancher* cast(const ActorLink* al);
1473 protected:
1475 Brancher(Home home);
1477 Brancher(Space& home, Brancher& b);
1478 public:
1480
1481
1489 virtual bool status(const Space& home) const = 0;
1497 virtual const Choice* choice(Space& home) = 0;
1499 virtual const Choice* choice(const Space& home, Archive& e) = 0;
1506 virtual ExecStatus commit(Space& home, const Choice& c,
1507 unsigned int a) = 0;
1522 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
1531 virtual void print(const Space& home, const Choice& c, unsigned int a,
1532 std::ostream& o) const;
1534
1536
1537 unsigned int id(void) const;
1539 BrancherGroup group(void) const;
1541 void group(BrancherGroup g);
1543 };
1544
1551 class LocalObject : public Actor {
1552 friend class ActorLink;
1553 friend class Space;
1554 friend class LocalHandle;
1555 protected:
1557 LocalObject(Home home);
1559 LocalObject(Space& home, LocalObject& l);
1561 static LocalObject* cast(ActorLink* al);
1563 static const LocalObject* cast(const ActorLink* al);
1564 private:
1566 GECODE_KERNEL_EXPORT void fwdcopy(Space& home);
1567 public:
1569 LocalObject* fwd(Space& home);
1570 };
1571
1577 private:
1579 LocalObject* o;
1580 protected:
1582 LocalHandle(void);
1586 LocalHandle(const LocalHandle& lh);
1587 public:
1591 void update(Space& home, LocalHandle& lh);
1593 ~LocalHandle(void);
1594 protected:
1596 LocalObject* object(void) const;
1598 void object(LocalObject* n);
1599 };
1600
1601
1607 protected:
1609 std::atomic<unsigned long int> n;
1610 public:
1612 NoGoods(void);
1614 NoGoods(const NoGoods& ng);
1616 NoGoods& operator =(const NoGoods& ng);
1619 virtual void post(Space& home) const;
1621 unsigned long int ng(void) const;
1623 void ng(unsigned long int n);
1625 virtual ~NoGoods(void);
1628 static NoGoods eng;
1629 };
1630
1636 public:
1644
1657 protected:
1659 const Type t;
1661
1662
1663 const unsigned long int r;
1667 const unsigned long long int s;
1669 const unsigned long long int f;
1671 const Space* l;
1673 const NoGoods& ng;
1675
1677
1678 const unsigned int a;
1680 public:
1682
1683
1684 MetaInfo(unsigned long int r,
1686 unsigned long long int s,
1687 unsigned long long int f,
1688 const Space* l,
1689 NoGoods& ng);
1691 MetaInfo(unsigned int a);
1693
1694 Type type(void) const;
1696
1697
1698 unsigned long int restart(void) const;
1700 RestartReason reason(void) const;
1702 unsigned long long int solution(void) const;
1704 unsigned long long int fail(void) const;
1706 const Space* last(void) const;
1713 const NoGoods& nogoods(void) const;
1715
1717
1718 unsigned int asset(void) const;
1720 };
1721
1731
1737 public:
1739 unsigned long long int propagate;
1741 StatusStatistics(void);
1743 void reset(void);
1748 };
1749
1755 public:
1757 CloneStatistics(void);
1759 void reset(void);
1764 };
1765
1771 public:
1773 CommitStatistics(void);
1775 void reset(void);
1780 };
1781
1782
1783
1788 friend class Actor;
1789 friend class Propagator;
1790 friend class PropagatorGroup;
1791 friend class Propagators;
1792 friend class Brancher;
1793 friend class BrancherGroup;
1794 friend class Branchers;
1795 friend class Advisor;
1796 template <class A> friend class Council;
1797 template<class VIC> friend class VarImp;
1798 template<class VarImp> friend class VarImpDisposer;
1799 friend class LocalObject;
1800 friend class Region;
1801 friend class AFC;
1802 friend class PostInfo;
1804 void trace(Home home, TraceFilter tf, int te, Tracer& t);
1805 private:
1807 GECODE_KERNEL_EXPORT void* local_info(unsigned int gid);
1812#ifdef GECODE_HAS_CBS
1814 unsigned int var_id_counter;
1815#endif
1817 bool no_gpi;
1819 ActorLink pl;
1821 ActorLink bl;
1827 ActorLink* b_status;
1839 ActorLink* b_commit;
1841 Brancher* brancher(unsigned int id);
1842
1844 void kill(Brancher& b);
1846 void kill(Propagator& p);
1847
1850 void kill_brancher(unsigned int id);
1851
1853 static const unsigned reserved_bid = 0U;
1854
1856 static const unsigned int sc_bits = 2;
1858 static const unsigned int sc_fast = 0;
1860 static const unsigned int sc_disabled = 1;
1862 static const unsigned int sc_trace = 2;
1863
1864 union {
1866 struct {
1888 unsigned int bid_sc;
1890 unsigned int n_sub;
1893 } p;
1895 struct {
1904 } c;
1905 } pc;
1907 void enqueue(Propagator* p);
1912#ifdef GECODE_HAS_VAR_DISPOSE
1914 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d];
1916 VarImpBase* _vars_d[AllVarConf::idx_d];
1918 template<class VIC> VarImpBase* vars_d(void) const;
1920 template<class VIC> void vars_d(VarImpBase* x);
1921#endif
1923 void update(ActorLink** sub);
1925
1927 void recover_noidx(void);
1928
1930 void recover(Space& source);
1931
1933 bool is_partial_clone(void) const;
1934
1936 Actor** d_fst;
1938 Actor** d_cur;
1940 Actor** d_lst;
1941
1943 GECODE_KERNEL_EXPORT static StatusStatistics unused_status;
1945 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone;
1947 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit;
1948
1962 GECODE_KERNEL_EXPORT Space* _clone(void);
1963
1997 void _commit(const Choice& c, unsigned int a);
1998
2030 void _trycommit(const Choice& c, unsigned int a);
2031
2034 TraceRecorder* findtracerecorder(void);
2037 void post(const PostInfo& pi);
2038
2046 void ap_notice_dispose(Actor* a, bool d);
2054 void ap_ignore_dispose(Actor* a, bool d);
2055 public:
2070 class NoGPI {
2071 private:
2073 Space& home;
2075 bool previous;
2076 NoGPI(const NoGPI&) = delete;
2077 NoGPI& operator =(const NoGPI&) = delete;
2078 public:
2080 explicit NoGPI(Space& home);
2082 ~NoGPI(void);
2083 };
2084
2092 class UseGPI {
2093 private:
2095 Space& home;
2097 bool previous;
2098 UseGPI(const UseGPI&) = delete;
2099 UseGPI& operator =(const UseGPI&) = delete;
2100 public:
2102 explicit UseGPI(Space& home);
2104 ~UseGPI(void);
2105 };
2106
2112 Space(void);
2125 Space(Space& s);
2127 Space& operator =(const Space& s) = default;
2133 virtual ~Space(void);
2144 virtual Space* copy(void) = 0;
2155 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best);
2180 virtual bool master(const MetaInfo& mi);
2212 virtual bool slave(const MetaInfo& mi);
2213
2214 /*
2215 * Member functions for search engines
2216 *
2217 */
2218
2233 SpaceStatus status(void);
2234
2267 const Choice* choice(void);
2268
2279 const Choice* choice(Archive& e) const;
2280
2297 Space* clone(void) const;
2299 Space* clone(CloneStatistics& stat) const;
2300
2336 void commit(const Choice& c, unsigned int a);
2338 void commit(const Choice& c, unsigned int a,
2339 CommitStatistics& stat);
2373 void trycommit(const Choice& c, unsigned int a);
2375 void trycommit(const Choice& c, unsigned int a,
2376 CommitStatistics& stat);
2396 NGL* ngl(const Choice& c, unsigned int a);
2397
2413 void print(const Choice& c, unsigned int a, std::ostream& o) const;
2414
2424 void notice(Actor& a, ActorProperty p, bool duplicate=false);
2433 void ignore(Actor& a, ActorProperty p, bool duplicate=false);
2434
2435
2484
2495 template<class A>
2507 template<class A>
2520 template<class A>
2522
2530 void fail(void);
2539 bool failed(void) const;
2544 bool stable(void) const;
2545
2547
2548
2549 Home operator ()(Propagator& p);
2551 Home operator ()(PropagatorGroup pg);
2553 Home operator ()(BrancherGroup bg);
2555
2561
2567 template<class T>
2568 T* alloc(long unsigned int n);
2575 template<class T>
2576 T* alloc(long int n);
2583 template<class T>
2584 T* alloc(unsigned int n);
2591 template<class T>
2592 T* alloc(int n);
2602 template<class T>
2603 void free(T* b, long unsigned int n);
2613 template<class T>
2614 void free(T* b, long int n);
2624 template<class T>
2625 void free(T* b, unsigned int n);
2635 template<class T>
2636 void free(T* b, int n);
2648 template<class T>
2649 T* realloc(T* b, long unsigned int n, long unsigned int m);
2661 template<class T>
2662 T* realloc(T* b, long int n, long int m);
2674 template<class T>
2675 T* realloc(T* b, unsigned int n, unsigned int m);
2687 template<class T>
2688 T* realloc(T* b, int n, int m);
2696 template<class T>
2697 T** realloc(T** b, long unsigned int n, long unsigned int m);
2705 template<class T>
2706 T** realloc(T** b, long int n, long int m);
2714 template<class T>
2715 T** realloc(T** b, unsigned int n, unsigned int m);
2723 template<class T>
2724 T** realloc(T** b, int n, int m);
2726 void* ralloc(size_t s);
2728 void rfree(void* p, size_t s);
2730 void* rrealloc(void* b, size_t n, size_t m);
2732 template<size_t> void* fl_alloc(void);
2738 template<size_t> void fl_dispose(FreeList* f, FreeList* l);
2740
2742
2745 template<class T>
2746 T& construct(void);
2752 template<class T, typename A1>
2753 T& construct(A1 const& a1);
2759 template<class T, typename A1, typename A2>
2760 T& construct(A1 const& a1, A2 const& a2);
2766 template<class T, typename A1, typename A2, typename A3>
2767 T& construct(A1 const& a1, A2 const& a2, A3 const& a3);
2773 template<class T, typename A1, typename A2, typename A3, typename A4>
2774 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4);
2780 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
2781 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5);
2783
2785
2786
2787 void afc_decay(double d);
2789 double afc_decay(void) const;
2793
2794 protected:
2801 private:
2803 Space& home;
2805 ActorLink* q;
2807 ActorLink* c;
2809 ActorLink* e;
2810 public:
2812 Propagators(Space& home);
2814 bool operator ()(void) const;
2816 void operator ++(void);
2818 Propagator& propagator(void) const;
2819 };
2820
2826 private:
2828 Space& home;
2830 ActorLink* q;
2832 ActorLink* c;
2834 ActorLink* e;
2835 public:
2839 bool operator ()(void) const;
2841 void operator ++(void);
2843 Propagator& propagator(void) const;
2844 };
2845
2851 private:
2853 ActorLink* c;
2855 ActorLink* e;
2856 public:
2858 IdlePropagators(Space& home);
2860 bool operator ()(void) const;
2862 void operator ++(void);
2864 Propagator& propagator(void) const;
2865 };
2866
2872 private:
2874 ActorLink* c;
2876 ActorLink* e;
2877 public:
2879 Branchers(Space& home);
2881 bool operator ()(void) const;
2883 void operator ++(void);
2885 Brancher& brancher(void) const;
2886 };
2887 };
2888
2891 private:
2896 public:
2898 Propagators(const Space& home, PropagatorGroup g);
2900 bool operator ()(void) const;
2902 void operator ++(void);
2904 const Propagator& propagator(void) const;
2905 };
2906
2909 private:
2913 BrancherGroup g;
2914 public:
2916 Branchers(const Space& home, BrancherGroup g);
2918 bool operator ()(void) const;
2920 void operator ++(void);
2922 const Brancher& brancher(void) const;
2923 };
2924
2925
2926
2927
2928 /*
2929 * Memory management
2930 *
2931 */
2932
2933 // Space allocation: general space heaps and free lists
2934 forceinline void*
2935 Space::ralloc(size_t s) {
2936 return mm.alloc(ssd.data().sm,s);
2937 }
2938 forceinline void
2939 Space::rfree(void* p, size_t s) {
2940 return mm.reuse(p,s);
2941 }
2942 forceinline void*
2943 Space::rrealloc(void* _b, size_t n, size_t m) {
2944 char* b = static_cast<char*>(_b);
2945 if (n < m) {
2946 char* p = static_cast<char*>(ralloc(m));
2947 memcpy(p,b,n);
2948 rfree(b,n);
2949 return p;
2950 } else {
2951 rfree(b+m,m-n);
2952 return b;
2953 }
2954 }
2955
2956 template<size_t s>
2957 forceinline void*
2959 return mm.template fl_alloc<s>(ssd.data().sm);
2960 }
2961 template<size_t s>
2962 forceinline void
2964 mm.template fl_dispose<s>(f,l);
2965 }
2966
2967 /*
2968 * Typed allocation routines
2969 *
2970 */
2971 template<class T>
2972 forceinline T*
2973 Space::alloc(long unsigned int n) {
2974 T* p = static_cast<T*>(ralloc(sizeof(T)*n));
2975 for (long unsigned int i=0; i<n; i++)
2976 (void) new (p+i) T();
2977 return p;
2978 }
2979 template<class T>
2980 forceinline T*
2981 Space::alloc(long int n) {
2982 assert(n >= 0);
2983 return alloc<T>(static_cast<long unsigned int>(n));
2984 }
2985 template<class T>
2986 forceinline T*
2987 Space::alloc(unsigned int n) {
2988 return alloc<T>(static_cast<long unsigned int>(n));
2989 }
2990 template<class T>
2991 forceinline T*
2993 assert(n >= 0);
2994 return alloc<T>(static_cast<long unsigned int>(n));
2995 }
2996
2997 template<class T>
2998 forceinline void
2999 Space::free(T* b, long unsigned int n) {
3000 for (long unsigned int i=0; i<n; i++)
3001 b[i].~T();
3002 rfree(b,n*sizeof(T));
3003 }
3004 template<class T>
3005 forceinline void
3006 Space::free(T* b, long int n) {
3007 assert(n >= 0);
3008 free<T>(b,static_cast<long unsigned int>(n));
3009 }
3010 template<class T>
3011 forceinline void
3012 Space::free(T* b, unsigned int n) {
3013 free<T>(b,static_cast<long unsigned int>(n));
3014 }
3015 template<class T>
3016 forceinline void
3017 Space::free(T* b, int n) {
3018 assert(n >= 0);
3019 free<T>(b,static_cast<long unsigned int>(n));
3020 }
3021
3022 template<class T>
3023 forceinline T*
3024 Space::realloc(T* b, long unsigned int n, long unsigned int m) {
3025 if (n < m) {
3026 T* p = static_cast<T*>(ralloc(sizeof(T)*m));
3027 for (long unsigned int i=0; i<n; i++)
3028 (void) new (p+i) T(b[i]);
3029 for (long unsigned int i=n; i<m; i++)
3030 (void) new (p+i) T();
3031 free<T>(b,n);
3032 return p;
3033 } else {
3034 free<T>(b+m,m-n);
3035 return b;
3036 }
3037 }
3038 template<class T>
3039 forceinline T*
3040 Space::realloc(T* b, long int n, long int m) {
3041 assert((n >= 0) && (m >= 0));
3042 return realloc<T>(b,static_cast<long unsigned int>(n),
3043 static_cast<long unsigned int>(m));
3044 }
3045 template<class T>
3046 forceinline T*
3047 Space::realloc(T* b, unsigned int n, unsigned int m) {
3048 return realloc<T>(b,static_cast<long unsigned int>(n),
3049 static_cast<long unsigned int>(m));
3050 }
3051 template<class T>
3052 forceinline T*
3053 Space::realloc(T* b, int n, int m) {
3054 assert((n >= 0) && (m >= 0));
3055 return realloc<T>(b,static_cast<long unsigned int>(n),
3056 static_cast<long unsigned int>(m));
3057 }
3058
3059#define GECODE_KERNEL_REALLOC(T) \
3060 template<> \
3061 forceinline T* \
3062 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
3063 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
3064 } \
3065 template<> \
3066 forceinline T* \
3067 Space::realloc<T>(T* b, long int n, long int m) { \
3068 assert((n >= 0) && (m >= 0)); \
3069 return realloc<T>(b,static_cast<long unsigned int>(n), \
3070 static_cast<long unsigned int>(m)); \
3071 } \
3072 template<> \
3073 forceinline T* \
3074 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
3075 return realloc<T>(b,static_cast<long unsigned int>(n), \
3076 static_cast<long unsigned int>(m)); \
3077 } \
3078 template<> \
3079 forceinline T* \
3080 Space::realloc<T>(T* b, int n, int m) { \
3081 assert((n >= 0) && (m >= 0)); \
3082 return realloc<T>(b,static_cast<long unsigned int>(n), \
3083 static_cast<long unsigned int>(m)); \
3084 }
3085
3087 GECODE_KERNEL_REALLOC(signed char)
3088 GECODE_KERNEL_REALLOC(unsigned char)
3089 GECODE_KERNEL_REALLOC(signed short int)
3090 GECODE_KERNEL_REALLOC(unsigned short int)
3091 GECODE_KERNEL_REALLOC(signed int)
3092 GECODE_KERNEL_REALLOC(unsigned int)
3093 GECODE_KERNEL_REALLOC(signed long int)
3094 GECODE_KERNEL_REALLOC(unsigned long int)
3096 GECODE_KERNEL_REALLOC(double)
3097
3098#undef GECODE_KERNEL_REALLOC
3099
3100 template<class T>
3101 forceinline T**
3102 Space::realloc(T** b, long unsigned int n, long unsigned int m) {
3103 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*)));
3104 }
3105 template<class T>
3106 forceinline T**
3107 Space::realloc(T** b, long int n, long int m) {
3108 assert((n >= 0) && (m >= 0));
3109 return realloc<T*>(b,static_cast<long unsigned int>(n),
3110 static_cast<long unsigned int>(m));
3111 }
3112 template<class T>
3113 forceinline T**
3114 Space::realloc(T** b, unsigned int n, unsigned int m) {
3115 return realloc<T*>(b,static_cast<long unsigned int>(n),
3116 static_cast<long unsigned int>(m));
3117 }
3118 template<class T>
3119 forceinline T**
3120 Space::realloc(T** b, int n, int m) {
3121 assert((n >= 0) && (m >= 0));
3122 return realloc<T*>(b,static_cast<long unsigned int>(n),
3123 static_cast<long unsigned int>(m));
3124 }
3125
3126
3127#ifdef GECODE_HAS_VAR_DISPOSE
3128 template<class VIC>
3130 Space::vars_d(void) const {
3131 return _vars_d[VIC::idx_d];
3132 }
3133 template<class VIC>
3134 forceinline void
3135 Space::vars_d(VarImpBase* x) {
3136 _vars_d[VIC::idx_d] = x;
3137 }
3138#endif
3139
3140 forceinline bool
3141 Space::is_partial_clone(void) const {
3142 return d_fst == &Actor::sentinel;
3143 }
3144
3145 // Space allocated entities: Actors, variable implementations, and advisors
3146 forceinline void
3147 Actor::operator delete(void*) {}
3148 forceinline void
3149 Actor::operator delete(void*, Space&) {}
3150 forceinline void*
3151 Actor::operator new(size_t s, Space& home) {
3152 return home.ralloc(s);
3153 }
3154
3155 template<class VIC>
3156 forceinline void
3157 VarImp<VIC>::operator delete(void*) {}
3158 template<class VIC>
3159 forceinline void
3160 VarImp<VIC>::operator delete(void*, Space&) {}
3161 template<class VIC>
3162 forceinline void*
3163 VarImp<VIC>::operator new(size_t s, Space& home) {
3164 return home.ralloc(s);
3165 }
3166
3167#ifndef __GNUC__
3168 forceinline void
3169 Advisor::operator delete(void*) {}
3170#endif
3171 forceinline void
3172 Advisor::operator delete(void*, Space&) {}
3173 forceinline void*
3174 Advisor::operator new(size_t s, Space& home) {
3175 return home.ralloc(s);
3176 }
3177
3178 forceinline void
3179 NGL::operator delete(void*) {}
3180 forceinline void
3181 NGL::operator delete(void*, Space&) {}
3182 forceinline void*
3183 NGL::operator new(size_t s, Space& home) {
3184 return home.ralloc(s);
3185 }
3186
3187
3188 /*
3189 * No-goods
3190 *
3191 */
3194 : n(0) {}
3197 : n(ng0.ng()) {}
3200 ng(ng0.ng());
3201 return *this;
3202 }
3203 forceinline unsigned long int
3204 NoGoods::ng(void) const {
3205 return n.load(std::memory_order_acquire);
3206 }
3207 forceinline void
3208 NoGoods::ng(unsigned long int n0) {
3209 n.store(n0, std::memory_order_release);
3210 }
3213
3214
3215 /*
3216 * Information from meta search engines
3217 */
3219 MetaInfo::MetaInfo(unsigned long int r0,
3220 RestartReason rr0,
3221 unsigned long long int s0,
3222 unsigned long long int f0,
3223 const Space* l0,
3224 NoGoods& ng0)
3225 : t(RESTART), r(r0), rr(rr0), s(s0), f(f0), l(l0), ng(ng0), a(0) {}
3226
3228 MetaInfo::MetaInfo(unsigned int a0)
3229 : t(PORTFOLIO), r(0), rr(RR_NO), s(0), f(0), l(nullptr), ng(NoGoods::eng), a(a0) {}
3230
3232 MetaInfo::type(void) const {
3233 return t;
3234 }
3235 forceinline unsigned long int
3236 MetaInfo::restart(void) const {
3237 assert(type() == RESTART);
3238 return r;
3239 }
3241 MetaInfo::reason(void) const {
3242 return rr;
3243 }
3244 forceinline unsigned long long int
3246 assert(type() == RESTART);
3247 return s;
3248 }
3249 forceinline unsigned long long int
3250 MetaInfo::fail(void) const {
3251 assert(type() == RESTART);
3252 return f;
3253 }
3254 forceinline const Space*
3255 MetaInfo::last(void) const {
3256 assert(type() == RESTART);
3257 return l;
3258 }
3259 forceinline const NoGoods&
3260 MetaInfo::nogoods(void) const {
3261 assert(type() == RESTART);
3262 return ng;
3263 }
3264 forceinline unsigned int
3265 MetaInfo::asset(void) const {
3266 assert(type() == PORTFOLIO);
3267 return a;
3268 }
3269
3270
3271
3272 /*
3273 * ActorLink
3274 *
3275 */
3277 ActorLink::prev(void) const {
3278 return _prev;
3279 }
3280
3282 ActorLink::next(void) const {
3283 return _next;
3284 }
3285
3288 return &_next;
3289 }
3290
3291 forceinline void
3293 _prev = al;
3294 }
3295
3296 forceinline void
3298 _next = al;
3299 }
3300
3301 forceinline void
3303 ActorLink* p = _prev; ActorLink* n = _next;
3304 p->_next = n; n->_prev = p;
3305 }
3306
3307 forceinline void
3309 _next = this; _prev =this;
3310 }
3311
3312 forceinline void
3314 // Inserts al at head of link-chain (that is, after this)
3315 ActorLink* n = _next;
3316 this->_next = a; a->_prev = this;
3317 a->_next = n; n->_prev = a;
3318 }
3319
3320 forceinline void
3322 // Inserts al at tail of link-chain (that is, before this)
3323 ActorLink* p = _prev;
3324 a->_next = this; this->_prev = a;
3325 p->_next = a; a->_prev = p;
3326 }
3327
3328 forceinline bool
3329 ActorLink::empty(void) const {
3330 return _next == this;
3331 }
3332
3333 template<class T>
3336 // Turning al into a reference is for gcc, assume is for MSVC
3337 GECODE_NOT_NULL(a);
3338 ActorLink& t = *a;
3339 return static_cast<ActorLink*>(&t);
3340 }
3341
3342 template<class T>
3343 forceinline const ActorLink*
3344 ActorLink::cast(const T* a) {
3345 // Turning al into a reference is for gcc, assume is for MSVC
3346 GECODE_NOT_NULL(a);
3347 const ActorLink& t = *a;
3348 return static_cast<const ActorLink*>(&t);
3349 }
3350
3351
3352 /*
3353 * Actor
3354 *
3355 */
3357 Actor::cast(ActorLink* al) {
3358 // Turning al into a reference is for gcc, assume is for MSVC
3359 GECODE_NOT_NULL(al);
3360 ActorLink& t = *al;
3361 return static_cast<Actor*>(&t);
3362 }
3363
3364 forceinline const Actor*
3365 Actor::cast(const ActorLink* al) {
3366 // Turning al into a reference is for gcc, assume is for MSVC
3367 GECODE_NOT_NULL(al);
3368 const ActorLink& t = *al;
3369 return static_cast<const Actor*>(&t);
3370 }
3371
3372 forceinline void
3373 Home::notice(Actor& a, ActorProperty p, bool duplicate) {
3374 s.notice(a,p,duplicate);
3375 }
3376
3379 StatusStatistics stat;
3380 return status(stat);
3381 }
3382
3384 Space::clone(void) const {
3385 CloneStatistics stat;
3386 return clone(stat);
3387 }
3388
3391 // Clone is only const for search engines. During cloning, several data
3392 // structures are updated (e.g. forwarding pointers), so we have to
3393 // cast away the constness.
3394 return const_cast<Space*>(this)->_clone();
3395 }
3396
3397 forceinline void
3398 Space::commit(const Choice& c, unsigned int a) {
3399 CommitStatistics stat;
3400 commit(c,a,stat);
3401 }
3402
3403 forceinline void
3404 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) {
3405 _commit(c,a);
3406 }
3407
3408 forceinline void
3409 Space::trycommit(const Choice& c, unsigned int a) {
3410 CommitStatistics stat;
3411 trycommit(c,a,stat);
3412 }
3413
3414 forceinline void
3415 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) {
3416 _trycommit(c,a);
3417 }
3418
3419 forceinline double
3420 Space::afc_decay(void) const {
3421 return ssd.data().gpi.decay();
3422 }
3423
3424 forceinline void
3426 ssd.data().gpi.decay(d);
3427 }
3428
3429 forceinline size_t
3431 return sizeof(*this);
3432 }
3433
3434
3435 /*
3436 * Home for posting actors
3437 *
3438 */
3442 : s(s0), p(p0), pg(pg0), bg(bg0) {}
3445 : s(h.s), p(h.p), pg(h.pg), bg(h.bg) {}
3448 s=h.s; p=h.p; pg=h.pg; bg=h.bg;
3449 return *this;
3450 }
3452 Home::operator Space&(void) {
3453 return s;
3454 }
3457 return Home(s,&p);
3458 }
3469 return Home(*this,&p);
3470 }
3473 return Home(*this,nullptr,pg,BrancherGroup::def);
3474 }
3477 return Home(*this,nullptr,PropagatorGroup::def,bg);
3478 }
3480 Home::propagator(void) const {
3481 return p;
3482 }
3485 return pg;
3486 }
3489 return bg;
3490 }
3491
3492 /*
3493 * View trace information
3494 *
3495 */
3496 forceinline void
3498 who = reinterpret_cast<Support::uptrint_t>(&p) | PROPAGATOR;
3499 }
3500 forceinline void
3502 who = reinterpret_cast<Support::uptrint_t>(&b) | BRANCHER;
3503 }
3504 forceinline void
3506 who = (static_cast<Support::uptrint_t>(g.id()) << 2) | POST;
3507 }
3508 forceinline void
3510 who = OTHER;
3511 }
3514 return static_cast<What>(who & 0b11);
3515 }
3516 forceinline const Propagator&
3518 assert(what() == PROPAGATOR);
3519 // Because PROPAGATOR == 0
3520 return *reinterpret_cast<Propagator*>(who);
3521 }
3522 forceinline const Brancher&
3524 assert(what() == BRANCHER);
3525 return *reinterpret_cast<Brancher*>
3526 (who & ~static_cast<Support::uptrint_t>(0b11));
3527 }
3530 assert(what() == POST);
3531 return PropagatorGroup(static_cast<unsigned int>(who >> 2));
3532 }
3533
3534 /*
3535 * Post information
3536 */
3539 : h(home), pg(home.propagatorgroup()),
3540 pid(h.ssd.data().gpi.pid()),
3541 nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) {
3542 h.pc.p.vti.post(pg);
3543 }
3544
3547 if (!nested) {
3548 if (h.pc.p.bid_sc & Space::sc_trace)
3549 h.post(*this);
3550 h.pc.p.vti.other();
3551 }
3552 }
3553
3554
3555 /*
3556 * Propagate trace information
3557 *
3558 */
3561 const Propagator* p0, Status s0)
3562 : i(i0), g(g0), p(p0), s(s0) {}
3563 forceinline unsigned int
3565 return i;
3566 }
3569 return g;
3570 }
3571 forceinline const Propagator*
3573 return p;
3574 }
3577 return s;
3578 }
3579
3580
3581 /*
3582 * Commit trace information
3583 *
3584 */
3587 unsigned int a0)
3588 : b(b0), c(c0), a(a0) {}
3589 forceinline unsigned int
3591 return b.id();
3592 }
3595 return b.group();
3596 }
3597 forceinline const Brancher&
3599 return b;
3600 }
3601 forceinline const Choice&
3603 return c;
3604 }
3605 forceinline unsigned int
3607 return a;
3608 }
3609
3610
3611 /*
3612 * Post trace information
3613 *
3614 */
3617 : g(g0), s(s0), n(n0) {}
3620 return g;
3621 }
3624 return s;
3625 }
3626 forceinline unsigned int
3628 return n;
3629 }
3630
3631
3633 Space::NoGPI::NoGPI(Space& h) : home(h), previous(h.no_gpi) {
3634 home.no_gpi = true;
3635 }
3636
3639 home.no_gpi = previous;
3640 }
3641
3642
3644 Space::UseGPI::UseGPI(Space& h) : home(h), previous(h.no_gpi) {
3645 home.no_gpi = false;
3646 }
3647
3650 home.no_gpi = previous;
3651 }
3652
3653
3654 /*
3655 * Propagator
3656 *
3657 */
3659 Propagator::cast(ActorLink* al) {
3660 // Turning al into a reference is for gcc, assume is for MSVC
3661 GECODE_NOT_NULL(al);
3662 ActorLink& t = *al;
3663 return static_cast<Propagator*>(&t);
3664 }
3665
3666 forceinline const Propagator*
3667 Propagator::cast(const ActorLink* al) {
3668 // Turning al into a reference is for gcc, assume is for MSVC
3669 GECODE_NOT_NULL(al);
3670 const ActorLink& t = *al;
3671 return static_cast<const Propagator*>(&t);
3672 }
3673
3675 Propagator::fwd(void) const {
3676 return static_cast<Propagator*>(prev());
3677 }
3678
3679 forceinline bool
3680 Propagator::local_info(void) const {
3681 return (reinterpret_cast<Support::uptrint_t>(gpi_disabled) & 0b10) != 0;
3682 }
3683
3684 forceinline bool
3686 return Support::marked(gpi_disabled);
3687 }
3688
3689 forceinline void
3690 Propagator::disable(Space& home) {
3691 home.pc.p.bid_sc |= Space::sc_disabled;
3692 gpi_disabled = Support::fmark(gpi_disabled);
3693 }
3694
3695 forceinline void
3696 Propagator::enable(Space& home) {
3697 (void) home;
3698 gpi_disabled = Support::funmark(gpi_disabled);
3699 }
3700
3701 forceinline Kernel::GPI::Info&
3703 return *static_cast<Kernel::GPI::Info*>(Support::funmark<2>(gpi_disabled));
3704 }
3705
3708 : gpi_disabled((home.propagator() != nullptr) ?
3709 // Inherit propagator information
3710 home.propagator()->gpi_disabled :
3711 static_cast<Space&>(home).no_gpi ?
3712 static_cast<Space&>(home).local_info
3713 (home.propagatorgroup().gid) :
3714 // New propagator information
3715 static_cast<Space&>(home).ssd.data().gpi.allocate
3716 (home.propagatorgroup().gid)) {
3717 u.advisors = nullptr;
3718 assert((u.med == 0) && (u.size == 0));
3719 static_cast<Space&>(home).pl.head(this);
3720 }
3721
3724 : gpi_disabled(p.gpi_disabled) {
3725 if (p.local_info()) {
3726 Kernel::GPI::Info* i = home.alloc<Kernel::GPI::Info>(1);
3727 *i = p.gpi();
3728 gpi_disabled = Support::ptrjoin(i, p.disabled() ? 0b11 : 0b10);
3729 }
3730 u.advisors = nullptr;
3731 assert((u.med == 0) && (u.size == 0));
3732 // Set forwarding pointer
3733 p.prev(this);
3734 }
3735
3738 return u.med;
3739 }
3740
3741 forceinline double
3742 Propagator::afc(void) const {
3743 return const_cast<Propagator&>(*this).gpi().afc;
3744 }
3745
3746#ifdef GECODE_HAS_CBS
3747 forceinline void
3748 Propagator::solndistrib(Space&, SendMarginal) const {}
3749
3750 forceinline void
3751 Propagator::domainsizesum(InDecision, unsigned int& size,
3752 unsigned int& size_b) const {
3753 size = 0;
3754 size_b = 0;
3755 }
3756#endif
3757
3758 forceinline unsigned int
3759 Propagator::id(void) const {
3760 return const_cast<Propagator&>(*this).gpi().pid;
3761 }
3762
3764 Propagator::group(void) const {
3765 return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid);
3766 }
3767
3768 forceinline void
3770 gpi().gid = g.id();
3771 }
3772
3775 p.u.size = s;
3776 return ES_SUBSUMED_;
3777 }
3778
3781 p.u.size = p.dispose(*this);
3782 return ES_SUBSUMED_;
3783 }
3784
3787 p.u.med = med;
3788 assert(p.u.med != 0);
3789 return ES_PARTIAL_;
3790 }
3791
3794 p.u.med = AllVarConf::med_combine(p.u.med,med);
3795 assert(p.u.med != 0);
3796 return ES_PARTIAL_;
3797 }
3798
3799
3800
3801 /*
3802 * Brancher
3803 *
3804 */
3806 Brancher::cast(ActorLink* al) {
3807 // Turning al into a reference is for gcc, assume is for MSVC
3808 GECODE_NOT_NULL(al);
3809 ActorLink& t = *al;
3810 return static_cast<Brancher*>(&t);
3811 }
3812
3813 forceinline const Brancher*
3814 Brancher::cast(const ActorLink* al) {
3815 // Turning al into a reference is for gcc, assume is for MSVC
3816 GECODE_NOT_NULL(al);
3817 const ActorLink& t = *al;
3818 return static_cast<const Brancher*>(&t);
3819 }
3820
3823 gid(_home.branchergroup().gid) {
3824 Space& home = static_cast<Space&>(_home);
3825 bid = home.pc.p.bid_sc >> Space::sc_bits;
3826 home.pc.p.bid_sc += (1 << Space::sc_bits);
3827 if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U)
3828 throw TooManyBranchers("Brancher::Brancher");
3829 // If no brancher available, make it the first one
3830 if (home.b_status == &static_cast<Space&>(home).bl) {
3831 home.b_status = this;
3832 if (home.b_commit == &static_cast<Space&>(home).bl)
3833 home.b_commit = this;
3834 }
3835 home.bl.tail(this);
3836 }
3837
3840 : bid(b.bid), gid(b.gid) {
3841 // Set forwarding pointer
3842 b.prev(this);
3843 }
3844
3845 forceinline unsigned int
3846 Brancher::id(void) const {
3847 return bid;
3848 }
3849
3851 Brancher::group(void) const {
3852 return BrancherGroup(gid);
3853 }
3854
3855 forceinline void
3857 gid = g.id();
3858 }
3859
3860
3861 forceinline void
3862 Space::kill(Brancher& b) {
3863 assert(!failed());
3864 // Make sure that neither b_status nor b_commit does not point to b!
3865 if (b_commit == &b)
3866 b_commit = b.next();
3867 if (b_status == &b)
3868 b_status = b.next();
3869 b.unlink();
3870 rfree(&b,b.dispose(*this));
3871 }
3872
3873 forceinline void
3874 Space::kill(Propagator& p) {
3875 assert(!failed());
3876 p.unlink();
3877 rfree(&p,p.dispose(*this));
3878 // Is the space already stable?
3879 if (pc.p.active < &pc.p.queue[0])
3880 return;
3881 // Enforce that empty queues are ignored
3882 do {
3883 assert(pc.p.active >= &pc.p.queue[0]);
3884 // First propagator or link back to queue?
3885 if (pc.p.active != pc.p.active->next())
3886 return; // A propagator is left in the queue
3887 } while (--pc.p.active >= &pc.p.queue[0]);
3888 // The space is stable now
3889 assert(pc.p.active < &pc.p.queue[0]);
3890 }
3891
3893 Space::brancher(unsigned int id) {
3894 /*
3895 * Due to weakly monotonic propagators the following scenario might
3896 * occur: a brancher has been committed with all its available
3897 * choices. Then, propagation determines less information
3898 * than before and the brancher now will create new choices.
3899 * Later, during recomputation, all of these choices
3900 * can be used together, possibly interleaved with
3901 * choices for other branchers. That means all branchers
3902 * must be scanned to find the matching brancher for the choice.
3903 *
3904 * b_commit tries to optimize scanning as it is most likely that
3905 * recomputation does not generate new choices during recomputation
3906 * and hence b_commit is moved from newer to older branchers.
3907 */
3908 ActorLink* b_old = b_commit;
3909 // Try whether we are lucky
3910 while (b_commit != &bl)
3911 if (id != Brancher::cast(b_commit)->id())
3912 b_commit = b_commit->next();
3913 else
3914 return Brancher::cast(b_commit);
3915 if (b_commit == &bl) {
3916 // We did not find the brancher, start at the beginning
3917 b_commit = bl.next();
3918 while (b_commit != b_old)
3919 if (id != Brancher::cast(b_commit)->id())
3920 b_commit = b_commit->next();
3921 else
3922 return Brancher::cast(b_commit);
3923 }
3924 return nullptr;
3925 }
3926
3927
3928 /*
3929 * Local objects
3930 *
3931 */
3932
3935 // Turning al into a reference is for gcc, assume is for MSVC
3936 GECODE_NOT_NULL(al);
3937 ActorLink& t = *al;
3938 return static_cast<LocalObject*>(&t);
3939 }
3940
3943 // Turning al into a reference is for gcc, assume is for MSVC
3944 GECODE_NOT_NULL(al);
3945 const ActorLink& t = *al;
3946 return static_cast<const LocalObject*>(&t);
3947 }
3948
3951 (void) home;
3952 ActorLink::cast(this)->prev(nullptr);
3953 }
3954
3959
3962 if (prev() == nullptr)
3963 fwdcopy(home);
3964 return LocalObject::cast(prev());
3965 }
3966
3968 LocalHandle::LocalHandle(void) : o(nullptr) {}
3975 o = lh.o;
3976 return *this;
3977 }
3981 LocalHandle::object(void) const { return o; }
3982 forceinline void
3984 forceinline void
3986 object(lh.object()->fwd(home));
3987 }
3988
3989
3990 /*
3991 * Choices
3992 *
3993 */
3995 Choice::Choice(const Brancher& b, const unsigned int a)
3996 : bid(b.id()), alt(a) {}
3997
3998 forceinline unsigned int
4000 return alt;
4001 }
4002
4003 forceinline unsigned int
4004 Choice::id(void) const {
4005 return bid;
4006 }
4007
4010
4011
4012
4013 /*
4014 * No-good literal
4015 *
4016 */
4017 forceinline bool
4018 NGL::leaf(void) const {
4019 return Support::marked(nl);
4020 }
4022 NGL::next(void) const {
4023 return static_cast<NGL*>(Support::funmark(nl));
4024 }
4025 forceinline void
4026 NGL::leaf(bool l) {
4027 nl = l ? Support::fmark(nl) : Support::funmark(nl);
4028 }
4029 forceinline void
4031 nl = Support::marked(nl) ? Support::mark(n) : n;
4032 }
4034 NGL::add(NGL* n, bool l) {
4035 nl = Support::marked(nl) ? Support::mark(n) : n;
4036 n->leaf(l);
4037 return n;
4038 }
4039
4042 : nl(nullptr) {}
4045 : nl(nullptr) {}
4048 : nl(nullptr) {}
4049 forceinline size_t
4051 return sizeof(*this);
4052 }
4053
4054 /*
4055 * Advisor
4056 *
4057 */
4058 template<class A>
4061 // Store propagator and forwarding in prev()
4062 ActorLink::prev(&p);
4063 // Link to next advisor in next()
4064 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this);
4065 }
4066
4069
4070 forceinline bool
4071 Advisor::disposed(void) const {
4072 return prev() == nullptr;
4073 }
4074
4075 forceinline Advisor*
4076 Advisor::cast(ActorLink* al) {
4077 return static_cast<Advisor*>(al);
4078 }
4079
4080 forceinline const Advisor*
4081 Advisor::cast(const ActorLink* al) {
4082 return static_cast<const Advisor*>(al);
4083 }
4084
4086 Advisor::link(Advisor& a) {
4087 return static_cast<ActorLink*>(&a);
4088 }
4089
4092 assert(!disposed());
4093 return *Propagator::cast(ActorLink::prev());
4094 }
4095
4096 template<class A>
4097 forceinline void
4099 assert(!disposed());
4100 ActorLink::prev(nullptr);
4101 // Shorten chains of disposed advisors by one, if possible
4102 Advisor* n = Advisor::cast(next());
4103 if ((n != nullptr) && n->disposed())
4104 next(n->next());
4105 }
4106
4108 Advisor::operator ()(const Space& home) const {
4109 return home.pc.p.vti;
4110 }
4111
4112 template<class A>
4115 a.dispose(*this,c);
4116 return ES_FIX;
4117 }
4118
4119 template<class A>
4122 a.dispose(*this,c);
4123 return ES_NOFIX;
4124 }
4125
4126 template<class A>
4129 a.dispose(*this,c);
4130 return ES_NOFIX_FORCE;
4131 }
4132
4133
4134
4135 /*
4136 * Advisor council
4137 *
4138 */
4139 template<class A>
4142
4143 template<class A>
4146 : advisors(nullptr) {}
4147
4148 template<class A>
4149 forceinline bool
4150 Council<A>::empty(void) const {
4151 ActorLink* a = advisors;
4152 while ((a != nullptr) && static_cast<A*>(a)->disposed())
4153 a = a->next();
4154 advisors = a;
4155 return a == nullptr;
4156 }
4157
4158 template<class A>
4159 forceinline void
4161 // Skip all disposed advisors
4162 {
4163 ActorLink* a = c.advisors;
4164 while ((a != nullptr) && static_cast<A*>(a)->disposed())
4165 a = a->next();
4166 c.advisors = a;
4167 }
4168 // Are there any advisors to be cloned?
4169 if (c.advisors != nullptr) {
4170 // The propagator in from-space
4171 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator();
4172 // The propagator in to-space
4173 Propagator* p_t = Propagator::cast(p_f->prev());
4174 // Advisors in from-space
4175 ActorLink** a_f = &c.advisors;
4176 // Advisors in to-space
4177 A* a_t = nullptr;
4178 // Enter advisor link early so failed clone recovery can restore links.
4179 assert(p_f->u.advisors == nullptr);
4180 p_f->u.advisors = c.advisors;
4181 try {
4182 while (*a_f != nullptr) {
4183 if (static_cast<A*>(*a_f)->disposed()) {
4184 *a_f = (*a_f)->next();
4185 } else {
4186 // Run specific copying part
4187 A* a = new (home) A(home,*static_cast<A*>(*a_f));
4188 // Set propagator pointer
4189 a->prev(p_t);
4190 // Set forwarding pointer
4191 (*a_f)->prev(a);
4192 // Link
4193 a->next(a_t);
4194 a_t = a;
4195 advisors = a_t;
4196 a_f = (*a_f)->next_ref();
4197 }
4198 }
4199 } catch (...) {
4200 dispose(home);
4201 advisors = nullptr;
4202 for (ActorLink* a = c.advisors; a != nullptr; a = a->next())
4203 if (!static_cast<A*>(a)->disposed())
4204 a->prev(p_f);
4205 p_f->u.advisors = nullptr;
4206 throw;
4207 }
4208 advisors = a_t;
4209 } else {
4210 advisors = nullptr;
4211 }
4212 }
4213
4214 template<class A>
4215 forceinline void
4217 ActorLink* a = advisors;
4218 while (a != nullptr) {
4219 if (!static_cast<A*>(a)->disposed())
4220 static_cast<A*>(a)->dispose(home,*this);
4221 a = a->next();
4222 }
4223 }
4224
4225
4226
4227 /*
4228 * Advisor iterator
4229 *
4230 */
4231 template<class A>
4234 : a(c.advisors) {
4235 while ((a != nullptr) && static_cast<A*>(a)->disposed())
4236 a = a->next();
4237 }
4238
4239 template<class A>
4240 forceinline bool
4242 return a != nullptr;
4243 }
4244
4245 template<class A>
4246 forceinline void
4248 do {
4249 a = a->next();
4250 } while ((a != nullptr) && static_cast<A*>(a)->disposed());
4251 }
4252
4253 template<class A>
4254 forceinline A&
4256 return *static_cast<A*>(a);
4257 }
4258
4259
4260
4261 /*
4262 * Space
4263 *
4264 */
4265 forceinline void
4266 Space::enqueue(Propagator* p) {
4268 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac];
4269 c->tail(ActorLink::cast(p));
4270 if (c > pc.p.active)
4271 pc.p.active = c;
4272 }
4273
4274 forceinline void
4276 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1;
4277 /*
4278 * Now active points beyond the last queue. This is essential as
4279 * enqueuing a propagator in a failed space keeps the space
4280 * failed.
4281 */
4282 }
4283 forceinline void
4285 s.fail();
4286 }
4287
4288 forceinline bool
4289 Space::failed(void) const {
4290 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1];
4291 }
4292 forceinline bool
4293 Home::failed(void) const {
4294 return s.failed();
4295 }
4296
4297 forceinline bool
4298 Space::stable(void) const {
4299 return ((pc.p.active < &pc.p.queue[0]) ||
4300 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]));
4301 }
4302
4303 forceinline void
4305 if (p & AP_DISPOSE) {
4306 ap_notice_dispose(&a,d);
4307 }
4308 if (p & AP_VIEW_TRACE) {
4309 pc.p.bid_sc |= sc_trace;
4310 }
4311 if (p & AP_TRACE) {
4312 pc.p.bid_sc |= sc_trace;
4313 }
4314 // Currently unused
4315 if (p & AP_WEAKLY) {
4316 // Nothing to do
4317 }
4318 }
4319
4320 forceinline void
4322 // Check whether array has already been discarded as space
4323 // deletion is already in progress
4324 if ((p & AP_DISPOSE) && (d_fst != nullptr))
4325 ap_ignore_dispose(&a,d);
4326 if (p & AP_VIEW_TRACE) {
4327 // Nothing to do
4328 }
4329 if (p & AP_TRACE) {
4330 // Nothing to do
4331 }
4332 // Currently unused
4333 if (p & AP_WEAKLY) {
4334 // Nothing to do
4335 }
4336 }
4337
4338
4339
4340 /*
4341 * Variable implementation
4342 *
4343 */
4344 template<class VIC>
4346 VarImp<VIC>::actor(PropCond pc) {
4347 assert((pc >= 0) && (pc < pc_max+2));
4348 return (pc == 0) ? b.base : b.base+u.idx[pc-1];
4349 }
4350
4351 template<class VIC>
4352 forceinline ActorLink**
4353 VarImp<VIC>::actorNonZero(PropCond pc) {
4354 assert((pc > 0) && (pc < pc_max+2));
4355 return b.base+u.idx[pc-1];
4356 }
4357
4358 template<class VIC>
4359 forceinline unsigned int&
4361 assert((pc > 0) && (pc < pc_max+2));
4362 return u.idx[pc-1];
4363 }
4364
4365 template<class VIC>
4366 forceinline unsigned int
4367 VarImp<VIC>::idx(PropCond pc) const {
4368 assert((pc > 0) && (pc < pc_max+2));
4369 return u.idx[pc-1];
4370 }
4371
4372 template<class VIC>
4375#ifdef GECODE_HAS_CBS
4376 : var_id(++home.var_id_counter)
4377#endif
4378 {
4379#ifndef GECODE_HAS_CBS
4380 (void) home;
4381#endif
4382 b.base = nullptr; entries = 0;
4383 for (PropCond pc=1; pc<pc_max+2; pc++)
4384 idx(pc) = 0;
4385 free_and_bits = 0;
4386 }
4387
4388 template<class VIC>
4391#ifdef GECODE_HAS_CBS
4392 : var_id(0)
4393#endif
4394 {
4395 b.base = nullptr; entries = 0;
4396 for (PropCond pc=1; pc<pc_max+2; pc++)
4397 idx(pc) = 0;
4398 free_and_bits = 0;
4399 }
4400
4401#ifdef GECODE_HAS_CBS
4402 template<class VIC>
4403 forceinline unsigned int
4404 VarImp<VIC>::id(void) const {
4405 return var_id;
4406 }
4407#endif
4408
4409 template<class VIC>
4410 forceinline unsigned int
4412 assert(!copied());
4413 return entries;
4414 }
4415
4416 template<class VIC>
4417 forceinline double
4418 VarImp<VIC>::afc(void) const {
4419 double d = 0.0;
4420 // Count the afc of each propagator
4421 {
4422 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0);
4423 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4424 while (a < e) {
4425 d += Propagator::cast(*a)->afc(); a++;
4426 }
4427 }
4428 // Count the afc of each advisor's propagator
4429 {
4430 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1);
4431 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries;
4432 while (a < e) {
4433 d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a)))
4434 ->propagator().afc();
4435 a++;
4436 }
4437 }
4438 return d;
4439 }
4440
4441 template<class VIC>
4444 return d.me;
4445 }
4446
4447 template<class VIC>
4448 forceinline unsigned int
4449 VarImp<VIC>::bits(void) const {
4450 return free_and_bits;
4451 }
4452
4453 template<class VIC>
4454 forceinline unsigned int&
4456 return free_and_bits;
4457 }
4458
4459#ifdef GECODE_HAS_VAR_DISPOSE
4460 template<class VIC>
4462 VarImp<VIC>::vars_d(Space& home) {
4463 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>());
4464 }
4465
4466 template<class VIC>
4467 forceinline void
4468 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
4469 home.vars_d<VIC>(x);
4470 }
4471#endif
4472
4473 template<class VIC>
4474 forceinline bool
4476 return Support::marked(b.fwd);
4477 }
4478
4479 template<class VIC>
4482 assert(copied());
4483 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd));
4484 }
4485
4486 template<class VIC>
4488 VarImp<VIC>::next(void) const {
4489 assert(copied());
4490 return u.next;
4491 }
4492
4493 template<class VIC>
4496#ifdef GECODE_HAS_CBS
4497 : var_id(x.var_id)
4498#endif
4499 {
4500 VarImpBase** reg;
4501 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
4502 if (x.b.base == nullptr) {
4503 // Variable implementation needs no index structure
4504 reg = &home.pc.c.vars_noidx;
4505 assert(x.degree() == 0);
4506 } else {
4507 reg = &home.pc.c.vars_u[idx_c];
4508 }
4509 // Save subscriptions in copy
4510 b.base = x.b.base;
4511 entries = x.entries;
4512 for (PropCond pc=1; pc<pc_max+2; pc++)
4513 idx(pc) = x.idx(pc);
4514
4515 // Set forwarding pointer
4516 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this));
4517 // Register original
4518 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x;
4519 }
4520
4521 template<class VIC>
4524 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
4525 }
4526
4527 template<class VIC>
4530 return static_cast<ModEventDelta>(me << VIC::med_fst);
4531 }
4532
4533 template<class VIC>
4536 return VIC::me_combine(me1,me2);
4537 }
4538
4539 template<class VIC>
4540 forceinline void
4542 bool force) {
4543 if (VIC::med_update(p.u.med,me) || force)
4544 home.enqueue(&p);
4545 }
4546
4547 template<class VIC>
4548 forceinline void
4550 if (b.base == nullptr)
4551 return;
4552 ActorLink** begin = actor(pc1);
4553 ActorLink** end = actorNonZero(pc2+1);
4554 while (end > begin) {
4555 end--;
4556 schedule(home,*Propagator::cast(*end),me);
4557 }
4558 }
4559
4560 template<class VIC>
4561 forceinline void
4562 VarImp<VIC>::resize(Space& home) {
4563 if (b.base == nullptr) {
4564 assert((free_and_bits >> free_bits) == 0);
4565 // Create fresh dependency array with four entries
4566 free_and_bits += 4 << free_bits;
4567 b.base = home.alloc<ActorLink*>(4);
4568 for (int i=0; i<pc_max+1; i++)
4569 u.idx[i] = 0;
4570 } else {
4571 // Resize dependency array
4572 unsigned int n = degree();
4573 // Find out whether the area is most likely in the special area
4574 // reserved for subscriptions. If yes, just resize mildly otherwise
4575 // more aggressively
4576 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions());
4577 unsigned int m =
4578 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ?
4579 (n+4) : ((n+1)*3>>1);
4580 ActorLink** prop = home.alloc<ActorLink*>(m);
4581 free_and_bits += (m-n) << free_bits;
4582 // Copy entries
4583 Heap::copy<ActorLink*>(prop, b.base, n);
4584 home.free<ActorLink*>(b.base,n);
4585 b.base = prop;
4586 }
4587 }
4588
4589 template<class VIC>
4590 forceinline void
4591 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) {
4592 assert(pc <= pc_max);
4593 // Count one new subscription
4594 home.pc.p.n_sub += 1;
4595 if ((free_and_bits >> free_bits) == 0)
4596 resize(home);
4597 free_and_bits -= 1 << free_bits;
4598
4599 // Enter subscription
4600 b.base[entries] = *actorNonZero(pc_max+1);
4601 entries++;
4602 for (PropCond j = pc_max; j > pc; j--) {
4603 *actorNonZero(j+1) = *actorNonZero(j);
4604 idx(j+1)++;
4605 }
4606 *actorNonZero(pc+1) = *actor(pc);
4607 idx(pc+1)++;
4608 *actor(pc) = ActorLink::cast(p);
4609
4610#ifdef GECODE_AUDIT
4611 ActorLink** f = actor(pc);
4612 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1)))
4613 if (*f == p)
4614 goto found;
4615 else
4616 f++;
4618 found: ;
4619#endif
4620 }
4621
4622 template<class VIC>
4623 forceinline void
4624 VarImp<VIC>::enter(Space& home, ActorLink* a) {
4625 // Note that a might be a marked pointer
4626 // Count one new subscription
4627 home.pc.p.n_sub += 1;
4628 if ((free_and_bits >> free_bits) == 0)
4629 resize(home);
4630 free_and_bits -= 1 << free_bits;
4631
4632 // Enter subscription
4633 b.base[entries++] = *actorNonZero(pc_max+1);
4634 *actorNonZero(pc_max+1) = a;
4635 }
4636
4637 template<class VIC>
4638 forceinline void
4640 bool assigned, ModEvent me, bool schedule) {
4641 if (assigned) {
4642 // Do not subscribe, just schedule the propagator
4643 if (schedule)
4645 } else {
4646 enter(home,&p,pc);
4647 // Schedule propagator
4648 if (schedule && (pc != PC_GEN_ASSIGNED))
4649 VarImp<VIC>::schedule(home,p,me);
4650 }
4651 }
4652
4653 template<class VIC>
4654 forceinline void
4655 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) {
4656 if (!assigned) {
4657 ActorLink* ma = static_cast<ActorLink*>
4658 (Support::ptrjoin(Advisor::link(a),fail ? 1 : 0));
4659 enter(home,ma);
4660 }
4661 }
4662
4663 template<class VIC>
4664 forceinline void
4666 bool assigned, ModEvent me) {
4667 if (assigned)
4669 else if (pc != PC_GEN_ASSIGNED)
4670 VarImp<VIC>::schedule(home,p,me);
4671 }
4672
4673 template<class VIC>
4674 void
4675 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) {
4676 assert(pc <= pc_max);
4677 ActorLink* a = ActorLink::cast(p);
4678 // Find actor in dependency array
4679 ActorLink** f = actor(pc);
4680#ifdef GECODE_AUDIT
4681 while (f < actorNonZero(pc+1))
4682 if (*f == a)
4683 goto found;
4684 else
4685 f++;
4687 found: ;
4688#else
4689 while (*f != a) f++;
4690#endif
4691 // Remove actor
4692 *f = *(actorNonZero(pc+1)-1);
4693 for (PropCond j = pc+1; j< pc_max+1; j++) {
4694 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
4695 idx(j)--;
4696 }
4697 *(actorNonZero(pc_max+1)-1) = b.base[entries-1];
4698 idx(pc_max+1)--;
4699 entries--;
4700 free_and_bits += 1 << free_bits;
4701 home.pc.p.n_sub -= 1;
4702 }
4703
4704 template<class VIC>
4705 forceinline void
4707 if ((b.base != nullptr) && !home.is_partial_clone())
4708 remove(home,&p,pc);
4709 }
4710
4711 template<class VIC>
4712 void
4713 VarImp<VIC>::remove(Space& home, ActorLink* a) {
4714 // Note that a might be a marked pointer
4715 // Find actor in dependency array
4716 ActorLink** f = actorNonZero(pc_max+1);
4717#ifdef GECODE_AUDIT
4718 while (f < b.base+entries)
4719 if (*f == a)
4720 goto found;
4721 else
4722 f++;
4724 found: ;
4725#else
4726 while (*f != a) f++;
4727#endif
4728 // Remove actor
4729 *f = b.base[--entries];
4730 free_and_bits += 1 << free_bits;
4731 home.pc.p.n_sub -= 1;
4732 }
4733
4734 template<class VIC>
4735 forceinline void
4737 if ((b.base != nullptr) && !home.is_partial_clone()) {
4738 ActorLink* ma = static_cast<ActorLink*>
4739 (Support::ptrjoin(Advisor::link(a),fail ? 1 : 0));
4740 remove(home,ma);
4741 }
4742 }
4743
4744 template<class VIC>
4745 forceinline void
4747 unsigned int n_sub = degree();
4748 home.pc.p.n_sub -= n_sub;
4749 unsigned int n = (free_and_bits >> free_bits) + n_sub;
4750 home.free<ActorLink*>(b.base,n);
4751 // Must be nullptr such that cloning works
4752 b.base = nullptr;
4753 // Must be 0 such that degree works
4754 entries = 0;
4755 // Must be nullptr such that afc works
4756 for (PropCond pc=1; pc<pc_max+2; pc++)
4757 idx(pc) = 0;
4758 free_and_bits &= (1 << free_bits) - 1;
4759 }
4760
4761 template<class VIC>
4762 forceinline bool
4764 /*
4765 * An advisor that is executed might remove itself due to subsumption.
4766 * As entries are removed from front to back, the advisors must
4767 * be iterated in forward direction.
4768 */
4769 ActorLink** la = actorNonZero(pc_max+1);
4770 ActorLink** le = b.base+entries;
4771 if (la == le)
4772 return true;
4773 d.me = me;
4774 // An advisor that is run, might be removed during execution.
4775 // As removal is done from the back the advisors have to be executed
4776 // in inverse order.
4777 do {
4778 Advisor* a = Advisor::cast
4779 (static_cast<ActorLink*>(Support::funmark(*la)));
4780 assert(!a->disposed());
4781 Propagator& p = a->propagator();
4782 switch (p.advise(home,*a,d)) {
4783 case ES_FIX:
4784 break;
4785 case ES_FAILED:
4786 return false;
4787 case ES_NOFIX:
4788 schedule(home,p,me);
4789 break;
4790 case ES_NOFIX_FORCE:
4791 schedule(home,p,me,true);
4792 break;
4793 case ES_SUBSUMED_:
4794 default:
4796 }
4797 } while (++la < le);
4798 return true;
4799 }
4800
4801 template<class VIC>
4802 void
4803 VarImp<VIC>::_fail(Space& home) {
4804 /*
4805 * An advisor that is executed might remove itself due to subsumption.
4806 * As entries are removed from front to back, the advisors must
4807 * be iterated in forward direction.
4808 */
4809 ActorLink** la = actorNonZero(pc_max+1);
4810 ActorLink** le = b.base+entries;
4811 if (la == le)
4812 return;
4813 // An advisor that is run, might be removed during execution.
4814 // As removal is done from the back the advisors have to be executed
4815 // in inverse order.
4816 do {
4817 if (Support::marked(*la)) {
4818 Advisor* a = Advisor::cast(static_cast<ActorLink*>
4819 (Support::unmark(*la)));
4820 assert(!a->disposed());
4821 Propagator& p = a->propagator();
4822 p.advise(home,*a);
4823 }
4824 } while (++la < le);
4825 }
4826
4827 template<class VIC>
4828 ModEvent
4830 _fail(home);
4831 return ME_GEN_FAILED;
4832 }
4833
4834 // Clang incorrectly reports an error on the access to u.idx[1] for BoolVarImp,
4835 // even though the access is guarded by pc_max > 0 which implies that the size is sufficient.
4836#pragma clang diagnostic push
4837#pragma clang diagnostic ignored "-Warray-bounds"
4838
4839 template<class VIC>
4840 forceinline void
4841 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) {
4842 // this refers to the variable to be updated (clone)
4843 // x refers to the original
4844 // Recover from copy
4845 x->b.base = b.base;
4846 x->u.idx[0] = u.idx[0];
4847 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4848 x->u.idx[1] = u.idx[1];
4849
4850 unsigned int np =
4851 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0));
4852 unsigned int na =
4853 static_cast<unsigned int >(x->b.base + x->entries -
4854 x->actorNonZero(pc_max+1));
4855 unsigned int n = na + np;
4856 assert(n == x->degree());
4857
4858 ActorLink** f = x->b.base;
4859 ActorLink** t = sub;
4860
4861 sub += n;
4862 b.base = t;
4863 // Process propagator subscriptions
4864 while (np >= 4) {
4865 ActorLink* p3 = f[3]->prev();
4866 ActorLink* p0 = f[0]->prev();
4867 ActorLink* p1 = f[1]->prev();
4868 ActorLink* p2 = f[2]->prev();
4869 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3;
4870 np -= 4; t += 4; f += 4;
4871 }
4872 if (np >= 2) {
4873 ActorLink* p0 = f[0]->prev();
4874 ActorLink* p1 = f[1]->prev();
4875 t[0] = p0; t[1] = p1;
4876 np -= 2; t += 2; f += 2;
4877 }
4878 if (np > 0) {
4879 ActorLink* p0 = f[0]->prev();
4880 t[0] = p0;
4881 t += 1; f += 1;
4882 }
4883 // Process advisor subscriptions
4884 while (na >= 4) {
4885 ptrdiff_t m0, m1, m2, m3;
4886 ActorLink* p3 =
4887 static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev();
4888 ActorLink* p0 =
4889 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4890 ActorLink* p1 =
4891 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4892 ActorLink* p2 =
4893 static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev();
4894 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4895 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4896 t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2));
4897 t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3));
4898 na -= 4; t += 4; f += 4;
4899 }
4900 if (na >= 2) {
4901 ptrdiff_t m0, m1;
4902 ActorLink* p0 =
4903 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4904 ActorLink* p1 =
4905 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev();
4906 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4907 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1));
4908 na -= 2; t += 2; f += 2;
4909 }
4910 if (na > 0) {
4911 ptrdiff_t m0;
4912 ActorLink* p0 =
4913 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev();
4914 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0));
4915 }
4916 }
4917#pragma clang diagnostic pop
4918
4919 template<class VIC>
4920 forceinline void
4921 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
4922 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4923 while (x != nullptr) {
4924 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n;
4925 }
4926 }
4927
4928 template<class VIC>
4929 forceinline void
4930 VarImp<VIC>::recover(Space& home, ActorLink**&) {
4931 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]);
4932 while (x != nullptr) {
4933 if (x->copied()) {
4934 VarImp<VIC>* n = x->next();
4935 VarImp<VIC>* copy = x->forward();
4936 x->b.base = copy->b.base;
4937 x->u.idx[0] = copy->u.idx[0];
4938 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int))
4939 x->u.idx[1] = copy->u.idx[1];
4940 x = n;
4941 } else {
4942 break;
4943 }
4944 }
4945 }
4946
4947
4948
4949 /*
4950 * Variable disposer
4951 *
4952 */
4953 template<class VarImp>
4955#ifdef GECODE_HAS_VAR_DISPOSE
4956 Space::vd[VarImp::idx_d] = this;
4957#endif
4958 }
4959
4960 template<class VarImp>
4961 void
4963 VarImp* x = static_cast<VarImp*>(_x);
4964 do {
4965 x->dispose(home); x = static_cast<VarImp*>(x->next_d());
4966 } while (x != nullptr);
4967 }
4968
4969 /*
4970 * Statistics
4971 */
4972
4973 forceinline void
4975 propagate = 0;
4976 }
4983 propagate += s.propagate;
4984 return *this;
4985 }
4988 StatusStatistics t(s);
4989 return t += *this;
4990 }
4991
4992 forceinline void
4994
5002 return s;
5003 }
5006 return *this;
5007 }
5008
5009 forceinline void
5011
5019 return s;
5020 }
5023 return *this;
5024 }
5025
5026 /*
5027 * Cost computation
5028 *
5029 */
5030
5032 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {}
5033
5034 forceinline PropCost
5035 PropCost::cost(PropCost::Mod m,
5037 unsigned int n) {
5038 if (n < 2)
5039 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
5040 else if (n == 2)
5041 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
5042 else if (n == 3)
5043 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
5044 else
5045 return (m == LO) ? lo : hi;
5046 }
5047
5050 return AC_RECORD;
5051 }
5053 PropCost::crazy(PropCost::Mod m, unsigned int n) {
5054 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n);
5055 }
5058 assert(n >= 0);
5059 return crazy(m,static_cast<unsigned int>(n));
5060 }
5062 PropCost::cubic(PropCost::Mod m, unsigned int n) {
5063 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n);
5064 }
5067 assert(n >= 0);
5068 return cubic(m,static_cast<unsigned int>(n));
5069 }
5072 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n);
5073 }
5076 assert(n >= 0);
5077 return quadratic(m,static_cast<unsigned int>(n));
5078 }
5080 PropCost::linear(PropCost::Mod m, unsigned int n) {
5081 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n);
5082 }
5085 assert(n >= 0);
5086 return linear(m,static_cast<unsigned int>(n));
5087 }
5090 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI;
5091 }
5094 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI;
5095 }
5098 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI;
5099 }
5100
5101 /*
5102 * Iterators for propagators and branchers of a space
5103 *
5104 */
5107 : home(home0), q(home.pc.p.active) {
5108 while (q >= &home.pc.p.queue[0]) {
5109 if (q->next() != q) {
5110 c = q->next(); e = q; q--;
5111 return;
5112 }
5113 q--;
5114 }
5115 q = nullptr;
5116 if (!home.pl.empty()) {
5117 c = home.pl.next();
5118 e = &home.pl;
5119 } else {
5120 c = e = nullptr;
5121 }
5122 }
5123 forceinline bool
5125 return c != nullptr;
5126 }
5127 forceinline void
5129 c = c->next();
5130 if (c == e) {
5131 if (q == nullptr) {
5132 c = nullptr;
5133 } else {
5134 while (q >= &home.pc.p.queue[0]) {
5135 if (q->next() != q) {
5136 c = q->next(); e = q; q--;
5137 return;
5138 }
5139 q--;
5140 }
5141 q = nullptr;
5142 if (!home.pl.empty()) {
5143 c = home.pl.next();
5144 e = &home.pl;
5145 } else {
5146 c = nullptr;
5147 }
5148 }
5149 }
5150 }
5153 return *Propagator::cast(c);
5154 }
5155
5156
5159 : home(home0), q(home.pc.p.active) {
5160 while (q >= &home.pc.p.queue[0]) {
5161 if (q->next() != q) {
5162 c = q->next(); e = q; q--;
5163 return;
5164 }
5165 q--;
5166 }
5167 q = c = e = nullptr;
5168 }
5169 forceinline bool
5171 return c != nullptr;
5172 }
5173 forceinline void
5175 c = c->next();
5176 if (c == e) {
5177 if (q == nullptr) {
5178 c = nullptr;
5179 } else {
5180 while (q >= &home.pc.p.queue[0]) {
5181 if (q->next() != q) {
5182 c = q->next(); e = q; q--;
5183 return;
5184 }
5185 q--;
5186 }
5187 q = c = e = nullptr;
5188 }
5189 }
5190 }
5193 return *Propagator::cast(c);
5194 }
5195
5196
5199 c = home.pl.next();
5200 e = &home.pl;
5201 }
5202 forceinline bool
5204 return c != e;
5205 }
5206 forceinline void
5208 c = c->next();
5209 }
5212 return *Propagator::cast(c);
5213 }
5214
5215
5218 : c(home.bl.next()), e(&home.bl) {}
5219 forceinline bool
5221 return c != e;
5222 }
5223 forceinline void
5225 c = c->next();
5226 }
5229 return *Brancher::cast(c);
5230 }
5231
5232
5233 /*
5234 * Groups of actors
5235 */
5237 Group::Group(unsigned int gid0) : gid(gid0) {}
5238
5239 forceinline bool
5240 Group::in(Group actor) const {
5241 return (gid == GROUPID_ALL) || (gid == actor.gid);
5242 }
5243
5244 forceinline bool
5245 Group::in(void) const {
5246 return (gid != GROUPID_ALL) && (gid != GROUPID_DEF);
5247 }
5248
5250 Group::Group(const Group& g) : gid(g.gid) {}
5251
5254 gid=g.gid; return *this;
5255 }
5256
5257 forceinline unsigned int
5258 Group::id(void) const {
5259 return gid;
5260 }
5261
5262
5265
5269
5273
5276 return static_cast<PropagatorGroup&>(Group::operator =(g));
5277 }
5278
5281 return Home(home,nullptr,*this,BrancherGroup::def);
5282 }
5283
5284 forceinline bool
5286 return id() == g.id();
5287 }
5288 forceinline bool
5290 return id() != g.id();
5291 }
5292
5295 if (id() != GROUPID_ALL)
5296 p.group(*this);
5297 return *this;
5298 }
5299
5300
5303
5306 : Group(gid) {}
5307
5311
5314 return static_cast<BrancherGroup&>(Group::operator =(g));
5315 }
5316
5319 return Home(home,nullptr,PropagatorGroup::def,*this);
5320 }
5321
5322 forceinline bool
5324 return id() == g.id();
5325 }
5326 forceinline bool
5328 return id() != g.id();
5329 }
5330
5333 if (id() != GROUPID_ALL)
5334 p.group(*this);
5335 return *this;
5336 }
5337
5338
5339 /*
5340 * Iterators for propagators and branchers in a group
5341 *
5342 */
5345 : ps(const_cast<Space&>(home)), g(g0) {
5346 while (ps() && !g.in(ps.propagator().group()))
5347 ++ps;
5348 }
5349 forceinline bool
5351 return ps();
5352 }
5353 forceinline void
5355 do
5356 ++ps;
5357 while (ps() && !g.in(ps.propagator().group()));
5358 }
5359 forceinline const Propagator&
5361 return ps.propagator();
5362 }
5363
5366 : bs(const_cast<Space&>(home)), g(g0) {
5367 while (bs() && !g.in(bs.brancher().group()))
5368 ++bs;
5369 }
5370 forceinline bool
5372 return bs();
5373 }
5374 forceinline void
5376 do
5377 ++bs;
5378 while (bs() && !g.in(bs.brancher().group()));
5379 }
5380 forceinline const Brancher&
5382 return bs.brancher();
5383 }
5384
5385
5386 /*
5387 * Space construction support
5388 *
5389 */
5390 template<class T>
5391 forceinline T&
5393 return alloc<T>(1);
5394 }
5395 template<class T, typename A1>
5396 forceinline T&
5397 Space::construct(A1 const& a1) {
5398 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5399 new (&t) T(a1);
5400 return t;
5401 }
5402 template<class T, typename A1, typename A2>
5403 forceinline T&
5404 Space::construct(A1 const& a1, A2 const& a2) {
5405 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5406 new (&t) T(a1,a2);
5407 return t;
5408 }
5409 template<class T, typename A1, typename A2, typename A3>
5410 forceinline T&
5411 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) {
5412 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5413 new (&t) T(a1,a2,a3);
5414 return t;
5415 }
5416 template<class T, typename A1, typename A2, typename A3, typename A4>
5417 forceinline T&
5418 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) {
5419 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5420 new (&t) T(a1,a2,a3,a4);
5421 return t;
5422 }
5423 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5>
5424 forceinline T&
5425 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) {
5426 T& t = *static_cast<T*>(ralloc(sizeof(T)));
5427 new (&t) T(a1,a2,a3,a4,a5);
5428 return t;
5429 }
5430
5431}
5432
5433// STATISTICS: kernel-core
Class for AFC (accumulated failure count) management.
Definition afc.hpp:40
Base-class for both propagators and branchers.
Definition core.hpp:635
friend class Space
Definition core.hpp:637
friend class LocalObject
Definition core.hpp:641
friend class ActorLink
Definition core.hpp:636
friend class VarImp
Definition core.hpp:642
friend class Advisor
Definition core.hpp:639
friend class Propagator
Definition core.hpp:638
friend class Brancher
Definition core.hpp:640
virtual Actor * copy(Space &home)=0
Create copy.
friend class Council
Definition core.hpp:643
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Base-class for advisors.
Definition core.hpp:1308
friend class SubscribedPropagators
Definition core.hpp:1312
Propagator & propagator(void) const
Return the advisor's propagator.
Definition core.hpp:4091
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:4060
friend class VarImp
Definition core.hpp:1309
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:4098
friend class Advisors
Definition core.hpp:1311
friend class Council
Definition core.hpp:1310
const ViewTraceInfo & operator()(const Space &home) const
Provide access to view trace information.
Definition core.hpp:4108
Class to iterate over advisors of a council.
Definition core.hpp:1282
Advisors(const Council< A > &c)
Initialize.
Definition core.hpp:4233
bool operator()(void) const
Test whether there advisors left.
Definition core.hpp:4241
void operator++(void)
Move iterator to next advisor.
Definition core.hpp:4247
A & advisor(void) const
Return advisor.
Definition core.hpp:4255
static const int idx_c
Index for cloning.
Definition var-type.hpp:467
static ModEventDelta med_combine(ModEventDelta med1, ModEventDelta med2)
Combine modification event delta med1 with med2.
Definition var-type.hpp:897
Archive representation
Definition archive.hpp:42
Group of branchers.
Definition core.hpp:806
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition core.cpp:1100
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition core.hpp:857
static BrancherGroup all
Group of all branchers.
Definition core.hpp:854
BrancherGroup & operator=(const BrancherGroup &g)
Assignment operator.
Definition core.hpp:5313
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition core.cpp:1077
BrancherGroup(unsigned int gid)
Initialize with group id gid.
Definition core.hpp:5305
friend class Brancher
Definition core.hpp:807
Home operator()(Space &home)
To augment a space argument.
Definition core.hpp:5318
bool operator!=(BrancherGroup g) const
Test whether this group is different from group g.
Definition core.hpp:5327
void kill(Space &home)
Kill all branchers in a group.
Definition core.cpp:1111
bool operator==(BrancherGroup g) const
Test whether this group is equal to group g.
Definition core.hpp:5323
BrancherGroup(void)
Constructor.
Definition core.hpp:5302
Base-class for branchers.
Definition core.hpp:1460
virtual const Choice * choice(Space &home)=0
Return choice.
friend class Space
Definition core.hpp:1462
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int a)=0
Commit for choice c and alternative a.
friend class ActorLink
Definition core.hpp:1461
unsigned int id(void) const
Return brancher id.
Definition core.hpp:3846
virtual const Choice * choice(const Space &home, Archive &e)=0
Return choice from e.
BrancherGroup group(void) const
Return group brancher belongs to.
Definition core.hpp:3851
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
virtual NGL * ngl(Space &home, const Choice &c, unsigned int a) const
Create no-good literal for choice c and alternative a.
Definition core.cpp:98
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3822
friend class Choice
Definition core.hpp:1463
void operator++(void)
Move iterator to next brancher.
Definition core.hpp:5375
const Brancher & brancher(void) const
Return propagator.
Definition core.hpp:5381
bool operator()(void) const
Test whether there are branchers left.
Definition core.hpp:5371
Branchers(const Space &home, BrancherGroup g)
Initialize.
Definition core.hpp:5365
Choice for performing commit
Definition core.hpp:1430
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition core.hpp:3995
friend class Space
Definition core.hpp:1431
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:958
virtual ~Choice(void)
Destructor.
Definition core.hpp:4009
unsigned int alternatives(void) const
Return number of alternatives.
Definition core.hpp:3999
Statistics for execution of clone
Definition core.hpp:1754
CloneStatistics operator+(const CloneStatistics &s)
Return sum with s.
Definition core.hpp:5000
void reset(void)
Reset information.
Definition core.hpp:4993
CloneStatistics & operator+=(const CloneStatistics &s)
Increment by statistics s.
Definition core.hpp:5005
CloneStatistics(void)
Initialize.
Definition core.hpp:4996
Statistics for execution of commit
Definition core.hpp:1770
CommitStatistics & operator+=(const CommitStatistics &s)
Increment by statistics s.
Definition core.hpp:5022
void reset(void)
Reset information.
Definition core.hpp:5010
CommitStatistics operator+(const CommitStatistics &s)
Return sum with s.
Definition core.hpp:5017
CommitStatistics(void)
Initialize.
Definition core.hpp:5013
Commit trace information.
Definition core.hpp:1014
BrancherGroup group(void) const
Return brancher group.
Definition core.hpp:3594
friend class Space
Definition core.hpp:1015
unsigned int alternative(void) const
Return alternative.
Definition core.hpp:3606
const Brancher & b
Brancher.
Definition core.hpp:1018
CommitTraceInfo(const Brancher &b, const Choice &c, unsigned int a)
Initialize.
Definition core.hpp:3586
unsigned int id(void) const
Return brancher identifier.
Definition core.hpp:3590
unsigned int a
Alternative.
Definition core.hpp:1022
const Choice & c
Choice.
Definition core.hpp:1020
const Choice & choice(void) const
Return choice.
Definition core.hpp:3602
const Brancher & brancher(void) const
Return brancher.
Definition core.hpp:3598
Council of advisors
Definition core.hpp:1257
bool empty(void) const
Test whether council has advisor left.
Definition core.hpp:4150
void update(Space &home, Council< A > &c)
Update during cloning (copies all advisors).
Definition core.hpp:4160
void dispose(Space &home)
Dispose council.
Definition core.hpp:4216
friend class Advisor
Definition core.hpp:1258
Council(void)
Default constructor.
Definition core.hpp:4141
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
friend class VarImp
Definition core.hpp:210
Base-class for freelist-managed objects.
Definition manager.hpp:100
Group baseclass for controlling actors.
Definition core.hpp:680
static Group all
Group of all actors.
Definition core.hpp:724
static Group def
Group of actors not in any user-defined group.
Definition core.hpp:727
static const unsigned int GROUPID_ALL
Fake id for group of all actors.
Definition core.hpp:690
Group(void)
Constructor.
Definition core.cpp:988
bool in(void) const
Check whether this is a real group (and not just default).
Definition core.hpp:5245
friend class CommitTraceInfo
Definition core.hpp:686
static Support::Mutex m
Mutex for protection.
Definition core.hpp:702
friend class PostTraceInfo
Definition core.hpp:687
static const unsigned int GROUPID_MAX
The maximal group number.
Definition core.hpp:694
Group & operator=(const Group &g)
Assignment operator.
Definition core.hpp:5253
unsigned int id(void) const
Return a unique id for the group.
Definition core.hpp:5258
static const unsigned int GROUPID_DEF
Pre-defined default group id.
Definition core.hpp:692
unsigned int gid
The group id.
Definition core.hpp:696
friend class Propagator
Definition core.hpp:682
friend class Brancher
Definition core.hpp:683
static unsigned int next
Next group id.
Definition core.hpp:699
friend class PropagateTraceInfo
Definition core.hpp:685
Group(unsigned int gid0)
Construct with predefined group id gid0.
Definition core.hpp:5237
friend class Home
Definition core.hpp:681
friend class ViewTraceInfo
Definition core.hpp:684
Base class for heap allocated objects.
Definition heap.hpp:344
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:593
Home class for posting propagators
Definition core.hpp:863
PropagatorGroup pg
A propagator group.
Definition core.hpp:871
BrancherGroup branchergroup(void) const
Return brancher group.
Definition core.hpp:3488
Home(Space &s, Propagator *p=nullptr, PropagatorGroup pg=PropagatorGroup::def, BrancherGroup bg=BrancherGroup::def)
Initialize the home with space s and propagator p and group g.
Definition core.hpp:3440
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
Propagator * p
A propagator (possibly) that is currently being rewritten.
Definition core.hpp:869
Space & s
The space where the propagator is to be posted.
Definition core.hpp:867
void fail(void)
Mark space as failed.
Definition core.hpp:4284
BrancherGroup bg
A brancher group.
Definition core.hpp:873
Propagator * propagator(void) const
Return propagator (or nullptr) for currently rewritten propagator.
Definition core.hpp:3480
PropagatorGroup propagatorgroup(void) const
Return propagator group.
Definition core.hpp:3484
friend class PostInfo
Definition core.hpp:864
Home operator()(Propagator &p)
Return a home extended by propagator to be rewritten.
Definition core.hpp:3456
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4293
Home & operator=(const Home &h)
Assignment operator.
Definition core.hpp:3447
Class for storing propagator information.
Definition gpi.hpp:42
unsigned int gid
Group identifier.
Definition gpi.hpp:47
Manage memory for space.
Definition manager.hpp:122
void * subscriptions(void) const
Get the memory area for subscriptions.
Definition manager.hpp:299
Class to store data shared among several spaces.
Handles for local (space-shared) objects.
Definition core.hpp:1576
LocalHandle(void)
Create local handle pointing to nullptr object.
Definition core.hpp:3968
~LocalHandle(void)
Destructor.
Definition core.hpp:3979
void update(Space &home, LocalHandle &lh)
Updating during cloning.
Definition core.hpp:3985
LocalHandle & operator=(const LocalHandle &lh)
Assignment operator.
Definition core.hpp:3974
LocalObject * object(void) const
Access to the local object.
Definition core.hpp:3981
Local (space-shared) object.
Definition core.hpp:1551
static LocalObject * cast(ActorLink *al)
Static cast for a non-null pointer (to give a hint to optimizer).
Definition core.hpp:3934
friend class Space
Definition core.hpp:1553
LocalObject * fwd(Space &home)
Return forwarding pointer.
Definition core.hpp:3961
friend class ActorLink
Definition core.hpp:1552
LocalObject(Home home)
Constructor for creation.
Definition core.hpp:3950
friend class LocalHandle
Definition core.hpp:1554
Information passed by meta search engines.
Definition core.hpp:1635
MetaInfo(unsigned long int r, RestartReason rr, unsigned long long int s, unsigned long long int f, const Space *l, NoGoods &ng)
Constructor for restart-based engine.
Definition core.hpp:3219
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition core.hpp:3260
const unsigned long long int f
Number of failures since last restart.
Definition core.hpp:1669
Type
Which type of information is provided.
Definition core.hpp:1638
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1642
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1640
unsigned long long int fail(void) const
Return number of failures since last restart.
Definition core.hpp:3250
const RestartReason rr
Reason for restarting.
Definition core.hpp:1665
const Type t
Type of information.
Definition core.hpp:1659
unsigned int asset(void) const
Return number of asset in portfolio.
Definition core.hpp:3265
const Space * l
Last solution found.
Definition core.hpp:1671
unsigned long long int solution(void) const
Return number of solutions since last restart.
Definition core.hpp:3245
unsigned long int restart(void) const
Return number of restarts.
Definition core.hpp:3236
const Space * last(void) const
Return last solution found (possibly nullptr).
Definition core.hpp:3255
const unsigned long int r
Number of restarts.
Definition core.hpp:1663
RestartReason reason(void) const
Return reason for restarting.
Definition core.hpp:3241
const unsigned long long int s
Number of solutions since last restart.
Definition core.hpp:1667
const unsigned int a
Number of asset in portfolio.
Definition core.hpp:1678
RestartReason
Reason for restarting.
Definition core.hpp:1645
@ RR_NO
No reason - used for PORTFOLIO.
Definition core.hpp:1647
@ RR_INIT
Restarting after initialisation.
Definition core.hpp:1649
@ RR_SOL
Restarting after a solution is found.
Definition core.hpp:1651
@ RR_CMPL
Restarting after exhausting search space.
Definition core.hpp:1653
@ RR_LIM
Restarting after reaching restart limit.
Definition core.hpp:1655
const NoGoods & ng
No-goods from restart.
Definition core.hpp:1673
Type type(void) const
Return type of information.
Definition core.hpp:3232
No-good literal recorded during search.
Definition core.hpp:1358
bool leaf(void) const
Test whether literal is a leaf.
Definition core.hpp:4018
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
virtual void cancel(Space &home, Propagator &p)=0
Cancel propagator p from all views of the no-good literal.
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
virtual NGL::Status status(const Space &home) const =0
Test the status of the no-good literal.
NGL(void)
Constructor for creation.
Definition core.hpp:4041
virtual NGL * copy(Space &home)=0
Create copy.
Status
The status of a no-good literal.
Definition core.hpp:1364
@ SUBSUMED
The literal is subsumed.
Definition core.hpp:1366
@ FAILED
The literal is failed.
Definition core.hpp:1365
@ NONE
The literal is neither failed nor subsumed.
Definition core.hpp:1367
virtual void reschedule(Space &home, Propagator &p)=0
Schedule propagator p for all views of the no-good literal.
NGL * next(void) const
Return pointer to next literal.
Definition core.hpp:4022
virtual size_t dispose(Space &home)
Dispose.
Definition core.hpp:4050
NGL * add(NGL *n, bool l)
Add node n and mark it as leaf l and return n.
Definition core.hpp:4034
virtual bool notice(void) const
Whether dispose must always be called (returns false).
Definition core.cpp:963
No-goods recorded from restarts.
Definition core.hpp:1606
virtual void post(Space &home) const
Post no-goods.
Definition core.cpp:88
static NoGoods eng
Empty no-goods.
Definition core.hpp:1628
virtual ~NoGoods(void)
Destructor.
Definition core.hpp:3212
NoGoods(void)
Initialize.
Definition core.hpp:3193
std::atomic< unsigned long int > n
Number of no-goods.
Definition core.hpp:1609
unsigned long int ng(void) const
Return number of no-goods posted.
Definition core.hpp:3204
NoGoods & operator=(const NoGoods &ng)
Assignment operator.
Definition core.hpp:3199
Configuration class for variable implementations without index structure.
Definition core.hpp:103
static bool med_update(ModEventDelta &med, ModEvent me)
Update modification even delta med by me, return true on change.
Definition core.hpp:130
static const int free_bits
Freely available bits.
Definition core.hpp:112
static const int idx_c
Index for update.
Definition core.hpp:106
static const int med_fst
Start of bits for modification event delta.
Definition core.hpp:114
static const int med_lst
End of bits for modification event delta.
Definition core.hpp:116
static const PropCond pc_max
Maximal propagation condition.
Definition core.hpp:110
static const int idx_d
Index for disposal.
Definition core.hpp:108
static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modification events me1 and me2.
Definition core.hpp:126
static const int med_mask
Bitmask for modification event delta.
Definition core.hpp:118
Class to set group information when a post function is executed.
Definition core.hpp:957
Space & h
The home space.
Definition core.hpp:961
friend class Space
Definition core.hpp:958
PostInfo(Home home)
Set information.
Definition core.hpp:3538
bool nested
Whether it is used nested.
Definition core.hpp:967
unsigned int pid
Next free propagator id.
Definition core.hpp:965
PropagatorGroup pg
The propagator group.
Definition core.hpp:963
~PostInfo(void)
Reset information.
Definition core.hpp:3546
Post trace information.
Definition core.hpp:1041
unsigned int propagators(void) const
Return number of posted propagators.
Definition core.hpp:3627
friend class Space
Definition core.hpp:1042
PropagatorGroup group(void) const
Return propagator group.
Definition core.hpp:3619
PropagatorGroup g
Propagator group.
Definition core.hpp:1053
Status
Post status.
Definition core.hpp:1046
@ SUBSUMED
Propagator not posted as already subsumed.
Definition core.hpp:1049
@ FAILED
Posting failed.
Definition core.hpp:1048
@ POSTED
Propagator was posted.
Definition core.hpp:1047
Status status(void) const
Return post status.
Definition core.hpp:3623
friend class PostInfo
Definition core.hpp:1043
PostTraceInfo(PropagatorGroup g, Status s, unsigned int n)
Initialize.
Definition core.hpp:3616
Status s
Status.
Definition core.hpp:1055
unsigned int n
Number of posted propagators.
Definition core.hpp:1057
Propagation cost.
Definition core.hpp:493
ActualCost ac
Actual cost.
Definition core.hpp:516
friend class Space
Definition core.hpp:494
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:5097
static PropCost ternary(PropCost::Mod m)
Three variables for modifier pcm.
Definition core.hpp:5089
static PropCost record(void)
For recording information (no propagation allowed).
Definition core.hpp:5049
static PropCost crazy(PropCost::Mod m, unsigned int n)
Exponential complexity for modifier m and size measure n.
Definition core.hpp:5053
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:5071
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition core.hpp:5062
static PropCost binary(PropCost::Mod m)
Two variables for modifier pcm.
Definition core.hpp:5093
Mod
Propagation cost modifier.
Definition core.hpp:519
@ HI
Expensive.
Definition core.hpp:521
ActualCost
The actual cost values that are used.
Definition core.hpp:497
@ AC_TERNARY_LO
Three variables, cheap.
Definition core.hpp:509
@ AC_TERNARY_HI
Three variables, expensive.
Definition core.hpp:507
@ AC_BINARY_LO
Two variables, cheap.
Definition core.hpp:510
@ AC_CUBIC_LO
Cubic complexity, cheap.
Definition core.hpp:501
@ AC_UNARY_HI
Only single variable, expensive.
Definition core.hpp:512
@ AC_RECORD
Reserved for recording information.
Definition core.hpp:498
@ AC_BINARY_HI
Two variables, expensive.
Definition core.hpp:508
@ AC_LINEAR_HI
Linear complexity, expensive.
Definition core.hpp:505
@ AC_CUBIC_HI
Cubic complexity, expensive.
Definition core.hpp:502
@ AC_MAX
Maximal cost value.
Definition core.hpp:513
@ AC_CRAZY_LO
Exponential complexity, cheap.
Definition core.hpp:499
@ AC_LINEAR_LO
Linear complexity, cheap.
Definition core.hpp:506
@ AC_UNARY_LO
Only single variable, cheap.
Definition core.hpp:511
@ AC_QUADRATIC_LO
Quadratic complexity, cheap.
Definition core.hpp:503
@ AC_CRAZY_HI
Exponential complexity, expensive.
Definition core.hpp:500
@ AC_QUADRATIC_HI
Quadratic complexity, expensive.
Definition core.hpp:504
Propagate trace information.
Definition core.hpp:978
unsigned int i
Propagator id.
Definition core.hpp:990
Status
Propagator status.
Definition core.hpp:982
@ SUBSUMED
Propagator is subsumed.
Definition core.hpp:986
@ FIX
Propagator computed fixpoint.
Definition core.hpp:983
@ NOFIX
Propagator did not compute fixpoint.
Definition core.hpp:984
@ FAILED
Propagator failed.
Definition core.hpp:985
PropagateTraceInfo(unsigned int i, PropagatorGroup g, const Propagator *p, Status s)
Initialize.
Definition core.hpp:3560
const Propagator * propagator(void) const
Return pointer to non-subsumed propagator.
Definition core.hpp:3572
unsigned int id(void) const
Return propagator identifier.
Definition core.hpp:3564
Status status(void) const
Return propagator status.
Definition core.hpp:3576
const Propagator * p
Propagator.
Definition core.hpp:994
PropagatorGroup g
Propagator group.
Definition core.hpp:992
PropagatorGroup group(void) const
Return propagator group.
Definition core.hpp:3568
Group of propagators.
Definition core.hpp:734
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition core.cpp:1022
bool operator==(PropagatorGroup g) const
Test whether this group is equal to group g.
Definition core.hpp:5285
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition core.hpp:799
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition core.cpp:999
friend class PostTraceInfo
Definition core.hpp:738
PropagatorGroup(unsigned int gid)
Initialize with group id gid.
Definition core.hpp:5267
bool operator!=(PropagatorGroup g) const
Test whether this group is different from group g.
Definition core.hpp:5289
PropagatorGroup(void)
Constructor.
Definition core.hpp:5264
PropagatorGroup & operator=(const PropagatorGroup &g)
Assignment operator.
Definition core.hpp:5275
friend class Propagator
Definition core.hpp:735
void disable(Space &home)
Disable all propagators in a group.
Definition core.cpp:1046
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition core.cpp:1055
Home operator()(Space &home)
To augment a space argument.
Definition core.hpp:5280
friend class PropagateTraceInfo
Definition core.hpp:737
void kill(Space &home)
Kill all propagators in a group.
Definition core.cpp:1033
friend class ViewTraceInfo
Definition core.hpp:736
static PropagatorGroup all
Group of all propagators.
Definition core.hpp:796
Base-class for propagators.
Definition core.hpp:1073
virtual void reschedule(Space &home)=0
Schedule function.
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1086
friend class SubscribedPropagators
Definition core.hpp:1079
friend class Space
Definition core.hpp:1075
double afc(void) const
Return the accumulated failure count.
Definition core.hpp:3742
virtual PropCost cost(const Space &home, const ModEventDelta &med) const =0
Cost function.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition core.cpp:73
friend class ActorLink
Definition core.hpp:1074
Kernel::GPI::Info & gpi(void)
Provide access to propagator information.
Definition core.hpp:3702
unsigned int id(void) const
Return propagator id.
Definition core.hpp:3759
friend class VarImp
Definition core.hpp:1076
friend class Advisor
Definition core.hpp:1077
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition core.hpp:3764
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition core.hpp:3737
Propagator * fwd(void) const
Return forwarding pointer during copying.
Definition core.hpp:3675
friend class PropagatorGroup
Definition core.hpp:1080
friend class Council
Definition core.hpp:1078
bool disabled(void) const
Whether propagator is currently disabled.
Definition core.hpp:3685
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1084
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Gecode::ActorLink * advisors
A list of advisors (used during cloning).
Definition core.hpp:1088
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:5350
const Propagator & propagator(void) const
Return propagator.
Definition core.hpp:5360
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:5354
Propagators(const Space &home, PropagatorGroup g)
Initialize.
Definition core.hpp:5344
Class to iterate over branchers of a space.
Definition core.hpp:2871
Brancher & brancher(void) const
Return propagator.
Definition core.hpp:5228
void operator++(void)
Move iterator to next brancher.
Definition core.hpp:5224
Branchers(Space &home)
Initialize.
Definition core.hpp:5217
bool operator()(void) const
Test whether there are branchers left.
Definition core.hpp:5220
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:5207
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:5211
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:5203
IdlePropagators(Space &home)
Initialize.
Definition core.hpp:5198
~NoGPI(void)
Restore the previous setting.
Definition core.hpp:3638
Class to iterate over propagators of a space.
Definition core.hpp:2800
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:5124
Propagators(Space &home)
Initialize.
Definition core.hpp:5106
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:5128
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:5152
ScheduledPropagators(Space &home)
Initialize.
Definition core.hpp:5158
Propagator & propagator(void) const
Return propagator.
Definition core.hpp:5192
bool operator()(void) const
Test whether there are propagators left.
Definition core.hpp:5170
void operator++(void)
Move iterator to next propagator.
Definition core.hpp:5174
~UseGPI(void)
Restore the previous setting.
Definition core.hpp:3649
Computation spaces.
Definition core.hpp:1787
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:3024
Space * source
Source space during clone construction.
Definition core.hpp:1903
friend void trace(Home home, TraceFilter tf, int te, Tracer &t)
Create tracer.
Definition general.cpp:39
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@275070317317120154232063063134255170030071110047 p
Data only available during propagation or branching.
void * ralloc(size_t s)
Allocate memory on space heap.
Definition core.hpp:2935
double afc_decay(void) const
Return AFC decay factor.
Definition core.hpp:3420
struct Gecode::Space::@055132133326276162005044145100211202071356247106::@155123175027073262103111264343315000271204104107 c
Data available only during copying.
void afc_unshare(void)
Unshare AFC information for all propagators.
Definition core.cpp:934
T & construct(void)
Construction routines.
Definition core.hpp:5392
friend class LocalObject
Definition core.hpp:1799
ActorLink queue[PropCost::AC_MAX+1]
Scheduled propagators according to cost.
Definition core.hpp:1881
LocalObject * local
Linked list of local objects.
Definition core.hpp:1901
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:2943
friend class VarImpDisposer
Definition core.hpp:1798
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later).
Definition core.hpp:2939
VarImpBase * vars_noidx
Keep variables during copying without index structure.
Definition core.hpp:1899
void * fl_alloc(void)
Allocate from freelist-managed memory.
Definition core.hpp:2958
friend class AFC
Definition core.hpp:1801
VarImpBase * vars_u[AllVarConf::idx_c]
Entries for updating variables.
Definition core.hpp:1897
friend class VarImp
Definition core.hpp:1797
friend class Advisor
Definition core.hpp:1795
friend class PostInfo
Definition core.hpp:1802
void afc_decay(double d)
Set AFC decay factor to d
Definition core.hpp:3425
friend class Propagator
Definition core.hpp:1789
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition core.hpp:2963
unsigned int n_sub
Number of subscriptions.
Definition core.hpp:1890
friend class PropagatorGroup
Definition core.hpp:1790
friend class Region
Definition core.hpp:1800
friend class Brancher
Definition core.hpp:1792
friend class Council
Definition core.hpp:1796
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2973
unsigned int bid_sc
Id of next brancher to be created plus status control.
Definition core.hpp:1888
friend class BrancherGroup
Definition core.hpp:1793
ActorLink * active
Cost level with next propagator to be executed.
Definition core.hpp:1879
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition core.hpp:2999
ViewTraceInfo vti
View trace information.
Definition core.hpp:1892
friend class Actor
Definition core.hpp:1788
Home operator()(Propagator &p)
Return a home for this space with the information that p is being rewritten.
Definition core.hpp:3468
SpaceStatus status(void)
Query space status without collecting statistics.
Definition core.hpp:3378
Statistics for execution of status
Definition core.hpp:1736
void reset(void)
Reset information.
Definition core.hpp:4974
StatusStatistics(void)
Initialize.
Definition core.hpp:4978
unsigned long long int propagate
Number of propagator executions.
Definition core.hpp:1739
StatusStatistics operator+(const StatusStatistics &s)
Return sum with s.
Definition core.hpp:4987
StatusStatistics & operator+=(const StatusStatistics &s)
Increment by statistics s.
Definition core.hpp:4982
Iterator over subscribed propagators.
A mutex for mutual exclausion among several threads.
Definition thread.hpp:78
Exception: too many branchers
Definition exception.hpp:93
Trace filters.
Definition filter.hpp:133
Propagator for recording trace information.
Definition recorder.hpp:154
Base-class for variable implementations.
Definition core.hpp:177
Base class for Variable type disposer.
Definition core.hpp:185
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition core.cpp:53
VarImpDisposer(void)
Constructor (registers disposer with kernel).
Definition core.hpp:4954
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition core.hpp:4962
Base-class for variable implementations.
Definition core.hpp:224
void subscribe(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition core.hpp:4639
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition core.hpp:4829
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
Definition core.hpp:4746
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:4763
VarImp(void)
Creation of static instances.
Definition core.hpp:4390
friend class SubscribedPropagators
Definition core.hpp:228
friend class Space
Definition core.hpp:225
double afc(void) const
Return accumulated failure count (plus degree).
Definition core.hpp:4418
unsigned int bits(void) const
Provide access to free bits.
Definition core.hpp:4449
ActorLink ** base
Subscribed actors.
Definition core.hpp:238
bool copied(void) const
Is variable already copied.
Definition core.hpp:4475
friend class VarImpDisposer
Definition core.hpp:227
static void reschedule(Space &home, Propagator &p, PropCond pc, bool assigned, ModEvent me)
Schedule propagator p.
Definition core.hpp:4665
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Definition core.hpp:4541
unsigned int idx[pc_max+1]
Indices of subscribed actors.
Definition core.hpp:278
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition core.hpp:4481
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4523
VarImp * next(void) const
Return next copied variable.
static ModEvent me_combine(ModEvent me1, ModEvent me2)
Combine modifications events me1 and me2.
Definition core.hpp:4535
friend class Propagator
Definition core.hpp:226
unsigned int degree(void) const
Return degree (number of subscribed propagators and advisors).
Definition core.hpp:4411
VarImp(Space &home)
Creation.
Definition core.hpp:4374
static ModEventDelta med(ModEvent me)
Definition core.hpp:4529
VarImp< VIC > * fwd
Forwarding pointer.
Definition core.hpp:247
VarImp< VIC > * next
During cloning, points to the next copied variable.
Definition core.hpp:280
static ModEvent modevent(const Delta &d)
Return modification event.
Definition core.hpp:4443
View trace information.
Definition core.hpp:917
What what(void) const
Return what is currently executing.
Definition core.hpp:3513
friend class Space
Definition core.hpp:918
const Brancher & brancher(void) const
Return currently executing brancher.
Definition core.hpp:3523
const Propagator & propagator(void) const
Return currently executing propagator.
Definition core.hpp:3517
void other(void)
Record that nothing is known at this point.
Definition core.hpp:3509
friend class PostInfo
Definition core.hpp:919
What
What is currently executing.
Definition core.hpp:922
@ BRANCHER
A brancher is executing.
Definition core.hpp:926
@ POST
A post function is executing.
Definition core.hpp:928
@ PROPAGATOR
A propagator is currently executing.
Definition core.hpp:924
PropagatorGroup post(void) const
Return propagator group of currently executing post function.
Definition core.hpp:3529
Support::uptrint_t who
Encoding a tagged pointer or a tagged group id.
Definition core.hpp:934
#define GECODE_KERNEL_REALLOC(T)
Definition core.hpp:3059
const int * pi[]
Definition photo.cpp:14262
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3793
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition core.hpp:3786
ExecStatus ES_SUBSUMED_DISPOSED(Propagator &p, size_t s)
Propagator p is subsumed
Definition core.hpp:3774
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition core.hpp:4114
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:4128
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:4121
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
ActorProperty
Actor properties.
Definition core.hpp:560
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:4304
bool stable(void) const
Return if space is stable (at fixpoint or failed).
Definition core.hpp:4298
void fail(void)
Fail space.
Definition core.hpp:4275
@ AP_VIEW_TRACE
Definition core.hpp:580
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
@ AP_TRACE
Definition core.hpp:585
@ AP_WEAKLY
Definition core.hpp:575
Space(void)
Default constructor.
Definition core.cpp:121
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:918
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:896
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition core.cpp:900
virtual Space * copy(void)=0
Copying member function.
Space * clone(void) const
Clone space.
Definition core.hpp:3384
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:568
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:673
void trycommit(const Choice &c, unsigned int a)
If possible, commit choice c for alternative a.
Definition core.hpp:3409
void commit(const Choice &c, unsigned int a)
Commit choice c for alternative a.
Definition core.hpp:3398
SpaceStatus
Space status
Definition core.hpp:1726
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
void print(const Search::Statistics &stat, bool restart)
Print statistics.
Definition job-shop.cpp:677
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
void * ptrjoin(void *p, ptrdiff_t m)
Join unmarked pointer p and m into marked pointer.
void * ptrsplit(void *p, ptrdiff_t &m)
Split possibly marked pointer p into mark m and unmarked pointer.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
std::make_unsigned_t< ptrdiff_t > uptrint_t
Unsigned integer for pointer encodings.
Definition int-type.hpp:53
void * fmark(void *p)
Return marked pointer for p (possibly already marked).
void * mark(void *p)
Return marked pointer for unmarked pointer p.
void * funmark(void *p)
Clear the lowest bits bits of a possibly marked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode toplevel namespace
const PropCond PC_GEN_ASSIGNED
Propagation condition for an assigned variable.
Definition core.hpp:81
const ModEvent ME_GEN_NONE
Generic modification event: no modification.
Definition core.hpp:72
TFE propagator(PropagatorGroup g)
Only propagators (but not post functions) from g are considered.
Definition filter.cpp:131
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_SUBSUMED_
Internal: propagator is subsumed, do not use.
Definition core.hpp:480
@ ES_NOFIX_FORCE
Advisor forces rescheduling of propagator.
Definition core.hpp:485
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_PARTIAL_
Internal: propagator has computed partial fixpoint, do not use.
Definition core.hpp:486
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
const ModEvent ME_GEN_FAILED
Generic modification event: failed variable.
Definition core.hpp:70
int PropCond
Type for propagation conditions.
Definition core.hpp:77
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition core.hpp:74
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience).
Definition core.hpp:79
int ModEvent
Type for modification events.
Definition core.hpp:67
Gecode::FloatVal b(9, 12)
Gecode::FloatVal a(-8, 5)
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
#define GECODE_NOT_NULL(p)
Assert that a pointer is never nullptr.
Definition macros.hpp:75
#define GECODE_VTABLE_EXPORT
Definition support.hh:76