Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages
hashmap.h
00001 /* 00002 Copyright (C) 2000 by Jorrit Tyberghein 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Library General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00017 */ 00018 00019 #ifndef __CS_HASHMAP_H__ 00020 #define __CS_HASHMAP_H__ 00021 00022 #if 0 // let's not deprecate just yet :) 00023 #ifndef CS_COMPILER_MSVC 00024 # warning Use of csHashMap is deprecated. Please csHash instead. 00025 #endif 00026 #endif 00027 00028 #include "csextern.h" 00029 #include "parray.h" 00030 #include "array.h" 00031 // For csHashCompute() which used to be declared here. 00032 #include "hash.h" 00033 00034 class csHashMapReversible; 00035 class csHashIteratorReversible; 00036 00037 class csHashMap; 00038 00039 #if (CS_PROCESSOR_SIZE == 32) 00040 # if (_MSC_VER >= 1300) 00041 /* 00042 * Silence VC7 64bit warning. 00043 */ 00044 typedef unsigned int __w64 csHashKey; 00045 # else 00046 00047 typedef unsigned int csHashKey; 00048 # endif 00049 #else 00050 /* 00051 * At some places, pointers are casted to csHashKey. Work around truncation 00052 * problems by forcing csHashKey to at least 64bit on 64bit machines. 00053 */ 00054 typedef uint64 csHashKey; 00055 #endif 00056 00057 typedef void* csHashObject; 00058 00062 struct csHashElement 00063 { 00064 csHashKey key; 00065 csHashObject object; 00066 }; 00067 00069 typedef csArray<csHashElement> csHashBucket; 00071 typedef csArray<csHashBucket> csHashBucketVector; 00072 00081 class CS_CSUTIL_EXPORT csGlobalHashIterator 00082 { 00083 friend class csHashMap; 00084 friend class csGlobalHashIteratorReversible; 00085 00086 private: 00088 csHashBucket* bucket; 00090 const csHashBucket* cbucket; 00092 size_t element_index; 00094 size_t bucket_index; 00096 size_t bucket_len; 00098 size_t nbuckets; 00100 csHashMap* hash; 00102 const csHashMap* chash; 00103 00104 private: 00106 void GotoNextElement (); 00107 00109 void GotoNextElementConst (); 00110 00111 public: 00117 csGlobalHashIterator (csHashMap* hash); 00118 00122 csGlobalHashIterator (const csHashMap* hash); 00123 00125 bool HasNext () const; 00127 csHashObject Next (); 00129 csHashObject NextConst (); 00134 void DeleteNext (); 00135 }; 00136 00145 class CS_CSUTIL_EXPORT csHashIterator 00146 { 00147 friend class csHashMap; 00148 friend class csHashIteratorReversible; 00149 00150 private: 00152 csHashBucket* bucket; 00154 const csHashBucket* cbucket; 00156 size_t element_index; 00158 size_t current_index; 00160 size_t bucket_index; 00162 csHashKey key; 00164 csHashMap* hash; 00166 const csHashMap* chash; 00167 00168 private: 00170 void GotoNextSameKey (); 00171 00173 void GotoNextSameKeyConst (); 00174 00175 public: 00181 csHashIterator (csHashMap* hash, csHashKey Key); 00182 00186 csHashIterator (const csHashMap* hash, csHashKey Key); 00187 00189 bool HasNext () const; 00191 csHashObject Next (); 00193 csHashObject NextConst (); 00198 void DeleteNext (); 00199 }; 00200 00208 class CS_CSUTIL_EXPORT csHashMap 00209 { 00210 friend class csHashIterator; 00211 friend class csGlobalHashIterator; 00212 friend class csHashMapReversible; 00213 00214 private: 00216 csHashBucketVector Buckets; 00218 size_t NumBuckets; 00220 size_t hash_elements; 00221 00223 void ChangeBuckets (size_t newsize); 00224 00228 void PutInternal (size_t idx, csHashKey key, csHashObject object); 00229 00230 00232 static size_t FindNextPrime (size_t num); 00233 00234 public: 00235 static size_t prime_table[]; 00236 00247 csHashMap (size_t size = 53); 00248 00253 virtual ~csHashMap (); 00254 00260 void Put (csHashKey key, csHashObject object); 00261 00269 csHashObject Get (csHashKey key) const; 00270 00277 void Delete (csHashKey key, csHashObject object); 00278 00282 void DeleteAll (csHashKey key); 00283 00287 void DeleteAll (); 00288 00292 void DumpStats (); 00293 }; 00294 00300 class CS_CSUTIL_EXPORT csHashSet 00301 { 00302 private: 00303 csHashMap map; 00304 00305 public: 00310 csHashSet (unsigned int size = 211); 00311 00316 void Add (csHashObject object); 00317 00324 void AddNoTest (csHashObject object); 00325 00329 bool In (csHashObject object); 00330 00334 void DeleteAll (); 00335 00340 void Delete (csHashObject object); 00341 00343 inline csHashMap *GetHashMap () {return ↦} 00344 }; 00345 00346 #endif // __CS_HASHMAP_H__ 00347
Generated for Crystal Space by doxygen 1.3.9.1