ConcurrentHashmapImpl.h

Go to the documentation of this file.

// This file's extension implies that it's C, but it's really -*- C++ -*-.
/*
 * Copyright (C) 2002-2023 CERN for the benefit of the ATLAS collaboration.
 */
#ifndef CXXUTILS_CONCURRENTHASHMAPIMPL_H
#define CXXUTILS_CONCURRENTHASHMAPIMPL_H
 
 
#include "CxxUtils/bitscan.h"
#include "CxxUtils/atomic_fetch_minmax.h"
#include "CxxUtils/concepts.h"
#include <functional>
#include <cstdint>
#include <cstdlib>
#include <atomic>
#include <mutex>
#include <memory>
#include <new>
 
 
class ConcurrentHashmapImplTest;
 
 
namespace CxxUtils {
namespace detail {
 
 
using ConcurrentHashmapVal_t = uintptr_t;
 
 
#if HAVE_CONCEPTS
 
 
template <class T>
concept IsConcurrentHashmapPayload = std::is_standard_layout_v<T> &&
  std::is_trivial_v<T> &&
  sizeof (T) <= sizeof (ConcurrentHashmapVal_t);
 
 
#endif
 
 
 
class HashmapLock
  : public std::unique_lock<std::mutex>
{
public:
  using std::unique_lock<std::mutex>::unique_lock;
};
 
 
template <unsigned ENTRIES_PER_CACHELINE>
struct CHMTableIterator
{
  static  constexpr size_t ENTRIES_PER_CACHELINE_MASK = ENTRIES_PER_CACHELINE-1;
 
  CHMTableIterator (size_t hash, size_t mask, size_t maskBits, size_t probeLimit);
 
 
  size_t offset() const;
 
 
  size_t nprobes() const;
 
 
  bool next();
 
 
private:
  const size_t m_mask;
  const size_t m_boffs;
  const size_t m_stride;
  const size_t m_probeLimit;
  size_t m_bucket;
  size_t m_nprobes;
};
 
 
template <template <class> class UPDATER_,
          typename HASHER_ = std::hash<uintptr_t>,
          typename MATCHER_ = std::equal_to<uintptr_t>,
          uintptr_t NULLVAL_ = 0,
          uintptr_t TOMBSTONE_ = NULLVAL_>
class ConcurrentHashmapImpl
{
public:
  using val_t = ConcurrentHashmapVal_t;
  using Hasher_t = HASHER_;
  using Matcher_t = MATCHER_;
  static constexpr uintptr_t nullval = NULLVAL_;
  static constexpr uintptr_t tombstone = TOMBSTONE_;
  static constexpr size_t INVALID = static_cast<size_t>(-1);
 
  using Lock_t = HashmapLock;
 
 
private:
  struct entry_t {
    std::atomic<val_t> m_key;
    std::atomic<val_t> m_val;
  };
 
  static constexpr size_t CACHELINE = 64;
 
  // Ensure that entries will evenly pack a cache line.
  // If CACHELINE is a power of two, this implies that sizeof(entry_t)
  // is as well.
  static_assert (CACHELINE >= sizeof (entry_t) &&
                 CACHELINE % sizeof(entry_t) == 0);
 
  static constexpr size_t ENTRIES_PER_CACHELINE = CACHELINE / sizeof(entry_t);
  static constexpr size_t ENTRIES_PER_CACHELINE_MASK = (ENTRIES_PER_CACHELINE-1);
 
  friend class ::ConcurrentHashmapImplTest;
 
 
  class alignas(CACHELINE) Table
  {
  public:
    using TableIterator = CHMTableIterator<ENTRIES_PER_CACHELINE>;
 
 
    Table (size_t capacity,
           const Hasher_t& hasher = Hasher_t(),
           const Matcher_t& matcher = Matcher_t());
 
 
    static void* operator new (size_t, size_t capacity);
 
 
    void operator delete (void* p);
 
    
    size_t probeRead (val_t key, size_t hash) const;
 
    
    size_t probeWrite (val_t key, size_t hash, bool& insert);
 
 
    size_t capacity() const;
 
 
    const entry_t& entry (size_t offset) const;
 
 
    entry_t& entry (size_t offset);
 
 
  private:
    const size_t m_capacity;
    const size_t m_maxProbe;
    const size_t m_mask;
    const size_t m_maskBits;
    const Hasher_t& m_hasher;
    const Matcher_t& m_matcher;
    std::atomic<size_t> m_longestProbe;
    alignas(CACHELINE) entry_t m_entries[1];
  };
 
 
public:
  using Updater_t = UPDATER_<Table>;
  using Context_t = typename Updater_t::Context_t;
 
 
 
  ConcurrentHashmapImpl (Updater_t&& updater,
                         size_t capacity_in,
                         const Hasher_t& hasher,
                         const Matcher_t& matcher,
                         const typename Updater_t::Context_t& ctx);
 
 
  // Don't implement copying.
  // This should be done by derived classes, if desired.
  ConcurrentHashmapImpl (const ConcurrentHashmapImpl&) = delete;
  ConcurrentHashmapImpl& operator= (const ConcurrentHashmapImpl&) = delete;
  
 
  size_t size() const;
 
 
  size_t capacity() const;
 
 
  size_t erased() const;
 
 
  const Hasher_t& hasher() const;
 
 
  const Matcher_t& matcher() const;
 
 
  class const_iterator
  {
  public:
    const_iterator (const Table& table, bool end);
 
 
    const_iterator (const Table& table, size_t offset);
 
 
    void next();
 
 
    void prev();
 
 
    val_t key() const;
    
 
    val_t value() const;
 
 
    bool operator!= (const const_iterator& other) const;
 
 
    bool valid() const;
    
    
  private:
    const Table& m_table;
    size_t m_offset;
  };
 
 
  Lock_t lock();
 
 
  std::pair<const_iterator, bool>
  put (val_t key, size_t hash, val_t val,
       bool overwrite,
       const typename Updater_t::Context_t& ctx);
 
 
  std::pair<const_iterator, bool>
  put (const Lock_t& lock,
       val_t key, size_t hash, val_t val,
       bool overwrite,
       const typename Updater_t::Context_t& ctx);
 
 
  const_iterator get (val_t key, size_t hash) const;
 
 
  bool erase (val_t key, size_t hash);
 
 
  bool erase (const Lock_t& lock, val_t key, size_t hash);
 
 
  using const_iterator_range = std::pair<const_iterator, const_iterator>;
 
 
  const_iterator_range range() const;
 
 
  const_iterator begin() const;
 
 
  const_iterator end() const;
 
 
  const_iterator clear (size_t capacity,
                        const typename Updater_t::Context_t& ctx);
 
 
  const_iterator clear (const typename Updater_t::Context_t& ctx);
 
 
  void forceClear();
 
 
  void reserve (size_t capacity,
                const typename Updater_t::Context_t& ctx);
 
 
  void quiescent (const typename Updater_t::Context_t& ctx);
 
 
  void swap (ConcurrentHashmapImpl& other);
 
 
  Updater_t& updater();
 
 
private:
  bool grow (const Lock_t& lock, const typename Updater_t::Context_t& ctx);
 
 
  bool grow (const Lock_t& lock, size_t new_capacity, const typename Updater_t::Context_t& ctx);
 
 
  static uint64_t round_up (uint64_t);
 
 
  Updater_t m_updater;
  const Hasher_t m_hasher;
  const Matcher_t m_matcher;
  Table* m_table;
  std::atomic<size_t> m_size;
  std::atomic<size_t> m_erased;
  std::mutex m_mutex;
};
 
 
} // namespace detail
 
 
} // namespace CxxUtils
 
 
#include "CxxUtils/ConcurrentHashmapImpl.icc"
 
 
#endif // not CXXUTILS_CONCURRENTHASHMAPIMPL_H