3 files changed, 148 insertions, 0 deletions
diff --git a/src/util/include/bloom_filter.hpp b/src/util/include/bloom_filter.hpp
new file mode 100644
index 00000000..04b72e20
--- /dev/null
+++ b/src/util/include/bloom_filter.hpp
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <bitset>
+#include <cstdint>
+#include <functional>
+
+namespace util {
+
+template <typename T>
+class BloomFilter {
+ public:
+  explicit BloomFilter(std::function<uint64_t(T)> hasher)
+      : hasher_(hasher), bits_() {}
+
+  auto Insert(T val) -> void {
+    uint64_t hash = std::invoke(hasher_, val);
+    bits_[hash & 0xFFFF] = 1;
+    bits_[(hash >> 16) & 0xFFFF] = 1;
+    bits_[(hash >> 32) & 0xFFFF] = 1;
+    bits_[(hash >> 48) & 0xFFFF] = 1;
+  }
+
+  auto Contains(T val) -> bool {
+    uint64_t hash = std::invoke(hasher_, val);
+    return bits_[hash & 0xFFFF] && bits_[(hash >> 16) & 0xFFFF] &&
+           bits_[(hash >> 32) & 0xFFFF] && bits_[(hash >> 48) & 0xFFFF];
+  }
+
+ private:
+  std::function<uint64_t(T)> hasher_;
+  std::bitset<(1 << 16)> bits_;
+};
+
+}  // namespace util
diff --git a/src/util/include/lru_cache.hpp b/src/util/include/lru_cache.hpp
new file mode 100644
index 00000000..8f955a07
--- /dev/null
+++ b/src/util/include/lru_cache.hpp
@@ -0,0 +1,69 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <bitset>
+#include <cstdint>
+#include <list>
+#include <optional>
+#include <unordered_map>
+#include <utility>
+
+namespace util {
+
+/*
+ * Basic least recently used cache. Stores the `Size` most recently accessed
+ * entries in memory.
+ *
+ * Not safe for use from multiple tasks, but all operations are constant time.
+ */
+template <int Size, typename K, typename V>
+class LruCache {
+ public:
+  LruCache() : entries_(), key_to_it_() {}
+
+  auto Put(K key, V val) -> void {
+    if (key_to_it_.contains(key)) {
+      // This key was already present. Overwrite by removing the previous
+      // value.
+      entries_.erase(key_to_it_[key]);
+      key_to_it_.erase(key);
+    } else if (entries_.size() >= Size) {
+      // Cache is full. Evict the last entry.
+      key_to_it_.erase(entries_.back().first);
+      entries_.pop_back();
+    }
+
+    // Add the new value.
+    entries_.push_front({key, val});
+    key_to_it_[key] = entries_.begin();
+  }
+
+  auto Get(K key) -> std::optional<V> {
+    if (!key_to_it_.contains(key)) {
+      return {};
+    }
+    // Use splice() to move the entry to the front of the list. This approach
+    // doesn't invalidate any of the iterators in key_to_it_, and is constant
+    // time.
+    auto it = key_to_it_[key];
+    entries_.splice(entries_.begin(), entries_, it);
+    return it->second;
+  }
+
+  auto Clear() -> void {
+    entries_.clear();
+    key_to_it_.clear();
+  }
+
+ private:
+  std::list<std::pair<K, V>> entries_;
+  std::unordered_map<K, decltype(entries_.begin())> key_to_it_;
+};
+
+}  // namespace util
diff --git a/src/util/include/random.hpp b/src/util/include/random.hpp
new file mode 100644
index 00000000..cd8ab1c6
--- /dev/null
+++ b/src/util/include/random.hpp
@@ -0,0 +1,39 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <cstdint>
+
+#include "komihash.h"
+
+namespace util {
+
+class IRandom {
+ public:
+  virtual ~IRandom() {}
+
+  virtual auto Next() -> std::uint64_t = 0;
+  virtual auto RangeInclusive(std::uint64_t lower, std::uint64_t upper)
+      -> std::uint64_t = 0;
+};
+
+extern IRandom* sRandom;
+
+class Random : public IRandom {
+ public:
+  Random();
+
+  auto Next() -> std::uint64_t override;
+  auto RangeInclusive(std::uint64_t lower, std::uint64_t upper)
+      -> std::uint64_t override;
+
+ private:
+  std::uint64_t seed1_;
+  std::uint64_t seed2_;
+};
+
+}  // namespace util