00001
00002
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
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 template<class K, class T>
00025 class hash_map {
00026 public:
00027 struct 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 {
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;
00056 size_type cur_size;
00057 size_type max_size;
00058 float max_load;
00059 float grow;
00060 const T default_value;
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
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
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
00100 void set_load(float m = 0.7, float g = 1.7) { max_load = m; grow = g; }
00101
00102
00103 size_type size() const { return cur_size; }
00104
00105
00106 size_type bucket_count() const { return max_size; }
00107
00108
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
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
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
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
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
00182 iterator end() const { return iterator(); }
00183
00184 };
00185
00186 #endif