![]() |
Public API Reference |
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 "csutil/parray.h" 00029 #include "csutil/array.h" 00030 00031 class csHashMapReversible; 00032 class csHashIteratorReversible; 00033 00034 class csHashMap; 00035 00037 typedef uint32 csHashKey; 00039 typedef void* csHashObject; 00040 00042 csHashKey csHashCompute(char const*); 00044 csHashKey csHashCompute(char const*, int length); 00045 00049 struct csHashElement 00050 { 00051 csHashKey key; 00052 csHashObject object; 00053 }; 00054 00056 typedef csArray<csHashElement> csHashBucket; 00058 typedef csArray<csHashBucket> csHashBucketVector; 00059 00068 class csGlobalHashIterator 00069 { 00070 friend class csHashMap; 00071 friend class csGlobalHashIteratorReversible; 00072 00073 private: 00075 csHashBucket* bucket; 00077 const csHashBucket* cbucket; 00079 int element_index; 00081 uint32 bucket_index; 00083 uint32 bucket_len; 00085 uint32 nbuckets; 00087 csHashMap* hash; 00089 const csHashMap* chash; 00090 00091 private: 00093 void GotoNextElement (); 00094 00096 void GotoNextElementConst (); 00097 00098 public: 00104 csGlobalHashIterator (csHashMap* hash); 00105 00109 csGlobalHashIterator (const csHashMap* hash); 00110 00112 bool HasNext () const; 00114 csHashObject Next (); 00116 const csHashObject NextConst (); 00121 void DeleteNext (); 00122 }; 00123 00132 class csHashIterator 00133 { 00134 friend class csHashMap; 00135 friend class csHashIteratorReversible; 00136 00137 private: 00139 csHashBucket* bucket; 00141 const csHashBucket* cbucket; 00143 int element_index; 00145 int current_index; 00147 uint32 bucket_index; 00149 csHashKey key; 00151 csHashMap* hash; 00153 const csHashMap* chash; 00154 00155 private: 00157 void GotoNextSameKey (); 00158 00160 void GotoNextSameKeyConst (); 00161 00162 public: 00168 csHashIterator (csHashMap* hash, csHashKey Key); 00169 00173 csHashIterator (const csHashMap* hash, csHashKey Key); 00174 00176 bool HasNext () const; 00178 csHashObject Next (); 00180 const csHashObject NextConst (); 00185 void DeleteNext (); 00186 }; 00187 00195 class csHashMap 00196 { 00197 friend class csHashIterator; 00198 friend class csGlobalHashIterator; 00199 friend class csHashMapReversible; 00200 00201 private: 00203 csHashBucketVector Buckets; 00205 uint32 NumBuckets; 00207 int hash_elements; 00208 00210 void ChangeBuckets (uint32 newsize); 00211 00215 void PutInternal (uint32 idx, csHashKey key, csHashObject object); 00216 00217 00219 static uint32 FindNextPrime (uint32 num); 00220 00221 public: 00222 static uint32 prime_table[]; 00223 00234 csHashMap (uint32 size = 53); 00235 00240 virtual ~csHashMap (); 00241 00247 void Put (csHashKey key, csHashObject object); 00248 00256 csHashObject Get (csHashKey key) const; 00257 00264 void Delete (csHashKey key, csHashObject object); 00265 00269 void DeleteAll (csHashKey key); 00270 00274 void DeleteAll (); 00275 00279 void DumpStats (); 00280 }; 00281 00287 class csHashSet 00288 { 00289 private: 00290 csHashMap map; 00291 00292 public: 00297 csHashSet (uint32 size = 211); 00298 00303 void Add (csHashObject object); 00304 00311 void AddNoTest (csHashObject object); 00312 00316 bool In (csHashObject object); 00317 00321 void DeleteAll (); 00322 00327 void Delete (csHashObject object); 00328 00330 inline csHashMap *GetHashMap () {return ↦} 00331 }; 00332 00333 #endif // __CS_HASHMAP_H__ 00334