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);
859 double afc(
const Space& home)
const;
885 bool empty(
void)
const;
930 bool disposed(
void)
const;
951 static void*
operator new(
size_t s,
Space& home);
953 static void operator delete(
void*
p,
Space& home);
957 static void operator delete(
void*
p);
960 static void*
operator new(
size_t s);
995 virtual NGL* copy(
Space& home,
bool share) = 0;
998 virtual bool notice(
void)
const;
1000 virtual size_t dispose(
Space& home);
1003 bool leaf(
void)
const;
1006 NGL* next(
void)
const;
1016 static void*
operator new(
size_t s,
Space& home);
1019 static void operator delete(
void* s,
Space& home);
1021 static void operator delete(
void*
p);
1041 unsigned int id(
void)
const;
1047 unsigned int alternatives(
void)
const;
1051 virtual size_t size(
void)
const = 0;
1053 static void*
operator new(size_t);
1055 static void operator delete(
void*);
1088 unsigned int id(
void)
const;
1098 virtual bool status(
const Space& home)
const = 0;
1116 unsigned int a) = 0;
1143 std::ostream& o)
const;
1167 unsigned int id(
void)
const;
1241 unsigned long int n;
1249 unsigned long int ng(
void)
const;
1251 void ng(
unsigned long int n);
1365 Brancher* brancher(
unsigned int id);
1368 void kill_brancher(
unsigned int id);
1370 static const unsigned reserved_branch_id = 0U;
1407 void enqueue(Propagator*
p);
1412 #ifdef GECODE_HAS_VAR_DISPOSE
1418 template<
class VIC> VarImpBase* vars_d(
void)
const;
1420 template<
class VIC>
void vars_d(VarImpBase*
x);
1422 void update(ActorLink** sub);
1444 unsigned int _wmp_afc;
1446 void afc_enable(
void);
1448 bool afc_enabled(
void)
const;
1450 void wmp(
unsigned int n);
1452 unsigned int wmp(
void)
const;
1514 void _commit(
const Choice&
c,
unsigned int a);
1544 virtual Space* copy(
bool share) = 0;
1570 virtual void master(
unsigned long int i,
const Space* s,
1585 virtual void slave(
unsigned long int i,
const Space* s);
1590 static void*
operator new(size_t);
1595 static void operator delete(
void*);
1615 SpaceStatus status(StatusStatistics& stat=unused_status);
1649 const Choice* choice(
void);
1661 const Choice* choice(Archive& e)
const;
1683 Space*
clone(
bool share=
true, CloneStatistics& stat=unused_clone)
const;
1719 void commit(
const Choice&
c,
unsigned int a,
1720 CommitStatistics& stat=unused_commit);
1742 NGL* ngl(
const Choice&
c,
unsigned int a);
1759 void print(
const Choice&
c,
unsigned int a, std::ostream& o)
const;
1807 ExecStatus ES_SUBSUMED_DISPOSED(Propagator&
p,
size_t s);
1867 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>&
c, A&
a);
1885 bool failed(
void)
const;
1890 bool stable(
void)
const;
1908 Home operator ()(Propagator&
p);
1924 T* alloc(
long unsigned int n);
1932 T* alloc(
long int n);
1940 T* alloc(
unsigned int n);
1959 void free(T*
b,
long unsigned int n);
1970 void free(T*
b,
long int n);
1981 void free(T*
b,
unsigned int n);
1992 void free(T*
b,
int n);
2005 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
2018 T* realloc(T*
b,
long int n,
long int m);
2031 T* realloc(T*
b,
unsigned int n,
unsigned int m);
2044 T* realloc(T*
b,
int n,
int m);
2053 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
2062 T** realloc(T**
b,
long int n,
long int m);
2071 T** realloc(T**
b,
unsigned int n,
unsigned int m);
2080 T** realloc(T**
b,
int n,
int m);
2082 void* ralloc(
size_t s);
2084 void rfree(
void*
p,
size_t s);
2086 void* rrealloc(
void*
b,
size_t n,
size_t m);
2088 template<
size_t>
void* fl_alloc(
void);
2094 template<
size_t>
void fl_dispose(FreeList* f, FreeList*
l);
2117 template<
class T,
typename A1>
2118 T& construct(A1
const& a1);
2124 template<
class T,
typename A1,
typename A2>
2125 T& construct(A1
const& a1, A2
const& a2);
2131 template<
class T,
typename A1,
typename A2,
typename A3>
2132 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
2138 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
2139 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
2145 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
2146 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
2168 bool operator ()(
void)
const;
2170 void operator ++(
void);
2190 bool operator ()(
void)
const;
2192 void operator ++(
void);
2194 const Brancher& brancher(
void)
const;
2201 void afc_decay(
double d);
2203 double afc_decay(
void)
const;
2206 void afc_set(
double a);
2220 SharedHandle::Object::operator
new(
size_t s) {
2224 SharedHandle::Object::operator
delete(
void*
p) {
2229 Space::operator
new(
size_t s) {
2233 Space::operator
delete(
void*
p) {
2238 Choice::operator
delete(
void*
p) {
2242 Choice::operator
new(
size_t s) {
2250 return mm.
alloc(sm,s);
2254 return mm.
reuse(p,s);
2258 char*
b =
static_cast<char*
>(
_b);
2260 char*
p =
static_cast<char*
>(
ralloc(m));
2273 return mm.template fl_alloc<s>(sm);
2278 mm.template fl_dispose<s>(f,
l);
2288 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*n));
2289 for (
long unsigned int i=n;
i--; )
2290 (
void)
new (p+
i) T();
2297 return alloc<T>(
static_cast<long unsigned int>(
n));
2302 return alloc<T>(
static_cast<long unsigned int>(
n));
2308 return alloc<T>(
static_cast<long unsigned int>(
n));
2314 for (
long unsigned int i=n;
i--; )
2316 rfree(b,n*
sizeof(T));
2322 free<T>(
b,
static_cast<long unsigned int>(
n));
2327 free<T>(
b,
static_cast<long unsigned int>(
n));
2333 free<T>(
b,
static_cast<long unsigned int>(
n));
2340 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*m));
2341 for (
long unsigned int i=n;
i--; )
2342 (
void)
new (p+
i) T(b[
i]);
2343 for (
long unsigned int i=n; i<m; i++)
2344 (
void)
new (p+
i) T();
2355 assert((n >= 0) && (m >= 0));
2356 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2357 static_cast<long unsigned int>(m));
2362 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2363 static_cast<long unsigned int>(m));
2368 assert((n >= 0) && (m >= 0));
2369 return realloc<T>(
b,
static_cast<long unsigned int>(
n),
2370 static_cast<long unsigned int>(m));
2373 #define GECODE_KERNEL_REALLOC(T) \
2376 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2377 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2381 Space::realloc<T>(T* b, long int n, long int m) { \
2382 assert((n >= 0) && (m >= 0)); \
2383 return realloc<T>(b,static_cast<long unsigned int>(n), \
2384 static_cast<long unsigned int>(m)); \
2388 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2389 return realloc<T>(b,static_cast<long unsigned int>(n), \
2390 static_cast<long unsigned int>(m)); \
2394 Space::realloc<T>(T* b, int n, int m) { \
2395 assert((n >= 0) && (m >= 0)); \
2396 return realloc<T>(b,static_cast<long unsigned int>(n), \
2397 static_cast<long unsigned int>(m)); \
2412 #undef GECODE_KERNEL_REALLOC
2417 return static_cast<T**
>(
rrealloc(b,n*
sizeof(T),m*
sizeof(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));
2441 #ifdef GECODE_HAS_VAR_DISPOSE
2444 Space::vars_d(
void)
const {
2445 return _vars_d[VIC::idx_d];
2449 Space::vars_d(VarImpBase*
x) {
2450 _vars_d[VIC::idx_d] =
x;
2456 Actor::operator
delete(
void*) {}
2458 Actor::operator
delete(
void*,
Space&) {}
2460 Actor::operator
new(
size_t s,
Space& home) {
2461 return home.ralloc(s);
2473 return home.ralloc(s);
2478 Advisor::operator
delete(
void*) {}
2481 Advisor::operator
delete(
void*,
Space&) {}
2483 Advisor::operator
new(
size_t s,
Space& home) {
2484 return home.ralloc(s);
2488 NGL::operator
delete(
void*) {}
2492 NGL::operator
new(
size_t s,
Space& home) {
2493 return home.ralloc(s);
2502 : next(NULL), fwd(NULL), use_cnt(0) {}
2505 assert(use_cnt == 0);
2513 SharedHandle::subscribe(
void) {
2514 if (o != NULL) o->use_cnt++;
2517 SharedHandle::cancel(
void) {
2518 if ((o != NULL) && (--o->use_cnt == 0))
2525 cancel(); o=
n; subscribe();
2541 cancel(); o=sh.o; subscribe();
2551 }
else if (sh.o->fwd != NULL) {
2556 sh.o->next = home.pc.
c.shared;
2557 home.pc.
c.shared = sh.o;
2619 p->_next =
n; n->_prev =
p;
2624 _next =
this; _prev =
this;
2631 this->_next =
a; a->_prev =
this;
2632 a->_next =
n; n->_prev =
a;
2639 a->_next =
this; this->_prev =
a;
2640 p->_next =
a; a->_prev =
p;
2645 return _next ==
this;
2676 return static_cast<Actor*
>(&
t);
2680 Actor::cast(
const ActorLink* al) {
2684 return static_cast<const Actor*
>(&
t);
2688 Space::afc_enable(
void) {
2692 Space::afc_enabled(
void)
const {
2693 return (_wmp_afc & 1U) != 0U;
2696 Space::wmp(
unsigned int n) {
2697 _wmp_afc = (_wmp_afc & 1U) | (n << 1);
2700 Space::wmp(
void)
const {
2701 return _wmp_afc >> 1U;
2714 return const_cast<Space*
>(
this)->_clone(share);
2724 return gafc.
decay();
2729 return sizeof(*this);
2754 return Home(*
this,&p);
2774 Propagator::cast(
const ActorLink* al) {
2783 : gafc((home.propagator() != NULL) ?
2785 home.propagator()->gafc :
2787 static_cast<
Space&>(home).gafc.allocate()) {
2789 assert((u.med == 0) && (u.size == 0));
2790 static_cast<Space&
>(home).pl.head(
this);
2797 assert((u.med == 0) && (u.size == 0));
2809 return const_cast<Space&
>(home).gafc.afc(gafc);
2827 assert(p.u.
med != 0);
2834 assert(p.u.
med != 0);
2853 Brancher::cast(
const ActorLink* al) {
2857 return static_cast<const Brancher*
>(&
t);
2862 _id(static_cast<
Space&>(home).pc.
p.branch_id++) {
2863 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2866 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2867 static_cast<Space&
>(home).b_status =
this;
2868 if (static_cast<Space&>(home).b_commit == &
static_cast<Space&
>(home).bl)
2869 static_cast<Space&
>(home).b_commit =
this;
2871 static_cast<Space&
>(home).bl.tail(
this);
2887 Space::brancher(
unsigned int id) {
2904 while (b_commit != Brancher::cast(&bl))
2905 if (
id != b_commit->
id())
2906 b_commit = Brancher::cast(b_commit->next());
2909 if (b_commit == Brancher::cast(&bl)) {
2911 b_commit = Brancher::cast(bl.
next());
2912 while (b_commit != b_old)
2913 if (
id != b_commit->
id())
2914 b_commit = Brancher::cast(b_commit->next());
2927 : _id(
Space::reserved_branch_id) {}
2941 return const_cast<Space&
>(home).brancher(_id) != NULL;
2945 home.kill_brancher(_id);
2983 fwdcopy(home,share);
3016 : _id(b.id()), _alt(a) {}
3024 Choice::id(
void)
const {
3071 return sizeof(*this);
3091 Advisor::disposed(
void)
const {
3092 return prev() == NULL;
3096 Advisor::cast(ActorLink* al) {
3097 return static_cast<Advisor*
>(al);
3101 Advisor::cast(
const ActorLink* al) {
3102 return static_cast<const Advisor*
>(al);
3107 assert(!disposed());
3114 assert(!disposed());
3118 if ((n != NULL) && n->disposed())
3162 while ((a != NULL) && static_cast<A*>(a)->disposed())
3174 while ((a != NULL) && static_cast<A*>(a)->disposed())
3179 if (c.advisors != NULL) {
3181 Propagator* p_f = &
static_cast<A*
>(c.advisors)->propagator();
3183 Propagator* p_t = Propagator::cast(p_f->prev());
3188 while (*a_f != NULL) {
3189 if (static_cast<A*>(*a_f)->disposed()) {
3190 *a_f = (*a_f)->next();
3193 A*
a =
new (home) A(home,share,*static_cast<A*>(*a_f));
3201 a_f = (*a_f)->next_ref();
3218 if (!static_cast<A*>(a)->disposed())
3219 static_cast<A*
>(
a)->dispose(home,*
this);
3234 while ((a != NULL) && static_cast<A*>(a)->disposed())
3249 }
while ((
a != NULL) && static_cast<A*>(
a)->disposed());
3255 return *
static_cast<A*
>(
a);
3269 if (c > pc.p.active)
3298 return ((pc.p.active < &pc.p.queue[0]) ||
3311 assert((pc >= 0) && (pc < pc_max+2));
3312 return (pc == 0) ?
b.base :
b.base+
u.idx[pc-1];
3317 VarImp<VIC>::actorNonZero(
PropCond pc) {
3318 assert((pc > 0) && (pc < pc_max+2));
3319 return b.base+
u.idx[pc-1];
3325 assert((pc > 0) && (pc < pc_max+2));
3332 assert((pc > 0) && (pc < pc_max+2));
3339 b.base = NULL; entries = 0;
3340 for (
PropCond pc=1; pc<pc_max+2; pc++)
3348 b.base = NULL; entries = 0;
3349 for (
PropCond pc=1; pc<pc_max+2; pc++)
3370 d += Propagator::cast(*a)->afc(home); a++;
3378 d += Advisor::cast(*a)->propagator().afc(home); a++;
3393 return free_and_bits;
3399 return free_and_bits;
3402 #ifdef GECODE_HAS_VAR_DISPOSE
3406 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
3411 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>*
x) {
3412 home.vars_d<VIC>(
x);
3440 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3441 if (x.b.
base == NULL) {
3443 reg = &home.pc.
c.vars_noidx;
3446 reg = &home.pc.
c.vars_u[idx_c];
3450 entries = x.entries;
3451 for (
PropCond pc=1; pc<pc_max+2; pc++)
3452 idx(pc) = x.
idx(pc);
3463 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3475 return VIC::me_combine(me1,me2);
3482 if (VIC::med_update(p.u.
med,me) || force)
3492 schedule(home,*Propagator::cast(*p),me);
3498 assert(pc <= pc_max);
3500 home.pc.
p.n_sub += 1;
3501 if ((free_and_bits >> free_bits) == 0)
3503 free_and_bits -= 1 << free_bits;
3506 b.base[entries] = *actorNonZero(pc_max+1);
3508 for (
PropCond j = pc_max; j > pc; j--) {
3509 *actorNonZero(j+1) = *actorNonZero(j);
3512 *actorNonZero(pc+1) = *actor(pc);
3517 ActorLink** f = actor(pc);
3518 while (f < (pc == pc_max+1 ?
b.base+entries : actorNonZero(pc+1)))
3530 VarImp<VIC>::enter(Space& home, Advisor*
a) {
3532 home.pc.p.n_sub += 1;
3533 if ((free_and_bits >> free_bits) == 0)
3535 free_and_bits -= 1 << free_bits;
3538 b.base[entries++] = *actorNonZero(pc_max+1);
3539 *actorNonZero(pc_max+1) =
a;
3544 VarImp<VIC>::resize(Space& home) {
3545 if (
b.base == NULL) {
3546 assert((free_and_bits >> free_bits) == 0);
3548 free_and_bits += 4 << free_bits;
3549 b.base = home.alloc<ActorLink*>(4);
3550 for (
int i=0;
i<pc_max+1;
i++)
3554 unsigned int n = degree();
3558 ActorLink** s =
static_cast<ActorLink**
>(home.mm.subscriptions());
3560 ((s <=
b.base) && (
b.base < s+home.pc.p.n_sub)) ?
3561 (n+4) : ((n+1)*3>>1);
3562 ActorLink** prop = home.alloc<ActorLink*>(m);
3563 free_and_bits += (m-
n) << free_bits;
3565 Heap::copy<ActorLink*>(prop,
b.base,
n);
3566 home.free<ActorLink*>(
b.base,
n);
3597 assert(pc <= pc_max);
3602 while (f < actorNonZero(pc+1))
3610 while (*f != a) f++;
3613 *f = *(actorNonZero(pc+1)-1);
3614 for (
PropCond j = pc+1; j< pc_max+1; j++) {
3615 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3618 *(actorNonZero(pc_max+1)-1) =
b.base[entries-1];
3621 free_and_bits += 1 << free_bits;
3622 home.pc.
p.n_sub -= 1;
3627 VarImp<VIC>::remove(Space& home, Advisor* a) {
3629 ActorLink** f = actorNonZero(pc_max+1);
3631 while (f <
b.base+entries)
3639 while (*f != a) f++;
3642 *f =
b.base[--entries];
3643 free_and_bits += 1 << free_bits;
3644 home.pc.p.n_sub -= 1;
3664 unsigned int n_sub = degree();
3665 home.pc.
p.n_sub -= n_sub;
3666 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3682 ActorLink** la = actorNonZero(pc_max+1);
3691 Advisor* a = Advisor::cast(*la);
3692 assert(!a->disposed());
3694 switch (p.advise(home,*a,d)) {
3698 if (home.afc_enabled())
3699 home.gafc.
fail(p.gafc);
3702 schedule(home,p,me);
3705 schedule(home,p,me,
true);
3710 }
while (++la < le);
3721 x->u.
idx[0] =
u.idx[0];
3722 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
3723 x->u.
idx[1] =
u.idx[1];
3726 unsigned int n = x->
degree();
3733 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3734 t[2]=f[2]->
prev(); t[3]=f[3]->
prev();
3739 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3749 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3750 VarImp<VIC>* x =
static_cast<VarImp<VIC>*
>(home.pc.c.vars_u[idx_c]);
3752 VarImp<VIC>* n = x->
next(); x->forward()->update(x,sub); x =
n;
3762 template<
class VarImp>
3764 #ifdef GECODE_HAS_VAR_DISPOSE
3765 Space::vd[VarImp::idx_d] =
this;
3769 template<
class VarImp>
3774 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
3775 }
while (x != NULL);
3856 return (m ==
LO) ? lo : hi;
3866 return crazy(m,static_cast<unsigned int>(n));
3875 return cubic(m,static_cast<unsigned int>(n));
3884 return quadratic(m,static_cast<unsigned int>(n));
3893 return linear(m,static_cast<unsigned int>(n));
3914 : home(home0), q(home.pc.p.active) {
3915 while (q >= &home.pc.p.queue[0]) {
3916 if (q->
next() != q) {
3917 c = q->
next(); e = q; q--;
3923 if (!home.pl.empty()) {
3924 c = Propagator::cast(home.pl.next());
3925 e = Propagator::cast(&home.pl);
3941 while (q >= &home.pc.p.queue[0]) {
3942 if (q->next() != q) {
3943 c = q->
next(); e = q; q--;
3949 if (!home.pl.empty()) {
3950 c = Propagator::cast(home.pl.next());
3951 e = Propagator::cast(&home.pl);
3960 return *Propagator::cast(c);
3965 : c(
Brancher::cast(home.bl.next())), e(&home.bl) {}
3976 return *Brancher::cast(c);
3988 template<
class T,
typename A1>
3991 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3995 template<
class T,
typename A1,
typename A2>
3998 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4002 template<
class T,
typename A1,
typename A2,
typename A3>
4005 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4006 new (&
t) T(a1,a2,a3);
4009 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
4012 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4013 new (&
t) T(a1,a2,a3,a4);
4016 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
4019 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
4020 new (&
t) T(a1,a2,a3,a4,a5);