hash_map.icc

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 // $Id:$
00003 // ---------------------------------------------------------------------------
00004 
00005 #ifndef HEP_HASH_MAP_SRC
00006 #define HEP_HASH_MAP_SRC
00007 
00008 #include <string.h>
00009 #include <utility>
00010 #include "CLHEP/Evaluator/string.icc"
00011 
00012 /*
00013  * Simplified hash_map class.
00014  * It provides only basic functions of the standard <hash_map> and
00015  * is intended to be used as a replacement of the standard class where
00016  * full functionality of <hash_map> is not required, but it is essential
00017  * to have highly portable and effective code.
00018  *
00019  * This file should be used exclusively inside *.cc files.
00020  * Usage inside header files can result to a clash with standard <hash_map>.
00021  *
00022  * @author Evgeni Chernyaev  <Evgueni.Tcherniaev@cern.ch>
00023  */
00024 template<class K, class T>
00025 class hash_map {
00026 public:
00027   struct Entry {            // Hash_map entry   
00028     std::pair<const K,T> data;
00029     Entry* next;
00030     Entry(K k, T v, Entry* n) : data(k,v), next(n) {}
00031   };
00032 
00033   class hash_map_iterator { // Hash_map iterator
00034     Entry* entry;
00035   public: 
00036     hash_map_iterator() : entry(0) {}
00037     hash_map_iterator(Entry & e) : entry(&e) {} 
00038     std::pair<const K,T> & operator * () const { return entry->data; }
00039     std::pair<const K,T> * operator ->() const { return &(operator*()); }
00040     bool operator==(hash_map_iterator i) const {
00041       return (entry == i.entry);
00042     }
00043     bool operator!=(hash_map_iterator i) const {
00044       return (entry != i.entry);
00045     }
00046   };
00047 
00048 public:
00049   typedef unsigned int            size_type;
00050   typedef std::pair<const K,T> value_type;
00051   typedef hash_map_iterator       iterator;
00052   typedef hash_map_iterator       const_iterator;
00053 
00054 private:
00055   Entry**   table;          // Hash table: pointers to entries
00056   size_type cur_size;       // Number of entries
00057   size_type max_size;       // Bucket_count - current size of the table
00058   float     max_load;       // Keep (n) <= (max_size * max_load)
00059   float     grow;           // When necessary, resize(max_size * grow)
00060   const T   default_value;  // Default value used by []
00061 
00062   size_type hash(const char * key) const {
00063     size_type res = 0;
00064     while(*key) { res = res*31 + *key++; }
00065     return res;
00066   }
00067 
00068   size_type hash(const string & key) const {
00069     return hash(key.c_str());
00070   }
00071 
00072   bool eq(const char * a, const char * b) const {
00073     return (strcmp(a, b) == 0);
00074   }
00075 
00076   bool eq(const string & a, const string & b) const {
00077     return (a == b);
00078   }
00079 
00080 public:
00081 
00082   // Constructor.
00083   hash_map(const T & dv = T(), size_type n = 107)
00084     : table(0), cur_size(0), max_size(0), default_value(dv)
00085   {
00086     set_load();
00087     resize(n);
00088   }
00089 
00090   // Destructor.
00091   ~hash_map() {
00092     for(size_type i=0; i<max_size; i++) {
00093       Entry* n = table[i];
00094       while(n) { Entry* p = n; n = p->next; delete p; }
00095     }
00096     delete [] table;
00097   }    
00098 
00099   // Sets load and grow parameters.
00100   void set_load(float m = 0.7, float g = 1.7) { max_load = m; grow = g; } 
00101 
00102   // Returns number of elements.
00103   size_type size() const { return cur_size; }
00104 
00105   // Returns size of the hash table.
00106   size_type bucket_count() const { return max_size; }
00107 
00108   // Resizes the hash table.
00109   void resize(size_type s) {
00110     if (s <= max_size) return;
00111     Entry** tmp = table;
00112     table = new Entry* [s];
00113     for (size_type k=0; k<s; k++) table[k] = 0;
00114     for (size_type i=0; i<max_size; i++) {
00115       Entry* n = tmp[i];
00116       while(n) {
00117         Entry* p = n;
00118         n = p->next;
00119         size_type ii = hash(p->data.first) % s;
00120         p->next = table[ii];
00121         table[ii] = p;
00122       }
00123     }
00124     max_size = s;
00125     delete [] tmp;
00126   }
00127 
00128   // Subscripting.
00129   T & operator[](const K & key) {
00130     size_type i = hash(key) % max_size;
00131     for (Entry* p=table[hash(key) % max_size]; p; p=p->next) {
00132       if (eq(key,p->data.first)) return p->data.second;
00133     }
00134     if (cur_size++ >= max_size*max_load) {
00135       resize(size_type(max_size*grow));
00136       i = hash(key) % max_size;
00137     }
00138     table[i] = new Entry(key, default_value, table[i]);
00139     return table[i]->data.second;
00140   }
00141 
00142   // Finds element with given key.  
00143   iterator find(const K & key) const {
00144     size_type i = hash(key) % max_size;
00145     for (Entry* p=table[i]; p; p=p->next) {
00146       if (eq(key,p->data.first)) return iterator(*p);
00147     }
00148     return end();
00149   }
00150 
00151   // Erases element with given key.
00152   size_type erase(const K & key) {
00153     size_type i = hash(key) % max_size;
00154     Entry* p = table[i];
00155     if (p == 0) return 0;
00156     if (eq(key,p->data.first)) {
00157       table[i] = p->next; delete p; cur_size--; return 1;
00158     }
00159     Entry** pp = &table[i];
00160     for (p=p->next; p; p=p->next) {
00161       if (eq(key,p->data.first)) {
00162         *pp = p->next; delete p; cur_size--; return 1;
00163       }else{
00164         pp = &(p->next);
00165       }
00166     }
00167     return 0;
00168   }
00169 
00170   // Clears the hash table.
00171   void clear() {
00172     for(size_type i=0; i<max_size; i++) {
00173       for (Entry* p=table[i]; p;) {
00174         Entry* pp = p; p = p->next; delete pp;
00175       }
00176     table[i] = 0;
00177     }
00178     cur_size = 0;
00179   }
00180 
00181   // Returns end iterator.
00182   iterator end() const { return iterator(); }
00183 
00184 };
00185 
00186 #endif /* HEP_HASH_MAP_SRC */

Generated on Mon May 27 17:50:31 2013 for Geant4 by  doxygen 1.4.7