Implementation of a concurrent `std::bitset` using Intel TBB.

concurrent_bitset.hpp

/**
 * @file   concurrent_bitset.hpp
 *
 * Implementation of a concurrent @c std::bitset using Intel TBB.
 *
 * @author  riccardo.murri@gmail.com
 * @version $Revision$
 */
/*
 * Copyright (c) 2011 Riccardo Murri <riccardo.murri@gmail.com>. All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 * See http://www.gnu.org/licenses/gpl.html for licence details.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
 *
 */

#ifndef CONCURRENT_BITSET_HPP
#define CONCURRENT_BITSET_HPP


#include <tbb/spin_rw_mutex.h>

#include <cassert>
#include <util> // std::pair
#include <stdexcept>



/** A thread-safe @c std::bitset clone, using @a P independent locks
    to reduce contention. 

    The total bitset is split into @a N/P
    independent @c std::bitset instances, each of which is protected
    by a mutex.  Two threads accessing the same @c concurrent_bitset
    instance will clash (and one of them will block) iff they happen
    to access bits mapped to the same @c std::bitset storage.  
      
    Methods not (yet?) implemented from the @c std::bitset interface:
    - @c{bitset(unsigned long), bitset(std::string)} constructors
    - all operators
    - non-const operator[]
    - @c to_ulong
    - @c to_string

    @seealso std::bitset
*/
template < std::size_t N, std::size_t P = 32 >
class concurrent_bitset {
public:
  /** Constructor: initializes all bits to 0. */
  concurrent_bitset();

  /** Destructor. */
  ~concurrent_bitset();

  /** Return the value of the bit at position @a pos. */
  bool operator[] (std::size_t pos) const;
    
  /** Return the value of the bit at position @a pos, or throw an @c
      out_of_range exception if @a pos is greater than the total
      bitset size. */
  bool test (std::size_t pos) const;

  /** Return the total size @a N of the bitset. */
  std::size_t size() const;

  /** Return the total number of bits set to 1. */
  std::size_t count() const;

  /** Return @c true if a bit is set to 1. */
  bool any() const;

  /** Return @c true if no bit is set. */
  bool none() const;
    
  /** Set all bits to 1. */
  concurrent_bitset<N,P>& set ();

  /** Store @a val as the new value for the bit at position @a pos. */
  concurrent_bitset<N,P>& set (std::size_t pos, bool val = true);

  /** Reset all bits to 0. */
  concurrent_bitset<N,P>& reset ();

  /** Reset bit at position @a pos to 0. */
  concurrent_bitset<N,P>& reset (std::size_t pos);

  /** Flip all bits. That is, change all 0s for 1s and all 1s for 0s. */
  concurrent_bitset<N,P>& flip ();

  /** Flip bit at position @a pos: reset it if set, set it if reset. */
  concurrent_bitset<N,P>& flip (std::size_t pos);

protected:
  /** Compute where position @a gpos in the whole @c
      concurrent_bitset is stored in the @c storage array.  Output
      value @a n is the index of @c storage array where the bitset
      holding the values is, and @a lpos is the position of the bit
      in there. */
  void _global_to_local_pos(std::size_t const gpos, std::size_t& n, std::size_t& lpos);

private:

  typedef tbb::spin_rw_mutex __mutex_t;

  typedef std::pair< __mutex_t, std::bitset<(N/P)+1> > __lk_bitset_t;

  /** Actual storage of mutexes and bitsets. */
  __lk_bitset_t __storage[P];
};



//
// implementation
//


template <std::size_t N, std::size_t P>
concurrent_bitset<N,P>::concurrent_bitset() 
  : storage()
{
  // nothing to do
}


template <std::size_t N, std::size_t P>
concurrent_bitset<N,P>::~concurrent_bitset()
{
  // nothing to do
}


template <std::size_t N, std::size_t P>
inline void 
concurrent_bitset<N,P>::_global_to_local_pos(std::size_t const gpos, 
                                             std::size_t& n, std::size_t& lpos)
{
  assert(0 <= gpos);
  assert(gpos < N);
  n = gpos % P;
  lpos = gpos / P;
}


template <std::size_t N, std::size_t P>
inline std::size_t
concurrent_bitset<N,P>::size() const
{
  return P;
}


template <std::size_t N, std::size_t P>
inline bool
concurrent_bitset<N,P>::operator[] (std::size_t pos) const
{
  std::size_t n, lpos;
  _global_to_local_pos_(pos, n, lpos);

  __mutex_t::scoped_lock lk(__storage[n].first, false); // read-only lock
  const bool result = __storage[n].second[lpos];
  lk.release();
  return result;
}
  

template <std::size_t N, std::size_t P>
inline bool
concurrent_bitset<N,P>::test (std::size_t pos) const
{
  if (pos >= N or pos < 0)
    throw new std::out_of_range("concurrent_bitset::test");
  return (*this)[pos];
}
  

template <std::size_t N, std::size_t P>
inline concurrent_bitset<N,P>& 
concurrent_bitset<N,P>::set(std::size_t pos, bool val)
{
  std::size_t n, lpos;
  _global_to_local_pos_(pos, n, lpos);
    
  __mutex_t::scoped_lock lk(__storage[n].first, true); // read-write lock
  __storage[n].second.set(lpos);
  return *this;
}


template <std::size_t N, std::size_t P>
inline concurrent_bitset<N,P>& 
concurrent_bitset<N,P>::reset(std::size_t pos)
{
  std::size_t n, lpos;
  _global_to_local_pos_(pos, n, lpos);
    
  __mutex_t::scoped_lock lk(__storage[n].first, true); // read-write lock
  __storage[n].second.reset(lpos);
  return *this;
}


template <std::size_t N, std::size_t P>
inline concurrent_bitset<N,P>& 
concurrent_bitset<N,P>::flip(std::size_t pos) 
{
  std::size_t n, lpos;
  _global_to_local_pos_(pos, n, lpos);
    
  __mutex_t::scoped_lock lk(__storage[n].first, true); // read-write lock
  __storage[n].second.flip(lpos);
  return *this;
}


template <std::size_t N, std::size_t P>
inline concurrent_bitset<N,P>& 
concurrent_bitset<N,P>::set()
{
  for (std::size_t n = 0; n < P; ++n) {
    __mutex_t::scoped_lock lk(__storage[n].first, true); // read-write lock
    __storage[n].second.set();
  }
  return *this;
}


template <std::size_t N, std::size_t P>
inline concurrent_bitset<N,P>& 
concurrent_bitset<N,P>::reset()
{
  for (std::size_t n = 0; n < P; ++n) {
    __mutex_t::scoped_lock lk(__storage[n].first, true); // read-write lock
    __storage[n].second.reset();
  }
  return *this;
}


template <std::size_t N, std::size_t P>
inline concurrent_bitset<N,P>& 
concurrent_bitset<N,P>::flip()
{
  for (std::size_t n = 0; n < P; ++n) {
    __mutex_t::scoped_lock lk(__storage[n].first, true); // read-write lock
    __storage[n].second.flip();
  }
  return *this;
}


template <std::size_t N, std::size_t P>
inline std::size_t
concurrent_bitset<N,P>::count() const
{
  std::size_t count = 0;
  for (std::size_t n = 0; n < P; ++n) {
    __mutex_t::scoped_lock lk(__storage[n].first, false); // read-only lock
    count += __storage[n].second.count();
  }
  return count;
}


template <std::size_t N, std::size_t P>
inline bool
concurrent_bitset<N,P>::any() const
{
  for (std::size_t n = 0; n < P; ++n) {
    __mutex_t::scoped_lock lk(__storage[n].first, false); // read-only lock
    if (__storage[n].second.any())
      return true;
  }
  return false;
}


template <std::size_t N, std::size_t P>
inline bool
concurrent_bitset<N,P>::none() const
{
  for (std::size_t n = 0; n < P; ++n) {
    __mutex_t::scoped_lock lk(__storage[n].first, false); // read-only lock
    if (not __storage[n].second.none())
      return false;
  }
  return true;
}


#endif // CONCURRENT_BITSET_HPP