An array of unsigned values of some bit size, packed tightly. More...

#include <PackedArray.h>

Collaboration diagram for CxxUtils::PackedArray:

Classes
class	proxy
	proxy class for representing an lvalue to an element of `PackedArray`. More...

Public Types
typedef size_t	size_type
typedef unsigned int	value_type
typedef basetype::allocator_type	allocator_type

Public Member Functions
	PackedArray (int bitsize=8, const allocator_type &allocator=allocator_type())
	Constructor.
	PackedArray (int bitsize, size_type n, value_type val=0, const allocator_type &allocator=allocator_type())
	Constructor.
void	assign (size_type n, value_type u)
	Set the container to multiple copies of the same value.
allocator_type	get_allocator () const
	Returns the allocator of the underlying vector.
size_type	size () const
	Returns the number of elements in the collection.
size_type	max_size () const
	Returns the `size()` of the largest possible collection.
size_type	capacity () const
	Returns the total number of elements that the collection can hold before needing to allocate more memory.
void	resize (size_type sz, value_type c=0)
	Resizes the collection to the specified number of elements.
bool	empty () const
	Returns `true` if the collection is empty.
void	reserve (size_type n)
	Attempt to preallocate enough memory for a specified number of elements.
value_type	get (size_type n) const
	Return the entry at index `n`.
void	set (size_type n, value_type val)
	Set the entry at index `n`.
value_type	operator[] (size_type n) const
	Access an element, as an rvalue.
proxy	operator[] (size_type n)
	Access an element, as an lvalue.
value_type	at (size_type n) const
	Access an element, as an rvalue.
proxy	at (size_type n)
	Access an element, as an lvalue.
value_type	front () const
	Access the first element in the collection as an rvalue.
value_type	back () const
	Access the last element in the collection as an rvalue.
proxy	front ()
	Access the first element in the collection as an lvalue.
proxy	back ()
	Access the last element in the collection as an lvalue.
void	push_back (value_type x)
	Add an element to the end of the collection.
void	pop_back ()
	Remove the last element from the collection.
void	swap (PackedArray &other)
	Swap this collection with another.
void	clear ()
	Erase all the elements in the collection.
void	set_bitsize (int bitsize)
	Change the bitsize of the container.
int	bitsize () const
	Return the bitsize of the container.

Private Types
typedef std::vector< unsigned int >	basetype

Private Member Functions
size_t	nbase (size_type n) const
	Calculate the number of entries in the base vector needed to hold entries with the current bitsize.
size_t	tondx (size_type n) const
	Find the index in the base vector where entry starts.
int	tooff (size_type n) const
	Find the bit offset of entry within its entry in the base vector.
value_type	doget (size_type ndx, int off) const
	Return the entry at base index `ndx/offset` `off`.
void	doset (size_type ndx, int off, value_type v)
	Set the entry at base index `ndx/offset` `off` to `v`.
void	range_check (size_type n) const
	Check that `n` is in range and throw `out_of_range` if not.

Private Attributes
int	m_bitsize
	The current bitsize of the container.
size_type	m_size
	The current number of entries in the container.
value_type	m_mask
	Mask with m_bitsize bits set.
basetype	m_vec
	Underlying vector holding the data.

Detailed Description

An array of unsigned values of some bit size, packed tightly.

When creating an instance of this class, specify the bit size of the entries. The entries will be packed so that each takes exactly that many bits. For example, if the bit size is 10, 16 entries will be packed into 5 32-bit words. The bitsize may be changed, but only if the container is empty.

Any values assigned to the array that are too large to be represented in the specified number of bits will have the high bits silently dropped.

The interface is modeled after std::vector, except that there are no iterators. They could be added if there is a need for them.

Definition at line 41 of file PackedArray.h.

Member Typedef Documentation

◆ allocator_type

typedef basetype::allocator_type CxxUtils::PackedArray::allocator_type

Definition at line 51 of file PackedArray.h.

◆ basetype

typedef std::vector<unsigned int> CxxUtils::PackedArray::basetype

private

Definition at line 45 of file PackedArray.h.

◆ size_type

typedef size_t CxxUtils::PackedArray::size_type

Definition at line 49 of file PackedArray.h.

◆ value_type

typedef unsigned int CxxUtils::PackedArray::value_type

Definition at line 50 of file PackedArray.h.

Constructor & Destructor Documentation

◆ PackedArray() [1/2]

CxxUtils::PackedArray::PackedArray	(	int	bitsize = 8,
		const allocator_type &	allocator = allocator_type() )

Constructor.

Parameters

bitsize	The size, in bits, of each element. Must be greater than zero, and not larger than the size of an unsigned int.
allocator	Allocator for the underlying vector.

Definition at line 144 of file PackedArray.cxx.

  : m_bitsize (bitsize),
    m_size (0),
    m_mask  (mask (bitsize)),
    m_vec (allocator)
{
  assert (m_bitsize > 0 && m_bitsize <= nper);
}

◆ PackedArray() [2/2]

CxxUtils::PackedArray::PackedArray	(	int	bitsize,
		size_type	n,
		value_type	val = 0,
		const allocator_type &	allocator = allocator_type() )

Constructor.

Parameters

bitsize	The size, in bits, of each element. Must be greater than zero, and not larger than the size of an unsigned int.
n	Initial number of entries in the container.
val	Value to which the initial entries are to be set.
allocator	Allocator for the underlying vector.

Definition at line 164 of file PackedArray.cxx.

  : m_bitsize (bitsize),
    m_size (n),
    m_mask  (mask (bitsize)),
    m_vec (nbase(n), 0, allocator)
{
  assert (m_bitsize > 0 && m_bitsize <= nper);
  if (val != 0) {
    for (size_type i = 0; i < n; i++)
      set (i, val);
  }
}

Member Function Documentation

◆ assign()

void CxxUtils::PackedArray::assign	(	size_type	n,
		value_type	u )

Set the container to multiple copies of the same value.

Parameters

n	Number of entries to which the container is to be set.
u	Value to which the entries are to be set.
n	Number of entries to which the container is to be set.
val	Value to which the entries are to be set.

Definition at line 186 of file PackedArray.cxx.

{
  m_size = n;
  m_vec.clear();
  m_vec.resize (nbase(n));
  if (u != 0) {
    for (size_type i = 0; i < n; i++)
      set (i, u);
  }
}

◆ at() [1/2]

PackedArray::proxy CxxUtils::PackedArray::at ( size_type n )

Access an element, as an lvalue.

Parameters

n	Array index to access.

Returns: Proxy to the element at n.

Will raise std::out_of_range if the index is out-of-bounds. Note that we return a proxy object rather than a reference.

Definition at line 361 of file PackedArray.cxx.

{
  range_check (n);
  return proxy (*this, n);
}

◆ at() [2/2]

PackedArray::value_type CxxUtils::PackedArray::at ( size_type n ) const

Access an element, as an rvalue.

Parameters

n	Array index to access.

Returns: The element at n.

Will raise std::out_of_range if the index is out-of-bounds. Note that we return a value_type rather than a reference.

Definition at line 346 of file PackedArray.cxx.

{
  range_check (n);
  return doget (tondx (n), tooff (n));
}

◆ back() [1/2]

PackedArray::proxy CxxUtils::PackedArray::back ( )

Access the last element in the collection as an lvalue.

Returns: Proxy to the last element in the collection.

No checking is done to ensure that the container is not empty. Note that we return a proxy object rather than a reference.

Definition at line 414 of file PackedArray.cxx.

{
  return proxy (*this, m_size-1);
}

◆ back() [2/2]

PackedArray::value_type CxxUtils::PackedArray::back ( ) const

Access the last element in the collection as an rvalue.

Returns: The last element in the collection.

No checking is done to ensure that the container is not empty. Note that we return a value_type rather than a reference.

Definition at line 388 of file PackedArray.cxx.

{
  return doget (tondx (m_size-1), tooff (m_size-1));
}

◆ bitsize()

int CxxUtils::PackedArray::bitsize ( ) const

Return the bitsize of the container.

Definition at line 487 of file PackedArray.cxx.

{
  return m_bitsize;
}

◆ capacity()

PackedArray::size_type CxxUtils::PackedArray::capacity ( ) const

Returns the total number of elements that the collection can hold before needing to allocate more memory.

Definition at line 229 of file PackedArray.cxx.

{
  return m_vec.capacity() * nper / m_bitsize;
}

◆ clear()

void CxxUtils::PackedArray::clear ( )

Erase all the elements in the collection.

Definition at line 462 of file PackedArray.cxx.

{
  m_size = 0;
  m_vec.clear();
}

◆ doget()

PackedArray::value_type CxxUtils::PackedArray::doget	(	size_type	ndx,
		int	off ) const

inlineprivate

Return the entry at base index ndx/offset off.

Parameters

ndx	Index of the entry in the base vector at which the packed entry starts.
off	Bit offset within that entry where the packed entry starts.

Definition at line 84 of file PackedArray.cxx.

{
  // Get the bits from the first entry.
  value_type v = m_vec[ndx] >> off;
 
  // If the packed entry wraps between two base entries, collect the bits
  // from the next base entry.
  if (m_bitsize > nper - off) {
    int bits = m_bitsize - (nper - off);
    // cppcheck-suppress shiftTooManyBits; false positive
    //    m_bitsize <= nper
    v |= ((m_vec[ndx+1] & mask(bits)) << (nper - off));
  }
 
  // Mask down to the proper number of bits.
  return v & m_mask;
}

◆ doset()

void CxxUtils::PackedArray::doset	(	size_type	ndx,
		int	off,
		value_type	v )

inlineprivate

Set the entry at base index ndx/offset off to v.

Set the entry at base index ndx/offset off.

Parameters

ndx	Index of the entry in the base vector at which the packed entry starts.
off	Bit offset within that entry where the packed entry starts.
v	Value to which the entry should be set.

Definition at line 111 of file PackedArray.cxx.

{
  // Set the bits in the first entry.
  m_vec[ndx] = (m_vec[ndx] & ~(m_mask<<off)) | ((v&m_mask) << off);
 
  // If the packed entry wraps between two base entries, set the bits
  // in the next entry.
  if (m_bitsize > nper - off) {
    value_type mask2 = mask (m_bitsize - (nper - off));
    m_vec[ndx+1] = (m_vec[ndx+1] & ~mask2) | ((v >> (nper - off)) & mask2);
  }
}

◆ empty()

bool CxxUtils::PackedArray::empty ( ) const

Returns true if the collection is empty.

Definition at line 272 of file PackedArray.cxx.

{
  return m_size == 0;
}

◆ front() [1/2]

PackedArray::proxy CxxUtils::PackedArray::front ( )

Access the first element in the collection as an lvalue.

Returns: Proxy to the first element in the collection.

No checking is done to ensure that the container is not empty. Note that we return a proxy object rather than a reference.

Definition at line 401 of file PackedArray.cxx.

{
  return proxy (*this, 0);
}

◆ front() [2/2]

PackedArray::value_type CxxUtils::PackedArray::front ( ) const

Access the first element in the collection as an rvalue.

Returns: The first element in the collection.

No checking is done to ensure that the container is not empty. Note that we return a value_type rather than a reference.

Definition at line 375 of file PackedArray.cxx.

{
  return doget (0, 0);
}

◆ get()

PackedArray::value_type CxxUtils::PackedArray::get ( size_type n ) const

Return the entry at index n.

Parameters

n	The index of the entry to retrieve.

Definition at line 293 of file PackedArray.cxx.

{
  return doget (tondx (n), tooff (n));
}

◆ get_allocator()

PackedArray::allocator_type CxxUtils::PackedArray::get_allocator ( ) const

Returns the allocator of the underlying vector.

Definition at line 201 of file PackedArray.cxx.

{
  return m_vec.get_allocator();
}

◆ max_size()

PackedArray::size_type CxxUtils::PackedArray::max_size ( ) const

Returns the size() of the largest possible collection.

Definition at line 219 of file PackedArray.cxx.

{
  return m_vec.max_size();
}

◆ nbase()

PackedArray::size_type CxxUtils::PackedArray::nbase ( size_type n ) const

inlineprivate

Calculate the number of entries in the base vector needed to hold
entries with the current bitsize.

Parameters

n	Number of packed entries desired.

Definition at line 49 of file PackedArray.cxx.

{
  return (n * m_bitsize + nper-1) / nper;
}

◆ operator[]() [1/2]

PackedArray::proxy CxxUtils::PackedArray::operator[] ( size_type n )

Access an element, as an lvalue.

Parameters

n	Array index to access.

Returns: Proxy to the element at n.

No bounds checking is done. Note that we return a proxy object rather than a reference.

Definition at line 332 of file PackedArray.cxx.

{
  return proxy (*this, n);
}

◆ operator[]() [2/2]

PackedArray::value_type CxxUtils::PackedArray::operator[] ( size_type n ) const

Access an element, as an rvalue.

Parameters

n	Array index to access.

Returns: The element at n.

No bounds checking is done. Note that we return a value_type rather than a reference.

Definition at line 318 of file PackedArray.cxx.

{
  return doget (tondx (n), tooff (n));
}

◆ pop_back()

void CxxUtils::PackedArray::pop_back ( )

Remove the last element from the collection.

Definition at line 437 of file PackedArray.cxx.

{
  --m_size;
  size_t nb = nbase (m_size);
  if (nb != m_vec.size())
    m_vec.resize (nb);
}

◆ push_back()

void CxxUtils::PackedArray::push_back ( value_type x )

Add an element to the end of the collection.

Parameters

x	The element to add to the collection.

Definition at line 424 of file PackedArray.cxx.

{
  ++m_size;
  size_t nb = nbase (m_size);
  if (nb != m_vec.size())
    m_vec.resize (nb);
  doset (tondx (m_size-1), tooff (m_size-1), x);
}

◆ range_check()

void CxxUtils::PackedArray::range_check ( size_type n ) const

private

Check that n is in range and throw out_of_range if not.

Parameters

n	Index to check.

Definition at line 129 of file PackedArray.cxx.

{
  if (n >= m_size) {
    throw_out_of_range (__PRETTY_FUNCTION__, n, m_size, this);
  }
}

◆ reserve()

void CxxUtils::PackedArray::reserve ( size_type n )

Attempt to preallocate enough memory for a specified number of elements.

Parameters

n	Number of elements required.

Definition at line 283 of file PackedArray.cxx.

{
  m_vec.reserve (nbase (n));
}

◆ resize()

void CxxUtils::PackedArray::resize	(	size_type	sz,
		value_type	c = 0 )

Resizes the collection to the specified number of elements.

Parameters

sz	The new size of the collection.
c	Value to which any new elements are to be set.

Definition at line 240 of file PackedArray.cxx.

{
  m_vec.resize (nbase (sz));
  if (sz > m_size) {
    // Making the container bigger.  Need to fill the remaining values.
    if (c != 0) {
      // Set them to something non-zero.
      for (size_t i = m_size; i < sz; i++)
        set (i, c);
    }
    else {
      // Filling the new entries with 0.
      // New elements in the base vector will have been set to 0.
      // However, we also need to zero out any remaining packed elements
      // (or piece thereof) in the last base element that was occupied
      // before the resize.
      int off = tooff (m_size);
      // Don't need to do anything if packed entries exactly fit
      // in the allocated base size.
      if (off != 0) {
        size_t ndx = tondx (m_size);
        m_vec[ndx] &= mask (off);
      }
    }
  }
  m_size = sz;
}

◆ set()

void CxxUtils::PackedArray::set	(	size_type	n,
		value_type	val )

Set the entry at index n.

Parameters

n	The index of the entry to set.
val	The new value for the entry at index `n`.

Definition at line 304 of file PackedArray.cxx.

{
  return doset (tondx (n), tooff (n), val);
}

◆ set_bitsize()

void CxxUtils::PackedArray::set_bitsize ( int bitsize )

Change the bitsize of the container.

bitsize The new bitsize.

This method may only be called when the container is empty.

Definition at line 475 of file PackedArray.cxx.

{
  assert (m_size == 0);
  assert (bitsize > 0 && bitsize <= nper);
  m_bitsize = bitsize;
  m_mask = mask (bitsize);
}

◆ size()

PackedArray::size_type CxxUtils::PackedArray::size ( ) const

Returns the number of elements in the collection.

Definition at line 210 of file PackedArray.cxx.

{
  return m_size;
}

◆ swap()

void CxxUtils::PackedArray::swap ( PackedArray & other )

Swap this collection with another.

Parameters

other The collection with which to swap.

Definition at line 450 of file PackedArray.cxx.

{
  std::swap (m_bitsize, other.m_bitsize);
  std::swap (m_size,    other.m_size);
  std::swap (m_mask,    other.m_mask);
  std::swap (m_vec,     other.m_vec);
}

◆ tondx()

PackedArray::size_type CxxUtils::PackedArray::tondx ( size_type n ) const

inlineprivate

Find the index in the base vector where entry
starts.

Parameters

n	Packed entry desired.

Definition at line 60 of file PackedArray.cxx.

{
  return (n * m_bitsize) / nper;
}

◆ tooff()

int CxxUtils::PackedArray::tooff ( size_type n ) const

inlineprivate

Find the bit offset of entry
within its entry in the base vector.

Parameters

n	Packed entry desired.

Definition at line 71 of file PackedArray.cxx.

{
  return (n * m_bitsize) % nper;
}

Member Data Documentation

◆ m_bitsize

int CxxUtils::PackedArray::m_bitsize

private

The current bitsize of the container.

Definition at line 276 of file PackedArray.h.

◆ m_mask

value_type CxxUtils::PackedArray::m_mask

private

Mask with m_bitsize bits set.

Definition at line 282 of file PackedArray.h.

◆ m_size

size_type CxxUtils::PackedArray::m_size

private

The current number of entries in the container.

Definition at line 279 of file PackedArray.h.

◆ m_vec

basetype CxxUtils::PackedArray::m_vec

private

Underlying vector holding the data.

Definition at line 285 of file PackedArray.h.

The documentation for this class was generated from the following files:

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ basetype

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ PackedArray() [1/2]

◆ PackedArray() [2/2]

Member Function Documentation

◆ assign()

◆ at() [1/2]

◆ at() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ bitsize()

◆ capacity()

◆ clear()

◆ doget()

◆ doset()

◆ empty()

◆ front() [1/2]

◆ front() [2/2]

◆ get()

◆ get_allocator()

◆ max_size()

◆ nbase()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop_back()

◆ push_back()

◆ range_check()

◆ reserve()

◆ resize()

◆ set()

◆ set_bitsize()

◆ size()

◆ swap()

◆ tondx()

◆ tooff()

Member Data Documentation

◆ m_bitsize

◆ m_mask

◆ m_size

◆ m_vec