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:
CxxUtils::pointer_list< NELT >

List of all members.

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.
typedef list_block::value_type value_type
 The stored element type.

Public Member Functions

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

Protected Member Functions

void firstblock ()
 Allocate the first block of the list.
void nextblock ()
list_blockgetblock ()
 Allocate a new block.

Protected Attributes

list_blockm_head
 The first block in the list.
value_typem_insert
 The current insertion point in the list.
size_t m_size
 The current list size.
allocatorm_pool
 The list allocator.

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.


Constructor & Destructor Documentation

CxxUtils::pointer_list_base::pointer_list_base ( pool_type pool  )  [inline]

Constructor. pool gives the allocator for this container.

Constructor.

Parameters:
pool The allocator for this container.

Member Function Documentation

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.

void CxxUtils::pointer_list_base::nextblock (  )  [protected]

Extend the list with another block. m_insert should be at the end of the last block.


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on 1 Dec 2017 for RootCore Packages by  doxygen 1.6.1