Home - sourcemod-central - file revision - core/sm_fastlink.h@a0587dee87ae Mercurial
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
core/sm_fastlink.h
author Nicholas Hastings <skamonkey@gmail.com>
Mon Jun 14 09:32:50 2010 -0400 (2010-06-14)
changeset 3041 a0587dee87ae
parent 2289 44045ead61cd
child 3261 e4359292e59a
permissions -rw-r--r--
Fixed outputname null pointer crash in sdktools (bug 4422, r=fyren) 
     1 /**
     2  * vim: set ts=4 :
     3  * =============================================================================
     4  * SourceMod
     5  * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
     6  * =============================================================================
     7  *
     8  * This program is free software; you can redistribute it and/or modify it under
     9  * the terms of the GNU General Public License, version 3.0, as published by the
    10  * Free Software Foundation.
    11  * 
    12  * This program is distributed in the hope that it will be useful, but WITHOUT
    13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
    15  * details.
    16  *
    17  * You should have received a copy of the GNU General Public License along with
    18  * this program.  If not, see <http://www.gnu.org/licenses/>.
    19  *
    20  * As a special exception, AlliedModders LLC gives you permission to link the
    21  * code of this program (as well as its derivative works) to "Half-Life 2," the
    22  * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
    23  * by the Valve Corporation.  You must obey the GNU General Public License in
    24  * all respects for all other code used.  Additionally, AlliedModders LLC grants
    25  * this exception to all derivative works.  AlliedModders LLC defines further
    26  * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
    27  * or <http://www.sourcemod.net/license.php>.
    28  *
    29  * Version: $Id$
    30  */
    31 
    32 #ifndef _INCLUDE_SOURCEMOD_FASTLINK_H_
    33 #define _INCLUDE_SOURCEMOD_FASTLINK_H_
    34 
    35 #include <assert.h>
    36 
    37 template <typename T>
    38 class FastLink
    39 {
    40 	friend class iterator;
    41 public:
    42 	struct FastLinkNode
    43 	{
    44 		unsigned int prev;
    45 		unsigned int next;
    46 		unsigned int freeNode;
    47 		T obj;
    48 	};
    49 public:
    50 	FastLink(unsigned int maxsize) : m_Size(0), m_FirstLink(0), m_FreeNodes(0), m_LastLink(0), m_UsableIndex(0)
    51 	{
    52 		m_MaxSize = maxsize;
    53 		m_Nodes = new FastLinkNode[m_MaxSize+1];
    54 	}
    55 public:
    56 	bool push_back(const T & obj)
    57 	{
    58 		unsigned int new_node = GetFreeIndex();
    59 		if (!new_node)
    60 		{
    61 			return false;
    62 		}
    63 		m_Nodes[new_node].obj = obj;
    64 		m_Nodes[new_node].next = 0;
    65 		if (!m_FirstLink)
    66 		{
    67 			m_Nodes[new_node].prev = 0;
    68 			m_FirstLink = new_node;
    69 			m_LastLink = new_node;
    70 		} else {
    71 			m_Nodes[new_node].prev = m_LastLink;
    72 			m_Nodes[m_LastLink].next = new_node;
    73 			m_LastLink = new_node;
    74 		}
    75 		m_Size++;
    76 		return true;
    77 	}
    78 	size_t size() const
    79 	{
    80 		return m_Size;
    81 	}
    82 private:
    83 	unsigned int GetFreeIndex()
    84 	{
    85 		if (m_FreeNodes)
    86 		{
    87 			return m_Nodes[m_FreeNodes--].freeNode;
    88 		} else {
    89 			if (m_UsableIndex >= m_MaxSize)
    90 			{
    91 				return 0;
    92 			}
    93 			m_UsableIndex++;
    94 			return m_UsableIndex;
    95 		}
    96 	}
    97 public:
    98 	class iterator
    99 	{
   100 		friend class FastLink;
   101 	public:
   102 		iterator()
   103 		{
   104 			link = NULL;
   105 			position = 0;
   106 		}
   107 		iterator(const FastLink *_link, unsigned int _position)
   108 		{
   109 			link = _link;
   110 			position = _position;
   111 		}
   112 	public:
   113 		bool operator ==(const iterator &where) const
   114 		{
   115 			return (link == where.link && position == where.position);
   116 		}
   117 		bool operator !=(const iterator &where) const
   118 		{
   119 			return (link != where.link || position != where.position);
   120 		}
   121 		T & operator *()
   122 		{
   123 			return link->m_Nodes[position].obj;
   124 		}
   125 		const T & operator *() const
   126 		{
   127 			return link->m_Nodes[position].obj;
   128 		}
   129 		iterator & operator++()
   130 		{
   131 			position = link->m_Nodes[position].next;
   132 			return *this;
   133 		}
   134 	private:
   135 		const FastLink *link;
   136 		unsigned int position;
   137 	};
   138 public:
   139 	iterator begin() const
   140 	{
   141 		return iterator(this, m_FirstLink);
   142 	}
   143 	iterator end() const
   144 	{
   145 		return iterator(this, 0);
   146 	}
   147 	void remove(const T & obj)
   148 	{
   149 		for (iterator iter=begin(); iter!=end(); ++iter)
   150 		{
   151 			if ((*iter) == obj)
   152 			{
   153 				erase(iter);
   154 				return;
   155 			}
   156 		}
   157 	}
   158 	iterator erase(const iterator &where)
   159 	{
   160 		/* Whoa, this better be right! */
   161 		assert(where.link == this);
   162 
   163 		iterator iter(where.link, where.position);
   164 		++iter;
   165 
   166 		unsigned int index = where.position;
   167 
   168 		/* Each case is different, we have no sentinel.
   169 		 * CASE: We're the HEAD AND the TAIL */
   170 		if (index == m_FirstLink
   171 			&& index == m_LastLink)
   172 		{
   173 			m_FirstLink = 0;
   174 			m_LastLink = 0;
   175 		}
   176 		/* We're the HEAD */
   177 		else if (index == m_FirstLink)
   178 		{
   179 			m_FirstLink = m_Nodes[index].next;
   180 			m_Nodes[m_FirstLink].prev = 0;
   181 		}
   182 		/* We're the TAIL */
   183 		else if (index == m_LastLink)
   184 		{
   185 			m_LastLink = m_Nodes[index].prev;
   186 			m_Nodes[m_LastLink].next = 0;
   187 		}
   188 		/* We're in the middle! */
   189 		else
   190 		{
   191 			/* Patch forward reference */
   192 			m_Nodes[m_Nodes[index].next].prev = m_Nodes[index].prev;
   193 			/* Patch backward reference */
   194 			m_Nodes[m_Nodes[index].prev].next = m_Nodes[index].next;
   195 		}
   196 
   197 		/* Add us to the free list */
   198 		m_Nodes[++m_FreeNodes].freeNode = index;
   199 
   200 		m_Size--;
   201 
   202 		return iter;
   203 	}
   204 #if defined MENU_DEBUG
   205 public:
   206 #else
   207 private:
   208 #endif
   209 	size_t m_Size;
   210 	unsigned int m_FirstLink;
   211 	unsigned int m_FreeNodes;
   212 	unsigned int m_LastLink;
   213 	unsigned int m_MaxSize;
   214 	unsigned int m_UsableIndex;
   215 	FastLinkNode *m_Nodes;
   216 };
   217 
   218 #endif //_INCLUDE_SOURCEMOD_FASTLINK_H_
sourcemod-central
Feed