ConcurrentRangeMap.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-2025 CERN for the benefit of the ATLAS collaboration
*/
 
 
#ifndef CXXUTILS_CONCURRENTRANGEMAP_H
#define CXXUTILS_CONCURRENTRANGEMAP_H
 
 
#include "CxxUtils/stall.h"
#include "CxxUtils/IsUpdater.h"
#include <atomic>
#include <mutex>
#include <utility>
#include <vector>
#include <memory>
#include <algorithm>
#include <functional>
#include <ranges>
 
 
namespace CxxUtils {
 

template <class T, class CONTEXT>
class IRangeMapPayloadDeleter
{
public:
  typedef void delete_function (const T*);
 

  IRangeMapPayloadDeleter (delete_function* delfcn);
 

  virtual ~IRangeMapPayloadDeleter() = default;
 

  virtual void discard (const T* p) = 0;
 

  virtual void quiescent (const CONTEXT& ctx) = 0;
 

  delete_function* delfcn() const;
 
 
private:
  delete_function* m_delfcn;
};
 
 
//*****************************************************************************
 
 
namespace detail {
 

template <class COMPARE, class RANGE, class KEY, class CONTEXT>
concept IsConcurrentRangeCompare = requires (const COMPARE& c,
                                             const RANGE& r1,
                                             const RANGE& r2,
                                             RANGE& r_nc,
                                             const KEY& k,
                                             const CONTEXT& ctx)
{
  { c(k, r2) } -> std::same_as<bool>;
  { c(r1, r2) } -> std::same_as<bool>;
  { c.inRange (k, r2) } -> std::same_as<bool>;
  { c.overlap (ctx, r1, r_nc) } -> std::same_as<int>;
  { c.extendRange (r_nc, r2) } -> std::same_as<int>;
};
 
 
} // namespace detail
 
 
//*****************************************************************************
 

template <class RANGE, class KEY, class T, class COMPARE,
          template <class> class UPDATER>
requires (detail::IsUpdater<UPDATER> &&
          detail::IsConcurrentRangeCompare<COMPARE, RANGE, KEY, typename UPDATER<int>::Context_t>)
class ConcurrentRangeMap
{
public:
  typedef RANGE key_type;
  typedef const T* mapped_type;
  typedef std::pair<RANGE, const T*> value_type;
  typedef const value_type& const_reference;
  typedef const value_type* const_pointer;
  typedef size_t size_type;
  typedef int difference_type;
  typedef COMPARE key_compare;
  typedef KEY key_query_type;
 

  typedef void delete_function (const T*);
 

  struct DeletePayload
  {
    DeletePayload (delete_function* delfcn)
      : m_delete (delfcn)
    {
    }

    template <class U>
    static void delfcn (const T* p)
    {
      delete reinterpret_cast<const U*>(p);
    }
    template <class U>
    DeletePayload (const std::default_delete<U>&)
    {
      m_delete = delfcn<U>;
    }

    void operator() (const T* p) const
    {
      m_delete (p);
    }

    delete_function* m_delete;
  };
 

  using payload_unique_ptr = std::unique_ptr<T, DeletePayload>;
 
  using const_iterator = const value_type*;
  using const_iterator_range = std::ranges::subrange<const_iterator>;
 

  class Impl
  {
  public:
    Impl (size_t capacity = 10);
 

    ~Impl() = default;
 

    value_type* data();
 

    size_t capacity() const;
 
 
  private:
    std::vector<value_type> m_data;
  };
 
  using Updater_t = UPDATER<Impl>;
  using IPayloadDeleter = CxxUtils::IRangeMapPayloadDeleter<T, typename Updater_t::Context_t>;
 

  ConcurrentRangeMap (Updater_t&& updater,
                      std::shared_ptr<IPayloadDeleter> payloadDeleter,
                      size_t capacity = 16,
                      const COMPARE& compare = COMPARE());
 

  ~ConcurrentRangeMap();
 

  IPayloadDeleter& deleter();
 

  const IPayloadDeleter& deleter() const;
 

  const_iterator find (const key_query_type& key) const;
 

  enum class EmplaceResult
  {
    SUCCESS,

    OVERLAP,

    DUPLICATE,
 
    // Existing range was extended to match the new range; new object
    // was deleted.
    EXTENDED
  };
 

  EmplaceResult emplace (const RANGE& range,
                         payload_unique_ptr ptr,
                         bool tryExtend = false,
                         const typename Updater_t::Context_t& ctx =
                           Updater_t::defaultContext());
 

  void erase (const key_query_type& key,
              const typename Updater_t::Context_t& ctx =
                Updater_t::defaultContext());
 

  int extendLastRange (const RANGE& newRange,
                       const typename Updater_t::Context_t& ctx =
                         Updater_t::defaultContext());
 

  void updateRanges (std::function<void (RANGE&)> rangeUpdater,
                     const typename Updater_t::Context_t& ctx =
                       Updater_t::defaultContext());
 

  size_t trim (const std::vector<key_query_type>& keys, bool trimall = false);
 

  void clear();
 

  size_t size() const;
 

  bool empty() const;
 

  size_t capacity() const;
 

  size_t nInserts() const;
 

  size_t maxSize() const;
 

  const_iterator_range range() const;
 

  void quiescent (const typename Updater_t::Context_t& ctx =
                    Updater_t::defaultContext());
 
 
private:
  typedef std::mutex mutex_t;
  typedef std::lock_guard<mutex_t> lock_t;
 

  const_iterator getBegin (const_iterator& last) const;
 

  void updatePointers (value_type* new_begin, value_type* new_end);
 
  
  bool anyInRange (const key_type& r,
                   const std::vector<key_query_type>& keys) const;
 

  void installImpl (std::unique_ptr<Impl> new_impl,
                    value_type* new_begin,
                    value_type* new_end,
                    const typename Updater_t::Context_t& ctx);
 
  
  int extendImpl (lock_t& lock,
                  const RANGE& extendedRange,
                    const typename Updater_t::Context_t& ctx);
 
 

  Updater_t m_updater;

  COMPARE m_compare;

  std::shared_ptr<IPayloadDeleter> m_payloadDeleter;

  Impl* m_impl;

  std::atomic<value_type*> m_begin;
  std::atomic<value_type*> m_last;

  size_t m_nInserts;
  size_t m_maxSize;

  mutex_t m_mutex;
};
 
 
} // namespace CxxUtils
 
 
#include "CxxUtils/ConcurrentRangeMap.icc"
 
 
#endif // not CXXUTILS_CONCURRENTRANGEMAP_H