A few notes:
There is currently no non exception-based way of knowing whether a key is present in the table or not. This is intentional for my use case.
Unlike the lookup process, the baking process is definitely not appropriate for a real-time application. That's ok as it's meant to be run offline.
Obviously, this is only appropriate for storing trivial types.
What I'm particularly interested in is:
I "think" I managed to pull this off without any Undefined Behavior, but I'd really want some other pairs of eyes checking for this, as I'm in dodgy territory on that front.
As usual, any and all criticism on general code quality.
Thanks!
#include <cassert>
#include <cstdint>
#include <cstring>
#include <functional>
#include <type_traits>
#include <unordered_set>
#include <utility>
// The flat hash table is meant to be used when a hash table is baked once,
// typically during a build process, and then used repeatadly. It can be
// initialized by simply pointing it at a memory location containing the
// raw data.
// The table does NOT maintain ownership over the data.
template <typename ValT, typename HashT = std::uint64_t>
class flat_hash_table {
static_assert(std::is_trivial_v<ValT>);
static_assert(std::is_trivial_v<HashT>);
public:
flat_hash_table(char const* mem_loc, std::size_t mem_len)
: mem_loc_(mem_loc) {
if (mem_len < sizeof(bucket_count_)) {
throw std::invalid_argument("invalid flat hash data");
}
char const* read_ptr = mem_loc;
std::memcpy(&bucket_count_, read_ptr, sizeof(bucket_count_));
read_ptr += sizeof(bucket_count_);
if (mem_len < sizeof(bucket_count_) + bucket_count_ * sizeof(bucket_t)) {
throw std::invalid_argument("invalid flat hash data");
}
if (std::uintptr_t(read_ptr) % alignof(bucket_t) != 0) {
throw std::invalid_argument("flat hash data appears to be misaligned");
}
static_assert(std::is_trivially_constructible_v<bucket_t>);
buckets_ = new (const_cast<char*>(read_ptr)) bucket_t[bucket_count_];
for (std::uint32_t i = 0; i < bucket_count_; ++i) {
if (buckets_[i].offset + buckets_[i].count * sizeof(elem_t) > mem_len) {
throw std::invalid_argument("invalid flat hash data");
}
auto bucket_loc = mem_loc_ + buckets_[i].offset;
if (std::uintptr_t(bucket_loc) % alignof(elem_t) != 0) {
throw std::invalid_argument("flat hash data appears to be misaligned");
}
static_assert(std::is_trivially_constructible_v<elem_t>);
new (const_cast<char*>(bucket_loc)) elem_t[buckets_[i].count];
}
}
// Lookup a value from the hash table, throws if the value is not
// present.
template <typename KeyT>
ValT const& at(KeyT const& key) {
HashT key_hash = std::hash<KeyT>{}(key);
auto const& bucket = buckets_[key_hash % bucket_count_];
if (bucket.count > 0) {
elem_t const* elem_table =
reinterpret_cast<elem_t const*>(mem_loc_ + bucket.offset);
auto end = elem_table + bucket.count;
// Elements within a bucket are stored as a sorted vector, so we
// can do a binary search.
auto found = std::lower_bound(
elem_table, end, key_hash,
[](elem_t const& lhs, HashT const& rhs) { return lhs.key < rhs; });
if (found != end && found->key == key_hash) {
return found->val;
}
}
throw std::out_of_range("element not present in flat hash table");
}
private:
char const* mem_loc_;
struct bucket_t {
std::uint32_t count;
std::uint32_t offset;
};
// This cannot be a std::pair<> because the default constructor is not trivial
struct elem_t {
HashT key;
ValT val;
};
std::uint32_t bucket_count_;
bucket_t const* buckets_;
template <typename K, typename V, typename H>
friend std::vector<char> bake_flat_hash_table(
std::vector<std::pair<K, V>> const&);
};
// Bakes a dataset into a flat_has_table raw data chunk.
template <typename KeyT, typename ValT, typename HashT = std::uint64_t>
std::vector<char> bake_flat_hash_table(
std::vector<std::pair<KeyT, ValT>> const& data) {
using table_t = flat_hash_table<ValT, HashT>;
using elem_t = typename table_t::elem_t;
using bucket_t = typename table_t::bucket_t;
static_assert(std::is_trivial_v<ValT>);
static_assert(std::is_trivial_v<HashT>);
// TODO: Better process to determine optimal bucket count.
std::uint32_t bucket_count = data.size() / 2 + 1;
std::vector<std::vector<elem_t>> buckets(bucket_count);
{
// Keep track of seen hashes since we do not tolerate true collisions.
std::unordered_set<HashT> hash_values_set;
for (auto const& d : data) {
HashT hash_val = HashT(std::hash<KeyT>{}(d.first));
if (hash_values_set.count(hash_val) != 0) {
throw std::runtime_error(
"True hash collision in dataset, cannot make a flat hash table out "
"of it.");
}
hash_values_set.insert(hash_val);
buckets[hash_val % bucket_count].emplace_back(elem_t{hash_val, d.second});
}
}
std::size_t header_mem_size = 0;
header_mem_size += sizeof(std::uint32_t); // for bucket_count
header_mem_size += sizeof(bucket_t) * bucket_count; // bucket table
// Make sure the actual value payloads is correctly aligned
constexpr auto elem_align = alignof(elem_t);
static_assert((elem_align & (elem_align - 1)) == 0);
header_mem_size = (header_mem_size + (elem_align - 1)) & ~(elem_align - 1);
auto mem_size = header_mem_size + sizeof(elem_t) * data.size();
std::vector<char> result(mem_size);
char* header_w_ptr = result.data();
char* data_w_ptr = result.data() + header_mem_size;
auto write = [&](char*& dst, auto const& v) {
assert(dst + sizeof(v) <= result.data() + result.size());
std::memcpy(dst, &v, sizeof(v));
dst += sizeof(v);
};
write(header_w_ptr, bucket_count);
for (auto& b : buckets) {
std::sort(b.begin(), b.end(), [](auto const& lhs, auto const& rhs) {
return lhs.key < rhs.key;
});
auto offset = data_w_ptr - result.data();
bucket_t bucket_header{std::uint32_t(b.size()), std::uint32_t(offset)};
write(header_w_ptr, bucket_header);
for (auto const& e : b) {
write(data_w_ptr, e);
}
}
return result;
}
#include <iostream>
#include <string_view>
#include <vector>
int main() {
std::vector<std::pair<std::string, float>> raw_values = {
{"hi", 12.0f}, {"yo", 10.0f}, {"sup", 3.0f},
};
std::vector<char> raw_data = bake_flat_hash_table(raw_values);
flat_hash_table<float> values(raw_data.data(), raw_data.size());
std::cout << values.at(std::string_view("yo")) << "\n";
std::cout << values.at(std::string_view("sup")) << "\n";
std::cout << values.at(std::string_view("hi")) << "\n";
return 0;
}
Obvious next steps / stuff I'm already aware of:
- Endianness handling
- Proper iterator-based lookup interface
- Better bucket counting
