Interesting Idea

[PiMaster]

Sometime during the day I thought of a really interesting way to encapsulate reference counting (if I'm understanding it correctly). The basic idea is that you have a structure similar to an element in a doubly-linked list - it has a pointer to the previous node, the next node, and a value. Now instead of any value, you have a pointer to a value. Whenever you make a new one of these structures (let's call them references) and set it to another reference, that new reference is added to the list. Whenever a reference has new data assigned to it, it takes itself out of the list and starts a new one. When a reference is destroyed, if both its reference pointers are NULL, it deletes the value.

Has this idea ever been implemented?

[Disch]

It sounds like it would just be heavier than normal reference counting (just increasing / decreasing an integer).

Having to remove an object from the list means searching a list which is added overhead. Compare that to just decrementing a counter.

[PiMaster]

While it would require more bytes of data to implement it, I was thinking that the advantage of using something like this would be that it could be used generically, rather than integrated into a specific data type.

Removal of a reference from the list wouldn't require any searching, it would just assign the previous node's next value its next value, and the next value's previous value its previous value.

Some quick code to explain what I mean:

template<typename T>
struct reference{
	protected:
		reference<T>* prev;
		T* value;
		reference<T>* next;
	public:
		reference(){
			prev=NULL;
			value=NULL;
			next=NULL;}
		reference(T& v){
			value=&v;}
		~reference(){
			if(prev==NULL && next==NULL){
				delete value;}
			else{
				if(prev!=NULL){
					prev->next=next;}
				if(next!=NULL){
					next->prev=prev;}}}
		reference& operator=(reference& ref){
			//cut off ties from old list
			if(prev!=NULL){
				prev->next=next;}
			if(next!=NULL){
				next->prev=prev;}
			//connect to new list
			prev=&ref;
			value=ref.value;
			next=ref.next;
			//update surrounding nodes
			ref.next->prev=this;
			ref.next=this;
			return *this;}
		reference& operator=(T* v){
			//cut off ties from old list
			if(prev!=NULL){
				prev->next=next;}
			if(next!=NULL){
				next->prev=prev;}
			//create new list
			prev=NULL;
			value=v;
			next=NULL;}
		//... other operators (if any)
		};

How is reference counting implemented normally?

[ne555]

http://ootips.org/yonat/4dev/smart-pointers.html#Which (there are others method too)

template <typename T>
class reference{
private:
	T *value;
	unsigned int *count;
	void decrement(){
		if(value){
			(*count)--;
			if(*count == 0){ //I am the last one
				delete value;
				delete count;
			}
		}
	}
	void increment(){
		(*count)++;
	}
public:
	reference(T *v = NULL){
		value = v;
		if(v)
			count = new unsigned int (1);
		else
			count = NULL;
	}
	reference(const reference &b){
		value = b.value;
		count = b.count;
		increment();
	}
	reference& operator=(const reference& ref){
		if( this!=&ref ){
			decrement();
			value = ref.value;
			count = ref.count;
			if(value)
				increment();
		}
		return *this;
	}
	~reference(){
		decrement();
	}
};

[PiMaster]

Derp, didn't think of a pointer to a counting variable allocated with new.

And it's already implemented... Oh well, it was worth a try =P

[chrisname]

I did something sort of similar to this to (try to) implement a robust mutex system (it wasn't quite the same as a mutex because it could use mutual exclusion or reference counting, but I can't remember the word for that). I don't remember if it worked or not.