![]() |
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 #include "csutil/parray.h" 00023 #include "csutil/array.h" 00024 00025 class csHashMapReversible; 00026 class csHashIteratorReversible; 00027 00028 class csHashMap; 00029 00031 typedef uint32 csHashKey; 00033 typedef void* csHashObject; 00034 00036 csHashKey csHashCompute(char const*); 00038 csHashKey csHashCompute(char const*, int length); 00039 00043 struct csHashElement 00044 { 00045 csHashKey key; 00046 csHashObject object; 00047 }; 00048 00050 typedef csArray<csHashElement> csHashBucket; 00052 typedef csArray<csHashBucket> csHashBucketVector; 00053 00062 class csGlobalHashIterator 00063 { 00064 friend class csHashMap; 00065 friend class csGlobalHashIteratorReversible; 00066 00067 private: 00069 csHashBucket* bucket; 00071 int element_index; 00073 uint32 bucket_index; 00075 uint32 bucket_len; 00077 uint32 nbuckets; 00079 csHashMap* hash; 00080 00081 private: 00083 void GotoNextElement (); 00084 00085 public: 00091 csGlobalHashIterator (csHashMap* hash); 00092 00094 bool HasNext (); 00096 csHashObject Next (); 00101 void DeleteNext (); 00102 }; 00103 00112 class csHashIterator 00113 { 00114 friend class csHashMap; 00115 friend class csHashIteratorReversible; 00116 00117 private: 00119 csHashBucket* bucket; 00121 int element_index; 00123 int current_index; 00125 uint32 bucket_index; 00127 csHashKey key; 00129 csHashMap* hash; 00130 00131 private: 00133 void GotoNextSameKey (); 00134 00135 public: 00141 csHashIterator (csHashMap* hash, csHashKey Key); 00142 00144 bool HasNext (); 00146 csHashObject Next (); 00151 void DeleteNext (); 00152 }; 00153 00160 class csHashMap 00161 { 00162 friend class csHashIterator; 00163 friend class csGlobalHashIterator; 00164 friend class csHashMapReversible; 00165 00166 private: 00168 csHashBucketVector Buckets; 00170 uint32 NumBuckets; 00172 int hash_elements; 00173 00175 void ChangeBuckets (uint32 newsize); 00176 00180 void PutInternal (uint32 idx, csHashKey key, csHashObject object); 00181 00182 00184 static uint32 FindLargerPrime (uint32 num); 00185 00186 public: 00187 static uint32 prime_table[]; 00188 00199 csHashMap (uint32 size = 53); 00200 00205 virtual ~csHashMap (); 00206 00212 void Put (csHashKey key, csHashObject object); 00213 00221 csHashObject Get (csHashKey key) const; 00222 00229 void Delete (csHashKey key, csHashObject object); 00230 00234 void DeleteAll (csHashKey key); 00235 00239 void DeleteAll (); 00240 00244 void DumpStats (); 00245 }; 00246 00252 class csHashSet 00253 { 00254 private: 00255 csHashMap map; 00256 00257 public: 00262 csHashSet (uint32 size = 211); 00263 00268 void Add (csHashObject object); 00269 00276 void AddNoTest (csHashObject object); 00277 00281 bool In (csHashObject object); 00282 00286 void DeleteAll (); 00287 00292 void Delete (csHashObject object); 00293 00295 inline csHashMap *GetHashMap () {return ↦} 00296 }; 00297 00298 #endif // __CS_HASHMAP_H__ 00299