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> 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> 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> 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> 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> 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> 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> 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> 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
