Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

A policy based reference counting implementation for compound objects

, 26 May 2005
Reference counting smart pointers and handles of various flavours.
/////////////////////////////////
// compounds.hpp
//	generic compound objects
//

#pragma once
#include "smart.hpp"
#pragma message ("Compiling " __FILE__)


namespace GE_{ namespace stdx{


	//////////////////
	//	traits classes definig types and type related helper functions

    struct comp_dumb_traits
	{
		template<class Derived>
		class types
		{
		public:
			typedef Derived value;
			typedef Derived* ptr;	//forward pointers
			typedef Derived* wptr;	//backward pointers
		};

		template<class P> //a pointer
		static void clear_ptr(P& p) { p=0; } 

		class base //will hinerit this class
		{
		};

	};

	struct comp_smart_traits
	{
		template<class Derived>
		class types
		{
		public:
			typedef Derived value;
			typedef typename stdx::ptr<Derived>::strong ptr;
			typedef typename stdx::ptr<Derived>::weak wptr;
		};

		template<class P>
		static void clear_ptr(P& p) { p=P(); }

		class base:
			public virtual refcountable
		{
		};
	};

	
	/////////////////////////////// 
	//	an iterator class
	//

	//traits for linear visit iterator
	struct iter_traits_chain
	{
		template<class D>
			struct types
		{
			typedef D* access_t;
			typedef D& reference_t;
		};

		template<class P>
			static P access(const P& p) { return p; }
		template<class D>
			static D& dereference(D* p) { return *p; }

		template<class P>
			static void increment(P& p, int i=1) 
		{ 
			while(p && i>0) p=p->get_next(), i--; 
			while(p && i<0) p=p->get_prev(), i++; 
		}
		
		template<class P>
			static void decrement(P& p, int i=1) 
		{
			while(p && i>0) p=p->get_prev(), i--; 
			while(p && i<0) p=p->get_next(), i++; 
		}

	};

	//traits for deep tree visit iterator
	struct iter_traits_deep:
		public iter_traits_chain
	{
		template<class P>
			static void increment(P& p, int i=1) 
		{ 
			while(p && i>0) p=p->get_deepfirst_next(), i--; 
			while(p && i<0) p=p->get_deepfirst_prev(), i++; 
		}
		
		template<class P>
			static void decrement(P& p, int i=1) 
		{
			while(p && i>0) p=p->get_deepfirst_prev(), i--; 
			while(p && i<0) p=p->get_deepfirst_next(), i++; 
		}
	};

	//the iterator class 
	template<class Compound, 
			class iter_trs = iter_traits_chain,
			class traits = Compound::traits_t >
	class iterator
	{
		friend class iterator;
	private:
		typename traits::types<Compound>::wptr p;
	public:
		typedef traits traits_t;
		typedef iter_trs iter_traits_t;
		typedef Compound value_type;
		typedef typename iter_trs::types<Compound>::access_t pointer;
		typedef typename iter_trs::types<Compound>::reference_t reference;

		iterator() { traits::clear_ptr(p); }
		iterator(const iterator& i) { p = i.p; }
		template<class traits2, class trs2>
			iterator(const iterator<Compound,traits2,trs2>& i) { p = i.p; }
		iterator(const typename traits::types<Compound>::wptr& pD) :p(pD) {}
		iterator& operator=(const iterator& i) { p = i.p; return *this; }

		pointer operator->() const { return iter_trs::access(p); }
		reference operator*() const { return iter_trs::dereference(&*p); }
		iterator& operator++() {  iter_trs::increment(p); return *this; }
		iterator& operator--() {  iter_trs::decrement(p); return *this; }
		iterator operator++(int) { iterator i(*this); ++(*this); return i; }
		iterator operator--(int) { iterator i(*this); --(*this); return i; }
		iterator& operator+=(int i)	{ iter_trs::increment(p,i); return *this; }
		iterator& operator-=(int i) { iter_trs::decrement(p,i); return *this; }
		Compound& operator[](int i) const
		{	iterator it(*this) it+=i; return *it;	}

		bool operator==(const iterator& i) { return p==i.p; }
		bool operator!=(const iterator& i) { return p!=i.p; }
		bool operator<(const iterator& i) { return p<i.p; }
		bool operator!() const { return !p; }
	};
    



	////////////////////////////
	//	collection nodes:
	//	derive from here for self collecting object
	//

	// chain class: link nodes in a bidirectional list
	template<class Derived, class traits = comp_dumb_traits>
	class chain_node:
		public traits::base
	{
	public:
		typedef typename traits::types<Derived>::ptr ptr;
		typedef typename traits::types<Derived>::wptr wptr;
		typedef stdx::iterator<Derived,iter_traits_chain, traits> iterator;

		typedef Derived chain_t;
		typedef traits traits_t;

		ptr get_next() const {return pNext;} 
		wptr get_prev() const {return pPrev;} 
		wptr get_first() { wptr p(pThis()), q; while(!!p) { q=p; p=p->get_prev(); } return q; }
		ptr get_last() { ptr p(pThis()), q; while(!!p) { q=p; p=p->get_next(); } return q; }
		void leave_chain()
		{
			if(!!pNext) P(pNext)->pPrev = pPrev;
			if(!!pPrev) P(pPrev)->pNext = pNext;
			traits::clear_ptr(pNext); traits::clear_ptr(pPrev);
		}

		void set_next(ptr pNewNext)
		{
			if(!pNewNext) return;
			pNewNext->leave_chain();
			if(!!pNext) 
				P(pNext)->pPrev = pNewNext;
			P(pNewNext)->pNext = pNext;
			P(pNewNext)->pPrev= pThis();
			pNext = pNewNext;
		}

		void set_prev(ptr pNewPrev)
		{
			if(!pNewPrev) return;
			pNewPrev->leave_chain();
			if(!!pPrev) 
				P(pPrev)->pNext = pNewPrev;
			P(pNewPrev)->pPrev = pPrev;
			P(pNewPrev)->pNext= pThis();
			pPrev = pNewPrev;
		}

		chain_node()
		{
			traits::clear_ptr(pNext); traits::clear_ptr(pPrev);
		}

		~chain_node() { leave_chain(); }

	private:
		friend class chain_node<Derived>;
		ptr pThis() const { return static_cast<Derived*>(const_cast<chain_node*>(this)); }
		chain_node* P(Derived* p) const { return static_cast<chain_node*>(p); }
		ptr pNext;
		wptr pPrev;

	};

	//hierarchy class: link nodes inside a tree
	template<class Derived, class traits = comp_smart_traits> //type derives from hierarchy_node
	class hierarchy_node:
		public traits::base
	{
	public:
		typedef typename traits::types<Derived>::ptr ptr;
		typedef typename traits::types<Derived>::wptr wptr;

		typedef Derived chain_t;
		typedef traits traits_t;

		typedef stdx::iterator<Derived, iter_traits_chain, traits> shallowiterator;
		typedef stdx::iterator<Derived, iter_traits_deep, traits> deepiterator;

		wptr get_parent() const { return pParent; };
		wptr get_root() { return (!pParent)? pThis(): get_parent()->get_root(); }
		ptr get_first() const { return pFirst; }
		ptr get_next() const { return pNext; }
		ptr get_last() const { return pLast; }
		wptr get_prev() const { return pPrev; }
		unsigned get_childrencount() const { return count; }

		ptr get_deepfirst_next() const
		{
			if(pFirst) return pFirst;
			if(pNext) return pNext;
			wptr p(get_parent());
			while(!!p)
			{
				ptr r(p->get_next());
				if(!!r) return r;
				p = p->get_parent();
			}
			return 0;
		}

		ptr get_deepfirst_last() const
		{
			ptr p(pThis()), q;
			while(!!p)
			{	q = p;	p = p->get_last();	}
			return q;
		}

		ptr get_deepfirst_prev() const
		{
			if(!!pPrev)
				return pPrev->get_deepfirst_last();
			return get_parent();
		}
		
		ptr get_deeplast_next() const
		{
			if(pLast) return pLast;
			if(pPrev) return pPrev;
			wptr p(get_parent());
			while(!!p)
			{
				ptr r(p->get_prev());
				if(!!r) return r;
				p = p->get_parent();
			}
			return 0;
		}

		ptr get_deeplast_last() const
		{
			ptr p(pThis()), q;
			while(!!p)
			{	q = p;	p = p->get_first();	}
			return q;
		}

		ptr get_deeplast_prev() const
		{
			if(!!pNext)
				return pNext->get_deeplast_last();
			return get_parent();
		}

		
		ptr get_child(int idx) const
		{  
			idx%=count; if(idx<0) idx+=count;
			ptr p(get_first()); 
			while(idx--) p = p->get_next(); 
			return p; 
		}

		int get_index()
		{
			if(!pParent) return 0;
			ptr p = get_parent()->get_first();
			ptr th = pThis();
			int idx=0;
			while(p != th) p = p->get_next(), idx++;
			return idx;
		}
		
		void leave_parent()
		{
			ptr keep(pThis());
			if(!pParent) return;
			if(!!pNext) pNext->pPrev = pPrev;
			else pParent->pLast = pPrev;
			if(!!pPrev) pPrev->pNext = pNext;
			else pParent->pFirst = pNext;
			pParent->count--;
			traits::clear_ptr(pParent);
			traits::clear_ptr(pPrev);
			traits::clear_ptr(pNext);
		}

		void set_first(ptr pNewFirst)
		{
			if(!pNewFirst) return;
			pNewFirst->leave_parent();
			if(pFirst)
			{
				pNewFirst->pNext = pFirst;
				pFirst->pPrev = pNewFirst;
			}
			else 
				pLast = pNewFirst;
			pFirst = pNewFirst;
			pNewFirst->pParent = pThis();
			count++;
			return;
		}

		void set_next(ptr pNewNext)
		{
			if(!pNewNext) return pThis;
			ptr keep(pThis());
			pNewNext->leave_parent();
			if(!!pNext)
			{
				pNext->pPrev = pNewNext;
				pNewNext->pNext = pNext;
				pNewNext->pPrev = pThis();
				pNext = pNewNext;
			}
			else
			{
				pNext = pNewNext;
				pNewNext->pPrev = pThis();
				if(!!pParent) pParent->pLast = pNewNext;
			}
			pNewNext->pParent = pParent;
			pParent->count++;
			return;
		}

		void set_last(ptr pNewLast)
		{
			if(!pNewLast) return;
			pNewLast->leave_parent();
			if(pLast)
			{
				pNewLast->pPrev = pLast;
				pLast->pNext = pNewLast;
			}
			else 
				pFirst = pNewLast;
			pLast = pNewLast;
			pNewLast->pParent = pThis();
			count++;
			return;
		}

		void set_prev(ptr pNewPrev)
		{
			if(!pNewPrev) return;
			ptr keep(pThis());
			pNewPrev->leave_parent();
			if(!!pPrev)
			{
				pPrev->pNext = pNewPrev;
				pNewPrev->pPrev = pPrev;
				pNewPrev->pNext = pThis();
				pPrev = pNewPrev;
			}
			else
			{
				pPrev = pNewPrev;
				pNewPrev->pNext = pThis();
				if(!!pParent) pParent->pFirst = pNewPrev;
			}
			pNewPrev->pParent = pParent;
			pParent->count++;
			return;
		}

		void set_at(int idx, ptr pNew)
		{
			if(!count) 
			{
				set_first(pNew);
				return;
			}
            
			if(idx<0)
			{
				idx++; idx%=count; //-1 remains the last
				ptr p(get_last());
				while(idx++) 
					p=p->get_prev();
				p->set_next(pNew);
			}
			else
			{
				idx%=count; //0 remains the first
				ptr p(get_first());
				while(idx--) 
					p=p->get_next();
				p->set_prev(pNew);
			}
			return;
		}

		hierarchy_node() 
		{ 
			count =0 ; 
			traits::clear_ptr(pFirst);
			traits::clear_ptr(pLast);
			traits::clear_ptr(pParent);
			traits::clear_ptr(pPrev);
			traits::clear_ptr(pNext);
		}

	protected:

		//virtual and automatically called with smart nodes
		// call it in the Derived destructor elsewhere
		void on_lastrelease() 
		{
			while(count)
				get_last()->leave_parent();
			leave_parent();
		}

	private:
		friend class hierarchy_node<Derived,traits>;
		Derived* pThis() const { return static_cast<Derived*>(const_cast<hierarchy_node*>(this)); }

		ptr pFirst, pLast, pNext;
		wptr pPrev, pParent;
		unsigned count;
	};
	

	//hierachy of pointers (dual indirection)
	template<class Ptr, class traits=comp_smart_traits> //Ptr is a smart pointer
	class hierarchy_refnode:
		public hierarchy_node<hierarchy_refnode, traits>
	{
	protected:
		Ptr pVal;

		template<class iter_traits>
		struct iter_deref:
			public iter_traits
		{
			template<class D> //D is hierarchy_refnode
				struct types
			{
				typedef typename Ptr::value_type* access_t;
				typedef typename Ptr::value_type& reference_t;
			};

			template<class P> //p is hierarchy_refnode*
				static Ptr::value_type* access(const P& p) { return p->pVal; }
			template<class D>
				static Ptr::value_type& dereference(D* p) { return *p->pVal; }

		};

		friend struct iter_deref;
	public:

		typedef stdx::iterator<hierarchy_refnode, iter_deref<iter_traits_chain>, traits > shallowiterator;
		typedef stdx::iterator<hierarchy_refnode, iter_deref<iter_traits_deep>, traits > deepiterator;

		hierarchy_refnode(const Ptr& p) { pVal = p; }
	};

	//hierachy of values (auto dereferece)
	template<class Type, class traits=comp_smart_traits> //Type is a value
	class hierarchy_valnode:
		public hierarchy_node<hierarchy_valnode, traits>
	{
	protected:
		Type val;

		template<class iter_traits>
		struct iter_deref:
			public iter_traits
		{
			template<class D> //D is hierarchy_valnode
				struct types
			{
				typedef Type* access_t;
				typedef Type& reference_t;
			};

			template<class P> //p is hierarchy_valnode*
				static Type* access(const P& p) { return &p->val; }
			template<class D>
				static Type& dereference(D* p) { return p->val; }

		};

		friend struct iter_deref;

	public:

		typedef stdx::iterator<hierarchy_valnode, iter_deref<iter_traits_chain>, traits > shallowiterator;
		typedef stdx::iterator<hierarchy_valnode, iter_deref<iter_traits_deep>, traits > deepiterator;

		hierarchy_valnode(const Type& v) { val = v; }
	};


}}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Emilio Garavaglia
Architect
Italy Italy
Born and living in Milan (Italy), I'm an engineer in electronics actually working in the ICT department of an important oil/gas & energy company as responsible for planning and engineering of ICT infrastructures.
Interested in programming since the '70s, today I still define architectures for the ICT, deploying dedicated specific client application for engineering purposes, working with C++, MFC, STL, and recently also C# and D.

| Advertise | Privacy | Mobile
Web04 | 2.8.140926.1 | Last Updated 27 May 2005
Article Copyright 2005 by Emilio Garavaglia
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid