core.icc

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2003
 *     Mikael Lagerkvist, 2006
 *
 *  Bugfixes provided by:
 *     Alexander Samoilov <alexander_samoilov@yahoo.com>
 *
 *  Last modified:
 *     $Date: 2008-07-11 10:27:28 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
 *     $Revision: 7332 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

namespace Gecode {

  class Space;

  class SharedHandle {
  public:
    class Object {
      friend class Space;
      friend class SharedHandle;
    private:
      unsigned int use_cnt;
      Object* next;
      Object* fwd;
    public:
      Object(void);
      virtual Object* copy(void) const = 0;
      virtual ~Object(void);
      static void* operator new(size_t s);
      static void  operator delete(void* p);
    };
  private:
    Object* o;
    void subscribe(void);
    void cancel(void);
  public:
    SharedHandle(void);
    SharedHandle(Object* so);
    SharedHandle(const SharedHandle& sh);
    SharedHandle& operator=(const SharedHandle& sh);
    void update(Space* home, bool share, SharedHandle& sh);
    ~SharedHandle(void);
  protected:
    Object* object(void) const;
    void object(Object* n);
  };



  typedef int ModEvent;

  const ModEvent ME_GEN_FAILED   = -1;
  const ModEvent ME_GEN_NONE     =  0;
  const ModEvent ME_GEN_ASSIGNED =  1;

  typedef int PropCond;
  const PropCond PC_GEN_NONE     = -1;
  const PropCond PC_GEN_ASSIGNED = 0;

  typedef int ModEventDelta;

}

#include "gecode/kernel/var-type.icc"

namespace Gecode {

  class NoIdxVarImpConf {
  public:
    static const int idx_c = -1;
    static const int idx_d = -1;
    static const PropCond pc_max = PC_GEN_ASSIGNED;
    static const int free_bits = 0;
    static const int med_fst = 0;
    static const int med_lst = 0;
    static const int med_mask = 0;
    static Gecode::ModEvent me_combine(ModEvent me1, ModEvent me2);
    static bool med_update(ModEventDelta& med, ModEvent me);
    static GECODE_KERNEL_EXPORT const Support::Symbol vti;
  };

  forceinline ModEvent
  NoIdxVarImpConf::me_combine(ModEvent, ModEvent) {
    GECODE_NEVER; return 0;
  }
  forceinline bool
  NoIdxVarImpConf::med_update(ModEventDelta&, ModEvent) {
    GECODE_NEVER; return false;
  }


  /*
   * These are the classes of interest
   *
   */
  class ActorLink;
  class Actor;
  class Propagator;
  class Advisor;
  template <class A> class Council;
  template <class A> class Advisors;
  template <class VIC> class VarImp;


  /*
   * Variable implementations
   *
   */

  class VarImpBase {};

  class GECODE_VTABLE_EXPORT VarDisposerBase {
  public:
    GECODE_KERNEL_EXPORT virtual void dispose(Space* home, VarImpBase* x);
    GECODE_KERNEL_EXPORT virtual ~VarDisposerBase(void);
  };

  template <class VarType>
  class VarDisposer : public VarDisposerBase {
  public:
    VarDisposer(void);
    virtual void dispose(Space* home, VarImpBase* x);
  };

  class Delta {
    template <class VIC> friend class VarImp;
  private:
    ModEvent me; 
  public:
    ModEvent modevent(void) const;
  };

  template <class VIC>
  class VarImp : public VarImpBase {
    friend class Space;
    friend class Propagator;
    template <class VarType> friend class VarDisposer;
  private:
    static const int idx_c = VIC::idx_c;
    static const int idx_d = VIC::idx_d;
    static const int free_bits = VIC::free_bits;
    unsigned int free_and_bits;
    static const Gecode::PropCond pc_max = VIC::pc_max;
    ActorLink** idx[pc_max+3];

    void update(VarImp* x, ActorLink**& sub);
    static void update(Space* home, ActorLink**& sub);

    void enter(Space* home, ActorLink* a, PropCond pc);
    void resize(Space* home);
    void remove(Space* home, ActorLink* a, PropCond pc);

  protected:
#ifdef GECODE_HAS_VAR_DISPOSE
    static VarImp<VIC>* vars_d(Space* home);
    static void vars_d(Space* home, VarImp<VIC>* x);
#endif

  public:
    VarImp(Space* home);
    VarImp(void);



    void subscribe(Space* home, Propagator* p, PropCond pc,
                   bool assigned, ModEvent me, bool schedule);
    void cancel(Space* home, Propagator* p, PropCond pc,
                bool assigned);
    void subscribe(Space* home, Advisor* a, bool assigned);
    void cancel(Space* home, Advisor* p, bool assigned);
    void cancel(Space* home);
    unsigned int degree(void) const;
    bool advise(Space* home, ModEvent me, Delta* d);



    VarImp(Space* home, bool share, VarImp& x);
    bool copied(void) const;
    VarImp* forward(void) const;
    VarImp* next(void) const;



    static void schedule(Space* home, Propagator* p, ModEvent me);
    static ModEvent me(ModEventDelta med);
    static ModEventDelta med(ModEvent me);
    static ModEvent me_combine(ModEvent me1, ModEvent me2);

    unsigned int bits(void) const;
    unsigned int& bits(void);

  protected:
    void schedule(Space* home, PropCond pc1, PropCond pc2, ModEvent me);

  public:


    static void* operator new(size_t,Space*);
    static void  operator delete(void*,Space*);
    static void  operator delete(void*);
    


    static const Support::Symbol vti;
    
  };

  template <class VIC>
  const Support::Symbol
  VarImp<VIC>::vti = VIC::vti;


  namespace Reflection {
    class ActorSpecIter;
    class ActorSpec;
    class BranchingSpec;
    class VarMap;
  }

  enum ExecStatus {
    __ES_SUBSUMED       = -2, 
    ES_FAILED           = -1, 
    ES_NOFIX            =  0, 
    ES_OK               =  0, 
    ES_FIX              =  1, 
    __ES_PARTIAL        =  2  
  };

  enum PropCost {
    PC_CRAZY_LO     = 0, 
    PC_CRAZY_HI     = 0, 
    PC_CUBIC_LO     = 1, 
    PC_CUBIC_HI     = 1, 
    PC_QUADRATIC_LO = 2, 
    PC_QUADRATIC_HI = 2, 
    PC_LINEAR_HI    = 3, 
    PC_LINEAR_LO    = 4, 
    PC_TERNARY_HI   = 5, 
    PC_BINARY_HI    = 6, 
    PC_TERNARY_LO   = 6, 
    PC_BINARY_LO    = 7, 
    PC_UNARY_LO     = 7, 
    PC_UNARY_HI     = 7, 
    PC_MAX          = 7  
  };

  class ActorLink {
    friend class Actor;
    friend class Propagator;
    friend class Advisor;
    friend class Branching;
    friend class Space;
    template <class VIC> friend class VarImp;
  private:
    ActorLink* _next; ActorLink* _prev;
  public:

    ActorLink* prev(void) const; void prev(ActorLink*);
    ActorLink* next(void) const; void next(ActorLink*);
    ActorLink** next_ref(void);

    void init(void);
    void unlink(void);
    void head(ActorLink* al);
    void tail(ActorLink* al);
    template <class T> static ActorLink* cast(T* a);
    template <class T> static const ActorLink* cast(const T* a);
  };


  class GECODE_VTABLE_EXPORT Actor : private ActorLink {
    friend class ActorLink;
    friend class Space;
    friend class Propagator;
    friend class Advisor;
    friend class Branching;
    friend class Reflection::ActorSpecIter;
    template <class VIC> friend class VarImp;
    template <class A> friend class Council;
  private:
    static Actor* cast(ActorLink* al);
    static const Actor* cast(const ActorLink* al);
  public:
    virtual Actor* copy(Space*,bool) = 0;



    GECODE_KERNEL_EXPORT 
    virtual size_t allocated(void) const;
    GECODE_KERNEL_EXPORT
    virtual size_t dispose(Space* home);
    void force(Space* home);
    void unforce(Space* home);
    static void* operator new(size_t s, Space* home);
    static void  operator delete(void* p, Space* home);
    GECODE_KERNEL_EXPORT
    virtual Reflection::ActorSpec spec(const Space* home,
                                       Reflection::VarMap& m) const;
  private:
#ifndef __GNUC__
    static void  operator delete(void* p);
#endif
    static void* operator new(size_t s);

#ifdef __GNUC__
  public:
    GECODE_KERNEL_EXPORT virtual ~Actor(void);
    static void  operator delete(void* p);
#endif
  };


  ExecStatus ES_SUBSUMED(Propagator* p, size_t s);
  ExecStatus ES_SUBSUMED(Propagator* p, Space* home);
  ExecStatus ES_FIX_PARTIAL(Propagator* p, ModEventDelta med);
  ExecStatus ES_NOFIX_PARTIAL(Propagator* p, ModEventDelta med);

  class GECODE_VTABLE_EXPORT Propagator : public Actor {
    friend class ActorLink;
    friend class Space;
    template <class VIC> friend class VarImp;
    friend ExecStatus ES_SUBSUMED(Propagator*, size_t);
    friend ExecStatus ES_SUBSUMED(Propagator*, Space*);
    friend ExecStatus ES_FIX_PARTIAL(Propagator*, ModEventDelta);
    friend ExecStatus ES_NOFIX_PARTIAL(Propagator*, ModEventDelta);
    friend class Advisor;
    template <class A> friend class Council;
  private:
    union {
      ModEventDelta med;
      size_t size;
      Gecode::ActorLink* advisors;
    } u;
    static Propagator* cast(ActorLink* al);
    static const Propagator* cast(const ActorLink* al);
  protected:
    Propagator(Space* home);
    Propagator(Space* home, bool share, Propagator& p);

  public:


    virtual ExecStatus propagate(Space* home, ModEventDelta med) = 0;
    virtual PropCost cost(ModEventDelta med) const  = 0;
    GECODE_KERNEL_EXPORT
    virtual ExecStatus advise(Space* home, Advisor* a, const Delta* d);
  };


  template <class A>
  class Council {
    friend class Advisor;
    friend class Advisors<A>;
  private:
    mutable ActorLink* advisors;
  public:
    Council(void);
    Council(Space* home);
    bool empty(void) const;
    void update(Space* home, bool share, Council<A>& c);
    void dispose(Space* home);
  };


  template <class A>
  class Advisors {
  private:
    ActorLink* a;
  public:
    Advisors(const Council<A>& c);
    bool operator()(void) const;
    void operator++(void);
    A* advisor(void) const;
  };


  template <class A>
  ExecStatus ES_SUBSUMED_FIX(A* a, Space* home, Council<A>& c);
  template <class A>
  ExecStatus ES_SUBSUMED_NOFIX(A* a, Space* home, Council<A>& c);

  class Advisor : private ActorLink {
    template <class VIC> friend class VarImp;
    template <class A> friend class Council;
    template <class A> friend class Advisors;
  private:
    bool disposed(void) const;
    static Advisor* cast(ActorLink* al);
    static const Advisor* cast(const ActorLink* al);
  protected:
    Propagator* propagator(void) const; 
  public:
    template <class A>
    Advisor(Space* home, Propagator* p, Council<A>& c);
    Advisor(Space* home, bool share, Advisor& a);



    template <class A>
    void dispose(Space* home, Council<A>& c);
    static void* operator new(size_t s, Space* home);
    static void  operator delete(void* p, Space* home);
  private:
#ifndef __GNUC__
    static void  operator delete(void* p);
#endif
    static void* operator new(size_t s);
  };


  class Branching;

  class BranchingDesc {
    friend class Space;
    friend class Reflection::BranchingSpec;
  private:
    unsigned int _id;  
    unsigned int _alt; 

    unsigned int id(void) const;
  protected:
    BranchingDesc(const Branching* b, const unsigned int a);
  public:
    unsigned int alternatives(void) const;
    GECODE_KERNEL_EXPORT virtual ~BranchingDesc(void);
    virtual size_t size(void) const = 0;
    static void* operator new(size_t);
    static void  operator delete(void*);
  };

  class GECODE_VTABLE_EXPORT Branching : public Actor {
    friend class ActorLink;
    friend class Space;
    friend class BranchingDesc;
    friend class Reflection::ActorSpecIter;
  private:
    unsigned int id; 
    static Branching* cast(ActorLink* al);
    static const Branching* cast(const ActorLink* al);
  protected:
    Branching(Space* home);
    Branching(Space* home, bool share, Branching& b);

  public:


    virtual bool status(const Space* home) const = 0;
    virtual const BranchingDesc* description(const Space* home) const = 0;
    virtual ExecStatus commit(Space* home, const BranchingDesc* d,
                              unsigned int a) = 0;
    


    virtual GECODE_KERNEL_EXPORT Reflection::BranchingSpec
    branchingSpec(const Space* home,
                  Reflection::VarMap& m, const BranchingDesc* d) const;
  };



  enum SpaceStatus {
    SS_FAILED, 
    SS_SOLVED, 
    SS_BRANCH  
  };

  class GECODE_VTABLE_EXPORT Space {
    friend class Actor;
    friend class Propagator;
    friend class Branching;
    friend class Advisor;
    friend class Reflection::ActorSpecIter;
    template <class VIC> friend class VarImp;
    template <class VarType> friend class VarDisposer;
    friend class SharedHandle;
  private:
    MemoryManager mm; 
    ActorLink a_actors;
    Branching* b_status;
    Branching* b_commit;
    union {
      struct {
        ActorLink* active;
        ActorLink queue[PC_MAX+1];
        unsigned int branch_id;
        unsigned int n_sub;
      } p;
      struct {
        VarImpBase* vars_u[AllVarConf::idx_c];
        VarImpBase* vars_noidx;
        SharedHandle::Object* shared;
      } c;
    } pc;
    void enqueue(Propagator* p);
#ifdef GECODE_HAS_VAR_DISPOSE
    GECODE_KERNEL_EXPORT static VarDisposerBase* vd[AllVarConf::idx_d];
    VarImpBase* _vars_d[AllVarConf::idx_d];
    template <class VIC> VarImpBase* vars_d(void) const;
    template <class VIC> void vars_d(VarImpBase* x);
#endif
    void update(ActorLink** sub);


    Actor** d_fst;
    Actor** d_cur;
    Actor** d_lst;
    GECODE_KERNEL_EXPORT void d_resize(void);

    GECODE_KERNEL_EXPORT static unsigned long int unused_uli;
  public:
    GECODE_KERNEL_EXPORT Space(void);
    GECODE_KERNEL_EXPORT virtual ~Space(void);
    GECODE_KERNEL_EXPORT Space(bool share, Space& s);
    virtual Space* copy(bool share) = 0;
    static void* operator new(size_t);
    static void  operator delete(void*);


    /*
     * Member functions for search engines
     *
     */

    GECODE_KERNEL_EXPORT SpaceStatus status(unsigned long int& pn=unused_uli);

    const BranchingDesc* description(void) const;

    GECODE_KERNEL_EXPORT Space* clone(bool share=true);

    GECODE_KERNEL_EXPORT void commit(const BranchingDesc* d, unsigned int a);

    void fail(void);
    bool failed(void) const;
    bool stable(void) const;
    GECODE_KERNEL_EXPORT unsigned int propagators(void) const;
    GECODE_KERNEL_EXPORT unsigned int branchings(void) const;


    GECODE_KERNEL_EXPORT
    virtual void getVars(Reflection::VarMap& m, bool registerOnly);
    GECODE_KERNEL_EXPORT
    Reflection::BranchingSpec branchingSpec(Reflection::VarMap& m,
                                            const BranchingDesc* d) const;


    void* alloc(size_t);
    void  reuse(void*,size_t);
    template <size_t> void* fl_alloc(void);
    template <size_t> void  fl_dispose(FreeList* f, FreeList* l);
    GECODE_KERNEL_EXPORT 
    size_t allocated(void) const;
  };




  /*
   * Memory management
   *
   */

  // Heap allocated
  forceinline void* 
  SharedHandle::Object::operator new(size_t s) {
    return Memory::malloc(s);
  }
  forceinline void
  SharedHandle::Object::operator delete(void* p) {
    Memory::free(p);
  }

  forceinline void*
  Space::operator new(size_t s) {
    return Memory::malloc(s);
  }
  forceinline void
  Space::operator delete(void* p) {
    Memory::free(p);
  }

  forceinline void
  BranchingDesc::operator delete(void* p) {
    Memory::free(p);
  }
  forceinline void*
  BranchingDesc::operator new(size_t s) {
    return Memory::malloc(s);
  }

  // Space allocation: general space heaps and free lists
  forceinline void*
  Space::alloc(size_t s) {
    return mm.alloc(s);
  }
  forceinline void
  Space::reuse(void* p, size_t s) {
    return mm.reuse(p,s);
  }
  template <size_t s>
  forceinline void*
  Space::fl_alloc(void) {
    return mm.template fl_alloc<s>();
  }
  template <size_t s>
  forceinline void
  Space::fl_dispose(FreeList* f, FreeList* l) {
    mm.template fl_dispose<s>(f,l);
  }

#ifdef GECODE_HAS_VAR_DISPOSE
  template <class VIC>
  forceinline VarImpBase*
  Space::vars_d(void) const {
    return _vars_d[VIC::idx_d];
  }
  template <class VIC>
  forceinline void
  Space::vars_d(VarImpBase* x) {
    _vars_d[VIC::idx_d] = x;
  }
#endif

  // Space allocated entities: Actors, variable implementations, and advisors
  forceinline void
  Actor::operator delete(void*) {}
  forceinline void
  Actor::operator delete(void*, Space*) {}
  forceinline void*
  Actor::operator new(size_t s, Space* home) {
    return home->alloc(s);
  }

  template <class VIC>
  forceinline void
  VarImp<VIC>::operator delete(void*) {}
  template <class VIC>
  forceinline void
  VarImp<VIC>::operator delete(void*, Space*) {}
  template <class VIC>
  forceinline void*
  VarImp<VIC>::operator new(size_t s, Space* home) {
    return home->alloc(s);
  }

#ifndef __GNUC__
  forceinline void
  Advisor::operator delete(void*) {}
#endif
  forceinline void
  Advisor::operator delete(void*, Space*) {}
  forceinline void*
  Advisor::operator new(size_t s, Space* home) {
    return home->alloc(s);
  }


  /*
   * Shared objects and handles
   *
   */
  forceinline
  SharedHandle::Object::Object(void) 
    : use_cnt(0), fwd(NULL) {}
  forceinline
  SharedHandle::Object::~Object(void) {
    assert(use_cnt == 0);
  }