1 /// \file DS_Map.h
2 /// \internal
3 /// \brief Map
4 ///
5 /// This file is part of RakNet Copyright 2003 Jenkins Software LLC
6 ///
7 /// Raknet is available under the terms of the GPLv3 license, see /usr/local/share/licenses/raknet-3.9.2_10,1/GPLv3.
8 
9 
10 #ifndef __RAKNET_MAP_H
11 #define __RAKNET_MAP_H
12 
13 #include "DS_OrderedList.h"
14 #include "Export.h"
15 #include "RakMemoryOverride.h"
16 #include "RakAssert.h"
17 
18 // If I want to change this to a red-black tree, this is a good site: http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
19 // This makes insertions and deletions faster.  But then traversals are slow, while they are currently fast.
20 
21 /// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures
22 /// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish.
23 namespace DataStructures
24 {
25 	/// The default comparison has to be first so it can be called as a default parameter.
26 	/// It then is followed by MapNode, followed by NodeComparisonFunc
27 	template <class key_type>
defaultMapKeyComparison(const key_type & a,const key_type & b)28 		int defaultMapKeyComparison(const key_type &a, const key_type &b)
29 	{
30 		if (a<b) return -1; if (a==b) return 0; return 1;
31 	}
32 
33 	/// \note IMPORTANT! If you use defaultMapKeyComparison then call IMPLEMENT_DEFAULT_COMPARISON or you will get an unresolved external linker error.
34 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&, const key_type&)=defaultMapKeyComparison<key_type> >
35 	class RAK_DLL_EXPORT Map
36 	{
37 	public:
IMPLEMENT_DEFAULT_COMPARISON(void)38 		static void IMPLEMENT_DEFAULT_COMPARISON(void) {DataStructures::defaultMapKeyComparison<key_type>(key_type(),key_type());}
39 
40 		struct MapNode
41 		{
MapNodeMapNode42 			MapNode() {}
MapNodeMapNode43 			MapNode(key_type _key, data_type _data) : mapNodeKey(_key), mapNodeData(_data) {}
44 			MapNode& operator = ( const MapNode& input ) {mapNodeKey=input.mapNodeKey; mapNodeData=input.mapNodeData; return *this;}
MapNodeMapNode45 			MapNode( const MapNode & input) {mapNodeKey=input.mapNodeKey; mapNodeData=input.mapNodeData;}
46 			key_type mapNodeKey;
47 			data_type mapNodeData;
48 		};
49 
50 		// Has to be a static because the comparison callback for DataStructures::OrderedList is a C function
NodeComparisonFunc(const key_type & a,const MapNode & b)51 		static int NodeComparisonFunc(const key_type &a, const MapNode &b)
52 		{
53 #ifdef _MSC_VER
54 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
55 #endif
56 			return key_comparison_func(a, b.mapNodeKey);
57 		}
58 
59 		Map();
60 		~Map();
61 		Map( const Map& original_copy );
62 		Map& operator= ( const Map& original_copy );
63 
64 		data_type& Get(const key_type &key) const;
65 		data_type Pop(const key_type &key);
66 		// Add if needed
67 		void Set(const key_type &key, const data_type &data);
68 		// Must already exist
69 		void SetExisting(const key_type &key, const data_type &data);
70 		// Must add
71 		void SetNew(const key_type &key, const data_type &data);
72 		bool Has(const key_type &key) const;
73 		bool Delete(const key_type &key);
74 		data_type& operator[] ( const unsigned int position ) const;
75 		key_type GetKeyAtIndex( const unsigned int position ) const;
76 		unsigned GetIndexAtKey( const key_type &key );
77 		void RemoveAtIndex(const unsigned index);
78 		void Clear(void);
79 		unsigned Size(void) const;
80 
81 	protected:
82 		DataStructures::OrderedList< key_type,MapNode,&Map::NodeComparisonFunc > mapNodeList;
83 
84 		void SaveLastSearch(const key_type &key, unsigned index) const;
85 		bool HasSavedSearchResult(const key_type &key) const;
86 
87 		unsigned lastSearchIndex;
88 		key_type lastSearchKey;
89 		bool lastSearchIndexValid;
90 	};
91 
92 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Map()93 	Map<key_type, data_type, key_comparison_func>::Map()
94 	{
95 		lastSearchIndexValid=false;
96 	}
97 
98 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
~Map()99 	Map<key_type, data_type, key_comparison_func>::~Map()
100 	{
101 		Clear();
102 	}
103 
104 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Map(const Map & original_copy)105 	Map<key_type, data_type, key_comparison_func>::Map( const Map& original_copy )
106 	{
107 		mapNodeList=original_copy.mapNodeList;
108         lastSearchIndex=original_copy.lastSearchIndex;
109 		lastSearchKey=original_copy.lastSearchKey;
110 		lastSearchIndexValid=original_copy.lastSearchIndexValid;
111 	}
112 
113     template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
114 	Map<key_type, data_type, key_comparison_func>& Map<key_type, data_type, key_comparison_func>::operator= ( const Map& original_copy )
115 	{
116 		mapNodeList=original_copy.mapNodeList;
117 		lastSearchIndex=original_copy.lastSearchIndex;
118 		lastSearchKey=original_copy.lastSearchKey;
119 		lastSearchIndexValid=original_copy.lastSearchIndexValid;
120 		return *this;
121 	}
122 
123 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Get(const key_type & key)124 	data_type& Map<key_type, data_type, key_comparison_func>::Get(const key_type &key) const
125 	{
126 		if (HasSavedSearchResult(key))
127 			return mapNodeList[lastSearchIndex].mapNodeData;
128 
129 		bool objectExists;
130 		unsigned index;
131 		index=mapNodeList.GetIndexFromKey(key, &objectExists);
132 		RakAssert(objectExists);
133 		SaveLastSearch(key,index);
134 		return mapNodeList[index].mapNodeData;
135 	}
136 
137 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
GetIndexAtKey(const key_type & key)138 	unsigned Map<key_type, data_type, key_comparison_func>::GetIndexAtKey( const key_type &key )
139 	{
140 		if (HasSavedSearchResult(key))
141 			return lastSearchIndex;
142 
143 		bool objectExists;
144 		unsigned index;
145 		index=mapNodeList.GetIndexFromKey(key, &objectExists);
146 		if (objectExists==false)
147 		{
148 			RakAssert(objectExists);
149 		}
150 		SaveLastSearch(key,index);
151 		return index;
152 	}
153 
154 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
RemoveAtIndex(const unsigned index)155 	void Map<key_type, data_type, key_comparison_func>::RemoveAtIndex(const unsigned index)
156 	{
157 		mapNodeList.RemoveAtIndex(index);
158 		lastSearchIndexValid=false;
159 	}
160 
161 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Pop(const key_type & key)162 		data_type Map<key_type, data_type, key_comparison_func>::Pop(const key_type &key)
163 	{
164 		bool objectExists;
165 		unsigned index;
166 		if (HasSavedSearchResult(key))
167 			index=lastSearchIndex;
168 		else
169 		{
170 			index=mapNodeList.GetIndexFromKey(key, &objectExists);
171 			RakAssert(objectExists);
172 		}
173 		data_type tmp = mapNodeList[index].mapNodeData;
174 		mapNodeList.RemoveAtIndex(index);
175 		lastSearchIndexValid=false;
176 		return tmp;
177 	}
178 
179 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Set(const key_type & key,const data_type & data)180 	void Map<key_type, data_type, key_comparison_func>::Set(const key_type &key, const data_type &data)
181 	{
182 		bool objectExists;
183 		unsigned index;
184 
185 		if (HasSavedSearchResult(key))
186 		{
187 			mapNodeList[lastSearchIndex].mapNodeData=data;
188 			return;
189 		}
190 
191 		index=mapNodeList.GetIndexFromKey(key, &objectExists);
192 
193 		if (objectExists)
194 		{
195 			SaveLastSearch(key,index);
196 			mapNodeList[index].mapNodeData=data;
197 		}
198 		else
199 		{
200 			SaveLastSearch(key,mapNodeList.Insert(key,MapNode(key,data), true, __FILE__,__LINE__));
201 		}
202 	}
203 
204 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
SetExisting(const key_type & key,const data_type & data)205 	void Map<key_type, data_type, key_comparison_func>::SetExisting(const key_type &key, const data_type &data)
206 	{
207 		bool objectExists;
208 		unsigned index;
209 
210 		if (HasSavedSearchResult(key))
211 		{
212 			index=lastSearchIndex;
213 		}
214 		else
215 		{
216 			index=mapNodeList.GetIndexFromKey(key, &objectExists);
217 			RakAssert(objectExists);
218 			SaveLastSearch(key,index);
219 		}
220 
221 		mapNodeList[index].mapNodeData=data;
222 	}
223 
224 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
SetNew(const key_type & key,const data_type & data)225 	void Map<key_type, data_type, key_comparison_func>::SetNew(const key_type &key, const data_type &data)
226 	{
227 #ifdef _DEBUG
228 		bool objectExists;
229 		mapNodeList.GetIndexFromKey(key, &objectExists);
230 		RakAssert(objectExists==false);
231 #endif
232 		SaveLastSearch(key,mapNodeList.Insert(key,MapNode(key,data), true, __FILE__,__LINE__));
233 	}
234 
235 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Has(const key_type & key)236 	bool Map<key_type, data_type, key_comparison_func>::Has(const key_type &key) const
237 	{
238 		if (HasSavedSearchResult(key))
239 			return true;
240 
241 		bool objectExists;
242 		unsigned index;
243 		index=mapNodeList.GetIndexFromKey(key, &objectExists);
244 		if (objectExists)
245 			SaveLastSearch(key,index);
246 		return objectExists;
247 	}
248 
249 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Delete(const key_type & key)250 	bool Map<key_type, data_type, key_comparison_func>::Delete(const key_type &key)
251 	{
252 		if (HasSavedSearchResult(key))
253 		{
254 			lastSearchIndexValid=false;
255 			mapNodeList.RemoveAtIndex(lastSearchIndex);
256 			return true;
257 		}
258 
259 		bool objectExists;
260 		unsigned index;
261 		index=mapNodeList.GetIndexFromKey(key, &objectExists);
262 		if (objectExists)
263 		{
264 			lastSearchIndexValid=false;
265 			mapNodeList.RemoveAtIndex(index);
266 			return true;
267 		}
268 		else
269 			return false;
270 	}
271 
272 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Clear(void)273 	void Map<key_type, data_type, key_comparison_func>::Clear(void)
274 	{
275 		lastSearchIndexValid=false;
276 		mapNodeList.Clear(false, __FILE__, __LINE__);
277 	}
278 
279 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
280 	data_type& Map<key_type, data_type, key_comparison_func>::operator[]( const unsigned int position ) const
281 	{
282 		return mapNodeList[position].mapNodeData;
283 	}
284 
285 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
GetKeyAtIndex(const unsigned int position)286 		key_type Map<key_type, data_type, key_comparison_func>::GetKeyAtIndex( const unsigned int position ) const
287 	{
288 		return mapNodeList[position].mapNodeKey;
289 	}
290 
291 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
Size(void)292 	unsigned Map<key_type, data_type, key_comparison_func>::Size(void) const
293 	{
294 		return mapNodeList.Size();
295 	}
296 
297 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
SaveLastSearch(const key_type & key,const unsigned index)298 	void Map<key_type, data_type, key_comparison_func>::SaveLastSearch(const key_type &key, const unsigned index) const
299 	{
300 		(void) key;
301 		(void) index;
302 
303 		/*
304 		lastSearchIndex=index;
305 		lastSearchKey=key;
306 		lastSearchIndexValid=true;
307 		*/
308 	}
309 
310 	template <class key_type, class data_type, int (*key_comparison_func)(const key_type&,const key_type&)>
HasSavedSearchResult(const key_type & key)311 	bool Map<key_type, data_type, key_comparison_func>::HasSavedSearchResult(const key_type &key) const
312 	{
313 		(void) key;
314 
315 		// Not threadsafe!
316 		return false;
317 		// return lastSearchIndexValid && key_comparison_func(key,lastSearchKey)==0;
318 	}
319 }
320 
321 #endif
322