lllinkedqueue.h
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:7k
- /**
- * @file lllinkedqueue.h
- * @brief Declaration of linked queue classes.
- *
- * $LicenseInfo:firstyear=2003&license=viewergpl$
- *
- * Copyright (c) 2003-2010, Linden Research, Inc.
- *
- * Second Life Viewer Source Code
- * The source code in this file ("Source Code") is provided by Linden Lab
- * to you under the terms of the GNU General Public License, version 2.0
- * ("GPL"), unless you have obtained a separate licensing agreement
- * ("Other License"), formally executed by you and Linden Lab. Terms of
- * the GPL can be found in doc/GPL-license.txt in this distribution, or
- * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
- *
- * There are special exceptions to the terms and conditions of the GPL as
- * it is applied to this Source Code. View the full text of the exception
- * in the file doc/FLOSS-exception.txt in this software distribution, or
- * online at
- * http://secondlifegrid.net/programs/open_source/licensing/flossexception
- *
- * By copying, modifying or distributing this software, you acknowledge
- * that you have read and understood your obligations described above,
- * and agree to abide by those obligations.
- *
- * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
- * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
- * COMPLETENESS OR PERFORMANCE.
- * $/LicenseInfo$
- */
- #ifndef LL_LLLINKEDQUEUE_H
- #define LL_LLLINKEDQUEUE_H
- #include "llerror.h"
- // node that actually contains the data
- template <class DATA_TYPE> class LLLinkedQueueNode
- {
- public:
- DATA_TYPE mData;
- LLLinkedQueueNode *mNextp;
- LLLinkedQueueNode *mPrevp;
- public:
- LLLinkedQueueNode();
- LLLinkedQueueNode(const 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
- ~LLLinkedQueueNode();
- };
- template <class DATA_TYPE> class LLLinkedQueue
- {
- public:
- LLLinkedQueue();
- // destructor destroys list and nodes, but not data in nodes
- ~LLLinkedQueue();
- // Puts at end of FIFO
- void push(const DATA_TYPE data);
- // Takes off front of FIFO
- BOOL pop(DATA_TYPE &data);
- BOOL peek(DATA_TYPE &data);
- void reset();
- S32 getLength() const;
- BOOL isEmpty() const;
- BOOL remove(const DATA_TYPE data);
- BOOL checkData(const DATA_TYPE data) const;
- private:
- // add node to end of list
- // set mCurrentp to mQueuep
- void addNodeAtEnd(LLLinkedQueueNode<DATA_TYPE> *nodep);
- private:
- LLLinkedQueueNode<DATA_TYPE> mHead; // head node
- LLLinkedQueueNode<DATA_TYPE> mTail; // tail node
- S32 mLength;
- };
- //
- // Nodes
- //
- template <class DATA_TYPE>
- LLLinkedQueueNode<DATA_TYPE>::LLLinkedQueueNode() :
- mData(), mNextp(NULL), mPrevp(NULL)
- { }
- template <class DATA_TYPE>
- LLLinkedQueueNode<DATA_TYPE>::LLLinkedQueueNode(const DATA_TYPE data) :
- mData(data), mNextp(NULL), mPrevp(NULL)
- { }
- template <class DATA_TYPE>
- LLLinkedQueueNode<DATA_TYPE>::~LLLinkedQueueNode()
- { }
- //
- // Queue itself
- //
- template <class DATA_TYPE>
- LLLinkedQueue<DATA_TYPE>::LLLinkedQueue()
- : mHead(),
- mTail(),
- mLength(0)
- { }
- // destructor destroys list and nodes, but not data in nodes
- template <class DATA_TYPE>
- LLLinkedQueue<DATA_TYPE>::~LLLinkedQueue()
- {
- reset();
- }
- // put data into a node and stick it at the end of the list
- template <class DATA_TYPE>
- void LLLinkedQueue<DATA_TYPE>::push(const DATA_TYPE data)
- {
- // make the new node
- LLLinkedQueueNode<DATA_TYPE> *nodep = new LLLinkedQueueNode<DATA_TYPE>(data);
- addNodeAtEnd(nodep);
- }
- // 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 LLLinkedQueue<DATA_TYPE>::remove(const DATA_TYPE data)
- {
- BOOL b_found = FALSE;
- LLLinkedQueueNode<DATA_TYPE> *currentp = mHead.mNextp;
- while (currentp)
- {
- if (currentp->mData == data)
- {
- b_found = TRUE;
- // if there is a next one, fix it
- if (currentp->mNextp)
- {
- currentp->mNextp->mPrevp = currentp->mPrevp;
- }
- else // we are at end of list
- {
- mTail.mPrevp = currentp->mPrevp;
- }
- // if there is a previous one, fix it
- if (currentp->mPrevp)
- {
- currentp->mPrevp->mNextp = currentp->mNextp;
- }
- else // we are at beginning of list
- {
- mHead.mNextp = currentp->mNextp;
- }
- // remove the node
- delete currentp;
- mLength--;
- break;
- }
- currentp = currentp->mNextp;
- }
- return b_found;
- }
- // remove all nodes from the list but do not delete associated data
- template <class DATA_TYPE>
- void LLLinkedQueue<DATA_TYPE>::reset()
- {
- LLLinkedQueueNode<DATA_TYPE> *currentp;
- LLLinkedQueueNode<DATA_TYPE> *nextp;
- currentp = mHead.mNextp;
- while (currentp)
- {
- nextp = currentp->mNextp;
- delete currentp;
- currentp = nextp;
- }
- // reset mHead and mCurrentp
- mHead.mNextp = NULL;
- mTail.mPrevp = NULL;
- mLength = 0;
- }
- template <class DATA_TYPE>
- S32 LLLinkedQueue<DATA_TYPE>::getLength() const
- {
- return mLength;
- }
- template <class DATA_TYPE>
- BOOL LLLinkedQueue<DATA_TYPE>::isEmpty() const
- {
- return mLength <= 0;
- }
- // 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 LLLinkedQueue<DATA_TYPE>::checkData(const DATA_TYPE data) const
- {
- LLLinkedQueueNode<DATA_TYPE> *currentp = mHead.mNextp;
- while (currentp)
- {
- if (currentp->mData == data)
- {
- return TRUE;
- }
- currentp = currentp->mNextp;
- }
- return FALSE;
- }
- template <class DATA_TYPE>
- BOOL LLLinkedQueue<DATA_TYPE>::pop(DATA_TYPE &data)
- {
- LLLinkedQueueNode<DATA_TYPE> *currentp;
- currentp = mHead.mNextp;
- if (!currentp)
- {
- return FALSE;
- }
- mHead.mNextp = currentp->mNextp;
- if (currentp->mNextp)
- {
- currentp->mNextp->mPrevp = currentp->mPrevp;
- }
- else
- {
- mTail.mPrevp = currentp->mPrevp;
- }
- data = currentp->mData;
- delete currentp;
- mLength--;
- return TRUE;
- }
- template <class DATA_TYPE>
- BOOL LLLinkedQueue<DATA_TYPE>::peek(DATA_TYPE &data)
- {
- LLLinkedQueueNode<DATA_TYPE> *currentp;
- currentp = mHead.mNextp;
- if (!currentp)
- {
- return FALSE;
- }
- data = currentp->mData;
- return TRUE;
- }
- //////////////////////////////////////////////////////////////////////////////////////////
- // private members
- //////////////////////////////////////////////////////////////////////////////////////////
- // add node to end of list
- // set mCurrentp to mQueuep
- template <class DATA_TYPE>
- void LLLinkedQueue<DATA_TYPE>::addNodeAtEnd(LLLinkedQueueNode<DATA_TYPE> *nodep)
- {
- // add the node to the end of the list
- nodep->mNextp = NULL;
- nodep->mPrevp = mTail.mPrevp;
- mTail.mPrevp = nodep;
- // if there's something in the list, fix its back pointer
- if (nodep->mPrevp)
- {
- nodep->mPrevp->mNextp = nodep;
- }
- else // otherwise fix the head node
- {
- mHead.mNextp = nodep;
- }
- mLength++;
- }
- #endif