lllinkedqueue.h
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:7k
源码类别:

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file lllinkedqueue.h
  3.  * @brief Declaration of linked queue classes.
  4.  *
  5.  * $LicenseInfo:firstyear=2003&license=viewergpl$
  6.  * 
  7.  * Copyright (c) 2003-2010, Linden Research, Inc.
  8.  * 
  9.  * Second Life Viewer Source Code
  10.  * The source code in this file ("Source Code") is provided by Linden Lab
  11.  * to you under the terms of the GNU General Public License, version 2.0
  12.  * ("GPL"), unless you have obtained a separate licensing agreement
  13.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  14.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  15.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  16.  * 
  17.  * There are special exceptions to the terms and conditions of the GPL as
  18.  * it is applied to this Source Code. View the full text of the exception
  19.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  20.  * online at
  21.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  22.  * 
  23.  * By copying, modifying or distributing this software, you acknowledge
  24.  * that you have read and understood your obligations described above,
  25.  * and agree to abide by those obligations.
  26.  * 
  27.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  28.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  29.  * COMPLETENESS OR PERFORMANCE.
  30.  * $/LicenseInfo$
  31.  */
  32. #ifndef LL_LLLINKEDQUEUE_H
  33. #define LL_LLLINKEDQUEUE_H
  34. #include "llerror.h"
  35. // node that actually contains the data
  36. template <class DATA_TYPE> class LLLinkedQueueNode
  37. {
  38. public:
  39. DATA_TYPE mData;
  40. LLLinkedQueueNode *mNextp;
  41. LLLinkedQueueNode *mPrevp;
  42. public:
  43. LLLinkedQueueNode();
  44. LLLinkedQueueNode(const DATA_TYPE data);
  45. // destructor does not, by default, destroy associated data
  46. // however, the mDatap must be NULL to ensure that we aren't causing memory leaks
  47. ~LLLinkedQueueNode();
  48. };
  49. template <class DATA_TYPE> class LLLinkedQueue
  50. {
  51. public:
  52. LLLinkedQueue();
  53. // destructor destroys list and nodes, but not data in nodes
  54. ~LLLinkedQueue();
  55. // Puts at end of FIFO
  56. void push(const DATA_TYPE data);
  57. // Takes off front of FIFO
  58. BOOL pop(DATA_TYPE &data);
  59. BOOL peek(DATA_TYPE &data);
  60. void reset();
  61. S32 getLength() const;
  62. BOOL isEmpty() const;
  63. BOOL remove(const DATA_TYPE data);
  64. BOOL checkData(const DATA_TYPE data) const;
  65. private:
  66. // add node to end of list
  67. // set mCurrentp to mQueuep
  68. void addNodeAtEnd(LLLinkedQueueNode<DATA_TYPE> *nodep);
  69. private:
  70. LLLinkedQueueNode<DATA_TYPE> mHead; // head node
  71. LLLinkedQueueNode<DATA_TYPE> mTail; // tail node
  72. S32 mLength;
  73. };
  74. //
  75. // Nodes
  76. //
  77. template <class DATA_TYPE>
  78. LLLinkedQueueNode<DATA_TYPE>::LLLinkedQueueNode() : 
  79. mData(), mNextp(NULL), mPrevp(NULL)
  80. { }
  81. template <class DATA_TYPE>
  82. LLLinkedQueueNode<DATA_TYPE>::LLLinkedQueueNode(const DATA_TYPE data) : 
  83. mData(data), mNextp(NULL), mPrevp(NULL)
  84. { }
  85. template <class DATA_TYPE>
  86. LLLinkedQueueNode<DATA_TYPE>::~LLLinkedQueueNode()
  87. { }
  88. //
  89. // Queue itself
  90. //
  91. template <class DATA_TYPE>
  92. LLLinkedQueue<DATA_TYPE>::LLLinkedQueue()
  93. : mHead(), 
  94. mTail(), 
  95. mLength(0)
  96. { }
  97. // destructor destroys list and nodes, but not data in nodes
  98. template <class DATA_TYPE>
  99. LLLinkedQueue<DATA_TYPE>::~LLLinkedQueue()
  100. {
  101. reset();
  102. }
  103. // put data into a node and stick it at the end of the list
  104. template <class DATA_TYPE>
  105. void LLLinkedQueue<DATA_TYPE>::push(const DATA_TYPE data)
  106. {
  107. // make the new node
  108. LLLinkedQueueNode<DATA_TYPE> *nodep = new LLLinkedQueueNode<DATA_TYPE>(data);
  109. addNodeAtEnd(nodep);
  110. }
  111. // search the list starting at mHead.mNextp and remove the link with mDatap == data
  112. // set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data
  113. // return TRUE if found, FALSE if not found
  114. template <class DATA_TYPE>
  115. BOOL LLLinkedQueue<DATA_TYPE>::remove(const DATA_TYPE data)
  116. {
  117. BOOL b_found = FALSE;
  118. LLLinkedQueueNode<DATA_TYPE> *currentp = mHead.mNextp;
  119. while (currentp)
  120. {
  121. if (currentp->mData == data)
  122. {
  123. b_found = TRUE;
  124. // if there is a next one, fix it
  125. if (currentp->mNextp)
  126. {
  127. currentp->mNextp->mPrevp = currentp->mPrevp;
  128. }
  129. else // we are at end of list
  130. {
  131. mTail.mPrevp = currentp->mPrevp;
  132. }
  133. // if there is a previous one, fix it
  134. if (currentp->mPrevp)
  135. {
  136. currentp->mPrevp->mNextp = currentp->mNextp;
  137. }
  138. else // we are at beginning of list
  139. {
  140. mHead.mNextp = currentp->mNextp;
  141. }
  142. // remove the node
  143. delete currentp;
  144. mLength--;
  145. break;
  146. }
  147. currentp = currentp->mNextp; 
  148. }
  149. return b_found;
  150. }
  151. // remove all nodes from the list but do not delete associated data
  152. template <class DATA_TYPE>
  153. void LLLinkedQueue<DATA_TYPE>::reset()
  154. {
  155. LLLinkedQueueNode<DATA_TYPE> *currentp;
  156. LLLinkedQueueNode<DATA_TYPE> *nextp;
  157. currentp = mHead.mNextp;
  158. while (currentp)
  159. {
  160. nextp = currentp->mNextp;
  161. delete currentp;
  162. currentp = nextp;
  163. }
  164. // reset mHead and mCurrentp
  165. mHead.mNextp = NULL;
  166. mTail.mPrevp = NULL;
  167. mLength = 0;
  168. }
  169. template <class DATA_TYPE>
  170. S32 LLLinkedQueue<DATA_TYPE>::getLength() const
  171. {
  172. return mLength;
  173. }
  174. template <class DATA_TYPE>
  175. BOOL LLLinkedQueue<DATA_TYPE>::isEmpty() const
  176. {
  177. return mLength <= 0;
  178. }
  179. // check to see if data is in list
  180. // set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep
  181. // return TRUE if found, FALSE if not found
  182. template <class DATA_TYPE>
  183. BOOL LLLinkedQueue<DATA_TYPE>::checkData(const DATA_TYPE data) const
  184. {
  185. LLLinkedQueueNode<DATA_TYPE> *currentp = mHead.mNextp;
  186. while (currentp)
  187. {
  188. if (currentp->mData == data)
  189. {
  190. return TRUE;
  191. }
  192. currentp = currentp->mNextp;
  193. }
  194. return FALSE;
  195. }
  196. template <class DATA_TYPE>
  197. BOOL LLLinkedQueue<DATA_TYPE>::pop(DATA_TYPE &data)
  198. {
  199. LLLinkedQueueNode<DATA_TYPE> *currentp;
  200. currentp = mHead.mNextp;
  201. if (!currentp)
  202. {
  203. return FALSE;
  204. }
  205. mHead.mNextp = currentp->mNextp;
  206. if (currentp->mNextp)
  207. {
  208. currentp->mNextp->mPrevp = currentp->mPrevp;
  209. }
  210. else
  211. {
  212. mTail.mPrevp = currentp->mPrevp;
  213. }
  214. data = currentp->mData;
  215. delete currentp;
  216. mLength--;
  217. return TRUE;
  218. }
  219. template <class DATA_TYPE>
  220. BOOL LLLinkedQueue<DATA_TYPE>::peek(DATA_TYPE &data)
  221. {
  222. LLLinkedQueueNode<DATA_TYPE> *currentp;
  223. currentp = mHead.mNextp;
  224. if (!currentp)
  225. {
  226. return FALSE;
  227. }
  228. data = currentp->mData;
  229. return TRUE;
  230. }
  231. //////////////////////////////////////////////////////////////////////////////////////////
  232. // private members
  233. //////////////////////////////////////////////////////////////////////////////////////////
  234. // add node to end of list
  235. // set mCurrentp to mQueuep
  236. template <class DATA_TYPE>
  237. void LLLinkedQueue<DATA_TYPE>::addNodeAtEnd(LLLinkedQueueNode<DATA_TYPE> *nodep)
  238. {
  239. // add the node to the end of the list
  240. nodep->mNextp = NULL;
  241. nodep->mPrevp = mTail.mPrevp;
  242. mTail.mPrevp = nodep;
  243. // if there's something in the list, fix its back pointer
  244. if (nodep->mPrevp)
  245. {
  246. nodep->mPrevp->mNextp = nodep;
  247. }
  248. else // otherwise fix the head node
  249. {
  250. mHead.mNextp = nodep;
  251. }
  252. mLength++;
  253. }
  254. #endif