ConcurrentBitset.cxx

Go to the documentation of this file.

/*
  Copyright (C) 2002-2022 CERN for the benefit of the ATLAS collaboration
*/
#include "CxxUtils/ConcurrentBitset.h"
 
 
namespace CxxUtils {
 
 
//*********************************************************************************
// Constructors, destructors, assignment.
 
 
ConcurrentBitset::ConcurrentBitset (bit_t nbits /*= 0*/)
  : m_impl (new (nbits) Impl (nbits))
{
}
 
 
ConcurrentBitset::ConcurrentBitset (const ConcurrentBitset& other)
  : m_impl (new ((*other.m_impl).nbits()) Impl ((*other.m_impl)))
{
}
 
 
ConcurrentBitset::ConcurrentBitset (std::initializer_list<bit_t> l,
                                    bit_t nbits /*= 0*/)
{
  if (nbits == 0) {
    // Set the size of the set based on the maximum value in the list.
    auto max_it = std::max_element (l.begin(), l.end());
    if (max_it != l.end()) {
      nbits = *max_it + 1;
    }
    // Round up.
    nbits = (nbits + BLOCKSIZE-1) & ~MASK;
  }
  m_impl = new (nbits) Impl (nbits);
  for (bit_t b : l) {
    set (b);
  }
}
 
 
ConcurrentBitset::ConcurrentBitset (ConcurrentBitset&& other)
{
  other.emptyGarbage();
  Impl* impl = other.m_impl;
  other.m_impl = nullptr;
  m_impl = impl;
}
 
 
ConcurrentBitset::~ConcurrentBitset()
{
  delete m_impl;
  emptyGarbage();
}
 
 
ConcurrentBitset& ConcurrentBitset::operator= (const ConcurrentBitset& other)
{
  if (this != &other) {
    const Impl* otherImpl = other.m_impl;
    expand (otherImpl->nbits());
    (*m_impl).assign (*otherImpl);
  }
  return *this;
}
 
 
ConcurrentBitset& ConcurrentBitset::operator= (ConcurrentBitset&& other)
{
  if (this != &other) {
    emptyGarbage();
    other.emptyGarbage();
    delete m_impl;
    Impl* impl = other.m_impl;
    other.m_impl = nullptr;
    m_impl = impl;
  }
  return *this;
}
 
 
void ConcurrentBitset::emptyGarbage()
{
  lock_t lock (m_mutex);
  for (Impl* p : m_garbage) {
    free (p);
  }
  m_garbage.clear();
}
 
 
void ConcurrentBitset::expandOol (bit_t new_nbits)
{
  // Need to take out the lock.
  lock_t lock (m_mutex);
  // Check the size again while we're holding the lock.
  bit_t nbits = (*m_impl).nbits();
  if (new_nbits > nbits) {
    // We need to expand.  Allocate a new implementation and initialize it,
    // copying from the existing implementation.
    Impl* i = new (new_nbits) Impl (*m_impl, new_nbits);
 
    // Remember that we need to delete the old object.
    m_garbage.push_back (m_impl);
 
    // Publish the new one.
    m_impl = i;
  }
}
 
 
//*********************************************************************************
// Implementation.
 
 
// 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")))
ConcurrentBitset::bit_t
ConcurrentBitset::Impl::count() const
{
  bit_t n = 0;
  for (bit_t i=0; i<m_nblocks; i++) {
    n += CxxUtils::count_ones (m_data[i]);
  }
  return n;
}
__attribute__ ((target ("default")))
#endif
ConcurrentBitset::bit_t
ConcurrentBitset::Impl::count() const
{
  bit_t n = 0;
  for (bit_t i=0; i<m_nblocks; i++) {
    n += CxxUtils::count_ones (m_data[i]);
  }
  return n;
}
 
 
bool ConcurrentBitset::Impl::none() const
{
  for (bit_t i = 0; i < m_nblocks; i++) {
    if (m_data[i]) return false;
  }
  return true;
}
 
 
bool ConcurrentBitset::Impl::all() const
{
  if (m_nblocks == 0) {
    return true;
  }
 
  // Check all blocks except the last.
  for (bit_t i = 0; i < m_nblocks-1; i++) {
    if (m_data[i] != ~static_cast<Block_t>(0)) return false;
  }
  // Special case for the last, since the last block may not be full.
  if (m_data[m_nblocks] != ones<Block_t> (m_nbits - (m_nblocks-1)*BLOCKSIZE)) {
    return false;
  }
  return true;
}
 
 
void ConcurrentBitset::Impl::set()
{
  for (bit_t i=0; i<m_nblocks; i++) {
    m_data[i].store (~static_cast<Block_t>(0), std::memory_order_relaxed);
  }
  std::atomic_thread_fence (std::memory_order_seq_cst);
  if (m_nblocks > 0) {
    m_hwm = m_nblocks-1;
  }
}
 
 
void ConcurrentBitset::Impl::flip()
{
  for (bit_t i=0; i<m_nblocks; i++) {
    m_data[i] ^= ~static_cast<Block_t>(0);
  }
  if (m_nblocks > 0) {
    m_hwm = m_nblocks-1;
  }
}
 
 
} // namespace CxxUtils