major rewrite of hashlib::dict<>

1 files changed, 123 insertions, 196 deletions

diff --git a/kernel/hashlib.h b/kernel/hashlib.h
index 3164282f..a34d194f 100644
--- a/kernel/hashlib.h
+++ b/kernel/hashlib.h
@@ -140,8 +140,8 @@ struct hash_obj_ops {
 
 inline int hashtable_size(int min_size)
 {
-	static std::vector<int> primes = {
-		23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
+	static std::vector<int> zero_and_some_primes = {
+		0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
 		853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
 		12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
 		120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
@@ -151,13 +151,13 @@ inline int hashtable_size(int min_size)
 		121590311, 151987889, 189984863, 237481091, 296851369, 371064217
 	};
 
-	for (auto p : primes)
-		if (p > min_size) return p;
+	for (auto p : zero_and_some_primes)
+		if (p >= min_size) return p;
 
 	if (sizeof(int) == 4)
 		throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
 
-	for (auto p : primes)
+	for (auto p : zero_and_some_primes)
 		if (100129 * p > min_size) return 100129 * p;
 
 	throw std::length_error("hash table exceeded maximum size.");
@@ -168,49 +168,26 @@ class dict
 {
 	struct entry_t
 	{
-		int link;
 		std::pair<K, T> udata;
+		int next;
 
-		entry_t() : link(-1) { }
-		entry_t(const std::pair<K, T> &udata) : link(1), udata(udata) { }
-
-		bool is_free() const { return link < 0; }
-		int get_next() const { return (link > 0 ? link : -link) - 2; }
-		bool get_last() const { return get_next() == -1; }
-		void set_next_used(int next) { link = next + 2; }
-		void set_next_free(int next) { link = -(next + 2); }
+		entry_t() { }
+		entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) { }
 	};
 
 	std::vector<int> hashtable;
 	std::vector<entry_t> entries;
-	int free_list, counter, begin_n;
-	int begin_seek_count;
 	OPS ops;
 
-	void init()
-	{
-		free_list = -1;
-		counter = 0;
-		begin_n = -1;
-		begin_seek_count = 0;
-	}
-
-	void init_from(const dict<K, T, OPS> &other)
-	{
-		hashtable.clear();
-		entries.clear();
-
-		counter = other.size();
-		begin_n = counter - 1;
-		entries.reserve(counter);
-
-		for (auto &it : other)
-			entries.push_back(entry_t(it));
-
-		rehash();
+#if 0
+	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 mkhash(const K &key) const
+	int do_hash(const K &key) const
 	{
 		unsigned int hash = 0;
 		if (!hashtable.empty())
@@ -218,145 +195,108 @@ class dict
 		return hash;
 	}
 
-	void upd_begin_n(bool do_refree = true)
+	void do_rehash()
 	{
-		if (begin_n < -1) {
-			begin_n = -(begin_n+2);
-			while (begin_n >= 0 && entries[begin_n].is_free()) { begin_seek_count++; begin_n--; }
-			if (do_refree && begin_seek_count > int(entries.size() / 2)) refree();
+		hashtable.clear();
+		hashtable.resize(hashtable_size(entries.size() * hashtable_size_factor), -1);
+
+		for (int i = 0; i < int(entries.size()); i++) {
+			do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
+			int hash = do_hash(entries[i].udata.first);
+			entries[i].next = hashtable[hash];
+			hashtable[hash] = i;
 		}
 	}
 
-	void refree()
+	int do_erase(int index, int hash)
 	{
-		free_list = -1;
-		begin_n = -1;
+		do_assert(index < int(entries.size()));
+		if (hashtable.empty() || index < 0)
+			return 0;
 
-		int last_free = -1;
-		for (int i = 0; i < int(entries.size()); i++)
-			if (entries[i].is_free()) {
-				if (last_free != -1)
-					entries[last_free].set_next_free(i);
-				else
-					free_list = i;
-				last_free = i;
-			} else
-				begin_n = i;
-
-		if (last_free != -1)
-			entries[last_free].set_next_free(-1);
-
-		begin_seek_count = 0;
-	}
-
-	void rehash()
-	{
-		upd_begin_n(false);
-		entries.resize(begin_n + 1);
+		int k = hashtable[hash];
+		if (k == index) {
+			hashtable[hash] = entries[index].next;
+		} else {
+			while (entries[k].next != index) {
+				k = entries[k].next;
+				do_assert(0 <= k && k < int(entries.size()));
+			}
+			entries[k].next = entries[index].next;
+		}
 
-		free_list = -1;
-		begin_n = -1;
+		int back_idx = entries.size()-1;
 
-		hashtable.clear();
-		hashtable.resize(hashtable_size(entries.size() * hashtable_size_factor), -1);
+		if (index != back_idx)
+		{
+			int back_hash = do_hash(entries[back_idx].udata.first);
 
-		int last_free = -1;
-		for (int i = 0; i < int(entries.size()); i++)
-			if (entries[i].is_free()) {
-				if (last_free != -1)
-					entries[last_free].set_next_free(i);
-				else
-					free_list = i;
-				last_free = i;
+			k = hashtable[back_hash];
+			if (k == back_idx) {
+				hashtable[back_hash] = index;
 			} else {
-				int hash = mkhash(entries[i].udata.first);
-				entries[i].set_next_used(hashtable[hash]);
-				hashtable[hash] = i;
-				begin_n = i;
+				while (entries[k].next != back_idx) {
+					k = entries[k].next;
+					do_assert(0 <= k && k < int(entries.size()));
+				}
+				entries[k].next = index;
 			}
 
-		if (last_free != -1)
-			entries[last_free].set_next_free(-1);
+			entries[index] = std::move(entries[back_idx]);
+		}
 
-		begin_seek_count = 0;
+		entries.pop_back();
+
+		if (entries.empty())
+			hashtable.clear();
+
+		return 1;
 	}
 
-	int do_erase(const K &key, int hash)
+	int do_lookup(const K &key, int &hash) const
 	{
-		int last_index = -1;
-		int index = hashtable.empty() ? -1 : hashtable[hash];
-		while (1) {
-			if (index < 0)
-				return 0;
-			if (ops.cmp(entries[index].udata.first, key)) {
-				if (last_index < 0)
-					hashtable[hash] = entries[index].get_next();
-				else
-					entries[last_index].set_next_used(entries[index].get_next());
-				entries[index].udata = std::pair<K, T>();
-				entries[index].set_next_free(free_list);
-				free_list = index;
-				if (--counter == 0)
-					clear();
-				else if (index == begin_n)
-					begin_n = -(begin_n+2);
-				return 1;
-			}
-			last_index = index;
-			index = entries[index].get_next();
+		if (hashtable.empty())
+			return -1;
+
+		if (entries.size() * hashtable_size_trigger > hashtable.size()) {
+			((dict*)this)->do_rehash();
+			hash = do_hash(key);
 		}
-	}
 
-	int lookup_index(const K &key, int hash) const
-	{
-		int index = hashtable.empty() ? -1 : hashtable[hash];
-		while (1) {
-			if (index < 0)
-				return -1;
-			if (ops.cmp(entries[index].udata.first, key))
-				return index;
-			index = entries[index].get_next();
+		int index = hashtable[hash];
+
+		while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
+			index = entries[index].next;
+			do_assert(-1 <= index && index < int(entries.size()));
 		}
+
+		return index;
 	}
 
-	int insert_at(const std::pair<K, T> &value, int hash)
+	int do_insert(const std::pair<K, T> &value, int &hash)
 	{
-		if (free_list < 0)
-		{
-			free_list = entries.size();
-			entries.push_back(entry_t());
-
-			if (entries.size() * hashtable_size_trigger > hashtable.size()) {
-				int i = free_list;
-				entries[i].udata = value;
-				entries[i].set_next_used(0);
-				begin_n = i;
-				counter++;
-				rehash();
-				return i;
-			}
+		if (hashtable.empty()) {
+			entries.push_back(entry_t(value, -1));
+			do_rehash();
+			hash = do_hash(value.first);
+		} else {
+			entries.push_back(entry_t(value, hashtable[hash]));
+			hashtable[hash] = entries.size() - 1;
 		}
-
-		int i = free_list;
-		free_list = entries[i].get_next();
-		entries[i].udata = value;
-		entries[i].set_next_used(hashtable[hash]);
-		hashtable[hash] = i;
-		if ((begin_n < -1 && -(begin_n+2) <= i) || (begin_n >= -1 && begin_n <= i))
-			begin_n = i;
-		counter++;
-		return i;
+		return entries.size() - 1;
 	}
 
 public:
 	class iterator
 	{
+		friend dict<K, T, OPS>;
+	protected:
 		dict<K, T, OPS> *ptr;
 		int index;
 	public:
 		iterator() { }
 		iterator(dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
-		iterator operator++() { do index--; while (index >= 0 && ptr->entries[index].is_free()); return *this; }
+		iterator operator++() { index--; return *this; }
 		bool operator==(const iterator &other) const { return index == other.index; }
 		bool operator!=(const iterator &other) const { return index != other.index; }
 		std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
@@ -367,12 +307,14 @@ public:
 
 	class const_iterator
 	{
+		friend dict<K, T, OPS>;
+	protected:
 		const dict<K, T, OPS> *ptr;
 		int index;
 	public:
 		const_iterator() { }
 		const_iterator(const dict<K, T, OPS> *ptr, int index) : ptr(ptr), index(index) { }
-		const_iterator operator++() { do index--; while (index >= 0 && ptr->entries[index].is_free()); return *this; }
+		const_iterator operator++() { index--; return *this; }
 		bool operator==(const const_iterator &other) const { return index == other.index; }
 		bool operator!=(const const_iterator &other) const { return index != other.index; }
 		const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
@@ -381,23 +323,22 @@ public:
 
 	dict()
 	{
-		init();
 	}
 
 	dict(const dict<K, T, OPS> &other)
 	{
-		init_from(other);
+		entries = other.entries;
+		do_rehash();
 	}
 
 	dict(dict<K, T, OPS> &&other)
 	{
-		init();
 		swap(other);
 	}
 
 	dict<K, T, OPS> &operator=(const dict<K, T, OPS> &other) {
-		if (this != &other)
-			init_from(other);
+		entries = other.entries;
+		do_rehash();
 		return *this;
 	}
 
@@ -409,7 +350,6 @@ public:
 
 	dict(const std::initializer_list<std::pair<K, T>> &list)
 	{
-		init();
 		for (auto &it : list)
 			insert(it);
 	}
@@ -417,7 +357,6 @@ public:
 	template<class InputIterator>
 	dict(InputIterator first, InputIterator last)
 	{
-		init();
 		insert(first, last);
 	}
 
@@ -430,38 +369,39 @@ public:
 
 	std::pair<iterator, bool> insert(const std::pair<K, T> &value)
 	{
-		int hash = mkhash(value.first);
-		int i = lookup_index(value.first, hash);
+		int hash = do_hash(value.first);
+		int i = do_lookup(value.first, hash);
 		if (i >= 0)
 			return std::pair<iterator, bool>(iterator(this, i), false);
-		i = insert_at(value, hash);
+		i = do_insert(value, hash);
 		return std::pair<iterator, bool>(iterator(this, i), true);
 	}
 
 	int erase(const K &key)
 	{
-		int hash = mkhash(key);
-		return do_erase(key, hash);
+		int hash = do_hash(key);
+		int index = do_lookup(key, hash);
+		return do_erase(index, hash);
 	}
 
 	iterator erase(iterator it)
 	{
-		int hash = mkhash(it->first);
-		do_erase(it->first, hash);
+		int hash = do_hash(it->first);
+		do_erase(it.index, hash);
 		return ++it;
 	}
 
 	int count(const K &key) const
 	{
-		int hash = mkhash(key);
-		int i = lookup_index(key, hash);
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
 		return i < 0 ? 0 : 1;
 	}
 
 	iterator find(const K &key)
 	{
-		int hash = mkhash(key);
-		int i = lookup_index(key, hash);
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
 		if (i < 0)
 			return end();
 		return iterator(this, i);
@@ -469,8 +409,8 @@ public:
 
 	const_iterator find(const K &key) const
 	{
-		int hash = mkhash(key);
-		int i = lookup_index(key, hash);
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
 		if (i < 0)
 			return end();
 		return const_iterator(this, i);
@@ -478,8 +418,8 @@ public:
 
 	T& at(const K &key)
 	{
-		int hash = mkhash(key);
-		int i = lookup_index(key, hash);
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
 		if (i < 0)
 			throw std::out_of_range("dict::at()");
 		return entries[i].udata.second;
@@ -487,8 +427,8 @@ public:
 
 	const T& at(const K &key) const
 	{
-		int hash = mkhash(key);
-		int i = lookup_index(key, hash);
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
 		if (i < 0)
 			throw std::out_of_range("dict::at()");
 		return entries[i].udata.second;
@@ -496,10 +436,10 @@ public:
 
 	T& operator[](const K &key)
 	{
-		int hash = mkhash(key);
-		int i = lookup_index(key, hash);
+		int hash = do_hash(key);
+		int i = do_lookup(key, hash);
 		if (i < 0)
-			i = insert_at(std::pair<K, T>(key, T()), hash);
+			i = do_insert(std::pair<K, T>(key, T()), hash);
 		return entries[i].udata.second;
 	}
 
@@ -507,29 +447,16 @@ public:
 	{
 		hashtable.swap(other.hashtable);
 		entries.swap(other.entries);
-		std::swap(free_list, other.free_list);
-		std::swap(counter, other.counter);
-		std::swap(begin_n, other.begin_n);
-		std::swap(begin_seek_count, other.begin_seek_count);
 	}
 
 	bool operator==(const dict<K, T, OPS> &other) const {
-		if (counter != other.counter)
+		if (size() != other.size())
 			return false;
-		if (counter == 0)
-			return true;
-		if (entries.size() < other.entries.size())
-			for (auto &it : *this) {
-				auto oit = other.find(it.first);
-				if (oit == other.end() || oit->second != it.second)
-					return false;
-			}
-		else
-			for (auto &oit : other) {
-				auto it = find(oit.first);
-				if (it == end() || it->second != oit.second)
-					return false;
-			}
+		for (auto &it : entries) {
+			auto oit = other.find(it.udata.first);
+			if (oit == other.end() || oit->second != it.udata.second)
+				return false;
+		}
 		return true;
 	}
 
@@ -537,14 +464,14 @@ public:
 		return !(*this == other);
 	}
 
-	size_t size() const { return counter; }
-	bool empty() const { return counter == 0; }
-	void clear() { hashtable.clear(); entries.clear(); init(); }
+	size_t size() const { return entries.size(); }
+	bool empty() const { return entries.empty(); }
+	void clear() { hashtable.clear(); entries.clear(); }
 
-	iterator begin() { upd_begin_n(); return iterator(this, begin_n); }
+	iterator begin() { return iterator(this, int(entries.size())-1); }
 	iterator end() { return iterator(nullptr, -1); }
 
-	const_iterator begin() const { ((dict*)this)->upd_begin_n(); return const_iterator(this, begin_n); }
+	const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
 	const_iterator end() const { return const_iterator(nullptr, -1); }
 };