ConcurrentMap.icc

Go to the documentation of this file.

/*
 * Copyright (C) 2002-2025 CERN for the benefit of the ATLAS collaboration.
 */
/**
 * @file CxxUtils/ConcurrentMap.icc
 * @author scott snyder <snyder@bnl.gov>
 * @date Jan, 2023
 * @brief Hash map from integers/pointers allowing concurrent, lockless reads.
 */
 
 
namespace CxxUtils {
 
 
#define T_CONCURRENTMAP template <class KEY, class VALUE,               \
                                  template <class> class UPDATER,       \
                                  class HASHER,                         \
                                  class MATCHER,                        \
                                  detail::ConcurrentHashmapVal_t NULLVAL, \
                                  detail::ConcurrentHashmapVal_t TOMBSTONE> \
  requires (detail::IsConcurrentHashmapPayload<KEY> &&              \
            detail::IsConcurrentHashmapPayload<VALUE> &&                \
            detail::IsUpdater<UPDATER> &&                               \
            detail::IsHash<HASHER, KEY> &&                              \
            detail::IsBinaryPredicate<MATCHER, KEY>)
 
 
#define CONCURRENTMAP ConcurrentMap<KEY, VALUE, UPDATER,        \
                                    HASHER, MATCHER,            \
                                    NULLVAL, TOMBSTONE>
 
 
/**
 * @brief Constructor.
 * @param updater Object used to manage memory
 *                (see comments at the start of the class).
 * @param capacity The initial table capacity.
 *                 (Will be rounded up to a power of two.)
 * @param ctx Execution context.
 */
T_CONCURRENTMAP
CONCURRENTMAP::ConcurrentMap (Updater_t&& updater,
                              size_type capacity /*= 64*/,
                              const Context_t& ctx
                                /* = Updater_t::defaultContext()*/) 
  : m_impl (std::move (updater),
            capacity,
            Hasher(),
            Matcher(),
            ctx)
{
}
 
 
/** 
 * @brief Constructor from another map.
 * @param updater Object used to manage memory
 *                (see comments at the start of the class).
 * @param capacity The initial table capacity of the new table.
 *                 (Will be rounded up to a power of two.)
 * @param ctx Execution context.
 *
 * (Not really a copy constructor since we need to pass @c updater.)
 */
T_CONCURRENTMAP
CONCURRENTMAP::ConcurrentMap (const ConcurrentMap& other,
                              Updater_t&& updater,
                              size_type capacity /*= 64*/,
                              const Context_t& ctx
                                /*= Updater_t::defaultContext()*/)
  : m_impl (std::move (updater),
            capacity,
            Hasher(),
            Matcher(),
            ctx)
{
  // not using reference, because our iterator doesn't return a reference
  for (const auto p : other) {
    this->put (p.first, p.second, true, ctx);
  }
}
 
 
/** 
 * @brief Constructor from a range.
 * @param f Start iterator for the range.
 * @param l End iterator for the range.
 * @param updater Object used to manage memory
 *                (see comments at the start of the class).
 * @param capacity The initial table capacity of the new table.
 *                 (Will be rounded up to a power of two.)
 * @param ctx Execution context.
 *
 * Constructor from a range of pairs.
 */
T_CONCURRENTMAP
template <class InputIterator>
CONCURRENTMAP::ConcurrentMap (InputIterator f,
                              InputIterator l,
                              Updater_t&& updater,
                              size_t capacity /*= 64*/,
                              const Context_t& ctx
                                /*= Updater_t::defaultContext()*/)
  : m_impl (std::move (updater),
            capacity,
            Hasher(),
            Matcher(),
            ctx)
{
  Lock_t lck = lock();
  for (; f != l; ++f) {
    this->put (lck, f->first, f->second, true, ctx);
  }
}
 
 
/**
 * @brief Return the number of items currently in the map.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::size() const -> size_type
{
  return m_impl.size();
}
 
 
/**
 * @brief Test if the map is currently empty.
 */
T_CONCURRENTMAP
inline
bool CONCURRENTMAP::empty() const
{
  return !m_impl.size();
}
 
 
/**
 * @brief Return the current size (capacity) of the hash table.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::capacity() const -> size_t
{
  return m_impl.capacity();
}
 
 
/**
 * @brief The number of erased elements in the current table.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::erased() const -> size_t
{
  return m_impl.erased();
}
 
 
/**
 * @brief Constructor.
 * @param it Iterator of the underlying table.
 */
T_CONCURRENTMAP
inline
CONCURRENTMAP::const_iterator::const_iterator (typename Impl_t::const_iterator it)
  : m_impl (it)
{
}
 
 
/**
 * @brief Test if this iterator is valid.
 *
 * This should be the same as testing for != end().
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::const_iterator::valid() const -> bool
{
  return m_impl.valid();
}
 
 
/**
 * @brief iterator_facade requirement: Increment the iterator.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::const_iterator::increment() -> void
{
  m_impl.next();
}
 
 
/**
 * @brief iterator_facade requirement: Decrement the iterator.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::const_iterator::decrement() -> void
{
  m_impl.prev();
}
 
 
/**
 * @brief iterator_facade requirement: Equality test.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::const_iterator::equal (const const_iterator& other) const
  -> bool
{
  return !(m_impl != other.m_impl);
}
 
 
/**
 * @brief iterator_facade requirement: Dereference the iterator.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::const_iterator::dereference() const
  -> const const_iterator_value
{
  return const_iterator_value (keyAsKey (m_impl.key()),
                               mappedAsMapped (m_impl.value()));
}
 
 
/**
 * @brief Return an iterator range covering the entire map.
 */
T_CONCURRENTMAP
auto CONCURRENTMAP::range() const -> const_iterator_range
{
  auto [begin, end] = m_impl.range();
  return const_iterator_range (begin, end);
}
 
 
/**
 * @brief Iterator at the start of the map.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::begin() const -> const_iterator
{
  return const_iterator (m_impl.begin());
}
 
 
/**
 * @brief Iterator at the end of the map.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::end() const -> const_iterator
{
  return const_iterator (m_impl.end());
}
 
 
/**
 * @brief Iterator at the start of the map.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::cbegin() const -> const_iterator
{
  return begin();
}
 
 
/**
 * @brief Iterator at the end of the map.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::cend() const -> const_iterator
{
  return end();
}
 
 
/**
 * @brief Test if a key is in the container.
 * @param key The key to test.
 */
T_CONCURRENTMAP
inline
bool CONCURRENTMAP::contains (key_type key) const
{
  return get(key).valid();
}
 
 
/**
 * @brief Return the number of times a given key is in the container.
 * @param key The key to test.
 *
 * Returns either 0 or 1, depending on whether or not the key is in the map.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::count (key_type key) const -> size_type
{
  return contains (key) ? 1 : 0;
}
 
 
/**
 * @brief Look up an element in the map.
 * @param key The element to find.
 *
 * Returns either an iterator referencing the found element or end().
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::find (key_type key) const -> const_iterator
{
  return const_iterator (this->get (key));
}
 
 
/**
 * @brief Look up an element in the map.
 * @param key The element to find.
 *
 * Returns the value associated with the key.
 * Throws @c std::out_of_range if the key does not exist in the map.
 */
T_CONCURRENTMAP
auto CONCURRENTMAP::at (key_type key) const -> mapped_type
{
  typename Impl_t::const_iterator it = this->get (key);
  if (!it.valid()) {
    throw std::out_of_range ("ConcurrentMap::at");
  }
  return mappedAsMapped (it.value());
}
 
 
/**
 * @brief Return a range of iterators with entries matching @c key.
 * @param key The element to find.
 *
 * As keys are unique in this container, this is either a single-element
 * range, or both iterators are equal to end().
 */
T_CONCURRENTMAP
auto CONCURRENTMAP::equal_range (key_type key) const
  -> std::pair<const_iterator, const_iterator>
{
  const_iterator i1 = find (key);
  const_iterator i2 = i1;
  if (i2.valid()) {
    ++i2;
  }
  return std::make_pair (i1, i2);
}
 
 
/**
 * @brief Take a lock on the container.
 *
 * Take a lock on the container.
 * The lock can then be passed to insertion methods, allowing to factor out
 * the locking inside loops.  The lock will be released when the
 * lock object is destroyed.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::lock() -> Lock_t
{
  return m_impl.lock();
}
 
 
/**
 * @brief Add an element to the map.
 * @param key The key of the new item to add.
 * @param val The value of the new item to add.
 * @param ctx Execution context.
 *
 * This will not overwrite an existing entry.
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::emplace (key_type key,
                             mapped_type val,
                             const Context_t& ctx
                               /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  return put (key, val, false, ctx);
}
 
 
/**
 * @brief Add an element to the map, with external locking.
 * @param lock The lock object returned from lock().
 * @param val The value of the new item to add.
 * @param ctx Execution context.
 *
 * This will not overwrite an existing entry.
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::emplace (const Lock_t& lock,
                             key_type key,
                             mapped_type val,
                             const Context_t& ctx
                               /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  return put (lock, key, val, false, ctx);
}
 
 
/**
 * @brief Add an element to the map, or overwrite an existing one.
 * @param key The key of the new item to add.
 * @param val The value of the new item to add.
 * @param ctx Execution context.
 *
 * This will overwrite an existing entry.
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::insert_or_assign (key_type key,
                                      mapped_type val,
                                      const Context_t& ctx
                                        /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  return put (key, val, true, ctx);
}
 
 
/**
 * @brief Add an element to the map, or overwrite an existing one,
 *        with external locking.
 * @param lock The lock object returned from lock().
 * @param key The key of the new item to add.
 * @param val The value of the new item to add.
 * @param ctx Execution context.
 *
 * This will overwrite an existing entry.
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::insert_or_assign (const Lock_t& lock,
                                      key_type key,
                                      mapped_type val,
                                      const Context_t& ctx
                                        /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  return put (lock, key, val, true, ctx);
}
 
 
/**
 * @brief Add an element to the map.
 * @param p The item to add.
 *          Should be a pair where first is the key
 *          and second is the integer value.
 *
 * This will not overwrite an existing entry.
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 *
 * For external locking, use emplace().
 */
T_CONCURRENTMAP
template <class PAIR>
inline
auto CONCURRENTMAP::insert (const PAIR& p)
  -> std::pair<const_iterator, bool>
{
  return emplace (p.first, p.second);
}
 
 
/**
 * @brief Insert a range of elements to the map.
 * @param first Start of the range.
 * @param last End of the range.
 *
 * The range should be a sequence of pairs where first is the string key
 *  and second is the integer value.
 */
T_CONCURRENTMAP
template <class InputIterator>
void CONCURRENTMAP::insert (InputIterator first, InputIterator last)
{
  Lock_t lck = lock();
  const Context_t& ctx = Updater_t::defaultContext();
  for (; first != last; ++first) {
    emplace (lck, first->first, first->second, ctx);
  }
}
 
 
/**
 * @brief Erase an entry from the table.
 * @param key The key to erase.
 *
 * Mark the corresponding entry as deleted.
 * Return true on success, false on failure (key not found).
 *
 * The tombstone value must be different from the null value.
 *
 * This may cause the key type returned by an iterator to change
 * asynchronously to the tombstone value.
 **/
T_CONCURRENTMAP
inline
bool CONCURRENTMAP::erase (key_type key)
{
  val_t kval = keyAsVal (key);
  size_t hash = m_impl.hasher() (kval);
  return m_impl.erase (kval, hash);
}
 
 
/**
 * @brief Erase an entry from the table, with external locking.
 * @param lock The lock object returned from lock().
 * @param key The key to erase.
 *
 * Mark the corresponding entry as deleted.
 * Return true on success, false on failure (key not found).
 *
 * The tombstone value must be different from the null value.
 *
 * This may cause the key type returned by an iterator to change
 * asynchronously to the tombstone value.
 **/
T_CONCURRENTMAP
inline
bool CONCURRENTMAP::erase (const Lock_t& lock, key_type key)
{
  val_t kval = keyAsVal (key);
  size_t hash = m_impl.hasher() (kval);
  return m_impl.erase (lock, kval, hash);
}
 
 
/**
 * @brief Increase the table capacity.
 * @param capacity The new table capacity.
 * @param ctx Execution context.
 *
 * No action will be taken if @c capacity is smaller
 * than the current capacity.
 */
T_CONCURRENTMAP
inline
void CONCURRENTMAP::reserve (size_type capacity,
                             const Context_t& ctx
                               /*= Updater_t::defaultContext()*/)
{
  return m_impl.reserve (capacity, ctx);
}
 
 
/**
 * @brief Increase the table capacity.
 * @param capacity The new table capacity.
 *
 * No action will be taken if @c capacity is smaller
 * than the current capacity.
 */
T_CONCURRENTMAP
inline
void CONCURRENTMAP::rehash (size_type capacity)
{
  return reserve (capacity);
}
 
 
/**
 * @brief Erase the table and change the capacity.
 * @param capacity The new table capacity.
 * @param ctx Execution context.
 */
T_CONCURRENTMAP
inline
void CONCURRENTMAP::clear (size_t capacity,
                           const Context_t& ctx /*= Updater_t::defaultContext()*/)
{
  m_impl.clear (capacity, ctx);
}
 
 
/**
 * @brief Erase the table (don't change the capacity).
 * @param ctx Execution context.
 */
T_CONCURRENTMAP
inline
void CONCURRENTMAP::clear (const Context_t& ctx /*= Updater_t::defaultContext()*/)
{
  m_impl.clear (ctx);
}
 
 
/**
 * @brief Erase the table in-place.
 *
 * This method avoids allocating a new version of the table.
 * However, it is not safe to use concurrently --- no other threads
 * may be accessing the container at the same time, either for read
 * or write.
 */
T_CONCURRENTMAP
inline
void CONCURRENTMAP::forceClear()
{
  m_impl.forceClear();
}
 
 
/**
 * @brief Called when this thread is no longer referencing anything
 *        from this container.
 * @param ctx Execution context.
 */
T_CONCURRENTMAP
inline
void CONCURRENTMAP::quiescent (const Context_t& ctx)
{
  return m_impl.quiescent (ctx);
}
 
 
/**
 * @brief Swap this container with another.
 * @param other The container with which to swap.
 *
 * This will also call swap on the Updater object; hence, the Updater
 * object must also support swap.  The Hasher and Matcher instances
 * are NOT swapped.
 *
 * This operation is NOT thread-safe.  No other threads may be accessing
 * either container during this operation.
 */
T_CONCURRENTMAP
void CONCURRENTMAP::swap (ConcurrentMap& other)
{
  return m_impl.swap (other.m_impl);
}
 
 
/**
 * @brief Access the Updater instance.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::updater() -> Updater_t&
{
  return m_impl.updater();
}
 
 
/**
 * @brief Convert an underlying key value to this type's key value.
 * @param val The underlying key value.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::keyAsKey (val_t val) -> key_type
{
  return CxxUtils::detail::UIntConv<key_type>::uintToVal (val);
}
 
 
/**
 * @brief Convert this type's key value to an underlying key value.
 * @param k The key.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::keyAsVal (key_type k) -> val_t
{
  return CxxUtils::detail::UIntConv<key_type>::valToUInt (k);
}
 
 
/**
 * @brief Convert an underlying mapped value to this type's mapped value.
 * @param val The underlying mapped value.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::mappedAsMapped (val_t val) -> mapped_type
{
  return CxxUtils::detail::UIntConv<mapped_type>::uintToVal (val);
}
 
 
/**
 * @brief Convert this type's mapped value to an underlying mapped value.
 * @param val The mapped value.
 */
T_CONCURRENTMAP
inline
auto CONCURRENTMAP::mappedAsVal (mapped_type val) -> val_t
{
  return CxxUtils::detail::UIntConv<mapped_type>::valToUInt (val);
}
 
 
/**
 * @brief Do a lookup in the table.
 * @param key The key to look up.
 *
 * Returns an iterator of the underlying map pointing at the found
 * entry or end();
 */
T_CONCURRENTMAP
auto CONCURRENTMAP::get (key_type key) const
  -> typename Impl_t::const_iterator
{
  val_t kval = keyAsVal (key);
  size_t hash = m_impl.hasher() (kval);
  return m_impl.get (kval, hash);
}
 
 
/**
 * @brief Insert / overwrite an entry in the table.
 * @param key The key of the new item to add.
 * @param val The value of the new item to add.
 * @param overwrite If true, allow overwriting an existing entry.
 * @param ctx Execution context.
 *
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 */
T_CONCURRENTMAP
auto CONCURRENTMAP::put (key_type key,
                         mapped_type val,
                         bool overwrite /*= true*/,
                         const Context_t& ctx /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  val_t kval = keyAsVal (key);
  size_t hash = m_impl.hasher() (kval);
  auto [it, flag] = m_impl.put (kval, hash,
                                mappedAsVal (val),
                                overwrite, ctx);
  return std::make_pair (const_iterator (it), flag);
}
 
 
/**
 * @brief Insert / overwrite an entry in the table, with external locking.
 * @param lock The lock object returned from lock().
 * @param key The key of the new item to add.
 * @param val The value of the new item to add.
 * @param overwrite If true, allow overwriting an existing entry.
 * @param ctx Execution context.
 *
 * The first element in the returned pair is an iterator referencing
 * the added item.  The second is a flag that is true if a new element
 * was added.
 */
T_CONCURRENTMAP
auto CONCURRENTMAP::put (const Lock_t& lock,
                         key_type key,
                         mapped_type val,
                         bool overwrite /*= true*/,
                         const Context_t& ctx /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  val_t kval = keyAsVal (key);
  size_t hash = m_impl.hasher() (kval);
  auto [it, flag] = m_impl.put (lock, kval, hash,
                                mappedAsVal (val),
                                overwrite, ctx);
  return std::make_pair (const_iterator (it), flag);
}
 
 
#undef T_CONCURRENTMAP
#undef CONCURRENTMAP
 
 
} // namespace CxxUtils