1 files changed, 158 insertions, 0 deletions
diff --git a/hashmap.hpp b/hashmap.hpp
new file mode 100644
index 0000000..952bf86
--- /dev/null
+++ b/hashmap.hpp
@@ -0,0 +1,158 @@
+#ifndef hashmap_hpp
+#define hashmap_hpp
+
+extern "C" {
+#include "plat.h"
+}
+
+#include <tuple>
+#include <stddef.h>
+
+template <typename T>
+struct Hash_Function {};
+
+template <typename Key, typename Value, int size>
+struct Hash_Map {
+	enum {
+		flags_tombstone = 1 << 0,
+		flags_null      = 1 << 1
+	};
+
+	Key keys[size];
+	Value values[size];
+	uint8_t flags[size];
+
+	void init() {
+		int i;
+		for (i = 0; i < size; i++) flags[i] = flags_null;
+	}
+
+	int find(const Key& to_find) const {
+		int tombstone = -1, i;
+		int bucket = (int)(Hash_Function<Key>{}(to_find) % (size_t)size);
+		for (i = 0; i < size; i++) {
+			const Key& k = keys[bucket];
+			uint8_t flag = flags[bucket];
+			if (flag & flags_null) {
+				if (flag & flags_tombstone) {
+					if (tombstone < 0) tombstone = bucket;
+				} else return tombstone >= 0? tombstone: bucket;
+			} else if (k == to_find) return bucket;
+			bucket = (bucket + 1) % size;
+		}
+		if (tombstone >= 0) return tombstone;
+		return -1;
+	}
+
+	Value& set(const Key& k, const Value& v) {
+		int bucket = find(k);
+		assert(bucket >= 0); /* full */
+		flags[bucket] = 0;
+		keys[bucket] = k;
+		values[bucket] = v;
+		return values[bucket];
+	}
+
+	Value* get(const Key& k) {
+		int bucket = find(k);
+		if (bucket < 0 || flags[bucket] & flags_null) return 0;
+		return &values[bucket];
+	}
+
+	Value& operator[](const Key& k) {
+		int bucket = find(k);
+		assert(bucket >= 0);
+		return values[bucket];
+	}
+
+	const Value& operator[](const Key& k) const {
+		int bucket = find(k);
+		assert(bucket >= 0);
+		return values[bucket];
+	}
+
+	Key* kaddr(const Key& k) {
+		int bucket = find(k);
+		if (bucket < 0 || flags[bucket] & flags_null) return 0;
+		return &keys[bucket];
+	}
+
+	void remove(const Key& k) {
+		int bucket = find(k);
+		assert(bucket >= 0);
+		flags[bucket] = flags_null | flags_tombstone;
+	}
+
+	int has(const Key& k) {
+		int bucket = find(k);
+		return bucket >= 0 && ~flags[bucket] & flags_null;
+	}
+
+	template <typename Table>
+	struct iterator {
+		Table* table;
+		int bucket;
+
+		void init_begin(Table* t) {
+			bucket = 0;
+			table = t;
+			while (
+				bucket < size &&
+				table->flags[bucket] & flags_null
+			) bucket++;
+		}
+		void init_end(Table* t) {
+			bucket = size;
+			table = t;
+		}
+		bool equals(const iterator<Table>& other) {
+			return bucket == other.bucket && table == other.table;
+		}
+		bool operator==(const iterator<Table>& other) {
+			return equals(other);
+		}
+		bool operator!=(const iterator<Table>& other) {
+			return !equals(other);
+		}
+		iterator<Table> operator++() {
+			bucket++;
+			while (
+				bucket < size &&
+				table->flags[bucket] & flags_null
+			) bucket++;
+			return *this;
+		}
+		std::pair<Key&, Value&> operator*() {
+			return { table->keys[bucket], table->values[bucket] };
+		}
+		std::pair<const Key&, const Value&> operator*() const {
+			return { table->keys[bucket], table->values[bucket] };
+		}
+	};
+
+	iterator<Hash_Map<Key, Value, size>> begin() {
+		iterator<Hash_Map<Key, Value, size>> r;
+		r.init_begin(this);
+		return r;
+	}
+
+	iterator<Hash_Map<Key, Value, size>> end() {
+		iterator<Hash_Map<Key, Value, size>> r;
+		r.init_end(this);
+		return r;
+	}
+
+	iterator<const Hash_Map<Key, Value, size>> begin() const {
+		iterator<const Hash_Map<Key, Value, size>> r;
+		r.init_begin(this);
+		return r;
+	}
+
+	iterator<const Hash_Map<Key, Value, size>> end() const {
+		iterator<const Hash_Map<Key, Value, size>> r;
+		r.init_end(this);
+		return r;
+	}
+};
+
+#endif