Queue.h 5.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. /*
  2. ===========================================================================
  3. Doom 3 BFG Edition GPL Source Code
  4. Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company.
  5. This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").
  6. Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation, either version 3 of the License, or
  9. (at your option) any later version.
  10. Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. GNU General Public License for more details.
  14. You should have received a copy of the GNU General Public License
  15. along with Doom 3 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>.
  16. In addition, the Doom 3 BFG Edition Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 BFG Edition Source Code. If not, please request a copy in writing from id Software at the address below.
  17. If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  18. ===========================================================================
  19. */
  20. #ifndef __QUEUE_H__
  21. #define __QUEUE_H__
  22. /*
  23. ===============================================================================
  24. Queue template
  25. ===============================================================================
  26. */
  27. template< class type, int nextOffset >
  28. class idQueueTemplate {
  29. public:
  30. idQueueTemplate();
  31. void Add( type *element );
  32. type * Get();
  33. private:
  34. type * first;
  35. type * last;
  36. };
  37. #define QUEUE_NEXT_PTR( element ) (*((type**)(((byte*)element)+nextOffset)))
  38. template< class type, int nextOffset >
  39. idQueueTemplate<type,nextOffset>::idQueueTemplate() {
  40. first = last = NULL;
  41. }
  42. template< class type, int nextOffset >
  43. void idQueueTemplate<type,nextOffset>::Add( type *element ) {
  44. QUEUE_NEXT_PTR(element) = NULL;
  45. if ( last ) {
  46. QUEUE_NEXT_PTR(last) = element;
  47. } else {
  48. first = element;
  49. }
  50. last = element;
  51. }
  52. template< class type, int nextOffset >
  53. type *idQueueTemplate<type,nextOffset>::Get() {
  54. type *element;
  55. element = first;
  56. if ( element ) {
  57. first = QUEUE_NEXT_PTR(first);
  58. if ( last == element ) {
  59. last = NULL;
  60. }
  61. QUEUE_NEXT_PTR(element) = NULL;
  62. }
  63. return element;
  64. }
  65. /*
  66. ================================================
  67. A node of a Queue
  68. ================================================
  69. */
  70. template< typename type >
  71. class idQueueNode {
  72. public:
  73. idQueueNode() { next = NULL; }
  74. type * GetNext() const { return next; }
  75. void SetNext( type *next ) { this->next = next; }
  76. private:
  77. type * next;
  78. };
  79. /*
  80. ================================================
  81. A Queue, idQueue, is a template Container class implementing the Queue abstract data
  82. type.
  83. ================================================
  84. */
  85. template< typename type, idQueueNode<type> type::*nodePtr >
  86. class idQueue {
  87. public:
  88. idQueue();
  89. void Add( type *element );
  90. type * RemoveFirst();
  91. type * Peek() const;
  92. bool IsEmpty();
  93. static void Test();
  94. private:
  95. type * first;
  96. type * last;
  97. };
  98. /*
  99. ========================
  100. idQueue<type,nodePtr>::idQueue
  101. ========================
  102. */
  103. template< typename type, idQueueNode<type> type::*nodePtr >
  104. idQueue<type,nodePtr>::idQueue() {
  105. first = last = NULL;
  106. }
  107. /*
  108. ========================
  109. idQueue<type,nodePtr>::Add
  110. ========================
  111. */
  112. template< typename type, idQueueNode<type> type::*nodePtr >
  113. void idQueue<type,nodePtr>::Add( type *element ) {
  114. (element->*nodePtr).SetNext( NULL );
  115. if ( last ) {
  116. (last->*nodePtr).SetNext( element );
  117. } else {
  118. first = element;
  119. }
  120. last = element;
  121. }
  122. /*
  123. ========================
  124. idQueue<type,nodePtr>::RemoveFirst
  125. ========================
  126. */
  127. template< typename type, idQueueNode<type> type::*nodePtr >
  128. type *idQueue<type,nodePtr>::RemoveFirst() {
  129. type *element;
  130. element = first;
  131. if ( element ) {
  132. first = (first->*nodePtr).GetNext();
  133. if ( last == element ) {
  134. last = NULL;
  135. }
  136. (element->*nodePtr).SetNext( NULL );
  137. }
  138. return element;
  139. }
  140. /*
  141. ========================
  142. idQueue<type,nodePtr>::Peek
  143. ========================
  144. */
  145. template< typename type, idQueueNode<type> type::*nodePtr >
  146. type *idQueue<type,nodePtr>::Peek() const {
  147. return first;
  148. }
  149. /*
  150. ========================
  151. idQueue<type,nodePtr>::IsEmpty
  152. ========================
  153. */
  154. template< typename type, idQueueNode<type> type::*nodePtr >
  155. bool idQueue<type,nodePtr>::IsEmpty() {
  156. return ( first == NULL );
  157. }
  158. /*
  159. ========================
  160. idQueue<type,nodePtr>::Test
  161. ========================
  162. */
  163. template< typename type, idQueueNode<type> type::*nodePtr >
  164. void idQueue<type,nodePtr>::Test() {
  165. class idMyType {
  166. public:
  167. idQueueNode<idMyType> queueNode;
  168. };
  169. idQueue<idMyType,&idMyType::queueNode> myQueue;
  170. idMyType *element = new (TAG_IDLIB) idMyType;
  171. myQueue.Add( element );
  172. element = myQueue.RemoveFirst();
  173. delete element;
  174. }
  175. #endif // !__QUEUE_H__