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