2 * Copyright (C) 2002-2023 CERN for the benefit of the ATLAS collaboration.
5 * @file CxxUtils/ConcurrentStrToValMap.icc
6 * @author scott snyder <snyder@bnl.gov>
8 * @brief Hash map from strings to arbitrary objects allowing
9 * concurrent, lockless reads.
16 #define T_CONCURRENTSTRTOVALMAP template <class VALUE, \
17 template <class> class UPDATER> \
18 ATH_REQUIRES (detail::IsUpdater<UPDATER>)
20 #define CONCURRENTSTRTOVALMAP ConcurrentStrToValMap<VALUE, UPDATER>
25 * @param updater Object used to manage memory
26 * (see comments at the start of the class).
27 * @param capacity The initial table capacity.
28 * (Will be rounded up to a power of two.)
29 * @param ctx Execution context.
31 T_CONCURRENTSTRTOVALMAP
32 CONCURRENTSTRTOVALMAP::ConcurrentStrToValMap (Updater_t&& updater,
33 size_type capacity /*= 64*/,
35 /* = Updater_t::defaultContext()*/)
36 : m_impl (std::move (updater),
46 * @brief Constructor from another map.
47 * @param updater Object used to manage memory
48 * (see comments at the start of the class).
49 * @param capacity The initial table capacity of the new table.
50 * (Will be rounded up to a power of two.)
51 * @param ctx Execution context.
53 * (Not really a copy constructor since we need to pass @c updater.)
55 T_CONCURRENTSTRTOVALMAP
56 CONCURRENTSTRTOVALMAP::ConcurrentStrToValMap (const ConcurrentStrToValMap& other,
58 size_type capacity /*= 64*/,
60 /*= Updater_t::defaultContext()*/)
61 : m_impl (std::move (updater),
67 // not using reference, because our iterator doesn't return a reference
68 for (const auto p : other) {
69 this->put (std::make_unique<key_type> (p.first),
70 std::make_unique<mapped_type> (p.second),
77 * @brief Constructor from a range.
78 * @param f Start iterator for the range.
79 * @param l End iterator for the range.
80 * @param updater Object used to manage memory
81 * (see comments at the start of the class).
82 * @param capacity The initial table capacity of the new table.
83 * (Will be rounded up to a power of two.)
84 * @param ctx Execution context.
86 * Constructor from a range of pairs.
88 T_CONCURRENTSTRTOVALMAP
89 template <class InputIterator>
90 CONCURRENTSTRTOVALMAP::ConcurrentStrToValMap (InputIterator f,
93 size_t capacity /*= 64*/,
95 /*= Updater_t::defaultContext()*/)
96 : m_impl (std::move (updater),
102 if constexpr (std::is_rvalue_reference_v<typename InputIterator::reference>)
104 for (; f != l; ++f) {
105 emplace (std::move (f->first), std::move (f->second), ctx);
109 for (; f != l; ++f) {
110 emplace (f->first, f->second, ctx);
119 T_CONCURRENTSTRTOVALMAP
120 CONCURRENTSTRTOVALMAP::~ConcurrentStrToValMap()
122 // Need to delete the strings and values that we've stored.
123 auto [begin, end] = m_impl.range();
124 while (begin != end) {
125 if (begin.key() != Impl_t::nullval) {
126 delete keyAsString (begin.key());
127 delete mappedAsMapped (begin.value());
135 * @brief Return the number of items currently in the map.
137 T_CONCURRENTSTRTOVALMAP
139 auto CONCURRENTSTRTOVALMAP::size() const -> size_type
141 return m_impl.size();
146 * @brief Test if the map is currently empty.
148 T_CONCURRENTSTRTOVALMAP
150 bool CONCURRENTSTRTOVALMAP::empty() const
152 return !m_impl.size();
157 * @brief Return the current size (capacity) of the hash table.
159 T_CONCURRENTSTRTOVALMAP
161 auto CONCURRENTSTRTOVALMAP::capacity() const -> size_t
163 return m_impl.capacity();
168 * @brief Constructor.
169 * @param it Iterator of the underlying table.
171 T_CONCURRENTSTRTOVALMAP
173 CONCURRENTSTRTOVALMAP::const_iterator::const_iterator (typename Impl_t::const_iterator it)
180 * @brief Conversion from non-const iterator (for interoperability).
181 * @param other The other iterator.
183 T_CONCURRENTSTRTOVALMAP
185 CONCURRENTSTRTOVALMAP::const_iterator::const_iterator (const iterator& other)
186 : m_impl (other.m_impl)
192 * @brief Test if this iterator is valid.
194 * This should be the same as testing for != end().
196 T_CONCURRENTSTRTOVALMAP
198 auto CONCURRENTSTRTOVALMAP::const_iterator::valid() const -> bool
200 return m_impl.valid();
205 * @brief iterator_facade requirement: Increment the iterator.
207 T_CONCURRENTSTRTOVALMAP
209 auto CONCURRENTSTRTOVALMAP::const_iterator::increment() -> void
216 * @brief iterator_facade requirement: Decrement the iterator.
218 T_CONCURRENTSTRTOVALMAP
220 auto CONCURRENTSTRTOVALMAP::const_iterator::decrement() -> void
227 * @brief iterator_facade requirement: Dereference the iterator.
229 T_CONCURRENTSTRTOVALMAP
231 auto CONCURRENTSTRTOVALMAP::const_iterator::dereference() const
232 -> const const_iterator_value
234 return const_iterator_value (*keyAsString (m_impl.key()),
235 *mappedAsMapped (m_impl.value()));
240 * @brief iterator_facade requirement: Equality test.
242 T_CONCURRENTSTRTOVALMAP
244 auto CONCURRENTSTRTOVALMAP::const_iterator::equal (const const_iterator& other) const
247 return !(m_impl != other.m_impl);
252 * @brief iterator_facade requirement: Equality test. (Interoperability.)
254 T_CONCURRENTSTRTOVALMAP
256 auto CONCURRENTSTRTOVALMAP::const_iterator::equal (const iterator& other) const
259 return !(m_impl != other.m_impl);
264 * @brief Constructor.
265 * @param it Iterator of the underlying table.
267 T_CONCURRENTSTRTOVALMAP
269 CONCURRENTSTRTOVALMAP::iterator::iterator (typename Impl_t::const_iterator it)
276 * @brief Test if this iterator is valid.
278 * This should be the same as testing for != end().
280 T_CONCURRENTSTRTOVALMAP
282 auto CONCURRENTSTRTOVALMAP::iterator::valid() const -> bool
284 return m_impl.valid();
289 * @brief iterator_facade requirement: Increment the iterator.
291 T_CONCURRENTSTRTOVALMAP
293 auto CONCURRENTSTRTOVALMAP::iterator::increment() -> void
300 * @brief iterator_facade requirement: Decrement the iterator.
302 T_CONCURRENTSTRTOVALMAP
304 auto CONCURRENTSTRTOVALMAP::iterator::decrement() -> void
311 * @brief iterator_facade requirement: Dereference the iterator.
313 T_CONCURRENTSTRTOVALMAP
315 auto CONCURRENTSTRTOVALMAP::iterator::dereference() const
316 -> const iterator_value
318 return iterator_value (*keyAsString (m_impl.key()),
319 *mappedAsMapped (m_impl.value()));
324 * @brief iterator_facade requirement: Equality test.
326 T_CONCURRENTSTRTOVALMAP
328 auto CONCURRENTSTRTOVALMAP::iterator::equal (const iterator& other) const
331 return !(m_impl != other.m_impl);
336 * @brief iterator_facade requirement: Equality test. (Interoperability.)
338 T_CONCURRENTSTRTOVALMAP
340 auto CONCURRENTSTRTOVALMAP::iterator::equal (const const_iterator& other) const
343 return !(m_impl != other.m_impl);
348 * @brief Return an iterator range covering the entire map.
350 T_CONCURRENTSTRTOVALMAP
351 auto CONCURRENTSTRTOVALMAP::range() const -> const_iterator_range
353 auto [begin, end] = m_impl.range();
354 return const_iterator_range (begin, end);
359 * @brief Return an iterator range covering the entire map.
361 * The mapped objects must themselves be thread-safe in order to make
362 * any changes to them through the returned iterators.
364 T_CONCURRENTSTRTOVALMAP
365 auto CONCURRENTSTRTOVALMAP::range() -> iterator_range
367 auto [begin, end] = m_impl.range();
368 return iterator_range (begin, end);
373 * @brief Iterator at the start of the map.
375 T_CONCURRENTSTRTOVALMAP
377 auto CONCURRENTSTRTOVALMAP::begin() const -> const_iterator
379 return const_iterator (m_impl.begin());
384 * @brief Iterator at the end of the map.
386 T_CONCURRENTSTRTOVALMAP
388 auto CONCURRENTSTRTOVALMAP::end() const -> const_iterator
390 return const_iterator (m_impl.end());
395 * @brief Iterator at the start of the map.
397 * The mapped objects must themselves be thread-safe in order to make
398 * any changes to them through the returned iterators.
400 T_CONCURRENTSTRTOVALMAP
402 auto CONCURRENTSTRTOVALMAP::begin() -> iterator
404 return iterator (m_impl.begin());
409 * @brief Iterator at the end of the map.
411 * The mapped objects must themselves be thread-safe in order to make
412 * any changes to them through the returned iterators.
414 T_CONCURRENTSTRTOVALMAP
416 auto CONCURRENTSTRTOVALMAP::end() -> iterator
418 return iterator (m_impl.end());
423 * @brief Iterator at the start of the map.
425 T_CONCURRENTSTRTOVALMAP
427 auto CONCURRENTSTRTOVALMAP::cbegin() const -> const_iterator
434 * @brief Iterator at the end of the map.
436 T_CONCURRENTSTRTOVALMAP
438 auto CONCURRENTSTRTOVALMAP::cend() const -> const_iterator
445 * @brief Test if a key is in the container.
446 * @param key The key to test.
448 T_CONCURRENTSTRTOVALMAP
450 bool CONCURRENTSTRTOVALMAP::contains (const key_type& key) const
452 return get(key).valid();
457 * @brief Return the number of times a given key is in the container.
458 * @param key The key to test.
460 * Returns either 0 or 1, depending on whether or not the key is in the map.
462 T_CONCURRENTSTRTOVALMAP
464 auto CONCURRENTSTRTOVALMAP::count (const key_type& key) const -> size_type
466 return contains (key) ? 1 : 0;
471 * @brief Look up an element in the map.
472 * @param key The element to find.
474 * Returns either an iterator referencing the found element or end().
476 T_CONCURRENTSTRTOVALMAP
478 auto CONCURRENTSTRTOVALMAP::find (const key_type& key) const -> const_iterator
480 return const_iterator (this->get (key));
485 * @brief Look up an element in the map.
486 * @param key The element to find.
488 * Returns either an iterator referencing the found element or end().
490 * The mapped object must itself be thread-safe in order to make
491 * any changes to it through the returned iterator.
493 T_CONCURRENTSTRTOVALMAP
495 auto CONCURRENTSTRTOVALMAP::find (const key_type& key) -> iterator
497 return iterator (this->get (key));
502 * @brief Look up an element in the map.
503 * @param key The element to find.
505 * Returns the value associated with the key.
506 * Throws @c std::out_of_range if the key does not exist in the map.
508 T_CONCURRENTSTRTOVALMAP
509 auto CONCURRENTSTRTOVALMAP::at (const key_type& key) const -> const mapped_type&
511 typename Impl_t::const_iterator it = this->get (key);
513 throw std::out_of_range ("ConcurrentToValMap::at");
515 return *mappedAsMapped (it.value());
520 * @brief Look up an element in the map.
521 * @param key The element to find.
523 * Returns the value associated with the key.
524 * Throws @c std::out_of_range if the key does not exist in the map.
526 * This returns a non-const reference to the mapped object.
527 * The mapped object must be thread-safe itself in order to safely
528 * make any changes to it.
530 T_CONCURRENTSTRTOVALMAP
531 auto CONCURRENTSTRTOVALMAP::at (const key_type& key) -> mapped_type&
533 typename Impl_t::const_iterator it = this->get (key);
535 throw std::out_of_range ("ConcurrentToValMap::at");
537 return *mappedAsMapped (it.value());
542 * @brief Return a range of iterators with entries matching @c key.
543 * @param key The element to find.
545 * As keys are unique in this container, this is either a single-element
546 * range, or both iterators are equal to end().
548 T_CONCURRENTSTRTOVALMAP
549 auto CONCURRENTSTRTOVALMAP::equal_range (const key_type& key) const
550 -> std::pair<const_iterator, const_iterator>
552 const_iterator i1 = find (key);
553 const_iterator i2 = i1;
557 return std::make_pair (i1, i2);
562 * @brief Return a range of iterators with entries matching @c key.
563 * @param key The element to find.
565 * As keys are unique in this container, this is either a single-element
566 * range, or both iterators are equal to end().
568 * The mapped objects must themselves be thread-safe in order to make
569 * any changes to them through the returned iterators.
571 T_CONCURRENTSTRTOVALMAP
572 auto CONCURRENTSTRTOVALMAP::equal_range (const key_type& key)
573 -> std::pair<iterator, iterator>
575 iterator i1 = find (key);
580 return std::make_pair (i1, i2);
585 * @brief Add an element to the map.
586 * @param key The key of the new item to add.
587 * @param val The value of the new item to add.
588 * @param ctx Execution context.
590 * This will not overwrite an existing entry.
591 * The first element in the returned pair is an iterator referencing
592 * the added item. The second is a flag that is true if a new element
595 T_CONCURRENTSTRTOVALMAP
597 auto CONCURRENTSTRTOVALMAP::emplace (const key_type& key,
598 const mapped_type& val,
600 /*= Updater_t::defaultContext()*/)
601 -> std::pair<const_iterator, bool>
603 return put (std::make_unique<key_type> (key),
604 std::make_unique<mapped_type> (val),
610 * @brief Add an element to the map.
611 * @param key The key of the new item to add.
612 * @param val The value of the new item to add.
613 * @param ctx Execution context.
615 * This will not overwrite an existing entry.
616 * The first element in the returned pair is an iterator referencing
617 * the added item. The second is a flag that is true if a new element
620 T_CONCURRENTSTRTOVALMAP
622 auto CONCURRENTSTRTOVALMAP::emplace (key_type&& key,
623 const mapped_type& val,
625 /*= Updater_t::defaultContext()*/)
626 -> std::pair<const_iterator, bool>
628 return put (std::make_unique<key_type> (std::move (key)),
629 std::make_unique<mapped_type> (val),
635 * @brief Add an element to the map.
636 * @param key The key of the new item to add.
637 * @param val The value of the new item to add.
638 * @param ctx Execution context.
640 * This will not overwrite an existing entry.
641 * The first element in the returned pair is an iterator referencing
642 * the added item. The second is a flag that is true if a new element
645 T_CONCURRENTSTRTOVALMAP
647 auto CONCURRENTSTRTOVALMAP::emplace (const key_type& key,
650 /*= Updater_t::defaultContext()*/)
651 -> std::pair<const_iterator, bool>
653 return put (std::make_unique<key_type> (key),
654 std::make_unique<mapped_type> (std::move (val)),
660 * @brief Add an element to the map.
661 * @param key The key of the new item to add.
662 * @param val The value of the new item to add.
663 * @param ctx Execution context.
665 * This will not overwrite an existing entry.
666 * The first element in the returned pair is an iterator referencing
667 * the added item. The second is a flag that is true if a new element
670 T_CONCURRENTSTRTOVALMAP
672 auto CONCURRENTSTRTOVALMAP::emplace (key_type&& key,
675 /*= Updater_t::defaultContext()*/)
676 -> std::pair<const_iterator, bool>
678 return put (std::make_unique<key_type> (std::move (key)),
679 std::make_unique<mapped_type> (std::move (val)),
685 * @brief Add an element to the map.
686 * @param key The key of the new item to add.
687 * @param val The value of the new item to add.
688 * @param ctx Execution context.
690 * This will not overwrite an existing entry.
691 * The first element in the returned pair is an iterator referencing
692 * the added item. The second is a flag that is true if a new element
695 T_CONCURRENTSTRTOVALMAP
697 auto CONCURRENTSTRTOVALMAP::emplace (const key_type& key,
698 std::unique_ptr<mapped_type> val,
700 /*= Updater_t::defaultContext()*/)
701 -> std::pair<const_iterator, bool>
703 return put (std::make_unique<key_type> (key),
710 * @brief Add an element to the map.
711 * @param key The key of the new item to add.
712 * @param val The value of the new item to add.
713 * @param ctx Execution context.
715 * This will not overwrite an existing entry.
716 * The first element in the returned pair is an iterator referencing
717 * the added item. The second is a flag that is true if a new element
720 T_CONCURRENTSTRTOVALMAP
722 auto CONCURRENTSTRTOVALMAP::emplace (key_type&& key,
723 std::unique_ptr<mapped_type> val,
725 /*= Updater_t::defaultContext()*/)
726 -> std::pair<const_iterator, bool>
728 return put (std::make_unique<key_type> (std::move (key)),
735 * @brief Add an element to the map.
736 * @param p The item to add.
737 * Should be a pair where first is the string key
738 * and second is the integer value.
739 * @param ctx Execution context.
741 * This will not overwrite an existing entry.
742 * The first element in the returned pair is an iterator referencing
743 * the added item. The second is a flag that is true if a new element
746 T_CONCURRENTSTRTOVALMAP
747 template <class PAIR>
749 auto CONCURRENTSTRTOVALMAP::insert (const PAIR& p,
750 const Context_t& ctx /*= Updater_t::defaultContext()*/)
751 -> std::pair<const_iterator, bool>
753 return emplace (p.first, p.second, ctx);
758 * @brief Add an element to the map.
759 * @param p The item to add.
760 * Should be a pair where first is the string key
761 * and second is the integer value.
762 * @param ctx Execution context.
764 * This will not overwrite an existing entry.
765 * The first element in the returned pair is an iterator referencing
766 * the added item. The second is a flag that is true if a new element
769 T_CONCURRENTSTRTOVALMAP
770 template <class PAIR>
772 auto CONCURRENTSTRTOVALMAP::insert (PAIR&& p,
773 const Context_t& ctx /*= Updater_t::defaultContext()*/)
774 -> std::pair<const_iterator, bool>
776 return emplace (std::move (p.first), std::move (p.second), ctx);
781 * @brief Insert a range of elements to the map.
782 * @param first Start of the range.
783 * @param last End of the range.
784 * @param ctx Execution context.
786 * The range should be a sequence of pairs where first is the string key
787 * and second is the integer value.
789 T_CONCURRENTSTRTOVALMAP
790 template <class InputIterator>
791 void CONCURRENTSTRTOVALMAP::insert (InputIterator first, InputIterator last,
792 const Context_t& ctx /*= Updater_t::defaultContext()*/)
794 if constexpr (std::is_rvalue_reference_v<typename InputIterator::reference>)
796 for (; first != last; ++first) {
797 emplace (std::move (first->first), std::move (first->second), ctx);
801 for (; first != last; ++first) {
802 emplace (first->first, first->second, ctx);
809 * @brief Increase the table capacity.
810 * @param capacity The new table capacity.
811 * @param ctx Execution context.
813 * No action will be taken if @c capacity is smaller
814 * than the current capacity.
816 T_CONCURRENTSTRTOVALMAP
818 void CONCURRENTSTRTOVALMAP::reserve (size_type capacity,
820 /*= Updater_t::defaultContext()*/)
822 return m_impl.reserve (capacity, ctx);
827 * @brief Increase the table capacity.
828 * @param capacity The new table capacity.
830 * No action will be taken if @c capacity is smaller
831 * than the current capacity.
833 T_CONCURRENTSTRTOVALMAP
835 void CONCURRENTSTRTOVALMAP::rehash (size_type capacity)
837 return reserve (capacity);
842 * @brief Called when this thread is no longer referencing anything
843 * from this container.
844 * @param ctx Execution context.
846 T_CONCURRENTSTRTOVALMAP
848 void CONCURRENTSTRTOVALMAP::quiescent (const Context_t& ctx)
850 return m_impl.quiescent (ctx);
855 * @brief Swap this container with another.
856 * @param other The container with which to swap.
858 * This will also call swap on the Updater object; hence, the Updater
859 * object must also support swap.
861 * This operation is NOT thread-safe. No other threads may be accessing
862 * either container during this operation.
864 T_CONCURRENTSTRTOVALMAP
865 void CONCURRENTSTRTOVALMAP::swap (ConcurrentStrToValMap& other)
867 m_impl.swap (other.m_impl);
872 * @brief Access the Updater instance.
874 T_CONCURRENTSTRTOVALMAP
875 auto CONCURRENTSTRTOVALMAP::updater() -> Updater_t&
877 return m_impl.updater();
882 * @brief Convert an underlying key value to a string pointer.
883 * @param val The underlying key value.
885 T_CONCURRENTSTRTOVALMAP
887 auto CONCURRENTSTRTOVALMAP::keyAsString (val_t val) -> const std::string*
889 return reinterpret_cast<std::string*> (val);
894 * @brief Convert a string pointer to an underlying key value.
895 * @param s The string pointer.
897 T_CONCURRENTSTRTOVALMAP
899 auto CONCURRENTSTRTOVALMAP::keyAsVal (const std::string* s) -> val_t
901 return reinterpret_cast<val_t> (s);
906 * @brief Convert an underlying mapped value a pointer to
907 * this type's mapped value.
908 * @param val The underlying mapped value.
910 T_CONCURRENTSTRTOVALMAP
912 auto CONCURRENTSTRTOVALMAP::mappedAsMapped (val_t val) -> mapped_type*
914 return CxxUtils::detail::UIntConv<mapped_type*>::uintToVal (val);
919 * @brief Convert this type's mapped value to an underlying mapped value.
920 * @param val The mapped value.
922 T_CONCURRENTSTRTOVALMAP
924 auto CONCURRENTSTRTOVALMAP::mappedAsVal (mapped_type* val) -> val_t
926 return CxxUtils::detail::UIntConv<mapped_type*>::valToUInt (val);
931 * @brief Do a lookup in the table.
932 * @param key The key to look up.
934 * Returns an iterator of the underlying map pointing at the found
937 T_CONCURRENTSTRTOVALMAP
938 auto CONCURRENTSTRTOVALMAP::get (const key_type& key) const
939 -> typename Impl_t::const_iterator
941 size_t hash = m_impl.hasher() (key);
942 return m_impl.get (keyAsVal(&key), hash);
947 * @brief Insert an entry in the table.
948 * @param key The key of the new item to add.
949 * @param val The new mapped value to add.
950 * @param ctx Execution context.
952 * The first element in the returned pair is an iterator referencing
953 * the added item. The second is a flag that is true if a new element
956 T_CONCURRENTSTRTOVALMAP
957 auto CONCURRENTSTRTOVALMAP::put (std::unique_ptr<key_type> key,
958 std::unique_ptr<mapped_type> val,
959 const Context_t& ctx /*= Updater_t::defaultContext()*/)
960 -> std::pair<const_iterator, bool>
962 size_t hash = m_impl.hasher() (*key);
963 auto [it, flag] = m_impl.put (keyAsVal(key.get()), hash,
964 mappedAsVal (val.get()),
971 return std::make_pair (const_iterator (it), flag);
976 * @brief Hash function from the underlying representation type.
978 T_CONCURRENTSTRTOVALMAP
980 auto CONCURRENTSTRTOVALMAP::Hasher::operator() (const val_t p) const -> size_t
982 return m_hash (*keyAsString(p));
987 * @brief Hash function from a std::string.
989 T_CONCURRENTSTRTOVALMAP
991 auto CONCURRENTSTRTOVALMAP::Hasher::operator() (const std::string& s) const -> size_t
998 * @brief Compare two keys (as the underlying representation type) for equality.
1000 T_CONCURRENTSTRTOVALMAP
1002 auto CONCURRENTSTRTOVALMAP::Matcher::operator() (const val_t a, const val_t b) const -> bool
1004 // First test if the keys (pointers) themselves are equal.
1005 if (a == b) return true;
1006 // Otherwise, need to test the strings to which they point.
1007 return *keyAsString(a) == *keyAsString(b);
1011 #undef T_CONCURRENTSTRTOVALMAP
1012 #undef CONCURRENTSTRTOVALMAP
1015 } // namespace CxxUtils