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
*/
/*
 */
// $Id$
#ifndef CXXUTILS_CONCURRENTBITSET_H
#define CXXUTILS_CONCURRENTBITSET_H
 
 
#include "CxxUtils/atomic_fetch_minmax.h"
#include "CxxUtils/features.h"
#include "CxxUtils/bitscan.h"
#include "CxxUtils/ones.h"
#include <climits>
#include <vector>
#include <algorithm>
#include <iterator>
#include <atomic>
#include <mutex>
#include <memory>
#include <type_traits>
#include <cstddef>
 
 
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;
 
 
    // Use popcnt instruction if available.  This ugliness needed
    // because our default compilation options do not enable
    // use of this instruction.
#if defined(__x86_64__) && HAVE_FUNCTION_MULTIVERSIONING
 
    __attribute__ ((target ("popcnt")))
    bit_t count() const;
    __attribute__ ((target ("default")))
#endif
    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