A fast way to store a variable-sized collection of pointers. More...
#include <pointer_list.h>
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_block * | getblock () |
| Allocate a new block. | |
Protected Attributes | |
| list_block * | m_head |
| The first block in the list. | |
| value_type * | m_insert |
| The current insertion point in the list. | |
| size_t | m_size |
| The current list size. | |
| allocator & | m_pool |
| The list allocator. | |
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.
| CxxUtils::pointer_list_base::pointer_list_base | ( | pool_type & | pool | ) | [inline] |
| 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.
1.6.1
