20 #ifndef REVERSE_PURGE_HASH_MAP_HPP_
21 #define REVERSE_PURGE_HASH_MAP_HPP_
38 typename V = uint64_t,
39 typename H = std::hash<K>,
40 typename E = std::equal_to<K>,
41 typename A = std::allocator<K>
43 class reverse_purge_hash_map {
45 using AllocV =
typename std::allocator_traits<A>::template rebind_alloc<V>;
46 using AllocU16 =
typename std::allocator_traits<A>::template rebind_alloc<uint16_t>;
48 reverse_purge_hash_map(uint8_t lg_size, uint8_t lg_max_size,
const E& equal,
const A& allocator);
49 reverse_purge_hash_map(
const reverse_purge_hash_map& other);
50 reverse_purge_hash_map(reverse_purge_hash_map&& other) noexcept;
51 ~reverse_purge_hash_map();
52 reverse_purge_hash_map& operator=(
const reverse_purge_hash_map& other);
53 reverse_purge_hash_map& operator=(reverse_purge_hash_map&& other);
55 template<
typename FwdK>
56 V adjust_or_insert(FwdK&& key, V value);
58 V get(
const K& key)
const;
59 uint8_t get_lg_cur_size()
const;
60 uint8_t get_lg_max_size()
const;
61 uint32_t get_capacity()
const;
62 uint32_t get_num_active()
const;
63 const A& get_allocator()
const;
66 iterator begin()
const;
70 static constexpr
double LOAD_FACTOR = 0.75;
71 static constexpr uint16_t DRIFT_LIMIT = 1024;
72 static constexpr uint32_t MAX_SAMPLE_SIZE = 1024;
83 inline bool is_active(uint32_t probe)
const;
84 void subtract_and_keep_positive_only(V amount);
85 void hash_delete(uint32_t probe);
86 uint32_t internal_adjust_or_insert(
const K& key, V value);
87 V resize_or_purge_if_needed();
88 void resize(uint8_t lg_new_size);
93 template<
typename K,
typename V,
typename H,
typename E,
typename A>
94 class reverse_purge_hash_map<K, V, H, E, A>::iterator {
96 using iterator_category = std::input_iterator_tag;
97 using value_type = std::pair<K&, V>;
98 using difference_type = void;
100 using reference =
const value_type;
102 friend class reverse_purge_hash_map<K, V, H, E, A>;
103 iterator& operator++() {
105 if (count < map->num_active_) {
106 const uint32_t mask = (1 << map->lg_cur_size_) - 1;
108 index = (index + stride) & mask;
109 }
while (!map->is_active(index));
113 iterator operator++(
int) { iterator tmp(*
this); operator++();
return tmp; }
114 bool operator==(
const iterator& rhs)
const {
return count == rhs.count; }
115 bool operator!=(
const iterator& rhs)
const {
return count != rhs.count; }
116 reference operator*()
const {
117 return value_type(map->keys_[index], map->values_[index]);
120 static constexpr
double GOLDEN_RATIO_RECIPROCAL = 0.6180339887498949;
121 const reverse_purge_hash_map<K, V, H, E, A>* map;
125 iterator(
const reverse_purge_hash_map<K, V, H, E, A>* map, uint32_t index, uint32_t count):
126 map(map), index(index), count(count), stride(static_cast<uint32_t>((1 << map->lg_cur_size_) * GOLDEN_RATIO_RECIPROCAL) | 1) {}
131 #include "reverse_purge_hash_map_impl.hpp"
DataSketches namespace.
Definition: binomial_bounds.hpp:38