boost/detail/dynamic_bitset.hpp
// (C) Copyright Chuck Allison and Jeremy Siek 2001, 2002.
//
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all
// copies. This software is provided "as is" without express or
// implied warranty, and with no claim as to its suitability for any
// purpose.
// With optimizations by Gennaro Prota.
#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP
#define BOOST_DETAIL_DYNAMIC_BITSET_HPP
#include "boost/config.hpp"
#include "boost/detail/iterator.hpp"
#if !(defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) || defined(__BORLANDC__))
#define BOOST_DYN_BITSET_USE_FRIENDS
#endif
namespace boost {
namespace detail {
// Forward references
template <typename BlockInputIterator>
std::size_t initial_num_blocks(BlockInputIterator first,
BlockInputIterator last,
std::input_iterator_tag);
template <typename BlockForwardIterator>
std::size_t initial_num_blocks(BlockForwardIterator first,
BlockForwardIterator last,
std::forward_iterator_tag);
// The following 2 classes make sure that the bitset
// gets allocated in an exception safe manner
template <typename Allocator>
class dynamic_bitset_alloc_base {
public:
dynamic_bitset_alloc_base(const Allocator& alloc)
: m_alloc(alloc) { }
protected:
Allocator m_alloc;
};
template <typename Block, typename Allocator>
class dynamic_bitset_base :
#ifdef BOOST_DYN_BITSET_USE_FRIENDS
protected
#else
public
#endif
dynamic_bitset_alloc_base<Allocator>
{
typedef std::size_t size_type;
#ifndef BOOST_DYN_BITSET_USE_FRIENDS
public:
#endif
enum { bits_per_block = CHAR_BIT * sizeof(Block) };
public:
dynamic_bitset_base()
: m_bits(0), m_num_bits(0), m_num_blocks(0) { }
dynamic_bitset_base(size_type num_bits, const Allocator& alloc)
: dynamic_bitset_alloc_base<Allocator>(alloc),
m_bits(dynamic_bitset_alloc_base<Allocator>::
m_alloc.allocate(calc_num_blocks(num_bits), static_cast<void const *>(0))),
m_num_bits(num_bits),
m_num_blocks(calc_num_blocks(num_bits))
{
using namespace std;
memset(m_bits, 0, m_num_blocks * sizeof(Block)); // G.P.S. ask to Jeremy
}
~dynamic_bitset_base() {
if (m_bits)
this->m_alloc.deallocate(m_bits, m_num_blocks);
}
#ifdef BOOST_DYN_BITSET_USE_FRIENDS
protected:
#endif
Block* m_bits;
size_type m_num_bits;
size_type m_num_blocks;
static size_type word(size_type bit) { return bit / bits_per_block; } // [gps]
static size_type offset(size_type bit){ return bit % bits_per_block; } // [gps]
static Block mask1(size_type bit) { return Block(1) << offset(bit); }
static Block mask0(size_type bit) { return ~(Block(1) << offset(bit)); }
static size_type calc_num_blocks(size_type num_bits)
{ return (num_bits + bits_per_block - 1) / bits_per_block; }
};
// ------- count table implementation --------------
typedef unsigned char byte_t;
// only count<true> has a definition
#if 0
// This was giving Intel C++ and Borland C++ trouble -JGS
template <bool = true> struct count;
template <> struct count <true> {
#else
template <bool bogus = true>
struct count {
#endif
typedef byte_t element_type;
static const byte_t table[];
BOOST_STATIC_CONSTANT (unsigned int, max_bit = 8); // must be a power of two
};
//typedef count<true> table_t;
// the table: wrapped in a class template, so
// that it is only instantiated if/when needed
//
#if 0
// Intel C++ and Borland C++ trouble -JGS
template <>
const byte_t count <true>::table[] =
#else
template <bool bogus>
const byte_t count<bogus>::table[] =
#endif
{
// Automatically generated by GPTableGen.exe v.1.0
//
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
// -------------------------------------------------------
template <typename BlockInputIterator>
std::size_t initial_num_blocks(BlockInputIterator first,
BlockInputIterator last,
std::input_iterator_tag)
{
return 0;
}
template <typename BlockForwardIterator>
std::size_t initial_num_blocks(BlockForwardIterator first,
BlockForwardIterator last,
std::forward_iterator_tag)
{
std::size_t n = 0;
while (first != last)
++first, ++n;
return n;
}
template <typename BlockInputIterator>
std::size_t initial_num_blocks(BlockInputIterator first,
BlockInputIterator last)
{
typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
return initial_num_blocks(first, last, cat);
}
} // namespace detail
} // namespace boost
#endif // BOOST_DETAIL_DYNAMIC_BITSET_HPP