File size: 3,742 Bytes
1bfc3f0 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | // Shared primitives for the ActionCodec2 native kernels.
#pragma once
#include <cstdint>
#include <algorithm>
#include <utility>
#include <vector>
namespace ac2 {
class CounterMap {
public:
static constexpr uint64_t kEmpty = ~0ull;
explicit CounterMap(size_t capacity_hint = 1024) { reserve(capacity_hint); }
void reserve(size_t entries) {
size_t target = 16;
while (target * 3 < entries * 4) target <<= 1; // keep load factor <= 0.75
if (target <= mask_ + 1 && !keys_.empty()) return;
rehash(target);
}
size_t size() const { return size_; }
size_t buckets() const { return mask_ + 1; }
void clear() {
std::fill(keys_.begin(), keys_.end(), kEmpty);
size_ = 0;
}
int64_t get(uint64_t key) const {
size_t slot = probe(key);
return keys_[slot] == key ? values_[slot] : 0;
}
int64_t add(uint64_t key, int64_t delta) {
return add_with_previous(key, delta).second;
}
// Update and expose both values with one hash-table probe. This is useful
// when a caller must distinguish a newly observed key from a stale one.
std::pair<int64_t, int64_t> add_with_previous(uint64_t key, int64_t delta) {
size_t slot = probe(key);
if (keys_[slot] != key) {
if ((size_ + 1) * 4 > (mask_ + 1) * 3) {
rehash((mask_ + 1) << 1);
slot = probe(key);
}
keys_[slot] = key;
values_[slot] = 0;
++size_;
}
const int64_t previous = values_[slot];
values_[slot] += delta;
return {previous, values_[slot]};
}
template <typename Fn>
void for_each(Fn&& fn) const {
for (size_t slot = 0; slot <= mask_; ++slot) {
if (keys_[slot] != kEmpty && values_[slot] != 0) fn(keys_[slot], values_[slot]);
}
}
size_t live_entries() const {
size_t live = 0;
for (size_t slot = 0; slot <= mask_; ++slot) {
if (keys_[slot] != kEmpty && values_[slot] != 0) ++live;
}
return live;
}
private:
static uint64_t mix(uint64_t value) { // splitmix64 finalizer
value ^= value >> 30;
value *= 0xbf58476d1ce4e5b9ull;
value ^= value >> 27;
value *= 0x94d049bb133111ebull;
return value ^ (value >> 31);
}
size_t probe(uint64_t key) const {
size_t slot = mix(key) & mask_;
while (keys_[slot] != kEmpty && keys_[slot] != key) slot = (slot + 1) & mask_;
return slot;
}
void rehash(size_t buckets) {
std::vector<uint64_t> old_keys;
std::vector<int64_t> old_values;
old_keys.swap(keys_);
old_values.swap(values_);
keys_.assign(buckets, kEmpty);
values_.assign(buckets, 0);
mask_ = buckets - 1;
size_ = 0;
for (size_t slot = 0; slot < old_keys.size(); ++slot) {
if (old_keys[slot] != kEmpty && old_values[slot] != 0) {
size_t target = probe(old_keys[slot]);
keys_[target] = old_keys[slot];
values_[target] = old_values[slot];
++size_;
}
}
}
std::vector<uint64_t> keys_;
std::vector<int64_t> values_;
size_t mask_ = 0;
size_t size_ = 0;
};
struct HeapEntry {
int64_t count;
uint64_t key;
uint32_t version; // only shifted temporal self-rules use this
};
struct HeapOrder {
bool operator()(const HeapEntry& a, const HeapEntry& b) const {
if (a.count != b.count) return a.count < b.count; // larger count first
return a.key > b.key; // smaller key first
}
};
inline void heap_push(std::vector<HeapEntry>& heap, const HeapEntry& entry) {
heap.push_back(entry);
std::push_heap(heap.begin(), heap.end(), HeapOrder{});
}
inline HeapEntry heap_pop(std::vector<HeapEntry>& heap) {
std::pop_heap(heap.begin(), heap.end(), HeapOrder{});
HeapEntry top = heap.back();
heap.pop_back();
return top;
}
} // namespace ac2
|