Home - sourcemod-central - file revision - core/sm_fastlink.h@2cd3d817b5ab Mercurial
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
core/sm_fastlink.h
author David Anderson <dvander@alliedmods.net>
Fri Jun 08 03:50:23 2007 +0000 (2007-06-08)
changeset 925 2cd3d817b5ab
parent 854 ffeae23d84b3
child 1131 d109d9e33ee5
permissions -rw-r--r--
added sm_unban 
     1 /**
     2  * vim: set ts=4 :
     3  * ===============================================================
     4  * SourceMod (C)2004-2007 AlliedModders LLC.  All rights reserved.
     5  * ===============================================================
     6  *
     7  * This file is not open source and may not be copied without explicit
     8  * written permission of AlliedModders LLC.  This file may not be redistributed 
     9  * in whole or significant part.
    10  * For information, see LICENSE.txt or http://www.sourcemod.net/license.php
    11  *
    12  * Version: $Id$
    13  */
    14 
    15 
    16 #ifndef _INCLUDE_SOURCEMOD_FASTLINK_H_
    17 #define _INCLUDE_SOURCEMOD_FASTLINK_H_
    18 
    19 #include <assert.h>
    20 
    21 template <typename T>
    22 class FastLink
    23 {
    24 	friend class iterator;
    25 public:
    26 	struct FastLinkNode
    27 	{
    28 		unsigned int prev;
    29 		unsigned int next;
    30 		unsigned int freeNode;
    31 		T obj;
    32 	};
    33 public:
    34 	FastLink(unsigned int maxsize) : m_Size(0), m_FirstLink(0), m_FreeNodes(0), m_LastLink(0)
    35 	{
    36 		m_MaxSize = maxsize;
    37 		m_Nodes = new FastLinkNode[m_MaxSize+1];
    38 	}
    39 public:
    40 	bool push_back(const T & obj)
    41 	{
    42 		unsigned int new_node = GetFreeIndex();
    43 		if (!new_node)
    44 		{
    45 			return false;
    46 		}
    47 		m_Nodes[new_node].obj = obj;
    48 		m_Nodes[new_node].next = 0;
    49 		if (!m_FirstLink)
    50 		{
    51 			m_Nodes[new_node].prev = 0;
    52 			m_FirstLink = new_node;
    53 			m_LastLink = new_node;
    54 		} else {
    55 			m_Nodes[new_node].prev = m_LastLink;
    56 			m_Nodes[m_LastLink].next = new_node;
    57 			m_LastLink = new_node;
    58 		}
    59 		m_Size++;
    60 		return true;
    61 	}
    62 	size_t size() const
    63 	{
    64 		return m_Size;
    65 	}
    66 private:
    67 	unsigned int GetFreeIndex()
    68 	{
    69 		if (m_FreeNodes)
    70 		{
    71 			return m_Nodes[m_FreeNodes--].freeNode;
    72 		} else {
    73 			if (m_LastLink >= m_MaxSize)
    74 			{
    75 				return 0;
    76 			}
    77 			return m_LastLink + 1;
    78 		}
    79 	}
    80 public:
    81 	class iterator
    82 	{
    83 		friend class FastLink;
    84 	public:
    85 		iterator()
    86 		{
    87 			link = NULL;
    88 			position = 0;
    89 		}
    90 		iterator(const FastLink *_link, unsigned int _position)
    91 		{
    92 			link = _link;
    93 			position = _position;
    94 		}
    95 	public:
    96 		bool operator ==(const iterator &where) const
    97 		{
    98 			return (link == where.link && position == where.position);
    99 		}
   100 		bool operator !=(const iterator &where) const
   101 		{
   102 			return (link != where.link || position != where.position);
   103 		}
   104 		T & operator *()
   105 		{
   106 			return link->m_Nodes[position].obj;
   107 		}
   108 		const T & operator *() const
   109 		{
   110 			return link->m_Nodes[position].obj;
   111 		}
   112 		iterator & operator++()
   113 		{
   114 			position = link->m_Nodes[position].next;
   115 			return *this;
   116 		}
   117 	private:
   118 		const FastLink *link;
   119 		unsigned int position;
   120 	};
   121 public:
   122 	iterator begin() const
   123 	{
   124 		return iterator(this, m_FirstLink);
   125 	}
   126 	iterator end() const
   127 	{
   128 		return iterator(this, 0);
   129 	}
   130 	void remove(const T & obj)
   131 	{
   132 		for (iterator iter=begin(); iter!=end(); ++iter)
   133 		{
   134 			if ((*iter) == obj)
   135 			{
   136 				erase(iter);
   137 				return;
   138 			}
   139 		}
   140 	}
   141 	iterator erase(const iterator &where)
   142 	{
   143 		/* Whoa, this better be right! */
   144 		assert(where.link == this);
   145 
   146 		iterator iter(where.link, where.position);
   147 		++iter;
   148 
   149 		unsigned int index = where.position;
   150 
   151 		/* Each case is different, we have no sentinel.
   152 		 * CASE: We're the HEAD AND the TAIL */
   153 		if (index == m_FirstLink
   154 			&& index == m_LastLink)
   155 		{
   156 			m_FirstLink = 0;
   157 			m_LastLink = 0;
   158 		}
   159 		/* We're the HEAD */
   160 		else if (index == m_FirstLink)
   161 		{
   162 			m_FirstLink = m_Nodes[index].next;
   163 			m_Nodes[m_FirstLink].prev = 0;
   164 		}
   165 		/* We're the TAIL */
   166 		else if (index == m_LastLink)
   167 		{
   168 			m_LastLink = m_Nodes[index].prev;
   169 			m_Nodes[m_LastLink].next = 0;
   170 		}
   171 		/* We're in the middle! */
   172 		else
   173 		{
   174 			/* Patch forward reference */
   175 			m_Nodes[m_Nodes[index].next].prev = m_Nodes[index].prev;
   176 			/* Patch backward reference */
   177 			m_Nodes[m_Nodes[index].prev].next = m_Nodes[index].next;
   178 		}
   179 
   180 		/* Add us to the free list */
   181 		m_Nodes[++m_FreeNodes].freeNode = index;
   182 
   183 		m_Size--;
   184 
   185 		return iter;
   186 	}
   187 private:
   188 	size_t m_Size;
   189 	unsigned int m_FirstLink;
   190 	unsigned int m_FreeNodes;
   191 	unsigned int m_LastLink;
   192 	unsigned int m_MaxSize;
   193 	FastLinkNode *m_Nodes;
   194 };
   195 
   196 #endif //_INCLUDE_SOURCEMOD_FASTLINK_H_
sourcemod-central
Feed