CrystalSpace

Public API Reference

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

csutil/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 "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 
00040 typedef unsigned int csHashKey;
00042 typedef void* csHashObject;
00043 
00047 struct csHashElement
00048 {
00049   csHashKey key;
00050   csHashObject object;
00051 };
00052 
00054 typedef csArray<csHashElement> csHashBucket;
00056 typedef csArray<csHashBucket> csHashBucketVector;
00057 
00066 class CS_CSUTIL_EXPORT csGlobalHashIterator
00067 {
00068   friend class csHashMap;
00069   friend class csGlobalHashIteratorReversible;
00070 
00071 private:
00073   csHashBucket* bucket;
00075   const csHashBucket* cbucket;
00077   int element_index;
00079   unsigned int bucket_index;
00081   unsigned int bucket_len;
00083   unsigned int nbuckets;
00085   csHashMap* hash;
00087   const csHashMap* chash;
00088 
00089 private:
00091   void GotoNextElement ();
00092 
00094   void GotoNextElementConst ();
00095 
00096 public:
00102   csGlobalHashIterator (csHashMap* hash);
00103 
00107   csGlobalHashIterator (const csHashMap* hash);
00108 
00110   bool HasNext () const;
00112   csHashObject Next ();
00114   csHashObject NextConst ();
00119   void DeleteNext ();
00120 };
00121 
00130 class CS_CSUTIL_EXPORT csHashIterator
00131 {
00132   friend class csHashMap;
00133   friend class csHashIteratorReversible;
00134 
00135 private:
00137   csHashBucket* bucket;
00139   const csHashBucket* cbucket;
00141   int element_index;
00143   int current_index;
00145   unsigned int bucket_index;
00147   csHashKey key;
00149   csHashMap* hash;
00151   const csHashMap* chash;
00152 
00153 private:
00155   void GotoNextSameKey ();
00156 
00158   void GotoNextSameKeyConst ();
00159 
00160 public:
00166   csHashIterator (csHashMap* hash, csHashKey Key);
00167 
00171   csHashIterator (const csHashMap* hash, csHashKey Key);
00172 
00174   bool HasNext () const;
00176   csHashObject Next ();
00178   csHashObject NextConst ();
00183   void DeleteNext ();
00184 };
00185 
00193 class CS_CSUTIL_EXPORT csHashMap
00194 {
00195   friend class csHashIterator;
00196   friend class csGlobalHashIterator;
00197   friend class csHashMapReversible;
00198 
00199 private:
00201   csHashBucketVector Buckets;
00203   unsigned int NumBuckets;
00205   int hash_elements;
00206 
00208   void ChangeBuckets (unsigned int newsize);
00209 
00213   void PutInternal (unsigned int idx, csHashKey key, csHashObject object);
00214 
00215 
00217   static unsigned int FindNextPrime (unsigned int num);
00218 
00219 public:
00220   static unsigned int prime_table[];
00221 
00232   csHashMap (unsigned int size = 53);
00233 
00238   virtual ~csHashMap ();
00239 
00245   void Put (csHashKey key, csHashObject object);
00246 
00254   csHashObject Get (csHashKey key) const;
00255 
00262   void Delete (csHashKey key, csHashObject object);
00263 
00267   void DeleteAll (csHashKey key);
00268 
00272   void DeleteAll ();
00273 
00277   void DumpStats ();
00278 };
00279 
00285 class CS_CSUTIL_EXPORT csHashSet
00286 {
00287 private:
00288   csHashMap map;
00289 
00290 public:
00295   csHashSet (unsigned int size = 211);
00296 
00301   void Add (csHashObject object);
00302 
00309   void AddNoTest (csHashObject object);
00310 
00314   bool In (csHashObject object);
00315 
00319   void DeleteAll ();
00320 
00325   void Delete (csHashObject object);
00326 
00328   inline csHashMap *GetHashMap () {return &map;}
00329 };
00330 
00331 #endif // __CS_HASHMAP_H__
00332 

Generated for Crystal Space by doxygen 1.2.18