Component bslalg_hashtablebucket [Package bslalg]

Provide a bucket representation for hash table data structures. More...

Namespaces
namespace	bslalg

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Creating and Using a List Template Class

Purpose:

Provide a bucket representation for hash table data structures.

Classes:

bslalg::HashTableBucket

hash-table, manages externally allocated nodes

See also:

Component bslalg_hashtableimputil, Component bslalg_bidirectionallink, Component bslalg_bidirectionalnode

Description:

This component provides an ability to keep track of a segment of a linked list of bslalg::BidirectionalLink objects. It contains pointers to the first and last elements of the list segment in question, or two null pointers for an empty list.

Usage:

This section illustrates intended usage of this component.

Example 1: Creating and Using a List Template Class:

Suppose we want to create a linked list template class, it will be called MyList.

First, we create the iterator helper class, which will eventually be defined as a nested type within the MyList class.

                              // ===============
                              // MyList_Iterator
                              // ===============

  template <class PAYLOAD>
  class MyList_Iterator {
      // 'Iterator' type for class 'MyList'.  This class will be typedef'ed
      // to be a nested class within 'MyList'.

      // PRIVATE TYPES
      typedef bslalg::BidirectionalNode<PAYLOAD> Node;

      // DATA
      Node *d_node;

      // FRIENDS
      template <class PL>
      friend bool operator==(MyList_Iterator<PL>,
                             MyList_Iterator<PL>);

    public:
      // CREATORS
      MyList_Iterator() : d_node(0) {}
      explicit
      MyList_Iterator(Node *node) : d_node(node) {}

      // MANIPULATORS

      MyList_Iterator operator++();

      // ACCESSORS
      PAYLOAD& operator*() const { return d_node->value(); }
  };

Then, we define our MyList class, which will inherit from bslalg::HashTableBucket. MyList::Iterator will be a public typedef of MyList_Iterator. For brevity, we will omit a lot of functionality that a full, general-purpose list class would have, implementing only what we will need for this example.

                                  // ======
                                  // MyList
                                  // ======

  template <class PAYLOAD>
  class MyList : public bslalg::HashTableBucket {
      // This class stores a doubly-linked list containing objects of type
      // 'PAYLOAD'.

      // PRIVATE TYPES
      typedef bslalg::BidirectionalNode<PAYLOAD> Node;

    public:
      // PUBLIC TYPES
      typedef PAYLOAD                            ValueType;
      typedef MyList_Iterator<ValueType>         Iterator;

      // DATA
      bslma::Allocator *d_allocator_p;

    public:
      // CREATORS
      explicit
      MyList(bslma::Allocator *basicAllocator = 0)
      : d_allocator_p(bslma::Default::allocator(basicAllocator))
      {
          reset();
      }
      ~MyList();

      // MANIPULATORS
      Iterator begin() { return Iterator((Node *) first()); }
      Iterator end()   { return Iterator(0); }
      void pushBack(const ValueType& value);
      void popBack();
  };

Next, we implement the functions for the iterator type.

                              // ---------------
                              // MyList_Iterator
                              // ---------------

  // MANIPULATORS
  template <class PAYLOAD>
  MyList_Iterator<PAYLOAD> MyList_Iterator<PAYLOAD>::operator++()
  {
      d_node = (Node *) d_node->nextLink();
      return *this;
  }

  template <class PAYLOAD>
  inline
  bool operator==(MyList_Iterator<PAYLOAD> lhs,
                  MyList_Iterator<PAYLOAD> rhs)
  {
      return lhs.d_node == rhs.d_node;
  }

  template <class PAYLOAD>
  inline
  bool operator!=(MyList_Iterator<PAYLOAD> lhs,
                  MyList_Iterator<PAYLOAD> rhs)
  {
      return !(lhs == rhs);
  }

Then, we implement the functions for the MyList class:

                                  // ------
                                  // MyList
                                  // ------

  // CREATORS
  template <class PAYLOAD>
  MyList<PAYLOAD>::~MyList()
  {
      typedef bslalg::BidirectionalLink BDL;

      for (Node *p = (Node *) first(); p; ) {
          Node *toDelete = p;
          p = (Node *) p->nextLink();

          toDelete->value().~ValueType();
          d_allocator_p->deleteObjectRaw(static_cast<BDL *>(toDelete));
      }

      reset();
  }

  // MANIPULATORS
  template <class PAYLOAD>
  void MyList<PAYLOAD>::pushBack(const PAYLOAD& value)
  {
      Node *node = (Node *) d_allocator_p->allocate(sizeof(Node));
      node->setNextLink(0);
      node->setPreviousLink(last());
      bslalg::ScalarPrimitives::copyConstruct(&node->value(),
                                              value,
                                              d_allocator_p);

      if (0 == last()) {
          BSLS_ASSERT_SAFE(0 == first());

          setFirstAndLast(node, node);
      }
      else {
          last()->setNextLink(node);
          setLast(node);
      }
  }

  template <class PAYLOAD>
  void MyList<PAYLOAD>::popBack()
  {
      BSLS_ASSERT_SAFE(first() && last());

      Node *toDelete = (Node *) last();

      if (first() != toDelete) {
          BSLS_ASSERT_SAFE(0 != last());
          setLast(last()->previousLink());
          last()->setNextLink(0);
      }
      else {
          reset();
      }

      d_allocator_p->deleteObject(toDelete);
  }

Next, in main, we use our MyList class to store a list of ints:

  MyList<int> intList;

Then, we declare an array of ints to populate it with:

  int intArray[] = { 8, 2, 3, 5, 7, 2 };
  enum { NUM_INTS = sizeof intArray / sizeof *intArray };

Now, we iterate, pushing ints to the list:

  for (const int *pInt = intArray; pInt < intArray + NUM_INTS; ++pInt) {
      intList.pushBack(*pInt);
  }

Finally, we use our Iterator type to traverse the list and observe its values:

  MyList<int>::Iterator it = intList.begin();
  assert(8 == *it);
  assert(2 == *++it);
  assert(3 == *++it);
  assert(5 == *++it);
  assert(7 == *++it);
  assert(2 == *++it);
  assert(intList.end() == ++it);