ConcurrentPtrSet.icc

Go to the documentation of this file.

/*
 * Copyright (C) 2002-2025 CERN for the benefit of the ATLAS collaboration.
 */
/**
 * @file CxxUtils/ConcurrentPtrSet.icc
 * @author scott snyder <snyder@bnl.gov>
 * @date Jul, 2022
 * @brief A set of pointers, alowing concurrent, lockless reads.
 */
 
 
namespace CxxUtils {
 
 
#define T_CONCURRENTPTRSET template <class VALUE, template <class> class UPDATER> \
  requires (detail::IsUpdater<UPDATER>)
 
 
#define CONCURRENTPTRSET ConcurrentPtrSet<VALUE, UPDATER>
 
 
/**
 * @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_CONCURRENTPTRSET
CONCURRENTPTRSET::ConcurrentPtrSet (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 set.
 * @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_CONCURRENTPTRSET
CONCURRENTPTRSET::ConcurrentPtrSet (const ConcurrentPtrSet& other,
                                    Updater_t&& updater,
                                    size_type capacity /*= 64*/,
                                    const Context_t& ctx
                                      /*= Updater_t::defaultContext()*/)
  : m_impl (std::move (updater),
            capacity,
            Hasher(),
            Matcher(),
            ctx)
{
  for (const auto p : other) {
    this->put (p, 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.
 */
T_CONCURRENTPTRSET
template <class InputIterator>
CONCURRENTPTRSET::ConcurrentPtrSet (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, ctx);
  }
}
 
 
/**
 * @brief Destructor.
 */
T_CONCURRENTPTRSET
CONCURRENTPTRSET::~ConcurrentPtrSet()
{
}
 
 
/**
 * @brief Return the number of items currently in the set.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::size() const -> size_type
{
  return m_impl.size();
}
 
 
/**
 * @brief Test if the set is currently empty.
 */
T_CONCURRENTPTRSET
inline
bool CONCURRENTPTRSET::empty() const
{
  return !m_impl.size();
}
 
 
/**
 * @brief Return the current size (capacity) of the hash table.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::capacity() const -> size_t
{
  return m_impl.capacity();
}
 
 
/**
 * @brief Constructor.
 * @param it Iterator of the underlying table.
 */
T_CONCURRENTPTRSET
inline
CONCURRENTPTRSET::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_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::const_iterator::valid() const -> bool
{
  return m_impl.valid();
}
 
 
/**
 * @brief iterator_facade requirement: Increment the iterator.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::const_iterator::increment() -> void
{
  m_impl.next();
}
 
 
/**
 * @brief iterator_facade requirement: Decrement the iterator.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::const_iterator::decrement() -> void
{
  m_impl.prev();
}
 
 
/**
 * @brief iterator_facade requirement: Dereference the iterator.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::const_iterator::dereference() const
  -> key_type
{
  return keyAsPtr (m_impl.key());
}
 
 
/**
 * @brief iterator_facade requirement: Equality test.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::const_iterator::equal (const const_iterator& other) const
  -> bool
{
  return !(m_impl != other.m_impl);
}
 
 
/**
 * @brief Return an iterator range covering the entire set.
 */
T_CONCURRENTPTRSET
auto CONCURRENTPTRSET::range() const -> const_iterator_range
{
  auto [begin, end] = m_impl.range();
  return const_iterator_range (begin, end);
}
 
 
/**
 * @brief Iterator at the start of the set.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::begin() const -> const_iterator
{
  return const_iterator (m_impl.begin());
}
 
 
/**
 * @brief Iterator at the end of the set.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::end() const -> const_iterator
{
  return const_iterator (m_impl.end());
}
 
 
/**
 * @brief Iterator at the start of the set.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::cbegin() const -> const_iterator
{
  return begin();
}
 
 
/**
 * @brief Iterator at the end of the set.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::cend() const -> const_iterator
{
  return end();
}
 
 
/**
 * @brief Test if a key is in the container.
 * @param key The key to test.
 */
T_CONCURRENTPTRSET
inline
bool CONCURRENTPTRSET::contains (const const_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 set.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::count (const const_key_type key) const -> size_type
{
  return contains (key) ? 1 : 0;
}
 
 
/**
 * @brief Look up an element in the set.
 * @param key The element to find.
 *
 * Returns either an iterator referencing the found element or end().
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::find (const const_key_type key) const -> const_iterator
{
  return const_iterator (this->get (key));
}
 
 
/**
 * @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_CONCURRENTPTRSET
auto CONCURRENTPTRSET::equal_range (const const_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_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::lock() -> Lock_t
{
  return m_impl.lock();
}
 
 
/**
 * @brief Add an element to the set.
 * @param key The key 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_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::emplace (const key_type key,
                                const Context_t& ctx
                                  /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  return put (key, ctx);
}
 
 
/**
 * @brief Add an element to the set, with external locking.
 * @param lock The lock object returned from lock().
 * @param key The key 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_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::emplace (const Lock_t& lock,
                                const key_type key,
                                const Context_t& ctx
                                  /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  return put (lock, key, ctx);
}
 
 
/**
 * @brief Add an element to the set.
 * @param p The item to add.
 *
 * 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.
 *
 * This is the same as emplace().  Use that for the case of external locking.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::insert (const key_type p)
  -> std::pair<const_iterator, bool>
{
  return emplace (p);
}
 
 
/**
 * @brief Insert a range of elements to the set.
 * @param first Start of the range.
 * @param last End of the range.
 */
T_CONCURRENTPTRSET
template <class InputIterator>
void CONCURRENTPTRSET::insert (InputIterator first, InputIterator last)
{
  Lock_t lck = lock();
  const Context_t& ctx = Updater_t::defaultContext();
  for (; first != last; ++first) {
    emplace (lck, *first, ctx);
  }
}
 
 
/**
 * @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_CONCURRENTPTRSET
inline
void CONCURRENTPTRSET::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_CONCURRENTPTRSET
inline
void CONCURRENTPTRSET::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_CONCURRENTPTRSET
inline
void CONCURRENTPTRSET::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_CONCURRENTPTRSET
inline
void CONCURRENTPTRSET::clear (const Context_t& ctx /*= Updater_t::defaultContext()*/)
{
  m_impl.clear (ctx);
}
 
 
/**
 * @brief Called when this thread is no longer referencing anything
 *        from this container.
 * @param ctx Execution context.
 */
T_CONCURRENTPTRSET
inline
void CONCURRENTPTRSET::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.
 *
 * This operation is NOT thread-safe.  No other threads may be accessing
 * either container during this operation.
 */
T_CONCURRENTPTRSET
void CONCURRENTPTRSET::swap (ConcurrentPtrSet& other)
{
  m_impl.swap (other.m_impl);
}
 
 
/**
 * @brief Access the Updater instance.
 */
T_CONCURRENTPTRSET
auto CONCURRENTPTRSET::updater() -> Updater_t&
{
  return m_impl.updater();
}
 
 
/**
 * @brief Convert an underlying key value to a pointer.
 * @param val The underlying key value.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::keyAsPtr (val_t val) -> key_type
{
  return reinterpret_cast<key_type> (val);
}
 
 
/**
 * @brief Convert a pointer to an underlying key value.
 * @param val The pointer.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::keyAsVal (const const_key_type p) -> val_t
{
  return reinterpret_cast<val_t> (p);
}
 
 
/**
 * @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_CONCURRENTPTRSET
auto CONCURRENTPTRSET::get (const const_key_type key) const
  -> typename Impl_t::const_iterator
{
  size_t hash = m_impl.hasher() (key);
  return m_impl.get (keyAsVal(key), hash);
}
 
 
/**
 * @brief Insert an entry in the table.
 * @param key The new item to add.
 * @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_CONCURRENTPTRSET
auto CONCURRENTPTRSET::put (const key_type key,
                            const Context_t& ctx /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  size_t hash = m_impl.hasher() (key);
  auto [it, flag] = m_impl.put (keyAsVal(key), hash,
                                0,
                                false, ctx);
  return std::make_pair (const_iterator (it), flag);
}
 
 
/**
 * @brief Insert an entry in the table, with external locking.
 * @param lock The lock object returned from lock().
 * @param key The new item to add.
 * @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_CONCURRENTPTRSET
auto CONCURRENTPTRSET::put (const Lock_t& lock,
                            const key_type key,
                            const Context_t& ctx /*= Updater_t::defaultContext()*/)
  -> std::pair<const_iterator, bool>
{
  size_t hash = m_impl.hasher() (key);
  auto [it, flag] = m_impl.put (lock,
                                keyAsVal(key), hash,
                                0,
                                false, ctx);
  return std::make_pair (const_iterator (it), flag);
}
 
 
/**
 * @brief Hash function from the underlying representation type.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::Hasher::operator() (const val_t p) const -> size_t
{
  return m_hash (keyAsPtr(p));
}
 
 
/**
 * @brief Hash function from a pointer.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::Hasher::operator() (const const_key_type p) const -> size_t
{
  return m_hash (p);
}
 
 
/**
 * @brief Compare two keys (as the underlying representation type) for equality.
 */
T_CONCURRENTPTRSET
inline
auto CONCURRENTPTRSET::Matcher::operator() (const val_t a, const val_t b) const -> bool
{
  return a == b;
}
 
 
#undef T_CONCURRENTPTRSET
#undef CONCURRENTPTRSET
 
 
} // namespace CxxUtils