userver: userver/rcu/rcu_map.hpp Source File
⚠️ This is the documentation for an old userver version. Click here to switch to the latest version.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
rcu_map.hpp
Go to the documentation of this file.
1#pragma once
2
3/// @file userver/rcu/rcu_map.hpp
4/// @brief @copybrief rcu::RcuMap
5
6#include <iterator>
7#include <memory>
8#include <optional>
9#include <type_traits>
10#include <unordered_map>
11#include <utility>
12
13#include <userver/rcu/rcu.hpp>
14#include <userver/utils/traceful_exception.hpp>
15
16USERVER_NAMESPACE_BEGIN
17
18namespace rcu {
19
20namespace impl {
21template <typename RcuMapTraits>
22struct RcuTraitsFromRcuMapTraits {
23 using MutexType = typename RcuMapTraits::MutexType;
24};
25} // namespace impl
26
27/// Thrown on missing element access
29 public:
30 using utils::TracefulException::TracefulException;
31};
32
33/// Default RcuMap traits.
34/// Member types:
35/// - `Hash` is a functor type that returns hash value for `Key`
36/// - `keyEqual` is a functor type that provide equality test for two values of
37/// type `Key`
38/// - `MutexType` is a writer's mutex type that has to be used to protect
39/// structure on update
40template <typename Key, typename Value>
41struct DefaultRcuMapTraits {
42 using Hash = std::hash<Key>;
43 using KeyEqual = std::equal_to<Key>;
44 using MutexType = engine::Mutex;
45};
46
47/// @brief Forward iterator for the rcu::RcuMap
48///
49/// Use member functions of rcu::RcuMap to retrieve the iterator.
50template <typename Key, typename Value, typename IterValue,
51 typename RcuMapTraits>
52class RcuMapIterator final {
53 using Hash = typename RcuMapTraits::Hash;
54 using KeyEqual = typename RcuMapTraits::KeyEqual;
55 using MapType =
56 std::unordered_map<Key, std::shared_ptr<Value>, Hash, KeyEqual>;
57 using BaseIterator = typename MapType::const_iterator;
58 using RcuTraits = typename impl::RcuTraitsFromRcuMapTraits<RcuMapTraits>;
59
60 public:
61 using iterator_category = std::input_iterator_tag;
62 using difference_type = ptrdiff_t;
63 using value_type = std::pair<Key, std::shared_ptr<IterValue>>;
64 using reference = const value_type&;
65 using pointer = const value_type*;
66
67 RcuMapIterator() = default;
68
69 RcuMapIterator operator++(int);
70 RcuMapIterator& operator++();
71 reference operator*() const;
72 pointer operator->() const;
73
74 bool operator==(const RcuMapIterator&) const;
75 bool operator!=(const RcuMapIterator&) const;
76
77 /// @cond
78 /// For internal use only
79 RcuMapIterator(ReadablePtr<MapType, RcuTraits>&& ptr, BaseIterator iter);
80 /// @endcond
81
82 private:
83 void UpdateCurrent();
84
85 std::optional<ReadablePtr<MapType, RcuTraits>> ptr_;
86 BaseIterator it_;
87 value_type current_;
88};
89
90/// @ingroup userver_concurrency userver_containers
91///
92/// @brief Map-like structure allowing RCU keyset updates.
93///
94/// Only keyset changes are thread-safe in scope of this class.
95/// Values are stored in `shared_ptr`s and are not copied during keyset change.
96/// The map itself is implemented as rcu::Variable, so every keyset change
97/// (e.g. insert or erase) triggers the whole map copying.
98/// @note No synchronization is provided for value access, it must be
99/// implemented by Value when necessary.
100///
101/// ## Example usage:
102///
103/// @snippet rcu/rcu_map_test.cpp Sample rcu::RcuMap usage
104///
105/// @see @ref scripts/docs/en/userver/synchronization.md
106template <typename Key, typename Value, typename RcuMapTraits>
107class RcuMap final {
108 using RcuTraits = typename impl::RcuTraitsFromRcuMapTraits<RcuMapTraits>;
109
110 public:
111 static_assert(!std::is_reference_v<Key>);
112 static_assert(!std::is_reference_v<Value>);
113 static_assert(!std::is_const_v<Key>);
114
115 template <typename ValuePtrType>
116 struct InsertReturnTypeImpl;
117
118 using Hash = typename RcuMapTraits::Hash;
119 using KeyEqual = typename RcuMapTraits::KeyEqual;
120 using MutexType = typename RcuMapTraits::MutexType;
121 using ValuePtr = std::shared_ptr<Value>;
122 using Iterator = RcuMapIterator<Key, Value, Value, RcuMapTraits>;
123 using ConstValuePtr = std::shared_ptr<const Value>;
124 using ConstIterator = RcuMapIterator<Key, Value, const Value, RcuMapTraits>;
125 using RawMap = std::unordered_map<Key, ValuePtr, Hash, KeyEqual>;
126 using Snapshot = std::unordered_map<Key, ConstValuePtr, Hash, KeyEqual>;
127 using InsertReturnType = InsertReturnTypeImpl<ValuePtr>;
128
129 RcuMap() = default;
130
131 RcuMap(const RcuMap&) = delete;
132 RcuMap(RcuMap&&) = delete;
133 RcuMap& operator=(const RcuMap&) = delete;
134 RcuMap& operator=(RcuMap&&) = delete;
135
136 /// Returns an estimated size of the map at some point in time
138
139 /// @name Iteration support
140 /// @details Keyset is fixed at the start of the iteration and is not affected
141 /// by concurrent changes.
142 /// @{
143 ConstIterator begin() const;
144 ConstIterator end() const;
145 Iterator begin();
146 Iterator end();
147 /// @}
148
149 /// @brief Returns a readonly value pointer by its key if exists
150 /// @throws MissingKeyException if the key is not present
151 const ConstValuePtr operator[](const Key&) const;
152
153 /// @brief Returns a modifiable value pointer by key if exists or
154 /// default-creates one
155 /// @note Copies the whole map if the key doesn't exist.
156 const ValuePtr operator[](const Key&);
157
158 /// @brief Inserts a new element into the container if there is no element
159 /// with the key in the container.
160 /// Returns a pair consisting of a pointer to the inserted element, or the
161 /// already-existing element if no insertion happened, and a bool denoting
162 /// whether the insertion took place.
163 /// @note Copies the whole map if the key doesn't exist.
164 InsertReturnType Insert(const Key& key, ValuePtr value);
165
166 /// @brief Inserts a new element into the container constructed in-place with
167 /// the given args if there is no element with the key in the container.
168 /// Returns a pair consisting of a pointer to the inserted element, or the
169 /// already-existing element if no insertion happened, and a bool denoting
170 /// whether the insertion took place.
171 /// @note Copies the whole map if the key doesn't exist.
172 template <typename... Args>
173 InsertReturnType Emplace(const Key& key, Args&&... args);
174
175 /// @brief If a key equivalent to `key` already exists in the container, does
176 /// nothing.
177 /// Otherwise, behaves like `Emplace` except that the element is constructed
178 /// as `std::make_shared<Value>(std::piecewise_construct,
179 /// std::forward_as_tuple(key),
180 /// std::forward_as_tuple(std::forward<Args>(args)...))`.
181 /// Returns a pair consisting of a pointer to the inserted element, or the
182 /// already-existing element if no insertion happened, and a bool denoting
183 /// whether the insertion took place.
184 template <typename... Args>
185 InsertReturnType TryEmplace(const Key& key, Args&&... args);
186
187 /// @brief If a key equivalent to `key` already exists in the container,
188 /// replaces the associated value. Otherwise, inserts a new pair into the map.
189 template <typename RawKey>
190 void InsertOrAssign(RawKey&& key, ValuePtr value);
191
192 /// @brief Returns a readonly value pointer by its key or an empty pointer
193 const ConstValuePtr Get(const Key&) const;
194
195 /// @brief Returns a modifiable value pointer by key or an empty pointer
196 const ValuePtr Get(const Key&);
197
198 /// @brief Removes a key from the map
199 /// @returns whether the key was present
200 /// @note Copies the whole map, might be slow for large maps.
201 bool Erase(const Key&);
202
203 /// @brief Removes a key from the map returning its value
204 /// @returns a value if the key was present, empty pointer otherwise
205 /// @note Copies the whole map, might be slow for large maps.
206 ValuePtr Pop(const Key&);
207
208 /// Resets the map to an empty state
209 void Clear();
210
211 /// Replace current data by data from `new_map`.
212 void Assign(RawMap new_map);
213
214 /// @brief Starts a transaction, used to perform a series of arbitrary changes
215 /// to the map.
216 /// @details The map is copied. Don't forget to `Commit` to apply the changes.
218
219 /// @brief Returns a readonly copy of the map
220 /// @note Equivalent to `{begin(), end()}` construct, preferable
221 /// for long-running operations.
223
224 private:
225 InsertReturnType DoInsert(const Key& key, ValuePtr value);
226
227 rcu::Variable<RawMap, RcuTraits> rcu_;
228};
229
230template <typename K, typename V, typename RcuMapTraits>
231template <typename ValuePtrType>
232struct RcuMap<K, V, RcuMapTraits>::InsertReturnTypeImpl {
233 ValuePtrType value;
234 bool inserted;
235};
236
237template <typename K, typename V, typename RcuMapTraits>
238typename RcuMap<K, V, RcuMapTraits>::ConstIterator
239RcuMap<K, V, RcuMapTraits>::begin() const {
240 auto ptr = rcu_.Read();
241 const auto iter = ptr->cbegin();
242 return
243 typename RcuMap<K, V, RcuMapTraits>::ConstIterator(std::move(ptr), iter);
244}
245
246template <typename K, typename V, typename RcuMapTraits>
247typename RcuMap<K, V, RcuMapTraits>::ConstIterator
248RcuMap<K, V, RcuMapTraits>::end() const {
249 // End iterator must be empty, because otherwise begin and end calls will
250 // return iterators that point into different map snapshots.
251 return {};
252}
253
254template <typename K, typename V, typename RcuMapTraits>
255typename RcuMap<K, V, RcuMapTraits>::Iterator
256RcuMap<K, V, RcuMapTraits>::begin() {
257 auto ptr = rcu_.Read();
258 const auto iter = ptr->cbegin();
259 return {std::move(ptr), iter};
260}
261
262template <typename K, typename V, typename RcuMapTraits>
263typename RcuMap<K, V, RcuMapTraits>::Iterator
264RcuMap<K, V, RcuMapTraits>::end() {
265 // End iterator must be empty, because otherwise begin and end calls will
266 // return iterators that point into different map snapshots.
267 return {};
268}
269
270template <typename K, typename V, typename RcuMapTraits>
271size_t RcuMap<K, V, RcuMapTraits>::SizeApprox() const {
272 auto ptr = rcu_.Read();
273 return ptr->size();
274}
275
276template <typename K, typename V, typename RcuMapTraits>
277// Protects from assignment to map[key]
278// NOLINTNEXTLINE(readability-const-return-type)
279const typename RcuMap<K, V, RcuMapTraits>::ConstValuePtr
280RcuMap<K, V, RcuMapTraits>::operator[](const K& key) const {
281 if (auto value = Get(key)) {
282 return value;
283 }
284 throw MissingKeyException("Key ") << key << " is missing";
285}
286
287template <typename K, typename V, typename RcuMapTraits>
288// Protects from assignment to map[key]
289// NOLINTNEXTLINE(readability-const-return-type)
290const typename RcuMap<K, V, RcuMapTraits>::ConstValuePtr
291RcuMap<K, V, RcuMapTraits>::Get(const K& key) const {
292 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
293 return const_cast<RcuMap<K, V, RcuMapTraits>*>(this)->Get(key);
294}
295
296template <typename K, typename V, typename RcuMapTraits>
297// Protects from assignment to map[key]
298// NOLINTNEXTLINE(readability-const-return-type)
299const typename RcuMap<K, V, RcuMapTraits>::ValuePtr
300RcuMap<K, V, RcuMapTraits>::operator[](const K& key) {
301 auto value = Get(key);
302 if (!value) {
303 auto txn = rcu_.StartWrite();
304 auto insertion_result = txn->emplace(key, std::make_shared<V>());
305 value = insertion_result.first->second;
306 if (insertion_result.second) txn.Commit();
307 }
308 return value;
309}
310
311template <typename K, typename V, typename RcuMapTraits>
312typename RcuMap<K, V, RcuMapTraits>::InsertReturnType
313RcuMap<K, V, RcuMapTraits>::Insert(
314 const K& key, typename RcuMap<K, V, RcuMapTraits>::ValuePtr value) {
315 InsertReturnType result{Get(key), false};
316 if (result.value) return result;
317
318 return DoInsert(key, std::move(value));
319}
320
321template <typename K, typename V, typename RcuMapTraits>
322template <typename... Args>
323typename RcuMap<K, V, RcuMapTraits>::InsertReturnType
324RcuMap<K, V, RcuMapTraits>::Emplace(const K& key, Args&&... args) {
325 InsertReturnType result{Get(key), false};
326 if (result.value) return result;
327
328 return DoInsert(key, std::make_shared<V>(std::forward<Args>(args)...));
329}
330
331template <typename K, typename V, typename RcuMapTraits>
332typename RcuMap<K, V, RcuMapTraits>::InsertReturnType
333RcuMap<K, V, RcuMapTraits>::DoInsert(
334 const K& key, typename RcuMap<K, V, RcuMapTraits>::ValuePtr value) {
335 auto txn = rcu_.StartWrite();
336 auto insertion_result = txn->emplace(key, std::move(value));
337 InsertReturnType result{insertion_result.first->second,
338 insertion_result.second};
339 if (result.inserted) txn.Commit();
340 return result;
341}
342
343template <typename K, typename V, typename RcuMapTraits>
344template <typename... Args>
345typename RcuMap<K, V, RcuMapTraits>::InsertReturnType
346RcuMap<K, V, RcuMapTraits>::TryEmplace(const K& key, Args&&... args) {
347 InsertReturnType result{Get(key), false};
348 if (!result.value) {
349 auto txn = rcu_.StartWrite();
350 auto insertion_result = txn->try_emplace(key, nullptr);
351 if (insertion_result.second) {
352 result.value = insertion_result.first->second =
353 std::make_shared<V>(std::forward<Args>(args)...);
354 txn.Commit();
355 result.inserted = true;
356 } else {
357 result.value = insertion_result.first->second;
358 }
359 }
360 return result;
361}
362
363template <typename Key, typename Value, typename RcuMapTraits>
364template <typename RawKey>
365void RcuMap<Key, Value, RcuMapTraits>::InsertOrAssign(RawKey&& key,
366 RcuMap::ValuePtr value) {
367 auto txn = rcu_.StartWrite();
368 txn->insert_or_assign(std::forward<RawKey>(key), std::move(value));
369 txn.Commit();
370}
371
372template <typename K, typename V, typename RcuMapTraits>
373// Protects from assignment to map[key]
374// NOLINTNEXTLINE(readability-const-return-type)
375const typename RcuMap<K, V, RcuMapTraits>::ValuePtr
376RcuMap<K, V, RcuMapTraits>::Get(const K& key) {
377 auto snapshot = rcu_.Read();
378 auto it = snapshot->find(key);
379 if (it == snapshot->end()) return {};
380 return it->second;
381}
382
383template <typename K, typename V, typename RcuMapTraits>
384bool RcuMap<K, V, RcuMapTraits>::Erase(const K& key) {
385 if (Get(key)) {
386 auto txn = rcu_.StartWrite();
387 if (txn->erase(key)) {
388 txn.Commit();
389 return true;
390 }
391 }
392 return false;
393}
394
395template <typename K, typename V, typename RcuMapTraits>
396typename RcuMap<K, V, RcuMapTraits>::ValuePtr RcuMap<K, V, RcuMapTraits>::Pop(
397 const K& key) {
398 auto value = Get(key);
399 if (value) {
400 auto txn = rcu_.StartWrite();
401 if (txn->erase(key)) txn.Commit();
402 }
403 return value;
404}
405
406template <typename K, typename V, typename RcuMapTraits>
407void RcuMap<K, V, RcuMapTraits>::Clear() {
408 rcu_.Assign({});
409}
410
411template <typename K, typename V, typename RcuMapTraits>
412void RcuMap<K, V, RcuMapTraits>::Assign(RawMap new_map) {
413 rcu_.Assign(std::move(new_map));
414}
415
416template <typename K, typename V, typename RcuMapTraits>
417auto RcuMap<K, V, RcuMapTraits>::StartWrite()
419 return rcu_.StartWrite();
420}
421
422template <typename K, typename V, typename RcuMapTraits>
423typename RcuMap<K, V, RcuMapTraits>::Snapshot
424RcuMap<K, V, RcuMapTraits>::GetSnapshot() const {
425 return {begin(), end()};
426}
427
428template <typename Key, typename Value, typename IterValue,
429 typename RcuMapTraits>
430RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::RcuMapIterator(
431 ReadablePtr<MapType, RcuTraits>&& ptr,
432 typename MapType::const_iterator iter)
433 : ptr_(std::move(ptr)), it_(iter) {
434 UpdateCurrent();
435}
436
437template <typename Key, typename Value, typename IterValue,
438 typename RcuMapTraits>
439auto RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::operator++(int)
440 -> RcuMapIterator {
441 RcuMapIterator tmp(*this);
442 ++*this;
443 return tmp;
444}
445
446template <typename Key, typename Value, typename IterValue,
447 typename RcuMapTraits>
448auto RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::operator++()
449 -> RcuMapIterator& {
450 ++it_;
451 UpdateCurrent();
452 return *this;
453}
454
455template <typename Key, typename Value, typename IterValue,
456 typename RcuMapTraits>
457auto RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::operator*() const
458 -> reference {
459 return current_;
460}
461
462template <typename Key, typename Value, typename IterValue,
463 typename RcuMapTraits>
464auto RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::operator->() const
465 -> pointer {
466 return &current_;
467}
468
469template <typename Key, typename Value, typename IterValue,
470 typename RcuMapTraits>
471bool RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::operator==(
472 const RcuMapIterator& rhs) const {
473 if (ptr_) {
474 if (rhs.ptr_) {
475 return it_ == rhs.it_;
476 } else {
477 return it_ == (*ptr_)->end();
478 }
479 } else {
480 return !rhs.ptr_ || rhs.it_ == (*rhs.ptr_)->end();
481 }
482}
483
484template <typename Key, typename Value, typename IterValue,
485 typename RcuMapTraits>
486bool RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::operator!=(
487 const RcuMapIterator& rhs) const {
488 return !(*this == rhs);
489}
490
491template <typename Key, typename Value, typename IterValue,
492 typename RcuMapTraits>
493void RcuMapIterator<Key, Value, IterValue, RcuMapTraits>::UpdateCurrent() {
494 if (it_ != (*ptr_)->end()) {
495 current_ = *it_;
496 }
497}
498
499} // namespace rcu
500
501USERVER_NAMESPACE_END