Add a basic hashtable data structure, with tests!
The basic hashtable is intended to be used to support a variety
of different datastructures such as map, set, multimap,
multiset, linkedmap, generationcache, etc.
Consequently its interface is fairly primitive.
The basic hashtable supports copy-on-write style functionality
using SharedBuffer.
The change introduces a simple generic function in TypeHelpers for
specifying hash functions. The idea is to add template
specializations of hash_type<T> next to the relevant data structures
such as String8, String16, sp<T>, etc.
Change-Id: I2c479229e9d4527b4fbfe3b8b04776a2fd32c973
diff --git a/include/utils/TypeHelpers.h b/include/utils/TypeHelpers.h
index a1663f3..7538817 100644
--- a/include/utils/TypeHelpers.h
+++ b/include/utils/TypeHelpers.h
@@ -213,6 +213,9 @@
template <typename KEY, typename VALUE>
struct key_value_pair_t {
+ typedef KEY key_t;
+ typedef VALUE value_t;
+
KEY key;
VALUE value;
key_value_pair_t() { }
@@ -222,6 +225,12 @@
inline bool operator < (const key_value_pair_t& o) const {
return strictly_order_type(key, o.key);
}
+ inline const KEY& getKey() const {
+ return key;
+ }
+ inline const VALUE& getValue() const {
+ return value;
+ }
};
template<>
@@ -243,6 +252,41 @@
// ---------------------------------------------------------------------------
+/*
+ * Hash codes.
+ */
+typedef uint32_t hash_t;
+
+template <typename TKey>
+hash_t hash_type(const TKey& key);
+
+/* Built-in hash code specializations.
+ * Assumes pointers are 32bit. */
+#define ANDROID_INT32_HASH(T) \
+ template <> inline hash_t hash_type(const T& value) { return hash_t(value); }
+#define ANDROID_INT64_HASH(T) \
+ template <> inline hash_t hash_type(const T& value) { \
+ return hash_t((value >> 32) ^ value); }
+#define ANDROID_REINTERPRET_HASH(T, R) \
+ template <> inline hash_t hash_type(const T& value) { \
+ return hash_type(*reinterpret_cast<const R*>(&value)); }
+
+ANDROID_INT32_HASH(bool)
+ANDROID_INT32_HASH(char)
+ANDROID_INT32_HASH(unsigned char)
+ANDROID_INT32_HASH(short)
+ANDROID_INT32_HASH(unsigned short)
+ANDROID_INT32_HASH(int)
+ANDROID_INT32_HASH(unsigned int)
+ANDROID_INT64_HASH(long)
+ANDROID_INT64_HASH(unsigned long)
+ANDROID_REINTERPRET_HASH(float, uint32_t)
+ANDROID_REINTERPRET_HASH(double, uint64_t)
+
+template <typename T> inline hash_t hash_type(const T*& value) {
+ return hash_type(uintptr_t(value));
+}
+
}; // namespace android
// ---------------------------------------------------------------------------