core/sourcehook/sh_list.h
author Scott Ehlert <ds@alliedmods.net>
Thu Dec 10 00:59:50 2009 -0600 (2009-12-10)
changeset 689 4065ba5e9155
parent 684 8015336442cb
child 733 2365240861a2
permissions -rw-r--r--
Rewrote user message caching code to always use IServerGameDLL::GetUserMessageInfo (bug 4117, r=dvander).

Games where the above function can crash are handled by detouring tier0's Error() function and jumping back to our own code. So in theory this should work on all games now.
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2008 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 <stdlib.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 
   101 		void push_front(const T &obj)
   102 		{
   103 			insert(begin(), obj);
   104 		}
   105 
   106 		void push_sorted(const T &obj)
   107 		{
   108 			iterator iter;
   109 			for (iter = begin(); iter != end(); ++iter)
   110 			{
   111 				if (obj < *iter)
   112 				{
   113 					insert(iter, obj);
   114 					return;
   115 				}
   116 			}
   117 			push_back(obj);
   118 		}
   119 
   120 		size_t size() const
   121 		{
   122 			return m_Size;
   123 		}
   124 
   125 		void clear()
   126 		{
   127 			ListNode *node = m_Head->next;
   128 			ListNode *temp;
   129 			m_Head->next = m_Head;
   130 			m_Head->prev = m_Head;
   131 
   132 			// Iterate through the nodes until we find g_Head (the sentinel) again
   133 			while (node != m_Head)
   134 			{
   135 				temp = node->next;
   136 				delete node;
   137 				node = temp;
   138 			}
   139 			m_Size = 0;
   140 		}
   141 		bool empty() const
   142 		{
   143 			return (m_Size == 0);
   144 		}
   145 		T & front()
   146 		{
   147 			return m_Head->next->obj;
   148 		}
   149 		T & back()
   150 		{
   151 			return m_Head->prev->obj;
   152 		}
   153 	private:
   154 		ListNode *m_Head;
   155 		size_t m_Size;
   156 	public:
   157 		class iterator
   158 		{
   159 		friend class List;
   160 		public:
   161 			iterator()
   162 			{
   163 				m_This = NULL;
   164 			}
   165 			iterator(const List &src)
   166 			{
   167 				m_This = src.m_Head;
   168 			}
   169 			iterator(ListNode *n) : m_This(n)
   170 			{
   171 			}
   172 			iterator(const iterator &where)
   173 			{
   174 				m_This = where.m_This;
   175 			}
   176 			//pre decrement
   177 			iterator & operator--()
   178 			{
   179 				if (m_This)
   180 					m_This = m_This->prev;
   181 				return *this;
   182 			}
   183 			//post decrement
   184 			iterator operator--(int)
   185 			{
   186 				iterator old(*this);
   187 				if (m_This)
   188 					m_This = m_This->prev;
   189 				return old;
   190 			}	
   191 			
   192 			//pre increment
   193 			iterator & operator++()
   194 			{
   195 				if (m_This)
   196 					m_This = m_This->next;
   197 				return *this;
   198 			}
   199 			//post increment
   200 			iterator operator++(int)
   201 			{
   202 				iterator old(*this);
   203 				if (m_This)
   204 					m_This = m_This->next;
   205 				return old;
   206 			}
   207 			
   208 			const T & operator * () const
   209 			{
   210 				return m_This->obj;
   211 			}
   212 			T & operator * ()
   213 			{
   214 				return m_This->obj;
   215 			}
   216 			
   217 			T * operator -> ()
   218 			{
   219 				return &(m_This->obj);
   220 			}
   221 			const T * operator -> () const
   222 			{
   223 				return &(m_This->obj);
   224 			}
   225 			
   226 			bool operator != (const iterator &where) const
   227 			{
   228 				return (m_This != where.m_This);
   229 			}
   230 			bool operator ==(const iterator &where) const
   231 			{
   232 				return (m_This == where.m_This);
   233 			}
   234 
   235 			operator bool()
   236 			{
   237 				return m_This != NULL;
   238 			}
   239 		private:
   240 			ListNode *m_This;
   241 		};
   242 	public:
   243 		iterator begin() const
   244 		{
   245 			return iterator(m_Head->next);
   246 		}
   247 		iterator end() const
   248 		{
   249 			return iterator(m_Head);
   250 		}
   251 		iterator erase(iterator &where)
   252 		{
   253 			ListNode *pNode = where.m_This;
   254 			iterator iter(where);
   255 			iter++;
   256 
   257 
   258 			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
   259 			pNode->prev->next = pNode->next;
   260 			pNode->next->prev = pNode->prev;
   261 
   262 			delete pNode;
   263 			m_Size--;
   264 
   265 			return iter;
   266 		}
   267 
   268 		iterator insert(iterator where, const T &obj)
   269 		{
   270 			// Insert obj right before where
   271 
   272 			ListNode *node = new ListNode(obj);
   273 			ListNode *pWhereNode = where.m_This;
   274 			
   275 			pWhereNode->prev->next = node;
   276 			node->prev = pWhereNode->prev;
   277 			pWhereNode->prev = node;
   278 			node->next = pWhereNode;
   279 
   280 			m_Size++;
   281 
   282 			return iterator(node);
   283 		}
   284 
   285 	public:
   286 		void remove(const T & obj)
   287 		{
   288 			iterator b;
   289 			for (b=begin(); b!=end(); b++)
   290 			{
   291 				if ( (*b) == obj )
   292 				{
   293 					erase( b );
   294 					break;
   295 				}
   296 			}
   297 		}
   298 		template <typename U>
   299 		iterator find(const U & equ) const
   300 		{
   301 			iterator iter;
   302 			for (iter=begin(); iter!=end(); iter++)
   303 			{
   304 				if ( (*iter) == equ )
   305 					return iter;
   306 			}
   307 			return end();
   308 		}
   309 		List & operator =(const List &src)
   310 		{
   311 			clear();
   312 			iterator iter;
   313 			for (iter=src.begin(); iter!=src.end(); iter++)
   314 				push_back( (*iter) );
   315 			return *this;
   316 		}
   317 	};
   318 
   319 };	//NAMESPACE
   320 
   321 #endif //_INCLUDE_CSDM_LIST_H