bslstl_treenodepool

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Creating a IntSet Container

Purpose

Provide efficient creation of nodes used in tree-based container.

Classes

• bslstl::TreeNodePool: memory manager to allocate tree nodes

See also

bslstl_simplepool

Description

This component implements a mechanism that creates and deletes bslstl::TreeNode objects for the (template parameter) type VALUE for use in a tree-based container.

A bslstl::TreeNodePool contains a memory pool provided by the bslstl_simplepool component to provide memory for the nodes (see bslstl_simplepool ). When the pool is empty, a number of memory blocks is allocated and added to the pool, where each block is large enough to contain a bslstl::TreeNode. The first allocation contains one memory block. Subsequent allocations double the number of memory blocks of the previous allocation up to an implementation defined maximum number of blocks.

Usage

This section illustrates intended use of this component.

Example 1: Creating a IntSet Container

This example demonstrates how to create a container type, IntSet using bslalg::RbTreeUtil.

First, we define a comparison functor for comparing a bslstl::RbTreeNode<int> object and an int value. This functor conforms to the requirements of bslalg::RbTreeUtil:

struct IntNodeComparator {
    // This class defines a comparator providing comparison operations
    // between 'bslstl::TreeNode<int>' objects, and 'int' values.
 
  private:
    // PRIVATE TYPES
    typedef bslstl::TreeNode<int> Node;
        // Alias for a node type containing an 'int' value.
 
  public:
    // CLASS METHODS
    bool operator()(const bslalg::RbTreeNode& lhs, int rhs) const
    {
        return static_cast<const Node&>(lhs).value() < rhs;
    }
 
    bool operator()(int lhs, const bslalg::RbTreeNode& rhs) const
    {
        return lhs < static_cast<const Node&>(rhs).value();
    }
};

Then, we define the public interface of IntSet. Note that it contains a TreeNodePool that will be used by bslalg::RbTreeUtil as a FACTORY to create and delete nodes. Also note that a number of simplifications have been made for the purpose of illustration. For example, this implementation provides only a minimal set of critical operations, and it does not use the empty base-class optimization for the comparator.

template <class ALLOCATOR = bsl::allocator<int> >
class IntSet {
    // This class implements a set of (unique) 'int' values.
 
    // PRIVATE TYPES
    typedef bslstl::TreeNodePool<int, ALLOCATOR> TreeNodePool;
 
    // DATA
    bslalg::RbTreeAnchor d_tree;      // tree of node objects
    TreeNodePool         d_nodePool;  // allocator for node objects
 
    // NOT IMPLEMENTED
    IntSet(const IntSet&);
    IntSet& operator=(const IntSet&);
 
  public:
    // CREATORS
    IntSet(const ALLOCATOR& allocator = ALLOCATOR());
        // Create an empty set.  Optionally specify an 'allocator' used to
        // supply memory.  If 'allocator' is not specified, a default
        // constructed 'ALLOCATOR' object is used.
 
    //! ~IntSet() = 0;
        // Destroy this object.
 
    // MANIPULATORS
    void insert(int value);
        // Insert the specified 'value' into this set.
 
    bool remove(int value);
        // If 'value' is a member of this set, then remove it from the set
        // and return 'true'.  Otherwise, return 'false' with no effect.
 
    // ACCESSORS
    bool isElement(int value) const;
        // Return 'true' if the specified 'value' is a member of this set,
        // and 'false' otherwise.
 
    int numElements() const;
        // Return the number of elements in this set.
};

Now, we implement the methods of IntSet using RbTreeUtil.

// CREATORS
template <class ALLOCATOR>
inline
IntSet<ALLOCATOR>::IntSet(const ALLOCATOR& allocator)
: d_tree()
, d_nodePool(allocator)
{
}
 
// MANIPULATORS
template <class ALLOCATOR>
void IntSet<ALLOCATOR>::insert(int value)
{
    int comparisonResult;
    bslalg::RbTreeNode *parent =
        bslalg::RbTreeUtil::findUniqueInsertLocation(&comparisonResult,
                                                     &d_tree,
                                                     IntNodeComparator(),
                                                     value);

Here we use the TreeNodePool object, d_nodePool, to create the node that was inserted into the set.

    if (0 != comparisonResult) {
        bslalg::RbTreeNode *node = d_nodePool.emplaceIntoNewNode(value);
        bslalg::RbTreeUtil::insertAt(&d_tree,
                                     parent,
                                     comparisonResult < 0,
                                     node);
    }
}
 
template <class ALLOCATOR>
bool IntSet<ALLOCATOR>::remove(int value)
{
    IntNodeComparator comparator;
    bslalg::RbTreeNode *node =
              bslalg::RbTreeUtil::find(d_tree, comparator, value);

Here we use the TreeNodePool object, d_nodePool, to delete a node that was removed from the set.

    if (node) {
        bslalg::RbTreeUtil::remove(&d_tree, node);
        d_nodePool.deleteNode(node);
    }
    return node;
}
 
// ACCESSORS
template <class ALLOCATOR>
inline
bool IntSet<ALLOCATOR>::isElement(int value) const
{
    return bslalg::RbTreeUtil::find(d_tree, IntNodeComparator(), value);
}
 
template <class ALLOCATOR>
inline
int IntSet<ALLOCATOR>::numElements() const
{
    return d_tree.numNodes();
}

Finally, we create a sample IntSet object and insert 3 values into the IntSet. We verify the attributes of the Set before and after each insertion.

bslma::TestAllocator defaultAllocator("defaultAllocator");
bslma::DefaultAllocatorGuard defaultGuard(&defaultAllocator);
 
bslma::TestAllocator objectAllocator("objectAllocator");
 
IntSet<bsl::allocator<int> > set(&objectAllocator);
assert(0 == defaultAllocator.numBytesInUse());
assert(0 == objectAllocator.numBytesInUse());
assert(0 == set.numElements());
 
set.insert(1);
assert(set.isElement(1));
assert(1 == set.numElements());
 
set.insert(1);
assert(set.isElement(1));
assert(1 == set.numElements());
 
set.insert(2);
assert(set.isElement(1));
assert(set.isElement(2));
assert(2 == set.numElements());
 
assert(0 == defaultAllocator.numBytesInUse());
assert(0 <  objectAllocator.numBytesInUse());