85 lines
2.2 KiB
C++
85 lines
2.2 KiB
C++
module map;
|
|
|
|
import std;
|
|
|
|
namespace brc {
|
|
|
|
map::map(std::size_t entry_count) : entries(std::make_unique<entry[]>(entry_count)), entry_count(entry_count) {}
|
|
|
|
std::uint64_t map::get_key(std::string_view city) noexcept {
|
|
std::uint64_t raw = 0;
|
|
const auto data_count = std::min(static_cast<int>(city.size()), 8);
|
|
std::memcpy(&raw, city.data(), data_count);
|
|
|
|
raw *= 0x9E3779B97F4A7C15ULL;
|
|
return raw ^ (raw >> 32);
|
|
}
|
|
|
|
std::uint64_t map::get_index(std::string_view city) const noexcept {
|
|
const auto key = get_key(city);
|
|
auto index = key & (entry_count - 1);
|
|
|
|
while (true) {
|
|
auto& e = entries[index];
|
|
if (e.key_ptr == nullptr) {
|
|
e.key_hash = key;
|
|
e.key_ptr = city.data();
|
|
e.key_len = static_cast<std::uint16_t>(city.size());
|
|
break;
|
|
} else if (key == e.key_hash && city == std::string_view(e.key_ptr, e.key_len)) {
|
|
break;
|
|
}
|
|
index = (index + 1 == entry_count) ? 0 : index + 1;
|
|
}
|
|
|
|
return index;
|
|
}
|
|
|
|
void map::insert(std::string_view city, std::int32_t measurement) {
|
|
const auto index = get_index(city);
|
|
|
|
auto& entry = entries[index];
|
|
entry.count += 1;
|
|
entry.total += measurement;
|
|
entry.min = std::min(entry.min, measurement);
|
|
entry.max = std::max(entry.max, measurement);
|
|
}
|
|
|
|
void map::merge_against(const map& other) {
|
|
for (std::size_t i = 0; i < other.entry_count; i++) {
|
|
if (other.entries[i].key_ptr == nullptr) {
|
|
continue;
|
|
}
|
|
|
|
auto& other_entry = other.entries[i];
|
|
auto& our_entry = entries[get_index(std::string_view(other_entry.key_ptr, other_entry.key_len))];
|
|
our_entry.min = std::min(our_entry.min, other_entry.min);
|
|
our_entry.max = std::max(our_entry.max, other_entry.max);
|
|
our_entry.count += other_entry.count;
|
|
our_entry.total += other_entry.total;
|
|
}
|
|
}
|
|
|
|
std::vector<entry> map::collapse() const noexcept {
|
|
auto data = std::vector<entry>();
|
|
data.reserve(entry_count);
|
|
|
|
for (std::size_t i = 0; i < entry_count; i++) {
|
|
if (entries[i].key_ptr == nullptr) {
|
|
continue;
|
|
}
|
|
|
|
data.push_back(entries[i]);
|
|
}
|
|
|
|
std::sort(data.begin(), data.end(), [](const entry& a, const entry& b) {
|
|
const auto a_sv = std::string_view(a.key_ptr, a.key_len);
|
|
const auto b_sv = std::string_view(b.key_ptr, b.key_len);
|
|
return a_sv < b_sv;
|
|
});
|
|
|
|
return data;
|
|
}
|
|
|
|
} // namespace brc
|