1 files changed, 193 insertions, 0 deletions
diff --git a/emulator/qtools/hash_table.h b/emulator/qtools/hash_table.h
new file mode 100644
index 0000000..45786ec
--- /dev/null
+++ b/emulator/qtools/hash_table.h
@@ -0,0 +1,193 @@
+// Copyright 2006 The Android Open Source Project
+
+#ifndef HASH_TABLE_H
+#define HASH_TABLE_H
+
+#include <string.h>
+#include <inttypes.h>
+
+template<class T>
+class HashTable {
+  public:
+    HashTable(int size, T default_value = T());
+    ~HashTable();
+
+    typedef struct entry {
+        entry    *next;
+        char     *key;
+        T        value;
+    } entry_type;
+
+    typedef T value_type;
+
+    void         Update(const char *key, T value);
+    T            Find(const char *key);
+    entry_type*  GetFirst();
+    entry_type*  GetNext();
+
+  private:
+    uint32_t     HashFunction(const char *key);
+
+    int          size_;
+    int          mask_;
+    T            default_value_;
+    entry_type   **table_;
+    int          num_entries_;
+    int          current_index_;
+    entry_type   *current_ptr_;
+};
+
+template<class T>
+HashTable<T>::HashTable(int size, T default_value)
+{
+    int pow2;
+
+    // Round up size to a power of two
+    for (pow2 = 2; pow2 < size; pow2 <<= 1)
+        ;    // empty body
+
+    size_ = pow2;
+    mask_ = pow2 - 1;
+    default_value_ = default_value;
+
+    // Allocate a table of pointers and initialize them all to NULL.
+    table_ = new entry_type*[size_];
+    for (int ii = 0; ii < size_; ++ii)
+        table_[ii] = NULL;
+    num_entries_ = 0;
+    current_index_ = 0;
+    current_ptr_ = NULL;
+}
+
+template<class T>
+HashTable<T>::~HashTable()
+{
+    for (int ii = 0; ii < size_; ++ii) {
+        entry_type *ptr, *next;
+
+        // Delete all the pointers in the chain at this table position.
+        // Save the next pointer before deleting each entry so that we
+        // don't dereference part of a deallocated object.
+        for (ptr = table_[ii]; ptr; ptr = next) {
+            next = ptr->next;
+            delete[] ptr->key;
+            delete ptr;
+        }
+    }
+    delete[] table_;
+}
+
+// Professor Daniel J. Bernstein's hash function.  See
+// http://www.partow.net/programming/hashfunctions/
+template<class T>
+uint32_t HashTable<T>::HashFunction(const char *key)
+{
+    uint32_t hash = 5381;
+
+    int len = strlen(key);
+    for(int ii = 0; ii < len; ++key, ++ii)
+        hash = ((hash << 5) + hash) + *key;
+
+    return hash;
+}
+
+template<class T>
+void HashTable<T>::Update(const char *key, T value)
+{
+    // Hash the key to get the table position
+    int len = strlen(key);
+    int pos = HashFunction(key) & mask_;
+
+    // Search the chain for a matching key
+    for (entry_type *ptr = table_[pos]; ptr; ptr = ptr->next) {
+        if (strcmp(ptr->key, key) == 0) {
+            ptr->value = value;
+            return;
+        }
+    }
+
+    // Create a new hash entry and fill in the values
+    entry_type *ptr = new entry_type;
+
+    // Copy the string
+    ptr->key = new char[len + 1];
+    strcpy(ptr->key, key);
+    ptr->value = value;
+
+    // Insert the new entry at the beginning of the list
+    ptr->next = table_[pos];
+    table_[pos] = ptr;
+    num_entries_ += 1;
+}
+
+template<class T>
+typename HashTable<T>::value_type HashTable<T>::Find(const char *key)
+{
+    // Hash the key to get the table position
+    int pos = HashFunction(key) & mask_;
+
+    // Search the chain for a matching key
+    for (entry_type *ptr = table_[pos]; ptr; ptr = ptr->next) {
+        if (strcmp(ptr->key, key) == 0)
+            return ptr->value;
+    }
+
+    // If we get here, then we didn't find the key
+    return default_value_;
+}
+
+template<class T>
+typename HashTable<T>::entry_type* HashTable<T>::GetFirst()
+{
+    // Find the first non-NULL table entry.
+    for (current_index_ = 0; current_index_ < size_; ++current_index_) {
+        if (table_[current_index_])
+            break;
+    }
+
+    // If there are no table entries, then return NULL.
+    if (current_index_ == size_)
+        return NULL;
+
+    // Remember and return the current element.
+    current_ptr_ = table_[current_index_];
+    return current_ptr_;
+}
+
+template<class T>
+typename HashTable<T>::entry_type* HashTable<T>::GetNext()
+{
+    // If we already iterated part way through the hash table, then continue
+    // to the next element.
+    if (current_ptr_) {
+        current_ptr_ = current_ptr_->next;
+
+        // If we are pointing to a valid element, then return it.
+        if (current_ptr_)
+            return current_ptr_;
+
+        // Otherwise, start searching at the next table index.
+        current_index_ += 1;
+    }
+
+    // Find the next non-NULL table entry.
+    for (; current_index_ < size_; ++current_index_) {
+        if (table_[current_index_])
+            break;
+    }
+
+    // If there are no more non-NULL table entries, then return NULL.
+    if (current_index_ == size_) {
+        // Reset the current index so that we will start over from the
+        // beginning on the next call to GetNext().
+        current_index_ = 0;
+        return NULL;
+    }
+
+    // Remember and return the current element.
+    current_ptr_ = table_[current_index_];
+    return current_ptr_;
+}
+
+
+#endif  // HASH_TABLE_H