From adf4ecbc1f571d26bed2b1c264c38a5f3c25e9b4 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Mon, 9 Feb 2015 20:11:51 +0100
Subject: Some hashlib improvements

---
 kernel/hashlib.h | 46 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 37 insertions(+), 9 deletions(-)

(limited to 'kernel/hashlib.h')

diff --git a/kernel/hashlib.h b/kernel/hashlib.h
index c96023920..94b573e47 100644
--- a/kernel/hashlib.h
+++ b/kernel/hashlib.h
@@ -178,18 +178,19 @@ class dict
 
 		entry_t() { }
 		entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) { }
+		entry_t(std::pair<K, T> &&udata, int next) : udata(std::move(udata)), next(next) { }
 	};
 
 	std::vector<int> hashtable;
 	std::vector<entry_t> entries;
 	OPS ops;
 
-#if 0
+#ifdef NDEBUG
+	static inline void do_assert(bool) { }
+#else
 	static inline void do_assert(bool cond) {
 		if (!cond) throw std::runtime_error("dict<> assert failed.");
 	}
-#else
-	static inline void do_assert(bool) { }
 #endif
 
 	int do_hash(const K &key) const
@@ -220,6 +221,8 @@ class dict
 			return 0;
 
 		int k = hashtable[hash];
+		do_assert(0 <= k && k < int(entries.size()));
+
 		if (k == index) {
 			hashtable[hash] = entries[index].next;
 		} else {
@@ -237,6 +240,8 @@ class dict
 			int back_hash = do_hash(entries[back_idx].udata.first);
 
 			k = hashtable[back_hash];
+			do_assert(0 <= k && k < int(entries.size()));
+
 			if (k == back_idx) {
 				hashtable[back_hash] = index;
 			} else {
@@ -278,6 +283,19 @@ class dict
 		return index;
 	}
 
+	int do_insert(const K &key, int &hash)
+	{
+		if (hashtable.empty()) {
+			entries.push_back(entry_t(std::pair<K, T>(key, T()), -1));
+			do_rehash();
+			hash = do_hash(key);
+		} else {
+			entries.push_back(entry_t(std::pair<K, T>(key, T()), hashtable[hash]));
+			hashtable[hash] = entries.size() - 1;
+		}
+		return entries.size() - 1;
+	}
+
 	int do_insert(const std::pair<K, T> &value, int &hash)
 	{
 		if (hashtable.empty()) {
@@ -375,6 +393,16 @@ public:
 			insert(*first);
 	}
 
+	std::pair<iterator, bool> insert(const K &key)
+	{
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
+		if (i >= 0)
+			return std::pair<iterator, bool>(iterator(this, i), false);
+		i = do_insert(key, hash);
+		return std::pair<iterator, bool>(iterator(this, i), true);
+	}
+
 	std::pair<iterator, bool> insert(const std::pair<K, T> &value)
 	{
 		int hash = do_hash(value.first);
@@ -476,14 +504,14 @@ public:
 			return false;
 		for (auto &it : entries) {
 			auto oit = other.find(it.udata.first);
-			if (oit == other.end() || oit->second != it.udata.second)
+			if (oit == other.end() || !(oit->second == it.udata.second))
 				return false;
 		}
 		return true;
 	}
 
 	bool operator!=(const dict &other) const {
-		return !(*this == other);
+		return !operator==(other);
 	}
 
 	size_t size() const { return entries.size(); }
@@ -516,12 +544,12 @@ protected:
 	std::vector<entry_t> entries;
 	OPS ops;
 
-#if 0
+#ifdef NDEBUG
+	static inline void do_assert(bool) { }
+#else
 	static inline void do_assert(bool cond) {
 		if (!cond) throw std::runtime_error("pool<> assert failed.");
 	}
-#else
-	static inline void do_assert(bool) { }
 #endif
 
 	int do_hash(const K &key) const
@@ -791,7 +819,7 @@ public:
 	}
 
 	bool operator!=(const pool &other) const {
-		return !(*this == other);
+		return !operator==(other);
 	}
 
 	size_t size() const { return entries.size(); }
-- 
cgit v1.2.3