TAO_Notify::Bit_Vector Class Reference

Simple bit vector. More...

#include <Bit_Vector.h>

Collaboration diagram for TAO_Notify::Bit_Vector:


Public Member Functions
	Bit_Vector ()
	The constructor.
	~Bit_Vector ()
	The destructor.
bool	is_set (const size_t location) const
	Determine if a bit at location is set.
void	set_bit (const size_t location, bool set)
	Set or unset a bit at location, growing the vector as needed.
size_t	find_first_bit (bool set) const
	Find the first bit that is either set or unset in an O(1).
Private Types
typedef ACE_UINT32	BASIC_UINT_TYPE
typedef ACE_Vector< BASIC_UINT_TYPE >	VECTOR_TYPE
	BITS_PER_WORD = 32
	BPW_LOG_2 = 5
enum	{ BITS_PER_WORD = 32, BPW_LOG_2 = 5 }
Private Member Functions
void	evaluate_firsts (const size_t location, bool set)
	Update our first set and unset bits.
size_t	find_first_bit_of (const size_t location, bool set)
Private Attributes
VECTOR_TYPE	bitvec_
size_t	size_
size_t	first_set_bit_
size_t	first_cleared_bit_

Detailed Description

Simple bit vector.

Written to support block allocation from persistent storage. Should be promoted to the ACE level to make it generally usable.

Definition at line 39 of file Bit_Vector.h.

Member Typedef Documentation

typedef ACE_UINT32 TAO_Notify::Bit_Vector::BASIC_UINT_TYPE [private]

Definition at line 41 of file Bit_Vector.h.

typedef ACE_Vector<BASIC_UINT_TYPE> TAO_Notify::Bit_Vector::VECTOR_TYPE [private]

Definition at line 42 of file Bit_Vector.h.

Member Enumeration Documentation

anonymous enum [private]

Enumerator:

BITS_PER_WORD
BPW_LOG_2

Definition at line 43 of file Bit_Vector.h.

00043        {
00044     BITS_PER_WORD = 32,
00045     BPW_LOG_2 = 5
00046   };

Constructor & Destructor Documentation

TAO_Notify::Bit_Vector::Bit_Vector ( )

The constructor.

Definition at line 10 of file Bit_Vector.cpp.

00011   : size_(0)
00012   , first_set_bit_(0)
00013   , first_cleared_bit_(0)
00014 {
00015 }

TAO_Notify::Bit_Vector::~Bit_Vector ( )

The destructor.

Definition at line 17 of file Bit_Vector.cpp.

00018 {
00019 }

Member Function Documentation

void TAO_Notify::Bit_Vector::evaluate_firsts	(	const size_t	location,
		bool	set
	)			`[private]`

Update our first set and unset bits.

Definition at line 71 of file Bit_Vector.cpp.

References find_first_bit_of(), first_cleared_bit_, and first_set_bit_.

Referenced by set_bit().

00072 {
00073   if (set)
00074   {
00075     if (this->first_cleared_bit_ == location)
00076     {
00077       this->first_cleared_bit_ = this->find_first_bit_of(location, false);
00078     }
00079     if (this->first_set_bit_ > location)
00080     {
00081       this->first_set_bit_ = location;
00082     }
00083   }
00084   else if (!set)
00085   {
00086     if (this->first_set_bit_ == location)
00087     {
00088       this->first_set_bit_ = this->find_first_bit_of(location, true);
00089     }
00090     if (this->first_cleared_bit_ > location)
00091     {
00092       this->first_cleared_bit_ = location;
00093     }
00094   }
00095 }

size_t TAO_Notify::Bit_Vector::find_first_bit ( bool set ) const

Find the first bit that is either set or unset in an O(1).

Definition at line 56 of file Bit_Vector.cpp.

References first_cleared_bit_, and first_set_bit_.

Referenced by TAO_Notify::Persistent_File_Allocator::allocate_block().

00057 {
00058   size_t result = 0;
00059   if (set)
00060   {
00061     result = this->first_set_bit_;
00062   }
00063   else
00064   {
00065     result = this->first_cleared_bit_;
00066   }
00067   return result;
00068 }

size_t TAO_Notify::Bit_Vector::find_first_bit_of	(	const size_t	location,
		bool	set
	)			`[private]`

Iterate from location to the end, finding the first bit that matches the requested set or unset value.

Definition at line 98 of file Bit_Vector.cpp.

References is_set(), and size_.

Referenced by evaluate_firsts().

00099 {
00100   size_t newloc = 0;
00101   size_t idx = 0;
00102   for (idx = location; (newloc == 0) && (idx < this->size_ + 1); idx++)
00103   {
00104     if (is_set(idx) == set)
00105     {
00106       newloc = idx;
00107     }
00108   }
00109   return newloc;
00110 }

bool TAO_Notify::Bit_Vector::is_set ( const size_t location ) const

Determine if a bit at location is set.

Definition at line 22 of file Bit_Vector.cpp.

References BITS_PER_WORD, bitvec_, BPW_LOG_2, and size_.

Referenced by find_first_bit_of().

00023 {
00024   bool result = false;
00025   if (location < this->size_)
00026   {
00027     result = (0 != (this->bitvec_[location >> BPW_LOG_2] & (1 << (location % BITS_PER_WORD))));
00028   }
00029   return result;
00030 }

void TAO_Notify::Bit_Vector::set_bit	(	const size_t	location,
		bool	set
	)

Set or unset a bit at location, growing the vector as needed.

Definition at line 33 of file Bit_Vector.cpp.

References BITS_PER_WORD, bitvec_, BPW_LOG_2, evaluate_firsts(), ACE_Vector< T, DEFAULT_SIZE >::resize(), and size_.

Referenced by TAO_Notify::Persistent_File_Allocator::free_block(), and TAO_Notify::Persistent_File_Allocator::used().

00034 {
00035   if (location >= this->size_)
00036   {
00037     if ((location >> BPW_LOG_2) >= (this->size_ >> BPW_LOG_2))
00038     {
00039       size_t need = (location >> BPW_LOG_2) - (this->size_ >> BPW_LOG_2);
00040       this->bitvec_.resize(this->bitvec_.size() + need + 1, 0);
00041     }
00042     this->size_ = location + 1;
00043   }
00044   if (set)
00045   {
00046     this->bitvec_[location >> BPW_LOG_2] |= (1 << (location % BITS_PER_WORD));
00047   }
00048   else
00049   {
00050     this->bitvec_[location >> BPW_LOG_2] &= ~(1 << (location % BITS_PER_WORD));
00051   }
00052   this->evaluate_firsts(location, set);
00053 }