CrystalSpace

Public API Reference

Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class 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 CS_COMPILER_MSVC
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 
00039 #if (CS_PROCESSOR_SIZE == 32)
00040 # if (_MSC_VER >= 1300)
00041   /*
00042    * Silence VC7 64bit warning.
00043    */
00044   typedef unsigned int __w64 csHashKey;
00045 # else
00046 
00047   typedef unsigned int csHashKey;
00048 # endif
00049 #else
00050   /*
00051    * At some places, pointers are casted to csHashKey. Work around truncation
00052    * problems by forcing csHashKey to at least 64bit on 64bit machines.
00053    */
00054   typedef uint64 csHashKey;
00055 #endif
00056 
00057 typedef void* csHashObject;
00058 
00062 struct csHashElement
00063 {
00064   csHashKey key;
00065   csHashObject object;
00066 };
00067 
00069 typedef csArray<csHashElement> csHashBucket;
00071 typedef csArray<csHashBucket> csHashBucketVector;
00072 
00081 class CS_CSUTIL_EXPORT csGlobalHashIterator
00082 {
00083   friend class csHashMap;
00084   friend class csGlobalHashIteratorReversible;
00085 
00086 private:
00088   csHashBucket* bucket;
00090   const csHashBucket* cbucket;
00092   size_t element_index;
00094   size_t bucket_index;
00096   size_t bucket_len;
00098   size_t nbuckets;
00100   csHashMap* hash;
00102   const csHashMap* chash;
00103 
00104 private:
00106   void GotoNextElement ();
00107 
00109   void GotoNextElementConst ();
00110 
00111 public:
00117   csGlobalHashIterator (csHashMap* hash);
00118 
00122   csGlobalHashIterator (const csHashMap* hash);
00123 
00125   bool HasNext () const;
00127   csHashObject Next ();
00129   csHashObject NextConst ();
00134   void DeleteNext ();
00135 };
00136 
00145 class CS_CSUTIL_EXPORT csHashIterator
00146 {
00147   friend class csHashMap;
00148   friend class csHashIteratorReversible;
00149 
00150 private:
00152   csHashBucket* bucket;
00154   const csHashBucket* cbucket;
00156   size_t element_index;
00158   size_t current_index;
00160   size_t bucket_index;
00162   csHashKey key;
00164   csHashMap* hash;
00166   const csHashMap* chash;
00167 
00168 private:
00170   void GotoNextSameKey ();
00171 
00173   void GotoNextSameKeyConst ();
00174 
00175 public:
00181   csHashIterator (csHashMap* hash, csHashKey Key);
00182 
00186   csHashIterator (const csHashMap* hash, csHashKey Key);
00187 
00189   bool HasNext () const;
00191   csHashObject Next ();
00193   csHashObject NextConst ();
00198   void DeleteNext ();
00199 };
00200 
00208 class CS_CSUTIL_EXPORT csHashMap
00209 {
00210   friend class csHashIterator;
00211   friend class csGlobalHashIterator;
00212   friend class csHashMapReversible;
00213 
00214 private:
00216   csHashBucketVector Buckets;
00218   size_t NumBuckets;
00220   size_t hash_elements;
00221 
00223   void ChangeBuckets (size_t newsize);
00224 
00228   void PutInternal (size_t idx, csHashKey key, csHashObject object);
00229 
00230 
00232   static size_t FindNextPrime (size_t num);
00233 
00234 public:
00235   static size_t prime_table[];
00236 
00247   csHashMap (size_t size = 53);
00248 
00253   virtual ~csHashMap ();
00254 
00260   void Put (csHashKey key, csHashObject object);
00261 
00269   csHashObject Get (csHashKey key) const;
00270 
00277   void Delete (csHashKey key, csHashObject object);
00278 
00282   void DeleteAll (csHashKey key);
00283 
00287   void DeleteAll ();
00288 
00292   void DumpStats ();
00293 };
00294 
00300 class CS_CSUTIL_EXPORT csHashSet
00301 {
00302 private:
00303   csHashMap map;
00304 
00305 public:
00310   csHashSet (unsigned int size = 211);
00311 
00316   void Add (csHashObject object);
00317 
00324   void AddNoTest (csHashObject object);
00325 
00329   bool In (csHashObject object);
00330 
00334   void DeleteAll ();
00335 
00340   void Delete (csHashObject object);
00341 
00343   inline csHashMap *GetHashMap () {return &map;}
00344 };
00345 
00346 #endif // __CS_HASHMAP_H__
00347 

Generated for Crystal Space by doxygen 1.3.9.1