Click here to Skip to main content
11,573,935 members (70,679 online)
Click here to Skip to main content
Add your own
alternative version

Single-threaded concurrency model design

, 12 Jul 2009 CPOL 15.4K 275 24
A lightweight library to support single-threaded concurrency with multiple components.
// ContainersInl.h
//
//////////////////////////////////////////////////////////////////////
#pragma once

// Disable level-4 warnings. We've examined them and found non-harmful.
// Compile this file at level 3.
#pragma warning (push, 3)

template <class T> inline void swap_t(T& var1, T& var2)
{
	T var = var1;
	var1 = var2;
	var2 = var;
}

template <class ARG_KEY>
inline size_t MapInlHashKey(ARG_KEY nKey)
{
	return (size_t) nKey;
}

template <class ARG_KEY>
struct TreeInlComparator {
	ARG_KEY m_Key;
	TreeInlComparator(ARG_KEY key)
		:m_Key(key)
	{
	}

	int Compare(ARG_KEY key)
	{
		return (key < m_Key) ? (-1) : (key > m_Key) ? 1 : 0;
	}
};

// The following comparator should be used to compare long strings
template <class T>
struct TreeInlComparator_String {

	const T* m_szTxt;
	ULONG m_nLMatch;
	ULONG m_nRMatch;

	TreeInlComparator_String(const T* txt)
		:m_szTxt(txt)
		,m_nLMatch(0)
		,m_nRMatch(0)
	{
	}
	int Compare(const T* szVal)
	{
		for (ULONG nPos = min(m_nLMatch, m_nRMatch); ; nPos++)
		{
			T chThis = m_szTxt[nPos];
			T chArg = szVal[nPos];
			if (chArg < chThis)
			{
				m_nLMatch = nPos;
				return -1;
			}
			if (chArg > chThis)
			{
				m_nRMatch = nPos;
				return 1;
			}
			if (!chThis)
				return 0;
		}
	}
};



namespace Container
{
	namespace Impl
	{
		// Helper implementation template classes.

		// Counter that inherits any engine.
		template <class Eng, class T_COUNT> class InhCounter
			:public Eng
		{
			T_COUNT m_nCount;
		protected:
			InhCounter() :m_nCount(0) {}

			void zInc() { m_nCount++; }
			void zDec() { ASSERT(m_nCount > 0); m_nCount--; }
			void zResetCount() { m_nCount = 0; }
			void zAssertCount(size_t nVal) const { ASSERT(m_nCount == (T_COUNT) nVal); }
			void zSwapCount(InhCounter& other) { swap_t(m_nCount, other.m_nCount); }

		public:
			typename T_COUNT GetCount() const { return m_nCount; }
			__declspec(property(get=GetCount)) T_COUNT _Count;
		};

		template <class Eng> class InhCounter<Eng, void>
			:public Eng
		{
		protected:
			void zInc() {}
			void zDec() {}
			void zResetCount() {}
			void zAssertCount(size_t nVal) const {}
			void zSwapCount(InhCounter& other) {}
		};

		// Extension to any container that creates/deletes elements dynamically.
		template <class Eng, class CastNode>
		class InhDyn
			:public Eng
		{
		public:
			~InhDyn() { Clear(); }

			// The following methods demand to have delete for CastNode.
			void Clear()
			{
				while (!_Empty)
					delete (CastNode*) zAnyOrderRemove();
			}

			// Must also support random remove.
			void Delete(CastNode* pNode)
			{
				Remove(*pNode);
				delete pNode;
			}
		};


		// Linked list base node. May come with either Prev, Next or both pointers.
		template <bool Prev, bool Next> class Node;
		template <> class Node<true, false> { protected: Node* m_pPrev; template <bool Prev, bool Next, bool Head, bool Tail> friend class ListEngBase; };
		template <> class Node<false, true> { protected: Node* m_pNext; template <bool Prev, bool Next, bool Head, bool Tail> friend class ListEngBase; };
		template <> class Node<true, true> { protected: Node* m_pPrev; Node* m_pNext; template <bool Prev, bool Next, bool Head, bool Tail> friend class ListEngBase; };

		// Base container of either Head, Tail or both pointers.
		template <class Node, bool Head, bool Tail> struct InhHT;
		template <class Node> struct InhHT<Node, true, false>
		{
			Node* m_pHead;
		};
		template <class Node> struct InhHT<Node, false, true>
		{
			Node* m_pTail;
		};
		template <class Node> struct InhHT<Node, true, true>
			:public InhHT<Node, true, false>
			,public InhHT<Node, false, true>
		{
		};

		// Base linked list engine.
		template <bool Prev, bool Next, bool Head, bool Tail>
		class ListEngBase
			:protected InhHT<Node<Prev, Next>, Head, Tail>
		{
		public:
			typedef Node<Prev, Next> Node;

			bool IsEmpty() const { return zIsEmpty<Head>(); }
			__declspec(property(get=IsEmpty)) bool _Empty;

		protected:

			ListEngBase() { Reset(); }
			~ListEngBase() { ASSERT(_Empty); }

			void Reset()
			{
				zSetHead<true>(NULL);
				zSetHead<false>(NULL);
			}
			void Swap(ListEngBase& lst)
			{
				zSwapHead<Head>(lst);
				zSwapTail<Tail>(lst);
			}

#ifdef _DEBUG
			size_t AssertValid() const
			{
				return zAssertValid<Head && Next>();
			}
#endif // _DEBUG

			void Remove(Node& node)
			{
				zRemove<true>(node);
				zRemove<false>(node);
			}

		private:

			// Empty test
			template <bool Head> bool zIsEmpty() const;
			template <> bool zIsEmpty<true>() const { return !m_pHead; }
			template <> bool zIsEmpty<false>() const { return !m_pTail; }

			//
			// The following template functions operate on vise/versa parameter.
			//

			// Head/Tail retrive
			template <bool vise> Node* zGetHead();
			template <> Node* zGetHead<true>() { return m_pHead; }
			template <> Node* zGetHead<false>() { return m_pTail; }
			// Head/Tail set
			template <bool vise> void zSetHead(Node* pVal);
			template <> void zSetHead<true>(Node* pVal) { zSetHeadEx<Head>(pVal); }
			template <> void zSetHead<false>(Node* pVal) { zSetTailEx<Tail>(pVal); }
			template <bool> void zSetHeadEx(Node* pVal) { m_pHead = pVal; }
			template <bool> void zSetTailEx(Node* pVal) { m_pTail = pVal; }
			template <> void zSetHeadEx<false>(Node* pVal) {}
			template <> void zSetTailEx<false>(Node* pVal) {}
			// Node prev/next retrieve
			template <bool vise> static Node* zGetNext(Node&);
			template <> static Node* zGetNext<true>(Node& node) { return node.m_pNext; }
			template <> static Node* zGetNext<false>(Node& node) { return node.m_pPrev; }
			// Node prev/next set
			template <bool vise> static void zSetNext(Node&, Node* pVal);
			template <> static void zSetNext<true>(Node& node, Node* pVal) { zSetNextEx<Next>(node, pVal); }
			template <> static void zSetNext<false>(Node& node, Node* pVal) { zSetPrevEx<Prev>(node, pVal); }
			template <bool> static void zSetNextEx(Node& node, Node* pVal) { node.m_pNext = pVal; }
			template <bool> static void zSetPrevEx(Node& node, Node* pVal) { node.m_pPrev = pVal; }
			template <> static void zSetNextEx<false>(Node& node, Node* pVal) {}
			template <> static void zSetPrevEx<false>(Node& node, Node* pVal) {}
			// Node prev/next assert
#ifdef _DEBUG
			template <bool vise> static void zAssertNext(const Node&, const Node* pVal);
			template <> static void zAssertNext<true>(const Node& node, const Node* pVal) { zAssertNextEx<Next>(node, pVal); }
			template <> static void zAssertNext<false>(const Node& node, const Node* pVal) { zAssertPrevEx<Prev>(node, pVal); }
			template <bool> static void zAssertNextEx(const Node& node, const Node* pVal) { ASSERT(node.m_pNext == pVal); }
			template <bool> static void zAssertPrevEx(const Node& node, const Node* pVal) { ASSERT(node.m_pPrev == pVal); }
			template <> static void zAssertNextEx<false>(const Node& node, const Node* pVal) {}
			template <> static void zAssertPrevEx<false>(const Node& node, const Node* pVal) {}
#endif // _DEBUG
			// Swap
			template <bool> void zSwapHead(ListEngBase& lst) { swap_t(m_pHead, lst.m_pHead); }
			template <bool> void zSwapTail(ListEngBase& lst) { swap_t(m_pTail, lst.m_pTail); }
			template <> void zSwapHead<false>(ListEngBase& lst) {}
			template <> void zSwapTail<false>(ListEngBase& lst) {}

			template <bool vise> void zInsertNextEx(Node& node, Node* pPos, Node* pLink)
			{
				zSetNext<!vise>(node, pPos);							// node->prev = pos
				zSetNext<vise>(node, pLink);							// node->next = link
				if (pLink)
					zSetNext<!vise>(*pLink, &node);						// link->prev = node
				else
					zSetHead<!vise>(&node);								// tail = node
			}
			template <bool vise> void zRemoveNextEx(Node& node, Node* pPos)
			{
				Node* pLink = zGetNext<vise>(node);						// link = node->next
				if (pLink)
					zSetNext<!vise>(*pLink, pPos);						// link->prev = pos
				else
					zSetHead<!vise>(pPos);								// tail = pos
			}
			template <bool vise> void zRemove(Node& node)
			{
				zRemoveNextEx<vise>(node, zGetNext<!vise>(node));
			}

			// Validity test
#ifdef _DEBUG
			template <bool vise> size_t zAssertValid() const
			{
				size_t nCount = 0;
				for (Node* pVal = ((ListEngBase*) this)->zGetHead<vise>(); pVal; ) // val = head
				{
					if (!nCount)
						zAssertNext<!vise>(*pVal, NULL); // !val->prev

					nCount++;
					
					Node* pNext = zGetNext<vise>(*pVal); // next = val->next
					if (!pNext)
						break;

					zAssertNext<!vise>(*pNext, pVal); // next->prev == val
					pVal = pNext;
				}
				return nCount;
			}
#endif // _DEBUG

		protected:
			// Inserts
			template <bool vise> void zInsertNext(Node& node, Node& pos)
			{
				zInsertNextEx<vise>(node, &pos, zGetNext<vise>(pos));	// node, pos, pos->next
				zSetNext<vise>(pos, &node);								// pos->next = node
			}
			template <bool vise> void zInsertHead(Node& node)
			{
				zInsertNextEx<vise>(node, NULL, zGetHead<vise>());		// node, NULL, head
				zSetHead<vise>(&node);									// head = node
			}
			template <bool vise> void zInsertNext(Node& node, Node* pPos)
			{
				if (pPos)
					zInsertNext<vise>(node, *pPos);
				else
					zInsertHead<vise>(node);
			}
			// Removes
			template <bool vise> Node* zRemoveNext(Node& pos)
			{
				Node* pNode = zGetNext<vise>(pos); ASSERT(pNode);		// node = pos->next
				zSetNext<vise>(pos, zGetNext<vise>(*pNode));			// pos->next = node->next
				zRemoveNextEx<vise>(*pNode, &pos);
				return pNode;
			}
			template <bool vise> Node* zRemoveHead()
			{
				Node* pNode = zGetHead<vise>(); ASSERT(pNode);			// node = head
				zSetHead<vise>(zGetNext<vise>(*pNode));					// head = node->next
				zRemoveNextEx<vise>(*pNode, NULL);
				return pNode;
			}
			template <bool vise> Node* zRemoveNext(Node* pPos)
			{
				return pPos ? zRemoveNext<vise>(*pPos) : zRemoveHead<vise>();
			}

			// Any order iteration:
			Node* zAnyOrderRemove() { return zRemoveHead<Head && Next>(); }
		};



	}; // namespace Impl

	//////////////////////////////////////////////////////////////
	// Linked List engine either with or without the InhCounter
	template <bool Prev, bool Next, bool Head, bool Tail, class T_COUNT>
	class ListEng
		:public Impl::InhCounter<Impl::ListEngBase<Prev, Next, Head, Tail>, T_COUNT>
	{
		typedef Impl::ListEngBase<Prev, Next, Head, Tail> Eng;
	protected:
		// should not be instantiated as-is
		ListEng() {}
		~ListEng() {}

	public:
		typedef typename Eng::Node Node;

		void Reset()
		{
			Eng::Reset();
			zResetCount();
		}
		void Swap(ListEng& lst)
		{
			Eng::Swap(lst);
			zSwapCount(lst);
		}

		void AssertValid() const
		{
#ifdef _DEBUG
			zAssertCount(Eng::AssertValid());
#endif // _DEBUG
		}

	protected:
		// vise/Versa
		template <bool vise> void zInsertNext(Node& node, Node& pos) { Eng::zInsertNext<vise>(node, pos); zInc(); }
		template <bool vise> Node* zRemoveNext(Node& pos) { zDec(); return Eng::zRemoveNext<vise>(pos); }
		template <bool vise> void zInsertHead(Node& node) { Eng::zInsertHead<vise>(node); zInc(); }
		template <bool vise> Node* zRemoveHead() { zDec(); return Eng::zRemoveHead<vise>(); }
		template <bool vise> void zInsertNext(Node& node, Node* pPos) { Eng::zInsertNext<vise>(node, pPos); zInc(); }
		template <bool vise> Node* zRemoveNext(Node* pPos) { zDec(); return Eng::zRemoveNext<vise>(pPos); }
		Node* zAnyOrderRemove() { zDec(); return Eng::zAnyOrderRemove(); }

		void zRemove(Node& node)
		{
			Eng::Remove(node);
			zDec();
		}
	};

	// Standard list. Enherits the engine, plus the cast.
	template <class Eng, class CastNode = Eng::Node>
	class ListEx
		:public Eng
	{
		// disable copy constructor and assignment
		ListEx(const ListEx&);
		void operator = (const ListEx&);

	public:

		ListEx() {}
		~ListEx() {}

		// Must have head pointer
		CastNode* GetHead() { return (CastNode*) m_pHead; }
		const CastNode* GetHead() const { return (const CastNode*) m_pHead; }
		__declspec(property(get=GetHead)) CastNode* _Head;
		__declspec(property(get=GetHead)) const CastNode* _Head;

		// Must have tail pointer.
		CastNode* GetTail() { return (CastNode*) m_pTail; }
		const CastNode* GetTail() const { return (const CastNode*) m_pTail; }
		__declspec(property(get=GetTail)) CastNode* _Tail;
		__declspec(property(get=GetTail)) const CastNode* _Tail;

		// Must have forward iteration
		void InsertNext(CastNode& node, CastNode& pos) { zInsertNext<true>(node, pos); }
		CastNode* RemoveNext(CastNode& pos) { return (CastNode*) zRemoveNext<true>(pos); }
		// Must also have the head pointer
		void InsertHead(CastNode& node) { zInsertHead<true>(node); }
		CastNode* RemoveHead() { return (CastNode*) zRemoveHead<true>(); }
		void InsertNext(CastNode& node, CastNode* pPos) { zInsertNext<true>(node, pPos); }
		CastNode* RemoveNext(CastNode* pPos) { return (CastNode*) zRemoveNext<true>(pPos); }

		// Must have backward iteration
		void InsertPrev(CastNode& node, CastNode& pos) { zInsertNext<false>(node, pos); }
		CastNode* RemovePrev(CastNode& pos) { return (CastNode*) zRemoveNext<false>(pos); }
		// Must also have the tail pointer
		void InsertTail(CastNode& node) { zInsertHead<false>(node); }
		CastNode* RemoveTail() { return (CastNode*) zRemoveHead<false>(); }
		void InsertPrev(CastNode& node, CastNode* pPos) { zInsertNext<false>(node, pPos); }
		CastNode* RemovePrev(CastNode* pPos) { return (CastNode*) zRemoveNext<false>(pPos); }

		// Must have both iterations.
		void Remove(CastNode& node) { zRemove(node); }
	};

	// Dynamic linked list. Same as the above, plus allocates and deletes elements.
	template <class Eng, class CastNode = Eng::Node>
	class ListDyn
		:public Impl::InhDyn<ListEx<Eng, CastNode>, CastNode>
	{
		// disable copy constructor and assignment
		ListDyn(const ListDyn&);
		void operator = (const ListDyn&);

	public:
		ListDyn() {}

		// Must have forward iteration
		CastNode* CreateNext(CastNode& pos) { return zCreateNext<true>(pos); }
		void DeleteNext(CastNode& pos) { zDeleteNext<true>(pos); }
		// Must also have the head pointer
		CastNode* CreateHead() { return zCreateHead<true>(); }
		void DeleteHead() { zDeleteHead<true>(); }
		CastNode* CreateNext(CastNode* pPos) { zCreateNext<true>(pPos); }
		void DeleteNext(CastNode* pPos) { zDeleteNext<true>(pPos); }

		// Must have backward iteration
		CastNode* CreatePrev(CastNode& pos) { return zCreateNext<false>(pos); }
		void DeletePrev(CastNode& pos) { zDeleteNext<false>(pos); }
		// Must also have the head pointer
		CastNode* CreateTail() { return zCreateHead<false>(); }
		void DeleteTail() { zDeleteHead<false>(); }
		CastNode* CreatePrev(CastNode* pPos) { zCreateNext<false>(pPos); }
		void DeletePrev(CastNode* pPos) { zDeleteNext<false>(pPos); }

	private:
		// Vise/Versa
		template <bool vise> CastNode* zCreateNext(CastNode& pos) { CastNode* p = new CastNode; zInsertNext<vise>(*p, pos); return p; }
		template <bool vise> void zDeleteNext(CastNode& pos) { delete (CastNode*) zRemoveNext<vise>(pos); }
		template <bool vise> CastNode* zCreateHead() { CastNode* p = new CastNode; zInsertHead<vise>(*p); return p; }
		template <bool vise> void zDeleteHead() { delete (CastNode*) zRemoveHead<vise>(); }
		template <bool vise> CastNode* zCreateNext(CastNode* pPos) { CastNode* p = new CastNode; zInsertNext<vise>(*p, pPos); }
		template <bool vise> void zDeleteNext(CastNode* pPos) { delete (CastNode*) zRemoveNext<vise>(pPos); }
	};

	// Common list engine types
	typedef ListEng<true, true, true, true, void> ListHT;		// double-link, Head + tail.
	typedef ListEng<true, true, true, true, size_t> ListHTC;	// same, counted.

	typedef ListEng<true, true, true, false, void> ListH;		// double-link, head.
	typedef ListEng<true, true, true, false, size_t> ListHC;	// same, counted.

	typedef ListEng<false, true, true, true, void> QueueHT;		// forward-link, Head + tail.
	typedef ListEng<false, true, true, true, size_t> QueueHTC;	// same, counted.

	typedef ListEng<false, true, true, false, void> QueueH;		// forward-link, Head.
	typedef ListEng<false, true, true, false, size_t> QueueHC;	// same, counted.

	// Extended linked list node. Easy cast to a successor type.
	template <class Eng, class CastNode> struct NodeEx :public Eng::Node {
		CastNode* GetNext() { return (CastNode*) m_pNext; }
		const CastNode* GetNext() const { return (const CastNode*) m_pNext; }
		CastNode* GetPrev() { return (CastNode*) m_pPrev; }
		const CastNode* GetPrev() const { return (const CastNode*) m_pPrev; }
		__declspec(property(get=GetNext)) CastNode* _Next;
		__declspec(property(get=GetNext)) const CastNode* _Next;
		__declspec(property(get=GetPrev)) CastNode* _Prev;
		__declspec(property(get=GetPrev)) const CastNode* _Prev;
	};

	//////////////////////////////////////////////////////////////////////
	// Hash Table

	// Base Hash engine
	namespace Impl
	{
		template<class KEY, class ARG_KEY>
		struct HashEngBase
		{

			struct Node :public NodeEx<QueueH, Node> {
				KEY m_Key;
			};

		protected:

			typedef ListEx<QueueH, Node> List;
			typedef ARG_KEY ARG_KEY;

			List* m_pHashTable;
			size_t m_nHashTableCount;

			void Insert(Node& node)
			{
				EntryFromKey((ARG_KEY) node.m_Key).InsertHead(node);
			}
			void Remove(Node& node)
			{
				List& list = EntryFromKey((ARG_KEY) node.m_Key);
				Node* pVal = list._Head;
				if (&node == pVal)
					list.RemoveHead();
				else
				{
					while (&node != pVal->_Next)
						pVal = pVal->_Next;
					list.RemoveNext(pVal);
				}
			}

			void Swap(HashEngBase& other)
			{
				swap_t(m_pHashTable, other.m_pHashTable);
				swap_t(m_nHashTableCount, other.m_nHashTableCount);
			}

			void Reset()
			{
				ZeroMemory(m_pHashTable, m_nHashTableCount * sizeof(List));
			}

		private:

			size_t IndexFromKey(ARG_KEY Key) const
			{
				ASSERT(m_pHashTable && m_nHashTableCount);
				return MapInlHashKey(Key) % m_nHashTableCount;
			}
			List& EntryFromKey(ARG_KEY Key)
			{
				return m_pHashTable[IndexFromKey(Key)];
			}
			const List& EntryFromKey(ARG_KEY Key) const
			{
				return m_pHashTable[IndexFromKey(Key)];
			}
		public:

			HashEngBase()
				:m_pHashTable(NULL)
				,m_nHashTableCount(0)
			{
			}

			Node* Find(ARG_KEY Key)
			{
				for (Node* pNode = EntryFromKey(Key)._Head; ; pNode = pNode->_Next)
				{
					if (!pNode)
						return NULL;
					if (pNode->m_Key == Key)
						return pNode;
				}
				// unreachable
			}
			const Node* Find(ARG_KEY Key) const
			{
				return ((HashEngBase*) this)->Find(Key);
			}

			// The following is for walking through elements. Not recommended to use, better arrange
			// the elements in an extra list.
			Node* GetFirst()
			{
				if (m_pHashTable)
					for (size_t nIndex = 0; nIndex < m_nHashTableCount; nIndex++)
					{
						Node* pVal = m_pHashTable[nIndex]._Head;
						if (pVal)
							return pVal;
					}
				return NULL; // the map is empty
			}
			Node* GetNext(Node* pNode)
			{
				ASSERT(pNode);
				if (pNode->_Next)
					return pNode->_Next;

				for (size_t nIndex = IndexFromKey((ARG_KEY) pNode->m_Key) + 1; nIndex < m_nHashTableCount; nIndex++)
				{
					Node* pVal = m_pHashTable[nIndex]._Head;
					if (pVal)
						return pVal;
				}
				return NULL;
			}
		};

	}; // namespace Impl


	// Hash table engine, either with or without the InhCounter
	template<class KEY, class ARG_KEY, class T_COUNT>
	class HashEng
		:public Impl::InhCounter<Impl::HashEngBase<KEY, ARG_KEY>, T_COUNT>
	{
		typedef Impl::HashEngBase<KEY, ARG_KEY> Eng;
	protected:
		// should not be instantiated as-is
		HashEng() {}
		~HashEng() {}

	public:
		typedef typename Eng::Node Node;

		void Reset()
		{
			Eng::Reset();
			zResetCount();
		}
		void Swap(HashEng& other)
		{
			Eng::Swap(other);
			zSwapCount(other);
		}
		void Insert(Node& node)
		{
			Eng::Insert(node);
			zInc();
		}
		void Insert(Node& node, ARG_KEY key)
		{
			node.m_Key = key;
			Insert(node);
		}
		void Remove(Node& node)
		{
			Eng::Remove(node);
			zDec();
		}
	};

	// Hash table, with cast + table placeholder.
	template <class HashEng, size_t nHashTableCount, class CastNode = HashEng::Node>
	class HashEx
		:public HashEng
	{
		BYTE m_pPlaceHolder[sizeof(HashEng::List) * nHashTableCount];

		// disable copy constructor and assignment
		HashEx(const HashEx&);
		void operator = (const HashEx&);
	public:
		HashEx()
		{
			ZeroMemory(m_pPlaceHolder, sizeof(m_pPlaceHolder));
			m_pHashTable = (HashEng::List*) m_pPlaceHolder;
			m_nHashTableCount = nHashTableCount;
		}

		void Insert(CastNode& node)
		{
			HashEng::Insert(node);
		}
		void Insert(CastNode& node, typename HashEng::ARG_KEY Key)
		{
			HashEng::Insert(node, Key);
		}
		CastNode* Find(typename HashEng::ARG_KEY Key)
		{
			return (CastNode*) HashEng::Find(Key);
		}
		const CastNode* Find(typename HashEng::ARG_KEY Key) const
		{
			return ((HashEx*) this)->Find(Key);
		}
		void Remove(CastNode& node)
		{
			HashEng::Remove(node);
		}
	};

	// Common hash table types
	typedef HashEng<ULONG_PTR, ULONG_PTR, void> HashOrd;	// integer key.
	typedef HashEng<ULONG_PTR, ULONG_PTR, size_t> HashOrdC;	// same, counted.


	//////////////////////////////////////////////////////////////////////
	// Tree
	namespace Impl {

		class TreeEngRaw
		{
		protected:

			class Node {
			protected:

				Node* m_pC[2]; // Left/Right children
				Node* m_pT;
				int m_nBallance; // Negative=Left, Positive=Right


				bool zIsBallanceOk() const { return (m_nBallance >= -1) && (m_nBallance <= 1); }

				int zParentIdx() const
				{
					ASSERT((this == m_pT->m_pC[0]) || (this == m_pT->m_pC[1]));
					return (this == m_pT->m_pC[1]);
				}
				void zSetChildSafe(int nIdx, Node* pChild)
				{
					if (m_pC[nIdx] = pChild)
						pChild->m_pT = this;
				}

#ifdef _DEBUG
				size_t zAssertValid(size_t& nTotal, const Node* pT, size_t nL, size_t nR) const
				{
					ASSERT(m_pT == pT);
					ASSERT(zIsBallanceOk());
					ASSERT(nL + m_nBallance == nR);

					nTotal++;
					return max(nL, nR) + 1;
				}
#endif // _DEBUG

				friend class TreeEngRaw;

				template <class KEY, class ARG_KEY>
				friend struct TreeEngBase;
			};

			Node* m_pRoot;

			void zReplaceFixTop(Node& node, Node& next)
			{
				if (next.m_pT = node.m_pT)
					node.m_pT->m_pC[node.zParentIdx()] = &next;
				else
				{
					ASSERT(&node == m_pRoot);
					m_pRoot = &next;
				}
			}

			bool zRotate(Node& node, int nDir)
			{
				ASSERT((-1 == nDir) || (1 == nDir));
				int nIdx = (1 == nDir);

				ASSERT(node.m_nBallance);
				ASSERT(node.m_nBallance * nDir < 0);

				Node* pNext = node.m_pC[!nIdx];
				ASSERT(pNext && pNext->zIsBallanceOk());

				if (nDir == pNext->m_nBallance)
				{
					VERIFY(!zRotate(*pNext, -nDir));
					pNext = pNext = node.m_pC[!nIdx];
					ASSERT(pNext && pNext->zIsBallanceOk());
					ASSERT(nDir != pNext->m_nBallance);
				}

				bool bDepthDecrease = pNext->m_nBallance && !node.zIsBallanceOk();

				node.m_nBallance += nDir;
				if (pNext->m_nBallance)
				{
					if (!node.m_nBallance)
						pNext->m_nBallance += nDir;
					node.m_nBallance += nDir;
				}
				pNext->m_nBallance += nDir;

				node.zSetChildSafe(!nIdx, pNext->m_pC[nIdx]);

				pNext->m_pC[nIdx] = &node;

				zReplaceFixTop(node, *pNext);

				node.m_pT = pNext;

				return bDepthDecrease;
			}

			void zAdjustBallance(Node* pNode, int nDir, bool bRemoved)
			{
				ASSERT((1 == nDir) || (-1 == nDir));

				while (true)
				{
					ASSERT(pNode && pNode->zIsBallanceOk());

					Node* pT = pNode->m_pT;
					pNode->m_nBallance += nDir;

					int nDirNext;
					if (pT)
						nDirNext = ((0 != pNode->zParentIdx()) ^ bRemoved) ? 1 : -1;

					bool bMatch;
					switch (pNode->m_nBallance)
					{
					default: ASSERT(0);
					case -1:
					case 1:
						bMatch = false;
						break;
					case 0:
						bMatch = true;
						break;

					case -2:
						bMatch = zRotate(*pNode, 1);
						break;

					case 2:
						bMatch = zRotate(*pNode, -1);
						break;
					}

					if (!pT || (bMatch ^ bRemoved))
						break;

					pNode = pT;
					nDir = nDirNext;
				}
			}

			void zRemove(Node& node, Node* pOnlyChild)
			{
				ASSERT(!node.m_pC[0] || !node.m_pC[1]);

				if (pOnlyChild)
					pOnlyChild->m_pT = node.m_pT;

				Node* pT = node.m_pT;
				if (pT)
				{
					int nIdx = node.zParentIdx();
					pT->m_pC[nIdx] = pOnlyChild;

					zAdjustBallance(pT, nIdx ? -1 : 1, true);

				} else
					m_pRoot = pOnlyChild;
			}

			template <int nIdx> static Node* zGetExtr(Node* pPos)
			{
				while (true)
				{
					Node* pVal = pPos->m_pC[nIdx];
					if (!pVal)
						return pPos;
					pPos = pVal;
				}
			}
			template <int nIdx> Node* zGetExtrRoot()
			{
				return m_pRoot ? zGetExtr<nIdx>(m_pRoot) : NULL;
			}


			template <int nIdx>
			Node* zWalk(Node& node)
			{
				Node* pRet = node.m_pC[nIdx];
				if (pRet)
					return zGetExtr<!nIdx>(pRet);

				pRet = &node;
				while (true)
				{
					Node* pParent = pRet->m_pT;
					if (!pParent)
						return NULL;

					if (pRet->zParentIdx() != nIdx)
						return pParent;

					pRet = pParent;
				}
			}

			Node* zAnyOrderRemove()
			{
				Node* pRoot = m_pRoot;
				ASSERT(pRoot);
				zRemove(*pRoot);
				return pRoot;
			}

			void Reset() { m_pRoot = NULL; }
			void Swap(TreeEngRaw& other) { swap_t(m_pRoot, other.m_pRoot); }

			TreeEngRaw() :m_pRoot(NULL) {}


			void zRemove(Node& node)
			{
				if (node.m_pC[0])
					if (node.m_pC[1])
					{
						// find the successor of this node.
						Node* pSucc = zGetExtr<0>(node.m_pC[1]);

						zRemove(*pSucc, pSucc->m_pC[1]);

						pSucc->zSetChildSafe(0, node.m_pC[0]);
						pSucc->zSetChildSafe(1, node.m_pC[1]);
						zReplaceFixTop(node, *pSucc);

						pSucc->m_nBallance = node.m_nBallance;

					} else
						zRemove(node, node.m_pC[0]);
				else
					zRemove(node, node.m_pC[1]);
			}

			void zInsert(Node& node, Node* pT, int nIdx)
			{
				node.m_pC[0] = NULL;
				node.m_pC[1] = NULL;
				node.m_pT = pT;
				node.m_nBallance = 0;

				if (pT)
				{
					ASSERT(!pT->m_pC[nIdx]);
					pT->m_pC[nIdx] = &node;

					zAdjustBallance(pT, nIdx ? 1 : -1, false);

				} else
				{
					ASSERT(!m_pRoot);
					m_pRoot = &node;
				}
			}

		public:

			~TreeEngRaw()
			{
				ASSERT(IsEmpty());
			}
			bool IsEmpty() const { return !m_pRoot; }
			__declspec(property(get=IsEmpty)) bool _Empty;
		};


		template <class KEY, class ARG_KEY>
		struct TreeEngBase
			:public TreeEngRaw
		{
			typedef ARG_KEY ARG_KEY;

			struct Node
				:public TreeEngRaw::Node
			{
				KEY m_Key;

#ifdef _DEBUG
			private:
				size_t zAssertValid(size_t& nTotal, const Node* pT, int nDir) const
				{
					if (!this)
						return 0;

					if (pT)
					{
						TreeInlComparator<ARG_KEY> hint(pT->m_Key);
						int nCmp = hint.Compare(m_Key);
						ASSERT(!nCmp || (nCmp == nDir));
					}

					size_t nL = ((Node*) m_pC[0])->zAssertValid(nTotal, this, -1);
					size_t nR = ((Node*) m_pC[1])->zAssertValid(nTotal, this, 1);
					return TreeEngRaw::Node::zAssertValid(nTotal, pT, nL, nR);
				}
				friend struct TreeEngBase;
#endif // _DEBUG
			};
		private:

			template <bool bExact, int nDir>
			Node* zFind(ARG_KEY Key)
			{
				TreeInlComparator<ARG_KEY> hint(Key);
				Node* pMatch = NULL;

				for (Node* pNode = (Node*) m_pRoot; pNode; )
				{
					int nCmp = hint.Compare(pNode->m_Key);

					if (bExact && !nCmp)
						return pNode; // exact match.

					if (nCmp == nDir)
						pMatch = pNode;

					pNode = (Node*) pNode->m_pC[nCmp < 0];
				}
				return pMatch;
			}

		public:

			Node* Find(ARG_KEY Key) { return zFind<true, 0>(Key); }
			Node* FindMin() { return (Node*) zGetExtrRoot<0>(); }
			Node* FindMax() { return (Node*) zGetExtrRoot<1>(); }
			Node* FindSmaller(ARG_KEY Key) { return zFind<false, -1>(Key); }
			Node* FindBigger(ARG_KEY Key) { return zFind<false, 1>(Key); }
			Node* FindExactSmaller(ARG_KEY Key) { return zFind<true, -1>(Key); }
			Node* FindExactBigger(ARG_KEY Key) { return zFind<true, 1>(Key); }

		protected:

#ifdef _DEBUG
			size_t AssertValid() const
			{
				size_t nTotal = 0;
				((Node*) m_pRoot)->zAssertValid(nTotal, NULL, 0);
				return nTotal;
			}
#endif // _DEBUG

			void zInsert(Node& node)
			{
				if (m_pRoot)
				{
					TreeInlComparator<ARG_KEY> hint(node.m_Key);
					for (Node* pNode = (Node*) m_pRoot; ; )
					{
						int nIdx = (hint.Compare(pNode->m_Key) < 0);
						if (!pNode->m_pC[nIdx])
						{
							TreeEngRaw::zInsert(node, pNode, nIdx);
							break;
						}
						pNode = (Node*) pNode->m_pC[nIdx];
					}
				}
				else
					TreeEngRaw::zInsert(node, NULL, 0);
			}
			void zRemove(Node& node)
			{
				TreeEngRaw::zRemove(node);
			}

			Node* zAnyOrderRemove() { return (Node*) TreeEngRaw::zAnyOrderRemove(); }

			Node* zWalkL(Node& node) { return (Node*) TreeEngRaw::zWalk<0>(node); }
			Node* zWalkR(Node& node) { return (Node*) TreeEngRaw::zWalk<1>(node); }

			template <int nIdx>
			Node* zWalkEqual(Node& node)
			{
				Node* pVal = (Node*) zWalk<nIdx>(node);
				if (pVal)
				{
					TreeInlComparator<ARG_KEY> hint(node.m_Key);
					if (!hint.Compare(pVal->m_Key))
						return pVal;
				}
				return NULL;
			}

			template <int nIdx>
			Node* zGetExtrEqual(Node* pPos)
			{
				while (true)
				{
					Node* pVal = zWalkEqual<nIdx>(*pPos);
					if (!pVal)
						return pPos;

					pPos = pVal;
				}
				return NULL;
			}

			Node* zWalkEqualL(Node& node) { return zWalkEqual<0>(node); }
			Node* zWalkEqualR(Node& node) { return zWalkEqual<1>(node); }

			Node* zWalkEqualMin(Node& node) { return zGetExtrEqual<0>(&node); }
			Node* zWalkEqualMax(Node& node) { return zGetExtrEqual<1>(&node); }
		};


	}; // namespace Impl

	template <class KEY, class ARG_KEY, class T_COUNT>
	class TreeEng
		:public Impl::InhCounter<Impl::TreeEngBase<KEY, ARG_KEY>, T_COUNT>
	{
	protected:
		// should not be instantiated as-is
		TreeEng() {}
		~TreeEng() {}

	public:
		typedef Impl::TreeEngBase<KEY, ARG_KEY> Eng;
		typedef typename Eng::Node Node;

		void Reset()
		{
			Eng::Reset();
			zResetCount();
		}
		void Swap(TreeEng& other)
		{
			Eng::Swap(other);
			zSwapCount(other);
		}
		void Insert(Node& node)
		{
			Eng::zInsert(node);
			zInc();
		}
		void Insert(Node& node, ARG_KEY key)
		{
			node.m_Key = key;
			Insert(node);
		}
		void Remove(Node& node)
		{
			Eng::zRemove(node);
			zDec();
		}
		void AssertValid()
		{
#ifdef _DEBUG
			zAssertCount(Eng::AssertValid());
#endif // _DEBUG
		}

		Node* zAnyOrderRemove() { zDec(); return Eng::zAnyOrderRemove(); }
	};

	// Tree with cast either with or without the count.
	template <class TreeEng, class CastNode = TreeEng::Node>
	class TreeEx
		:public TreeEng
	{
		// disable copy constructor and assignment
		TreeEx(const TreeEx&);
		void operator = (const TreeEx&);
	public:
		TreeEx() {}

		CastNode* Find(typename TreeEng::ARG_KEY Key)
			{ return (CastNode*) TreeEng::Find(Key); }
		CastNode* FindMin()
			{ return (CastNode*) TreeEng::FindMin(); }
		CastNode* FindMax()
			{ return (CastNode*) TreeEng::FindMax(); }
		CastNode* FindSmaller(typename TreeEng::ARG_KEY Key)
			{ return (CastNode*) TreeEng::FindSmaller(Key); }
		CastNode* FindBigger(typename TreeEng::ARG_KEY Key)
			{ return (CastNode*) TreeEng::FindBigger(Key); }
		CastNode* FindExactSmaller(typename TreeEng::ARG_KEY Key)
			{ return (CastNode*) TreeEng::FindExactSmaller(Key); }
		CastNode* FindExactBigger(typename TreeEng::ARG_KEY Key)
			{ return (CastNode*) TreeEng::FindExactBigger(Key); }
		CastNode* FindNext(CastNode& node)
			{ return (CastNode*) TreeEng::zWalkR(node); }
		CastNode* FindPrev(CastNode& node)
			{ return (CastNode*) TreeEng::zWalkL(node); }

		CastNode* FindNextEqual(CastNode& node)
			{ return (CastNode*) TreeEng::zWalkEqualR(node); }
		CastNode* FindPrevEqual(CastNode& node)
			{ return (CastNode*) TreeEng::zWalkEqualL(node); }
		CastNode* FindMinEqual(CastNode& node)
			{ return (CastNode*) TreeEng::zWalkEqualMin(node); }
		CastNode* FindMaxEqual(CastNode& node)
			{ return (CastNode*) TreeEng::zWalkEqualMax(node); }




		const CastNode* Find(typename TreeEng::ARG_KEY Key) const
			{ return ((TreeEx*) this)->Find(Key); }
		const CastNode* FindMin() const
			{ return ((TreeEx*) this)->FindMin(); }
		const CastNode* FindMax() const
			{ return ((TreeEx*) this)->FindMax(); }
		const CastNode* FindSmaller(typename TreeEng::ARG_KEY Key) const
			{ return ((TreeEx*) this)->FindSmaller(Key); }
		const CastNode* FindBigger(typename TreeEng::ARG_KEY Key) const
			{ return ((TreeEx*) this)->FindBigger(Key); }
		const CastNode* FindExactSmaller(typename TreeEng::ARG_KEY Key) const
			{ return ((TreeEx*) this)->FindExactSmaller(Key); }
		const CastNode* FindExactBigger(typename TreeEng::ARG_KEY Key) const
			{ return ((TreeEx*) this)->FindExactBigger(Key); }
		const CastNode* FindNext(const CastNode& node) const
			{ return (const CastNode*) ((TreeEx*) this)->zWalkR((CastNode&) node); }
		const CastNode* FindPrev(const CastNode& node) const
			{ return (const CastNode*) ((TreeEx*) this)->zWalkL((CastNode&) node); }

		const CastNode* FindNextEqual(CastNode& node) const
			{ return (CastNode*) ((TreeEx*) this)->TreeEng::zWalkEqualR(node); }
		const CastNode* FindPrevEqual(CastNode& node) const
			{ return (CastNode*) ((TreeEx*) this)->TreeEng::zWalkEqualL(node); }
		const CastNode* FindMinEqual(CastNode& node) const
			{ return (CastNode*) ((TreeEx*) this)->TreeEng::zWalkEqualMin(node); }
		const CastNode* FindMaxEqual(CastNode& node) const
			{ return (CastNode*) ((TreeEx*) this)->TreeEng::zWalkEqualMax(node); }

		void Insert(CastNode& node)
		{
			TreeEng::Insert(node);
		}
		void Insert(CastNode& node, typename TreeEng::ARG_KEY key)
		{
			TreeEng::Insert(node, key);
		}
		void Remove(CastNode& node) { TreeEng::Remove(node); }
	};

	// Tree with cast either with or without the count.
	template <class TreeEng, class CastNode = TreeEng::Node>
	class TreeDyn
		:public Impl::InhDyn<TreeEx<TreeEng, CastNode>, CastNode>
	{
		// disable copy constructor and assignment
		TreeDyn(const TreeDyn&);
		void operator = (const TreeDyn&);
	public:
		TreeDyn() {}

		// The following methods demand to have new/delete for the CastNode.
		CastNode* Create(typename TreeEng::ARG_KEY key)
		{
			CastNode* pNode = new CastNode;
			Insert(*pNode, key);
			return pNode;
		}
	};

	// Common hash table types
	typedef TreeEng<ULONG_PTR, ULONG_PTR, void> TreeOrd;	// integer key.
	typedef TreeEng<ULONG_PTR, ULONG_PTR, size_t> TreeOrdC;	// same, counted.

}; // namespace Container

#pragma warning (pop) // Restore warnings level.

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

valdok
Software Developer (Senior)
Israel Israel
My name is Vladislav Gelfer, I was born in Kiev (former Soviet Union), since 1993 I live in Israel.
In programming I'm interested mostly in low-level, OOP design, DSP and multimedia.
Besides of the programming I like physics, math, digital photography.

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150624.2 | Last Updated 12 Jul 2009
Article Copyright 2009 by valdok
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid