CxxUtils::pointer_list_base Class Reference

A fast way to store a variable-sized collection of pointers. More...

#include <pointer_list.h>

Inheritance diagram for CxxUtils::pointer_list_base:

Collaboration diagram for CxxUtils::pointer_list_base:

Classes
class	allocator
	Very simple allocator for use with pointer_list. More...
struct	list_block
	A single block in the list. More...

Public Types
typedef allocator	pool_type
	Alias for allocator. More...
typedef list_block::value_type	value_type
	The stored element type. More...

Public Member Functions
	pointer_list_base (pool_type &pool)
	Constructor. pool gives the allocator for this container. More...
void	push_back (value_type p)
	Add a new element to the end of the container. O(1) More...
size_t	size () const
	The current size of the container. O(1). More...
void	clear ()
	Erase the container. More...
bool	empty () const
	Test to see if the container is empty. More...

Protected Member Functions
void	firstblock ()
	Allocate the first block of the list. More...
void	nextblock ()
	Extend the list with another block. More...
list_block *	getblock ()
	Allocate a new block. More...

Protected Attributes
list_block *	m_head
	The first block in the list. More...
value_type *	m_insert
	The current insertion point in the list. More...
size_t	m_size
	The current list size. More...
allocator &	m_pool
	The list allocator. More...

Detailed Description

A fast way to store a variable-sized collection of pointers.

See pointer_list below for a summary.

Some extra detail: The list is a set of fixed-size blocks, each holding (by default) 15 pointers. At the end of each block is another pointer used to form a a linked list. We used to mark this last pointer by setting the low bit as a sentinel. But now that we control our own allocator we can instead just insist that the blocks have a size that's a power of 2 and are fully aligned. We can then test the low bits of the address to tell if we're looking at the last pointer of a block.

We then need to keep pointers to the head block, and to the current insertion position. To insert, we see if the insertion position is pointing at a block end. If so, we allocate another block, chain to it, and reset the insertion position to the beginning of the new block. Then store the pointer in the insertion position and bump it. Iterators are just pointers to the stored pointers. We use the end positions to tell when to chain to a new block. The insertion point gives the end iterator.

pointer_list is templated on the number of pointers stored in each block. We put it as a template parameter so that it can be accessed from the iterator class without having to have a reference from the iterator back to the containing list.

Definition at line 54 of file pointer_list.h.

Member Typedef Documentation

pool_type

typedef allocator CxxUtils::pointer_list_base::pool_type

Alias for allocator.

Definition at line 166 of file pointer_list.h.

value_type

typedef list_block::value_type CxxUtils::pointer_list_base::value_type

The stored element type.

Definition at line 169 of file pointer_list.h.

Constructor & Destructor Documentation

pointer_list_base()

CxxUtils::pointer_list_base::pointer_list_base

(

pool_type &

pool

)

Constructor. pool gives the allocator for this container.

Member Function Documentation

clear()

void CxxUtils::pointer_list_base::clear

(

)

Erase the container.

O(1). Note: doesn't free memory. Memory currently in use will be reused when the container is filled again.

Definition at line 89 of file pointer_list.cxx.

{
  if (m_head)
    m_insert = &m_head->m_data[0];
  m_size = 0;
}

empty()

bool CxxUtils::pointer_list_base::empty

(

)

const

Test to see if the container is empty.

firstblock()

void CxxUtils::pointer_list_base::firstblock ( )

protected

Allocate the first block of the list.

Definition at line 100 of file pointer_list.cxx.

{
  m_head = getblock();
  m_insert = &m_head->m_data[0];
}

getblock()

pointer_list_base::list_block * CxxUtils::pointer_list_base::getblock ( )

protected

Allocate a new block.

Definition at line 127 of file pointer_list.cxx.

{
  list_block* b = m_pool.allocate();
  size_t maxndx = m_pool.nelt();
 
  // Make sure only the last element has the sentinel bit set.
  std::fill (b->m_data, b->m_data + maxndx, value_type());
  b->m_data[maxndx] = 0;
 
  return b;
}

nextblock()

void CxxUtils::pointer_list_base::nextblock ( )

protected

Extend the list with another block.

m_insert should be at the end of the last block.

Definition at line 111 of file pointer_list.cxx.

{
  // There may be one already allocated.  Use it if so.
  list_block* newblock = 
    reinterpret_cast<list_block*> (*m_insert);
  if (!newblock) {
    newblock = getblock();
    *m_insert = newblock;
  }
  m_insert = &newblock->m_data[0];
}

push_back()

void CxxUtils::pointer_list_base::push_back

(

value_type

p

)

Add a new element to the end of the container. O(1)

size()

size_t CxxUtils::pointer_list_base::size

(

)

const

The current size of the container. O(1).

Member Data Documentation

m_head

list_block* CxxUtils::pointer_list_base::m_head

protected

The first block in the list.

Definition at line 191 of file pointer_list.h.

m_insert

value_type* CxxUtils::pointer_list_base::m_insert

protected

The current insertion point in the list.

Definition at line 194 of file pointer_list.h.

m_pool

allocator& CxxUtils::pointer_list_base::m_pool

protected

The list allocator.

Definition at line 200 of file pointer_list.h.

m_size

size_t CxxUtils::pointer_list_base::m_size

protected

The current list size.

Definition at line 197 of file pointer_list.h.

---

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

• pointer_list.h
• pointer_list.cxx