pass-by-ref semantics for structs (was Deque impl.)

[Rainer Schuetze]

On 01.02.2013 00:14, Steven Schveighoffer wrote:
> On Thu, 31 Jan 2013 17:37:39 -0500, Steven Schveighoffer
> <schveiguy at yahoo.com> wrote:
>
>> On Thu, 31 Jan 2013 17:31:38 -0500, Rainer Schuetze
>> <r.sagitario at gmx.de> wrote:
>>
>>> Any reference that is accessible from multiple threads, e.g. a global
>>> shared variable.
>>>
>>> shared(Container) allObjects;
>>>
>>> Without any thread having a reference to it, the payload's reference
>>> count is 1. The reading thread above increments the counter when
>>> making a local copy, but the writing thread decrements the counter
>>> when assigning Container.init. If both run concurrently, with the
>>> sequence 1 to 3 above, trouble is inevitable.
>>
>> Right, but isn't that an issue with having ANY shared variable that
>> isn't protected by a lock?
>>
>> I was thinking you had passed the pointer in via a message or something.
>
> BTW, couldn't we solve this with a function that increments the retain
> count, and then returns a pointer to the object?  Such a method would
> have to be atomic on shared instances.

The problem is to make it atomic without expensive locks. Lacking the 
CAS2 operation (that does a CAS on two arbitrary memory locations 
simultaneously), my first thought was that it is not possible.

Considering it again, I guess it can be done by not using atomic 
increment/decrement, but splitting up the operations. The main idea is 
to no longer touch the data after the reference count has become 0 once:

// CAS returns *var before operation, only modifies if *var == expected
size_t CAS(size_t* var, size_t expected, size_t newval);

struct PayLoad(T)
{
	T* array;
	size_t size;
	size_t refCount;

	PayLoad!T* ref()
	{
		size_t cnt = refCount;
		while(cnt)
		{
			int old = CAS(&refCount, cnt, cnt+1);
			if(old == cnt)
				return this;
			cnt = refCount;
		}
		// in the rare case the payload has become invalid,
		// return a new empty object to avoid having to
		// check for null (could also be null if the container
		// always checks its payload pointer)
		return new PayLoad!T;
	}
	void deref()
	{
		size_t cnt, old;
		do
		{
			assert(refCount);
			cnt = refCount;
			old = CAS(&refCount, cnt, cnt-1);
		}
		while(old != cnt);
		if(refCount == 0)
			free(array);		
	}
}

struct Container(T)
{
	PayLoad!T* payload;

	this()	// I know this doesn't work, but would be convenient
	{
		payload = new Payload!T;
	}
	this(this)
	{
		payload = payload.ref();
	}
	~this()
	{
		payload.deref();
	}
         void opAssign(typeof(this) rhs)
	{
		if(rhs.payload !is payload)
		{
			payload.deref();
			payload = rhs.payload.ref();
		}
	}
}

PayLoad!T will still have to be garbage collected, though.

BTW: Maybe I am misunderstanding it, but according to 
http://dlang.org/operatoroverloading.html overloading opAssign on the 
same type as in "void opAssign(typeof(this) rhs)" is not allowed. Is 
this correct? You find it in phobos as well.

Another BTW: the links to anchors on the same page are broken as they 
don't include the html file.