[Gecode] Propgator copy

[Christian Schulte]

Please have a look to the DFA implementation (or to sharedArray) in
int/regular/dfa.*. There you will see that also reference counting is used.
This is done in the proper C++ way with overloading the copy
constructor/assignment operators.

However, you should also provide a real copy operation for reference
counting: the clone operation of a space can be given an additional argument
telling whether to share data or to completely copy it.

The reasoning behind this is to allow for thread-safety (I have a master
student doing a parallel thread-based search engine): if you want to have
spaces to be run in parallel, you have to copy rather than share. Otherwise
reference counting will introduce race conditions.

All the best
Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: Gustavo Gutierrez [mailto:ggutierrez at atlas.puj.edu.co] 
Sent: Thursday, February 10, 2005 3:18 PM
To: schulte at imit.kth.se
Subject: RE: [Gecode] Propgator copy


Hi all,

Thanks for the answer.

Looking at int/distinct/dom.icc gave me some implementations hints. My case
is a little distinct since it is better (i.e. time) to maintain a reference
to the tree than to build the tree at every propagate method invocation.

What i am doing is not to copy the tree in the copy method. Instead i am
passing a reference to the tree. Additionally each copy has a counter to the
number of references to the tree structure. This allows to free the memory
allocated by the tree when there are only one reference to it.

This is my code. I hope any of you can give me your opinion.

template <class Var>
class HC4 : public NaryPropagator<Var,PC_RI_LAST> {
	private:
		/*An object to store the constraint in user form (A TREE)*/
		Constraint* _cst;
		/*An integer to count how many rerefences are to _cst*/
		int _copies;
	protected:
		HC4(Space*,Constraint*,VarArray<Var>);
		HC4(Space*,HC4<Var>&);
	public:
		virtual Actor* copy(Space*,bool);
		virtual PropCost   cost(void) const;
		virtual ExecStatus propagate(Space*);
		static  ExecStatus post(Space*,Constraint*,VarArray<Var>);
		~HC4(void);
};

template <class Var>
HC4<Var>::HC4(Space* home, Constraint* c, VarArray<Var> vars) 
	: NaryPropagator<Var,PC_RI_LAST>(home,vars), _cst(c), _copies(1) {}

template <class Var>
HC4<Var>::HC4(Space* home, HC4<Var>& p)
	: NaryPropagator<Var,PC_RI_LAST>(home,*this), _cst(p._cst),     
_copies(p._copies+1) {}
 
emplate <class Var>
HC4<Var>::~HC4(void) {
	if (copies == 1) 
		delete _cst;
	copies--;
	NaryPropagator<Var,PC_RI_LAST>::~NaryPropagator();
}

template <class Var>
Actor* 
HC4<Var>::copy(Space* hom,bool){
	return new (home) HC4<Var>(home, *this);
}


Regards,
Gustavo Gutierrez
On Thu, 10 Feb 2005 09:22:27 +0100, Christian Schulte wrote
> The first issue is that of course your propagator is in charge of
> copying, if needed.
> 
> Secondly, consider whether you really want to always copy! Have a
> look to int/distinct/dom.icc. There the propagator also needs a 
> graph only during propagation. It maintains this graph as follows: 
> when the propagator is created or copied set the graph to empty. If 
> the propagate function is invoked, check whether the graph exists. 
> If not, create it. If yes, update it accordingly. Upon destruction 
> delete it, if it exists. Make sure that the destructor is called! 
> This you have to do by giving a special flag to the propagator. 
> Again see the above mentioned example.
> 
> All the best
> Christian
> 
> --
> Christian Schulte, http://www.imit.kth.se/~schulte/
> 
> -----Original Message-----
> From: gecode-bounces at ps.uni-sb.de [mailto:gecode-bounces at ps.uni- 
> sb.de] On Behalf Of Gustavo Gutierrez Sent: Wednesday, February 09,  
> 2005 6:01 PM To: gecode at ps.uni-sb.de Subject: [Gecode] Propgator copy
> 
> Hi,
> 
> First of all congratulations, GECODE is a really good piece of
> software! it is very useful and really *easily* extensible. Source 
> code is very clear, at least the parts i've read.
> 
> I have a question about propagators. I am writing a propagator, for 
> instance Prop, which needs to maintain a binary tree with some 
> information and a variable vector (VarArray). This propagator inherits 
> from NaryPropagator. Is there any special issue with this tree 
> structure i need to take into account?
> 
> The tree is used only by the propagate method and  it doesn't change
> its structure along propagation. I have some doubts implementing two 
> methods:
> 
> Prop(Space* home, Prop<Var>& p);
> 
> Call the super class NaryPropagator method to do this is not enough,
> what would happened with the tree?
> 
> Actor* copy(Space* home, bool);
> This method call the constructor i mentioned before, so i think all 
> depends on that implementation.
> 
> Finally, i think the memory allocated by the tree must be freed only
> at propagator destructor method.
> 
> Thanks in advance and hope to be clear. Feel free to ask for more 
> details.
> 
> Gustavo Gutierrez _______________________________________________
> Gecode mailing list
> Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode