1.1 --- a/core/sm_queue.h Fri Mar 28 06:21:34 2008 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,333 +0,0 @@
1.4 -/**
1.5 - * vim: set ts=4 :
1.6 - * =============================================================================
1.7 - * SourceMod
1.8 - * Copyright (C) 2004-2007 AlliedModders LLC. All rights reserved.
1.9 - * =============================================================================
1.10 - *
1.11 - * This program is free software; you can redistribute it and/or modify it under
1.12 - * the terms of the GNU General Public License, version 3.0, as published by the
1.13 - * Free Software Foundation.
1.14 - *
1.15 - * This program is distributed in the hope that it will be useful, but WITHOUT
1.16 - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 - * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.18 - * details.
1.19 - *
1.20 - * You should have received a copy of the GNU General Public License along with
1.21 - * this program. If not, see <http://www.gnu.org/licenses/>.
1.22 - *
1.23 - * As a special exception, AlliedModders LLC gives you permission to link the
1.24 - * code of this program (as well as its derivative works) to "Half-Life 2," the
1.25 - * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
1.26 - * by the Valve Corporation. You must obey the GNU General Public License in
1.27 - * all respects for all other code used. Additionally, AlliedModders LLC grants
1.28 - * this exception to all derivative works. AlliedModders LLC defines further
1.29 - * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
1.30 - * or <http://www.sourcemod.net/license.php>.
1.31 - *
1.32 - * Version: $Id$
1.33 - */
1.34 -
1.35 -#ifndef _INCLUDE_SM_QUEUE_H
1.36 -#define _INCLUDE_SM_QUEUE_H
1.37 -
1.38 -#include <new>
1.39 -#include <malloc.h>
1.40 -#include <sh_stack.h>
1.41 -
1.42 -using namespace SourceHook;
1.43 -
1.44 -/*
1.45 - A circular, doubly-linked List with one sentinel node
1.46 -
1.47 - Empty:
1.48 - m_Head = sentinel
1.49 - m_Head->next = m_Head;
1.50 - m_Head->prev = m_Head;
1.51 - One element:
1.52 - m_Head = sentinel
1.53 - m_Head->next = node1
1.54 - m_Head->prev = node1
1.55 - node1->next = m_Head
1.56 - node1->prev = m_Head
1.57 - Two elements:
1.58 - m_Head = sentinel
1.59 - m_Head->next = node1
1.60 - m_Head->prev = node2
1.61 - node1->next = node2
1.62 - node1->prev = m_Head
1.63 - node2->next = m_Head
1.64 - node2->prev = node1
1.65 -*/
1.66 -template <class T>
1.67 -class Queue
1.68 -{
1.69 -public:
1.70 - class iterator;
1.71 - friend class iterator;
1.72 - class QueueNode
1.73 - {
1.74 - public:
1.75 - T obj;
1.76 - QueueNode *next;
1.77 - QueueNode *prev;
1.78 - };
1.79 -private:
1.80 - // Initializes the sentinel node.
1.81 - QueueNode *_Initialize()
1.82 - {
1.83 - QueueNode *n = (QueueNode *)malloc(sizeof(QueueNode));
1.84 - n->next = n;
1.85 - n->prev = n;
1.86 - return n;
1.87 - }
1.88 -public:
1.89 - Queue() : m_Head(_Initialize()), m_Size(0)
1.90 - {
1.91 - }
1.92 -
1.93 - Queue(const Queue &src) : m_Head(_Initialize()), m_Size(0)
1.94 - {
1.95 - iterator iter;
1.96 - for (iter=src.begin(); iter!=src.end(); iter++)
1.97 - {
1.98 - push_back( (*iter) );
1.99 - }
1.100 - }
1.101 -
1.102 - ~Queue()
1.103 - {
1.104 - clear();
1.105 -
1.106 - // Don't forget to free the sentinel
1.107 - if (m_Head)
1.108 - {
1.109 - free(m_Head);
1.110 - m_Head = NULL;
1.111 - }
1.112 -
1.113 - while (!m_FreeNodes.empty())
1.114 - {
1.115 - free(m_FreeNodes.front());
1.116 - m_FreeNodes.pop();
1.117 - }
1.118 - }
1.119 -
1.120 - void push(const T &obj)
1.121 - {
1.122 - QueueNode *node;
1.123 -
1.124 - if (m_FreeNodes.empty())
1.125 - {
1.126 - node = (QueueNode *)malloc(sizeof(QueueNode));
1.127 - } else {
1.128 - node = m_FreeNodes.front();
1.129 - m_FreeNodes.pop();
1.130 - }
1.131 -
1.132 - /* Copy the object */
1.133 - new (&node->obj) T(obj);
1.134 -
1.135 - /* Install into the Queue */
1.136 - node->prev = m_Head->prev;
1.137 - node->next = m_Head;
1.138 - m_Head->prev->next = node;
1.139 - m_Head->prev = node;
1.140 -
1.141 - m_Size++;
1.142 - }
1.143 -
1.144 - size_t size() const
1.145 - {
1.146 - return m_Size;
1.147 - }
1.148 -
1.149 - void clear()
1.150 - {
1.151 - QueueNode *node = m_Head->next;
1.152 - QueueNode *temp;
1.153 - m_Head->next = m_Head;
1.154 - m_Head->prev = m_Head;
1.155 -
1.156 - // Iterate through the nodes until we find g_Head (the sentinel) again
1.157 - while (node != m_Head)
1.158 - {
1.159 - temp = node->next;
1.160 - node->obj.~T();
1.161 - m_FreeNodes.push(node);
1.162 - node = temp;
1.163 - }
1.164 - m_Size = 0;
1.165 - }
1.166 -
1.167 - bool empty() const
1.168 - {
1.169 - return (m_Size == 0);
1.170 - }
1.171 -
1.172 -private:
1.173 - QueueNode *m_Head;
1.174 - size_t m_Size;
1.175 - CStack<QueueNode *> m_FreeNodes;
1.176 -public:
1.177 - class iterator
1.178 - {
1.179 - friend class Queue;
1.180 - public:
1.181 - iterator()
1.182 - {
1.183 - m_This = NULL;
1.184 - }
1.185 - iterator(const Queue &src)
1.186 - {
1.187 - m_This = src.m_Head;
1.188 - }
1.189 - iterator(QueueNode *n) : m_This(n)
1.190 - {
1.191 - }
1.192 - iterator(const iterator &where)
1.193 - {
1.194 - m_This = where.m_This;
1.195 - }
1.196 - //pre decrement
1.197 - iterator & operator--()
1.198 - {
1.199 - if (m_This)
1.200 - m_This = m_This->prev;
1.201 - return *this;
1.202 - }
1.203 - //post decrement
1.204 - iterator operator--(int)
1.205 - {
1.206 - iterator old(*this);
1.207 - if (m_This)
1.208 - m_This = m_This->prev;
1.209 - return old;
1.210 - }
1.211 -
1.212 - //pre increment
1.213 - iterator & operator++()
1.214 - {
1.215 - if (m_This)
1.216 - m_This = m_This->next;
1.217 - return *this;
1.218 - }
1.219 - //post increment
1.220 - iterator operator++(int)
1.221 - {
1.222 - iterator old(*this);
1.223 - if (m_This)
1.224 - m_This = m_This->next;
1.225 - return old;
1.226 - }
1.227 -
1.228 - const T & operator * () const
1.229 - {
1.230 - return m_This->obj;
1.231 - }
1.232 - T & operator * ()
1.233 - {
1.234 - return m_This->obj;
1.235 - }
1.236 -
1.237 - T * operator -> ()
1.238 - {
1.239 - return &(m_This->obj);
1.240 - }
1.241 - const T * operator -> () const
1.242 - {
1.243 - return &(m_This->obj);
1.244 - }
1.245 -
1.246 - bool operator != (const iterator &where) const
1.247 - {
1.248 - return (m_This != where.m_This);
1.249 - }
1.250 - bool operator ==(const iterator &where) const
1.251 - {
1.252 - return (m_This == where.m_This);
1.253 - }
1.254 - private:
1.255 - QueueNode *m_This;
1.256 - };
1.257 -public:
1.258 - iterator begin() const
1.259 - {
1.260 - return iterator(m_Head->next);
1.261 - }
1.262 -
1.263 - iterator end() const
1.264 - {
1.265 - return iterator(m_Head);
1.266 - }
1.267 -
1.268 - iterator erase(iterator &where)
1.269 - {
1.270 - QueueNode *pNode = where.m_This;
1.271 - iterator iter(where);
1.272 - iter++;
1.273 -
1.274 -
1.275 - // Works for all cases: empty Queue, erasing first element, erasing tail, erasing in the middle...
1.276 - pNode->prev->next = pNode->next;
1.277 - pNode->next->prev = pNode->prev;
1.278 -
1.279 - pNode->obj.~T();
1.280 - m_FreeNodes.push(pNode);
1.281 - m_Size--;
1.282 -
1.283 - return iter;
1.284 - }
1.285 -public:
1.286 - void remove(const T & obj)
1.287 - {
1.288 - iterator b;
1.289 - for (b=begin(); b!=end(); b++)
1.290 - {
1.291 - if ( (*b) == obj )
1.292 - {
1.293 - erase( b );
1.294 - break;
1.295 - }
1.296 - }
1.297 - }
1.298 - template <typename U>
1.299 - iterator find(const U & equ) const
1.300 - {
1.301 - iterator iter;
1.302 - for (iter=begin(); iter!=end(); iter++)
1.303 - {
1.304 - if ( (*iter) == equ )
1.305 - {
1.306 - return iter;
1.307 - }
1.308 - }
1.309 - return end();
1.310 - }
1.311 - Queue & operator =(const Queue &src)
1.312 - {
1.313 - clear();
1.314 - iterator iter;
1.315 - for (iter=src.begin(); iter!=src.end(); iter++)
1.316 - {
1.317 - push_back( (*iter) );
1.318 - }
1.319 - return *this;
1.320 - }
1.321 -public:
1.322 - T & first() const
1.323 - {
1.324 - iterator i = begin();
1.325 -
1.326 - return (*i);
1.327 - }
1.328 -
1.329 - void pop()
1.330 - {
1.331 - iterator iter = begin();
1.332 - erase(iter);
1.333 - }
1.334 -};
1.335 -
1.336 -#endif //_INCLUDE_SM_QUEUE_H
