/*=============================================================================
	CAThreadSafeList.h
	
	$Log: CAThreadSafeList.h,v $
	Revision 1.2.2.1  2005/04/21 19:28:35  dwyatt
	bring over a few things from TOT for the benefit of test tools
	
	Revision 1.3  2005/03/17 23:21:48  dwyatt
	[4054656] fix for gcc4
	
	Revision 1.2  2005/03/11 04:45:59  dwyatt
	a few fixes
	
	Revision 1.1  2005/03/11 01:30:31  dwyatt
	initial checkin
	
	created Thu Mar 10 2005, Doug Wyatt
	Copyright (c) 2005 Apple Computer, Inc.  All Rights Reserved

	$NoKeywords: $
=============================================================================*/

#ifndef __CAThreadSafeList_h__
#define __CAThreadSafeList_h__

#include "CAAtomicFIFO.h"

//  linked list of T's
//	T must define operator ==
template <class T>
class TThreadSafeList {
private:
	enum EEventType { kAdd, kRemove, kClear };
	class Node {
	public:
		Node *		mNext;
		EEventType	mEventType;
		T			mObject;
		
		void	set_next(Node *node) { mNext = node; }
		Node *	get_next() { return mNext; }
	};

public:
	class iterator {
	public:
		iterator() { }
		iterator(Node *n) : mNode(n) { }
		
		bool operator == (const iterator &other) const { return this->mNode == other.mNode; }
		bool operator != (const iterator &other) const { return this->mNode != other.mNode; }
		
		T & operator * () const { return mNode->mObject; }
		
		iterator & operator ++ () { mNode = mNode->get_next(); return *this; }	// preincrement
		iterator operator ++ (int) { iterator tmp = *this; mNode = mNode->get_next(); return tmp; } // postincrement
		
	private:
		Node *		mNode;
	};
	
	TThreadSafeList() { }
	~TThreadSafeList()
	{
		mActiveList.free_all();
		mPendingList.free_all();
		mFreeList.free_all();
	}
	
	// These may be called on any thread
	
	void	deferred_add(const T &obj)	// can be called on any thread
	{
		Node *node = AllocNode();
		node->mEventType = kAdd;
		node->mObject = obj;
		mPendingList.push_atomic(node);
		//mPendingList.dump("pending after add");
	}
	
	void	deferred_remove(const T &obj)	// can be called on any thread
	{
		Node *node = AllocNode();
		node->mEventType = kRemove;
		node->mObject = obj;
		mPendingList.push_atomic(node);
		//mPendingList.dump("pending after remove");
	}
	
	void	deferred_clear()					// can be called on any thread
	{
		Node *node = AllocNode();
		node->mEventType = kClear;
		mPendingList.push_atomic(node);
	}
	
	// These must be called from only one thread
	
	void	update()		// must only be called from one thread
	{
		NodeStack reversed;
		Node *event, *node, *next;
		bool workDone = false, alreadyActive;
		
		// reverse the events so they are in order
		event = mPendingList.pop_all();
		while (event != NULL) {
			next = event->mNext;
			reversed.push_NA(event);
			event = next;
			workDone = true;
		}
		if (workDone) {
			//reversed.dump("pending popped");
			//mActiveList.dump("active before update");
			
			// now process them
			while ((event = reversed.pop_NA()) != NULL) {
				switch (event->mEventType) {
				case kAdd:
					alreadyActive = false;
					for (node = mActiveList.head(); node != NULL; node = node->mNext) {
						if (node->mObject == event->mObject) {
							//printf("already active!!!\n");
							alreadyActive = true;
							break;
						}
					}
					if (!alreadyActive)
						mActiveList.push_NA(event);	// just move the event to become an active node
					else
						FreeNode(event);
					break;
				case kRemove:
					// find matching node in the active list, remove it
					for (Node **pnode = mActiveList.phead(); *pnode != NULL; ) {
						node = *pnode;
						if (node->mObject == event->mObject) {
							*pnode = node->mNext;	// remove from linked list
							FreeNode(node);
							break;
						}
						pnode = &node->mNext;
					}
					// dispose the request node
					FreeNode(event);
					break;
				case kClear:
					for (node = mActiveList.head(); node != NULL; ) {
						next = node->mNext;
						FreeNode(node);
						node = next;
					}
					FreeNode(event);
					break;
				default:
					//printf("invalid node type %d!\n", event->mEventType);
					break;
				}
			}
			//mActiveList.dump("active after update");
		}
	}
	
	iterator begin() const {
		//mActiveList.dump("active at begin");
		return iterator(mActiveList.head());
	}
	iterator end() const { return iterator(NULL); }

	
private:
	Node *	AllocNode()
	{
		Node *node = mFreeList.pop_atomic();
		if (node == NULL)
			node = (Node *)malloc(sizeof(Node));
		return node;
	}
	
	void	FreeNode(Node *node)
	{
		mFreeList.push_atomic(node);
	}

private:
	class NodeStack : public TAtomicStack<Node> {
	public:
		void free_all() {
			Node *node;
			while ((node = this->pop_NA()) != NULL)
				free(node);
		}
		
		Node **	phead() { return &this->mHead; }
		Node *	head() const { return this->mHead; }
		
		/*void	dump(char *label) const
		{
			char buf[1024];
			int count = 0;
			Node *node = mHead;
			sprintf(buf, "%s:", label);
			while (node != NULL) {
				sprintf(buf+strlen(buf), " %p/%d", node, node->mEventType);
				if (++count == 5) { sprintf(buf+strlen(buf), "..."); break; }
				node = node->mNext;
			}
			puts(buf);
		}*/
		
		/*int size() const
		{
			int count = 0;
			for (Node *node = mHead; node != NULL; node = node->mNext)
				++count;
			return count;
		}*/
	};

	NodeStack	mActiveList;	// what's actually in the container - only accessed on one thread
	NodeStack	mPendingList;	// add or remove requests - threadsafe
	NodeStack	mFreeList;		// free nodes for reuse - threadsafe
};

#endif // __CAThreadSafeList_h__