CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

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 #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 &map;}
00296 };
00297 
00298 #endif // __CS_HASHMAP_H__
00299 

Generated for Crystal Space by doxygen 1.2.14