bslstl_bidirectionalnodepool

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Memory Allocation
  • Usage
    • Example 1: Creating a Linked List Container

Purpose

Provide efficient creation of nodes used in a node-based container.

Classes

• bslstl::BidirectionalNodePool: memory manager to allocate hash table nodes

See also

bslstl_simplepool

Description

This component implements a mechanism, BidirectionalNodePool, that creates and destroys bslalg::BidirectionalListNode objects holding objects of a (template parameter) type VALUE for use in hash-table-based containers.

A BidirectionalNodePool uses a memory pool provided by the bslstl_simplepool component in its implementation to provide memory for the nodes (see bslstl_simplepool ).

Memory Allocation

BidirectionalNodePool uses an allocator of the (template parameter) type ALLOCATOR specified at construction to allocate memory. BidirectionalNodePool supports allocators meeting the requirements of the C++ standard allocator requirements ([allocator.requirements], C++11 17.6.3.5).

If ALLOCATOR is bsl::allocator and the (template parameter) type VALUE defines the bslma::UsesBslmaAllocator trait, then the bslma::Allocator object specified at construction will be supplied to constructors of the (template parameter) type VALUE in the cloneNode method and emplaceIntoNewNode method overloads.

Usage

This section illustrates intended use of this component.

Example 1: Creating a Linked List Container

Suppose that we want to define a bidirectional linked list that can hold elements of a template parameter type. bslstl::BidirectionalNodePool can be used to create and destroy nodes that make up a linked list.

First, we create an elided definition of the class template MyList:

#include <bslalg_bidirectionallinklistutil.h>
 
/// This class template implements a bidirectional linked list of
/// element of the (template parameter) type `VALUE`.  The memory used
/// will be allocated from an allocator of the (template parameter) type
/// `ALLOCATOR` specified at construction.
template <class VALUE, class ALLOCATOR>
class MyList {
 
  public:
    // TYPES
 
    /// This `typedef` is an alias to the type of the linked list node.
    typedef bslalg::BidirectionalNode<VALUE> Node;
 
  private:
    // TYPES
 
    /// This `typedef` is an alias to the type of the memory pool.
    typedef bslstl::BidirectionalNodePool<VALUE, ALLOCATOR> Pool;
 
    /// This `typedef` is an alias to the utility `struct` providing
    /// functions for constructing and manipulating linked lists.
    typedef bslalg::BidirectionalLinkListUtil               Util;
 
    /// This `typedef` is an alias to the type of the linked list link.
    typedef bslalg::BidirectionalLink                       Link;
 
    // DATA
    Node *d_head_p;  // pointer to the head of the linked list
    Node *d_tail_p;  // pointer to the tail of the linked list
    Pool  d_pool;    // memory pool used to allocate memory
 
 
  public:
    // CREATORS
 
    /// Create an empty linked list that allocate memory using the
    /// specified `allocator`.
    MyList(const ALLOCATOR& allocator = ALLOCATOR());
 
    /// Destroy this linked list by calling destructor for each element
    /// and deallocate all allocated storage.
    ~MyList();
 
    // MANIPULATORS
 
    /// Insert the specified 'value' at the front of this linked list.
    void pushFront(const VALUE& value);
 
    /// Insert the specified 'value' at the end of this linked list.
    void pushBack(const VALUE& value);
 
     //...
 };

Now, we define the methods of MyMatrix:

CREATORS
 template <class VALUE, class ALLOCATOR>
 MyList<VALUE, ALLOCATOR>::MyList(const ALLOCATOR& allocator)
 : d_head_p(0)
 , d_tail_p(0)
 , d_pool(allocator)
 {
 }
 
 template <class VALUE, class ALLOCATOR>
 MyList<VALUE, ALLOCATOR>::~MyList()
 {
     Link *link = d_head_p;
     while (link) {
         Link *next = link->nextLink();

Here, we call the memory pool's deleteNode method to destroy the value attribute of the node and return its memory footprint back to the pool:

        d_pool.deleteNode(static_cast<Node*>(link));
        link = next;
    }
}
 
MANIPULATORS
template <class VALUE, class ALLOCATOR>
void
MyList<VALUE, ALLOCATOR>::pushFront(const VALUE& value)
{

Here, we call the memory pool's emplaceIntoNewNode method to allocate a node and copy-construct the specified value at the value attribute of the node:

    Node *node = static_cast<Node *>(d_pool.emplaceIntoNewNode(value));

Note that the memory pool will allocate the footprint of the node using the allocator specified at construction. If the (template parameter) type ALLOCATOR is an instance of bsl::allocator and the (template parameter) type VALUE has the bslma::UsesBslmaAllocator trait, then the allocator specified at construction will also be supplied to the copy-constructor of VALUE.

    if (!d_head_p) {
        d_tail_p = node;
        node->setNextLink(0);
        node->setPreviousLink(0);
    }
    else {
        Util::insertLinkBeforeTarget(node, d_head_p);
    }
    d_head_p = node;
}
 
template <class VALUE, class ALLOCATOR>
void
MyList<VALUE, ALLOCATOR>::pushBack(const VALUE& value)
{

Here, just like how we implemented the pushFront method, we call the pool's emplaceIntoNewNode method to allocate a node and copy-construct the specified value at the value attribute of the node:

    Node *node = static_cast<Node *>(d_pool.emplaceIntoNewNode(value));
    if (!d_head_p) {
        d_head_p = node;
        node->setNextLink(0);
        node->setPreviousLink(0);
    }
    else {
        Util::insertLinkAfterTarget(node, d_tail_p);
    }
    d_tail_p = node;
}