Component bslstl_treenodepool [Package bslstl]

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

Namespaces
namespace	bslstl

---

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:

Component 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.

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