bslstl_simplepool

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Comparison with bdema_Pool
  • Usage
    • Example 1: Creating a Node-Based Stack

Purpose

Provide efficient allocation of memory blocks for a specific type.

Classes

• bslstl::SimplePool: memory manager that allocates memory blocks for a type

See also

bslstl_treenodepool, bdlma_pool

Description

This component implements a memory pool, bslstl::SimplePool, that allocates and manages memory blocks of for a parameterized type. A bslstl::SimplePool object maintains an internal linked list of free memory blocks, and dispenses one block for each allocate method invocation. When a memory block is deallocated, it is returned to the free list for potential reuse.

Whenever the linked list of free memory blocks is depleted, bslstl::SimplePool replenishes the list by first allocating a large, contiguous "chunk" of memory, then splitting the chunk into multiple memory blocks each having the sizeof the simple pool's parameterized type. A chunk and its constituent memory blocks can be depicted visually:

   +-----+--- memory blocks of uniform size for parameterized type
   |     |
 ----- ----- ------------
|     |     |     ...    |
 =====^=====^============
 
 \___________ __________/
             V
         a "chunk"

This pool implementation is simple because its allocation strategy is not configurable. The size of a chunk starts from 1 memory block, and doubles each time a chunk is allocated up to an implementation defined maximum number of blocks.

Comparison with bdema_Pool

There are a few differences between bslstl::SimplePool and bdema_Pool:

1. bslstl::SimplePool is parameterized on both allocator and type, which improve performance and memory usage in exchange for increase in code size.
2. bslstl::SimplePool uses the allocator through the use of bsl::allocator_traits (which is generally not relevant to non-container type.
3. bslstl::SimplePool is less configurable in order to achieve abstraction of allocation and improvement in performance.

Clients are encouraged to use bdema_Pool as bslstl::SimplePool is designed for node-based STL containers, and its pooling behavior may change according to the needs of those containers.

Usage

This section illustrates intended use for this component.

Example 1: Creating a Node-Based Stack

Suppose that we want to implement a stack with a linked list. It is expensive to allocate memory every time a node is inserted. Therefore, we can use SimplePool to efficiently manage the memory for the list.

First, we define the class that implements the stack:

/// This class defines a node-based stack of integers.
template <class ALLOCATOR = bsl::allocator<int> >
class my_Stack {
 
    // PRIVATE TYPES
 
    /// This `struct` implements a link data structure containing a
    /// value and a pointer to the next node.
    struct Node {
 
        int   d_value;   // payload value
        Node *d_next_p;  // pointer to the next node
    };
 
    typedef bslstl::SimplePool<Node, ALLOCATOR> Pool;
        // Alias for memory pool.
 
  private:
    // DATA
    Node *d_head_p;  // pointer to the first node
    int   d_size;    // size of the stack
    Pool  d_pool;    // memory manager for the stack
 
  public:
    // CREATORS
 
    /// Create an empty `my_Stack` object.  Optionally specify a
    /// `basicAllocator` used to supply memory.  If `basicAllocator` is
    /// 0, the currently installed default allocator is used.
    my_Stack(const ALLOCATOR& allocator = ALLOCATOR());
 
    // MANIPULATORS
 
    /// Insert an element with the specified value to the top of this
    /// stack.
    void push(int value);
 
    /// Remove the top element from this stack.  The behavior is
    /// undefined unless `1 <= size()`.
    void pop();
 
    // ACCESSORS
 
    /// Return the value of the element on the top of this stack.  The
    /// behavior is undefined unless `1 <= size()`.
    int top();
 
    /// Return the number of elements in this stack.
    std::size_t size();
};

Now, we define the implementation of the stack. Notice how bslstl::SimplePool is used to allocate memory in push and deallocate memory in pop:

// CREATORS
template <class ALLOCATOR>
my_Stack<ALLOCATOR>::my_Stack(const ALLOCATOR& allocator)
: d_head_p(0)
, d_size(0)
, d_pool(allocator)
{
}
 
// MANIPULATORS
template <class ALLOCATOR>
void my_Stack<ALLOCATOR>::push(int value)
{
    Node *newNode = d_pool.allocate();
 
    newNode->d_value = value;
    newNode->d_next_p = d_head_p;
    d_head_p = newNode;
 
    ++d_size;
}
 
template <class ALLOCATOR>
void my_Stack<ALLOCATOR>::pop()
{
    BSLS_ASSERT(0 != size());
 
    Node *n = d_head_p;
    d_head_p = d_head_p->d_next_p;
    d_pool.deallocate(n);
    --d_size;
}
 
// ACCESSORS
template <class ALLOCATOR>
int my_Stack<ALLOCATOR>::top()
{
    BSLS_ASSERT(0 != size());
 
    return d_head_p->d_value;
}
 
template <class ALLOCATOR>
std::size_t my_Stack<ALLOCATOR>::size()
{
    return d_size;
}

Finally, we test our stack by pushing and popping some elements:

my_Stack stack;
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
assert(5 == stack.size());
 
assert(5 == stack.top());
stack.pop();
assert(4 == stack.top());
stack.pop();
assert(3 == stack.top());
stack.pop();
assert(2 == stack.top());
stack.pop();
assert(1 == stack.top());
stack.pop();
assert(0 == stack.size());