CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound 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 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 &map;}
00331 };
00332 
00333 #endif // __CS_HASHMAP_H__
00334 

Generated for Crystal Space by doxygen 1.2.14