Component bslstl_simplepool [Package bslstl]

Provide efficient allocation of memory blocks for a specific type. More...

Namespaces
namespace	bslstl

---

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:

Component bslstl_treenodepool, Component 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:

  template <class ALLOCATOR = bsl::allocator<int> >
  class my_Stack {
      // This class defines a node-based stack of integers.

      // PRIVATE TYPES
      struct Node {
          // This 'struct' implements a link data structure containing a
          // value and a pointer to the next 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
      my_Stack(const ALLOCATOR& allocator = ALLOCATOR());
          // 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.

      // MANIPULATORS
      void push(int value);
          // Insert an element with the specified value to the top of this
          // stack.

      void pop();
          // Remove the top element from this stack.  The behavior is
          // undefined unless '1 <= size()'.

      // ACCESSORS
      int top();
          // Return the value of the element on the top of this stack.  The
          // behavior is undefined unless '1 <= size()'.

      std::size_t size();
          // Return the number of elements in this stack.
  };

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());