Geant4  10.00.p01
hash_map.icc
Go to the documentation of this file.
1 // -*- C++ -*-
2 // $Id:$
3 // ---------------------------------------------------------------------------
4 
5 #ifndef HEP_HASH_MAP_SRC
6 #define HEP_HASH_MAP_SRC
7 
8 #include <string.h>
9 #include <utility>
10 #include "CLHEP/Evaluator/string.icc"
11 
12 /*
13  * Simplified hash_map class.
14  * It provides only basic functions of the standard <hash_map> and
15  * is intended to be used as a replacement of the standard class where
16  * full functionality of <hash_map> is not required, but it is essential
17  * to have highly portable and effective code.
18  *
19  * This file should be used exclusively inside *.cc files.
20  * Usage inside header files can result to a clash with standard <hash_map>.
21  *
22  * @author Evgeni Chernyaev <Evgueni.Tcherniaev@cern.ch>
23  */
24 template<class K, class T>
25 class hash_map {
26 public:
27  struct Entry { // Hash_map entry
28  std::pair<const K,T> data;
29  Entry* next;
30  Entry(K k, T v, Entry* n) : data(k,v), next(n) {}
31  };
32 
33  class hash_map_iterator { // Hash_map iterator
34  Entry* entry;
35  public:
36  hash_map_iterator() : entry(0) {}
37  hash_map_iterator(Entry & e) : entry(&e) {}
38  std::pair<const K,T> & operator * () const { return entry->data; }
39  std::pair<const K,T> * operator ->() const { return &(operator*()); }
40  bool operator==(hash_map_iterator i) const {
41  return (entry == i.entry);
42  }
43  bool operator!=(hash_map_iterator i) const {
44  return (entry != i.entry);
45  }
46  };
47 
48 public:
49  typedef unsigned int size_type;
50  typedef std::pair<const K,T> value_type;
51  typedef hash_map_iterator iterator;
52  typedef hash_map_iterator const_iterator;
53 
54 private:
55  Entry** table; // Hash table: pointers to entries
56  size_type cur_size; // Number of entries
57  size_type max_size; // Bucket_count - current size of the table
58  float max_load; // Keep (n) <= (max_size * max_load)
59  float grow; // When necessary, resize(max_size * grow)
60  const T default_value; // Default value used by []
61 
62  size_type hash(const char * key) const {
63  size_type res = 0;
64  while(*key) { res = res*31 + *key++; }
65  return res;
66  }
67 
68  size_type hash(const string & key) const {
69  return hash(key.c_str());
70  }
71 
72  bool eq(const char * a, const char * b) const {
73  return (strcmp(a, b) == 0);
74  }
75 
76  bool eq(const string & a, const string & b) const {
77  return (a == b);
78  }
79 
80 public:
81 
82  // Constructor.
83  hash_map(const T & dv = T(), size_type n = 107)
84  : table(0), cur_size(0), max_size(0), default_value(dv)
85  {
86  set_load();
87  resize(n);
88  }
89 
90  // Destructor.
91  ~hash_map() {
92  for(size_type i=0; i<max_size; i++) {
93  Entry* n = table[i];
94  while(n) { Entry* p = n; n = p->next; delete p; }
95  }
96  delete [] table;
97  }
98 
99  // Sets load and grow parameters.
100  void set_load(float m = 0.7, float g = 1.7) { max_load = m; grow = g; }
101 
102  // Returns number of elements.
103  size_type size() const { return cur_size; }
104 
105  // Returns size of the hash table.
106  size_type bucket_count() const { return max_size; }
107 
108  // Resizes the hash table.
109  void resize(size_type s) {
110  if (s <= max_size) return;
111  Entry** tmp = table;
112  table = new Entry* [s];
113  for (size_type k=0; k<s; k++) table[k] = 0;
114  for (size_type i=0; i<max_size; i++) {
115  Entry* n = tmp[i];
116  while(n) {
117  Entry* p = n;
118  n = p->next;
119  size_type ii = hash(p->data.first) % s;
120  p->next = table[ii];
121  table[ii] = p;
122  }
123  }
124  max_size = s;
125  delete [] tmp;
126  }
127 
128  // Subscripting.
129  T & operator[](const K & key) {
130  size_type i = hash(key) % max_size;
131  for (Entry* p=table[hash(key) % max_size]; p; p=p->next) {
132  if (eq(key,p->data.first)) return p->data.second;
133  }
134  if (cur_size++ >= max_size*max_load) {
135  resize(size_type(max_size*grow));
136  i = hash(key) % max_size;
137  }
138  table[i] = new Entry(key, default_value, table[i]);
139  return table[i]->data.second;
140  }
141 
142  // Finds element with given key.
143  iterator find(const K & key) const {
144  size_type i = hash(key) % max_size;
145  for (Entry* p=table[i]; p; p=p->next) {
146  if (eq(key,p->data.first)) return iterator(*p);
147  }
148  return end();
149  }
150 
151  // Erases element with given key.
152  size_type erase(const K & key) {
153  size_type i = hash(key) % max_size;
154  Entry* p = table[i];
155  if (p == 0) return 0;
156  if (eq(key,p->data.first)) {
157  table[i] = p->next; delete p; cur_size--; return 1;
158  }
159  Entry** pp = &table[i];
160  for (p=p->next; p; p=p->next) {
161  if (eq(key,p->data.first)) {
162  *pp = p->next; delete p; cur_size--; return 1;
163  }else{
164  pp = &(p->next);
165  }
166  }
167  return 0;
168  }
169 
170  // Clears the hash table.
171  void clear() {
172  for(size_type i=0; i<max_size; i++) {
173  for (Entry* p=table[i]; p;) {
174  Entry* pp = p; p = p->next; delete pp;
175  }
176  table[i] = 0;
177  }
178  cur_size = 0;
179  }
180 
181  // Returns end iterator.
182  iterator end() const { return iterator(); }
183 
184 };
185 
186 #endif /* HEP_HASH_MAP_SRC */