sourcehook/sh_list.h
author David Anderson <dvander@alliedmods.net>
Thu Sep 27 19:28:05 2007 +0000 (2007-09-27)
branchsourcemm-1.6.0
changeset 356 bbcf8dcb2aa7
parent 347 e82968c21606
permissions -rw-r--r--
removed unnecessary api call
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2007 Metamod:Source Development Team
     3 * No warranties of any kind
     4 *
     5 * License: zlib/libpng
     6 *
     7 * Author(s): David "BAILOPAN" Anderson
     8 * ============================
     9 */
    10 
    11 #ifndef _INCLUDE_SMM_LIST_H
    12 #define _INCLUDE_SMM_LIST_H
    13 
    14 #include <new>
    15 #include <malloc.h>
    16 
    17 namespace SourceHook
    18 {
    19 
    20 	//This class is from CSDM for AMX Mod X
    21 	/*
    22 		A circular, doubly-linked list with one sentinel node
    23 
    24 		Empty:
    25 			m_Head = sentinel
    26 			m_Head->next = m_Head;
    27 			m_Head->prev = m_Head;
    28 		One element:
    29 			m_Head = sentinel
    30 			m_Head->next = node1
    31 			m_Head->prev = node1
    32 			node1->next = m_Head
    33 			node1->prev = m_Head
    34 		Two elements:
    35 			m_Head = sentinel
    36 			m_Head->next = node1
    37 			m_Head->prev = node2
    38 			node1->next = node2
    39 			node1->prev = m_Head
    40 			node2->next = m_Head
    41 			node2->prev = node1
    42 	*/
    43 	template <class T>
    44 	class List
    45 	{
    46 	public:
    47 		class iterator;
    48 		friend class iterator;
    49 		class ListNode
    50 		{
    51 		public:
    52 			ListNode(const T & o) : obj(o) { };
    53 			ListNode() { };
    54 			T obj;
    55 			ListNode *next;
    56 			ListNode *prev;
    57 		};
    58 	private:
    59 		// Initializes the sentinel node.
    60 		// BAIL used malloc instead of new in order to bypass the need for a constructor.
    61 		ListNode *_Initialize()
    62 		{
    63 			ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    64 			n->next = n;
    65 			n->prev = n;
    66 			return n;
    67 		}
    68 	public:
    69 		List() : m_Head(_Initialize()), m_Size(0)
    70 		{
    71 		}
    72 		List(const List &src) : m_Head(_Initialize()), m_Size(0)
    73 		{
    74 			iterator iter;
    75 			for (iter=src.begin(); iter!=src.end(); iter++)
    76 				push_back( (*iter) );
    77 		}
    78 		~List()
    79 		{
    80 			clear();
    81 
    82 			// Don't forget to free the sentinel
    83 			if (m_Head)
    84 			{
    85 				free(m_Head);
    86 				m_Head = NULL;
    87 			}
    88 		}
    89 		void push_back(const T &obj)
    90 		{
    91 			ListNode *node = new ListNode(obj);
    92 
    93 			node->prev = m_Head->prev;
    94 			node->next = m_Head;
    95 			m_Head->prev->next = node;
    96 			m_Head->prev = node;
    97 
    98 			m_Size++;
    99 		}
   100 		size_t size() const
   101 		{
   102 			return m_Size;
   103 		}
   104 
   105 		void clear()
   106 		{
   107 			ListNode *node = m_Head->next;
   108 			ListNode *temp;
   109 			m_Head->next = m_Head;
   110 			m_Head->prev = m_Head;
   111 
   112 			// Iterate through the nodes until we find g_Head (the sentinel) again
   113 			while (node != m_Head)
   114 			{
   115 				temp = node->next;
   116 				delete node;
   117 				node = temp;
   118 			}
   119 			m_Size = 0;
   120 		}
   121 		bool empty() const
   122 		{
   123 			return (m_Size == 0);
   124 		}
   125 		T & back()
   126 		{
   127 			return m_Head->prev->obj;
   128 		}
   129 	private:
   130 		ListNode *m_Head;
   131 		size_t m_Size;
   132 	public:
   133 		class iterator
   134 		{
   135 		friend class List;
   136 		public:
   137 			iterator()
   138 			{
   139 				m_This = NULL;
   140 			}
   141 			iterator(const List &src)
   142 			{
   143 				m_This = src.m_Head;
   144 			}
   145 			iterator(ListNode *n) : m_This(n)
   146 			{
   147 			}
   148 			iterator(const iterator &where)
   149 			{
   150 				m_This = where.m_This;
   151 			}
   152 			//pre decrement
   153 			iterator & operator--()
   154 			{
   155 				if (m_This)
   156 					m_This = m_This->prev;
   157 				return *this;
   158 			}
   159 			//post decrement
   160 			iterator operator--(int)
   161 			{
   162 				iterator old(*this);
   163 				if (m_This)
   164 					m_This = m_This->prev;
   165 				return old;
   166 			}	
   167 			
   168 			//pre increment
   169 			iterator & operator++()
   170 			{
   171 				if (m_This)
   172 					m_This = m_This->next;
   173 				return *this;
   174 			}
   175 			//post increment
   176 			iterator operator++(int)
   177 			{
   178 				iterator old(*this);
   179 				if (m_This)
   180 					m_This = m_This->next;
   181 				return old;
   182 			}
   183 			
   184 			const T & operator * () const
   185 			{
   186 				return m_This->obj;
   187 			}
   188 			T & operator * ()
   189 			{
   190 				return m_This->obj;
   191 			}
   192 			
   193 			T * operator -> ()
   194 			{
   195 				return &(m_This->obj);
   196 			}
   197 			const T * operator -> () const
   198 			{
   199 				return &(m_This->obj);
   200 			}
   201 			
   202 			bool operator != (const iterator &where) const
   203 			{
   204 				return (m_This != where.m_This);
   205 			}
   206 			bool operator ==(const iterator &where) const
   207 			{
   208 				return (m_This == where.m_This);
   209 			}
   210 		private:
   211 			ListNode *m_This;
   212 		};
   213 	public:
   214 		iterator begin() const
   215 		{
   216 			return iterator(m_Head->next);
   217 		}
   218 		iterator end() const
   219 		{
   220 			return iterator(m_Head);
   221 		}
   222 		iterator erase(iterator &where)
   223 		{
   224 			ListNode *pNode = where.m_This;
   225 			iterator iter(where);
   226 			iter++;
   227 
   228 
   229 			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
   230 			pNode->prev->next = pNode->next;
   231 			pNode->next->prev = pNode->prev;
   232 
   233 			delete pNode;
   234 			m_Size--;
   235 
   236 			return iter;
   237 		}
   238 
   239 		iterator insert(iterator where, const T &obj)
   240 		{
   241 			// Insert obj right before where
   242 
   243 			ListNode *node = new ListNode(obj);
   244 			ListNode *pWhereNode = where.m_This;
   245 			
   246 			pWhereNode->prev->next = node;
   247 			node->prev = pWhereNode->prev;
   248 			pWhereNode->prev = node;
   249 			node->next = pWhereNode;
   250 
   251 			m_Size++;
   252 
   253 			return iterator(node);
   254 		}
   255 
   256 	public:
   257 		void remove(const T & obj)
   258 		{
   259 			iterator b;
   260 			for (b=begin(); b!=end(); b++)
   261 			{
   262 				if ( (*b) == obj )
   263 				{
   264 					erase( b );
   265 					break;
   266 				}
   267 			}
   268 		}
   269 		template <typename U>
   270 		iterator find(const U & equ) const
   271 		{
   272 			iterator iter;
   273 			for (iter=begin(); iter!=end(); iter++)
   274 			{
   275 				if ( (*iter) == equ )
   276 					return iter;
   277 			}
   278 			return end();
   279 		}
   280 		List & operator =(const List &src)
   281 		{
   282 			clear();
   283 			iterator iter;
   284 			for (iter=src.begin(); iter!=src.end(); iter++)
   285 				push_back( (*iter) );
   286 			return *this;
   287 		}
   288 	};
   289 };	//NAMESPACE
   290 
   291 #endif //_INCLUDE_CSDM_LIST_H