106 static void*
operator new(
size_t s);
108 static void operator delete(
void*
p);
265 template<
class VarImp>
316 static const int idx_c = VIC::idx_c;
318 static const int idx_d = VIC::idx_d;
320 static const int free_bits = VIC::free_bits;
322 unsigned int entries;
324 unsigned int free_and_bits;
339 unsigned int idx[pc_max+1];
373 void resize(
Space& home);
389 #ifdef GECODE_HAS_VAR_DISPOSE
444 unsigned int degree(
void)
const;
451 double afc(
const Space& home)
const;
493 unsigned int bits(
void)
const;
496 unsigned int&
bits(
void);
506 static void*
operator new(size_t,
Space&);
509 static void operator delete(
void*,
Space&);
511 static void operator delete(
void*);
654 bool empty(
void)
const;
684 virtual Actor* copy(
Space& home,
bool share) = 0;
690 virtual size_t dispose(
Space& home);
692 static void*
operator new(
size_t s,
Space& home);
694 static void operator delete(
void*
p,
Space& home);
697 static void operator delete(
void*
p);
700 static void*
operator new(
size_t s);
708 static void operator delete(
void*
p);
731 operator Space&(void);
861 double afc(
const Space& home)
const;
887 bool empty(
void)
const;
932 bool disposed(
void)
const;
953 static void*
operator new(
size_t s,
Space& home);
955 static void operator delete(
void*
p,
Space& home);
959 static void operator delete(
void*
p);
962 static void*
operator new(
size_t s);
997 virtual NGL* copy(
Space& home,
bool share) = 0;
1000 virtual bool notice(
void)
const;
1002 virtual size_t dispose(
Space& home);
1005 bool leaf(
void)
const;
1008 NGL* next(
void)
const;
1018 static void*
operator new(
size_t s,
Space& home);
1021 static void operator delete(
void* s,
Space& home);
1023 static void operator delete(
void*
p);
1043 unsigned int id(
void)
const;
1049 unsigned int alternatives(
void)
const;
1053 virtual size_t size(
void)
const = 0;
1055 static void*
operator new(size_t);
1057 static void operator delete(
void*);
1090 unsigned int id(
void)
const;
1100 virtual bool status(
const Space& home)
const = 0;
1118 unsigned int a) = 0;
1145 std::ostream& o)
const;
1169 unsigned int id(
void)
const;
1243 unsigned long int n;
1251 unsigned long int ng(
void)
const;
1253 void ng(
unsigned long int n);
1367 Brancher* brancher(
unsigned int id);
1370 void kill_brancher(
unsigned int id);
1372 static const unsigned reserved_branch_id = 0U;
1409 void enqueue(Propagator*
p);
1414 #ifdef GECODE_HAS_VAR_DISPOSE
1420 template<
class VIC> VarImpBase* vars_d(
void)
const;
1422 template<
class VIC>
void vars_d(VarImpBase*
x);
1424 void update(ActorLink** sub);
1446 unsigned int _wmp_afc;
1448 void afc_enable(
void);
1450 bool afc_enabled(
void)
const;
1452 void wmp(
unsigned int n);
1454 unsigned int wmp(
void)
const;
1516 void _commit(
const Choice&
c,
unsigned int a);
1549 void _trycommit(
const Choice&
c,
unsigned int a);
1579 virtual Space* copy(
bool share) = 0;
1605 virtual void master(
unsigned long int i,
const Space* s,
1620 virtual void slave(
unsigned long int i,
const Space* s);
1625 static void*
operator new(size_t);
1630 static void operator delete(
void*);
1650 SpaceStatus status(StatusStatistics& stat=unused_status);
1684 const Choice* choice(
void);
1696 const Choice* choice(Archive& e)
const;
1718 Space*
clone(
bool share=
true, CloneStatistics& stat=unused_clone)
const;
1754 void commit(
const Choice&
c,
unsigned int a,
1755 CommitStatistics& stat=unused_commit);
1788 void trycommit(
const Choice&
c,
unsigned int a,
1789 CommitStatistics& stat=unused_commit);
1809 NGL* ngl(
const Choice&
c,
unsigned int a);
1826 void print(
const Choice&
c,
unsigned int a, std::ostream& o)
const;
1874 ExecStatus ES_SUBSUMED_DISPOSED(Propagator&
p,
size_t s);
1934 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>&
c, A&
a);
1952 bool failed(
void)
const;
1957 bool stable(
void)
const;
1975 Home operator ()(Propagator&
p);
1991 T* alloc(
long unsigned int n);
1999 T* alloc(
long int n);
2007 T* alloc(
unsigned int n);
2026 void free(T*
b,
long unsigned int n);
2037 void free(T*
b,
long int n);
2048 void free(T*
b,
unsigned int n);
2059 void free(T*
b,
int n);
2072 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
2085 T* realloc(T*
b,
long int n,
long int m);
2098 T* realloc(T*
b,
unsigned int n,
unsigned int m);
2111 T* realloc(T*
b,
int n,
int m);
2120 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
2129 T** realloc(T**
b,
long int n,
long int m);
2138 T** realloc(T**
b,
unsigned int n,
unsigned int m);
2147 T** realloc(T**
b,
int n,
int m);
2149 void* ralloc(
size_t s);
2151 void rfree(
void*
p,
size_t s);
2153 void* rrealloc(
void*
b,
size_t n,
size_t m);
2155 template<
size_t>
void* fl_alloc(
void);
2161 template<
size_t>
void fl_dispose(FreeList* f, FreeList*
l);
2184 template<
class T,
typename A1>
2185 T& construct(A1
const& a1);
2191 template<
class T,
typename A1,
typename A2>
2192 T& construct(A1
const& a1, A2
const& a2);
2198 template<
class T,
typename A1,
typename A2,
typename A3>
2199 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
2205 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
2206 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
2212 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
2213 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
2235 bool operator ()(
void)
const;
2237 void operator ++(
void);
2257 bool operator ()(
void)
const;
2259 void operator ++(
void);
2261 const Brancher& brancher(
void)
const;
2268 void afc_decay(
double d);
2270 double afc_decay(
void)
const;
2273 void afc_set(
double a);
2287 SharedHandle::Object::operator
new(
size_t s) {
2291 SharedHandle::Object::operator
delete(
void*
p) {
2296 Space::operator
new(
size_t s) {
2300 Space::operator
delete(
void*
p) {
2305 Choice::operator
delete(
void*
p) {
2309 Choice::operator
new(
size_t s) {
2317 return mm.
alloc(sm,s);
2321 return mm.
reuse(p,s);
2325 char*
b =
static_cast<char*
>(
_b);
2327 char*
p =
static_cast<char*
>(
ralloc(m));
2340 return mm.template fl_alloc<s>(sm);
2345 mm.template fl_dispose<s>(f,
l);
2355 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*n));
2356 for (
long unsigned int i=n;
i--; )
2357 (
void)
new (p+
i) T();
2364 return alloc<T>(
static_cast<long unsigned int>(
n));
2369 return alloc<T>(
static_cast<long unsigned int>(
n));
2375 return alloc<T>(
static_cast<long unsigned int>(
n));
2381 for (
long unsigned int i=n;
i--; )
2383 rfree(b,n*
sizeof(T));
2389 free<T>(
b,
static_cast<long unsigned int>(
n));
2394 free<T>(
b,
static_cast<long unsigned int>(
n));
2400 free<T>(
b,
static_cast<long unsigned int>(
n));
2407 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*m));
2408 for (
long unsigned int i=n;
i--; )
2409 (
void)
new (p+
i) T(b[
i]);
2410 for (
long unsigned int i=n; i<m; i++)
2411 (
void)
new (p+
i) T();
2422 assert((n >= 0) && (m >= 0));
2423 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2424 static_cast<long unsigned int>(m));
2429 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2430 static_cast<long unsigned int>(m));
2435 assert((n >= 0) && (m >= 0));
2436 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2437 static_cast<long unsigned int>(m));
2440 #define GECODE_KERNEL_REALLOC(T) \
2443 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2444 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2448 Space::realloc<T>(T* b, long int n, long int m) { \
2449 assert((n >= 0) && (m >= 0)); \
2450 return realloc<T>(b,static_cast<long unsigned int>(n), \
2451 static_cast<long unsigned int>(m)); \
2455 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2456 return realloc<T>(b,static_cast<long unsigned int>(n), \
2457 static_cast<long unsigned int>(m)); \
2461 Space::realloc<T>(T* b, int n, int m) { \
2462 assert((n >= 0) && (m >= 0)); \
2463 return realloc<T>(b,static_cast<long unsigned int>(n), \
2464 static_cast<long unsigned int>(m)); \
2479 #undef GECODE_KERNEL_REALLOC
2484 return static_cast<T**
>(
rrealloc(b,n*
sizeof(T),m*
sizeof(T*)));
2489 assert((n >= 0) && (m >= 0));
2490 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2491 static_cast<long unsigned int>(m));
2496 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2497 static_cast<long unsigned int>(m));
2502 assert((n >= 0) && (m >= 0));
2503 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2504 static_cast<long unsigned int>(m));
2508 #ifdef GECODE_HAS_VAR_DISPOSE
2511 Space::vars_d(
void)
const {
2512 return _vars_d[VIC::idx_d];
2516 Space::vars_d(VarImpBase*
x) {
2517 _vars_d[VIC::idx_d] =
x;
2523 Actor::operator
delete(
void*) {}
2525 Actor::operator
delete(
void*,
Space&) {}
2527 Actor::operator
new(
size_t s,
Space& home) {
2528 return home.ralloc(s);
2540 return home.ralloc(s);
2545 Advisor::operator
delete(
void*) {}
2548 Advisor::operator
delete(
void*,
Space&) {}
2550 Advisor::operator
new(
size_t s,
Space& home) {
2551 return home.ralloc(s);
2555 NGL::operator
delete(
void*) {}
2559 NGL::operator
new(
size_t s,
Space& home) {
2560 return home.ralloc(s);
2569 : next(NULL), fwd(NULL), use_cnt(0) {}
2572 assert(use_cnt == 0);
2580 SharedHandle::subscribe(
void) {
2581 if (o != NULL) o->use_cnt++;
2584 SharedHandle::cancel(
void) {
2585 if ((o != NULL) && (--o->use_cnt == 0))
2592 cancel(); o=
n; subscribe();
2608 cancel(); o=sh.o; subscribe();
2618 }
else if (sh.o->fwd != NULL) {
2623 sh.o->next = home.pc.
c.shared;
2624 home.pc.
c.shared = sh.o;
2686 p->_next =
n; n->_prev =
p;
2691 _next =
this; _prev =
this;
2698 this->_next =
a; a->_prev =
this;
2699 a->_next =
n; n->_prev =
a;
2706 a->_next =
this; this->_prev =
a;
2707 p->_next =
a; a->_prev =
p;
2712 return _next ==
this;
2743 return static_cast<Actor*
>(&
t);
2747 Actor::cast(
const ActorLink* al) {
2751 return static_cast<const Actor*
>(&
t);
2755 Space::afc_enable(
void) {
2759 Space::afc_enabled(
void)
const {
2760 return (_wmp_afc & 1U) != 0U;
2763 Space::wmp(
unsigned int n) {
2764 _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2767 Space::wmp(
void)
const {
2768 return _wmp_afc >> 1U;
2781 return const_cast<Space*
>(
this)->_clone(share);
2796 return gafc.
decay();
2801 return sizeof(*this);
2826 return Home(*
this,&p);
2846 Propagator::cast(
const ActorLink* al) {
2860 : gafc((home.propagator() != NULL) ?
2862 home.propagator()->gafc :
2864 static_cast<
Space&>(home).gafc.allocate()) {
2866 assert((u.med == 0) && (u.size == 0));
2867 static_cast<Space&
>(home).pl.head(
this);
2874 assert((u.med == 0) && (u.size == 0));
2886 return const_cast<Space&
>(home).gafc.afc(gafc);
2904 assert(p.u.
med != 0);
2911 assert(p.u.
med != 0);
2930 Brancher::cast(
const ActorLink* al) {
2934 return static_cast<const Brancher*
>(&
t);
2939 _id(static_cast<
Space&>(home).pc.
p.branch_id++) {
2940 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2943 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2944 static_cast<Space&
>(home).b_status =
this;
2945 if (static_cast<Space&>(home).b_commit == &
static_cast<Space&
>(home).bl)
2946 static_cast<Space&
>(home).b_commit =
this;
2948 static_cast<Space&
>(home).bl.tail(
this);
2964 Space::brancher(
unsigned int id) {
2981 while (b_commit != Brancher::cast(&bl))
2982 if (
id != b_commit->
id())
2983 b_commit = Brancher::cast(b_commit->next());
2986 if (b_commit == Brancher::cast(&bl)) {
2988 b_commit = Brancher::cast(bl.
next());
2989 while (b_commit != b_old)
2990 if (
id != b_commit->
id())
2991 b_commit = Brancher::cast(b_commit->next());
3004 : _id(
Space::reserved_branch_id) {}
3018 return const_cast<Space&
>(home).brancher(_id) != NULL;
3022 home.kill_brancher(_id);
3060 fwdcopy(home,share);
3093 : _id(b.id()), _alt(a) {}
3101 Choice::id(
void)
const {
3148 return sizeof(*this);
3168 Advisor::disposed(
void)
const {
3169 return prev() == NULL;
3173 Advisor::cast(ActorLink* al) {
3174 return static_cast<Advisor*
>(al);
3178 Advisor::cast(
const ActorLink* al) {
3179 return static_cast<const Advisor*
>(al);
3184 assert(!disposed());
3191 assert(!disposed());
3195 if ((n != NULL) && n->disposed())
3239 while ((a != NULL) && static_cast<A*>(a)->disposed())
3251 while ((a != NULL) && static_cast<A*>(a)->disposed())
3256 if (c.advisors != NULL) {
3258 Propagator* p_f = &
static_cast<A*
>(c.advisors)->propagator();
3260 Propagator* p_t = Propagator::cast(p_f->prev());
3265 while (*a_f != NULL) {
3266 if (static_cast<A*>(*a_f)->disposed()) {
3267 *a_f = (*a_f)->next();
3270 A*
a =
new (home) A(home,share,*static_cast<A*>(*a_f));
3278 a_f = (*a_f)->next_ref();
3295 if (!static_cast<A*>(a)->disposed())
3296 static_cast<A*
>(
a)->dispose(home,*
this);
3311 while ((a != NULL) && static_cast<A*>(a)->disposed())
3326 }
while ((
a != NULL) && static_cast<A*>(
a)->disposed());
3332 return *
static_cast<A*
>(
a);
3346 if (c > pc.p.active)
3375 return ((pc.p.active < &pc.p.queue[0]) ||
3388 assert((pc >= 0) && (pc < pc_max+2));
3389 return (pc == 0) ?
b.base :
b.base+
u.idx[pc-1];
3394 VarImp<VIC>::actorNonZero(
PropCond pc) {
3395 assert((pc > 0) && (pc < pc_max+2));
3396 return b.base+
u.idx[pc-1];
3402 assert((pc > 0) && (pc < pc_max+2));
3409 assert((pc > 0) && (pc < pc_max+2));
3416 b.base = NULL; entries = 0;
3417 for (
PropCond pc=1; pc<pc_max+2; pc++)
3425 b.base = NULL; entries = 0;
3426 for (
PropCond pc=1; pc<pc_max+2; pc++)
3447 d += Propagator::cast(*a)->afc(home); a++;
3455 d += Advisor::cast(*a)->propagator().afc(home); a++;
3470 return free_and_bits;
3476 return free_and_bits;
3479 #ifdef GECODE_HAS_VAR_DISPOSE
3483 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
3488 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>*
x) {
3489 home.vars_d<VIC>(
x);
3517 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3518 if (x.b.
base == NULL) {
3520 reg = &home.pc.
c.vars_noidx;
3523 reg = &home.pc.
c.vars_u[idx_c];
3527 entries = x.entries;
3528 for (
PropCond pc=1; pc<pc_max+2; pc++)
3529 idx(pc) = x.
idx(pc);
3540 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3552 return VIC::me_combine(me1,me2);
3559 if (VIC::med_update(p.u.
med,me) || force)
3569 schedule(home,*Propagator::cast(*p),me);
3575 assert(pc <= pc_max);
3577 home.pc.
p.n_sub += 1;
3578 if ((free_and_bits >> free_bits) == 0)
3580 free_and_bits -= 1 << free_bits;
3583 b.base[entries] = *actorNonZero(pc_max+1);
3585 for (
PropCond j = pc_max; j > pc; j--) {
3586 *actorNonZero(j+1) = *actorNonZero(j);
3589 *actorNonZero(pc+1) = *actor(pc);
3594 ActorLink** f = actor(pc);
3595 while (f < (pc == pc_max+1 ?
b.base+entries : actorNonZero(pc+1)))
3607 VarImp<VIC>::enter(Space& home, Advisor*
a) {
3609 home.pc.p.n_sub += 1;
3610 if ((free_and_bits >> free_bits) == 0)
3612 free_and_bits -= 1 << free_bits;
3615 b.base[entries++] = *actorNonZero(pc_max+1);
3616 *actorNonZero(pc_max+1) =
a;
3621 VarImp<VIC>::resize(Space& home) {
3622 if (
b.base == NULL) {
3623 assert((free_and_bits >> free_bits) == 0);
3625 free_and_bits += 4 << free_bits;
3626 b.base = home.alloc<ActorLink*>(4);
3627 for (
int i=0;
i<pc_max+1;
i++)
3631 unsigned int n = degree();
3635 ActorLink** s =
static_cast<ActorLink**
>(home.mm.subscriptions());
3637 ((s <=
b.base) && (
b.base < s+home.pc.p.n_sub)) ?
3638 (n+4) : ((n+1)*3>>1);
3639 ActorLink** prop = home.alloc<ActorLink*>(m);
3640 free_and_bits += (m-
n) << free_bits;
3642 Heap::copy<ActorLink*>(prop,
b.base,
n);
3643 home.free<ActorLink*>(
b.base,
n);
3674 assert(pc <= pc_max);
3679 while (f < actorNonZero(pc+1))
3687 while (*f != a) f++;
3690 *f = *(actorNonZero(pc+1)-1);
3691 for (
PropCond j = pc+1; j< pc_max+1; j++) {
3692 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3695 *(actorNonZero(pc_max+1)-1) =
b.base[entries-1];
3698 free_and_bits += 1 << free_bits;
3699 home.pc.
p.n_sub -= 1;
3704 VarImp<VIC>::remove(Space& home, Advisor* a) {
3706 ActorLink** f = actorNonZero(pc_max+1);
3708 while (f <
b.base+entries)
3716 while (*f != a) f++;
3719 *f =
b.base[--entries];
3720 free_and_bits += 1 << free_bits;
3721 home.pc.p.n_sub -= 1;
3741 unsigned int n_sub = degree();
3742 home.pc.
p.n_sub -= n_sub;
3743 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3759 ActorLink** la = actorNonZero(pc_max+1);
3768 Advisor* a = Advisor::cast(*la);
3769 assert(!a->disposed());
3771 switch (p.advise(home,*a,d)) {
3775 if (home.afc_enabled())
3776 home.gafc.
fail(p.gafc);
3779 schedule(home,p,me);
3782 schedule(home,p,me,
true);
3787 }
while (++la < le);
3798 x->u.
idx[0] =
u.idx[0];
3799 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
3800 x->u.
idx[1] =
u.idx[1];
3803 unsigned int n = x->
degree();
3810 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3811 t[2]=f[2]->
prev(); t[3]=f[3]->
prev();
3816 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3826 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3827 VarImp<VIC>* x =
static_cast<VarImp<VIC>*
>(home.pc.c.vars_u[idx_c]);
3829 VarImp<VIC>* n = x->
next(); x->forward()->update(x,sub); x =
n;
3839 template<
class VarImp>
3841 #ifdef GECODE_HAS_VAR_DISPOSE
3842 Space::vd[VarImp::idx_d] =
this;
3846 template<
class VarImp>
3851 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
3852 }
while (x != NULL);
3933 return (m ==
LO) ? lo : hi;
3943 return crazy(m,static_cast<unsigned int>(n));
3952 return cubic(m,static_cast<unsigned int>(n));
3961 return quadratic(m,static_cast<unsigned int>(n));
3970 return linear(m,static_cast<unsigned int>(n));
3991 : home(home0), q(home.pc.p.active) {
3992 while (q >= &home.pc.p.queue[0]) {
3993 if (q->
next() != q) {
3994 c = q->
next(); e = q; q--;
4000 if (!home.pl.empty()) {
4001 c = Propagator::cast(home.pl.next());
4002 e = Propagator::cast(&home.pl);
4018 while (q >= &home.pc.p.queue[0]) {
4019 if (q->next() != q) {
4020 c = q->
next(); e = q; q--;
4026 if (!home.pl.empty()) {
4027 c = Propagator::cast(home.pl.next());
4028 e = Propagator::cast(&home.pl);
4037 return *Propagator::cast(c);
4042 : c(
Brancher::cast(home.bl.next())), e(&home.bl) {}
4053 return *Brancher::cast(c);
4065 template<
class T,
typename A1>
4068 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4072 template<
class T,
typename A1,
typename A2>
4075 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4079 template<
class T,
typename A1,
typename A2,
typename A3>
4082 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4083 new (&
t) T(a1,a2,a3);
4086 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
4089 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4090 new (&
t) T(a1,a2,a3,a4);
4093 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
4096 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4097 new (&
t) T(a1,a2,a3,a4,a5);