104 static void*
operator new(
size_t s);
106 static void operator delete(
void*
p);
263 template<
class VarImp>
314 static const int idx_c = VIC::idx_c;
316 static const int idx_d = VIC::idx_d;
318 static const int free_bits = VIC::free_bits;
320 unsigned int entries;
322 unsigned int free_and_bits;
337 unsigned int idx[pc_max+1];
371 void resize(
Space& home);
387 #ifdef GECODE_HAS_VAR_DISPOSE
442 unsigned int degree(
void)
const;
449 double afc(
const Space& home)
const;
492 unsigned int bits(
void)
const;
494 unsigned int&
bits(
void);
505 static void*
operator new(size_t,
Space&);
507 static void operator delete(
void*,
Space&);
509 static void operator delete(
void*);
652 bool empty(
void)
const;
682 virtual Actor* copy(
Space& home,
bool share) = 0;
688 virtual size_t allocated(
void)
const;
691 virtual size_t dispose(
Space& home);
693 static void*
operator new(
size_t s,
Space& home);
695 static void operator delete(
void*
p,
Space& home);
699 static void operator delete(
void*
p);
702 static void*
operator new(
size_t s);
709 static void operator delete(
void*
p);
732 operator Space&(void);
861 double afc(
const Space& home)
const;
886 bool empty(
void)
const;
931 bool disposed(
void)
const;
952 static void*
operator new(
size_t s,
Space& home);
954 static void operator delete(
void*
p,
Space& home);
959 static void operator delete(
void*
p);
962 static void*
operator new(
size_t s);
982 unsigned int id(
void)
const;
988 unsigned int alternatives(
void)
const;
992 virtual size_t size(
void)
const = 0;
994 static void*
operator new(size_t);
996 static void operator delete(
void*);
1037 virtual bool status(
const Space& home)
const = 0;
1055 unsigned int a) = 0;
1057 unsigned int id(
void)
const;
1081 unsigned int id(
void)
const;
1256 Brancher* brancher(
unsigned int id);
1259 void kill_brancher(
unsigned int id);
1261 static const unsigned reserved_branch_id = 0U;
1298 void enqueue(Propagator*
p);
1303 #ifdef GECODE_HAS_VAR_DISPOSE
1309 template<
class VIC> VarImpBase* vars_d(
void)
const;
1311 template<
class VIC>
void vars_d(VarImpBase*
x);
1314 void update(ActorLink** sub);
1337 unsigned int _wmp_afc;
1339 void afc_enable(
void);
1341 bool afc_enabled(
void)
const;
1343 void wmp(
unsigned int n);
1345 unsigned int wmp(
void)
const;
1407 void _commit(
const Choice&
c,
unsigned int a);
1411 void afc_decay(
double d);
1413 double afc_decay(
void)
const;
1442 virtual Space* copy(
bool share) = 0;
1467 virtual void master(
unsigned long int i,
const Space* s);
1481 virtual void slave(
unsigned long int i,
const Space* s);
1486 static void*
operator new(size_t);
1491 static void operator delete(
void*);
1511 SpaceStatus status(StatusStatistics& stat=unused_status);
1545 const Choice* choice(
void);
1557 const Choice* choice(Archive& e)
const;
1579 Space*
clone(
bool share=
true, CloneStatistics& stat=unused_clone)
const;
1615 void commit(
const Choice&
c,
unsigned int a,
1616 CommitStatistics& stat=unused_commit);
1661 ExecStatus ES_SUBSUMED_DISPOSED(Propagator&
p,
size_t s);
1721 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>&
c, A&
a);
1739 bool failed(
void)
const;
1744 bool stable(
void)
const;
1763 Home operator ()(Propagator&
p);
1778 T* alloc(
long unsigned int n);
1786 T* alloc(
long int n);
1794 T* alloc(
unsigned int n);
1813 void free(T*
b,
long unsigned int n);
1824 void free(T*
b,
long int n);
1835 void free(T*
b,
unsigned int n);
1846 void free(T*
b,
int n);
1859 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
1872 T* realloc(T*
b,
long int n,
long int m);
1885 T* realloc(T*
b,
unsigned int n,
unsigned int m);
1898 T* realloc(T*
b,
int n,
int m);
1907 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
1916 T** realloc(T**
b,
long int n,
long int m);
1925 T** realloc(T**
b,
unsigned int n,
unsigned int m);
1934 T** realloc(T**
b,
int n,
int m);
1936 void* ralloc(
size_t s);
1938 void rfree(
void*
p,
size_t s);
1940 void* rrealloc(
void*
b,
size_t n,
size_t m);
1942 template<
size_t>
void* fl_alloc(
void);
1948 template<
size_t>
void fl_dispose(FreeList* f, FreeList*
l);
1955 size_t allocated(
void)
const;
1978 template<
class T,
typename A1>
1979 T& construct(A1
const& a1);
1985 template<
class T,
typename A1,
typename A2>
1986 T& construct(A1
const& a1, A2
const& a2);
1992 template<
class T,
typename A1,
typename A2,
typename A3>
1993 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
1999 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
2000 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
2006 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
2007 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
2029 bool operator ()(
void)
const;
2031 void operator ++(
void);
2051 bool operator ()(
void)
const;
2053 void operator ++(
void);
2055 const Brancher& brancher(
void)
const;
2069 SharedHandle::Object::operator
new(
size_t s) {
2073 SharedHandle::Object::operator
delete(
void*
p) {
2078 Space::operator
new(
size_t s) {
2082 Space::operator
delete(
void*
p) {
2087 Choice::operator
delete(
void*
p) {
2091 Choice::operator
new(
size_t s) {
2098 return mm.
alloc(sm,s);
2102 return mm.
reuse(p,s);
2106 char*
b =
static_cast<char*
>(
_b);
2108 char*
p =
static_cast<char*
>(
ralloc(m));
2121 return mm.template fl_alloc<s>(sm);
2126 mm.template fl_dispose<s>(f,
l);
2132 for (
Actor**
a = d_fst;
a < d_cur;
a++)
2133 s += (*a)->allocated();
2144 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*n));
2145 for (
long unsigned int i=n;
i--; )
2146 (
void)
new (p+
i) T();
2153 return alloc<T>(
static_cast<long unsigned int>(
n));
2158 return alloc<T>(
static_cast<long unsigned int>(
n));
2164 return alloc<T>(
static_cast<long unsigned int>(
n));
2170 for (
long unsigned int i=n;
i--; )
2172 rfree(b,n*
sizeof(T));
2178 free<T>(
b,
static_cast<long unsigned int>(
n));
2183 free<T>(
b,
static_cast<long unsigned int>(
n));
2189 free<T>(
b,
static_cast<long unsigned int>(
n));
2196 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*m));
2197 for (
long unsigned int i=n;
i--; )
2198 (
void)
new (p+
i) T(b[
i]);
2199 for (
long unsigned int i=n; i<m; i++)
2200 (
void)
new (p+
i) T();
2211 assert((n >= 0) && (m >= 0));
2212 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2213 static_cast<long unsigned int>(m));
2218 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2219 static_cast<long unsigned int>(m));
2224 assert((n >= 0) && (m >= 0));
2225 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2226 static_cast<long unsigned int>(m));
2229 #define GECODE_KERNEL_REALLOC(T) \
2232 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2233 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2237 Space::realloc<T>(T* b, long int n, long int m) { \
2238 assert((n >= 0) && (m >= 0)); \
2239 return realloc<T>(b,static_cast<long unsigned int>(n), \
2240 static_cast<long unsigned int>(m)); \
2244 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2245 return realloc<T>(b,static_cast<long unsigned int>(n), \
2246 static_cast<long unsigned int>(m)); \
2250 Space::realloc<T>(T* b, int n, int m) { \
2251 assert((n >= 0) && (m >= 0)); \
2252 return realloc<T>(b,static_cast<long unsigned int>(n), \
2253 static_cast<long unsigned int>(m)); \
2268 #undef GECODE_KERNEL_REALLOC
2273 return static_cast<T**
>(
rrealloc(b,n*
sizeof(T),m*
sizeof(T*)));
2278 assert((n >= 0) && (m >= 0));
2279 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2280 static_cast<long unsigned int>(m));
2285 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2286 static_cast<long unsigned int>(m));
2291 assert((n >= 0) && (m >= 0));
2292 return realloc<T*>(
b,
static_cast<long unsigned int>(
n),
2293 static_cast<long unsigned int>(m));
2297 #ifdef GECODE_HAS_VAR_DISPOSE
2300 Space::vars_d(
void)
const {
2301 return _vars_d[VIC::idx_d];
2305 Space::vars_d(VarImpBase*
x) {
2306 _vars_d[VIC::idx_d] =
x;
2312 Actor::operator
delete(
void*) {}
2314 Actor::operator
delete(
void*,
Space&) {}
2316 Actor::operator
new(
size_t s,
Space& home) {
2317 return home.ralloc(s);
2329 return home.ralloc(s);
2334 Advisor::operator
delete(
void*) {}
2337 Advisor::operator
delete(
void*,
Space&) {}
2339 Advisor::operator
new(
size_t s,
Space& home) {
2340 return home.ralloc(s);
2349 : next(NULL), fwd(NULL), use_cnt(0) {}
2352 assert(use_cnt == 0);
2360 SharedHandle::subscribe(
void) {
2361 if (o != NULL) o->use_cnt++;
2364 SharedHandle::cancel(
void) {
2365 if ((o != NULL) && (--o->use_cnt == 0))
2372 cancel(); o=
n; subscribe();
2388 cancel(); o=sh.o; subscribe();
2398 }
else if (sh.o->fwd != NULL) {
2403 sh.o->next = home.pc.
c.shared;
2404 home.pc.
c.shared = sh.o;
2447 p->_next =
n; n->_prev =
p;
2452 _next =
this; _prev =
this;
2459 this->_next =
a; a->_prev =
this;
2460 a->_next =
n; n->_prev =
a;
2467 a->_next =
this; this->_prev =
a;
2468 p->_next =
a; a->_prev =
p;
2473 return _next ==
this;
2504 return static_cast<Actor*
>(&
t);
2508 Actor::cast(
const ActorLink* al) {
2512 return static_cast<const Actor*
>(&
t);
2516 Space::afc_enable(
void) {
2520 Space::afc_enabled(
void)
const {
2521 return (_wmp_afc & 1U) != 0U;
2524 Space::wmp(
unsigned int n) {
2525 _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2528 Space::wmp(
void)
const {
2529 return _wmp_afc >> 1U;
2575 return const_cast<Space*
>(
this)->_clone(share);
2584 Space::afc_decay(
void)
const {
2585 return gafc.
decay();
2590 return sizeof(*this);
2615 return Home(*
this,&p);
2635 Propagator::cast(
const ActorLink* al) {
2644 : gafc((home.propagator() != NULL) ?
2646 home.propagator()->gafc :
2648 static_cast<
Space&>(home).gafc.allocate()) {
2650 assert((u.med == 0) && (u.size == 0));
2651 static_cast<Space&
>(home).pl.head(
this);
2658 assert((u.med == 0) && (u.size == 0));
2670 return const_cast<Space&
>(home).gafc.afc(gafc);
2688 assert(p.u.
med != 0);
2695 assert(p.u.
med != 0);
2714 Brancher::cast(
const ActorLink* al) {
2718 return static_cast<const Brancher*
>(&
t);
2723 _id(static_cast<
Space&>(home).pc.
p.branch_id++) {
2724 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2727 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2728 static_cast<Space&
>(home).b_status =
this;
2729 if (static_cast<Space&>(home).b_commit == &
static_cast<Space&
>(home).bl)
2730 static_cast<Space&
>(home).b_commit =
this;
2732 static_cast<Space&
>(home).bl.tail(
this);
2748 Space::brancher(
unsigned int id) {
2765 while (b_commit != Brancher::cast(&bl))
2766 if (
id != b_commit->
id())
2767 b_commit = Brancher::cast(b_commit->next());
2770 if (b_commit == Brancher::cast(&bl)) {
2772 b_commit = Brancher::cast(bl.
next());
2773 while (b_commit != b_old)
2774 if (
id != b_commit->
id())
2775 b_commit = Brancher::cast(b_commit->next());
2788 : _id(
Space::reserved_branch_id) {}
2802 return const_cast<Space&
>(home).brancher(_id) != NULL;
2806 home.kill_brancher(_id);
2844 fwdcopy(home,share);
2877 : _id(b.id()), _alt(a) {}
2885 Choice::id(
void)
const {
2911 Advisor::disposed(
void)
const {
2912 return prev() == NULL;
2916 Advisor::cast(ActorLink* al) {
2917 return static_cast<Advisor*
>(al);
2921 Advisor::cast(
const ActorLink* al) {
2922 return static_cast<const Advisor*
>(al);
2927 assert(!disposed());
2934 assert(!disposed());
2938 if ((n != NULL) && n->disposed())
2982 while ((a != NULL) && static_cast<A*>(a)->disposed())
2994 while ((a != NULL) && static_cast<A*>(a)->disposed())
2999 if (c.advisors != NULL) {
3001 Propagator* p_f = &
static_cast<A*
>(c.advisors)->propagator();
3003 Propagator* p_t = Propagator::cast(p_f->prev());
3008 while (*a_f != NULL) {
3009 if (static_cast<A*>(*a_f)->disposed()) {
3010 *a_f = (*a_f)->next();
3013 A*
a =
new (home) A(home,share,*static_cast<A*>(*a_f));
3021 a_f = (*a_f)->next_ref();
3038 if (!static_cast<A*>(a)->disposed())
3039 static_cast<A*
>(
a)->dispose(home,*
this);
3054 while ((a != NULL) && static_cast<A*>(a)->disposed())
3069 }
while ((
a != NULL) && static_cast<A*>(
a)->disposed());
3075 return *
static_cast<A*
>(
a);
3089 if (c > pc.p.active)
3118 return ((pc.p.active < &pc.p.queue[0]) ||
3131 assert((pc >= 0) && (pc < pc_max+2));
3132 return (pc == 0) ?
b.base :
b.base+
u.idx[pc-1];
3137 VarImp<VIC>::actorNonZero(
PropCond pc) {
3138 assert((pc > 0) && (pc < pc_max+2));
3139 return b.base+
u.idx[pc-1];
3145 assert((pc > 0) && (pc < pc_max+2));
3152 assert((pc > 0) && (pc < pc_max+2));
3159 b.base = NULL; entries = 0;
3160 for (
PropCond pc=1; pc<pc_max+2; pc++)
3168 b.base = NULL; entries = 0;
3169 for (
PropCond pc=1; pc<pc_max+2; pc++)
3190 d += Propagator::cast(*a)->afc(home); a++;
3198 d += Advisor::cast(*a)->propagator().afc(home); a++;
3213 return free_and_bits;
3219 return free_and_bits;
3222 #ifdef GECODE_HAS_VAR_DISPOSE
3226 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
3231 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>*
x) {
3232 home.vars_d<VIC>(
x);
3260 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3261 if (x.b.
base == NULL) {
3263 reg = &home.pc.
c.vars_noidx;
3266 reg = &home.pc.
c.vars_u[idx_c];
3270 entries = x.entries;
3271 for (
PropCond pc=1; pc<pc_max+2; pc++)
3272 idx(pc) = x.
idx(pc);
3283 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3295 return VIC::me_combine(me1,me2);
3302 if (VIC::med_update(p.u.
med,me) || force)
3312 schedule(home,*Propagator::cast(*p),me);
3318 assert(pc <= pc_max);
3320 home.pc.
p.n_sub += 1;
3321 if ((free_and_bits >> free_bits) == 0)
3323 free_and_bits -= 1 << free_bits;
3326 b.base[entries] = *actorNonZero(pc_max+1);
3328 for (
PropCond j = pc_max; j > pc; j--) {
3329 *actorNonZero(j+1) = *actorNonZero(j);
3332 *actorNonZero(pc+1) = *actor(pc);
3337 ActorLink** f = actor(pc);
3338 while (f < (pc == pc_max+1 ?
b.base+entries : actorNonZero(pc+1)))
3350 VarImp<VIC>::enter(Space& home, Advisor*
a) {
3352 home.pc.p.n_sub += 1;
3353 if ((free_and_bits >> free_bits) == 0)
3355 free_and_bits -= 1 << free_bits;
3358 b.base[entries++] = *actorNonZero(pc_max+1);
3359 *actorNonZero(pc_max+1) =
a;
3364 VarImp<VIC>::resize(Space& home) {
3365 if (
b.base == NULL) {
3366 assert((free_and_bits >> free_bits) == 0);
3368 free_and_bits += 4 << free_bits;
3369 b.base = home.alloc<ActorLink*>(4);
3370 for (
int i=0;
i<pc_max+1;
i++)
3374 unsigned int n = degree();
3378 ActorLink** s =
static_cast<ActorLink**
>(home.mm.subscriptions());
3380 ((s <=
b.base) && (
b.base < s+home.pc.p.n_sub)) ?
3381 (n+4) : ((n+1)*3>>1);
3382 ActorLink** prop = home.alloc<ActorLink*>(m);
3383 free_and_bits += (m-
n) << free_bits;
3385 Heap::copy<ActorLink*>(prop,
b.base,
n);
3386 home.free<ActorLink*>(
b.base,
n);
3417 assert(pc <= pc_max);
3422 while (f < actorNonZero(pc+1))
3430 while (*f != a) f++;
3433 *f = *(actorNonZero(pc+1)-1);
3434 for (
PropCond j = pc+1; j< pc_max+1; j++) {
3435 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3438 *(actorNonZero(pc_max+1)-1) =
b.base[entries-1];
3441 free_and_bits += 1 << free_bits;
3442 home.pc.
p.n_sub -= 1;
3447 VarImp<VIC>::remove(Space& home, Advisor* a) {
3449 ActorLink** f = actorNonZero(pc_max+1);
3451 while (f <
b.base+entries)
3459 while (*f != a) f++;
3462 *f =
b.base[--entries];
3463 free_and_bits += 1 << free_bits;
3464 home.pc.p.n_sub -= 1;
3484 unsigned int n_sub = degree();
3485 home.pc.
p.n_sub -= n_sub;
3486 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3502 ActorLink** la = actorNonZero(pc_max+1);
3511 Advisor* a = Advisor::cast(*la);
3512 assert(!a->disposed());
3514 switch (p.advise(home,*a,d)) {
3518 if (home.afc_enabled())
3519 home.gafc.
fail(p.gafc);
3522 schedule(home,p,me);
3525 schedule(home,p,me,
true);
3530 }
while (++la < le);
3541 x->u.
idx[0] =
u.idx[0];
3542 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
3543 x->u.
idx[1] =
u.idx[1];
3546 unsigned int n = x->
degree();
3553 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3554 t[2]=f[2]->
prev(); t[3]=f[3]->
prev();
3559 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3569 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3570 VarImp<VIC>* x =
static_cast<VarImp<VIC>*
>(home.pc.c.vars_u[idx_c]);
3572 VarImp<VIC>* n = x->
next(); x->forward()->update(x,sub); x =
n;
3582 template<
class VarImp>
3584 #ifdef GECODE_HAS_VAR_DISPOSE
3585 Space::vd[VarImp::idx_d] =
this;
3589 template<
class VarImp>
3594 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
3595 }
while (x != NULL);
3676 return (m ==
LO) ? lo : hi;
3686 return crazy(m,static_cast<unsigned int>(n));
3695 return cubic(m,static_cast<unsigned int>(n));
3704 return quadratic(m,static_cast<unsigned int>(n));
3713 return linear(m,static_cast<unsigned int>(n));
3734 : home(home0), q(home.pc.p.active) {
3735 while (q >= &home.pc.p.queue[0]) {
3736 if (q->
next() != q) {
3737 c = q->
next(); e = q; q--;
3743 if (!home.pl.empty()) {
3744 c = Propagator::cast(home.pl.next());
3745 e = Propagator::cast(&home.pl);
3761 while (q >= &home.pc.p.queue[0]) {
3762 if (q->next() != q) {
3763 c = q->
next(); e = q; q--;
3769 if (!home.pl.empty()) {
3770 c = Propagator::cast(home.pl.next());
3771 e = Propagator::cast(&home.pl);
3780 return *Propagator::cast(c);
3785 : c(
Brancher::cast(home.bl.next())), e(&home.bl) {}
3796 return *Brancher::cast(c);
3808 template<
class T,
typename A1>
3811 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3815 template<
class T,
typename A1,
typename A2>
3818 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3822 template<
class T,
typename A1,
typename A2,
typename A3>
3825 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3826 new (&
t) T(a1,a2,a3);
3829 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
3832 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3833 new (&
t) T(a1,a2,a3,a4);
3836 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
3839 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3840 new (&
t) T(a1,a2,a3,a4,a5);