bslalg_hashtablebucket

Detailed Description

Provide a bucket representation for hash table data structures.

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

bslalg_hashtableimputil, bslalg_bidirectionallink, 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
                            // ===============
 
/// `Iterator` type for class `MyList`.  This class will be typedef'ed
/// to be a nested class within `MyList`.
template <class PAYLOAD>
class MyList_Iterator {
 
    // 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) {}
    //! MyList_Iterator(const MyList_Iterator& original) = default;
    //! ~MyList_Iterator() = default;
 
    // MANIPULATORS
    //! MyList_Iterator& operator=(const MyList_Iterator& other) = default;
 
    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
                                // ======
 
/// This class stores a doubly-linked list containing objects of type
/// `PAYLOAD`.
template <class PAYLOAD>
class MyList : public bslalg::HashTableBucket {
 
    // 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);