1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * Guido Tack <tack@gecode.org> 6 * Mikael Lagerkvist <lagerkvist@gecode.org> 7 * 8 * Contributing authors: 9 * Filip Konvicka <filip.konvicka@logis.cz> 10 * Samuel Gagnon <samuel.gagnon92@gmail.com> 11 * 12 * Copyright: 13 * Christian Schulte, 2002 14 * Guido Tack, 2003 15 * Mikael Lagerkvist, 2006 16 * LOGIS, s.r.o., 2009 17 * Samuel Gagnon, 2018 18 * 19 * Bugfixes provided by: 20 * Alexander Samoilov <alexander_samoilov@yahoo.com> 21 * 22 * This file is part of Gecode, the generic constraint 23 * development environment: 24 * http://www.gecode.org 25 * 26 * Permission is hereby granted, free of charge, to any person obtaining 27 * a copy of this software and associated documentation files (the 28 * "Software"), to deal in the Software without restriction, including 29 * without limitation the rights to use, copy, modify, merge, publish, 30 * distribute, sublicense, and/or sell copies of the Software, and to 31 * permit persons to whom the Software is furnished to do so, subject to 32 * the following conditions: 33 * 34 * The above copyright notice and this permission notice shall be 35 * included in all copies or substantial portions of the Software. 36 * 37 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 38 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 39 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 40 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 41 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 42 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 43 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 44 * 45 */ 46 47 #include <iostream> 48 49 namespace Gecode { 50 51 class Space; 52 53 /** 54 * \defgroup TaskVarMEPC Generic modification events and propagation conditions 55 * 56 * Predefined modification events must be taken into account 57 * by variable types. 58 * \ingroup TaskVar 59 */ 60 //@{ 61 /// Type for modification events 62 typedef int ModEvent; 63 64 /// Generic modification event: failed variable 65 const ModEvent ME_GEN_FAILED = -1; 66 /// Generic modification event: no modification 67 const ModEvent ME_GEN_NONE = 0; 68 /// Generic modification event: variable is assigned a value 69 const ModEvent ME_GEN_ASSIGNED = 1; 70 71 /// Type for propagation conditions 72 typedef int PropCond; 73 /// Propagation condition to be ignored (convenience) 74 const PropCond PC_GEN_NONE = -1; 75 /// Propagation condition for an assigned variable 76 const PropCond PC_GEN_ASSIGNED = 0; 77 //@} 78 79 /** 80 * \brief Modification event deltas 81 * 82 * Modification event deltas are used by propagators. A 83 * propagator stores a modification event for each variable type. 84 * They can be accessed through a variable or a view from a given 85 * propagator. They can be constructed from a given modevent by 86 * a variable or view. 87 * \ingroup TaskActor 88 */ 89 typedef int ModEventDelta; 90 91 } 92 93 #include <gecode/kernel/var-type.hpp> 94 95 namespace Gecode { 96 97 /// Configuration class for variable implementations without index structure 98 class NoIdxVarImpConf { 99 public: 100 /// Index for update 101 static const int idx_c = -1; 102 /// Index for disposal 103 static const int idx_d = -1; 104 /// Maximal propagation condition 105 static const PropCond pc_max = PC_GEN_ASSIGNED; 106 /// Freely available bits 107 static const int free_bits = 0; 108 /// Start of bits for modification event delta 109 static const int med_fst = 0; 110 /// End of bits for modification event delta 111 static const int med_lst = 0; 112 /// Bitmask for modification event delta 113 static const int med_mask = 0; 114 /// Combine modification events \a me1 and \a me2 115 static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2); 116 /// Update modification even delta \a med by \a me, return true on change 117 static bool med_update(ModEventDelta& med, ModEvent me); 118 }; 119 120 forceinline ModEvent me_combine(ModEvent,ModEvent)121 NoIdxVarImpConf::me_combine(ModEvent, ModEvent) { 122 GECODE_NEVER; return 0; 123 } 124 forceinline bool med_update(ModEventDelta &,ModEvent)125 NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) { 126 GECODE_NEVER; return false; 127 } 128 129 130 /* 131 * These are the classes of interest 132 * 133 */ 134 class ActorLink; 135 class Actor; 136 class Propagator; 137 class SubscribedPropagators; 138 class LocalObject; 139 class Advisor; 140 class AFC; 141 class Choice; 142 class Brancher; 143 class Group; 144 class PropagatorGroup; 145 class BrancherGroup; 146 class PostInfo; 147 class ViewTraceInfo; 148 class PropagateTraceInfo; 149 class CommitTraceInfo; 150 class PostTraceInfo; 151 class TraceRecorder; 152 class TraceFilter; 153 class Tracer; 154 155 template<class A> class Council; 156 template<class A> class Advisors; 157 template<class VIC> class VarImp; 158 159 160 /* 161 * Variable implementations 162 * 163 */ 164 165 /** 166 * \brief Base-class for variable implementations 167 * 168 * Serves as base-class that can be used without having to know any 169 * template arguments. 170 * \ingroup TaskVar 171 */ 172 class VarImpBase {}; 173 174 /** 175 * \brief Base class for %Variable type disposer 176 * 177 * Controls disposal of variable implementations. 178 * \ingroup TaskVar 179 */ 180 class GECODE_VTABLE_EXPORT VarImpDisposerBase { 181 public: 182 /// Dispose list of variable implementations starting at \a x 183 GECODE_KERNEL_EXPORT virtual void dispose(Space& home, VarImpBase* x); 184 /// Destructor (not used) 185 GECODE_KERNEL_EXPORT virtual ~VarImpDisposerBase(void); 186 }; 187 188 /** 189 * \brief %Variable implementation disposer 190 * 191 * Controls disposal of variable implementations. 192 * \ingroup TaskVar 193 */ 194 template<class VarImp> 195 class VarImpDisposer : public VarImpDisposerBase { 196 public: 197 /// Constructor (registers disposer with kernel) 198 VarImpDisposer(void); 199 /// Dispose list of variable implementations starting at \a x 200 virtual void dispose(Space& home, VarImpBase* x); 201 }; 202 203 /// Generic domain change information to be supplied to advisors 204 class Delta { 205 template<class VIC> friend class VarImp; 206 private: 207 /// Modification event 208 ModEvent me; 209 }; 210 211 /** 212 * \brief Base-class for variable implementations 213 * 214 * Implements variable implementation for variable implementation 215 * configuration of type \a VIC. 216 * \ingroup TaskVar 217 */ 218 template<class VIC> 219 class VarImp : public VarImpBase { 220 friend class Space; 221 friend class Propagator; 222 template<class VarImp> friend class VarImpDisposer; 223 friend class SubscribedPropagators; 224 private: 225 union { 226 /** 227 * \brief Subscribed actors 228 * 229 * The base pointer of the array of subscribed actors. 230 * 231 * This pointer must be first to avoid padding on 64 bit machines. 232 */ 233 ActorLink** base; 234 /** 235 * \brief Forwarding pointer 236 * 237 * During cloning, this is used as the forwarding pointer for the 238 * variable. The original value is saved in the copy and restored after 239 * cloning. 240 * 241 */ 242 VarImp<VIC>* fwd; 243 } b; 244 245 /// Index for update 246 static const int idx_c = VIC::idx_c; 247 /// Index for disposal 248 static const int idx_d = VIC::idx_d; 249 /// Number of freely available bits 250 static const int free_bits = VIC::free_bits; 251 /// Number of used subscription entries 252 unsigned int entries; 253 /// Number of free subscription entries 254 unsigned int free_and_bits; 255 /// Maximal propagation condition 256 static const Gecode::PropCond pc_max = VIC::pc_max; 257 #ifdef GECODE_HAS_CBS 258 /// Unique id for variable 259 const unsigned var_id; 260 #endif 261 262 union { 263 /** 264 * \brief Indices of subscribed actors 265 * 266 * The entries from base[0] to base[idx[pc_max]] are propagators, 267 * where the entries between base[idx[pc-1]] and base[idx[pc]] are 268 * the propagators that have subscribed with propagation condition pc. 269 * 270 * The entries between base[idx[pc_max]] and base[idx[pc_max+1]] are the 271 * advisors subscribed to the variable implementation. 272 */ 273 unsigned int idx[pc_max+1]; 274 /// During cloning, points to the next copied variable 275 VarImp<VIC>* next; 276 } u; 277 278 /// Return subscribed actor at index \a pc 279 ActorLink** actor(PropCond pc); 280 /// Return subscribed actor at index \a pc, where \a pc is non-zero 281 ActorLink** actorNonZero(PropCond pc); 282 /// Return reference to index \a pc, where \a pc is non-zero 283 unsigned int& idx(PropCond pc); 284 /// Return index \a pc, where \a pc is non-zero 285 unsigned int idx(PropCond pc) const; 286 287 /** 288 * \brief Update copied variable \a x 289 * 290 * The argument \a sub gives the memory area where subscriptions are 291 * to be stored. 292 */ 293 void update(VarImp* x, ActorLink**& sub); 294 /** 295 * \brief Update all copied variables of this type 296 * 297 * The argument \a sub gives the memory area where subscriptions are 298 * to be stored. 299 */ 300 static void update(Space& home, ActorLink**& sub); 301 302 /// Enter propagator to subscription array 303 void enter(Space& home, Propagator* p, PropCond pc); 304 /// Enter advisor to subscription array 305 void enter(Space& home, Advisor* a); 306 /// Resize subscription array 307 void resize(Space& home); 308 /// Remove propagator from subscription array 309 void remove(Space& home, Propagator* p, PropCond pc); 310 /// Remove advisor from subscription array 311 void remove(Space& home, Advisor* a); 312 313 314 protected: 315 /// Cancel all subscriptions when variable implementation is assigned 316 void cancel(Space& home); 317 /** 318 * \brief Run advisors when variable implementation has been modified with modification event \a me and domain change \a d 319 * 320 * Returns false if an advisor has failed. 321 */ 322 bool advise(Space& home, ModEvent me, Delta& d); 323 private: 324 /// Run advisors to be run on failure 325 void _fail(Space& home); 326 protected: 327 /// Run advisors to be run on failure and returns ME_GEN_FAILED 328 ModEvent fail(Space& home); 329 #ifdef GECODE_HAS_VAR_DISPOSE 330 /// Return reference to variables (dispose) 331 static VarImp<VIC>* vars_d(Space& home); 332 /// %Set reference to variables (dispose) 333 static void vars_d(Space& home, VarImp<VIC>* x); 334 #endif 335 336 public: 337 /// Creation 338 VarImp(Space& home); 339 /// Creation of static instances 340 VarImp(void); 341 342 #ifdef GECODE_HAS_CBS 343 /// Return variable id 344 unsigned int id(void) const; 345 #endif 346 347 /// \name Dependencies 348 //@{ 349 /** \brief Subscribe propagator \a p with propagation condition \a pc 350 * 351 * In case \a schedule is false, the propagator is just subscribed but 352 * not scheduled for execution (this must be used when creating 353 * subscriptions during propagation). 354 * 355 * In case the variable is assigned (that is, \a assigned is 356 * true), the subscribing propagator is scheduled for execution. 357 * Otherwise, the propagator subscribes and is scheduled for execution 358 * with modification event \a me provided that \a pc is different 359 * from \a PC_GEN_ASSIGNED. 360 */ 361 void subscribe(Space& home, Propagator& p, PropCond pc, 362 bool assigned, ModEvent me, bool schedule); 363 /// Cancel subscription of propagator \a p with propagation condition \a pc 364 void cancel(Space& home, Propagator& p, PropCond pc); 365 /** \brief Subscribe advisor \a a to variable 366 * 367 * The advisor \a a is only subscribed if \a assigned is false. 368 * 369 * If \a fail is true, the advisor \a a is also run when a variable 370 * operation triggers failure. This feature is undocumented. 371 * 372 */ 373 void subscribe(Space& home, Advisor& a, bool assigned, bool fail); 374 /// Cancel subscription of advisor \a a 375 void cancel(Space& home, Advisor& a, bool fail); 376 377 /** 378 * \brief Return degree (number of subscribed propagators and advisors) 379 * 380 * Note that the degree of a variable implementation is not available 381 * during cloning. 382 */ 383 unsigned int degree(void) const; 384 /** 385 * \brief Return accumulated failure count (plus degree) 386 * 387 * Note that the accumulated failure count of a variable implementation 388 * is not available during cloning. 389 */ 390 double afc(void) const; 391 //@} 392 393 /// \name Cloning variables 394 //@{ 395 /// Constructor for cloning 396 VarImp(Space& home, VarImp& x); 397 /// Is variable already copied 398 bool copied(void) const; 399 /// Use forward pointer if variable already copied 400 VarImp* forward(void) const; 401 /// Return next copied variable 402 VarImp* next(void) const; 403 //@} 404 405 /// \name Variable implementation-dependent propagator support 406 //@{ 407 /** 408 * \brief Schedule propagator \a p with modification event \a me 409 * 410 * If \a force is true, the propagator is re-scheduled (including 411 * cost computation) even though its modification event delta has 412 * not changed. 413 */ 414 static void schedule(Space& home, Propagator& p, ModEvent me, 415 bool force = false); 416 /** 417 * \brief Schedule propagator \a p 418 * 419 * Schedules a propagator for propagation condition \a pc and 420 * modification event \a me. If the variable is assigned, 421 * the appropriate modification event is used for scheduling. 422 */ 423 static void reschedule(Space& home, Propagator& p, PropCond pc, 424 bool assigned, ModEvent me); 425 /// Project modification event for this variable type from \a med 426 static ModEvent me(const ModEventDelta& med); 427 /// Translate modification event \a me into modification event delta 428 static ModEventDelta med(ModEvent me); 429 /// Combine modifications events \a me1 and \a me2 430 static ModEvent me_combine(ModEvent me1, ModEvent me2); 431 //@} 432 433 /// \name Delta information for advisors 434 //@{ 435 /// Return modification event 436 static ModEvent modevent(const Delta& d); 437 //@} 438 439 /// \name Bit management 440 //@{ 441 /// Provide access to free bits 442 unsigned int bits(void) const; 443 /// Provide access to free bits 444 unsigned int& bits(void); 445 //@} 446 447 protected: 448 /// Schedule subscribed propagators 449 void schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me); 450 451 public: 452 /// \name Memory management 453 //@{ 454 /// Allocate memory from space 455 static void* operator new(size_t,Space&); 456 /// Return memory to space 457 static void operator delete(void*,Space&); 458 /// Needed for exceptions 459 static void operator delete(void*); 460 //@} 461 }; 462 463 464 /** 465 * \defgroup TaskActorStatus Status of constraint propagation and branching commit 466 * Note that the enum values starting with a double underscore should not 467 * be used directly. Instead, use the provided functions with the same 468 * name without leading underscores. 469 * 470 * \ingroup TaskActor 471 */ 472 enum ExecStatus { 473 ES_SUBSUMED_ = -2, ///< Internal: propagator is subsumed, do not use 474 ES_FAILED = -1, ///< Execution has resulted in failure 475 ES_NOFIX = 0, ///< Propagation has not computed fixpoint 476 ES_OK = 0, ///< Execution is okay 477 ES_FIX = 1, ///< Propagation has computed fixpoint 478 ES_NOFIX_FORCE = 2, ///< Advisor forces rescheduling of propagator 479 ES_PARTIAL_ = 2 ///< Internal: propagator has computed partial fixpoint, do not use 480 }; 481 482 /** 483 * \brief Propagation cost 484 * \ingroup TaskActor 485 */ 486 class PropCost { 487 friend class Space; 488 public: 489 /// The actual cost values that are used 490 enum ActualCost { 491 AC_RECORD = 0, ///< Reserved for recording information 492 AC_CRAZY_LO = 1, ///< Exponential complexity, cheap 493 AC_CRAZY_HI = 1, ///< Exponential complexity, expensive 494 AC_CUBIC_LO = 1, ///< Cubic complexity, cheap 495 AC_CUBIC_HI = 1, ///< Cubic complexity, expensive 496 AC_QUADRATIC_LO = 2, ///< Quadratic complexity, cheap 497 AC_QUADRATIC_HI = 2, ///< Quadratic complexity, expensive 498 AC_LINEAR_HI = 3, ///< Linear complexity, expensive 499 AC_LINEAR_LO = 4, ///< Linear complexity, cheap 500 AC_TERNARY_HI = 4, ///< Three variables, expensive 501 AC_BINARY_HI = 5, ///< Two variables, expensive 502 AC_TERNARY_LO = 5, ///< Three variables, cheap 503 AC_BINARY_LO = 6, ///< Two variables, cheap 504 AC_UNARY_LO = 6, ///< Only single variable, cheap 505 AC_UNARY_HI = 6, ///< Only single variable, expensive 506 AC_MAX = 6 ///< Maximal cost value 507 }; 508 /// Actual cost 509 ActualCost ac; 510 public: 511 /// Propagation cost modifier 512 enum Mod { 513 LO, ///< Cheap 514 HI ///< Expensive 515 }; 516 private: 517 /// Compute dynamic cost for cost \a lo, expensive cost \a hi, and size measure \a n 518 static PropCost cost(Mod m, ActualCost lo, ActualCost hi, unsigned int n); 519 /// Constructor for automatic coercion of \a ac 520 PropCost(ActualCost ac); 521 public: 522 /// For recording information (no propagation allowed) 523 static PropCost record(void); 524 /// Exponential complexity for modifier \a m and size measure \a n 525 static PropCost crazy(PropCost::Mod m, unsigned int n); 526 /// Exponential complexity for modifier \a m and size measure \a n 527 static PropCost crazy(PropCost::Mod m, int n); 528 /// Cubic complexity for modifier \a m and size measure \a n 529 static PropCost cubic(PropCost::Mod m, unsigned int n); 530 /// Cubic complexity for modifier \a m and size measure \a n 531 static PropCost cubic(PropCost::Mod m, int n); 532 /// Quadratic complexity for modifier \a m and size measure \a n 533 static PropCost quadratic(PropCost::Mod m, unsigned int n); 534 /// Quadratic complexity for modifier \a m and size measure \a n 535 static PropCost quadratic(PropCost::Mod m, int n); 536 /// Linear complexity for modifier \a pcm and size measure \a n 537 static PropCost linear(PropCost::Mod m, unsigned int n); 538 /// Linear complexity for modifier \a pcm and size measure \a n 539 static PropCost linear(PropCost::Mod m, int n); 540 /// Three variables for modifier \a pcm 541 static PropCost ternary(PropCost::Mod m); 542 /// Two variables for modifier \a pcm 543 static PropCost binary(PropCost::Mod m); 544 /// Single variable for modifier \a pcm 545 static PropCost unary(PropCost::Mod m); 546 }; 547 548 549 /** 550 * \brief Actor properties 551 * \ingroup TaskActor 552 */ 553 enum ActorProperty { 554 /** 555 * \brief Actor must always be disposed 556 * 557 * Normally, a propagator will not be disposed if its home space 558 * is deleted. However, if an actor uses external resources, 559 * this property can be used to make sure that the actor 560 * will always be disposed. 561 */ 562 AP_DISPOSE = (1 << 0), 563 /** 564 * Propagator is only weakly monotonic, that is, the propagator 565 * is only monotonic on assignments. 566 * 567 */ 568 AP_WEAKLY = (1 << 1), 569 /** 570 * A propagator is in fact implementing a view trace recorder. 571 * 572 */ 573 AP_VIEW_TRACE = (1 << 2), 574 /** 575 * A propagator is in fact implementing a trace recorder. 576 * 577 */ 578 AP_TRACE = (1 << 3) 579 }; 580 581 582 /** 583 * \brief Double-linked list for actors 584 * 585 * Used to maintain which actors belong to a space and also 586 * (for propagators) to organize actors in the queue of 587 * waiting propagators. 588 */ 589 class ActorLink { 590 friend class Actor; 591 friend class Propagator; 592 friend class Advisor; 593 friend class Brancher; 594 friend class LocalObject; 595 friend class Space; 596 template<class VIC> friend class VarImp; 597 private: 598 ActorLink* _next; ActorLink* _prev; 599 public: 600 //@{ 601 /// Routines for double-linked list 602 ActorLink* prev(void) const; void prev(ActorLink*); 603 ActorLink* next(void) const; void next(ActorLink*); 604 ActorLink** next_ref(void); 605 //@} 606 607 /// Initialize links (self-linked) 608 void init(void); 609 /// Remove from predecessor and successor 610 void unlink(void); 611 /// Insert \a al directly after this 612 void head(ActorLink* al); 613 /// Insert \a al directly before this 614 void tail(ActorLink* al); 615 /// Test whether actor link is empty (points to itself) 616 bool empty(void) const; 617 /// Static cast for a non-null pointer (to give a hint to optimizer) 618 template<class T> static ActorLink* cast(T* a); 619 /// Static cast for a non-null pointer (to give a hint to optimizer) 620 template<class T> static const ActorLink* cast(const T* a); 621 }; 622 623 624 /** 625 * \brief Base-class for both propagators and branchers 626 * \ingroup TaskActor 627 */ 628 class GECODE_VTABLE_EXPORT Actor : private ActorLink { 629 friend class ActorLink; 630 friend class Space; 631 friend class Propagator; 632 friend class Advisor; 633 friend class Brancher; 634 friend class LocalObject; 635 template<class VIC> friend class VarImp; 636 template<class A> friend class Council; 637 private: 638 /// Static cast for a non-null pointer (to give a hint to optimizer) 639 static Actor* cast(ActorLink* al); 640 /// Static cast for a non-null pointer (to give a hint to optimizer) 641 static const Actor* cast(const ActorLink* al); 642 /// Static member to test against during space cloning 643 GECODE_KERNEL_EXPORT static Actor* sentinel; 644 public: 645 /// Create copy 646 virtual Actor* copy(Space& home) = 0; 647 648 /// \name Memory management 649 //@{ 650 /// Delete actor and return its size 651 GECODE_KERNEL_EXPORT 652 virtual size_t dispose(Space& home); 653 /// Allocate memory from space 654 static void* operator new(size_t s, Space& home); 655 /// No-op for exceptions 656 static void operator delete(void* p, Space& home); 657 //@} 658 public: 659 /// To avoid warnings 660 GECODE_KERNEL_EXPORT virtual ~Actor(void); 661 /// Not used 662 static void* operator new(size_t s); 663 /// Not used 664 static void operator delete(void* p); 665 }; 666 667 class Home; 668 669 /** 670 * \brief Group baseclass for controlling actors 671 * \ingroup TaskGroup 672 */ 673 class Group { 674 friend class Home; 675 friend class Propagator; 676 friend class Brancher; 677 friend class ViewTraceInfo; 678 friend class PropagateTraceInfo; 679 friend class CommitTraceInfo; 680 friend class PostTraceInfo; 681 protected: 682 /// Fake id for group of all actors 683 static const unsigned int GROUPID_ALL = 0U; 684 /// Pre-defined default group id 685 static const unsigned int GROUPID_DEF = 1U; 686 /// The maximal group number 687 static const unsigned int GROUPID_MAX = UINT_MAX >> 2; 688 /// The group id 689 unsigned int gid; 690 /// Next group id 691 GECODE_KERNEL_EXPORT 692 static unsigned int next; 693 /// Mutex for protection 694 GECODE_KERNEL_EXPORT 695 static Support::Mutex m; 696 /// Construct with predefined group id \a gid0 697 Group(unsigned int gid0); 698 public: 699 /// \name Construction and access 700 //@{ 701 /// Constructor 702 GECODE_KERNEL_EXPORT 703 Group(void); 704 /// Copy constructor 705 Group(const Group& g); 706 /// Assignment operator 707 Group& operator =(const Group& g); 708 /// Return a unique id for the group 709 unsigned int id(void) const; 710 /// Check whether actor group \a a is included in this group 711 bool in(Group a) const; 712 /// Check whether this is a real group (and not just default) 713 bool in(void) const; 714 //@} 715 /// Group of all actors 716 GECODE_KERNEL_EXPORT 717 static Group all; 718 /// Group of actors not in any user-defined group 719 GECODE_KERNEL_EXPORT 720 static Group def; 721 }; 722 723 /** 724 * \brief Group of propagators 725 * \ingroup TaskGroup 726 */ 727 class PropagatorGroup : public Group { 728 friend class Propagator; 729 friend class ViewTraceInfo; 730 friend class PropagateTraceInfo; 731 friend class PostTraceInfo; 732 protected: 733 /// Initialize with group id \a gid 734 PropagatorGroup(unsigned int gid); 735 public: 736 /// \name Construction 737 //@{ 738 /// Constructor 739 PropagatorGroup(void); 740 /// Copy constructor 741 PropagatorGroup(const PropagatorGroup& g); 742 /// Assignment operator 743 PropagatorGroup& operator =(const PropagatorGroup& g); 744 /// To augment a space argument 745 Home operator ()(Space& home); 746 //@} 747 /// \name Move propagators between groups 748 //@{ 749 /// Move propagators from group \a g to this group 750 GECODE_KERNEL_EXPORT 751 PropagatorGroup& move(Space& home, PropagatorGroup g); 752 /// Move propagator \a p to this group 753 PropagatorGroup& move(Space& home, Propagator& p); 754 /** 755 * \brief Move propagator with id \a id to this group 756 * 757 * Throws an exception of type UnknownPropagator, if no propagator 758 * with id \a id exists. 759 */ 760 GECODE_KERNEL_EXPORT 761 PropagatorGroup& move(Space& home, unsigned int id); 762 //@} 763 /// \name Operations on groups 764 //@{ 765 /// Test whether this group is equal to group \a g 766 bool operator ==(PropagatorGroup g) const; 767 /// Test whether this group is different from group \a g 768 bool operator !=(PropagatorGroup g) const; 769 /// Return number of propagators in a group 770 GECODE_KERNEL_EXPORT 771 unsigned int size(Space& home) const; 772 /// Kill all propagators in a group 773 GECODE_KERNEL_EXPORT 774 void kill(Space& home); 775 /// Disable all propagators in a group 776 GECODE_KERNEL_EXPORT 777 void disable(Space& home); 778 /** 779 * \brief Enable all propagators in a group 780 * 781 * If \a s is true, the propagators will be scheduled for propagation 782 * if needed. 783 */ 784 GECODE_KERNEL_EXPORT 785 void enable(Space& home, bool s=true); 786 //@} 787 /// Group of all propagators 788 GECODE_KERNEL_EXPORT 789 static PropagatorGroup all; 790 /// Group of propagators not in any user-defined group 791 GECODE_KERNEL_EXPORT 792 static PropagatorGroup def; 793 }; 794 795 /** 796 * \brief Group of branchers 797 * \ingroup TaskGroup 798 */ 799 class BrancherGroup : public Group { 800 friend class Brancher; 801 protected: 802 /// Initialize with group id \a gid 803 BrancherGroup(unsigned int gid); 804 public: 805 /// \name Construction 806 //@{ 807 /// Constructor 808 BrancherGroup(void); 809 /// Copy constructor 810 BrancherGroup(const BrancherGroup& g); 811 /// Assignment operator 812 BrancherGroup& operator =(const BrancherGroup& g); 813 /// To augment a space argument 814 Home operator ()(Space& home); 815 //@} 816 /// \name Move branchers between groups 817 //@{ 818 /// Move branchers from group \a g to this group 819 GECODE_KERNEL_EXPORT 820 BrancherGroup& move(Space& home, BrancherGroup g); 821 /// Move brancher \a b to this group 822 BrancherGroup& move(Space& home, Brancher& b); 823 /** 824 * \brief Move brancher with id \a id to this group 825 * 826 * Throws an exception of type UnknownBrancher, if no brancher 827 * with id \a id exists. 828 */ 829 GECODE_KERNEL_EXPORT 830 BrancherGroup& move(Space& home, unsigned int id); 831 //@} 832 /// \name Operations on groups 833 //@{ 834 /// Test whether this group is equal to group \a g 835 bool operator ==(BrancherGroup g) const; 836 /// Test whether this group is different from group \a g 837 bool operator !=(BrancherGroup g) const; 838 /// Return number of branchers in a group 839 GECODE_KERNEL_EXPORT 840 unsigned int size(Space& home) const; 841 /// Kill all branchers in a group 842 GECODE_KERNEL_EXPORT 843 void kill(Space& home); 844 //@} 845 /// Group of all branchers 846 GECODE_KERNEL_EXPORT 847 static BrancherGroup all; 848 /// Group of branchers not in any user-defined group 849 GECODE_KERNEL_EXPORT 850 static BrancherGroup def; 851 }; 852 853 /** 854 * \brief %Home class for posting propagators 855 */ 856 class Home { 857 friend class PostInfo; 858 protected: 859 /// The space where the propagator is to be posted 860 Space& s; 861 /// A propagator (possibly) that is currently being rewritten 862 Propagator* p; 863 /// A propagator group 864 PropagatorGroup pg; 865 /// A brancher group 866 BrancherGroup bg; 867 public: 868 /// \name Conversion 869 //@{ 870 /// Initialize the home with space \a s and propagator \a p and group \a g 871 Home(Space& s, Propagator* p=nullptr, 872 PropagatorGroup pg=PropagatorGroup::def, 873 BrancherGroup bg=BrancherGroup::def); 874 /// Copy constructor 875 Home(const Home& h); 876 /// Assignment operator 877 Home& operator =(const Home& h); 878 /// Retrieve the space of the home 879 operator Space&(void); 880 //@} 881 /// \name Extended information 882 //@{ 883 /// Return a home extended by propagator to be rewritten 884 Home operator ()(Propagator& p); 885 /// Return a home extended by a propagator group 886 Home operator ()(PropagatorGroup pg); 887 /// Return a home extended by a brancher group 888 Home operator ()(BrancherGroup bg); 889 /// Return propagator (or nullptr) for currently rewritten propagator 890 Propagator* propagator(void) const; 891 /// Return propagator group 892 PropagatorGroup propagatorgroup(void) const; 893 /// Return brancher group 894 BrancherGroup branchergroup(void) const; 895 //@} 896 /// \name Forwarding of common space operations 897 //@{ 898 /// Check whether corresponding space is failed 899 bool failed(void) const; 900 /// Mark space as failed 901 void fail(void); 902 /// Notice actor property 903 void notice(Actor& a, ActorProperty p, bool duplicate=false); 904 //@} 905 }; 906 907 /** 908 * \brief View trace information 909 */ 910 class ViewTraceInfo { 911 friend class Space; 912 friend class PostInfo; 913 public: 914 /// What is currently executing 915 enum What { 916 /// A propagator is currently executing 917 PROPAGATOR = 0, 918 /// A brancher is executing 919 BRANCHER = 1, 920 /// A post function is executing 921 POST = 2, 922 /// Unknown 923 OTHER = 3 924 }; 925 protected: 926 /// Encoding a tagged pointer or a tagged group id 927 ptrdiff_t who; 928 /// Record that propagator \a p is executing 929 void propagator(Propagator& p); 930 /// Record that brancher \a b is executing 931 void brancher(Brancher& b); 932 /// Record that a post function with propagator group \a g is executing 933 void post(PropagatorGroup g); 934 /// Record that nothing is known at this point 935 void other(void); 936 public: 937 /// Return what is currently executing 938 What what(void) const; 939 /// Return currently executing propagator 940 const Propagator& propagator(void) const; 941 /// Return currently executing brancher 942 const Brancher& brancher(void) const; 943 /// Return propagator group of currently executing post function 944 PropagatorGroup post(void) const; 945 }; 946 947 /** 948 * \brief Class to set group information when a post function is executed 949 */ 950 class PostInfo { 951 friend class Space; 952 protected: 953 /// The home space 954 Space& h; 955 /// The propagator group 956 PropagatorGroup pg; 957 /// Next free propagator id 958 unsigned int pid; 959 /// Whether it is used nested 960 bool nested; 961 public: 962 /// Set information 963 PostInfo(Home home); 964 /// Reset information 965 ~PostInfo(void); 966 }; 967 968 /** 969 * \brief Propagate trace information 970 */ 971 class PropagateTraceInfo { 972 friend class Space; 973 public: 974 /// Propagator status 975 enum Status { 976 FIX, ///< Propagator computed fixpoint 977 NOFIX, ///< Propagator did not compute fixpoint 978 FAILED, ///< Propagator failed 979 SUBSUMED ///< Propagator is subsumed 980 }; 981 protected: 982 /// Propagator id 983 unsigned int i; 984 /// Propagator group 985 PropagatorGroup g; 986 /// Propagator 987 const Propagator* p; 988 /// Status 989 Status s; 990 /// Initialize 991 PropagateTraceInfo(unsigned int i, PropagatorGroup g, 992 const Propagator* p, Status s); 993 public: 994 /// Return propagator identifier 995 unsigned int id(void) const; 996 /// Return propagator group 997 PropagatorGroup group(void) const; 998 /// Return pointer to non-subsumed propagator 999 const Propagator* propagator(void) const; 1000 /// Return propagator status 1001 Status status(void) const; 1002 }; 1003 1004 /** 1005 * \brief Commit trace information 1006 */ 1007 class CommitTraceInfo { 1008 friend class Space; 1009 protected: 1010 /// Brancher 1011 const Brancher& b; 1012 /// Choice 1013 const Choice& c; 1014 /// Alternative 1015 unsigned int a; 1016 /// Initialize 1017 CommitTraceInfo(const Brancher& b, const Choice& c, unsigned int a); 1018 public: 1019 /// Return brancher identifier 1020 unsigned int id(void) const; 1021 /// Return brancher group 1022 BrancherGroup group(void) const; 1023 /// Return brancher 1024 const Brancher& brancher(void) const; 1025 /// Return choice 1026 const Choice& choice(void) const; 1027 /// Return alternative 1028 unsigned int alternative(void) const; 1029 }; 1030 1031 /** 1032 * \brief Post trace information 1033 */ 1034 class PostTraceInfo { 1035 friend class Space; 1036 friend class PostInfo; 1037 public: 1038 /// Post status 1039 enum Status { 1040 POSTED, ///< Propagator was posted 1041 FAILED, ///< Posting failed 1042 SUBSUMED ///< Propagator not posted as already subsumed 1043 }; 1044 protected: 1045 /// Propagator group 1046 PropagatorGroup g; 1047 /// Status 1048 Status s; 1049 /// Number of posted propagators 1050 unsigned int n; 1051 /// Initialize 1052 PostTraceInfo(PropagatorGroup g, Status s, unsigned int n); 1053 public: 1054 /// Return post status 1055 Status status(void) const; 1056 /// Return propagator group 1057 PropagatorGroup group(void) const; 1058 /// Return number of posted propagators 1059 unsigned int propagators(void) const; 1060 }; 1061 1062 /** 1063 * \brief Base-class for propagators 1064 * \ingroup TaskActor 1065 */ 1066 class GECODE_VTABLE_EXPORT Propagator : public Actor { 1067 friend class ActorLink; 1068 friend class Space; 1069 template<class VIC> friend class VarImp; 1070 friend class Advisor; 1071 template<class A> friend class Council; 1072 friend class SubscribedPropagators; 1073 friend class PropagatorGroup; 1074 private: 1075 union { 1076 /// A set of modification events (used during propagation) 1077 ModEventDelta med; 1078 /// The size of the propagator (used during subsumption) 1079 size_t size; 1080 /// A list of advisors (used during cloning) 1081 Gecode::ActorLink* advisors; 1082 } u; 1083 /// A tagged pointer combining a pointer to global propagator information and whether the propagator is disabled 1084 void* gpi_disabled; 1085 /// Static cast for a non-null pointer (to give a hint to optimizer) 1086 static Propagator* cast(ActorLink* al); 1087 /// Static cast for a non-null pointer (to give a hint to optimizer) 1088 static const Propagator* cast(const ActorLink* al); 1089 /// Disable propagator 1090 void disable(Space& home); 1091 /// Enable propagator 1092 void enable(Space& home); 1093 protected: 1094 /// Constructor for posting 1095 Propagator(Home home); 1096 /// Constructor for cloning \a p 1097 Propagator(Space& home, Propagator& p); 1098 /// Return forwarding pointer during copying 1099 Propagator* fwd(void) const; 1100 /// Provide access to global propagator information 1101 Kernel::GPI::Info& gpi(void); 1102 1103 public: 1104 /// \name Propagation 1105 //@{ 1106 /** 1107 * \brief Schedule function 1108 * 1109 * The function is executed when a propagator is enabled again. 1110 * Note that a propagator should be scheduled with the right 1111 * modification event delta and should only be scheduled if 1112 * it is legal to execute the propagator. 1113 */ 1114 virtual void reschedule(Space& home) = 0; 1115 /** 1116 * \brief Propagation function 1117 * 1118 * The propagation function must return an execution status as 1119 * follows: 1120 * - ES_FAILED: the propagator has detected failure 1121 * - ES_NOFIX: the propagator has done propagation 1122 * - ES_FIX: the propagator has done propagation and has computed 1123 * a fixpoint. That is, running the propagator immediately 1124 * again will do nothing. 1125 * 1126 * Apart from the above values, a propagator can return 1127 * the result from calling one of the functions defined by a space: 1128 * - ES_SUBSUMED: the propagator is subsumed and has been already 1129 * deleted. 1130 * - ES_NOFIX_PARTIAL: the propagator has consumed some of its 1131 * propagation events. 1132 * - ES_FIX_PARTIAL: the propagator has consumed some of its 1133 * propagation events and with respect to these events is 1134 * at fixpoint 1135 * For more details, see the individual functions. 1136 * 1137 */ 1138 virtual ExecStatus propagate(Space& home, const ModEventDelta& med) = 0; 1139 /// Cost function 1140 virtual PropCost cost(const Space& home, const ModEventDelta& med) const = 0; 1141 /** 1142 * \brief Return the modification event delta 1143 * 1144 * This function returns the modification event delta of the currently 1145 * executing propagator and hence can only be called within the 1146 * propagate function of a propagator. 1147 */ 1148 ModEventDelta modeventdelta(void) const; 1149 /** 1150 * \brief Advise function 1151 * 1152 * The advisor is passed as argument \a a. 1153 * 1154 * A propagator must specialize this advise function, if it 1155 * uses advisors. The advise function must return an execution 1156 * status as follows: 1157 * - ES_FAILED: the advisor has detected failure. 1158 * - ES_FIX: the advisor's propagator (that is, this propagator) 1159 * does not need to be run. 1160 * - ES_NOFIX: the advisor's propagator (that is, this propagator) 1161 * must be run. 1162 * - ES_NOFIX_FORCE: the advisor's propagator (that is, this propagator) 1163 * must be run and it must forcefully be rescheduled (including 1164 * recomputation of cost). 1165 * 1166 * Apart from the above values, an advisor can return 1167 * the result from calling the function defined by a space: 1168 * - ES_FIX_DISPOSE: the advisor's propagator does not need to be run 1169 * and the advisor will be disposed. 1170 * - ES_NOFIX_DISPOSE: the advisor's propagator must be run and the 1171 * advisor will be disposed. 1172 * - ES_NOFIX_FORCE_DISPOSE: the advisor's propagator must be run 1173 * , it must forcefully be rescheduled (including recomputation 1174 * of cost), and the adviser will be disposed. 1175 * For more details, see the function documentation. 1176 * 1177 * The delta \a d describes how the variable has been changed 1178 * by an operation on the advisor's variable. Typically, 1179 * the delta information can only be utilized by either 1180 * static or member functions of views as the actual delta 1181 * information is both domain and view dependent. 1182 * 1183 */ 1184 GECODE_KERNEL_EXPORT 1185 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d); 1186 /// Run advisor \a a to be run on failure in failed space 1187 GECODE_KERNEL_EXPORT 1188 virtual void advise(Space& home, Advisor& a); 1189 //@} 1190 /// \name Information 1191 //@{ 1192 /// Return the accumlated failure count 1193 double afc(void) const; 1194 //@} 1195 #ifdef GECODE_HAS_CBS 1196 /// \name Marginal distribution 1197 //@{ 1198 /** 1199 * \brief Solution distribution 1200 * 1201 * Computes the marginal distribution for every variable and value in the 1202 * propagator. A callback is used to transmit each result. 1203 */ 1204 /// Signature for function transmitting marginal distributions 1205 typedef std::function<void(unsigned int prop_id, unsigned int var_id, 1206 int val, double dens)> SendMarginal; 1207 virtual void solndistrib(Space& home, SendMarginal send) const; 1208 /** 1209 * \brief Sum of variable cardinalities 1210 * 1211 * \param size Sum of variable cardinalities 1212 * \param size_b Sum of variable cardinalities for subset involved 1213 * in branching decisions 1214 */ 1215 /// Signature for function testing if variables are candidates to branching decisions 1216 typedef std::function<bool(unsigned int var_id)> InDecision; 1217 virtual void domainsizesum(InDecision in, unsigned int& size, 1218 unsigned int& size_b) const; 1219 //@} 1220 #endif 1221 /// \name Id and group support 1222 //@{ 1223 /// Return propagator id 1224 unsigned int id(void) const; 1225 /// Return group propagator belongs to 1226 PropagatorGroup group(void) const; 1227 /// Add propagator to group \a g 1228 void group(PropagatorGroup g); 1229 /// Whether propagator is currently disabled 1230 bool disabled(void) const; 1231 //@} 1232 }; 1233 1234 1235 /** 1236 * \brief %Council of advisors 1237 * 1238 * If a propagator uses advisors, it must maintain its advisors 1239 * through a council. 1240 * \ingroup TaskActor 1241 */ 1242 template<class A> 1243 class Council { 1244 friend class Advisor; 1245 friend class Advisors<A>; 1246 private: 1247 /// Starting point for a linked list of advisors 1248 mutable ActorLink* advisors; 1249 public: 1250 /// Default constructor 1251 Council(void); 1252 /// Construct advisor council 1253 Council(Space& home); 1254 /// Test whether council has advisor left 1255 bool empty(void) const; 1256 /// Update during cloning (copies all advisors) 1257 void update(Space& home, Council<A>& c); 1258 /// Dispose council 1259 void dispose(Space& home); 1260 }; 1261 1262 1263 /** 1264 * \brief Class to iterate over advisors of a council 1265 * \ingroup TaskActor 1266 */ 1267 template<class A> 1268 class Advisors { 1269 private: 1270 /// The current advisor 1271 ActorLink* a; 1272 public: 1273 /// Initialize 1274 Advisors(const Council<A>& c); 1275 /// Test whether there advisors left 1276 bool operator ()(void) const; 1277 /// Move iterator to next advisor 1278 void operator ++(void); 1279 /// Return advisor 1280 A& advisor(void) const; 1281 }; 1282 1283 1284 /** 1285 * \brief Base-class for advisors 1286 * 1287 * Advisors are typically subclassed for each propagator that 1288 * wants to use advisors. The actual member function that 1289 * is executed when a variable is changed, must be implemented 1290 * by the advisor's propagator. 1291 * 1292 * \ingroup TaskActor 1293 */ 1294 class Advisor : private ActorLink { 1295 template<class VIC> friend class VarImp; 1296 template<class A> friend class Council; 1297 template<class A> friend class Advisors; 1298 friend class SubscribedPropagators; 1299 private: 1300 /// Is the advisor disposed? 1301 bool disposed(void) const; 1302 /// Static cast 1303 static Advisor* cast(ActorLink* al); 1304 /// Static cast 1305 static const Advisor* cast(const ActorLink* al); 1306 protected: 1307 /// Return the advisor's propagator 1308 Propagator& propagator(void) const; 1309 public: 1310 /// Constructor for creation 1311 template<class A> 1312 Advisor(Space& home, Propagator& p, Council<A>& c); 1313 /// Copying constructor 1314 Advisor(Space& home, Advisor& a); 1315 /// Provide access to view trace information 1316 const ViewTraceInfo& operator ()(const Space& home) const; 1317 1318 /// \name Memory management 1319 //@{ 1320 /// Dispose the advisor 1321 template<class A> 1322 void dispose(Space& home, Council<A>& c); 1323 /// Allocate memory from space 1324 static void* operator new(size_t s, Space& home); 1325 /// No-op for exceptions 1326 static void operator delete(void* p, Space& home); 1327 //@} 1328 private: 1329 #ifndef __GNUC__ 1330 /// Not used (uses dispose instead) 1331 static void operator delete(void* p); 1332 #endif 1333 /// Not used 1334 static void* operator new(size_t s); 1335 }; 1336 1337 1338 /** 1339 * \brief No-good literal recorded during search 1340 * 1341 */ 1342 class GECODE_VTABLE_EXPORT NGL { 1343 private: 1344 /// Combines pointer to next literal and mark whether it is a leaf 1345 void* nl; 1346 public: 1347 /// The status of a no-good literal 1348 enum Status { 1349 FAILED, ///< The literal is failed 1350 SUBSUMED, ///< The literal is subsumed 1351 NONE ///< The literal is neither failed nor subsumed 1352 }; 1353 /// Constructor for creation 1354 NGL(void); 1355 /// Constructor for creation 1356 NGL(Space& home); 1357 /// Constructor for cloning \a ngl 1358 NGL(Space& home, NGL& ngl); 1359 /// Subscribe propagator \a p to all views of the no-good literal 1360 virtual void subscribe(Space& home, Propagator& p) = 0; 1361 /// Cancel propagator \a p from all views of the no-good literal 1362 virtual void cancel(Space& home, Propagator& p) = 0; 1363 /// Schedule propagator \a p for all views of the no-good literal 1364 virtual void reschedule(Space& home, Propagator& p) = 0; 1365 /// Test the status of the no-good literal 1366 virtual NGL::Status status(const Space& home) const = 0; 1367 /// Propagate the negation of the no-good literal 1368 virtual ExecStatus prune(Space& home) = 0; 1369 /// Create copy 1370 virtual NGL* copy(Space& home) = 0; 1371 /// Whether dispose must always be called (returns false) 1372 GECODE_KERNEL_EXPORT 1373 virtual bool notice(void) const; 1374 /// Dispose 1375 virtual size_t dispose(Space& home); 1376 /// \name Internal management routines 1377 //@{ 1378 /// Test whether literal is a leaf 1379 bool leaf(void) const; 1380 /// Return pointer to next literal 1381 NGL* next(void) const; 1382 /// Mark literal as leaf or not 1383 void leaf(bool l); 1384 /// %Set pointer to next literal 1385 void next(NGL* n); 1386 /// Add node \a n and mark it as leaf \a l and return \a n 1387 NGL* add(NGL* n, bool l); 1388 //@} 1389 /// \name Memory management 1390 //@{ 1391 /// Allocate memory from space 1392 static void* operator new(size_t s, Space& home); 1393 /// Return memory to space 1394 static void operator delete(void* s, Space& home); 1395 /// Needed for exceptions 1396 static void operator delete(void* p); 1397 //@} 1398 public: 1399 /// To avoid warnings 1400 GECODE_KERNEL_EXPORT virtual ~NGL(void); 1401 /// Not used 1402 static void* operator new(size_t s); 1403 }; 1404 1405 /** 1406 * \brief %Choice for performing commit 1407 * 1408 * Must be refined by inheritance such that the information stored 1409 * inside a choice is sufficient to redo a commit performed by a 1410 * particular brancher. 1411 * 1412 * \ingroup TaskActor 1413 */ 1414 class GECODE_VTABLE_EXPORT Choice : public HeapAllocated { 1415 friend class Space; 1416 private: 1417 unsigned int bid; ///< Identity to match creating brancher 1418 unsigned int alt; ///< Number of alternatives 1419 1420 /// Return id of the creating brancher 1421 unsigned int id(void) const; 1422 protected: 1423 /// Initialize for particular brancher \a b and alternatives \a a 1424 Choice(const Brancher& b, const unsigned int a); 1425 public: 1426 /// Return number of alternatives 1427 unsigned int alternatives(void) const; 1428 /// Destructor 1429 GECODE_KERNEL_EXPORT virtual ~Choice(void); 1430 /// Archive into \a e 1431 GECODE_KERNEL_EXPORT 1432 virtual void archive(Archive& e) const; 1433 }; 1434 1435 /** 1436 * \brief Base-class for branchers 1437 * 1438 * Note that branchers cannot be created inside a propagator 1439 * (no idea why one would like to do that anyway). If you do that 1440 * the system will explode in a truly interesting way. 1441 * 1442 * \ingroup TaskActor 1443 */ 1444 class GECODE_VTABLE_EXPORT Brancher : public Actor { 1445 friend class ActorLink; 1446 friend class Space; 1447 friend class Choice; 1448 private: 1449 /// Unique brancher identity 1450 unsigned int bid; 1451 /// Group id 1452 unsigned int gid; 1453 /// Static cast for a non-null pointer (to give a hint to optimizer) 1454 static Brancher* cast(ActorLink* al); 1455 /// Static cast for a non-null pointer (to give a hint to optimizer) 1456 static const Brancher* cast(const ActorLink* al); 1457 protected: 1458 /// Constructor for creation 1459 Brancher(Home home); 1460 /// Constructor for cloning \a b 1461 Brancher(Space& home, Brancher& b); 1462 public: 1463 /// \name Brancher 1464 //@{ 1465 /** 1466 * \brief Check status of brancher, return true if alternatives left 1467 * 1468 * This method is called when Space::status is called, it determines 1469 * whether to continue branching with this brancher or move on to 1470 * the (possibly) next brancher. 1471 * 1472 */ 1473 virtual bool status(const Space& home) const = 0; 1474 /** 1475 * \brief Return choice 1476 * 1477 * Note that this method relies on the fact that it is called 1478 * immediately after a previous call to status. Moreover, the 1479 * member function can only be called once. 1480 */ 1481 virtual const Choice* choice(Space& home) = 0; 1482 /// Return choice from \a e 1483 virtual const Choice* choice(const Space& home, Archive& e) = 0; 1484 /** 1485 * \brief Commit for choice \a c and alternative \a a 1486 * 1487 * The current brancher in the space \a home performs a commit from 1488 * the information provided by the choice \a c and the alternative \a a. 1489 */ 1490 virtual ExecStatus commit(Space& home, const Choice& c, 1491 unsigned int a) = 0; 1492 /** 1493 * \brief Create no-good literal for choice \a c and alternative \a a 1494 * 1495 * The current brancher in the space \a home creates a no-good literal 1496 * from the information provided by the choice \a c and the alternative 1497 * \a a. The brancher has the following options: 1498 * - it returns nullptr for all alternatives \a a. This means that the 1499 * brancher does not support no-good literals (default). 1500 * - it returns nullptr for the last alternative \a a. This means that 1501 * this alternative is equivalent to the negation of the disjunction 1502 * of all other alternatives. 1503 * 1504 */ 1505 GECODE_KERNEL_EXPORT 1506 virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const; 1507 /** 1508 * \brief Print branch for choice \a c and alternative \a a 1509 * 1510 * Prints an explanation of the alternative \a a of choice \a c 1511 * on the stream \a o. 1512 * 1513 */ 1514 GECODE_KERNEL_EXPORT 1515 virtual void print(const Space& home, const Choice& c, unsigned int a, 1516 std::ostream& o) const; 1517 //@} 1518 /// \name Id and group support 1519 //@{ 1520 /// Return brancher id 1521 unsigned int id(void) const; 1522 /// Return group brancher belongs to 1523 BrancherGroup group(void) const; 1524 /// Add brancher to group \a g 1525 void group(BrancherGroup g); 1526 //@} 1527 }; 1528 1529 /** 1530 * \brief Local (space-shared) object 1531 * 1532 * Local objects must inherit from this base class. 1533 * 1534 */ 1535 class LocalObject : public Actor { 1536 friend class ActorLink; 1537 friend class Space; 1538 friend class LocalHandle; 1539 protected: 1540 /// Constructor for creation 1541 LocalObject(Home home); 1542 /// Copy constructor 1543 LocalObject(Space& home, LocalObject& l); 1544 /// Static cast for a non-null pointer (to give a hint to optimizer) 1545 static LocalObject* cast(ActorLink* al); 1546 /// Static cast for a non-null pointer (to give a hint to optimizer) 1547 static const LocalObject* cast(const ActorLink* al); 1548 private: 1549 /// Make copy and set forwarding pointer 1550 GECODE_KERNEL_EXPORT void fwdcopy(Space& home); 1551 public: 1552 /// Return forwarding pointer 1553 LocalObject* fwd(Space& home); 1554 }; 1555 1556 /** 1557 * \brief Handles for local (space-shared) objects 1558 * 1559 */ 1560 class LocalHandle { 1561 private: 1562 /// The local object 1563 LocalObject* o; 1564 protected: 1565 /// Create local handle pointing to nullptr object 1566 LocalHandle(void); 1567 /// Create local handle that points to local object \a lo 1568 LocalHandle(LocalObject* lo); 1569 /// Copy constructor 1570 LocalHandle(const LocalHandle& lh); 1571 public: 1572 /// Assignment operator 1573 LocalHandle& operator =(const LocalHandle& lh); 1574 /// Updating during cloning 1575 void update(Space& home, LocalHandle& lh); 1576 /// Destructor 1577 ~LocalHandle(void); 1578 protected: 1579 /// Access to the local object 1580 LocalObject* object(void) const; 1581 /// Modify local object 1582 void object(LocalObject* n); 1583 }; 1584 1585 1586 /** 1587 * \brief No-goods recorded from restarts 1588 * 1589 */ 1590 class GECODE_VTABLE_EXPORT NoGoods { 1591 protected: 1592 /// Number of no-goods 1593 unsigned long int n; 1594 public: 1595 /// Initialize 1596 NoGoods(void); 1597 /// Post no-goods 1598 GECODE_KERNEL_EXPORT 1599 virtual void post(Space& home) const; 1600 /// Return number of no-goods posted 1601 unsigned long int ng(void) const; 1602 /// %Set number of no-goods posted to \a n 1603 void ng(unsigned long int n); 1604 /// Destructor 1605 virtual ~NoGoods(void); 1606 /// Empty no-goods 1607 GECODE_KERNEL_EXPORT 1608 static NoGoods eng; 1609 }; 1610 1611 /** 1612 * \brief Information passed by meta search engines 1613 * 1614 */ 1615 class GECODE_VTABLE_EXPORT MetaInfo { 1616 public: 1617 /// Which type of information is provided 1618 enum Type { 1619 /// Information is provided by a restart-based engine 1620 RESTART, 1621 /// Information is provided by a portfolio-based engine 1622 PORTFOLIO 1623 }; 1624 protected: 1625 /// Type of information 1626 const Type t; 1627 /// \name Restart-based information 1628 //@{ 1629 /// Number of restarts 1630 const unsigned long int r; 1631 /// Number of solutions since last restart 1632 const unsigned long long int s; 1633 /// Number of failures since last restart 1634 const unsigned long long int f; 1635 /// Last solution found 1636 const Space* l; 1637 /// No-goods from restart 1638 const NoGoods& ng; 1639 //@} 1640 /// \name Portfolio-based information 1641 //@{ 1642 /// Number of asset in portfolio 1643 const unsigned int a; 1644 //@} 1645 public: 1646 /// \name Constructors depending on type of engine 1647 //@{ 1648 /// Constructor for restart-based engine 1649 MetaInfo(unsigned long int r, 1650 unsigned long long int s, 1651 unsigned long long int f, 1652 const Space* l, 1653 NoGoods& ng); 1654 /// Constructor for portfolio-based engine 1655 MetaInfo(unsigned int a); 1656 //@} 1657 /// Return type of information 1658 Type type(void) const; 1659 /// \name Restart-based information 1660 //@{ 1661 /// Return number of restarts 1662 unsigned long int restart(void) const; 1663 /// Return number of solutions since last restart 1664 unsigned long long int solution(void) const; 1665 /// Return number of failures since last restart 1666 unsigned long long int fail(void) const; 1667 /// Return last solution found (possibly nullptr) 1668 const Space* last(void) const; 1669 /// Return no-goods recorded from restart 1670 const NoGoods& nogoods(void) const; 1671 //@} 1672 /// \name Portfolio-based information 1673 //@{ 1674 /// Return number of asset in portfolio 1675 unsigned int asset(void) const; 1676 //@} 1677 }; 1678 1679 /** 1680 * \brief %Space status 1681 * \ingroup TaskSearch 1682 */ 1683 enum SpaceStatus { 1684 SS_FAILED, ///< %Space is failed 1685 SS_SOLVED, ///< %Space is solved (no brancher left) 1686 SS_BRANCH ///< %Space must be branched (at least one brancher left) 1687 }; 1688 1689 /** 1690 * \brief %Statistics for execution of status 1691 * 1692 */ 1693 class StatusStatistics { 1694 public: 1695 /// Number of propagator executions 1696 unsigned long long int propagate; 1697 /// Initialize 1698 StatusStatistics(void); 1699 /// Reset information 1700 void reset(void); 1701 /// Return sum with \a s 1702 StatusStatistics operator +(const StatusStatistics& s); 1703 /// Increment by statistics \a s 1704 StatusStatistics& operator +=(const StatusStatistics& s); 1705 }; 1706 1707 /** 1708 * \brief %Statistics for execution of clone 1709 * 1710 */ 1711 class CloneStatistics { 1712 public: 1713 /// Initialize 1714 CloneStatistics(void); 1715 /// Reset information 1716 void reset(void); 1717 /// Return sum with \a s 1718 CloneStatistics operator +(const CloneStatistics& s); 1719 /// Increment by statistics \a s 1720 CloneStatistics& operator +=(const CloneStatistics& s); 1721 }; 1722 1723 /** 1724 * \brief %Statistics for execution of commit 1725 * 1726 */ 1727 class CommitStatistics { 1728 public: 1729 /// Initialize 1730 CommitStatistics(void); 1731 /// Reset information 1732 void reset(void); 1733 /// Return sum with \a s 1734 CommitStatistics operator +(const CommitStatistics& s); 1735 /// Increment by statistics \a s 1736 CommitStatistics& operator +=(const CommitStatistics& s); 1737 }; 1738 1739 1740 1741 /** 1742 * \brief Computation spaces 1743 */ 1744 class GECODE_VTABLE_EXPORT Space : public HeapAllocated { 1745 friend class Actor; 1746 friend class Propagator; 1747 friend class PropagatorGroup; 1748 friend class Propagators; 1749 friend class Brancher; 1750 friend class BrancherGroup; 1751 friend class Branchers; 1752 friend class Advisor; 1753 template <class A> friend class Council; 1754 template<class VIC> friend class VarImp; 1755 template<class VarImp> friend class VarImpDisposer; 1756 friend class LocalObject; 1757 friend class Region; 1758 friend class AFC; 1759 friend class PostInfo; 1760 friend GECODE_KERNEL_EXPORT 1761 void trace(Home home, TraceFilter tf, int te, Tracer& t); 1762 private: 1763 /// Shared data for space 1764 Kernel::SharedSpaceData ssd; 1765 /// Performs memory management for space 1766 Kernel::MemoryManager mm; 1767 #ifdef GECODE_HAS_CBS 1768 /// Global counter for variable ids 1769 unsigned int var_id_counter; 1770 #endif 1771 /// Doubly linked list of all propagators 1772 ActorLink pl; 1773 /// Doubly linked list of all branchers 1774 ActorLink bl; 1775 /** 1776 * \brief Points to the first brancher to be used for status 1777 * 1778 * If equal to &bl, no brancher does exist. 1779 */ 1780 Brancher* b_status; 1781 /** 1782 * \brief Points to the first brancher to be used for commit 1783 * 1784 * Note that \a b_commit can point to an earlier brancher 1785 * than \a b_status. This reflects the fact that the earlier 1786 * brancher is already done (that is, status on that brancher 1787 * returns false) but there might be still choices 1788 * referring to the earlier brancher. 1789 * 1790 * If equal to &bl, no brancher does exist. 1791 */ 1792 Brancher* b_commit; 1793 /// Find brancher with identity \a id 1794 Brancher* brancher(unsigned int id); 1795 1796 /// Kill brancher \a b 1797 void kill(Brancher& b); 1798 /// Kill propagator \a p 1799 void kill(Propagator& p); 1800 1801 /// Kill brancher with identity \a id 1802 GECODE_KERNEL_EXPORT 1803 void kill_brancher(unsigned int id); 1804 1805 /// Reserved brancher id (never created) 1806 static const unsigned reserved_bid = 0U; 1807 1808 /// Number of bits for status control 1809 static const unsigned int sc_bits = 2; 1810 /// No special features activated 1811 static const unsigned int sc_fast = 0; 1812 /// Disabled propagators are supported 1813 static const unsigned int sc_disabled = 1; 1814 /// Tracing is supported 1815 static const unsigned int sc_trace = 2; 1816 1817 union { 1818 /// Data only available during propagation or branching 1819 struct { 1820 /** 1821 * \brief Cost level with next propagator to be executed 1822 * 1823 * This maintains the following invariant (but only if the 1824 * space does not perform propagation): 1825 * - If active points to a queue, this queue might contain 1826 * a propagator. However, there will be at least one queue 1827 * containing a propagator. 1828 * - Otherwise, active is smaller than the first queue 1829 * or larger than the last queue. Then, the space is stable. 1830 * - If active is larger than the last queue, the space is failed. 1831 */ 1832 ActorLink* active; 1833 /// Scheduled propagators according to cost 1834 ActorLink queue[PropCost::AC_MAX+1]; 1835 /** 1836 * \brief Id of next brancher to be created plus status control 1837 * 1838 * The last two bits are reserved for status control. 1839 * 1840 */ 1841 unsigned int bid_sc; 1842 /// Number of subscriptions 1843 unsigned int n_sub; 1844 /// View trace information 1845 ViewTraceInfo vti; 1846 } p; 1847 /// Data available only during copying 1848 struct { 1849 /// Entries for updating variables 1850 VarImpBase* vars_u[AllVarConf::idx_c]; 1851 /// Keep variables during copying without index structure 1852 VarImpBase* vars_noidx; 1853 /// Linked list of local objects 1854 LocalObject* local; 1855 } c; 1856 } pc; 1857 /// Put propagator \a p into right queue 1858 void enqueue(Propagator* p); 1859 /** 1860 * \name update, and dispose variables 1861 */ 1862 //@{ 1863 #ifdef GECODE_HAS_VAR_DISPOSE 1864 /// Registered variable type disposers 1865 GECODE_KERNEL_EXPORT static VarImpDisposerBase* vd[AllVarConf::idx_d]; 1866 /// Entries for disposing variables 1867 VarImpBase* _vars_d[AllVarConf::idx_d]; 1868 /// Return reference to variables (dispose) 1869 template<class VIC> VarImpBase* vars_d(void) const; 1870 /// %Set reference to variables (dispose) 1871 template<class VIC> void vars_d(VarImpBase* x); 1872 #endif 1873 /// Update all cloned variables 1874 void update(ActorLink** sub); 1875 //@} 1876 1877 /// First actor for forced disposal 1878 Actor** d_fst; 1879 /// Current actor for forced disposal 1880 Actor** d_cur; 1881 /// Last actor for forced disposal 1882 Actor** d_lst; 1883 1884 /// Used for default argument 1885 GECODE_KERNEL_EXPORT static StatusStatistics unused_status; 1886 /// Used for default argument 1887 GECODE_KERNEL_EXPORT static CloneStatistics unused_clone; 1888 /// Used for default argument 1889 GECODE_KERNEL_EXPORT static CommitStatistics unused_commit; 1890 1891 /** 1892 * \brief Clone space 1893 * 1894 * Assumes that the space is stable and not failed. If the space is 1895 * failed, an exception of type SpaceFailed is thrown. If the space 1896 * is not stable, an exception of SpaceNotStable is thrown. 1897 * 1898 * Otherwise, a clone of the space is returned. 1899 * 1900 * Throws an exception of type SpaceNotCloned when the copy constructor 1901 * of the Space class is not invoked during cloning. 1902 * 1903 */ 1904 GECODE_KERNEL_EXPORT Space* _clone(void); 1905 1906 /** 1907 * \brief Commit choice \a c for alternative \a a 1908 * 1909 * The current brancher in the space performs a commit from 1910 * the information provided by the choice \a c 1911 * and the alternative \a a. The statistics information \a stat is 1912 * updated. 1913 * 1914 * Note that no propagation is perfomed (to support path 1915 * recomputation), in order to perform propagation the member 1916 * function status must be used. 1917 * 1918 * Committing with choices must be carried 1919 * out in the same order as the choices have been 1920 * obtained by the member function Space::choice(). 1921 * 1922 * It is perfectly okay to add constraints interleaved with 1923 * choices (provided they are in the right order). 1924 * However, if propagation is performed by calling the member 1925 * function status and then new choices are 1926 * computed, these choices are different. 1927 * 1928 * Only choices can be used that are up-to-date in the following 1929 * sense: if a new choice is created (via the choice member 1930 * function), no older choices can be used. 1931 * 1932 * Committing throws the following exceptions: 1933 * - SpaceNoBrancher, if the space has no current brancher (it is 1934 * already solved). 1935 * - SpaceIllegalAlternative, if \a a is not smaller than the number 1936 * of alternatives supported by the choice \a c. 1937 */ 1938 GECODE_KERNEL_EXPORT 1939 void _commit(const Choice& c, unsigned int a); 1940 1941 /** 1942 * \brief Commit choice \a c for alternative \a a if possible 1943 * 1944 * The current brancher in the space performs a commit from 1945 * the information provided by the choice \a c 1946 * and the alternative \a a. The statistics information \a stat is 1947 * updated. 1948 * 1949 * Note that no propagation is perfomed (to support path 1950 * recomputation), in order to perform propagation the member 1951 * function status must be used. 1952 * 1953 * Committing with choices must be carried 1954 * out in the same order as the choices have been 1955 * obtained by the member function Space::choice(). 1956 * 1957 * It is perfectly okay to add constraints interleaved with 1958 * choices (provided they are in the right order). 1959 * However, if propagation is performed by calling the member 1960 * function status and then new choices are 1961 * computed, these choices are different. 1962 * 1963 * Only choices can be used that are up-to-date in the following 1964 * sense: if a new choice is created (via the choice member 1965 * function), no older choices can be used. 1966 * 1967 * Committing throws the following exceptions: 1968 * - SpaceIllegalAlternative, if \a a is not smaller than the number 1969 * of alternatives supported by the choice \a c. 1970 */ 1971 GECODE_KERNEL_EXPORT 1972 void _trycommit(const Choice& c, unsigned int a); 1973 1974 /// Find trace recorder if exists 1975 GECODE_KERNEL_EXPORT 1976 TraceRecorder* findtracerecorder(void); 1977 /// Trace posting event 1978 GECODE_KERNEL_EXPORT 1979 void post(const PostInfo& pi); 1980 1981 /** 1982 * \brief Notice that an actor must be disposed 1983 * 1984 * Note that \a a might be a marked pointer where the mark 1985 * indicates that \a a is a trace recorder. 1986 */ 1987 GECODE_KERNEL_EXPORT 1988 void ap_notice_dispose(Actor* a, bool d); 1989 /** 1990 * \brief Ignore that an actor must be disposed 1991 * 1992 * Note that \a a might be a marked pointer where the mark 1993 * indicates that \a a is a trace recorder. 1994 */ 1995 GECODE_KERNEL_EXPORT 1996 void ap_ignore_dispose(Actor* a, bool d); 1997 public: 1998 /** 1999 * \brief Default constructor 2000 * \ingroup TaskModelScript 2001 */ 2002 GECODE_KERNEL_EXPORT 2003 Space(void); 2004 /** 2005 * \brief Constructor for cloning 2006 * 2007 * Must copy and update all data structures (such as variables 2008 * and variable arrays) required by the subclass of Space. 2009 * 2010 * Should not be used directly, use Space::clone to create a clone 2011 * of a Space. 2012 * 2013 * \ingroup TaskModelScript 2014 */ 2015 GECODE_KERNEL_EXPORT 2016 Space(Space& s); 2017 /// Assignment operator 2018 Space& operator =(const Space& s) = default; 2019 /** 2020 * \brief Destructor 2021 * \ingroup TaskModelScript 2022 */ 2023 GECODE_KERNEL_EXPORT 2024 virtual ~Space(void); 2025 /** 2026 * \brief Copying member function 2027 * 2028 * Must create a new object using the constructor for cloning. 2029 * 2030 * Should not be used directly, use Space::clone to create a clone 2031 * of a Space. 2032 * 2033 * \ingroup TaskModelScript 2034 */ 2035 virtual Space* copy(void) = 0; 2036 /** 2037 * \brief Constrain function for best solution search 2038 * 2039 * Must constrain this space to be better than the so far best 2040 * solution \a best. 2041 * 2042 * The default function does nothing. 2043 * 2044 * \ingroup TaskModelScript 2045 */ 2046 GECODE_KERNEL_EXPORT virtual void constrain(const Space& best); 2047 /** 2048 * \brief Master configuration function for meta search engines 2049 * 2050 * This configuration function is used by both restart and 2051 * portfolio meta search engines. 2052 * 2053 * \li A restart meta search engine calls this function on its 2054 * master space whenever it finds a solution or exploration 2055 * restarts. \a mi contains information about the current restart. 2056 * 2057 * If a solution has been found, then search will continue with 2058 * a restart id the function returns true, otherwise search 2059 * will continue. 2060 * 2061 * The default function posts no-goods obtained from \a mi. 2062 * 2063 * \li A portfolio meta engine calls this function once on 2064 * the master space. The return value is ignored. 2065 * 2066 * The default function does nothing. 2067 * 2068 * \ingroup TaskModelScript 2069 */ 2070 GECODE_KERNEL_EXPORT 2071 virtual bool master(const MetaInfo& mi); 2072 /** 2073 * \brief Slave configuration function for meta search engines 2074 * 2075 * This configuration function is used by both restart and 2076 * portfolio meta search engines. 2077 * 2078 * \li A restart meta search engine calls this function on its 2079 * slave space whenever it finds a solution or exploration 2080 * restarts. \a mi contains information about the current restart. 2081 * 2082 * If the function returns true, the search on the slave space is 2083 * considered complete, i.e., if it fails or exhaustively explores the 2084 * entire search space, the meta search engine finishes. If the 2085 * function returns false, the search on the slave space is considered 2086 * incomplete, and the meta engine will restart the search regardless 2087 * of whether the search on the slave space finishes or times out. 2088 * 2089 * \li A portfolio meta engine calls this function once on each asset 2090 * (that is, on each slave) and passes the number of the asset, 2091 * starting from zero. 2092 * 2093 * The default function does nothing and returns true. 2094 * 2095 * \ingroup TaskModelScript 2096 */ 2097 GECODE_KERNEL_EXPORT 2098 virtual bool slave(const MetaInfo& mi); 2099 2100 /* 2101 * Member functions for search engines 2102 * 2103 */ 2104 2105 /** 2106 * \brief Query space status 2107 * 2108 * Propagates the space until fixpoint or failure; 2109 * updates the statistics information \a stat; and: 2110 * - if the space is failed, SpaceStatus::SS_FAILED is returned. 2111 * - if the space is not failed but the space has no brancher left, 2112 * SpaceStatus::SS_SOLVED is returned. 2113 * - otherwise, SpaceStatus::SS_BRANCH is returned. 2114 * \ingroup TaskSearch 2115 */ 2116 GECODE_KERNEL_EXPORT 2117 SpaceStatus status(StatusStatistics& stat=unused_status); 2118 2119 /** 2120 * \brief Create new choice for current brancher 2121 * 2122 * This member function can only be called after the member function 2123 * Space::status on the same space has been called and in between 2124 * no non-const member function has been called on this space. 2125 * 2126 * Moreover, the member function can only be called at most once 2127 * (otherwise, it might generate conflicting choices). 2128 * 2129 * Note that the above invariant only pertains to calls of member 2130 * functions of the same space. If the invariant is violated, the 2131 * system is likely to crash (hopefully it does). In particular, if 2132 * applied to a space with no current brancher, the system will 2133 * crash. 2134 * 2135 * After a new choice has been created, no older choices 2136 * can be used on the space. 2137 * 2138 * If the status() member function has returned that the space has 2139 * no more branchers (that is, the result was either SS_FAILED or 2140 * SS_SOLVED), a call to choice() will return nullptr and purge 2141 * all remaining branchers inside the space. This is interesting 2142 * for the case SS_SOLVED, where the call to choice can serve as 2143 * garbage collection. 2144 * 2145 * Throws an exception of type SpaceNotStable when applied to a not 2146 * yet stable space. 2147 * 2148 * \ingroup TaskSearch 2149 */ 2150 GECODE_KERNEL_EXPORT 2151 const Choice* choice(void); 2152 2153 /** 2154 * \brief Create new choice from \a e 2155 * 2156 * The archived representation \a e must have been created from 2157 * a Choice that is compatible with this space (i.e., created from 2158 * the same model). 2159 * 2160 * \ingroup TaskSearch 2161 */ 2162 GECODE_KERNEL_EXPORT 2163 const Choice* choice(Archive& e) const; 2164 2165 /** 2166 * \brief Clone space 2167 * 2168 * Assumes that the space is stable and not failed. If the space is 2169 * failed, an exception of type SpaceFailed is thrown. If the space 2170 * is not stable, an exception of SpaceNotStable is thrown. 2171 * 2172 * Otherwise, a clone of the space is returned and the statistics 2173 * information \a stat is updated. 2174 * 2175 * Throws an exception of type SpaceNotCloned when the copy constructor 2176 * of the Space class is not invoked during cloning. 2177 * 2178 * \ingroup TaskSearch 2179 */ 2180 Space* clone(CloneStatistics& stat=unused_clone) const; 2181 2182 /** 2183 * \brief Commit choice \a c for alternative \a a 2184 * 2185 * The current brancher in the space performs a commit from 2186 * the information provided by the choice \a c 2187 * and the alternative \a a. The statistics information \a stat is 2188 * updated. 2189 * 2190 * Note that no propagation is perfomed (to support path 2191 * recomputation), in order to perform propagation the member 2192 * function status must be used. 2193 * 2194 * Committing with choices must be carried 2195 * out in the same order as the choices have been 2196 * obtained by the member function Space::choice(). 2197 * 2198 * It is perfectly okay to add constraints interleaved with 2199 * choices (provided they are in the right order). 2200 * However, if propagation is performed by calling the member 2201 * function status and then new choices are 2202 * computed, these choices are different. 2203 * 2204 * Only choices can be used that are up-to-date in the following 2205 * sense: if a new choice is created (via the choice member 2206 * function), no older choices can be used. 2207 * 2208 * Committing throws the following exceptions: 2209 * - SpaceNoBrancher, if the space has no current brancher (it is 2210 * already solved). 2211 * - SpaceIllegalAlternative, if \a a is not smaller than the number 2212 * of alternatives supported by the choice \a c. 2213 * 2214 * \ingroup TaskSearch 2215 */ 2216 void commit(const Choice& c, unsigned int a, 2217 CommitStatistics& stat=unused_commit); 2218 /** 2219 * \brief If possible, commit choice \a c for alternative \a a 2220 * 2221 * The current brancher in the space performs a commit from 2222 * the information provided by the choice \a c 2223 * and the alternative \a a. The statistics information \a stat is 2224 * updated. 2225 * 2226 * Note that no propagation is perfomed (to support path 2227 * recomputation), in order to perform propagation the member 2228 * function status must be used. 2229 * 2230 * Committing with choices must be carried 2231 * out in the same order as the choices have been 2232 * obtained by the member function Space::choice(). 2233 * 2234 * It is perfectly okay to add constraints interleaved with 2235 * choices (provided they are in the right order). 2236 * However, if propagation is performed by calling the member 2237 * function status and then new choices are 2238 * computed, these choices are different. 2239 * 2240 * Only choices can be used that are up-to-date in the following 2241 * sense: if a new choice is created (via the choice member 2242 * function), no older choices can be used. 2243 * 2244 * Committing throws the following exceptions: 2245 * - SpaceIllegalAlternative, if \a a is not smaller than the number 2246 * of alternatives supported by the choice \a c. 2247 * 2248 * \ingroup TaskSearch 2249 */ 2250 void trycommit(const Choice& c, unsigned int a, 2251 CommitStatistics& stat=unused_commit); 2252 /** 2253 * \brief Create no-good literal for choice \a c and alternative \a a 2254 * 2255 * The current brancher in the space \a home creates a no-good literal 2256 * from the information provided by the choice \a c and the alternative 2257 * \a a. The brancher has the following options: 2258 * - it returns nullptr for all alternatives \a a. This means that the 2259 * brancher does not support no-good literals. 2260 * - it returns nullptr for the last alternative \a a. This means that 2261 * this alternative is equivalent to the negation of the disjunction 2262 * of all other alternatives. 2263 * 2264 * It throws the following exceptions: 2265 * - SpaceIllegalAlternative, if \a a is not smaller than the number 2266 * of alternatives supported by the choice \a c. 2267 * 2268 * \ingroup TaskSearch 2269 */ 2270 GECODE_KERNEL_EXPORT 2271 NGL* ngl(const Choice& c, unsigned int a); 2272 2273 /** 2274 * \brief Print branch for choice \a c and alternative \a a 2275 * 2276 * Prints an explanation of the alternative \a a of choice \a c 2277 * on the stream \a o. 2278 * 2279 * Print throws the following exceptions: 2280 * - SpaceNoBrancher, if the space has no current brancher (it is 2281 * already solved). 2282 * - SpaceIllegalAlternative, if \a a is not smaller than the number 2283 * of alternatives supported by the choice \a c. 2284 * 2285 * \ingroup TaskSearch 2286 */ 2287 GECODE_KERNEL_EXPORT 2288 void print(const Choice& c, unsigned int a, std::ostream& o) const; 2289 2290 /** 2291 * \brief Notice actor property 2292 * 2293 * Make the space notice that the actor \a a has the property \a p. 2294 * Note that the same property can only be noticed once for an actor 2295 * unless \a duplicate is true. 2296 * \ingroup TaskActor 2297 */ 2298 GECODE_KERNEL_EXPORT 2299 void notice(Actor& a, ActorProperty p, bool duplicate=false); 2300 /** 2301 * \brief Ignore actor property 2302 * 2303 * Make the space ignore that the actor \a a has the property \a p. 2304 * Note that a property must be ignored before an actor is disposed. 2305 * \ingroup TaskActor 2306 */ 2307 GECODE_KERNEL_EXPORT 2308 void ignore(Actor& a, ActorProperty p, bool duplicate=false); 2309 2310 2311 /** 2312 * \brief %Propagator \a p is subsumed 2313 * 2314 * First disposes the propagator and then returns subsumption. 2315 * 2316 * \warning Has a side-effect on the propagator. Overwrites 2317 * the modification event delta of a propagator. 2318 * Use only directly with returning from propagation. 2319 * \ingroup TaskActorStatus 2320 */ 2321 ExecStatus ES_SUBSUMED(Propagator& p); 2322 /** 2323 * \brief %Propagator \a p is subsumed 2324 * 2325 * The size of the propagator is \a s. 2326 * 2327 * Note that the propagator must be subsumed and also disposed. So 2328 * in general, there should be code such as 2329 * \code return ES_SUBSUMED_DISPOSE(home,*this,dispose(home)) \endcode. 2330 * 2331 * \warning Has a side-effect on the propagator. Overwrites 2332 * the modification event delta of a propagator. 2333 * Use only directly with returning from propagation. 2334 * \ingroup TaskActorStatus 2335 */ 2336 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p, size_t s); 2337 /** 2338 * \brief %Propagator \a p has computed partial fixpoint 2339 * 2340 * %Set modification event delta to \a med and schedule propagator 2341 * accordingly. 2342 * 2343 * \warning Has a side-effect on the propagator. 2344 * Use only directly with returning from propagation. 2345 * \ingroup TaskActorStatus 2346 */ 2347 ExecStatus ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med); 2348 /** 2349 * \brief %Propagator \a p has not computed partial fixpoint 2350 * 2351 * Combine current modification event delta with \a and schedule 2352 * propagator accordingly. 2353 * 2354 * \warning Has a side-effect on the propagator. 2355 * Use only directly with returning from propagation. 2356 * \ingroup TaskActorStatus 2357 */ 2358 ExecStatus ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med); 2359 2360 /** 2361 * \brief %Advisor \a a must be disposed 2362 * 2363 * Disposes the advisor and returns that the propagator of \a a 2364 * need not be run. 2365 * 2366 * \warning Has a side-effect on the advisor. Use only directly when 2367 * returning from advise. 2368 * \ingroup TaskActorStatus 2369 */ 2370 template<class A> 2371 ExecStatus ES_FIX_DISPOSE(Council<A>& c, A& a); 2372 /** 2373 * \brief %Advisor \a a must be disposed and its propagator must be run 2374 * 2375 * Disposes the advisor and returns that the propagator of \a a 2376 * must be run. 2377 * 2378 * \warning Has a side-effect on the advisor. Use only directly when 2379 * returning from advise. 2380 * \ingroup TaskActorStatus 2381 */ 2382 template<class A> 2383 ExecStatus ES_NOFIX_DISPOSE(Council<A>& c, A& a); 2384 /** 2385 * \brief %Advisor \a a must be disposed and its propagator must be forcefully rescheduled 2386 * 2387 * Disposes the advisor and returns that the propagator of \a a 2388 * must be run and must be forcefully rescheduled (including 2389 * recomputation of cost). 2390 * 2391 * \warning Has a side-effect on the advisor. Use only directly when 2392 * returning from advise. 2393 * \ingroup TaskActorStatus 2394 */ 2395 template<class A> 2396 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a); 2397 2398 /** 2399 * \brief Fail space 2400 * 2401 * This is useful for failing outside of actors. Never use inside 2402 * a propagate or commit member function. The system will crash! 2403 * \ingroup TaskActor 2404 */ 2405 void fail(void); 2406 /** 2407 * \brief Check whether space is failed 2408 * 2409 * Note that this does not perform propagation. This is useful 2410 * for posting actors: only if a space is not yet failed, new 2411 * actors are allowed to be created. 2412 * \ingroup TaskActor 2413 */ 2414 bool failed(void) const; 2415 /** 2416 * \brief Return if space is stable (at fixpoint or failed) 2417 * \ingroup TaskActor 2418 */ 2419 bool stable(void) const; 2420 2421 /// \name Conversion from Space to Home 2422 //@{ 2423 /// Return a home for this space with the information that \a p is being rewritten 2424 Home operator ()(Propagator& p); 2425 /// Return a home for this space with propagator group information \a pg 2426 Home operator ()(PropagatorGroup pg); 2427 /// Return a home for this space with brancher group information \a bg 2428 Home operator ()(BrancherGroup bg); 2429 //@} 2430 2431 /** 2432 * \defgroup FuncMemSpace Space-memory management 2433 * \ingroup FuncMem 2434 */ 2435 //@{ 2436 /** 2437 * \brief Allocate block of \a n objects of type \a T from space heap 2438 * 2439 * Note that this function implements C++ semantics: the default 2440 * constructor of \a T is run for all \a n objects. 2441 */ 2442 template<class T> 2443 T* alloc(long unsigned int n); 2444 /** 2445 * \brief Allocate block of \a n objects of type \a T from space heap 2446 * 2447 * Note that this function implements C++ semantics: the default 2448 * constructor of \a T is run for all \a n objects. 2449 */ 2450 template<class T> 2451 T* alloc(long int n); 2452 /** 2453 * \brief Allocate block of \a n objects of type \a T from space heap 2454 * 2455 * Note that this function implements C++ semantics: the default 2456 * constructor of \a T is run for all \a n objects. 2457 */ 2458 template<class T> 2459 T* alloc(unsigned int n); 2460 /** 2461 * \brief Allocate block of \a n objects of type \a T from space heap 2462 * 2463 * Note that this function implements C++ semantics: the default 2464 * constructor of \a T is run for all \a n objects. 2465 */ 2466 template<class T> 2467 T* alloc(int n); 2468 /** 2469 * \brief Delete \a n objects allocated from space heap starting at \a b 2470 * 2471 * Note that this function implements C++ semantics: the destructor 2472 * of \a T is run for all \a n objects. 2473 * 2474 * Note that the memory is not freed, it is just scheduled for later 2475 * reusal. 2476 */ 2477 template<class T> 2478 void free(T* b, long unsigned int n); 2479 /** 2480 * \brief Delete \a n objects allocated from space heap starting at \a b 2481 * 2482 * Note that this function implements C++ semantics: the destructor 2483 * of \a T is run for all \a n objects. 2484 * 2485 * Note that the memory is not freed, it is just scheduled for later 2486 * reusal. 2487 */ 2488 template<class T> 2489 void free(T* b, long int n); 2490 /** 2491 * \brief Delete \a n objects allocated from space heap starting at \a b 2492 * 2493 * Note that this function implements C++ semantics: the destructor 2494 * of \a T is run for all \a n objects. 2495 * 2496 * Note that the memory is not freed, it is just scheduled for later 2497 * reusal. 2498 */ 2499 template<class T> 2500 void free(T* b, unsigned int n); 2501 /** 2502 * \brief Delete \a n objects allocated from space heap starting at \a b 2503 * 2504 * Note that this function implements C++ semantics: the destructor 2505 * of \a T is run for all \a n objects. 2506 * 2507 * Note that the memory is not freed, it is just scheduled for later 2508 * reusal. 2509 */ 2510 template<class T> 2511 void free(T* b, int n); 2512 /** 2513 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap 2514 * 2515 * Note that this function implements C++ semantics: the copy constructor 2516 * of \a T is run for all \f$\min(n,m)\f$ objects, the default 2517 * constructor of \a T is run for all remaining 2518 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is 2519 * run for all \a n objects in \a b. 2520 * 2521 * Returns the address of the new block. 2522 */ 2523 template<class T> 2524 T* realloc(T* b, long unsigned int n, long unsigned int m); 2525 /** 2526 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap 2527 * 2528 * Note that this function implements C++ semantics: the copy constructor 2529 * of \a T is run for all \f$\min(n,m)\f$ objects, the default 2530 * constructor of \a T is run for all remaining 2531 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is 2532 * run for all \a n objects in \a b. 2533 * 2534 * Returns the address of the new block. 2535 */ 2536 template<class T> 2537 T* realloc(T* b, long int n, long int m); 2538 /** 2539 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap 2540 * 2541 * Note that this function implements C++ semantics: the copy constructor 2542 * of \a T is run for all \f$\min(n,m)\f$ objects, the default 2543 * constructor of \a T is run for all remaining 2544 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is 2545 * run for all \a n objects in \a b. 2546 * 2547 * Returns the address of the new block. 2548 */ 2549 template<class T> 2550 T* realloc(T* b, unsigned int n, unsigned int m); 2551 /** 2552 * \brief Reallocate block of \a n objects starting at \a b to \a m objects of type \a T from the space heap 2553 * 2554 * Note that this function implements C++ semantics: the copy constructor 2555 * of \a T is run for all \f$\min(n,m)\f$ objects, the default 2556 * constructor of \a T is run for all remaining 2557 * \f$\max(n,m)-\min(n,m)\f$ objects, and the destrucor of \a T is 2558 * run for all \a n objects in \a b. 2559 * 2560 * Returns the address of the new block. 2561 */ 2562 template<class T> 2563 T* realloc(T* b, int n, int m); 2564 /** 2565 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap 2566 * 2567 * Returns the address of the new block. 2568 * 2569 * This is a specialization for performance. 2570 */ 2571 template<class T> 2572 T** realloc(T** b, long unsigned int n, long unsigned int m); 2573 /** 2574 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap 2575 * 2576 * Returns the address of the new block. 2577 * 2578 * This is a specialization for performance. 2579 */ 2580 template<class T> 2581 T** realloc(T** b, long int n, long int m); 2582 /** 2583 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap 2584 * 2585 * Returns the address of the new block. 2586 * 2587 * This is a specialization for performance. 2588 */ 2589 template<class T> 2590 T** realloc(T** b, unsigned int n, unsigned int m); 2591 /** 2592 * \brief Reallocate block of \a n pointers starting at \a b to \a m objects of type \a T* from the space heap 2593 * 2594 * Returns the address of the new block. 2595 * 2596 * This is a specialization for performance. 2597 */ 2598 template<class T> 2599 T** realloc(T** b, int n, int m); 2600 /// Allocate memory on space heap 2601 void* ralloc(size_t s); 2602 /// Free memory previously allocated with alloc (might be reused later) 2603 void rfree(void* p, size_t s); 2604 /// Reallocate memory block starting at \a b from size \a n to size \a s 2605 void* rrealloc(void* b, size_t n, size_t m); 2606 /// Allocate from freelist-managed memory 2607 template<size_t> void* fl_alloc(void); 2608 /** 2609 * \brief Return freelist-managed memory to freelist 2610 * 2611 * The first list element to be retuned is \a f, the last is \a l. 2612 */ 2613 template<size_t> void fl_dispose(FreeList* f, FreeList* l); 2614 //@} 2615 /// Construction routines 2616 //@{ 2617 /** 2618 * \brief Constructs a single object of type \a T from space heap using the default constructor. 2619 */ 2620 template<class T> 2621 T& construct(void); 2622 /** 2623 * \brief Constructs a single object of type \a T from space heap using a unary constructor. 2624 * 2625 * The parameter is passed as a const reference. 2626 */ 2627 template<class T, typename A1> 2628 T& construct(A1 const& a1); 2629 /** 2630 * \brief Constructs a single object of type \a T from space heap using a binary constructor. 2631 * 2632 * The parameters are passed as const references. 2633 */ 2634 template<class T, typename A1, typename A2> 2635 T& construct(A1 const& a1, A2 const& a2); 2636 /** 2637 * \brief Constructs a single object of type \a T from space heap using a ternary constructor. 2638 * 2639 * The parameters are passed as const references. 2640 */ 2641 template<class T, typename A1, typename A2, typename A3> 2642 T& construct(A1 const& a1, A2 const& a2, A3 const& a3); 2643 /** 2644 * \brief Constructs a single object of type \a T from space heap using a quaternary constructor. 2645 * 2646 * The parameters are passed as const references. 2647 */ 2648 template<class T, typename A1, typename A2, typename A3, typename A4> 2649 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4); 2650 /** 2651 * \brief Constructs a single object of type \a T from space heap using a quinary constructor. 2652 * 2653 * The parameters are passed as const references. 2654 */ 2655 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5> 2656 T& construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5); 2657 //@} 2658 2659 /// \name Low-level support for AFC 2660 //@{ 2661 /// %Set AFC decay factor to \a d 2662 void afc_decay(double d); 2663 /// Return AFC decay factor 2664 double afc_decay(void) const; 2665 /// Unshare AFC information for all propagators 2666 GECODE_KERNEL_EXPORT void afc_unshare(void); 2667 //@} 2668 2669 protected: 2670 /** 2671 * \brief Class to iterate over propagators of a space 2672 * 2673 * Note that the iterator cannot be used during cloning. 2674 */ 2675 class Propagators { 2676 private: 2677 /// Current space 2678 Space& home; 2679 /// Current queue 2680 ActorLink* q; 2681 /// Current propagator 2682 ActorLink* c; 2683 /// End mark 2684 ActorLink* e; 2685 public: 2686 /// Initialize 2687 Propagators(Space& home); 2688 /// Test whether there are propagators left 2689 bool operator ()(void) const; 2690 /// Move iterator to next propagator 2691 void operator ++(void); 2692 /// Return propagator 2693 Propagator& propagator(void) const; 2694 }; 2695 /** 2696 * \brief Class to iterate over scheduled propagators of a space 2697 * 2698 * Note that the iterator cannot be used during cloning. 2699 */ 2700 class ScheduledPropagators { 2701 private: 2702 /// current space 2703 Space& home; 2704 /// current queue 2705 ActorLink* q; 2706 /// current propagator 2707 ActorLink* c; 2708 /// end mark 2709 ActorLink* e; 2710 public: 2711 /// Initialize 2712 ScheduledPropagators(Space& home); 2713 /// Test whether there are propagators left 2714 bool operator ()(void) const; 2715 /// Move iterator to next propagator 2716 void operator ++(void); 2717 /// Return propagator 2718 Propagator& propagator(void) const; 2719 }; 2720 /** 2721 * \brief Class to iterate over idle propagators of a space 2722 * 2723 * Note that the iterator cannot be used during cloning. 2724 */ 2725 class IdlePropagators { 2726 private: 2727 /// Current propagator 2728 ActorLink* c; 2729 /// End mark 2730 ActorLink* e; 2731 public: 2732 /// Initialize 2733 IdlePropagators(Space& home); 2734 /// Test whether there are propagators left 2735 bool operator ()(void) const; 2736 /// Move iterator to next propagator 2737 void operator ++(void); 2738 /// Return propagator 2739 Propagator& propagator(void) const; 2740 }; 2741 /** 2742 * \brief Class to iterate over branchers of a space 2743 * 2744 * Note that the iterator cannot be used during cloning. 2745 */ 2746 class Branchers { 2747 private: 2748 /// current brancher 2749 ActorLink* c; 2750 /// end mark 2751 ActorLink* e; 2752 public: 2753 /// Initialize 2754 Branchers(Space& home); 2755 /// Test whether there are branchers left 2756 bool operator ()(void) const; 2757 /// Move iterator to next brancher 2758 void operator ++(void); 2759 /// Return propagator 2760 Brancher& brancher(void) const; 2761 }; 2762 }; 2763 2764 /// Class to iterate over propagators in a group 2765 class Propagators { 2766 private: 2767 /// Propagators 2768 Space::Propagators ps; 2769 /// Current group 2770 PropagatorGroup g; 2771 public: 2772 /// Initialize 2773 Propagators(const Space& home, PropagatorGroup g); 2774 /// Test whether there are propagators left 2775 bool operator ()(void) const; 2776 /// Move iterator to next propagator 2777 void operator ++(void); 2778 /// Return propagator 2779 const Propagator& propagator(void) const; 2780 }; 2781 2782 /// Class to iterate over branchers in a group 2783 class Branchers { 2784 private: 2785 /// Branchers 2786 Space::Branchers bs; 2787 /// Current group 2788 BrancherGroup g; 2789 public: 2790 /// Initialize 2791 Branchers(const Space& home, BrancherGroup g); 2792 /// Test whether there are branchers left 2793 bool operator ()(void) const; 2794 /// Move iterator to next brancher 2795 void operator ++(void); 2796 /// Return propagator 2797 const Brancher& brancher(void) const; 2798 }; 2799 2800 2801 2802 2803 /* 2804 * Memory management 2805 * 2806 */ 2807 2808 // Space allocation: general space heaps and free lists 2809 forceinline void* ralloc(size_t s)2810 Space::ralloc(size_t s) { 2811 return mm.alloc(ssd.data().sm,s); 2812 } 2813 forceinline void rfree(void * p,size_t s)2814 Space::rfree(void* p, size_t s) { 2815 return mm.reuse(p,s); 2816 } 2817 forceinline void* rrealloc(void * _b,size_t n,size_t m)2818 Space::rrealloc(void* _b, size_t n, size_t m) { 2819 char* b = static_cast<char*>(_b); 2820 if (n < m) { 2821 char* p = static_cast<char*>(ralloc(m)); 2822 memcpy(p,b,n); 2823 rfree(b,n); 2824 return p; 2825 } else { 2826 rfree(b+m,m-n); 2827 return b; 2828 } 2829 } 2830 2831 template<size_t s> 2832 forceinline void* fl_alloc(void)2833 Space::fl_alloc(void) { 2834 return mm.template fl_alloc<s>(ssd.data().sm); 2835 } 2836 template<size_t s> 2837 forceinline void fl_dispose(FreeList * f,FreeList * l)2838 Space::fl_dispose(FreeList* f, FreeList* l) { 2839 mm.template fl_dispose<s>(f,l); 2840 } 2841 2842 /* 2843 * Typed allocation routines 2844 * 2845 */ 2846 template<class T> 2847 forceinline T* alloc(long unsigned int n)2848 Space::alloc(long unsigned int n) { 2849 T* p = static_cast<T*>(ralloc(sizeof(T)*n)); 2850 for (long unsigned int i=0; i<n; i++) 2851 (void) new (p+i) T(); 2852 return p; 2853 } 2854 template<class T> 2855 forceinline T* alloc(long int n)2856 Space::alloc(long int n) { 2857 assert(n >= 0); 2858 return alloc<T>(static_cast<long unsigned int>(n)); 2859 } 2860 template<class T> 2861 forceinline T* alloc(unsigned int n)2862 Space::alloc(unsigned int n) { 2863 return alloc<T>(static_cast<long unsigned int>(n)); 2864 } 2865 template<class T> 2866 forceinline T* alloc(int n)2867 Space::alloc(int n) { 2868 assert(n >= 0); 2869 return alloc<T>(static_cast<long unsigned int>(n)); 2870 } 2871 2872 template<class T> 2873 forceinline void free(T * b,long unsigned int n)2874 Space::free(T* b, long unsigned int n) { 2875 for (long unsigned int i=0; i<n; i++) 2876 b[i].~T(); 2877 rfree(b,n*sizeof(T)); 2878 } 2879 template<class T> 2880 forceinline void free(T * b,long int n)2881 Space::free(T* b, long int n) { 2882 assert(n >= 0); 2883 free<T>(b,static_cast<long unsigned int>(n)); 2884 } 2885 template<class T> 2886 forceinline void free(T * b,unsigned int n)2887 Space::free(T* b, unsigned int n) { 2888 free<T>(b,static_cast<long unsigned int>(n)); 2889 } 2890 template<class T> 2891 forceinline void free(T * b,int n)2892 Space::free(T* b, int n) { 2893 assert(n >= 0); 2894 free<T>(b,static_cast<long unsigned int>(n)); 2895 } 2896 2897 template<class T> 2898 forceinline T* realloc(T * b,long unsigned int n,long unsigned int m)2899 Space::realloc(T* b, long unsigned int n, long unsigned int m) { 2900 if (n < m) { 2901 T* p = static_cast<T*>(ralloc(sizeof(T)*m)); 2902 for (long unsigned int i=0; i<n; i++) 2903 (void) new (p+i) T(b[i]); 2904 for (long unsigned int i=n; i<m; i++) 2905 (void) new (p+i) T(); 2906 free<T>(b,n); 2907 return p; 2908 } else { 2909 free<T>(b+m,m-n); 2910 return b; 2911 } 2912 } 2913 template<class T> 2914 forceinline T* realloc(T * b,long int n,long int m)2915 Space::realloc(T* b, long int n, long int m) { 2916 assert((n >= 0) && (m >= 0)); 2917 return realloc<T>(b,static_cast<long unsigned int>(n), 2918 static_cast<long unsigned int>(m)); 2919 } 2920 template<class T> 2921 forceinline T* realloc(T * b,unsigned int n,unsigned int m)2922 Space::realloc(T* b, unsigned int n, unsigned int m) { 2923 return realloc<T>(b,static_cast<long unsigned int>(n), 2924 static_cast<long unsigned int>(m)); 2925 } 2926 template<class T> 2927 forceinline T* realloc(T * b,int n,int m)2928 Space::realloc(T* b, int n, int m) { 2929 assert((n >= 0) && (m >= 0)); 2930 return realloc<T>(b,static_cast<long unsigned int>(n), 2931 static_cast<long unsigned int>(m)); 2932 } 2933 2934 #define GECODE_KERNEL_REALLOC(T) \ 2935 template<> \ 2936 forceinline T* \ 2937 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \ 2938 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \ 2939 } \ 2940 template<> \ 2941 forceinline T* \ 2942 Space::realloc<T>(T* b, long int n, long int m) { \ 2943 assert((n >= 0) && (m >= 0)); \ 2944 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2945 static_cast<long unsigned int>(m)); \ 2946 } \ 2947 template<> \ 2948 forceinline T* \ 2949 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \ 2950 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2951 static_cast<long unsigned int>(m)); \ 2952 } \ 2953 template<> \ 2954 forceinline T* \ 2955 Space::realloc<T>(T* b, int n, int m) { \ 2956 assert((n >= 0) && (m >= 0)); \ 2957 return realloc<T>(b,static_cast<long unsigned int>(n), \ 2958 static_cast<long unsigned int>(m)); \ 2959 } 2960 2961 GECODE_KERNEL_REALLOC(bool) GECODE_KERNEL_REALLOC(signed char)2962 GECODE_KERNEL_REALLOC(signed char) 2963 GECODE_KERNEL_REALLOC(unsigned char) 2964 GECODE_KERNEL_REALLOC(signed short int) 2965 GECODE_KERNEL_REALLOC(unsigned short int) 2966 GECODE_KERNEL_REALLOC(signed int) 2967 GECODE_KERNEL_REALLOC(unsigned int) 2968 GECODE_KERNEL_REALLOC(signed long int) 2969 GECODE_KERNEL_REALLOC(unsigned long int) 2970 GECODE_KERNEL_REALLOC(float) 2971 GECODE_KERNEL_REALLOC(double) 2972 2973 #undef GECODE_KERNEL_REALLOC 2974 2975 template<class T> 2976 forceinline T** 2977 Space::realloc(T** b, long unsigned int n, long unsigned int m) { 2978 return static_cast<T**>(rrealloc(b,n*sizeof(T),m*sizeof(T*))); 2979 } 2980 template<class T> 2981 forceinline T** realloc(T ** b,long int n,long int m)2982 Space::realloc(T** b, long int n, long int m) { 2983 assert((n >= 0) && (m >= 0)); 2984 return realloc<T*>(b,static_cast<long unsigned int>(n), 2985 static_cast<long unsigned int>(m)); 2986 } 2987 template<class T> 2988 forceinline T** realloc(T ** b,unsigned int n,unsigned int m)2989 Space::realloc(T** b, unsigned int n, unsigned int m) { 2990 return realloc<T*>(b,static_cast<long unsigned int>(n), 2991 static_cast<long unsigned int>(m)); 2992 } 2993 template<class T> 2994 forceinline T** realloc(T ** b,int n,int m)2995 Space::realloc(T** b, int n, int m) { 2996 assert((n >= 0) && (m >= 0)); 2997 return realloc<T*>(b,static_cast<long unsigned int>(n), 2998 static_cast<long unsigned int>(m)); 2999 } 3000 3001 3002 #ifdef GECODE_HAS_VAR_DISPOSE 3003 template<class VIC> 3004 forceinline VarImpBase* vars_d(void) const3005 Space::vars_d(void) const { 3006 return _vars_d[VIC::idx_d]; 3007 } 3008 template<class VIC> 3009 forceinline void vars_d(VarImpBase * x)3010 Space::vars_d(VarImpBase* x) { 3011 _vars_d[VIC::idx_d] = x; 3012 } 3013 #endif 3014 3015 // Space allocated entities: Actors, variable implementations, and advisors 3016 forceinline void operator delete(void *)3017 Actor::operator delete(void*) {} 3018 forceinline void operator delete(void *,Space &)3019 Actor::operator delete(void*, Space&) {} 3020 forceinline void* operator new(size_t s,Space & home)3021 Actor::operator new(size_t s, Space& home) { 3022 return home.ralloc(s); 3023 } 3024 3025 template<class VIC> 3026 forceinline void operator delete(void *)3027 VarImp<VIC>::operator delete(void*) {} 3028 template<class VIC> 3029 forceinline void operator delete(void *,Space &)3030 VarImp<VIC>::operator delete(void*, Space&) {} 3031 template<class VIC> 3032 forceinline void* operator new(size_t s,Space & home)3033 VarImp<VIC>::operator new(size_t s, Space& home) { 3034 return home.ralloc(s); 3035 } 3036 3037 #ifndef __GNUC__ 3038 forceinline void operator delete(void *)3039 Advisor::operator delete(void*) {} 3040 #endif 3041 forceinline void operator delete(void *,Space &)3042 Advisor::operator delete(void*, Space&) {} 3043 forceinline void* operator new(size_t s,Space & home)3044 Advisor::operator new(size_t s, Space& home) { 3045 return home.ralloc(s); 3046 } 3047 3048 forceinline void operator delete(void *)3049 NGL::operator delete(void*) {} 3050 forceinline void operator delete(void *,Space &)3051 NGL::operator delete(void*, Space&) {} 3052 forceinline void* operator new(size_t s,Space & home)3053 NGL::operator new(size_t s, Space& home) { 3054 return home.ralloc(s); 3055 } 3056 3057 3058 /* 3059 * No-goods 3060 * 3061 */ 3062 forceinline NoGoods(void)3063 NoGoods::NoGoods(void) 3064 : n(0) {} 3065 forceinline unsigned long int ng(void) const3066 NoGoods::ng(void) const { 3067 return n; 3068 } 3069 forceinline void ng(unsigned long int n0)3070 NoGoods::ng(unsigned long int n0) { 3071 n=n0; 3072 } 3073 forceinline ~NoGoods(void)3074 NoGoods::~NoGoods(void) {} 3075 3076 3077 /* 3078 * Information from meta search engines 3079 */ 3080 forceinline MetaInfo(unsigned long int r0,unsigned long long int s0,unsigned long long int f0,const Space * l0,NoGoods & ng0)3081 MetaInfo::MetaInfo(unsigned long int r0, 3082 unsigned long long int s0, 3083 unsigned long long int f0, 3084 const Space* l0, 3085 NoGoods& ng0) 3086 : t(RESTART), r(r0), s(s0), f(f0), l(l0), ng(ng0), a(0) {} 3087 3088 forceinline MetaInfo(unsigned int a0)3089 MetaInfo::MetaInfo(unsigned int a0) 3090 : t(PORTFOLIO), r(0), s(0), f(0), l(nullptr), ng(NoGoods::eng), a(a0) {} 3091 3092 forceinline MetaInfo::Type type(void) const3093 MetaInfo::type(void) const { 3094 return t; 3095 } 3096 forceinline unsigned long int restart(void) const3097 MetaInfo::restart(void) const { 3098 assert(type() == RESTART); 3099 return r; 3100 } 3101 forceinline unsigned long long int solution(void) const3102 MetaInfo::solution(void) const { 3103 assert(type() == RESTART); 3104 return s; 3105 } 3106 forceinline unsigned long long int fail(void) const3107 MetaInfo::fail(void) const { 3108 assert(type() == RESTART); 3109 return f; 3110 } 3111 forceinline const Space* last(void) const3112 MetaInfo::last(void) const { 3113 assert(type() == RESTART); 3114 return l; 3115 } 3116 forceinline const NoGoods& nogoods(void) const3117 MetaInfo::nogoods(void) const { 3118 assert(type() == RESTART); 3119 return ng; 3120 } 3121 forceinline unsigned int asset(void) const3122 MetaInfo::asset(void) const { 3123 assert(type() == PORTFOLIO); 3124 return a; 3125 } 3126 3127 3128 3129 /* 3130 * ActorLink 3131 * 3132 */ 3133 forceinline ActorLink* prev(void) const3134 ActorLink::prev(void) const { 3135 return _prev; 3136 } 3137 3138 forceinline ActorLink* next(void) const3139 ActorLink::next(void) const { 3140 return _next; 3141 } 3142 3143 forceinline ActorLink** next_ref(void)3144 ActorLink::next_ref(void) { 3145 return &_next; 3146 } 3147 3148 forceinline void prev(ActorLink * al)3149 ActorLink::prev(ActorLink* al) { 3150 _prev = al; 3151 } 3152 3153 forceinline void next(ActorLink * al)3154 ActorLink::next(ActorLink* al) { 3155 _next = al; 3156 } 3157 3158 forceinline void unlink(void)3159 ActorLink::unlink(void) { 3160 ActorLink* p = _prev; ActorLink* n = _next; 3161 p->_next = n; n->_prev = p; 3162 } 3163 3164 forceinline void init(void)3165 ActorLink::init(void) { 3166 _next = this; _prev =this; 3167 } 3168 3169 forceinline void head(ActorLink * a)3170 ActorLink::head(ActorLink* a) { 3171 // Inserts al at head of link-chain (that is, after this) 3172 ActorLink* n = _next; 3173 this->_next = a; a->_prev = this; 3174 a->_next = n; n->_prev = a; 3175 } 3176 3177 forceinline void tail(ActorLink * a)3178 ActorLink::tail(ActorLink* a) { 3179 // Inserts al at tail of link-chain (that is, before this) 3180 ActorLink* p = _prev; 3181 a->_next = this; this->_prev = a; 3182 p->_next = a; a->_prev = p; 3183 } 3184 3185 forceinline bool empty(void) const3186 ActorLink::empty(void) const { 3187 return _next == this; 3188 } 3189 3190 template<class T> 3191 forceinline ActorLink* cast(T * a)3192 ActorLink::cast(T* a) { 3193 // Turning al into a reference is for gcc, assume is for MSVC 3194 GECODE_NOT_NULL(a); 3195 ActorLink& t = *a; 3196 return static_cast<ActorLink*>(&t); 3197 } 3198 3199 template<class T> 3200 forceinline const ActorLink* cast(const T * a)3201 ActorLink::cast(const T* a) { 3202 // Turning al into a reference is for gcc, assume is for MSVC 3203 GECODE_NOT_NULL(a); 3204 const ActorLink& t = *a; 3205 return static_cast<const ActorLink*>(&t); 3206 } 3207 3208 3209 /* 3210 * Actor 3211 * 3212 */ 3213 forceinline Actor* cast(ActorLink * al)3214 Actor::cast(ActorLink* al) { 3215 // Turning al into a reference is for gcc, assume is for MSVC 3216 GECODE_NOT_NULL(al); 3217 ActorLink& t = *al; 3218 return static_cast<Actor*>(&t); 3219 } 3220 3221 forceinline const Actor* cast(const ActorLink * al)3222 Actor::cast(const ActorLink* al) { 3223 // Turning al into a reference is for gcc, assume is for MSVC 3224 GECODE_NOT_NULL(al); 3225 const ActorLink& t = *al; 3226 return static_cast<const Actor*>(&t); 3227 } 3228 3229 forceinline void notice(Actor & a,ActorProperty p,bool duplicate)3230 Home::notice(Actor& a, ActorProperty p, bool duplicate) { 3231 s.notice(a,p,duplicate); 3232 } 3233 3234 forceinline Space* clone(CloneStatistics &) const3235 Space::clone(CloneStatistics&) const { 3236 // Clone is only const for search engines. During cloning, several data 3237 // structures are updated (e.g. forwarding pointers), so we have to 3238 // cast away the constness. 3239 return const_cast<Space*>(this)->_clone(); 3240 } 3241 3242 forceinline void commit(const Choice & c,unsigned int a,CommitStatistics &)3243 Space::commit(const Choice& c, unsigned int a, CommitStatistics&) { 3244 _commit(c,a); 3245 } 3246 3247 forceinline void trycommit(const Choice & c,unsigned int a,CommitStatistics &)3248 Space::trycommit(const Choice& c, unsigned int a, CommitStatistics&) { 3249 _trycommit(c,a); 3250 } 3251 3252 forceinline double afc_decay(void) const3253 Space::afc_decay(void) const { 3254 return ssd.data().gpi.decay(); 3255 } 3256 3257 forceinline void afc_decay(double d)3258 Space::afc_decay(double d) { 3259 ssd.data().gpi.decay(d); 3260 } 3261 3262 forceinline size_t dispose(Space &)3263 Actor::dispose(Space&) { 3264 return sizeof(*this); 3265 } 3266 3267 3268 /* 3269 * Home for posting actors 3270 * 3271 */ 3272 forceinline Home(Space & s0,Propagator * p0,PropagatorGroup pg0,BrancherGroup bg0)3273 Home::Home(Space& s0, Propagator* p0, 3274 PropagatorGroup pg0, BrancherGroup bg0) 3275 : s(s0), p(p0), pg(pg0), bg(bg0) {} 3276 forceinline Home(const Home & h)3277 Home::Home(const Home& h) 3278 : s(h.s), p(h.p), pg(h.pg), bg(h.bg) {} 3279 forceinline Home& operator =(const Home & h)3280 Home::operator =(const Home& h) { 3281 s=h.s; p=h.p; pg=h.pg; bg=h.bg; 3282 return *this; 3283 } 3284 forceinline operator Space&(void)3285 Home::operator Space&(void) { 3286 return s; 3287 } 3288 forceinline Home operator ()(Propagator & p)3289 Home::operator ()(Propagator& p) { 3290 return Home(s,&p); 3291 } 3292 forceinline Home operator ()(PropagatorGroup pg)3293 Home::operator ()(PropagatorGroup pg) { 3294 return Home(s,nullptr,pg,BrancherGroup::def); 3295 } 3296 forceinline Home operator ()(BrancherGroup bg)3297 Home::operator ()(BrancherGroup bg) { 3298 return Home(s,nullptr,PropagatorGroup::def,bg); 3299 } 3300 forceinline Home operator ()(Propagator & p)3301 Space::operator ()(Propagator& p) { 3302 return Home(*this,&p); 3303 } 3304 forceinline Home operator ()(PropagatorGroup pg)3305 Space::operator ()(PropagatorGroup pg) { 3306 return Home(*this,nullptr,pg,BrancherGroup::def); 3307 } 3308 forceinline Home operator ()(BrancherGroup bg)3309 Space::operator ()(BrancherGroup bg) { 3310 return Home(*this,nullptr,PropagatorGroup::def,bg); 3311 } 3312 forceinline Propagator* propagator(void) const3313 Home::propagator(void) const { 3314 return p; 3315 } 3316 forceinline PropagatorGroup propagatorgroup(void) const3317 Home::propagatorgroup(void) const { 3318 return pg; 3319 } 3320 forceinline BrancherGroup branchergroup(void) const3321 Home::branchergroup(void) const { 3322 return bg; 3323 } 3324 3325 /* 3326 * View trace information 3327 * 3328 */ 3329 forceinline void propagator(Propagator & p)3330 ViewTraceInfo::propagator(Propagator& p) { 3331 who = reinterpret_cast<ptrdiff_t>(&p) | PROPAGATOR; 3332 } 3333 forceinline void brancher(Brancher & b)3334 ViewTraceInfo::brancher(Brancher& b) { 3335 who = reinterpret_cast<ptrdiff_t>(&b) | BRANCHER; 3336 } 3337 forceinline void post(PropagatorGroup g)3338 ViewTraceInfo::post(PropagatorGroup g) { 3339 who = (g.id() << 2) | POST; 3340 } 3341 forceinline void other(void)3342 ViewTraceInfo::other(void) { 3343 who = OTHER; 3344 } 3345 forceinline ViewTraceInfo::What what(void) const3346 ViewTraceInfo::what(void) const { 3347 return static_cast<What>(who & 3); 3348 } 3349 forceinline const Propagator& propagator(void) const3350 ViewTraceInfo::propagator(void) const { 3351 assert(what() == PROPAGATOR); 3352 // Because PROPAGATOR == 0 3353 return *reinterpret_cast<Propagator*>(who); 3354 } 3355 forceinline const Brancher& brancher(void) const3356 ViewTraceInfo::brancher(void) const { 3357 assert(what() == BRANCHER); 3358 return *reinterpret_cast<Brancher*>(who & ~3); 3359 } 3360 forceinline PropagatorGroup post(void) const3361 ViewTraceInfo::post(void) const { 3362 assert(what() == POST); 3363 return PropagatorGroup(static_cast<unsigned int>(who >> 2)); 3364 } 3365 3366 /* 3367 * Post information 3368 */ 3369 forceinline PostInfo(Home home)3370 PostInfo::PostInfo(Home home) 3371 : h(home), pg(home.propagatorgroup()), 3372 pid(h.ssd.data().gpi.pid()), 3373 nested(h.pc.p.vti.what() != ViewTraceInfo::OTHER) { 3374 h.pc.p.vti.post(pg); 3375 } 3376 3377 forceinline ~PostInfo(void)3378 PostInfo::~PostInfo(void) { 3379 if (!nested) { 3380 if (h.pc.p.bid_sc & Space::sc_trace) 3381 h.post(*this); 3382 h.pc.p.vti.other(); 3383 } 3384 } 3385 3386 3387 /* 3388 * Propagate trace information 3389 * 3390 */ 3391 forceinline PropagateTraceInfo(unsigned int i0,PropagatorGroup g0,const Propagator * p0,Status s0)3392 PropagateTraceInfo::PropagateTraceInfo(unsigned int i0, PropagatorGroup g0, 3393 const Propagator* p0, Status s0) 3394 : i(i0), g(g0), p(p0), s(s0) {} 3395 forceinline unsigned int id(void) const3396 PropagateTraceInfo::id(void) const { 3397 return i; 3398 } 3399 forceinline PropagatorGroup group(void) const3400 PropagateTraceInfo::group(void) const { 3401 return g; 3402 } 3403 forceinline const Propagator* propagator(void) const3404 PropagateTraceInfo::propagator(void) const { 3405 return p; 3406 } 3407 forceinline PropagateTraceInfo::Status status(void) const3408 PropagateTraceInfo::status(void) const { 3409 return s; 3410 } 3411 3412 3413 /* 3414 * Commit trace information 3415 * 3416 */ 3417 forceinline CommitTraceInfo(const Brancher & b0,const Choice & c0,unsigned int a0)3418 CommitTraceInfo::CommitTraceInfo(const Brancher& b0, const Choice& c0, 3419 unsigned int a0) 3420 : b(b0), c(c0), a(a0) {} 3421 forceinline unsigned int id(void) const3422 CommitTraceInfo::id(void) const { 3423 return b.id(); 3424 } 3425 forceinline BrancherGroup group(void) const3426 CommitTraceInfo::group(void) const { 3427 return b.group(); 3428 } 3429 forceinline const Brancher& brancher(void) const3430 CommitTraceInfo::brancher(void) const { 3431 return b; 3432 } 3433 forceinline const Choice& choice(void) const3434 CommitTraceInfo::choice(void) const { 3435 return c; 3436 } 3437 forceinline unsigned int alternative(void) const3438 CommitTraceInfo::alternative(void) const { 3439 return a; 3440 } 3441 3442 3443 /* 3444 * Post trace information 3445 * 3446 */ 3447 forceinline PostTraceInfo(PropagatorGroup g0,Status s0,unsigned int n0)3448 PostTraceInfo::PostTraceInfo(PropagatorGroup g0, Status s0, unsigned int n0) 3449 : g(g0), s(s0), n(n0) {} 3450 forceinline PropagatorGroup group(void) const3451 PostTraceInfo::group(void) const { 3452 return g; 3453 } 3454 forceinline PostTraceInfo::Status status(void) const3455 PostTraceInfo::status(void) const { 3456 return s; 3457 } 3458 forceinline unsigned int propagators(void) const3459 PostTraceInfo::propagators(void) const { 3460 return n; 3461 } 3462 3463 3464 /* 3465 * Propagator 3466 * 3467 */ 3468 forceinline Propagator* cast(ActorLink * al)3469 Propagator::cast(ActorLink* al) { 3470 // Turning al into a reference is for gcc, assume is for MSVC 3471 GECODE_NOT_NULL(al); 3472 ActorLink& t = *al; 3473 return static_cast<Propagator*>(&t); 3474 } 3475 3476 forceinline const Propagator* cast(const ActorLink * al)3477 Propagator::cast(const ActorLink* al) { 3478 // Turning al into a reference is for gcc, assume is for MSVC 3479 GECODE_NOT_NULL(al); 3480 const ActorLink& t = *al; 3481 return static_cast<const Propagator*>(&t); 3482 } 3483 3484 forceinline Propagator* fwd(void) const3485 Propagator::fwd(void) const { 3486 return static_cast<Propagator*>(prev()); 3487 } 3488 3489 forceinline bool disabled(void) const3490 Propagator::disabled(void) const { 3491 return Support::marked(gpi_disabled); 3492 } 3493 3494 forceinline void disable(Space & home)3495 Propagator::disable(Space& home) { 3496 home.pc.p.bid_sc |= Space::sc_disabled; 3497 gpi_disabled = Support::fmark(gpi_disabled); 3498 } 3499 3500 forceinline void enable(Space & home)3501 Propagator::enable(Space& home) { 3502 (void) home; 3503 gpi_disabled = Support::funmark(gpi_disabled); 3504 } 3505 3506 forceinline Kernel::GPI::Info& gpi(void)3507 Propagator::gpi(void) { 3508 return *static_cast<Kernel::GPI::Info*>(Support::funmark(gpi_disabled)); 3509 } 3510 3511 forceinline Propagator(Home home)3512 Propagator::Propagator(Home home) 3513 : gpi_disabled((home.propagator() != nullptr) ? 3514 // Inherit propagator information 3515 home.propagator()->gpi_disabled : 3516 // New propagator information 3517 static_cast<Space&>(home).ssd.data().gpi.allocate 3518 (home.propagatorgroup().gid)) { 3519 u.advisors = nullptr; 3520 assert((u.med == 0) && (u.size == 0)); 3521 static_cast<Space&>(home).pl.head(this); 3522 } 3523 3524 forceinline Propagator(Space &,Propagator & p)3525 Propagator::Propagator(Space&, Propagator& p) 3526 : gpi_disabled(p.gpi_disabled) { 3527 u.advisors = nullptr; 3528 assert((u.med == 0) && (u.size == 0)); 3529 // Set forwarding pointer 3530 p.prev(this); 3531 } 3532 3533 forceinline ModEventDelta modeventdelta(void) const3534 Propagator::modeventdelta(void) const { 3535 return u.med; 3536 } 3537 3538 forceinline double afc(void) const3539 Propagator::afc(void) const { 3540 return const_cast<Propagator&>(*this).gpi().afc; 3541 } 3542 3543 #ifdef GECODE_HAS_CBS 3544 forceinline void solndistrib(Space &,SendMarginal) const3545 Propagator::solndistrib(Space&, SendMarginal) const {} 3546 3547 forceinline void domainsizesum(InDecision,unsigned int & size,unsigned int & size_b) const3548 Propagator::domainsizesum(InDecision, unsigned int& size, 3549 unsigned int& size_b) const { 3550 size = 0; 3551 size_b = 0; 3552 } 3553 #endif 3554 3555 forceinline unsigned int id(void) const3556 Propagator::id(void) const { 3557 return const_cast<Propagator&>(*this).gpi().pid; 3558 } 3559 3560 forceinline PropagatorGroup group(void) const3561 Propagator::group(void) const { 3562 return PropagatorGroup(const_cast<Propagator&>(*this).gpi().gid); 3563 } 3564 3565 forceinline void group(PropagatorGroup g)3566 Propagator::group(PropagatorGroup g) { 3567 gpi().gid = g.id(); 3568 } 3569 3570 forceinline ExecStatus ES_SUBSUMED_DISPOSED(Propagator & p,size_t s)3571 Space::ES_SUBSUMED_DISPOSED(Propagator& p, size_t s) { 3572 p.u.size = s; 3573 return ES_SUBSUMED_; 3574 } 3575 3576 forceinline ExecStatus ES_SUBSUMED(Propagator & p)3577 Space::ES_SUBSUMED(Propagator& p) { 3578 p.u.size = p.dispose(*this); 3579 return ES_SUBSUMED_; 3580 } 3581 3582 forceinline ExecStatus ES_FIX_PARTIAL(Propagator & p,const ModEventDelta & med)3583 Space::ES_FIX_PARTIAL(Propagator& p, const ModEventDelta& med) { 3584 p.u.med = med; 3585 assert(p.u.med != 0); 3586 return ES_PARTIAL_; 3587 } 3588 3589 forceinline ExecStatus ES_NOFIX_PARTIAL(Propagator & p,const ModEventDelta & med)3590 Space::ES_NOFIX_PARTIAL(Propagator& p, const ModEventDelta& med) { 3591 p.u.med = AllVarConf::med_combine(p.u.med,med); 3592 assert(p.u.med != 0); 3593 return ES_PARTIAL_; 3594 } 3595 3596 3597 3598 /* 3599 * Brancher 3600 * 3601 */ 3602 forceinline Brancher* cast(ActorLink * al)3603 Brancher::cast(ActorLink* al) { 3604 // Turning al into a reference is for gcc, assume is for MSVC 3605 GECODE_NOT_NULL(al); 3606 ActorLink& t = *al; 3607 return static_cast<Brancher*>(&t); 3608 } 3609 3610 forceinline const Brancher* cast(const ActorLink * al)3611 Brancher::cast(const ActorLink* al) { 3612 // Turning al into a reference is for gcc, assume is for MSVC 3613 GECODE_NOT_NULL(al); 3614 const ActorLink& t = *al; 3615 return static_cast<const Brancher*>(&t); 3616 } 3617 3618 forceinline Brancher(Home _home)3619 Brancher::Brancher(Home _home) : 3620 gid(_home.branchergroup().gid) { 3621 Space& home = static_cast<Space&>(_home); 3622 bid = home.pc.p.bid_sc >> Space::sc_bits; 3623 home.pc.p.bid_sc += (1 << Space::sc_bits); 3624 if ((home.pc.p.bid_sc >> Space::sc_bits) == 0U) 3625 throw TooManyBranchers("Brancher::Brancher"); 3626 // If no brancher available, make it the first one 3627 if (home.b_status == &static_cast<Space&>(home).bl) { 3628 home.b_status = this; 3629 if (home.b_commit == &static_cast<Space&>(home).bl) 3630 home.b_commit = this; 3631 } 3632 home.bl.tail(this); 3633 } 3634 3635 forceinline Brancher(Space &,Brancher & b)3636 Brancher::Brancher(Space&, Brancher& b) 3637 : bid(b.bid), gid(b.gid) { 3638 // Set forwarding pointer 3639 b.prev(this); 3640 } 3641 3642 forceinline unsigned int id(void) const3643 Brancher::id(void) const { 3644 return bid; 3645 } 3646 3647 forceinline BrancherGroup group(void) const3648 Brancher::group(void) const { 3649 return BrancherGroup(gid); 3650 } 3651 3652 forceinline void group(BrancherGroup g)3653 Brancher::group(BrancherGroup g) { 3654 gid = g.id(); 3655 } 3656 3657 3658 forceinline void kill(Brancher & b)3659 Space::kill(Brancher& b) { 3660 assert(!failed()); 3661 // Make sure that neither b_status nor b_commit does not point to b! 3662 if (b_commit == &b) 3663 b_commit = Brancher::cast(b.next()); 3664 if (b_status == &b) 3665 b_status = Brancher::cast(b.next()); 3666 b.unlink(); 3667 rfree(&b,b.dispose(*this)); 3668 } 3669 3670 forceinline void kill(Propagator & p)3671 Space::kill(Propagator& p) { 3672 assert(!failed()); 3673 p.unlink(); 3674 rfree(&p,p.dispose(*this)); 3675 // Is the space already stable? 3676 if (pc.p.active < &pc.p.queue[0]) 3677 return; 3678 // Enforce that empty queues are ignored 3679 do { 3680 assert(pc.p.active >= &pc.p.queue[0]); 3681 // First propagator or link back to queue? 3682 if (pc.p.active != pc.p.active->next()) 3683 return; // A propagator is left in the queue 3684 } while (--pc.p.active >= &pc.p.queue[0]); 3685 // The space is stable now 3686 assert(pc.p.active < &pc.p.queue[0]); 3687 } 3688 3689 forceinline Brancher* brancher(unsigned int id)3690 Space::brancher(unsigned int id) { 3691 /* 3692 * Due to weakly monotonic propagators the following scenario might 3693 * occur: a brancher has been committed with all its available 3694 * choices. Then, propagation determines less information 3695 * than before and the brancher now will create new choices. 3696 * Later, during recomputation, all of these choices 3697 * can be used together, possibly interleaved with 3698 * choices for other branchers. That means all branchers 3699 * must be scanned to find the matching brancher for the choice. 3700 * 3701 * b_commit tries to optimize scanning as it is most likely that 3702 * recomputation does not generate new choices during recomputation 3703 * and hence b_commit is moved from newer to older branchers. 3704 */ 3705 Brancher* b_old = b_commit; 3706 // Try whether we are lucky 3707 while (b_commit != Brancher::cast(&bl)) 3708 if (id != b_commit->id()) 3709 b_commit = Brancher::cast(b_commit->next()); 3710 else 3711 return b_commit; 3712 if (b_commit == Brancher::cast(&bl)) { 3713 // We did not find the brancher, start at the beginning 3714 b_commit = Brancher::cast(bl.next()); 3715 while (b_commit != b_old) 3716 if (id != b_commit->id()) 3717 b_commit = Brancher::cast(b_commit->next()); 3718 else 3719 return b_commit; 3720 } 3721 return nullptr; 3722 } 3723 3724 3725 /* 3726 * Local objects 3727 * 3728 */ 3729 3730 forceinline LocalObject* cast(ActorLink * al)3731 LocalObject::cast(ActorLink* al) { 3732 // Turning al into a reference is for gcc, assume is for MSVC 3733 GECODE_NOT_NULL(al); 3734 ActorLink& t = *al; 3735 return static_cast<LocalObject*>(&t); 3736 } 3737 3738 forceinline const LocalObject* cast(const ActorLink * al)3739 LocalObject::cast(const ActorLink* al) { 3740 // Turning al into a reference is for gcc, assume is for MSVC 3741 GECODE_NOT_NULL(al); 3742 const ActorLink& t = *al; 3743 return static_cast<const LocalObject*>(&t); 3744 } 3745 3746 forceinline LocalObject(Home home)3747 LocalObject::LocalObject(Home home) { 3748 (void) home; 3749 ActorLink::cast(this)->prev(nullptr); 3750 } 3751 3752 forceinline LocalObject(Space &,LocalObject &)3753 LocalObject::LocalObject(Space&, LocalObject&) { 3754 ActorLink::cast(this)->prev(nullptr); 3755 } 3756 3757 forceinline LocalObject* fwd(Space & home)3758 LocalObject::fwd(Space& home) { 3759 if (prev() == nullptr) 3760 fwdcopy(home); 3761 return LocalObject::cast(prev()); 3762 } 3763 3764 forceinline LocalHandle(void)3765 LocalHandle::LocalHandle(void) : o(nullptr) {} 3766 forceinline LocalHandle(LocalObject * lo)3767 LocalHandle::LocalHandle(LocalObject* lo) : o(lo) {} 3768 forceinline LocalHandle(const LocalHandle & lh)3769 LocalHandle::LocalHandle(const LocalHandle& lh) : o(lh.o) {} 3770 forceinline LocalHandle& operator =(const LocalHandle & lh)3771 LocalHandle::operator =(const LocalHandle& lh) { 3772 o = lh.o; 3773 return *this; 3774 } 3775 forceinline ~LocalHandle(void)3776 LocalHandle::~LocalHandle(void) {} 3777 forceinline LocalObject* object(void) const3778 LocalHandle::object(void) const { return o; } 3779 forceinline void object(LocalObject * n)3780 LocalHandle::object(LocalObject* n) { o = n; } 3781 forceinline void update(Space & home,LocalHandle & lh)3782 LocalHandle::update(Space& home, LocalHandle& lh) { 3783 object(lh.object()->fwd(home)); 3784 } 3785 3786 3787 /* 3788 * Choices 3789 * 3790 */ 3791 forceinline Choice(const Brancher & b,const unsigned int a)3792 Choice::Choice(const Brancher& b, const unsigned int a) 3793 : bid(b.id()), alt(a) {} 3794 3795 forceinline unsigned int alternatives(void) const3796 Choice::alternatives(void) const { 3797 return alt; 3798 } 3799 3800 forceinline unsigned int id(void) const3801 Choice::id(void) const { 3802 return bid; 3803 } 3804 3805 forceinline ~Choice(void)3806 Choice::~Choice(void) {} 3807 3808 3809 3810 /* 3811 * No-good literal 3812 * 3813 */ 3814 forceinline bool leaf(void) const3815 NGL::leaf(void) const { 3816 return Support::marked(nl); 3817 } 3818 forceinline NGL* next(void) const3819 NGL::next(void) const { 3820 return static_cast<NGL*>(Support::funmark(nl)); 3821 } 3822 forceinline void leaf(bool l)3823 NGL::leaf(bool l) { 3824 nl = l ? Support::fmark(nl) : Support::funmark(nl); 3825 } 3826 forceinline void next(NGL * n)3827 NGL::next(NGL* n) { 3828 nl = Support::marked(nl) ? Support::mark(n) : n; 3829 } 3830 forceinline NGL* add(NGL * n,bool l)3831 NGL::add(NGL* n, bool l) { 3832 nl = Support::marked(nl) ? Support::mark(n) : n; 3833 n->leaf(l); 3834 return n; 3835 } 3836 3837 forceinline NGL(void)3838 NGL::NGL(void) 3839 : nl(nullptr) {} 3840 forceinline NGL(Space &)3841 NGL::NGL(Space&) 3842 : nl(nullptr) {} 3843 forceinline NGL(Space &,NGL &)3844 NGL::NGL(Space&, NGL&) 3845 : nl(nullptr) {} 3846 forceinline size_t dispose(Space &)3847 NGL::dispose(Space&) { 3848 return sizeof(*this); 3849 } 3850 3851 /* 3852 * Advisor 3853 * 3854 */ 3855 template<class A> 3856 forceinline Advisor(Space &,Propagator & p,Council<A> & c)3857 Advisor::Advisor(Space&, Propagator& p, Council<A>& c) { 3858 // Store propagator and forwarding in prev() 3859 ActorLink::prev(&p); 3860 // Link to next advisor in next() 3861 ActorLink::next(c.advisors); c.advisors = static_cast<A*>(this); 3862 } 3863 3864 forceinline Advisor(Space &,Advisor &)3865 Advisor::Advisor(Space&, Advisor&) {} 3866 3867 forceinline bool disposed(void) const3868 Advisor::disposed(void) const { 3869 return prev() == nullptr; 3870 } 3871 3872 forceinline Advisor* cast(ActorLink * al)3873 Advisor::cast(ActorLink* al) { 3874 return static_cast<Advisor*>(al); 3875 } 3876 3877 forceinline const Advisor* cast(const ActorLink * al)3878 Advisor::cast(const ActorLink* al) { 3879 return static_cast<const Advisor*>(al); 3880 } 3881 3882 forceinline Propagator& propagator(void) const3883 Advisor::propagator(void) const { 3884 assert(!disposed()); 3885 return *Propagator::cast(ActorLink::prev()); 3886 } 3887 3888 template<class A> 3889 forceinline void dispose(Space &,Council<A> &)3890 Advisor::dispose(Space&,Council<A>&) { 3891 assert(!disposed()); 3892 ActorLink::prev(nullptr); 3893 // Shorten chains of disposed advisors by one, if possible 3894 Advisor* n = Advisor::cast(next()); 3895 if ((n != nullptr) && n->disposed()) 3896 next(n->next()); 3897 } 3898 3899 forceinline const ViewTraceInfo& operator ()(const Space & home) const3900 Advisor::operator ()(const Space& home) const { 3901 return home.pc.p.vti; 3902 } 3903 3904 template<class A> 3905 forceinline ExecStatus ES_FIX_DISPOSE(Council<A> & c,A & a)3906 Space::ES_FIX_DISPOSE(Council<A>& c, A& a) { 3907 a.dispose(*this,c); 3908 return ES_FIX; 3909 } 3910 3911 template<class A> 3912 forceinline ExecStatus ES_NOFIX_DISPOSE(Council<A> & c,A & a)3913 Space::ES_NOFIX_DISPOSE(Council<A>& c, A& a) { 3914 a.dispose(*this,c); 3915 return ES_NOFIX; 3916 } 3917 3918 template<class A> 3919 forceinline ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A> & c,A & a)3920 Space::ES_NOFIX_DISPOSE_FORCE(Council<A>& c, A& a) { 3921 a.dispose(*this,c); 3922 return ES_NOFIX_FORCE; 3923 } 3924 3925 3926 3927 /* 3928 * Advisor council 3929 * 3930 */ 3931 template<class A> 3932 forceinline Council(void)3933 Council<A>::Council(void) {} 3934 3935 template<class A> 3936 forceinline Council(Space &)3937 Council<A>::Council(Space&) 3938 : advisors(nullptr) {} 3939 3940 template<class A> 3941 forceinline bool empty(void) const3942 Council<A>::empty(void) const { 3943 ActorLink* a = advisors; 3944 while ((a != nullptr) && static_cast<A*>(a)->disposed()) 3945 a = a->next(); 3946 advisors = a; 3947 return a == nullptr; 3948 } 3949 3950 template<class A> 3951 forceinline void update(Space & home,Council<A> & c)3952 Council<A>::update(Space& home, Council<A>& c) { 3953 // Skip all disposed advisors 3954 { 3955 ActorLink* a = c.advisors; 3956 while ((a != nullptr) && static_cast<A*>(a)->disposed()) 3957 a = a->next(); 3958 c.advisors = a; 3959 } 3960 // Are there any advisors to be cloned? 3961 if (c.advisors != nullptr) { 3962 // The propagator in from-space 3963 Propagator* p_f = &static_cast<A*>(c.advisors)->propagator(); 3964 // The propagator in to-space 3965 Propagator* p_t = Propagator::cast(p_f->prev()); 3966 // Advisors in from-space 3967 ActorLink** a_f = &c.advisors; 3968 // Advisors in to-space 3969 A* a_t = nullptr; 3970 while (*a_f != nullptr) { 3971 if (static_cast<A*>(*a_f)->disposed()) { 3972 *a_f = (*a_f)->next(); 3973 } else { 3974 // Run specific copying part 3975 A* a = new (home) A(home,*static_cast<A*>(*a_f)); 3976 // Set propagator pointer 3977 a->prev(p_t); 3978 // Set forwarding pointer 3979 (*a_f)->prev(a); 3980 // Link 3981 a->next(a_t); 3982 a_t = a; 3983 a_f = (*a_f)->next_ref(); 3984 } 3985 } 3986 advisors = a_t; 3987 // Enter advisor link for reset 3988 assert(p_f->u.advisors == nullptr); 3989 p_f->u.advisors = c.advisors; 3990 } else { 3991 advisors = nullptr; 3992 } 3993 } 3994 3995 template<class A> 3996 forceinline void dispose(Space & home)3997 Council<A>::dispose(Space& home) { 3998 ActorLink* a = advisors; 3999 while (a != nullptr) { 4000 if (!static_cast<A*>(a)->disposed()) 4001 static_cast<A*>(a)->dispose(home,*this); 4002 a = a->next(); 4003 } 4004 } 4005 4006 4007 4008 /* 4009 * Advisor iterator 4010 * 4011 */ 4012 template<class A> 4013 forceinline Advisors(const Council<A> & c)4014 Advisors<A>::Advisors(const Council<A>& c) 4015 : a(c.advisors) { 4016 while ((a != nullptr) && static_cast<A*>(a)->disposed()) 4017 a = a->next(); 4018 } 4019 4020 template<class A> 4021 forceinline bool operator ()(void) const4022 Advisors<A>::operator ()(void) const { 4023 return a != nullptr; 4024 } 4025 4026 template<class A> 4027 forceinline void operator ++(void)4028 Advisors<A>::operator ++(void) { 4029 do { 4030 a = a->next(); 4031 } while ((a != nullptr) && static_cast<A*>(a)->disposed()); 4032 } 4033 4034 template<class A> 4035 forceinline A& advisor(void) const4036 Advisors<A>::advisor(void) const { 4037 return *static_cast<A*>(a); 4038 } 4039 4040 4041 4042 /* 4043 * Space 4044 * 4045 */ 4046 forceinline void enqueue(Propagator * p)4047 Space::enqueue(Propagator* p) { 4048 ActorLink::cast(p)->unlink(); 4049 ActorLink* c = &pc.p.queue[p->cost(*this,p->u.med).ac]; 4050 c->tail(ActorLink::cast(p)); 4051 if (c > pc.p.active) 4052 pc.p.active = c; 4053 } 4054 4055 forceinline void fail(void)4056 Space::fail(void) { 4057 pc.p.active = &pc.p.queue[PropCost::AC_MAX+1]+1; 4058 /* 4059 * Now active points beyond the last queue. This is essential as 4060 * enqueuing a propagator in a failed space keeps the space 4061 * failed. 4062 */ 4063 } 4064 forceinline void fail(void)4065 Home::fail(void) { 4066 s.fail(); 4067 } 4068 4069 forceinline bool failed(void) const4070 Space::failed(void) const { 4071 return pc.p.active > &pc.p.queue[PropCost::AC_MAX+1]; 4072 } 4073 forceinline bool failed(void) const4074 Home::failed(void) const { 4075 return s.failed(); 4076 } 4077 4078 forceinline bool stable(void) const4079 Space::stable(void) const { 4080 return ((pc.p.active < &pc.p.queue[0]) || 4081 (pc.p.active > &pc.p.queue[PropCost::AC_MAX+1])); 4082 } 4083 4084 forceinline void notice(Actor & a,ActorProperty p,bool d)4085 Space::notice(Actor& a, ActorProperty p, bool d) { 4086 if (p & AP_DISPOSE) { 4087 ap_notice_dispose(&a,d); 4088 } 4089 if (p & AP_VIEW_TRACE) { 4090 pc.p.bid_sc |= sc_trace; 4091 } 4092 if (p & AP_TRACE) { 4093 pc.p.bid_sc |= sc_trace; 4094 } 4095 // Currently unused 4096 if (p & AP_WEAKLY) { 4097 // Nothing to do 4098 } 4099 } 4100 4101 forceinline void ignore(Actor & a,ActorProperty p,bool d)4102 Space::ignore(Actor& a, ActorProperty p, bool d) { 4103 // Check whether array has already been discarded as space 4104 // deletion is already in progress 4105 if ((p & AP_DISPOSE) && (d_fst != nullptr)) 4106 ap_ignore_dispose(&a,d); 4107 if (p & AP_VIEW_TRACE) { 4108 // Nothing to do 4109 } 4110 if (p & AP_TRACE) { 4111 // Nothing to do 4112 } 4113 // Currently unused 4114 if (p & AP_WEAKLY) { 4115 // Nothing to do 4116 } 4117 } 4118 4119 4120 4121 /* 4122 * Variable implementation 4123 * 4124 */ 4125 template<class VIC> 4126 forceinline ActorLink** actor(PropCond pc)4127 VarImp<VIC>::actor(PropCond pc) { 4128 assert((pc >= 0) && (pc < pc_max+2)); 4129 return (pc == 0) ? b.base : b.base+u.idx[pc-1]; 4130 } 4131 4132 template<class VIC> 4133 forceinline ActorLink** actorNonZero(PropCond pc)4134 VarImp<VIC>::actorNonZero(PropCond pc) { 4135 assert((pc > 0) && (pc < pc_max+2)); 4136 return b.base+u.idx[pc-1]; 4137 } 4138 4139 template<class VIC> 4140 forceinline unsigned int& idx(PropCond pc)4141 VarImp<VIC>::idx(PropCond pc) { 4142 assert((pc > 0) && (pc < pc_max+2)); 4143 return u.idx[pc-1]; 4144 } 4145 4146 template<class VIC> 4147 forceinline unsigned int idx(PropCond pc) const4148 VarImp<VIC>::idx(PropCond pc) const { 4149 assert((pc > 0) && (pc < pc_max+2)); 4150 return u.idx[pc-1]; 4151 } 4152 4153 template<class VIC> 4154 forceinline VarImp(Space & home)4155 VarImp<VIC>::VarImp(Space& home) 4156 #ifdef GECODE_HAS_CBS 4157 : var_id(++home.var_id_counter) 4158 #endif 4159 { 4160 #ifndef GECODE_HAS_CBS 4161 (void) home; 4162 #endif 4163 b.base = nullptr; entries = 0; 4164 for (PropCond pc=1; pc<pc_max+2; pc++) 4165 idx(pc) = 0; 4166 free_and_bits = 0; 4167 } 4168 4169 template<class VIC> 4170 forceinline VarImp(void)4171 VarImp<VIC>::VarImp(void) 4172 #ifdef GECODE_HAS_CBS 4173 : var_id(0) 4174 #endif 4175 { 4176 b.base = nullptr; entries = 0; 4177 for (PropCond pc=1; pc<pc_max+2; pc++) 4178 idx(pc) = 0; 4179 free_and_bits = 0; 4180 } 4181 4182 #ifdef GECODE_HAS_CBS 4183 template<class VIC> 4184 forceinline unsigned int id(void) const4185 VarImp<VIC>::id(void) const { 4186 return var_id; 4187 } 4188 #endif 4189 4190 template<class VIC> 4191 forceinline unsigned int degree(void) const4192 VarImp<VIC>::degree(void) const { 4193 assert(!copied()); 4194 return entries; 4195 } 4196 4197 template<class VIC> 4198 forceinline double afc(void) const4199 VarImp<VIC>::afc(void) const { 4200 double d = 0.0; 4201 // Count the afc of each propagator 4202 { 4203 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actor(0); 4204 ActorLink** e = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1); 4205 while (a < e) { 4206 d += Propagator::cast(*a)->afc(); a++; 4207 } 4208 } 4209 // Count the afc of each advisor's propagator 4210 { 4211 ActorLink** a = const_cast<VarImp<VIC>*>(this)->actorNonZero(pc_max+1); 4212 ActorLink** e = const_cast<VarImp<VIC>*>(this)->b.base+entries; 4213 while (a < e) { 4214 d += Advisor::cast(static_cast<ActorLink*>(Support::funmark(*a))) 4215 ->propagator().afc(); 4216 a++; 4217 } 4218 } 4219 return d; 4220 } 4221 4222 template<class VIC> 4223 forceinline ModEvent modevent(const Delta & d)4224 VarImp<VIC>::modevent(const Delta& d) { 4225 return d.me; 4226 } 4227 4228 template<class VIC> 4229 forceinline unsigned int bits(void) const4230 VarImp<VIC>::bits(void) const { 4231 return free_and_bits; 4232 } 4233 4234 template<class VIC> 4235 forceinline unsigned int& bits(void)4236 VarImp<VIC>::bits(void) { 4237 return free_and_bits; 4238 } 4239 4240 #ifdef GECODE_HAS_VAR_DISPOSE 4241 template<class VIC> 4242 forceinline VarImp<VIC>* vars_d(Space & home)4243 VarImp<VIC>::vars_d(Space& home) { 4244 return static_cast<VarImp<VIC>*>(home.vars_d<VIC>()); 4245 } 4246 4247 template<class VIC> 4248 forceinline void vars_d(Space & home,VarImp<VIC> * x)4249 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) { 4250 home.vars_d<VIC>(x); 4251 } 4252 #endif 4253 4254 template<class VIC> 4255 forceinline bool copied(void) const4256 VarImp<VIC>::copied(void) const { 4257 return Support::marked(b.fwd); 4258 } 4259 4260 template<class VIC> 4261 forceinline VarImp<VIC>* forward(void) const4262 VarImp<VIC>::forward(void) const { 4263 assert(copied()); 4264 return static_cast<VarImp<VIC>*>(Support::unmark(b.fwd)); 4265 } 4266 4267 template<class VIC> 4268 forceinline VarImp<VIC>* next(void) const4269 VarImp<VIC>::next(void) const { 4270 assert(copied()); 4271 return u.next; 4272 } 4273 4274 template<class VIC> 4275 forceinline VarImp(Space & home,VarImp<VIC> & x)4276 VarImp<VIC>::VarImp(Space& home, VarImp<VIC>& x) 4277 #ifdef GECODE_HAS_CBS 4278 : var_id(x.var_id) 4279 #endif 4280 { 4281 VarImpBase** reg; 4282 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1); 4283 if (x.b.base == nullptr) { 4284 // Variable implementation needs no index structure 4285 reg = &home.pc.c.vars_noidx; 4286 assert(x.degree() == 0); 4287 } else { 4288 reg = &home.pc.c.vars_u[idx_c]; 4289 } 4290 // Save subscriptions in copy 4291 b.base = x.b.base; 4292 entries = x.entries; 4293 for (PropCond pc=1; pc<pc_max+2; pc++) 4294 idx(pc) = x.idx(pc); 4295 4296 // Set forwarding pointer 4297 x.b.fwd = static_cast<VarImp<VIC>*>(Support::mark(this)); 4298 // Register original 4299 x.u.next = static_cast<VarImp<VIC>*>(*reg); *reg = &x; 4300 } 4301 4302 template<class VIC> 4303 forceinline ModEvent me(const ModEventDelta & med)4304 VarImp<VIC>::me(const ModEventDelta& med) { 4305 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst); 4306 } 4307 4308 template<class VIC> 4309 forceinline ModEventDelta med(ModEvent me)4310 VarImp<VIC>::med(ModEvent me) { 4311 return static_cast<ModEventDelta>(me << VIC::med_fst); 4312 } 4313 4314 template<class VIC> 4315 forceinline ModEvent me_combine(ModEvent me1,ModEvent me2)4316 VarImp<VIC>::me_combine(ModEvent me1, ModEvent me2) { 4317 return VIC::me_combine(me1,me2); 4318 } 4319 4320 template<class VIC> 4321 forceinline void schedule(Space & home,Propagator & p,ModEvent me,bool force)4322 VarImp<VIC>::schedule(Space& home, Propagator& p, ModEvent me, 4323 bool force) { 4324 if (VIC::med_update(p.u.med,me) || force) 4325 home.enqueue(&p); 4326 } 4327 4328 template<class VIC> 4329 forceinline void schedule(Space & home,PropCond pc1,PropCond pc2,ModEvent me)4330 VarImp<VIC>::schedule(Space& home, PropCond pc1, PropCond pc2, ModEvent me) { 4331 ActorLink** b = actor(pc1); 4332 ActorLink** p = actorNonZero(pc2+1); 4333 while (p-- > b) 4334 schedule(home,*Propagator::cast(*p),me); 4335 } 4336 4337 template<class VIC> 4338 forceinline void resize(Space & home)4339 VarImp<VIC>::resize(Space& home) { 4340 if (b.base == nullptr) { 4341 assert((free_and_bits >> free_bits) == 0); 4342 // Create fresh dependency array with four entries 4343 free_and_bits += 4 << free_bits; 4344 b.base = home.alloc<ActorLink*>(4); 4345 for (int i=0; i<pc_max+1; i++) 4346 u.idx[i] = 0; 4347 } else { 4348 // Resize dependency array 4349 unsigned int n = degree(); 4350 // Find out whether the area is most likely in the special area 4351 // reserved for subscriptions. If yes, just resize mildly otherwise 4352 // more agressively 4353 ActorLink** s = static_cast<ActorLink**>(home.mm.subscriptions()); 4354 unsigned int m = 4355 ((s <= b.base) && (b.base < s+home.pc.p.n_sub)) ? 4356 (n+4) : ((n+1)*3>>1); 4357 ActorLink** prop = home.alloc<ActorLink*>(m); 4358 free_and_bits += (m-n) << free_bits; 4359 // Copy entries 4360 Heap::copy<ActorLink*>(prop, b.base, n); 4361 home.free<ActorLink*>(b.base,n); 4362 b.base = prop; 4363 } 4364 } 4365 4366 template<class VIC> 4367 forceinline void enter(Space & home,Propagator * p,PropCond pc)4368 VarImp<VIC>::enter(Space& home, Propagator* p, PropCond pc) { 4369 assert(pc <= pc_max); 4370 // Count one new subscription 4371 home.pc.p.n_sub += 1; 4372 if ((free_and_bits >> free_bits) == 0) 4373 resize(home); 4374 free_and_bits -= 1 << free_bits; 4375 4376 // Enter subscription 4377 b.base[entries] = *actorNonZero(pc_max+1); 4378 entries++; 4379 for (PropCond j = pc_max; j > pc; j--) { 4380 *actorNonZero(j+1) = *actorNonZero(j); 4381 idx(j+1)++; 4382 } 4383 *actorNonZero(pc+1) = *actor(pc); 4384 idx(pc+1)++; 4385 *actor(pc) = ActorLink::cast(p); 4386 4387 #ifdef GECODE_AUDIT 4388 ActorLink** f = actor(pc); 4389 while (f < (pc == pc_max+1 ? b.base+entries : actorNonZero(pc+1))) 4390 if (*f == p) 4391 goto found; 4392 else 4393 f++; 4394 GECODE_NEVER; 4395 found: ; 4396 #endif 4397 } 4398 4399 template<class VIC> 4400 forceinline void enter(Space & home,Advisor * a)4401 VarImp<VIC>::enter(Space& home, Advisor* a) { 4402 // Note that a might be a marked pointer 4403 // Count one new subscription 4404 home.pc.p.n_sub += 1; 4405 if ((free_and_bits >> free_bits) == 0) 4406 resize(home); 4407 free_and_bits -= 1 << free_bits; 4408 4409 // Enter subscription 4410 b.base[entries++] = *actorNonZero(pc_max+1); 4411 *actorNonZero(pc_max+1) = a; 4412 } 4413 4414 template<class VIC> 4415 forceinline void subscribe(Space & home,Propagator & p,PropCond pc,bool assigned,ModEvent me,bool schedule)4416 VarImp<VIC>::subscribe(Space& home, Propagator& p, PropCond pc, 4417 bool assigned, ModEvent me, bool schedule) { 4418 if (assigned) { 4419 // Do not subscribe, just schedule the propagator 4420 if (schedule) 4421 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED); 4422 } else { 4423 enter(home,&p,pc); 4424 // Schedule propagator 4425 if (schedule && (pc != PC_GEN_ASSIGNED)) 4426 VarImp<VIC>::schedule(home,p,me); 4427 } 4428 } 4429 4430 template<class VIC> 4431 forceinline void subscribe(Space & home,Advisor & a,bool assigned,bool fail)4432 VarImp<VIC>::subscribe(Space& home, Advisor& a, bool assigned, bool fail) { 4433 if (!assigned) { 4434 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0)); 4435 enter(home,ma); 4436 } 4437 } 4438 4439 template<class VIC> 4440 forceinline void reschedule(Space & home,Propagator & p,PropCond pc,bool assigned,ModEvent me)4441 VarImp<VIC>::reschedule(Space& home, Propagator& p, PropCond pc, 4442 bool assigned, ModEvent me) { 4443 if (assigned) 4444 VarImp<VIC>::schedule(home,p,ME_GEN_ASSIGNED); 4445 else if (pc != PC_GEN_ASSIGNED) 4446 VarImp<VIC>::schedule(home,p,me); 4447 } 4448 4449 template<class VIC> 4450 void remove(Space & home,Propagator * p,PropCond pc)4451 VarImp<VIC>::remove(Space& home, Propagator* p, PropCond pc) { 4452 assert(pc <= pc_max); 4453 ActorLink* a = ActorLink::cast(p); 4454 // Find actor in dependency array 4455 ActorLink** f = actor(pc); 4456 #ifdef GECODE_AUDIT 4457 while (f < actorNonZero(pc+1)) 4458 if (*f == a) 4459 goto found; 4460 else 4461 f++; 4462 GECODE_NEVER; 4463 found: ; 4464 #else 4465 while (*f != a) f++; 4466 #endif 4467 // Remove actor 4468 *f = *(actorNonZero(pc+1)-1); 4469 for (PropCond j = pc+1; j< pc_max+1; j++) { 4470 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1); 4471 idx(j)--; 4472 } 4473 *(actorNonZero(pc_max+1)-1) = b.base[entries-1]; 4474 idx(pc_max+1)--; 4475 entries--; 4476 free_and_bits += 1 << free_bits; 4477 home.pc.p.n_sub -= 1; 4478 } 4479 4480 template<class VIC> 4481 forceinline void cancel(Space & home,Propagator & p,PropCond pc)4482 VarImp<VIC>::cancel(Space& home, Propagator& p, PropCond pc) { 4483 if (b.base != nullptr) 4484 remove(home,&p,pc); 4485 } 4486 4487 template<class VIC> 4488 void remove(Space & home,Advisor * a)4489 VarImp<VIC>::remove(Space& home, Advisor* a) { 4490 // Note that a might be a marked pointer 4491 // Find actor in dependency array 4492 ActorLink** f = actorNonZero(pc_max+1); 4493 #ifdef GECODE_AUDIT 4494 while (f < b.base+entries) 4495 if (*f == a) 4496 goto found; 4497 else 4498 f++; 4499 GECODE_NEVER; 4500 found: ; 4501 #else 4502 while (*f != a) f++; 4503 #endif 4504 // Remove actor 4505 *f = b.base[--entries]; 4506 free_and_bits += 1 << free_bits; 4507 home.pc.p.n_sub -= 1; 4508 } 4509 4510 template<class VIC> 4511 forceinline void cancel(Space & home,Advisor & a,bool fail)4512 VarImp<VIC>::cancel(Space& home, Advisor& a, bool fail) { 4513 if (b.base != nullptr) { 4514 Advisor* ma = static_cast<Advisor*>(Support::ptrjoin(&a,fail ? 1 : 0)); 4515 remove(home,ma); 4516 } 4517 } 4518 4519 template<class VIC> 4520 forceinline void cancel(Space & home)4521 VarImp<VIC>::cancel(Space& home) { 4522 unsigned int n_sub = degree(); 4523 home.pc.p.n_sub -= n_sub; 4524 unsigned int n = (free_and_bits >> free_bits) + n_sub; 4525 home.free<ActorLink*>(b.base,n); 4526 // Must be nullptr such that cloning works 4527 b.base = nullptr; 4528 // Must be 0 such that degree works 4529 entries = 0; 4530 // Must be nullptr such that afc works 4531 for (PropCond pc=1; pc<pc_max+2; pc++) 4532 idx(pc) = 0; 4533 free_and_bits &= (1 << free_bits) - 1; 4534 } 4535 4536 template<class VIC> 4537 forceinline bool advise(Space & home,ModEvent me,Delta & d)4538 VarImp<VIC>::advise(Space& home, ModEvent me, Delta& d) { 4539 /* 4540 * An advisor that is executed might remove itself due to subsumption. 4541 * As entries are removed from front to back, the advisors must 4542 * be iterated in forward direction. 4543 */ 4544 ActorLink** la = actorNonZero(pc_max+1); 4545 ActorLink** le = b.base+entries; 4546 if (la == le) 4547 return true; 4548 d.me = me; 4549 // An advisor that is run, might be removed during execution. 4550 // As removal is done from the back the advisors have to be executed 4551 // in inverse order. 4552 do { 4553 Advisor* a = Advisor::cast 4554 (static_cast<ActorLink*>(Support::funmark(*la))); 4555 assert(!a->disposed()); 4556 Propagator& p = a->propagator(); 4557 switch (p.advise(home,*a,d)) { 4558 case ES_FIX: 4559 break; 4560 case ES_FAILED: 4561 return false; 4562 case ES_NOFIX: 4563 schedule(home,p,me); 4564 break; 4565 case ES_NOFIX_FORCE: 4566 schedule(home,p,me,true); 4567 break; 4568 case ES_SUBSUMED_: 4569 default: 4570 GECODE_NEVER; 4571 } 4572 } while (++la < le); 4573 return true; 4574 } 4575 4576 template<class VIC> 4577 void _fail(Space & home)4578 VarImp<VIC>::_fail(Space& home) { 4579 /* 4580 * An advisor that is executed might remove itself due to subsumption. 4581 * As entries are removed from front to back, the advisors must 4582 * be iterated in forward direction. 4583 */ 4584 ActorLink** la = actorNonZero(pc_max+1); 4585 ActorLink** le = b.base+entries; 4586 if (la == le) 4587 return; 4588 // An advisor that is run, might be removed during execution. 4589 // As removal is done from the back the advisors have to be executed 4590 // in inverse order. 4591 do { 4592 if (Support::marked(*la)) { 4593 Advisor* a = Advisor::cast(static_cast<ActorLink*> 4594 (Support::unmark(*la))); 4595 assert(!a->disposed()); 4596 Propagator& p = a->propagator(); 4597 p.advise(home,*a); 4598 } 4599 } while (++la < le); 4600 } 4601 4602 template<class VIC> 4603 ModEvent fail(Space & home)4604 VarImp<VIC>::fail(Space& home) { 4605 _fail(home); 4606 return ME_GEN_FAILED; 4607 } 4608 4609 // Clang incorrectly reports an error on the access to u.idx[1] for BoolVarImp, 4610 // even though the access is guarded by pc_max > 0 which implies that the size is sufficient. 4611 #pragma clang diagnostic push 4612 #pragma clang diagnostic ignored "-Warray-bounds" 4613 4614 template<class VIC> 4615 forceinline void update(VarImp<VIC> * x,ActorLink ** & sub)4616 VarImp<VIC>::update(VarImp<VIC>* x, ActorLink**& sub) { 4617 // this refers to the variable to be updated (clone) 4618 // x refers to the original 4619 // Recover from copy 4620 x->b.base = b.base; 4621 x->u.idx[0] = u.idx[0]; 4622 if (pc_max > 0 && sizeof(ActorLink**) > sizeof(unsigned int)) 4623 x->u.idx[1] = u.idx[1]; 4624 4625 unsigned int np = 4626 static_cast<unsigned int>(x->actorNonZero(pc_max+1) - x->actor(0)); 4627 unsigned int na = 4628 static_cast<unsigned int >(x->b.base + x->entries - 4629 x->actorNonZero(pc_max+1)); 4630 unsigned int n = na + np; 4631 assert(n == x->degree()); 4632 4633 ActorLink** f = x->b.base; 4634 ActorLink** t = sub; 4635 4636 sub += n; 4637 b.base = t; 4638 // Process propagator subscriptions 4639 while (np >= 4) { 4640 ActorLink* p3 = f[3]->prev(); 4641 ActorLink* p0 = f[0]->prev(); 4642 ActorLink* p1 = f[1]->prev(); 4643 ActorLink* p2 = f[2]->prev(); 4644 t[0] = p0; t[1] = p1; t[2] = p2; t[3] = p3; 4645 np -= 4; t += 4; f += 4; 4646 } 4647 if (np >= 2) { 4648 ActorLink* p0 = f[0]->prev(); 4649 ActorLink* p1 = f[1]->prev(); 4650 t[0] = p0; t[1] = p1; 4651 np -= 2; t += 2; f += 2; 4652 } 4653 if (np > 0) { 4654 ActorLink* p0 = f[0]->prev(); 4655 t[0] = p0; 4656 t += 1; f += 1; 4657 } 4658 // Process advisor subscriptions 4659 while (na >= 4) { 4660 ptrdiff_t m0, m1, m2, m3; 4661 ActorLink* p3 = 4662 static_cast<ActorLink*>(Support::ptrsplit(f[3],m3))->prev(); 4663 ActorLink* p0 = 4664 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev(); 4665 ActorLink* p1 = 4666 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev(); 4667 ActorLink* p2 = 4668 static_cast<ActorLink*>(Support::ptrsplit(f[2],m2))->prev(); 4669 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0)); 4670 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1)); 4671 t[2] = static_cast<ActorLink*>(Support::ptrjoin(p2,m2)); 4672 t[3] = static_cast<ActorLink*>(Support::ptrjoin(p3,m3)); 4673 na -= 4; t += 4; f += 4; 4674 } 4675 if (na >= 2) { 4676 ptrdiff_t m0, m1; 4677 ActorLink* p0 = 4678 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev(); 4679 ActorLink* p1 = 4680 static_cast<ActorLink*>(Support::ptrsplit(f[1],m1))->prev(); 4681 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0)); 4682 t[1] = static_cast<ActorLink*>(Support::ptrjoin(p1,m1)); 4683 na -= 2; t += 2; f += 2; 4684 } 4685 if (na > 0) { 4686 ptrdiff_t m0; 4687 ActorLink* p0 = 4688 static_cast<ActorLink*>(Support::ptrsplit(f[0],m0))->prev(); 4689 t[0] = static_cast<ActorLink*>(Support::ptrjoin(p0,m0)); 4690 } 4691 } 4692 #pragma clang diagnostic pop 4693 4694 template<class VIC> 4695 forceinline void update(Space & home,ActorLink ** & sub)4696 VarImp<VIC>::update(Space& home, ActorLink**& sub) { 4697 VarImp<VIC>* x = static_cast<VarImp<VIC>*>(home.pc.c.vars_u[idx_c]); 4698 while (x != nullptr) { 4699 VarImp<VIC>* n = x->next(); x->forward()->update(x,sub); x = n; 4700 } 4701 } 4702 4703 4704 4705 /* 4706 * Variable disposer 4707 * 4708 */ 4709 template<class VarImp> VarImpDisposer(void)4710 VarImpDisposer<VarImp>::VarImpDisposer(void) { 4711 #ifdef GECODE_HAS_VAR_DISPOSE 4712 Space::vd[VarImp::idx_d] = this; 4713 #endif 4714 } 4715 4716 template<class VarImp> 4717 void dispose(Space & home,VarImpBase * _x)4718 VarImpDisposer<VarImp>::dispose(Space& home, VarImpBase* _x) { 4719 VarImp* x = static_cast<VarImp*>(_x); 4720 do { 4721 x->dispose(home); x = static_cast<VarImp*>(x->next_d()); 4722 } while (x != nullptr); 4723 } 4724 4725 /* 4726 * Statistics 4727 */ 4728 4729 forceinline void reset(void)4730 StatusStatistics::reset(void) { 4731 propagate = 0; 4732 } 4733 forceinline StatusStatistics(void)4734 StatusStatistics::StatusStatistics(void) { 4735 reset(); 4736 } 4737 forceinline StatusStatistics& operator +=(const StatusStatistics & s)4738 StatusStatistics::operator +=(const StatusStatistics& s) { 4739 propagate += s.propagate; 4740 return *this; 4741 } 4742 forceinline StatusStatistics operator +(const StatusStatistics & s)4743 StatusStatistics::operator +(const StatusStatistics& s) { 4744 StatusStatistics t(s); 4745 return t += *this; 4746 } 4747 4748 forceinline void reset(void)4749 CloneStatistics::reset(void) {} 4750 4751 forceinline CloneStatistics(void)4752 CloneStatistics::CloneStatistics(void) { 4753 reset(); 4754 } 4755 forceinline CloneStatistics operator +(const CloneStatistics &)4756 CloneStatistics::operator +(const CloneStatistics&) { 4757 CloneStatistics s; 4758 return s; 4759 } 4760 forceinline CloneStatistics& operator +=(const CloneStatistics &)4761 CloneStatistics::operator +=(const CloneStatistics&) { 4762 return *this; 4763 } 4764 4765 forceinline void reset(void)4766 CommitStatistics::reset(void) {} 4767 4768 forceinline CommitStatistics(void)4769 CommitStatistics::CommitStatistics(void) { 4770 reset(); 4771 } 4772 forceinline CommitStatistics operator +(const CommitStatistics &)4773 CommitStatistics::operator +(const CommitStatistics&) { 4774 CommitStatistics s; 4775 return s; 4776 } 4777 forceinline CommitStatistics& operator +=(const CommitStatistics &)4778 CommitStatistics::operator +=(const CommitStatistics&) { 4779 return *this; 4780 } 4781 4782 /* 4783 * Cost computation 4784 * 4785 */ 4786 4787 forceinline PropCost(PropCost::ActualCost ac0)4788 PropCost::PropCost(PropCost::ActualCost ac0) : ac(ac0) {} 4789 4790 forceinline PropCost cost(PropCost::Mod m,PropCost::ActualCost lo,PropCost::ActualCost hi,unsigned int n)4791 PropCost::cost(PropCost::Mod m, 4792 PropCost::ActualCost lo, PropCost::ActualCost hi, 4793 unsigned int n) { 4794 if (n < 2) 4795 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI; 4796 else if (n == 2) 4797 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI; 4798 else if (n == 3) 4799 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI; 4800 else 4801 return (m == LO) ? lo : hi; 4802 } 4803 4804 forceinline PropCost record(void)4805 PropCost::record(void) { 4806 return AC_RECORD; 4807 } 4808 forceinline PropCost crazy(PropCost::Mod m,unsigned int n)4809 PropCost::crazy(PropCost::Mod m, unsigned int n) { 4810 return cost(m,AC_CRAZY_LO,AC_CRAZY_HI,n); 4811 } 4812 forceinline PropCost crazy(PropCost::Mod m,int n)4813 PropCost::crazy(PropCost::Mod m, int n) { 4814 assert(n >= 0); 4815 return crazy(m,static_cast<unsigned int>(n)); 4816 } 4817 forceinline PropCost cubic(PropCost::Mod m,unsigned int n)4818 PropCost::cubic(PropCost::Mod m, unsigned int n) { 4819 return cost(m,AC_CUBIC_LO,AC_CUBIC_HI,n); 4820 } 4821 forceinline PropCost cubic(PropCost::Mod m,int n)4822 PropCost::cubic(PropCost::Mod m, int n) { 4823 assert(n >= 0); 4824 return cubic(m,static_cast<unsigned int>(n)); 4825 } 4826 forceinline PropCost quadratic(PropCost::Mod m,unsigned int n)4827 PropCost::quadratic(PropCost::Mod m, unsigned int n) { 4828 return cost(m,AC_QUADRATIC_LO,AC_QUADRATIC_HI,n); 4829 } 4830 forceinline PropCost quadratic(PropCost::Mod m,int n)4831 PropCost::quadratic(PropCost::Mod m, int n) { 4832 assert(n >= 0); 4833 return quadratic(m,static_cast<unsigned int>(n)); 4834 } 4835 forceinline PropCost linear(PropCost::Mod m,unsigned int n)4836 PropCost::linear(PropCost::Mod m, unsigned int n) { 4837 return cost(m,AC_LINEAR_LO,AC_LINEAR_HI,n); 4838 } 4839 forceinline PropCost linear(PropCost::Mod m,int n)4840 PropCost::linear(PropCost::Mod m, int n) { 4841 assert(n >= 0); 4842 return linear(m,static_cast<unsigned int>(n)); 4843 } 4844 forceinline PropCost ternary(PropCost::Mod m)4845 PropCost::ternary(PropCost::Mod m) { 4846 return (m == LO) ? AC_TERNARY_LO : AC_TERNARY_HI; 4847 } 4848 forceinline PropCost binary(PropCost::Mod m)4849 PropCost::binary(PropCost::Mod m) { 4850 return (m == LO) ? AC_BINARY_LO : AC_BINARY_HI; 4851 } 4852 forceinline PropCost unary(PropCost::Mod m)4853 PropCost::unary(PropCost::Mod m) { 4854 return (m == LO) ? AC_UNARY_LO : AC_UNARY_HI; 4855 } 4856 4857 /* 4858 * Iterators for propagators and branchers of a space 4859 * 4860 */ 4861 forceinline Propagators(Space & home0)4862 Space::Propagators::Propagators(Space& home0) 4863 : home(home0), q(home.pc.p.active) { 4864 while (q >= &home.pc.p.queue[0]) { 4865 if (q->next() != q) { 4866 c = q->next(); e = q; q--; 4867 return; 4868 } 4869 q--; 4870 } 4871 q = nullptr; 4872 if (!home.pl.empty()) { 4873 c = Propagator::cast(home.pl.next()); 4874 e = Propagator::cast(&home.pl); 4875 } else { 4876 c = e = nullptr; 4877 } 4878 } 4879 forceinline bool operator ()(void) const4880 Space::Propagators::operator ()(void) const { 4881 return c != nullptr; 4882 } 4883 forceinline void operator ++(void)4884 Space::Propagators::operator ++(void) { 4885 c = c->next(); 4886 if (c == e) { 4887 if (q == nullptr) { 4888 c = nullptr; 4889 } else { 4890 while (q >= &home.pc.p.queue[0]) { 4891 if (q->next() != q) { 4892 c = q->next(); e = q; q--; 4893 return; 4894 } 4895 q--; 4896 } 4897 q = nullptr; 4898 if (!home.pl.empty()) { 4899 c = Propagator::cast(home.pl.next()); 4900 e = Propagator::cast(&home.pl); 4901 } else { 4902 c = nullptr; 4903 } 4904 } 4905 } 4906 } 4907 forceinline Propagator& propagator(void) const4908 Space::Propagators::propagator(void) const { 4909 return *Propagator::cast(c); 4910 } 4911 4912 4913 forceinline ScheduledPropagators(Space & home0)4914 Space::ScheduledPropagators::ScheduledPropagators(Space& home0) 4915 : home(home0), q(home.pc.p.active) { 4916 while (q >= &home.pc.p.queue[0]) { 4917 if (q->next() != q) { 4918 c = q->next(); e = q; q--; 4919 return; 4920 } 4921 q--; 4922 } 4923 q = c = e = nullptr; 4924 } 4925 forceinline bool operator ()(void) const4926 Space::ScheduledPropagators::operator ()(void) const { 4927 return c != nullptr; 4928 } 4929 forceinline void operator ++(void)4930 Space::ScheduledPropagators::operator ++(void) { 4931 c = c->next(); 4932 if (c == e) { 4933 if (q == nullptr) { 4934 c = nullptr; 4935 } else { 4936 while (q >= &home.pc.p.queue[0]) { 4937 if (q->next() != q) { 4938 c = q->next(); e = q; q--; 4939 return; 4940 } 4941 q--; 4942 } 4943 q = c = e = nullptr; 4944 } 4945 } 4946 } 4947 forceinline Propagator& propagator(void) const4948 Space::ScheduledPropagators::propagator(void) const { 4949 return *Propagator::cast(c); 4950 } 4951 4952 4953 forceinline IdlePropagators(Space & home)4954 Space::IdlePropagators::IdlePropagators(Space& home) { 4955 c = Propagator::cast(home.pl.next()); 4956 e = Propagator::cast(&home.pl); 4957 } 4958 forceinline bool operator ()(void) const4959 Space::IdlePropagators::operator ()(void) const { 4960 return c != e; 4961 } 4962 forceinline void operator ++(void)4963 Space::IdlePropagators::operator ++(void) { 4964 c = c->next(); 4965 } 4966 forceinline Propagator& propagator(void) const4967 Space::IdlePropagators::propagator(void) const { 4968 return *Propagator::cast(c); 4969 } 4970 4971 4972 forceinline Branchers(Space & home)4973 Space::Branchers::Branchers(Space& home) 4974 : c(Brancher::cast(home.bl.next())), e(&home.bl) {} 4975 forceinline bool operator ()(void) const4976 Space::Branchers::operator ()(void) const { 4977 return c != e; 4978 } 4979 forceinline void operator ++(void)4980 Space::Branchers::operator ++(void) { 4981 c = c->next(); 4982 } 4983 forceinline Brancher& brancher(void) const4984 Space::Branchers::brancher(void) const { 4985 return *Brancher::cast(c); 4986 } 4987 4988 4989 /* 4990 * Groups of actors 4991 */ 4992 forceinline Group(unsigned int gid0)4993 Group::Group(unsigned int gid0) : gid(gid0) {} 4994 4995 forceinline bool in(Group actor) const4996 Group::in(Group actor) const { 4997 return (gid == GROUPID_ALL) || (gid == actor.gid); 4998 } 4999 5000 forceinline bool in(void) const5001 Group::in(void) const { 5002 return (gid != GROUPID_ALL) && (gid != GROUPID_DEF); 5003 } 5004 5005 forceinline Group(const Group & g)5006 Group::Group(const Group& g) : gid(g.gid) {} 5007 5008 forceinline Group& operator =(const Group & g)5009 Group::operator =(const Group& g) { 5010 gid=g.gid; return *this; 5011 } 5012 5013 forceinline unsigned int id(void) const5014 Group::id(void) const { 5015 return gid; 5016 } 5017 5018 5019 forceinline PropagatorGroup(void)5020 PropagatorGroup::PropagatorGroup(void) {} 5021 5022 forceinline PropagatorGroup(unsigned int gid)5023 PropagatorGroup::PropagatorGroup(unsigned int gid) 5024 : Group(gid) {} 5025 5026 forceinline PropagatorGroup(const PropagatorGroup & g)5027 PropagatorGroup::PropagatorGroup(const PropagatorGroup& g) 5028 : Group(g) {} 5029 5030 forceinline PropagatorGroup& operator =(const PropagatorGroup & g)5031 PropagatorGroup::operator =(const PropagatorGroup& g) { 5032 return static_cast<PropagatorGroup&>(Group::operator =(g)); 5033 } 5034 5035 forceinline Home operator ()(Space & home)5036 PropagatorGroup::operator ()(Space& home) { 5037 return Home(home,nullptr,*this,BrancherGroup::def); 5038 } 5039 5040 forceinline bool operator ==(PropagatorGroup g) const5041 PropagatorGroup::operator ==(PropagatorGroup g) const { 5042 return id() == g.id(); 5043 } 5044 forceinline bool operator !=(PropagatorGroup g) const5045 PropagatorGroup::operator !=(PropagatorGroup g) const { 5046 return id() != g.id(); 5047 } 5048 5049 forceinline PropagatorGroup& move(Space &,Propagator & p)5050 PropagatorGroup::move(Space& , Propagator& p) { 5051 if (id() != GROUPID_ALL) 5052 p.group(*this); 5053 return *this; 5054 } 5055 5056 5057 forceinline BrancherGroup(void)5058 BrancherGroup::BrancherGroup(void) {} 5059 5060 forceinline BrancherGroup(unsigned int gid)5061 BrancherGroup::BrancherGroup(unsigned int gid) 5062 : Group(gid) {} 5063 5064 forceinline BrancherGroup(const BrancherGroup & g)5065 BrancherGroup::BrancherGroup(const BrancherGroup& g) 5066 : Group(g) {} 5067 5068 forceinline BrancherGroup& operator =(const BrancherGroup & g)5069 BrancherGroup::operator =(const BrancherGroup& g) { 5070 return static_cast<BrancherGroup&>(Group::operator =(g)); 5071 } 5072 5073 forceinline Home operator ()(Space & home)5074 BrancherGroup::operator ()(Space& home) { 5075 return Home(home,nullptr,PropagatorGroup::def,*this); 5076 } 5077 5078 forceinline bool operator ==(BrancherGroup g) const5079 BrancherGroup::operator ==(BrancherGroup g) const { 5080 return id() == g.id(); 5081 } 5082 forceinline bool operator !=(BrancherGroup g) const5083 BrancherGroup::operator !=(BrancherGroup g) const { 5084 return id() != g.id(); 5085 } 5086 5087 forceinline BrancherGroup& move(Space &,Brancher & p)5088 BrancherGroup::move(Space& , Brancher& p) { 5089 if (id() != GROUPID_ALL) 5090 p.group(*this); 5091 return *this; 5092 } 5093 5094 5095 /* 5096 * Iterators for propagators and branchers in a group 5097 * 5098 */ 5099 forceinline Propagators(const Space & home,PropagatorGroup g0)5100 Propagators::Propagators(const Space& home, PropagatorGroup g0) 5101 : ps(const_cast<Space&>(home)), g(g0) { 5102 while (ps() && !g.in(ps.propagator().group())) 5103 ++ps; 5104 } 5105 forceinline bool operator ()(void) const5106 Propagators::operator ()(void) const { 5107 return ps(); 5108 } 5109 forceinline void operator ++(void)5110 Propagators::operator ++(void) { 5111 do 5112 ++ps; 5113 while (ps() && !g.in(ps.propagator().group())); 5114 } 5115 forceinline const Propagator& propagator(void) const5116 Propagators::propagator(void) const { 5117 return ps.propagator(); 5118 } 5119 5120 forceinline Branchers(const Space & home,BrancherGroup g0)5121 Branchers::Branchers(const Space& home, BrancherGroup g0) 5122 : bs(const_cast<Space&>(home)), g(g0) { 5123 while (bs() && !g.in(bs.brancher().group())) 5124 ++bs; 5125 } 5126 forceinline bool operator ()(void) const5127 Branchers::operator ()(void) const { 5128 return bs(); 5129 } 5130 forceinline void operator ++(void)5131 Branchers::operator ++(void) { 5132 do 5133 ++bs; 5134 while (bs() && !g.in(bs.brancher().group())); 5135 } 5136 forceinline const Brancher& brancher(void) const5137 Branchers::brancher(void) const { 5138 return bs.brancher(); 5139 } 5140 5141 5142 /* 5143 * Space construction support 5144 * 5145 */ 5146 template<class T> 5147 forceinline T& construct(void)5148 Space::construct(void) { 5149 return alloc<T>(1); 5150 } 5151 template<class T, typename A1> 5152 forceinline T& construct(A1 const & a1)5153 Space::construct(A1 const& a1) { 5154 T& t = *static_cast<T*>(ralloc(sizeof(T))); 5155 new (&t) T(a1); 5156 return t; 5157 } 5158 template<class T, typename A1, typename A2> 5159 forceinline T& construct(A1 const & a1,A2 const & a2)5160 Space::construct(A1 const& a1, A2 const& a2) { 5161 T& t = *static_cast<T*>(ralloc(sizeof(T))); 5162 new (&t) T(a1,a2); 5163 return t; 5164 } 5165 template<class T, typename A1, typename A2, typename A3> 5166 forceinline T& construct(A1 const & a1,A2 const & a2,A3 const & a3)5167 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3) { 5168 T& t = *static_cast<T*>(ralloc(sizeof(T))); 5169 new (&t) T(a1,a2,a3); 5170 return t; 5171 } 5172 template<class T, typename A1, typename A2, typename A3, typename A4> 5173 forceinline T& construct(A1 const & a1,A2 const & a2,A3 const & a3,A4 const & a4)5174 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4) { 5175 T& t = *static_cast<T*>(ralloc(sizeof(T))); 5176 new (&t) T(a1,a2,a3,a4); 5177 return t; 5178 } 5179 template<class T, typename A1, typename A2, typename A3, typename A4, typename A5> 5180 forceinline T& construct(A1 const & a1,A2 const & a2,A3 const & a3,A4 const & a4,A5 const & a5)5181 Space::construct(A1 const& a1, A2 const& a2, A3 const& a3, A4 const& a4, A5 const& a5) { 5182 T& t = *static_cast<T*>(ralloc(sizeof(T))); 5183 new (&t) T(a1,a2,a3,a4,a5); 5184 return t; 5185 } 5186 5187 } 5188 5189 // STATISTICS: kernel-core 5190