zibbr

Random 3d and p2p stuff that was originally the beginnings of an overly ambitious p2p virtual world thingy
git clone https://code.literati.org/zibbr.git
Log | Files | Refs

fsa.h (5969B)


      1 /* 
      2 
      3 A* Algorithm Implementation using STL is
      4 Copyright (C)2001-2005 Justin Heyes-Jones
      5 
      6 Permission is given by the author to freely redistribute and 
      7 include this code in any program as long as this credit is 
      8 given where due.
      9  
     10   COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, 
     11   WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, 
     12   INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE 
     13   IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
     14   OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND 
     15   PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED 
     16   CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL 
     17   DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY 
     18   NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF 
     19   WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE 
     20   OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
     21   THIS DISCLAIMER.
     22  
     23   Use at your own risk!
     24 
     25 
     26 
     27   FixedSizeAllocator class
     28   Copyright 2001 Justin Heyes-Jones
     29 
     30   This class is a constant time O(1) memory manager for objects of 
     31   a specified type. The type is specified using a template class.
     32 
     33   Memory is allocated from a fixed size buffer which you can specify in the
     34   class constructor or use the default.
     35 
     36   Using GetFirst and GetNext it is possible to iterate through the elements
     37   one by one, and this would be the most common use for the class. 
     38 
     39   I would suggest using this class when you want O(1) add and delete
     40   and you don't do much searching, which would be O(n). Structures such as binary 
     41   trees can be used instead to get O(logn) access time.
     42 
     43 */
     44 
     45 #ifndef FSA_H
     46 #define FSA_H
     47 
     48 #include <string.h>
     49 #include <stdio.h>
     50 
     51 template <class USER_TYPE> class FixedSizeAllocator
     52 {
     53 
     54 public: 
     55 	// Constants
     56 	enum
     57 	{
     58 		FSA_DEFAULT_SIZE = 100
     59 	};
     60 
     61 	// This class enables us to transparently manage the extra data 
     62 	// needed to enable the user class to form part of the double-linked
     63 	// list class
     64 	struct FSA_ELEMENT
     65 	{
     66 		USER_TYPE UserType;
     67 		
     68 		FSA_ELEMENT *pPrev;
     69 		FSA_ELEMENT *pNext;
     70 	};
     71 
     72 public: // methods
     73 	FixedSizeAllocator( unsigned int MaxElements = FSA_DEFAULT_SIZE ) :
     74 	m_MaxElements( MaxElements ),
     75 	m_pFirstUsed( NULL )
     76 	{
     77 		// Allocate enough memory for the maximum number of elements
     78 
     79 		m_pMemory = (FSA_ELEMENT *) (new char[ m_MaxElements * sizeof(FSA_ELEMENT) ]); 
     80 
     81 		// Set the free list first pointer
     82 		m_pFirstFree = m_pMemory;
     83 
     84 		// Clear the memory
     85 		memset( m_pMemory, 0, sizeof( FSA_ELEMENT ) * m_MaxElements );
     86 
     87 		// Point at first element
     88 		FSA_ELEMENT *pElement = m_pFirstFree;
     89 
     90 		// Set the double linked free list
     91 		for( unsigned int i=0; i<m_MaxElements; i++ )
     92 		{
     93 			pElement->pPrev = pElement-1;
     94 			pElement->pNext = pElement+1;
     95 
     96 			pElement++;
     97 		}
     98 
     99 		// first element should have a null prev
    100 		m_pFirstFree->pPrev = NULL;
    101 		// last element should have a null next
    102 		(pElement-1)->pNext = NULL;
    103 
    104 	}
    105 
    106 
    107 	~FixedSizeAllocator()
    108 	{
    109 		// Free up the memory
    110 		delete [] (char *) m_pMemory;
    111 	}
    112 
    113 	// Allocate a new USER_TYPE and return a pointer to it 
    114 	USER_TYPE *alloc()
    115 	{
    116 
    117 		FSA_ELEMENT *pNewNode = NULL;
    118 
    119 		if( !m_pFirstFree )
    120 		{
    121 			return NULL;
    122 		}
    123 		else
    124 		{
    125 			pNewNode = m_pFirstFree;
    126 			m_pFirstFree = pNewNode->pNext;
    127 
    128 			// if the new node points to another free node then
    129 			// change that nodes prev free pointer...
    130 			if( pNewNode->pNext )
    131 			{
    132 				pNewNode->pNext->pPrev = NULL;
    133 			}
    134 
    135 			// node is now on the used list
    136 
    137 			pNewNode->pPrev = NULL; // the allocated node is always first in the list
    138 
    139 			if( m_pFirstUsed == NULL )
    140 			{
    141 				pNewNode->pNext = NULL; // no other nodes
    142 			}
    143 			else
    144 			{
    145 				m_pFirstUsed->pPrev = pNewNode; // insert this at the head of the used list
    146 				pNewNode->pNext = m_pFirstUsed;
    147 			}
    148 
    149 			m_pFirstUsed = pNewNode;
    150 		}	
    151 		
    152 		return reinterpret_cast<USER_TYPE*>(pNewNode);
    153 	}
    154 
    155 	// Free the given user type
    156 	// For efficiency I don't check whether the user_data is a valid
    157 	// pointer that was allocated. I may add some debug only checking
    158 	// (To add the debug check you'd need to make sure the pointer is in 
    159 	// the m_pMemory area and is pointing at the start of a node)
    160 	void free( USER_TYPE *user_data )
    161 	{
    162 		FSA_ELEMENT *pNode = reinterpret_cast<FSA_ELEMENT*>(user_data);
    163 
    164 		// manage used list, remove this node from it
    165 		if( pNode->pPrev )
    166 		{
    167 			pNode->pPrev->pNext = pNode->pNext;
    168 		}
    169 		else
    170 		{
    171 			// this handles the case that we delete the first node in the used list
    172 			m_pFirstUsed = pNode->pNext;
    173 		}
    174 
    175 		if( pNode->pNext )
    176 		{
    177 			pNode->pNext->pPrev = pNode->pPrev;
    178 		}
    179 
    180 		// add to free list
    181 		if( m_pFirstFree == NULL ) 
    182 		{
    183 			// free list was empty
    184 			m_pFirstFree = pNode;
    185 			pNode->pPrev = NULL;
    186 			pNode->pNext = NULL;
    187 		}
    188 		else
    189 		{
    190 			// Add this node at the start of the free list
    191 			m_pFirstFree->pPrev = pNode;
    192 			pNode->pNext = m_pFirstFree;
    193 			m_pFirstFree = pNode;
    194 		}
    195 
    196 	}
    197 
    198 	// For debugging this displays both lists (using the prev/next list pointers)
    199 	void Debug()
    200 	{
    201 		printf( "free list " );
    202 
    203 		FSA_ELEMENT *p = m_pFirstFree;
    204 		while( p )
    205 		{
    206 			printf( "%x!%x ", p->pPrev, p->pNext );
    207 			p = p->pNext;
    208 		}
    209 		printf( "\n" );
    210 
    211 		printf( "used list " );
    212 
    213 		p = m_pFirstUsed;
    214 		while( p )
    215 		{
    216 			printf( "%x!%x ", p->pPrev, p->pNext );
    217 			p = p->pNext;
    218 		}
    219 		printf( "\n" );
    220 	}
    221 
    222 	// Iterators
    223 
    224 	USER_TYPE *GetFirst()
    225 	{
    226 		return reinterpret_cast<USER_TYPE *>(m_pFirstUsed);
    227 	}
    228 
    229 	USER_TYPE *GetNext( USER_TYPE *node )
    230 	{
    231 		return reinterpret_cast<USER_TYPE *>
    232 			(
    233 				(reinterpret_cast<FSA_ELEMENT *>(node))->pNext
    234 			);
    235 	}
    236 
    237 public: // data
    238 
    239 private: // methods
    240 
    241 private: // data
    242 
    243 	FSA_ELEMENT *m_pFirstFree;
    244 	FSA_ELEMENT *m_pFirstUsed;
    245 	unsigned int m_MaxElements;
    246 	FSA_ELEMENT *m_pMemory;
    247 
    248 };
    249 
    250 #endif // defined FSA_H