csutil/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 COMP_VC 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 00040 typedef unsigned int csHashKey; 00042 typedef void* csHashObject; 00043 00047 struct csHashElement 00048 { 00049 csHashKey key; 00050 csHashObject object; 00051 }; 00052 00054 typedef csArray<csHashElement> csHashBucket; 00056 typedef csArray<csHashBucket> csHashBucketVector; 00057 00066 class CS_CSUTIL_EXPORT csGlobalHashIterator 00067 { 00068 friend class csHashMap; 00069 friend class csGlobalHashIteratorReversible; 00070 00071 private: 00073 csHashBucket* bucket; 00075 const csHashBucket* cbucket; 00077 int element_index; 00079 unsigned int bucket_index; 00081 unsigned int bucket_len; 00083 unsigned int nbuckets; 00085 csHashMap* hash; 00087 const csHashMap* chash; 00088 00089 private: 00091 void GotoNextElement (); 00092 00094 void GotoNextElementConst (); 00095 00096 public: 00102 csGlobalHashIterator (csHashMap* hash); 00103 00107 csGlobalHashIterator (const csHashMap* hash); 00108 00110 bool HasNext () const; 00112 csHashObject Next (); 00114 const csHashObject NextConst (); 00119 void DeleteNext (); 00120 }; 00121 00130 class CS_CSUTIL_EXPORT csHashIterator 00131 { 00132 friend class csHashMap; 00133 friend class csHashIteratorReversible; 00134 00135 private: 00137 csHashBucket* bucket; 00139 const csHashBucket* cbucket; 00141 int element_index; 00143 int current_index; 00145 unsigned int bucket_index; 00147 csHashKey key; 00149 csHashMap* hash; 00151 const csHashMap* chash; 00152 00153 private: 00155 void GotoNextSameKey (); 00156 00158 void GotoNextSameKeyConst (); 00159 00160 public: 00166 csHashIterator (csHashMap* hash, csHashKey Key); 00167 00171 csHashIterator (const csHashMap* hash, csHashKey Key); 00172 00174 bool HasNext () const; 00176 csHashObject Next (); 00178 const csHashObject NextConst (); 00183 void DeleteNext (); 00184 }; 00185 00193 class CS_CSUTIL_EXPORT csHashMap 00194 { 00195 friend class csHashIterator; 00196 friend class csGlobalHashIterator; 00197 friend class csHashMapReversible; 00198 00199 private: 00201 csHashBucketVector Buckets; 00203 unsigned int NumBuckets; 00205 int hash_elements; 00206 00208 void ChangeBuckets (unsigned int newsize); 00209 00213 void PutInternal (unsigned int idx, csHashKey key, csHashObject object); 00214 00215 00217 static unsigned int FindNextPrime (unsigned int num); 00218 00219 public: 00220 static unsigned int prime_table[]; 00221 00232 csHashMap (unsigned int size = 53); 00233 00238 virtual ~csHashMap (); 00239 00245 void Put (csHashKey key, csHashObject object); 00246 00254 csHashObject Get (csHashKey key) const; 00255 00262 void Delete (csHashKey key, csHashObject object); 00263 00267 void DeleteAll (csHashKey key); 00268 00272 void DeleteAll (); 00273 00277 void DumpStats (); 00278 }; 00279 00285 class CS_CSUTIL_EXPORT csHashSet 00286 { 00287 private: 00288 csHashMap map; 00289 00290 public: 00295 csHashSet (unsigned int size = 211); 00296 00301 void Add (csHashObject object); 00302 00309 void AddNoTest (csHashObject object); 00310 00314 bool In (csHashObject object); 00315 00319 void DeleteAll (); 00320 00325 void Delete (csHashObject object); 00326 00328 inline csHashMap *GetHashMap () {return ↦} 00329 }; 00330 00331 #endif // __CS_HASHMAP_H__ 00332
Generated for Crystal Space by doxygen 1.2.18