3
\$\begingroup\$

I was interested in experimenting with some intrusive versions of common data structures, so I've written this simple chained hash-table using the approach:

#ifndef INTRUSIVE_HASH_TABLE_HPP
#define INTRUSIVE_HASH_TABLE_HPP

#include <cassert>
#include <cstddef>
#include <functional>
#include <type_traits>

// Types that will be inserted into the IntrusiveHashTable
// must inherit from this template class.
template<class T>
class HashTableNode
{
public:

    // Hash-table needs access to internal data of its nodes.
    template<class K, class V, class HASH>
    friend class IntrusiveHashTable;

    // IntrusiveHashTable interface:
    std::size_t getHashTableKeyHash() const { return htKeyHash;      }
    T *         getHashTableNext()    const { return htNext;         }
    bool        isLinkedToHashTable() const { return htKeyHash != 0; }

protected:

     HashTableNode() : htNext(nullptr), htKeyHash(0) { }
    ~HashTableNode() { }

private:

    // Next node in the IntrusiveHashTable bucket chain.
    // Null if this is the last item or if not linked.
    T * htNext;

    // Hash of the node's key.
    // Zero only if not linked to a table.
    std::size_t htKeyHash;
};

// This hash-table does not manage memory or lifetime of the objects inserted.
// Removing an item from the table WILL NOT destroy the object, just unlink it.
template
<
    class K,                  // The key type
    class V,                  // The mapped type (value)
    class HASH = std::hash<K> // Hashes a key instance
>
class IntrusiveHashTable
{
public:

    // Nested typedefs:
    using ValueType = V;
    using KeyHasher = HASH;
    using KeyType   = typename std::remove_cv<K>::type;

    // No copy or assignment:
    IntrusiveHashTable(const IntrusiveHashTable &) = delete;
    IntrusiveHashTable & operator = (const IntrusiveHashTable &) = delete;

    // Construct empty (no allocation). Allocates on first insertion.
    explicit IntrusiveHashTable(bool allowDuplicateKeys);

    // Construct and allocate storage with num buckets hint.
    IntrusiveHashTable(bool allowDuplicateKeys, std::size_t sizeHint);

    // Destructor clears the table and unlinks all items.
    ~IntrusiveHashTable();

    // Explicitly allocate storage. No-op if already allocated.
    void allocate();
    void allocate(std::size_t sizeHint);

    // Test if table buckets are already allocated.
    bool isAllocated() const;

    // Sets to empty without deallocating.
    void clear();

    // Clears and frees all memory.
    void deallocate();

    // Test if empty.
    bool isEmpty() const;

    // Get size in items.
    std::size_t getSize() const;

    // Number of buckets allocated.
    std::size_t getBucketCount() const;

    // Estimate memory usage of internal control structures.
    std::size_t getMemoryBytes() const;

    // Set/get the "allow duplicate keys" flag.
    void setAllowDuplicateKeys(bool allow);
    bool isAllowingDuplicateKeys() const;

    // Access item by key. Returns null if key is not present.
    ValueType * find(const KeyType & key) const;

    // Find all entries matching `key` in the table.
    // This is useful when the table is allowing duplicated keys.
    // `items[]` is an array of pointers to items.
    // `maxItems` is the maximum number of items to return (size of `items[]` array).
    // Returns the number of items found and added to the `items[]` array.
    std::size_t findAllMatching(const KeyType & key, ValueType ** items, std::size_t maxItems) const;

    // Count number of items with the given key.
    // Will never be greater than one if duplicate keys are not allowed.
    std::size_t countAllMatching(const KeyType & key) const;

    // Operator[] to access items by key (same as `find()`).
    ValueType * operator[] (const KeyType & key) const;

    // Insertion. Fails in case of duplicate keys only when duplicate keys are being disallowed.
    bool insert(const KeyType & key, ValueType * value);

    // Remove (unlink) single key/value pair. Returns a reference to the removed item. Null if no key found.
    ValueType * remove(const KeyType & key);

    // Remove (unlink) all items matching the key. Returns number of items removed.
    std::size_t removeAllMatching(const KeyType & key);

private:

    // Internal helpers:
    std::size_t hashOf(const KeyType & key) const;
    std::size_t bucketOf(std::size_t keyHash) const;
    static bool isPrime(const std::size_t x);

    // A prime number close to 2048.
    static constexpr std::size_t DefaultCapacity = 2053;

    // Array of pointers to items (the buckets).
    ValueType ** table;

    // Total size of `table` and buckets used so far.
    std::size_t bucketCount;
    std::size_t usedBuckets;

    // If allowing duplicate keys or not.
    bool allowDupKeys;
};

//
// Inline implementation of IntrusiveHashTable:
//

template<class K, class V, class HASH>
IntrusiveHashTable<K, V, HASH>::IntrusiveHashTable(const bool allowDuplicateKeys)
    : table(nullptr)
    , bucketCount(0)
    , usedBuckets(0)
    , allowDupKeys(allowDuplicateKeys)
{
    // Empty table. Allocates the buckets on first insertion.
}

template<class K, class V, class HASH>
IntrusiveHashTable<K, V, HASH>::IntrusiveHashTable(const bool allowDuplicateKeys, const std::size_t sizeHint)
    : table(nullptr)
    , bucketCount(0)
    , usedBuckets(0)
    , allowDupKeys(allowDuplicateKeys)
{
    allocate(sizeHint);
}

template<class K, class V, class HASH>
IntrusiveHashTable<K, V, HASH>::~IntrusiveHashTable()
{
    deallocate();
}

template<class K, class V, class HASH>
void IntrusiveHashTable<K, V, HASH>::allocate()
{
    allocate(DefaultCapacity);
}

template<class K, class V, class HASH>
void IntrusiveHashTable<K, V, HASH>::allocate(const std::size_t sizeHint)
{
    if (isAllocated())
    {
        return;
    }

    bucketCount = sizeHint;
    while (!isPrime(bucketCount))
    {
        ++bucketCount;
    }

    table = new ValueType *[bucketCount]();
}

template<class K, class V, class HASH>
bool IntrusiveHashTable<K, V, HASH>::isAllocated() const
{
    return table != nullptr && bucketCount != 0;
}

template<class K, class V, class HASH>
void IntrusiveHashTable<K, V, HASH>::clear()
{
    if (isEmpty())
    {
        return;
    }

    // Check each bucket. Non-null ones are occupied:
    for (std::size_t bucket = 0; bucket < bucketCount; ++bucket)
    {
        // Reset each item in this bucket's chain:
        for (ValueType * item = table[bucket]; item != nullptr;)
        {
            ValueType * nextItem = item->htNext;
            item->htNext = nullptr;
            item->htKeyHash = 0;
            item = nextItem;
        }
    }

    usedBuckets = 0;
}

template<class K, class V, class HASH>
void IntrusiveHashTable<K, V, HASH>::deallocate()
{
    if (!isAllocated())
    {
        return;
    }

    // Unlink all items:
    clear();

    // Free the table:
    delete[] table;
    table = nullptr;
    bucketCount = 0;
}

template<class K, class V, class HASH>
bool IntrusiveHashTable<K, V, HASH>::isEmpty() const
{
    return usedBuckets == 0;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::getSize() const
{
    return usedBuckets;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::getBucketCount() const
{
    return bucketCount;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::getMemoryBytes() const
{
    return bucketCount * sizeof(ValueType *);
}

template<class K, class V, class HASH>
void IntrusiveHashTable<K, V, HASH>::setAllowDuplicateKeys(const bool allow)
{
    allowDupKeys = allow;
}

template<class K, class V, class HASH>
bool IntrusiveHashTable<K, V, HASH>::isAllowingDuplicateKeys() const
{
    return allowDupKeys;
}

template<class K, class V, class HASH>
typename IntrusiveHashTable<K, V, HASH>::ValueType *
IntrusiveHashTable<K, V, HASH>::find(const KeyType & key) const
{
    if (isEmpty())
    {
        return nullptr;
    }

    const std::size_t keyHash = hashOf(key);
    for (ValueType * item = table[bucketOf(keyHash)]; item != nullptr; item = item->htNext)
    {
        if (keyHash == item->htKeyHash)
        {
            return item;
        }
    }

    return nullptr;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::findAllMatching(const KeyType & key, ValueType ** items, const std::size_t maxItems) const
{
    assert(items != nullptr);
    assert(maxItems != 0);

    if (isEmpty())
    {
        return 0;
    }

    const std::size_t keyHash = hashOf(key);
    std::size_t foundCount = 0;

    // Duplicate keys will share the same bucket/chain.
    for (ValueType * item = table[bucketOf(keyHash)]; item != nullptr; item = item->htNext)
    {
        if (keyHash == item->htKeyHash)
        {
            items[foundCount++] = item;
        }
        if (foundCount == maxItems)
        {
            break;
        }
    }

    return foundCount;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::countAllMatching(const KeyType & key) const
{
    if (isEmpty())
    {
        return 0;
    }

    const std::size_t keyHash = hashOf(key);
    std::size_t foundCount = 0;

    // Duplicate keys will share the same bucket/chain.
    for (ValueType * item = table[bucketOf(keyHash)]; item != nullptr; item = item->htNext)
    {
        if (keyHash == item->htKeyHash)
        {
            ++foundCount;
        }
    }

    return foundCount;
}

template<class K, class V, class HASH>
typename IntrusiveHashTable<K, V, HASH>::ValueType *
IntrusiveHashTable<K, V, HASH>::operator[] (const KeyType & key) const
{
    return find(key);
}

template<class K, class V, class HASH>
bool IntrusiveHashTable<K, V, HASH>::insert(const KeyType & key, ValueType * value)
{
    assert(value != nullptr);
    assert(!value->isLinkedToHashTable());

    // Ensure allocated:
    allocate();

    const std::size_t keyHash = hashOf(key);
    const std::size_t bucket  = bucketOf(keyHash);

    // This bucket's chain is already in use. Append to it:
    if (table[bucket] != nullptr)
    {
        // If disallowing duplicate keys we must scan this chain
        // and make sure no key with the same name already exists.
        if (!isAllowingDuplicateKeys())
        {
            for (ValueType * item = table[bucket]; item != nullptr; item = item->htNext)
            {
                if (keyHash == item->htKeyHash)
                {
                    return false; // This specific key is already in use, fail.
                }
            }
        }

        // Make the new value head of the chain:
        value->htKeyHash = keyHash;
        value->htNext    = table[bucket];
        table[bucket]    = value;
    }
    else // Empty chain:
    {
        value->htKeyHash = keyHash;
        value->htNext    = nullptr;
        table[bucket]    = value;
    }

    ++usedBuckets;
    return true;
}

template<class K, class V, class HASH>
typename IntrusiveHashTable<K, V, HASH>::ValueType *
IntrusiveHashTable<K, V, HASH>::remove(const KeyType & key)
{
    if (isEmpty())
    {
        return nullptr;
    }

    const std::size_t keyHash = hashOf(key);
    const std::size_t bucket  = bucketOf(keyHash);

    ValueType * previous = nullptr;
    for (ValueType * item = table[bucket]; item != nullptr;)
    {
        if (keyHash == item->htKeyHash)
        {
            --usedBuckets;

            if (previous != nullptr)
            {
                // Not the head of the chain, remove from middle:
                previous->htNext = item->htNext;
            }
            else if (item == table[bucket] && item->htNext == nullptr)
            {
                // Single item bucket, clear the entry:
                table[bucket] = nullptr;
            }
            else if (item == table[bucket] && item->htNext != nullptr)
            {
                // Head of chain with other item(s) following:
                table[bucket] = item->htNext;
            }
            else
            {
                assert(false && "IntrusiveHashTable bucket chain is corrupted!");
            }

            item->htNext = nullptr;
            item->htKeyHash = 0;
            return item;
        }

        previous = item;
        item = item->htNext;
    }

    return nullptr;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::removeAllMatching(const KeyType & key)
{
    if (isEmpty())
    {
        return 0;
    }

    const std::size_t keyHash = hashOf(key);
    const std::size_t bucket  = bucketOf(keyHash);

    ValueType * previous = nullptr;
    std::size_t removedCount = 0;

    for (ValueType * item = table[bucket]; item != nullptr;)
    {
        if (keyHash == item->htKeyHash)
        {
            --usedBuckets;

            if (previous != nullptr)
            {
                // Not the head of the chain, remove from middle:
                previous->htNext = item->htNext;
            }
            else if (item == table[bucket] && item->htNext == nullptr)
            {
                // Stop when the bucket's chain has been cleared:
                table[bucket] = nullptr;
                item->htNext  = nullptr;
                item->htKeyHash = 0;

                ++removedCount;
                break;
            }
            else if (item == table[bucket] && item->htNext != nullptr)
            {
                // Head of chain with other item(s) following:
                table[bucket] = item->htNext;
            }
            else
            {
                assert(false && "IntrusiveHashTable bucket chain is corrupted!");
            }

            ValueType * nextItem = item->htNext;
            item->htNext = nullptr;
            item->htKeyHash = 0;
            item = nextItem;

            ++removedCount;
        }
        else
        {
            previous = item;
            item = item->htNext;
        }
    }

    return removedCount;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::hashOf(const KeyType & key) const
{
    const std::size_t keyHash = KeyHasher()(key);
    assert(keyHash != 0 && "Null hash indexes not allowed!");
    return keyHash;
}

template<class K, class V, class HASH>
std::size_t IntrusiveHashTable<K, V, HASH>::bucketOf(const std::size_t keyHash) const
{
    const std::size_t bucket = keyHash % bucketCount;
    assert(bucket < bucketCount && "Bucket index out-of-bounds!");
    return bucket;
}

template<class K, class V, class HASH>
bool IntrusiveHashTable<K, V, HASH>::isPrime(const std::size_t x)
{
    if (((!(x & 1)) && x != 2) || (x < 2) || (x % 3 == 0 && x != 3))
    {
        return false;
    }
    for (std::size_t k = 1; (36 * k * k - 12 * k) < x; ++k)
    {
        if ((x % (6 * k + 1) == 0) || (x % (6 * k - 1) == 0))
        {
            return false;
        }
    }
    return true;
}

#endif // INTRUSIVE_HASH_TABLE_HPP

The overall idea is that the lifetime and memory management related to the objects stored is external to the structure, in consequence, the objects inserted are themselves the nodes and must be pointers. So the types must inherit from a "node" kind of structure. One benefit of this is avoiding an extra memory allocation for internal nodes that store links and data payload.

Overall I'm satisfied with the resulting implementation, though the removal methods seem a bit too verbose and complex. Would appreciate some special attention there.

Here is a small driver just to show the basic usage of the data structure, I'm not including the whole set of test here to avoid making this too long:

#include "intrusive_hash_table.hpp"
#include <string>
#include <iostream>

class Item : public HashTableNode<Item>
{
public:
    Item() { }
    Item(const std::string & s) : name(s) { }
    std::string name;
};

int main()
{
    // Small table to force keys to hash to the same bucket:
    IntrusiveHashTable<std::string, Item> myTable(/* allowDuplicateKeys = */ false, 5);

    assert(myTable.getSize() == 0);
    assert(myTable.isEmpty() == true);
    assert(myTable.getBucketCount() >= 5);
    assert(myTable.isAllowingDuplicateKeys() == false);

    // find() with inexistent keys:
    assert(myTable.find("uno" ) == nullptr);
    assert(myTable.find("dos" ) == nullptr);
    assert(myTable.find("tres") == nullptr);

    // insert():
    Item item0("i0");
    Item item1("i1");
    Item item2("i2");
    Item item3("i3");
    Item item4("i4");
    Item item5("i5");
    Item item6("i6");
    Item item7("i7");
    assert(myTable.insert("item0", &item0) == true);
    assert(myTable.insert("item1", &item1) == true);
    assert(myTable.insert("item2", &item2) == true);
    assert(myTable.insert("item3", &item3) == true);
    assert(myTable.insert("item4", &item4) == true);
    assert(myTable.insert("item5", &item5) == true);
    assert(myTable.insert("item6", &item6) == true);
    assert(myTable.insert("item7", &item7) == true);

    // operator[] / countAllMatching():
    assert(myTable["item7"] == &item7);
    assert(myTable["item6"] == &item6);
    assert(myTable["item5"] == &item5);
    assert(myTable["item4"] == &item4);
    assert(myTable["item3"] == &item3);
    assert(myTable["item2"] == &item2);
    assert(myTable["item1"] == &item1);
    assert(myTable["item0"] == &item0);
    assert(myTable.countAllMatching("item3") == 1);

    // remove():
    assert(myTable.remove("item5") == &item5);
    assert(myTable.remove("item3") == &item3);
    assert(myTable.remove("item1") == &item1);
    assert(myTable.remove("inexistent") == nullptr);
    assert(myTable.getSize() == 5);
}

I'm looking for second opinions mostly. Is there anything I can do to improve this? Nitpicking is also welcome.

\$\endgroup\$
3
\$\begingroup\$

Overall, it looks good, here are a few points you can improve on:

HashTableNode:

  1. You could use direct initialization of the member data and omit the default constructor. However, if your intention is to make construction protected, you'll still need a default constructor inside that section. The same is valid for the destructor, which is empty and so should also be a default:

    template<class T>
    class HashTableNode
    {
        ...
    
    protected:
    
         HashTableNode() = default;
        ~HashTableNode() = default;
    
    private:
    
        T *         htNext    = nullptr;
        std::size_t htKeyHash = 0;
    };
    

IntrusiveHashTable:

  1. Applying std::remove_cv on the key type seems unnecessary. It works just as well without it.

  2. findAllMatching() is written in C-style, that is, taking an array of pointers of a fixed size. It would be more modern to return a vector instead, which also wouldn't limit the number of matches by the size of the input array:

    std::vector<ValueType *> findAllMatching(const KeyType & key) const;
    

    Move-semantics | NRVO can elide the copy for the return value, so this will be quite efficient too.

  3. The internal array of buckets (ValueType ** table) is a raw pointer allocated with new and deleted in the destructor. Even though this pointer is encapsulated inside a class with well defined copy behavior, you could clean up the code further by using a unique_ptr or a vector to manage memory. This would also better separate responsibilities. Code that does too much is more prone to bugs (separation of concerns).

    I would recommend a std::vector<ValueType *>, which then makes bucketCount obsolete (thanks to the size() method) and also provides iterators and debug bounds checking for your iterations.

    Then in places where you have a loop like this:

    for (std::size_t bucket = 0; bucket < bucketCount; ++bucket)
    

    Could be replaced with a range based for loop.

  4. You can use the trailing return type syntax to simplify the implementation of a few methods. Instead of using the old verbose syntax involving typename:

    template<class K, class V, class HASH>
    typename IntrusiveHashTable<K, V, HASH>::ValueType * IntrusiveHashTable<K, V, HASH>::find(const KeyType & key) const { /*... */ }
    

    It can be shortened to:

    template<class K, class V, class HASH>
    auto IntrusiveHashTable<K, V, HASH>::find(const KeyType & key) const -> ValueType * { /* ... */ }
    

    That simplification can be applied to several methods in the IntrusiveHashTable class.

  5. Remember that assertions can be disabled!

     ...
     else
     {
         assert(false && "IntrusiveHashTable bucket chain is corrupted!");
     }
    

    This assertion might be disabled on a "release" build, so if that condition should ever happen, the error would go unnoticed. While this approach suffices in some cases, a more robust one would be throwing an exception.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.