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