ConcurrentBitset.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-2020 CERN for the benefit of the ATLAS collaboration
*/
/*
 */
 
 
#ifndef CXXUTILS_CONCURRENTBITSET_H
#define CXXUTILS_CONCURRENTBITSET_H
 
 
#include "CxxUtils/atomic_fetch_minmax.h"
#include "CxxUtils/features.h"
#include "CxxUtils/ones.h"
#include <climits>
#include <vector>
#include <algorithm>
#include <iterator>
#include <atomic>
#include <mutex>
#include <memory>
#include <type_traits>
#include <cstddef>
#include <bit>
 
 
namespace CxxUtils {
 

class ConcurrentBitset
{
private:
  // Forward declaration of implementation class.
  class Impl;

  typedef unsigned long Block_t;

  static const size_t BLOCKSIZE = sizeof(Block_t) * CHAR_BIT;

  static const size_t MASK = BLOCKSIZE-1;
 
 
  static_assert (std::atomic<Block_t>::is_always_lock_free);
 
public:
  typedef size_t bit_t;
 
 
  //========================================================================
 

  ConcurrentBitset (bit_t nbits = 0);
 

  ConcurrentBitset (const ConcurrentBitset& other);
 

  ConcurrentBitset (std::initializer_list<bit_t> l, bit_t nbits = 0);
 

  ConcurrentBitset (ConcurrentBitset&& other);
 

  ~ConcurrentBitset();
 

  ConcurrentBitset& operator= (const ConcurrentBitset& other);
 

  ConcurrentBitset& operator= (ConcurrentBitset&& other);
 

  void emptyGarbage();
 

  //========================================================================
 

  bit_t capacity() const;
 

  bit_t count() const;
 

  bit_t size() const;
 

  bool test (bit_t bit) const;
 

  size_t count (bit_t bit) const;
 

  bool empty() const;
 

  bool none() const;
 

  bool all() const;
 

  bool any() const;
 

  //========================================================================
 

  ConcurrentBitset& set (bit_t bit);
 

  ConcurrentBitset& reset (bit_t bit);
 

  ConcurrentBitset& erase (bit_t bit);
 

  ConcurrentBitset& flip (bit_t bit);
 

  ConcurrentBitset& set (bit_t bit, bool val);
 

  //========================================================================
 

  ConcurrentBitset& clear();
 

  ConcurrentBitset& reset();
 

  ConcurrentBitset& set();
 

  ConcurrentBitset& flip();
 

  ConcurrentBitset& operator&= (const ConcurrentBitset& other);
 

  ConcurrentBitset& operator|= (const ConcurrentBitset& other);
 
  
  ConcurrentBitset& operator^= (const ConcurrentBitset& other);
 

  ConcurrentBitset& operator-= (const ConcurrentBitset& other);
 

  ConcurrentBitset operator~() const;
 

  //========================================================================
 

  bool operator== (const ConcurrentBitset& other) const;
 

  bool operator!= (const ConcurrentBitset& other) const;
 

  //========================================================================
 

  ConcurrentBitset& insert (bit_t bit, bit_t new_nbits = 0);
 

  // The enable_if is needed to keep this something like
  //    bs.insert (1, 2)
  // from matching this overload.
  template <class ITERATOR,
            typename = typename std::enable_if<
              std::is_base_of<
                typename std::forward_iterator_tag,
                typename std::iterator_traits<ITERATOR>::iterator_category
                >::value> >
  ConcurrentBitset& insert (ITERATOR beg, ITERATOR end, bit_t new_nbits = 0);
 

  ConcurrentBitset& insert (std::initializer_list<bit_t> l, bit_t new_nbits = 0);
 

  ConcurrentBitset& insert (const ConcurrentBitset& other);
 
  
  //========================================================================
 

  class reference
  {
  private:
    friend class ConcurrentBitset;
 

    reference (Impl& impl, bit_t bit);
 
 
  public:
    reference& operator= (bool val) noexcept;
 

    reference& operator= (const reference& r) noexcept;
 

    operator bool() const noexcept;
 

    bool operator~() const noexcept;
 

    reference& flip() noexcept;
 
 
  private:
    std::atomic<Block_t>* m_block;

    Block_t m_mask;
  };
 

  bool operator[] (bit_t bit) const;
  

  reference operator[] (bit_t bit);
 
  
  //========================================================================
 

  struct const_iterator
  {
    typedef std::forward_iterator_tag iterator_category;
    typedef size_t value_type;
    typedef ptrdiff_t difference_type;
    typedef const value_type* pointer;
    typedef const value_type& reference;
 
 
  private:
    friend ConcurrentBitset;
 

    const_iterator (Block_t cache,
                    bit_t bit,
                    const std::atomic<Block_t>* data,
                    const std::atomic<Block_t>* end);
 
 
  public:
    bit_t operator*() const;
 

    const_iterator& operator++();
 

    const_iterator operator++(int);
 

    bool operator== (const const_iterator& other) const;
 

    bool operator!= (const const_iterator& other) const;
 
 
  private:
    Block_t m_cache;

    bit_t m_bit;

    const std::atomic<Block_t>* m_data;
 

    const std::atomic<Block_t>* m_end;
  };
 

  const_iterator begin() const;
 

  const_iterator end() const;
 

  const_iterator find (bit_t bit) const;
 
 

private:
  //========================================================================
 

  static bit_t nBlocks (bit_t nbits);
 

  Impl* newImpl (bit_t nbits);
 

  void expand (bit_t new_nbits);
 

  void expandOol (bit_t new_nbits);
 

  class Impl
  {
  public:
    void* operator new (size_t /*sz*/, bit_t nbits);
 
 
    /*
     * @brief Free an Impl structure.
     * @param p Pointer to the object to free.
     */
    void operator delete (void* p);
 
    
    Impl (bit_t nbits);
 

    Impl (const Impl& other, bit_t nbits = 0);
 
 
    // Assignment is unimplemented.
    Impl& operator= (const Impl&) = delete;
 

    void assign (const Impl& other);
 

    bit_t nbits() const;
 

    bool test (bit_t bit) const;
 

    bit_t count() const;
 

    bool none() const;
 
    
    bool all() const;
 

    std::atomic<Block_t>* block (bit_t bit);
 

    void set (bit_t bit);
 
    
    void reset (bit_t bit);
 

    void flip (bit_t bit);
 

    void clear();
 

    void set();
 

    void flip();
 
 
    typedef void operator_t (std::atomic<Block_t>& a, Block_t v);
    void operate (operator_t op, const Impl& other);
 

    bool operator== (const Impl& other) const;
 
 

    const_iterator begin() const;
 

    const_iterator end() const;
 

    const_iterator find (bit_t bit) const;
 
 
  private:
    size_t m_nbits;

    size_t m_nblocks;

    std::atomic<size_t> m_hwm;

    std::atomic<Block_t> m_data[1];
  };
 

 
 
private:
  std::atomic<Impl*> m_impl;

  std::vector<Impl*> m_garbage;

  typedef std::mutex mutex_t;
  typedef std::lock_guard<mutex_t> lock_t;
  mutex_t m_mutex;
};
 
 
} // namespace CxxUtils
 
 
#include "CxxUtils/ConcurrentBitset.icc"
 
  
#endif // not CXXUTILS_CONCURRENTBITSET_H