merge from viewer-release

1 files changed, 0 insertions, 1397 deletions

diff --git a/indra/llcommon/doublelinkedlist.h b/indra/llcommon/doublelinkedlist.h
deleted file mode 100755
index 0aeaa69df3..0000000000
--- a/indra/llcommon/doublelinkedlist.h
+++ /dev/null
@@ -1,1397 +0,0 @@
-/** 
- * @file doublelinkedlist.h
- * @brief Provides a standard doubly linked list for fun and profit.
- *
- * $LicenseInfo:firstyear=2001&license=viewerlgpl$
- * Second Life Viewer Source Code
- * Copyright (C) 2010, Linden Research, Inc.
- * 
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation;
- * version 2.1 of the License only.
- * 
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- * 
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- * 
- * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
- * $/LicenseInfo$
- */
-
-#ifndef LL_DOUBLELINKEDLIST_H
-#define LL_DOUBLELINKEDLIST_H
-
-#include "llerror.h"
-#include "llrand.h"
-
-// node that actually contains the data
-template <class DATA_TYPE> class LLDoubleLinkedNode
-{
-public:
-	DATA_TYPE			*mDatap;
-	LLDoubleLinkedNode	*mNextp;
-	LLDoubleLinkedNode	*mPrevp;
-
-
-public:
-	// assign the mDatap pointer
-	LLDoubleLinkedNode(DATA_TYPE *data);
-
-	// destructor does not, by default, destroy associated data
-	// however, the mDatap must be NULL to ensure that we aren't causing memory leaks
-	~LLDoubleLinkedNode();
-
-	// delete associated data and NULL out pointer
-	void deleteData();
-
-	// remove associated data and NULL out pointer
-	void removeData();
-};
-
-
-const U32 LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH = 4;
-
-template <class DATA_TYPE> class LLDoubleLinkedList
-{
-private:
-	LLDoubleLinkedNode<DATA_TYPE> mHead;		// head node
-	LLDoubleLinkedNode<DATA_TYPE> mTail;		// tail node
-	LLDoubleLinkedNode<DATA_TYPE> *mQueuep;		// The node in the batter's box
-	LLDoubleLinkedNode<DATA_TYPE> *mCurrentp;	// The node we're talking about
-
-	// The state stack allows nested exploration of the LLDoubleLinkedList
-	// but should be used with great care
-	LLDoubleLinkedNode<DATA_TYPE> *mQueuepStack[LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH];
-	LLDoubleLinkedNode<DATA_TYPE> *mCurrentpStack[LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH];
-	U32 mStateStackDepth;
-	U32	mCount;
-
-	// mInsertBefore is a pointer to a user-set function that returns 
-	// TRUE if "first" should be located before "second"
-	// NOTE: mInsertBefore() should never return TRUE when ("first" == "second")
-	// or never-ending loops can occur
-	BOOL				(*mInsertBefore)(DATA_TYPE *first, DATA_TYPE *second);	
-																				
-public:
-	LLDoubleLinkedList();
-
-	// destructor destroys list and nodes, but not data in nodes
-	~LLDoubleLinkedList();
-
-	// put data into a node and stick it at the front of the list
-	// set mCurrentp to mQueuep
-	void addData(DATA_TYPE *data);
-
-	// put data into a node and stick it at the end of the list
-	// set mCurrentp to mQueuep
-	void addDataAtEnd(DATA_TYPE *data);
-
-	S32 getLength() const;
-	// search the list starting at mHead.mNextp and remove the link with mDatap == data
-	// set mCurrentp to mQueuep
-	// return TRUE if found, FALSE if not found
-	BOOL removeData(const DATA_TYPE *data);
-
-	// search the list starting at mHead.mNextp and delete the link with mDatap == data
-	// set mCurrentp to mQueuep
-	// return TRUE if found, FALSE if not found
-	BOOL deleteData(DATA_TYPE *data);
-
-	// remove all nodes from the list and delete the associated data
-	void deleteAllData();
-
-	// remove all nodes from the list but do not delete data
-	void removeAllNodes();
-
-	BOOL isEmpty();
-
-	// check to see if data is in list
-	// set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep
-	// return TRUE if found, FALSE if not found
-	BOOL	checkData(const DATA_TYPE *data);
-
-	// NOTE: This next two funtions are only included here 
-	// for those too familiar with the LLLinkedList template class.
-	// They are depreciated.  resetList() is unecessary while 
-	// getCurrentData() is identical to getNextData() and has
-	// a misleading name.
-	//
-	// The recommended way to loop through a list is as follows:
-	//
-	// datap = list.getFirstData();
-	// while (datap)
-	// {
-	//     /* do stuff */
-	//     datap = list.getNextData();
-	// }
-
-		// place mQueuep on mHead node
-		void resetList();
-	
-		// return the data currently pointed to, 
-		// set mCurrentp to that node and bump mQueuep down the list
-		// NOTE: this function is identical to getNextData()
-		DATA_TYPE *getCurrentData();
-
-
-	// reset the list and return the data currently pointed to, 
-	// set mCurrentp to that node and bump mQueuep down the list
-	DATA_TYPE *getFirstData();
-
-
-	// reset the list and return the data at position n, set mCurentp 
-	// to that node and bump mQueuep down the list
-	// Note: n=0 will behave like getFirstData()
-	DATA_TYPE *getNthData(U32 n);
-
-	// reset the list and return the last data in it, 
-	// set mCurrentp to that node and bump mQueuep up the list
-	DATA_TYPE *getLastData();
-
-	// return data in mQueuep,
-	// set mCurrentp mQueuep and bump mQueuep down the list
-	DATA_TYPE *getNextData();
-
-	// return the data in mQueuep, 
-	// set mCurrentp to mQueuep and bump mQueuep up the list
-	DATA_TYPE *getPreviousData();
-
-	// remove the Node at mCurrentp
-	// set mCurrentp to mQueuep
-	void removeCurrentData();
-
-	// delete the Node at mCurrentp
-	// set mCurrentp to mQueuep
-	void deleteCurrentData();
-
-	// remove the Node at mCurrentp and insert it into newlist
-	// set mCurrentp to mQueuep
-	void moveCurrentData(LLDoubleLinkedList<DATA_TYPE> *newlist);
-
-	// insert the node in front of mCurrentp
-	// set mCurrentp to mQueuep
-	void insertNode(LLDoubleLinkedNode<DATA_TYPE> *node);
-
-	// insert the data in front of mCurrentp
-	// set mCurrentp to mQueuep
-	void insertData(DATA_TYPE *data);
-
-	// if mCurrentp has a previous node then :
-	//   * swaps mCurrentp with its previous
-	//   * set mCurrentp to mQueuep
-	//     (convenient for forward bubble-sort)
-	// otherwise does nothing
-	void swapCurrentWithPrevious();
-
-	// if mCurrentp has a next node then :
-	//   * swaps mCurrentp with its next
-	//   * set mCurrentp to mQueuep
-	//     (convenient for backwards bubble-sort)
-	// otherwise does nothing
-	void swapCurrentWithNext();
-
-	// move mCurrentp to the front of the list
-	// set mCurrentp to mQueuep
-	void moveCurrentToFront();
-	
-	// move mCurrentp to the end of the list
-	// set mCurrentp to mQueuep
-	void moveCurrentToEnd();
-
-	// set mInsertBefore
-	void setInsertBefore(BOOL (*insert_before)(DATA_TYPE *first, DATA_TYPE *second));
-
-	// add data in front of first node for which mInsertBefore(datap, node->mDatap) returns TRUE
-	// set mCurrentp to mQueuep
-	BOOL addDataSorted(DATA_TYPE *datap);
-
-	// sort the list using bubble-sort
-	// Yes, this is a different name than the same function in LLLinkedList.
-	// When it comes time for a name consolidation hopefully this one will win.
-	BOOL bubbleSort();
-
-	// does a single bubble sort pass on the list
-	BOOL lazyBubbleSort();
-
-	// returns TRUE if state successfully pushed (state stack not full)
-	BOOL pushState();
-
-	// returns TRUE if state successfully popped (state stack not empty)
-	BOOL popState();
-
-	// empties the state stack
-	void clearStateStack();
-
-	// randomly move the the links in the list for debug or (Discordian) purposes
-	// sets mCurrentp and mQueuep to top of list
-	void scramble();
-
-private:
-	// add node to beginning of list
-	// set mCurrentp to mQueuep
-	void addNode(LLDoubleLinkedNode<DATA_TYPE> *node);
-
-	// add node to end of list
-	// set mCurrentp to mQueuep
-	void addNodeAtEnd(LLDoubleLinkedNode<DATA_TYPE> *node);
-};
-
-//#endif
-
-////////////////////////////////////////////////////////////////////////////////////////////
-
-// doublelinkedlist.cpp
-// LLDoubleLinkedList template class implementation file.
-// Provides a standard doubly linked list for fun and profit.
-// 
-// Copyright 2001, Linden Research, Inc.
-
-//#include "llerror.h"
-//#include "doublelinkedlist.h"
-
-//////////////////////////////////////////////////////////////////////////////////////////
-// LLDoubleLinkedNode
-//////////////////////////////////////////////////////////////////////////////////////////
-
-
-// assign the mDatap pointer
-template <class DATA_TYPE>
-LLDoubleLinkedNode<DATA_TYPE>::LLDoubleLinkedNode(DATA_TYPE *data) : 
-	mDatap(data), mNextp(NULL), mPrevp(NULL)
-{
-}
-
-
-// destructor does not, by default, destroy associated data
-// however, the mDatap must be NULL to ensure that we aren't causing memory leaks
-template <class DATA_TYPE>
-LLDoubleLinkedNode<DATA_TYPE>::~LLDoubleLinkedNode()
-{
-	if (mDatap)
-	{
-		llerror("Attempting to call LLDoubleLinkedNode destructor with a non-null mDatap!", 1);
-	}
-}
-
-
-// delete associated data and NULL out pointer
-template <class DATA_TYPE>
-void LLDoubleLinkedNode<DATA_TYPE>::deleteData()
-{
-	delete mDatap;
-	mDatap = NULL;
-}
-
-
-template <class DATA_TYPE>
-void LLDoubleLinkedNode<DATA_TYPE>::removeData()
-{
-	mDatap = NULL;
-}
-
-
-//////////////////////////////////////////////////////////////////////////////////////
-// LLDoubleLinkedList
-//////////////////////////////////////////////////////////////////////////////////////
-
-//                                   <------- up -------
-//
-//                                               mCurrentp
-//                                   mQueuep         |
-//                                      |            |
-//                                      |            | 
-//                      .------.     .------.     .------.      .------.
-//                      |      |---->|      |---->|      |----->|      |-----> NULL
-//           NULL <-----|      |<----|      |<----|      |<-----|      |
-//                     _'------'     '------'     '------'      '------:_
-//             .------. /|               |             |               |\ .------.
-//  NULL <-----|mHead |/                 |         mQueuep               \|mTail |-----> NULL
-//             |      |               mCurrentp                           |      |
-//             '------'                                                   '------'
-//                               -------- down --------->
-
-template <class DATA_TYPE>
-LLDoubleLinkedList<DATA_TYPE>::LLDoubleLinkedList()
-: mHead(NULL), mTail(NULL), mQueuep(NULL)
-{
-	mCurrentp = mHead.mNextp;
-	mQueuep = mHead.mNextp;
-	mStateStackDepth = 0;
-	mCount = 0;
-	mInsertBefore = NULL;
-}
-
-
-// destructor destroys list and nodes, but not data in nodes
-template <class DATA_TYPE>
-LLDoubleLinkedList<DATA_TYPE>::~LLDoubleLinkedList()
-{
-	removeAllNodes();
-}
-
-
-// put data into a node and stick it at the front of the list
-// doesn't change mCurrentp nor mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::addData(DATA_TYPE *data)
-{
-	// don't allow NULL to be passed to addData
-	if (!data)
-	{
-		llerror("NULL pointer passed to LLDoubleLinkedList::addData()", 0);
-	}
-
-	// make the new node
-	LLDoubleLinkedNode<DATA_TYPE> *temp = new LLDoubleLinkedNode<DATA_TYPE> (data);
-
-	// add the node to the front of the list
-	temp->mPrevp = NULL; 
-	temp->mNextp = mHead.mNextp;
-	mHead.mNextp = temp;
-
-	// if there's something in the list, fix its back pointer
-	if (temp->mNextp)
-	{
-		temp->mNextp->mPrevp = temp;
-	}
-	// otherwise, fix the tail of the list
-	else 
-	{
-		mTail.mPrevp = temp;
-	}
-
-	mCount++;
-}
-
-
-// put data into a node and stick it at the end of the list
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::addDataAtEnd(DATA_TYPE *data)
-{
-	// don't allow NULL to be passed to addData
-	if (!data)
-	{
-		llerror("NULL pointer passed to LLDoubleLinkedList::addData()", 0);
-	}
-
-	// make the new node
-	LLDoubleLinkedNode<DATA_TYPE> *nodep = new LLDoubleLinkedNode<DATA_TYPE>(data);
-
-	addNodeAtEnd(nodep);
-	mCount++;
-}
-
-
-// search the list starting at mHead.mNextp and remove the link with mDatap == data
-// set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data
-// return TRUE if found, FALSE if not found
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::removeData(const DATA_TYPE *data)
-{
-	BOOL b_found = FALSE;
-	// don't allow NULL to be passed to addData
-	if (!data)
-	{
-		llerror("NULL pointer passed to LLDoubleLinkedList::removeData()", 0);
-	}
-
-	mCurrentp = mHead.mNextp;
-
-	while (mCurrentp)
-	{
-		if (mCurrentp->mDatap == data)
-		{
-			b_found = TRUE;
-
-			// if there is a next one, fix it
-			if (mCurrentp->mNextp)
-			{
-				mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-			}
-			else // we are at end of list
-			{
-				mTail.mPrevp = mCurrentp->mPrevp;
-			}
-
-			// if there is a previous one, fix it
-			if (mCurrentp->mPrevp)
-			{
-				mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-			}
-			else // we are at beginning of list
-			{
-				mHead.mNextp = mCurrentp->mNextp;
-			}
-
-			// remove the node
-			mCurrentp->removeData();
-			delete mCurrentp;
-			mCount--;
-			break;
-		}
-		mCurrentp = mCurrentp->mNextp; 
-	}
-
-	// reset the list back to where it was
-	if (mCurrentp == mQueuep)
-	{
-		mCurrentp = mQueuep = NULL;
-	}
-	else
-	{
-		mCurrentp = mQueuep;
-	}
-
-	return b_found;
-}
-
-
-// search the list starting at mHead.mNextp and delete the link with mDatap == data
-// set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data
-// return TRUE if found, FALSE if not found
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::deleteData(DATA_TYPE *data)
-{
-	BOOL b_found = FALSE;
-	// don't allow NULL to be passed to addData
-	if (!data)
-	{
-		llerror("NULL pointer passed to LLDoubleLinkedList::deleteData()", 0);
-	}
-
-	mCurrentp = mHead.mNextp;
-
-	while (mCurrentp)
-	{
-		if (mCurrentp->mDatap == data)
-		{
-			b_found = TRUE;
-
-			// if there is a next one, fix it
-			if (mCurrentp->mNextp)
-			{
-				mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-			}
-			else // we are at end of list
-			{
-				mTail.mPrevp = mCurrentp->mPrevp;
-			}
-
-			// if there is a previous one, fix it
-			if (mCurrentp->mPrevp)
-			{
-				mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-			}
-			else // we are at beginning of list
-			{
-				mHead.mNextp = mCurrentp->mNextp;
-			}
-
-			// remove the node
-			mCurrentp->deleteData();
-			delete mCurrentp;
-			mCount--;
-			break;
-		}
-		mCurrentp = mCurrentp->mNextp;
-	}
-
-	// reset the list back to where it was
-	if (mCurrentp == mQueuep)
-	{
-		mCurrentp = mQueuep = NULL;
-	}
-	else
-	{
-		mCurrentp = mQueuep;
-	}
-
-	return b_found;
-}
-
-
-// remove all nodes from the list and delete the associated data
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::deleteAllData()
-{
-	mCurrentp = mHead.mNextp;
-
-	while (mCurrentp)
-	{
-		mQueuep = mCurrentp->mNextp;
-		mCurrentp->deleteData();
-		delete mCurrentp;
-		mCurrentp = mQueuep;
-	}
-
-	// reset mHead and mQueuep
-	mHead.mNextp = NULL;
-	mTail.mPrevp = NULL;
-	mCurrentp = mHead.mNextp;
-	mQueuep = mHead.mNextp;
-	mStateStackDepth = 0;
-	mCount = 0;
-}
-
-
-// remove all nodes from the list but do not delete associated data
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::removeAllNodes()
-{
-	mCurrentp = mHead.mNextp;
-
-	while (mCurrentp)
-	{
-		mQueuep = mCurrentp->mNextp;
-		mCurrentp->removeData();
-		delete mCurrentp;
-		mCurrentp = mQueuep;
-	}
-
-	// reset mHead and mCurrentp
-	mHead.mNextp = NULL;
-	mTail.mPrevp = NULL;
-	mCurrentp = mHead.mNextp;
-	mQueuep = mHead.mNextp;
-	mStateStackDepth = 0;
-	mCount = 0;
-}
-
-template <class DATA_TYPE>
-S32 LLDoubleLinkedList<DATA_TYPE>::getLength() const
-{
-//	U32	length = 0;
-//	for (LLDoubleLinkedNode<DATA_TYPE>* temp = mHead.mNextp; temp != NULL; temp = temp->mNextp)
-//	{
-//		length++;
-//	}
-	return mCount;
-}
-
-// check to see if data is in list
-// set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep
-// return TRUE if found, FALSE if not found
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::checkData(const DATA_TYPE *data)
-{
-	mCurrentp = mHead.mNextp;
-
-	while (mCurrentp)
-	{
-		if (mCurrentp->mDatap == data)
-		{
-			mQueuep = mCurrentp;
-			return TRUE;
-		}
-		mCurrentp = mCurrentp->mNextp;
-	}
-
-	mCurrentp = mQueuep;
-	return FALSE;
-}
-
-// NOTE: This next two funtions are only included here 
-// for those too familiar with the LLLinkedList template class.
-// They are depreciated.  resetList() is unecessary while 
-// getCurrentData() is identical to getNextData() and has
-// a misleading name.
-//
-// The recommended way to loop through a list is as follows:
-//
-// datap = list.getFirstData();
-// while (datap)
-// {
-//     /* do stuff */
-//     datap = list.getNextData();
-// }
-
-	// place mCurrentp and mQueuep on first node
-	template <class DATA_TYPE>
-	void LLDoubleLinkedList<DATA_TYPE>::resetList()
-	{
-		mCurrentp = mHead.mNextp;
-		mQueuep = mHead.mNextp;
-		mStateStackDepth = 0;
-	}
-	
-	
-	// return the data currently pointed to, 
-	// set mCurrentp to that node and bump mQueuep down the list
-	template <class DATA_TYPE>
-	DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getCurrentData()
-	{
-		if (mQueuep)
-		{
-			mCurrentp = mQueuep;
-			mQueuep = mQueuep->mNextp;
-			return mCurrentp->mDatap;
-		}
-		else
-		{
-			return NULL;
-		}
-	}
-
-
-// reset the list and return the data currently pointed to, 
-// set mCurrentp to that node and bump mQueuep down the list
-template <class DATA_TYPE>
-DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getFirstData()
-{
-	mQueuep = mHead.mNextp;
-	mCurrentp = mQueuep;
-	if (mQueuep)
-	{
-		mQueuep = mQueuep->mNextp;
-		return mCurrentp->mDatap;
-	}
-	else
-	{
-		return NULL;
-	}
-}
-
-
-// reset the list and return the data at position n, set mCurentp 
-// to that node and bump mQueuep down the list
-// Note: n=0 will behave like getFirstData()
-template <class DATA_TYPE>
-DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getNthData(U32 n)
-{
-	mCurrentp = mHead.mNextp;
-
-	if (mCurrentp)
-	{
-		for (U32 i=0; i<n; i++)
-		{
-			mCurrentp = mCurrentp->mNextp;
-			if (!mCurrentp)
-			{
-				break;
-			}		
-		}
-	}
-
-	if (mCurrentp)
-	{
-		// bump mQueuep down the list
-		mQueuep = mCurrentp->mNextp;
-		return mCurrentp->mDatap;
-	}
-	else
-	{
-		mQueuep = NULL;
-		return NULL;
-	}
-}
-
-
-// reset the list and return the last data in it, 
-// set mCurrentp to that node and bump mQueuep up the list
-template <class DATA_TYPE>
-DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getLastData()
-{
-	mQueuep = mTail.mPrevp;
-	mCurrentp = mQueuep;
-	if (mQueuep)
-	{
-		mQueuep = mQueuep->mPrevp;
-		return mCurrentp->mDatap;
-	}
-	else
-	{
-		return NULL;
-	}
-}
-
-
-// return the data in mQueuep, 
-// set mCurrentp to mQueuep and bump mQueuep down the list
-template <class DATA_TYPE>
-DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getNextData()
-{
-	if (mQueuep)
-	{
-		mCurrentp = mQueuep;
-		mQueuep = mQueuep->mNextp;
-		return mCurrentp->mDatap;
-	}
-	else
-	{
-		return NULL;
-	}
-}
-
-
-// return the data in mQueuep, 
-// set mCurrentp to mQueuep and bump mQueuep up the list
-template <class DATA_TYPE>
-DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getPreviousData()
-{
-	if (mQueuep)
-	{
-		mCurrentp = mQueuep;
-		mQueuep = mQueuep->mPrevp;
-		return mCurrentp->mDatap;
-	}
-	else
-	{
-		return NULL;
-	}
-}
-
-
-// remove the Node at mCurrentp
-// set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep)
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::removeCurrentData()
-{
-	if (mCurrentp)
-	{
-		// if there is a next one, fix it
-		if (mCurrentp->mNextp)
-		{
-			mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-		}
-		else	// otherwise we are at end of list
-		{
-			mTail.mPrevp = mCurrentp->mPrevp;
-		}
-
-		// if there is a previous one, fix it
-		if (mCurrentp->mPrevp)
-		{
-			mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-		}
-		else	// otherwise we are at beginning of list
-		{
-			mHead.mNextp = mCurrentp->mNextp;
-		}
-
-		// remove the node
-		mCurrentp->removeData();
-		delete mCurrentp;
-		mCount--;
-
-		// check for redundant pointing
-		if (mCurrentp == mQueuep)
-		{
-			mCurrentp = mQueuep = NULL;
-		}
-		else
-		{
-			mCurrentp = mQueuep;
-		}
-	}
-}
-
-
-// delete the Node at mCurrentp
-// set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) 
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::deleteCurrentData()
-{
-	if (mCurrentp)
-	{
-		// remove the node
-		// if there is a next one, fix it
-		if (mCurrentp->mNextp)
-		{
-			mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-		}
-		else	// otherwise we are at end of list
-		{
-			mTail.mPrevp = mCurrentp->mPrevp;
-		}
-
-		// if there is a previous one, fix it
-		if (mCurrentp->mPrevp)
-		{
-			mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-		}
-		else	// otherwise we are at beginning of list
-		{
-			mHead.mNextp = mCurrentp->mNextp;
-		}
-
-		// remove the LLDoubleLinkedNode
-		mCurrentp->deleteData();
-		delete mCurrentp;
-		mCount--;
-
-		// check for redundant pointing
-		if (mCurrentp == mQueuep)
-		{
-			mCurrentp = mQueuep = NULL;
-		}
-		else
-		{
-			mCurrentp = mQueuep;
-		}
-	}
-}
-
-
-// remove the Node at mCurrentp and insert it into newlist
-// set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep)
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::moveCurrentData(LLDoubleLinkedList<DATA_TYPE> *newlist)
-{
-	if (mCurrentp)
-	{
-		// remove the node
-		// if there is a next one, fix it
-		if (mCurrentp->mNextp)
-		{
-			mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-		}
-		else	// otherwise we are at end of list
-		{
-			mTail.mPrevp = mCurrentp->mPrevp;
-		}
-
-		// if there is a previous one, fix it
-		if (mCurrentp->mPrevp)
-		{
-			mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-		}
-		else	// otherwise we are at beginning of list
-		{
-			mHead.mNextp = mCurrentp->mNextp;
-		}
-
-		// move the node to the new list
-		newlist->addNode(mCurrentp);
-
-		// check for redundant pointing
-		if (mCurrentp == mQueuep)
-		{
-			mCurrentp = mQueuep = NULL;
-		}
-		else
-		{
-			mCurrentp = mQueuep;
-		}
-	}
-}
-
-
-// Inserts the node previous to mCurrentp
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::insertNode(LLDoubleLinkedNode<DATA_TYPE> *nodep)
-{
-	// don't allow pointer to NULL to be passed
-	if (!nodep)
-	{
-		llerror("NULL pointer passed to LLDoubleLinkedList::insertNode()", 0);
-	}
-	if (!nodep->mDatap)
-	{
-		llerror("NULL data pointer passed to LLDoubleLinkedList::insertNode()", 0);
-	}
-
-	if (mCurrentp)
-	{
-		if (mCurrentp->mPrevp)
-		{
-			nodep->mPrevp = mCurrentp->mPrevp;
-			nodep->mNextp = mCurrentp;
-			mCurrentp->mPrevp->mNextp = nodep;
-			mCurrentp->mPrevp = nodep;
-		}
-		else	// at beginning of list
-		{
-			nodep->mPrevp = NULL;
-			nodep->mNextp = mCurrentp;
-			mHead.mNextp = nodep;
-			mCurrentp->mPrevp = nodep;
-		}
-		mCurrentp = mQueuep;
-	}
-	else	// add to front of list
-	{
-		addNode(nodep);
-	}
-}
-
-
-// insert the data in front of mCurrentp
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::insertData(DATA_TYPE *data)
-{
-	if (!data)
-	{
-		llerror("NULL data pointer passed to LLDoubleLinkedList::insertNode()", 0);
-	}
-	LLDoubleLinkedNode<DATA_TYPE> *node = new LLDoubleLinkedNode<DATA_TYPE>(data);
-	insertNode(node);
-	mCount++;
-}
-
-
-// if mCurrentp has a previous node then :
-//   * swaps mCurrentp with its previous
-//   * set mCurrentp to mQueuep
-// otherwise does nothing
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::swapCurrentWithPrevious()
-{
-	if (mCurrentp)
-	{
-		if (mCurrentp->mPrevp)
-		{
-			// Pull mCurrentp out of list
-			mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-			if (mCurrentp->mNextp)
-			{
-				mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-			}
-			else 	// mCurrentp was at end of list
-			{
-				mTail.mPrevp = mCurrentp->mPrevp;
-			}
-
-			// Fix mCurrentp's pointers
-			mCurrentp->mNextp = mCurrentp->mPrevp;
-			mCurrentp->mPrevp = mCurrentp->mNextp->mPrevp;
-			mCurrentp->mNextp->mPrevp = mCurrentp;
-
-			if (mCurrentp->mPrevp)
-			{
-				// Fix the backward pointer of mCurrentp's new previous
-				mCurrentp->mPrevp->mNextp = mCurrentp;
-			}
-			else	// mCurrentp is now at beginning of list
-			{
-				mHead.mNextp = mCurrentp;
-			}
-
-			// Set the list back to the way it was
-			mCurrentp = mQueuep;
-		}
-	}
-}
-
-
-// if mCurrentp has a next node then :
-//   * swaps mCurrentp with its next
-//   * set mCurrentp to mQueuep
-// otherwise does nothing
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::swapCurrentWithNext()
-{
-	if (mCurrentp)
-	{
-		if (mCurrentp->mNextp)
-		{
-			// Pull mCurrentp out of list
-			mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-			if (mCurrentp->mPrevp)
-			{
-				mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-			}
-			else 	// mCurrentp was at beginning of list
-			{
-				mHead.mNextp = mCurrentp->mNextp;
-			}
-
-			// Fix mCurrentp's pointers
-			mCurrentp->mPrevp = mCurrentp->mNextp;
-			mCurrentp->mNextp = mCurrentp->mPrevp->mNextp;
-			mCurrentp->mPrevp->mNextp = mCurrentp;
-
-			if (mCurrentp->mNextp)
-			{
-				// Fix the back pointer of mCurrentp's new next
-				mCurrentp->mNextp->mPrevp = mCurrentp;
-			}
-			else 	// mCurrentp is now at end of list
-			{
-				mTail.mPrevp = mCurrentp;
-			}
-			
-			// Set the list back to the way it was
-			mCurrentp = mQueuep;
-		}
-	}
-}
-
-// move mCurrentp to the front of the list
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::moveCurrentToFront()
-{
-	if (mCurrentp)
-	{
-		// if there is a previous one, fix it
-		if (mCurrentp->mPrevp)
-		{
-			mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-		}
-		else	// otherwise we are at beginning of list
-		{
-			// check for redundant pointing
-			if (mCurrentp == mQueuep)
-			{
-				mCurrentp = mQueuep = NULL;
-			}
-			else
-			{
-				mCurrentp = mQueuep;
-			}
-			return;
-		}
-
-		// if there is a next one, fix it
-		if (mCurrentp->mNextp)
-		{
-			mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-		}
-		else	// otherwise we are at end of list
-		{
-			mTail.mPrevp = mCurrentp->mPrevp;
-		}
-
-		// add mCurrentp to beginning of list
-		mCurrentp->mNextp = mHead.mNextp;
-		mHead.mNextp->mPrevp = mCurrentp;	// mHead.mNextp MUST be valid, 
-											// or the list had only one node
-											// and we would have returned already
-		mCurrentp->mPrevp = NULL;
-		mHead.mNextp = mCurrentp;
-
-		// check for redundant pointing
-		if (mCurrentp == mQueuep)
-		{
-			mCurrentp = mQueuep = NULL;
-		}
-		else
-		{
-			mCurrentp = mQueuep;
-		}
-	}
-
-}
-
-// move mCurrentp to the end of the list
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::moveCurrentToEnd()
-{
-	if (mCurrentp)
-	{
-		// if there is a next one, fix it
-		if (mCurrentp->mNextp)
-		{
-			mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp;
-		}
-		else	// otherwise we are at end of list and we're done
-		{
-			// check for redundant pointing
-			if (mCurrentp == mQueuep)
-			{
-				mCurrentp = mQueuep = NULL;
-			}
-			else
-			{
-				mCurrentp = mQueuep;
-			}
-			return;
-		}
-
-		// if there is a previous one, fix it
-		if (mCurrentp->mPrevp)
-		{
-			mCurrentp->mPrevp->mNextp = mCurrentp->mNextp;
-		}
-		else	// otherwise we are at beginning of list
-		{
-			mHead.mNextp = mCurrentp->mNextp;
-		}
-
-		// add mCurrentp to end of list
-		mCurrentp->mPrevp = mTail.mPrevp;
-		mTail.mPrevp->mNextp = mCurrentp;	// mTail.mPrevp MUST be valid, 
-											// or the list had only one node
-											// and we would have returned already
-		mCurrentp->mNextp = NULL;
-		mTail.mPrevp = mCurrentp;
-
-		// check for redundant pointing
-		if (mCurrentp == mQueuep)
-		{
-			mCurrentp = mQueuep = NULL;
-		}
-		else
-		{
-			mCurrentp = mQueuep;
-		}
-	}
-}
-
-
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::setInsertBefore(BOOL (*insert_before)(DATA_TYPE *first, DATA_TYPE *second) )
-{
-	mInsertBefore = insert_before;
-}
-
-
-// add data in front of the first node for which mInsertBefore(datap, node->mDatap) returns TRUE
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::addDataSorted(DATA_TYPE *datap)
-{
-	// don't allow NULL to be passed to addData()
-	if (!datap)
-	{
-		llerror("NULL pointer passed to LLDoubleLinkedList::addDataSorted()", 0);
-	}
-
-	// has mInsertBefore not been set?
-	if (!mInsertBefore)
-	{
-		addData(datap);
-		return FALSE;
-	}
-
-	// is the list empty?
-	if (!mHead.mNextp)
-	{
-		addData(datap);
-		return TRUE;
-	}
-
-	// Note: this step has been added so that the behavior of LLDoubleLinkedList
-	// is as rigorous as the LLLinkedList class about adding duplicate nodes.
-	// Duplicate nodes can cause a problem when sorting if mInsertBefore(foo, foo) 
-	// returns TRUE.  However, if mInsertBefore(foo, foo) returns FALSE, then there 
-	// shouldn't be any reason to exclude duplicate nodes (as we do here).
-	if (checkData(datap))
-	{
-		return FALSE;
-	}
-	
-	mCurrentp = mHead.mNextp;
-	while (mCurrentp)
-	{
-		// check to see if datap is already in the list
-		if (datap == mCurrentp->mDatap)
-		{
-			return FALSE;
-		}
-		else if (mInsertBefore(datap, mCurrentp->mDatap))
-		{
-			insertData(datap);
-			return TRUE;
-		}
-		mCurrentp = mCurrentp->mNextp;
-	}
-	
-	addDataAtEnd(datap);
-	return TRUE;
-}
-
-
-// bubble-sort until sorted and return TRUE if anything was sorted
-// leaves mQueuep pointing at last node that was swapped with its mNextp
-//
-// NOTE: if you find this function looping for really long times, then you
-// probably need to check your implementation of mInsertBefore(a,b) and make 
-// sure it does not return TRUE when (a == b)!
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::bubbleSort()
-{
-	BOOL b_swapped = FALSE;
-	U32 count = 0;
-	while (lazyBubbleSort()) 
-	{
-		b_swapped = TRUE;
-		if (count++ > 0x7FFFFFFF)
-		{
-			llwarning("LLDoubleLinkedList::bubbleSort() : too many passes...", 1);
-			llwarning("    make sure the mInsertBefore(a, b) does not return TRUE for a == b", 1);
-			break;
-		}
-	}
-	return b_swapped;
-}
-
-
-// do a single bubble-sort pass and return TRUE if anything was sorted
-// leaves mQueuep pointing at last node that was swapped with its mNextp
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::lazyBubbleSort()
-{
-	// has mInsertBefore been set?
-	if (!mInsertBefore)
-	{
-		return FALSE;
-	}
-
-	// is list empty?
-	mCurrentp = mHead.mNextp;
-	if (!mCurrentp)
-	{
-		return FALSE;
-	}
-
-	BOOL b_swapped = FALSE;
-
-	// the sort will exit after 0x7FFFFFFF nodes or the end of the list, whichever is first
-	S32  length = 0x7FFFFFFF;
-	S32  count = 0;
-
-	while (mCurrentp  &&  mCurrentp->mNextp  &&  count<length)
-	{
-		if (mInsertBefore(mCurrentp->mNextp->mDatap, mCurrentp->mDatap))
-		{
-			b_swapped = TRUE;
-			mQueuep = mCurrentp;
-			swapCurrentWithNext();	// sets mCurrentp to mQueuep
-		}
-		count++;
-		mCurrentp = mCurrentp->mNextp;
-	}
-	
-	return b_swapped;
-}
-
-
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::pushState()
-{
-	if (mStateStackDepth < LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH)
-	{
-		*(mQueuepStack + mStateStackDepth) = mQueuep;
-		*(mCurrentpStack + mStateStackDepth) = mCurrentp;
-		mStateStackDepth++;
-		return TRUE;
-	}
-	return FALSE;
-}
-
-
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::popState()
-{
-	if (mStateStackDepth > 0)
-	{
-		mStateStackDepth--;
-		mQueuep = *(mQueuepStack + mStateStackDepth);
-		mCurrentp = *(mCurrentpStack + mStateStackDepth);
-		return TRUE;
-	}
-	return FALSE;
-}
-
-
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::clearStateStack()
-{
-	mStateStackDepth = 0;
-}
-
-//////////////////////////////////////////////////////////////////////////////////////////
-// private members
-//////////////////////////////////////////////////////////////////////////////////////////
-
-// add node to beginning of list
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::addNode(LLDoubleLinkedNode<DATA_TYPE> *nodep)
-{
-	// add the node to the front of the list
-	nodep->mPrevp = NULL;
-	nodep->mNextp = mHead.mNextp;
-	mHead.mNextp = nodep;
-
-	// if there's something in the list, fix its back pointer
-	if (nodep->mNextp)
-	{
-		nodep->mNextp->mPrevp = nodep;
-	}
-	else	// otherwise fix the tail node
-	{
-		mTail.mPrevp = nodep;
-	}
-
-	mCurrentp = mQueuep;
-}
-
-
-// add node to end of list
-// set mCurrentp to mQueuep
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::addNodeAtEnd(LLDoubleLinkedNode<DATA_TYPE> *node)
-{
-	// add the node to the end of the list
-	node->mNextp = NULL;
-	node->mPrevp = mTail.mPrevp;
-	mTail.mPrevp = node;
-
-	// if there's something in the list, fix its back pointer
-	if (node->mPrevp)
-	{
-		node->mPrevp->mNextp = node;
-	}
-	else	// otherwise fix the head node
-	{
-		mHead.mNextp = node;
-	}
-
-	mCurrentp = mQueuep;
-}
-
-
-// randomly move nodes in the list for DEBUG (or Discordian) purposes
-// sets mCurrentp and mQueuep to top of list
-template <class DATA_TYPE>
-void LLDoubleLinkedList<DATA_TYPE>::scramble()
-{
-	S32 random_number;
-	DATA_TYPE *datap = getFirstData();
-	while(datap)
-	{
-		random_number = ll_rand(5);
-
-		if (0 == random_number)
-		{
-			removeCurrentData();
-			addData(datap);
-		}
-		else if (1 == random_number)
-		{
-			removeCurrentData();
-			addDataAtEnd(datap);
-		}
-		else if (2 == random_number)
-		{
-			swapCurrentWithPrevious();
-		}
-		else if (3 == random_number)
-		{
-			swapCurrentWithNext();
-		}
-		datap = getNextData();
-	}
-	mQueuep = mHead.mNextp;
-	mCurrentp = mQueuep;
-}
-
-template <class DATA_TYPE>
-BOOL LLDoubleLinkedList<DATA_TYPE>::isEmpty()
-{
-	return (mCount == 0);
-}
-
-
-#endif