1 // Copyright 2006 The Android Open Source Project
2
3 #ifndef HASH_TABLE_H
4 #define HASH_TABLE_H
5
6 #include <string.h>
7 #include <inttypes.h>
8
9 template<class T>
10 class HashTable {
11 public:
12 HashTable(int size, T default_value = T());
13 ~HashTable();
14
15 typedef struct entry {
16 entry *next;
17 char *key;
18 T value;
19 } entry_type;
20
21 typedef T value_type;
22
23 void Update(const char *key, T value);
24 bool Remove(const char *key);
25 T Find(const char *key);
26 entry_type* GetFirst();
27 entry_type* GetNext();
28
29 private:
30 uint32_t HashFunction(const char *key);
31
32 int size_;
33 int mask_;
34 T default_value_;
35 entry_type **table_;
36 int num_entries_;
37 int current_index_;
38 entry_type *current_ptr_;
39 };
40
41 template<class T>
HashTable(int size,T default_value)42 HashTable<T>::HashTable(int size, T default_value)
43 {
44 int pow2;
45
46 // Round up size to a power of two
47 for (pow2 = 2; pow2 < size; pow2 <<= 1)
48 ; // empty body
49
50 size_ = pow2;
51 mask_ = pow2 - 1;
52 default_value_ = default_value;
53
54 // Allocate a table of pointers and initialize them all to NULL.
55 table_ = new entry_type*[size_];
56 for (int ii = 0; ii < size_; ++ii)
57 table_[ii] = NULL;
58 num_entries_ = 0;
59 current_index_ = 0;
60 current_ptr_ = NULL;
61 }
62
63 template<class T>
~HashTable()64 HashTable<T>::~HashTable()
65 {
66 for (int ii = 0; ii < size_; ++ii) {
67 entry_type *ptr, *next;
68
69 // Delete all the pointers in the chain at this table position.
70 // Save the next pointer before deleting each entry so that we
71 // don't dereference part of a deallocated object.
72 for (ptr = table_[ii]; ptr; ptr = next) {
73 next = ptr->next;
74 delete[] ptr->key;
75 delete ptr;
76 }
77 }
78 delete[] table_;
79 }
80
81 // Professor Daniel J. Bernstein's hash function. See
82 // http://www.partow.net/programming/hashfunctions/
83 template<class T>
HashFunction(const char * key)84 uint32_t HashTable<T>::HashFunction(const char *key)
85 {
86 uint32_t hash = 5381;
87
88 int len = strlen(key);
89 for(int ii = 0; ii < len; ++key, ++ii)
90 hash = ((hash << 5) + hash) + *key;
91
92 return hash;
93 }
94
95 template<class T>
Update(const char * key,T value)96 void HashTable<T>::Update(const char *key, T value)
97 {
98 // Hash the key to get the table position
99 int len = strlen(key);
100 int pos = HashFunction(key) & mask_;
101
102 // Search the chain for a matching key
103 for (entry_type *ptr = table_[pos]; ptr; ptr = ptr->next) {
104 if (strcmp(ptr->key, key) == 0) {
105 ptr->value = value;
106 return;
107 }
108 }
109
110 // Create a new hash entry and fill in the values
111 entry_type *ptr = new entry_type;
112
113 // Copy the string
114 ptr->key = new char[len + 1];
115 strcpy(ptr->key, key);
116 ptr->value = value;
117
118 // Insert the new entry at the beginning of the list
119 ptr->next = table_[pos];
120 table_[pos] = ptr;
121 num_entries_ += 1;
122 }
123
124 template<class T>
Remove(const char * key)125 bool HashTable<T>::Remove(const char *key)
126 {
127 // Hash the key to get the table position
128 int len = strlen(key);
129 int pos = HashFunction(key) & mask_;
130
131 // Search the chain for a matching key and keep track of the previous
132 // element in the chain.
133 entry_type *prev = NULL;
134 for (entry_type *ptr = table_[pos]; ptr; prev = ptr, ptr = ptr->next) {
135 if (strcmp(ptr->key, key) == 0) {
136 if (prev == NULL) {
137 table_[pos] = ptr->next;
138 } else {
139 prev->next = ptr->next;
140 }
141 delete ptr->key;
142 delete ptr;
143 return true;
144 }
145 }
146 return false;
147 }
148
149 template<class T>
Find(const char * key)150 typename HashTable<T>::value_type HashTable<T>::Find(const char *key)
151 {
152 // Hash the key to get the table position
153 int pos = HashFunction(key) & mask_;
154
155 // Search the chain for a matching key
156 for (entry_type *ptr = table_[pos]; ptr; ptr = ptr->next) {
157 if (strcmp(ptr->key, key) == 0)
158 return ptr->value;
159 }
160
161 // If we get here, then we didn't find the key
162 return default_value_;
163 }
164
165 template<class T>
GetFirst()166 typename HashTable<T>::entry_type* HashTable<T>::GetFirst()
167 {
168 // Find the first non-NULL table entry.
169 for (current_index_ = 0; current_index_ < size_; ++current_index_) {
170 if (table_[current_index_])
171 break;
172 }
173
174 // If there are no table entries, then return NULL.
175 if (current_index_ == size_)
176 return NULL;
177
178 // Remember and return the current element.
179 current_ptr_ = table_[current_index_];
180 return current_ptr_;
181 }
182
183 template<class T>
GetNext()184 typename HashTable<T>::entry_type* HashTable<T>::GetNext()
185 {
186 // If we already iterated part way through the hash table, then continue
187 // to the next element.
188 if (current_ptr_) {
189 current_ptr_ = current_ptr_->next;
190
191 // If we are pointing to a valid element, then return it.
192 if (current_ptr_)
193 return current_ptr_;
194
195 // Otherwise, start searching at the next table index.
196 current_index_ += 1;
197 }
198
199 // Find the next non-NULL table entry.
200 for (; current_index_ < size_; ++current_index_) {
201 if (table_[current_index_])
202 break;
203 }
204
205 // If there are no more non-NULL table entries, then return NULL.
206 if (current_index_ == size_) {
207 // Reset the current index so that we will start over from the
208 // beginning on the next call to GetNext().
209 current_index_ = 0;
210 return NULL;
211 }
212
213 // Remember and return the current element.
214 current_ptr_ = table_[current_index_];
215 return current_ptr_;
216 }
217
218
219 #endif // HASH_TABLE_H
220