104 static void*
operator new(
size_t s);
106 static void operator delete(
void* p);
221 template<
class A>
class Council;
223 template<
class VIC>
class VarImp;
260 template<
class VarImp>
311 static const int idx_c = VIC::idx_c;
313 static const int idx_d = VIC::idx_d;
315 static const int free_bits = VIC::free_bits;
317 unsigned int entries;
319 unsigned int free_and_bits;
334 unsigned int idx[pc_max+1];
368 void resize(
Space& home);
384 #ifdef GECODE_HAS_VAR_DISPOSE
439 unsigned int degree(
void)
const;
446 double afc(
void)
const;
489 unsigned int bits(
void)
const;
491 unsigned int&
bits(
void);
502 static void*
operator new(size_t,
Space&);
504 static void operator delete(
void*,
Space&);
506 static void operator delete(
void*);
649 bool empty(
void)
const;
677 virtual Actor* copy(
Space& home,
bool share) = 0;
683 virtual size_t allocated(
void)
const;
686 virtual size_t dispose(
Space& home);
688 static void*
operator new(
size_t s,
Space& home);
690 static void operator delete(
void* p,
Space& home);
694 static void operator delete(
void* p);
697 static void*
operator new(
size_t s);
704 static void operator delete(
void* p);
725 operator Space&(void);
854 double afc(
void)
const;
879 bool empty(
void)
const;
924 bool disposed(
void)
const;
945 static void*
operator new(
size_t s,
Space& home);
947 static void operator delete(
void* p,
Space& home);
952 static void operator delete(
void* p);
955 static void*
operator new(
size_t s);
976 unsigned int id(
void)
const;
982 unsigned int alternatives(
void)
const;
986 virtual size_t size(
void)
const = 0;
988 static void*
operator new(size_t);
990 static void operator delete(
void*);
1031 virtual bool status(
const Space& home)
const = 0;
1049 unsigned int a) = 0;
1051 unsigned int id(
void)
const;
1255 void enqueue(Propagator* p);
1260 #ifdef GECODE_HAS_VAR_DISPOSE
1266 template<
class VIC> VarImpBase* vars_d(
void)
const;
1268 template<
class VIC>
void vars_d(VarImpBase* x);
1271 void update(ActorLink** sub);
1352 void _commit(
const Choice&
c,
unsigned int a);
1382 virtual Space* copy(
bool share) = 0;
1399 static void*
operator new(size_t);
1404 static void operator delete(
void*);
1424 SpaceStatus status(StatusStatistics& stat=unused_status);
1458 const Choice* choice(
void);
1470 const Choice* choice(Archive& e)
const;
1489 Space*
clone(
bool share=
true, CloneStatistics& stat=unused_clone)
const;
1525 void commit(
const Choice&
c,
unsigned int a,
1526 CommitStatistics& stat=unused_commit);
1571 ExecStatus ES_SUBSUMED_DISPOSED(Propagator& p,
size_t s);
1631 ExecStatus ES_NOFIX_DISPOSE_FORCE(Council<A>&
c, A&
a);
1649 bool failed(
void)
const;
1654 bool stable(
void)
const;
1673 Home operator ()(Propagator& p);
1688 T* alloc(
long unsigned int n);
1696 T* alloc(
long int n);
1704 T* alloc(
unsigned int n);
1723 void free(T*
b,
long unsigned int n);
1734 void free(T*
b,
long int n);
1745 void free(T*
b,
unsigned int n);
1756 void free(T*
b,
int n);
1769 T* realloc(T*
b,
long unsigned int n,
long unsigned int m);
1782 T* realloc(T*
b,
long int n,
long int m);
1795 T* realloc(T*
b,
unsigned int n,
unsigned int m);
1808 T* realloc(T*
b,
int n,
int m);
1817 T** realloc(T**
b,
long unsigned int n,
long unsigned int m);
1826 T** realloc(T**
b,
long int n,
long int m);
1835 T** realloc(T**
b,
unsigned int n,
unsigned int m);
1844 T** realloc(T**
b,
int n,
int m);
1846 void* ralloc(
size_t s);
1848 void rfree(
void* p,
size_t s);
1850 void* rrealloc(
void*
b,
size_t n,
size_t m);
1852 template<
size_t>
void* fl_alloc(
void);
1858 template<
size_t>
void fl_dispose(FreeList* f, FreeList* l);
1865 size_t allocated(
void)
const;
1889 template<
class T,
typename A1>
1890 T& construct(A1
const& a1);
1896 template<
class T,
typename A1,
typename A2>
1897 T& construct(A1
const& a1, A2
const& a2);
1903 template<
class T,
typename A1,
typename A2,
typename A3>
1904 T& construct(A1
const& a1, A2
const& a2, A3
const& a3);
1910 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
1911 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4);
1917 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
1918 T& construct(A1
const& a1, A2
const& a2, A3
const& a3, A4
const& a4, A5
const& a5);
1940 bool operator ()(
void)
const;
1942 void operator ++(
void);
1962 bool operator ()(
void)
const;
1964 void operator ++(
void);
1966 const Brancher& brancher(
void)
const;
1980 SharedHandle::Object::operator
new(
size_t s) {
1984 SharedHandle::Object::operator
delete(
void* p) {
1989 Space::operator
new(
size_t s) {
1993 Space::operator
delete(
void* p) {
1998 Choice::operator
delete(
void* p) {
2002 Choice::operator
new(
size_t s) {
2009 return mm.
alloc(sm,s);
2013 return mm.
reuse(p,s);
2017 char*
b =
static_cast<char*
>(
_b);
2019 char*
p =
static_cast<char*
>(
ralloc(m));
2032 return mm.template fl_alloc<s>(sm);
2037 mm.template fl_dispose<s>(f,l);
2043 for (
Actor**
a = d_fst;
a < d_cur;
a++)
2044 s += (*a)->allocated();
2055 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*n));
2056 for (
long unsigned int i=n;
i--; )
2057 (
void)
new (p+
i) T();
2064 return alloc<T>(
static_cast<long unsigned int>(n));
2069 return alloc<T>(
static_cast<long unsigned int>(n));
2075 return alloc<T>(
static_cast<long unsigned int>(n));
2081 for (
long unsigned int i=n;
i--; )
2083 rfree(b,n*
sizeof(T));
2089 free<T>(
b,
static_cast<long unsigned int>(n));
2094 free<T>(
b,
static_cast<long unsigned int>(n));
2100 free<T>(
b,
static_cast<long unsigned int>(n));
2107 T*
p =
static_cast<T*
>(
ralloc(
sizeof(T)*m));
2108 for (
long unsigned int i=n;
i--; )
2109 (
void)
new (p+
i) T(b[
i]);
2110 for (
long unsigned int i=n; i<
m; i++)
2111 (
void)
new (p+
i) T();
2122 assert((n >= 0) && (m >= 0));
2123 return realloc<T>(
b,
static_cast<long unsigned int>(n),
2124 static_cast<long unsigned int>(m));
2129 return realloc<T>(
b,
static_cast<long unsigned int>(n),
2130 static_cast<long unsigned int>(m));
2135 assert((n >= 0) && (m >= 0));
2136 return realloc<T>(
b,
static_cast<long unsigned int>(n),
2137 static_cast<long unsigned int>(m));
2140 #define GECODE_KERNEL_REALLOC(T) \
2143 Space::realloc<T>(T* b, long unsigned int n, long unsigned int m) { \
2144 return static_cast<T*>(rrealloc(b,n*sizeof(T),m*sizeof(T))); \
2148 Space::realloc<T>(T* b, long int n, long int m) { \
2149 assert((n >= 0) && (m >= 0)); \
2150 return realloc<T>(b,static_cast<long unsigned int>(n), \
2151 static_cast<long unsigned int>(m)); \
2155 Space::realloc<T>(T* b, unsigned int n, unsigned int m) { \
2156 return realloc<T>(b,static_cast<long unsigned int>(n), \
2157 static_cast<long unsigned int>(m)); \
2161 Space::realloc<T>(T* b, int n, int m) { \
2162 assert((n >= 0) && (m >= 0)); \
2163 return realloc<T>(b,static_cast<long unsigned int>(n), \
2164 static_cast<long unsigned int>(m)); \
2179 #undef GECODE_KERNEL_REALLOC
2184 return static_cast<T**
>(
rrealloc(b,n*
sizeof(T),m*
sizeof(T*)));
2189 assert((n >= 0) && (m >= 0));
2190 return realloc<T*>(
b,
static_cast<long unsigned int>(n),
2191 static_cast<long unsigned int>(m));
2196 return realloc<T*>(
b,
static_cast<long unsigned int>(n),
2197 static_cast<long unsigned int>(m));
2202 assert((n >= 0) && (m >= 0));
2203 return realloc<T*>(
b,
static_cast<long unsigned int>(n),
2204 static_cast<long unsigned int>(m));
2208 #ifdef GECODE_HAS_VAR_DISPOSE
2211 Space::vars_d(
void)
const {
2212 return _vars_d[VIC::idx_d];
2216 Space::vars_d(VarImpBase* x) {
2217 _vars_d[VIC::idx_d] = x;
2223 Actor::operator
delete(
void*) {}
2225 Actor::operator
delete(
void*,
Space&) {}
2227 Actor::operator
new(
size_t s,
Space& home) {
2228 return home.ralloc(s);
2240 return home.ralloc(s);
2245 Advisor::operator
delete(
void*) {}
2248 Advisor::operator
delete(
void*,
Space&) {}
2250 Advisor::operator
new(
size_t s,
Space& home) {
2251 return home.ralloc(s);
2260 : next(NULL), fwd(NULL), use_cnt(0) {}
2263 assert(use_cnt == 0);
2271 SharedHandle::subscribe(
void) {
2272 if (o != NULL) o->use_cnt++;
2275 SharedHandle::cancel(
void) {
2276 if ((o != NULL) && (--o->use_cnt == 0))
2283 cancel(); o=n; subscribe();
2299 cancel(); o=sh.o; subscribe();
2309 }
else if (sh.o->fwd != NULL) {
2314 sh.o->next = home.pc.
c.shared;
2315 home.pc.
c.shared = sh.o;
2358 p->_next = n; n->_prev = p;
2363 _next =
this; _prev =
this;
2370 this->_next =
a; a->_prev =
this;
2371 a->_next = n; n->_prev =
a;
2378 a->_next =
this; this->_prev =
a;
2379 p->_next =
a; a->_prev = p;
2384 return _next ==
this;
2402 return static_cast<const ActorLink*
>(&t);
2415 return static_cast<Actor*
>(&t);
2419 Actor::cast(
const ActorLink* al) {
2423 return static_cast<const Actor*
>(&t);
2469 return const_cast<Space*
>(
this)->_clone(share);
2479 return sizeof(*this);
2499 return Home(*
this,&p);
2519 Propagator::cast(
const ActorLink* al) {
2528 : pi((home.propagator() != NULL) ?
2530 home.propagator()->pi :
2532 static_cast<
Space&>(home).gpi.allocate()) {
2534 assert((u.med == 0) && (u.size == 0));
2535 static_cast<Space&
>(home).pl.head(
this);
2542 assert((u.med == 0) && (u.size == 0));
2572 assert(p.u.
med != 0);
2579 assert(p.u.
med != 0);
2598 Brancher::cast(
const ActorLink* al) {
2602 return static_cast<const Brancher*
>(&t);
2607 _id(static_cast<
Space&>(home).pc.p.branch_id++) {
2608 if (static_cast<Space&>(home).pc.p.branch_id == 0U)
2611 if (static_cast<Space&>(home).b_status == &static_cast<Space&>(home).bl) {
2612 static_cast<Space&
>(home).b_status =
this;
2613 if (static_cast<Space&>(home).b_commit == &
static_cast<Space&
>(home).bl)
2614 static_cast<Space&
>(home).b_commit =
this;
2616 static_cast<Space&
>(home).bl.tail(
this);
2665 fwdcopy(home,share);
2698 : _id(b.id()), _alt(a) {}
2706 Choice::id(
void)
const {
2732 Advisor::disposed(
void)
const {
2733 return prev() == NULL;
2737 Advisor::cast(ActorLink* al) {
2738 return static_cast<Advisor*
>(al);
2742 Advisor::cast(
const ActorLink* al) {
2743 return static_cast<const Advisor*
>(al);
2748 assert(!disposed());
2755 assert(!disposed());
2759 if ((n != NULL) && n->disposed())
2803 while ((a != NULL) && static_cast<A*>(a)->disposed())
2815 while ((a != NULL) && static_cast<A*>(a)->disposed())
2820 if (c.advisors != NULL) {
2822 Propagator* p_f = &
static_cast<A*
>(c.advisors)->propagator();
2824 Propagator* p_t = Propagator::cast(p_f->prev());
2829 while (*a_f != NULL) {
2830 if (static_cast<A*>(*a_f)->disposed()) {
2831 *a_f = (*a_f)->
next();
2834 A*
a =
new (home) A(home,share,*static_cast<A*>(*a_f));
2842 a_f = (*a_f)->next_ref();
2859 if (!static_cast<A*>(a)->disposed())
2860 static_cast<A*
>(
a)->dispose(home,*
this);
2875 while ((a != NULL) && static_cast<A*>(a)->disposed())
2890 }
while ((
a != NULL) && static_cast<A*>(
a)->disposed());
2896 return *
static_cast<A*
>(
a);
2910 if (c > pc.p.active)
2939 return ((pc.p.active < &pc.p.queue[0]) ||
2952 assert((pc >= 0) && (pc < pc_max+2));
2953 return (pc == 0) ?
b.base :
b.base+u.idx[pc-1];
2958 VarImp<VIC>::actorNonZero(
PropCond pc) {
2959 assert((pc > 0) && (pc < pc_max+2));
2960 return b.base+u.idx[pc-1];
2966 assert((pc > 0) && (pc < pc_max+2));
2973 assert((pc > 0) && (pc < pc_max+2));
2980 b.base = NULL; entries = 0;
2981 for (
PropCond pc=1; pc<pc_max+2; pc++)
2989 b.base = NULL; entries = 0;
2990 for (
PropCond pc=1; pc<pc_max+2; pc++)
3007 double d = degree();
3013 d += Propagator::cast(*a)->afc(); a++;
3021 d += Advisor::cast(*a)->propagator().afc(); a++;
3036 return free_and_bits;
3042 return free_and_bits;
3045 #ifdef GECODE_HAS_VAR_DISPOSE
3049 return static_cast<VarImp<VIC>*
>(home.vars_d<VIC>());
3054 VarImp<VIC>::vars_d(Space& home, VarImp<VIC>* x) {
3055 home.vars_d<VIC>(x);
3083 free_and_bits = x.free_and_bits & ((1 << free_bits) - 1);
3084 if (x.b.
base == NULL) {
3086 reg = &home.pc.
c.vars_noidx;
3089 reg = &home.pc.
c.vars_u[idx_c];
3093 entries = x.entries;
3094 for (
PropCond pc=1; pc<pc_max+2; pc++)
3095 idx(pc) = x.
idx(pc);
3106 return static_cast<ModEvent>((med & VIC::med_mask) >> VIC::med_fst);
3118 return VIC::me_combine(me1,me2);
3125 if (VIC::med_update(p.u.
med,me) || force)
3135 schedule(home,*Propagator::cast(*p),me);
3141 assert(pc <= pc_max);
3143 home.pc.
p.n_sub += 1;
3144 if ((free_and_bits >> free_bits) == 0)
3146 free_and_bits -= 1 << free_bits;
3149 b.base[entries] = *actorNonZero(pc_max+1);
3151 for (
PropCond j = pc_max; j > pc; j--) {
3152 *actorNonZero(j+1) = *actorNonZero(j);
3155 *actorNonZero(pc+1) = *actor(pc);
3160 ActorLink** f = actor(pc);
3161 while (f < (pc == pc_max+1 ?
b.base+entries : actorNonZero(pc+1)))
3173 VarImp<VIC>::enter(Space& home, Advisor*
a) {
3175 home.pc.p.n_sub += 1;
3176 if ((free_and_bits >> free_bits) == 0)
3178 free_and_bits -= 1 << free_bits;
3181 b.base[entries++] = *actorNonZero(pc_max+1);
3182 *actorNonZero(pc_max+1) =
a;
3187 VarImp<VIC>::resize(Space& home) {
3188 if (
b.base == NULL) {
3189 assert((free_and_bits >> free_bits) == 0);
3191 free_and_bits += 4 << free_bits;
3192 b.base = home.alloc<ActorLink*>(4);
3193 for (
int i=0;
i<pc_max+1;
i++)
3197 unsigned int n = degree();
3201 ActorLink** s =
static_cast<ActorLink**
>(home.mm.subscriptions());
3203 ((s <=
b.base) && (
b.base < s+home.pc.p.n_sub)) ?
3204 (n+4) : ((n+1)*3>>1);
3205 ActorLink** prop = home.alloc<ActorLink*>(
m);
3206 free_and_bits += (m-n) << free_bits;
3208 Heap::copy<ActorLink*>(prop,
b.base, n);
3209 home.free<ActorLink*>(
b.base,n);
3240 assert(pc <= pc_max);
3245 while (f < actorNonZero(pc+1))
3253 while (*f != a) f++;
3256 *f = *(actorNonZero(pc+1)-1);
3257 for (
PropCond j = pc+1; j< pc_max+1; j++) {
3258 *(actorNonZero(j)-1) = *(actorNonZero(j+1)-1);
3261 *(actorNonZero(pc_max+1)-1) =
b.base[entries-1];
3264 free_and_bits += 1 << free_bits;
3265 home.pc.
p.n_sub -= 1;
3270 VarImp<VIC>::remove(Space& home, Advisor* a) {
3272 ActorLink** f = actorNonZero(pc_max+1);
3274 while (f <
b.base+entries)
3282 while (*f != a) f++;
3285 *f =
b.base[--entries];
3286 free_and_bits += 1 << free_bits;
3287 home.pc.p.n_sub -= 1;
3307 unsigned int n_sub = degree();
3308 home.pc.
p.n_sub -= n_sub;
3309 unsigned int n = (free_and_bits >> VIC::free_bits) + n_sub;
3325 ActorLink** la = actorNonZero(pc_max+1);
3334 Advisor* a = Advisor::cast(*la);
3335 assert(!a->disposed());
3337 switch (p.advise(home,*a,d)) {
3341 p.pi.fail(home.gpi);
3344 schedule(home,p,me);
3347 schedule(home,p,me,
true);
3352 }
while (++la < le);
3363 x->u.
idx[0] = u.idx[0];
3364 if (pc_max > 0 &&
sizeof(
ActorLink**) >
sizeof(
unsigned int))
3365 x->u.
idx[1] = u.idx[1];
3368 unsigned int n = x->
degree();
3375 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3376 t[2]=f[2]->
prev(); t[3]=f[3]->
prev();
3381 t[0]=f[0]->
prev(); t[1]=f[1]->
prev();
3391 VarImp<VIC>::update(Space& home, ActorLink**& sub) {
3392 VarImp<VIC>* x =
static_cast<VarImp<VIC>*
>(home.pc.c.vars_u[idx_c]);
3394 VarImp<VIC>* n = x->
next(); x->forward()->update(x,sub); x = n;
3404 template<
class VarImp>
3406 #ifdef GECODE_HAS_VAR_DISPOSE
3407 Space::vd[VarImp::idx_d] =
this;
3411 template<
class VarImp>
3416 x->dispose(home); x =
static_cast<VarImp*
>(x->next_d());
3417 }
while (x != NULL);
3498 return (m ==
LO) ? lo : hi;
3508 return crazy(m,static_cast<unsigned int>(n));
3517 return cubic(m,static_cast<unsigned int>(n));
3526 return quadratic(m,static_cast<unsigned int>(n));
3535 return linear(m,static_cast<unsigned int>(n));
3556 : home(home0), q(home.pc.p.active) {
3557 while (q >= &home.pc.p.queue[0]) {
3558 if (q->
next() != q) {
3559 c = q->
next(); e = q; q--;
3565 if (!home.pl.empty()) {
3566 c = Propagator::cast(home.pl.next());
3567 e = Propagator::cast(&home.pl);
3583 while (q >= &home.pc.p.queue[0]) {
3584 if (q->next() != q) {
3585 c = q->
next(); e = q; q--;
3591 if (!home.pl.empty()) {
3592 c = Propagator::cast(home.pl.next());
3593 e = Propagator::cast(&home.pl);
3602 return *Propagator::cast(c);
3607 : c(
Brancher::cast(home.bl.next())), e(&home.bl) {}
3618 return *Brancher::cast(c);
3630 template<
class T,
typename A1>
3633 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3637 template<
class T,
typename A1,
typename A2>
3640 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3644 template<
class T,
typename A1,
typename A2,
typename A3>
3647 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3648 new (&t) T(a1,a2,a3);
3651 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4>
3654 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3655 new (&t) T(a1,a2,a3,a4);
3658 template<
class T,
typename A1,
typename A2,
typename A3,
typename A4,
typename A5>
3661 T& t = *
static_cast<T*
>(
ralloc(
sizeof(T)));
3662 new (&t) T(a1,a2,a3,a4,a5);