Record_pool - Sharing with explicit ownership (C++)

> Coding, hacking, computer graphics, game dev, and such...
User avatar
fips
Site Admin
Posts: 166
Joined: Wed Nov 12, 2008 9:49 pm
Location: Prague
Contact:

Record_pool - Sharing with explicit ownership (C++)

Post by fips »

When designing a framework or piece of software in C++, one has to make a fundamental decision right at the early stage of the project, which is: How to deal with object sharing? This is of critical importance as the chosen approach irreversibly affects the whole codebase. I recognize 3 major sharing patterns that satisfy all my needs in the context of the real-time systems development:

1) No sharing at all (private 1:1 ownership)
2) Sharing through a table (explicit 1:N ownership)
3) Sharing through a pool (explicit 1:N ownership)


No sharing (1) is the easiest to deal with. It basically means that an object owns another object, and the lifetime of the owned object is bound to its owner. This can be easily achieved by direct containment (composition) by value, or with the help of std::unique_ptr.

Generally, when dealing with object sharing, there're basically two options: One can either go with implicit ownership using std::shared_ptr, or with explicit ownership using a kind of table or pool. I don't like the former one for a variety of reasons. So I'll rather talk about the latter.

The beauty of a table (2) is that there's just a single authority (the table itself) that is responsible for adding new and managing shared objects (removing is not allowed), so at any time, we can safely access shared objects through an index that is guaranteed to never get invalidated (more precisely, indices are bound to the lifetime of the table). Although a bit limited in use, I find this to be the prettiest way of sharing ;)

A pool (3) basically extends (2) by adding the possibility of removing shared objects. We can no longer use pure indices to access the objects as they might get deleted at any time, so we need a handle to do the job (I still call it index, though). The handle offers exactly the same constant-time look-up speed as the index, but on top of that it provides a kind of weak reference to check the existence of the object it's supposed to refer to. That's all we need to safely detect deleted objects in the client code.

The code blow shows my implementation of Record_index and Record_pool:

VIEW THE CODE BELOW IN FULL-SCREEN (record_pool_sample.cpp)

Code: Select all

/*
(c) 2012 +++ Filip Stoklas, aka FipS, http://www.4FipS.com +++
THIS CODE IS FREE - LICENSED UNDER THE MIT LICENSE
ARTICLE URL: http://forums.4fips.com/viewtopic.php?f=3&t=768
*/

#include <vector>
#include <algorithm>
#include <cstdint> // uint16_t, ...
#include <cassert>

/// A simple handle-like index, combination of a table index and magic number for consistency checks.
template <typename Bound_T>
struct Record_index_pod
{
    /// Constructs a new index (we don't have a CTOR for this as we want the index to act as a POD).
    static Record_index_pod make(size_t value, size_t magic)
    {
        assert(value <= Value_max_value && magic <= Magic_max_value); // check for overflow
        const Record_index_pod index = { static_cast<uint16_t>(value), static_cast<uint16_t>(magic) };
        assert(index.value() == value && index.magic() == magic); // double check ;)
        return index;
    }

    /// Returns an invalid index (a kind of null-pointer equivalent).
    static Record_index_pod invalid()
    {
        return make(0, Magic_invalid_value);
    }

    /// Checks for invalid index (it, however, doesn't make any assumptions about the record it might refer to).
    bool valid() const
    {
        return *this != invalid();
    }

    size_t value() const { return _value; }
    size_t magic() const { return _magic; }
    size_t key() const { return _key; }

    bool operator == (const Record_index_pod &rhs) const { return _key == rhs._key; }
    bool operator != (const Record_index_pod &rhs) const { return _key != rhs._key; }
    bool operator < (const Record_index_pod &rhs) const { return _key < rhs._key; }
    bool operator > (const Record_index_pod &rhs) const { return _key > rhs._key; }
    bool operator <= (const Record_index_pod &rhs) const { return _key <= rhs._key; }
    bool operator >= (const Record_index_pod &rhs) const { return _key >= rhs._key; }

    enum // define sizes and limits
    {
        Value_bit_count = 16,
        Magic_bit_count = 16,

        Value_max_value = (1 << Value_bit_count) - 1,
        Magic_max_value = (1 << Magic_bit_count) - 1,

        Magic_invalid_value = 0
    };

    union
    {
        struct // bit fields are much easier to debug than masks...
        {
            uint16_t _value : Value_bit_count;
            uint16_t _magic : Magic_bit_count;
        };

        uint32_t _key; // a composite (value & magic)
    };
};

/// A record pool, it stores records by value and provides safe access to them through the index.
template <typename T, typename Index_T = Record_index_pod<T>>
class Record_pool
{
 public:

    typedef Index_T Index;

    /// Creates a new pool, optionally pre-allocated to the given size.
    explicit Record_pool(size_t size = 0)
    {
        grow(size);
    } 

    /// Adds a new record to the pool, returns its index.
    Index add(const T &rec)
    {
        if(_free_list.empty())
            grow(_table.empty() ? 16 : _table.size()); // grow to 16 if empty

        // pop a free table index
        assert(!_free_list.empty());
        const size_t table_index = _free_list.back();
        _free_list.pop_back();

        // store the record & update the magic number
        assert(table_index < _table.size());
        Entry &entry = _table[table_index];
        entry = Entry(rec, entry.magic + 1, true);
        entry.magic += (entry.magic == Index::Magic_invalid_value) ? 1 : 0; // handle wrapping

        assert(entry.magic != Index::Magic_invalid_value);
        return Index::make(table_index, entry.magic);
    }

    /// Removes an existing record from the pool.
    void remove(Index index)
    {
        assert(has(index));

        // deactivate & return to the free list
        _table[index.value()].active = false;
        _free_list.emplace_back(index.value());
    }

    /// Gets a record at the given index, asserts if not found.
    const T & get(Index index) const
    {
        assert(has(index));
        return _table[index.value()].payload;
    }

    /// Gets a record at the given index, asserts if not found.
    T & get(Index index)
    {
        assert(has(index));
        return _table[index.value()].payload;
    }

    /// Checks whether there's a valid record at the given index. 
    bool has(Index index) const
    {
        const size_t table_index = index.value();
        const size_t magic = index.magic();

        const Entry &entry = _table[table_index];

        return
         magic != Index::Magic_invalid_value &&
         table_index < _table.size() &&
         entry.active &&
         entry.magic == magic
        ;
    }

 private:

    /// Grows the pool by the given size.
    void grow(size_t size)
    {
        if(size == 0)
            return;

        const size_t orig_size = _table.size();
        const size_t new_size = orig_size + size;

        // resize the table using T(), therefore T must be default-constructible
        _table.resize(new_size, Entry(T(), Index::Magic_invalid_value, false));
        _free_list.resize(new_size);

        // generate free indices
        size_t magic = new_size;
        std::generate(
         _free_list.begin() + orig_size,
         _free_list.end(),
         [&magic]()->size_t { return --magic; }
        );
    }

    struct Entry
    {
        T payload; // the actual record
        uint32_t magic : Index::Magic_bit_count; // its corresponding magic number
        bool active : 1; // used / unused pool entry

        Entry(const T &payload, size_t magic, bool active):
        payload(payload), magic(magic), active(active)
        {}
    };

    std::vector<Entry> _table;
    std::vector<size_t> _free_list;
};

/// A demo Entity type managed by Record_pool.
struct Entity
{
    std::string name;
    int x, y;

    Entity() : name(), x(), y() {} ///< Must be default-constructible.
    Entity(const std::string &name, int x, int y) : name(name), x(x), y(y) {}
};

int main()
{
    // introduce a new index type (it's typically done in an interface header)
    struct Entity_pool_index_tag {}; // it's bound to this tag to make the index type-safe
    typedef Record_index_pod<Entity_pool_index_tag> Entity_pool_index;

    // define the pool (it's typically done inside implementation)
    typedef Record_pool<Entity, Entity_pool_index> Entity_pool;
    Entity_pool pool;

    // add a new entity into the pool
    const Entity_pool_index foo_index = pool.add(Entity("foo", 10, 20));
    assert(foo_index.valid()); // 'foo_index' is valid
    assert(pool.has(foo_index)); // 'pool' has 'foo'

    // access the entity using the index
    const Entity &foo = pool.get(foo_index);
    printf("entity : name='%s', pos=[%d, %d]\n", foo.name.c_str(), int(foo.x), int(foo.y));

    // remove the entity from the pool
    pool.remove(foo_index);
    assert(foo_index.valid()); // 'foo_index' is valid
    assert(!pool.has(foo_index)); // 'pool' doesn't have 'foo'

    // add a new entity into the empty pool
    const Entity_pool_index bar_index = pool.add(Entity("bar", 10, 20));
    assert(bar_index.valid()); // 'bar_index' is valid
    assert(pool.has(bar_index)); // 'pool' has 'bar'
    assert(foo_index.valid()); // 'foo_index' is valid
    assert(!pool.has(foo_index)); // 'pool' doesn't have 'foo'
    // pool.get(foo_index); // this would assert/crash

    // note that a new index gets the same 'value', but a different 'magic'
    // (the exact behaviour is just an implementation detail though)
    assert(foo_index.value() == bar_index.value() && foo_index.magic() != bar_index.magic());

    return 0;
}

// output:
// entity : name='foo', pos=[10, 20]
There're a few implementation details worth mentioning:
  • Record_index doesn't need to know anything about its associated Record_pool. So its use in interfaces doesn't bring unnecessary dependencies.
  • Record_index can be bound to a tag type, to make its type unique and provide additional type safety. Although one might consider using the same tag type for all index types in the release build to let the compiler generate less code.
  • A record within the Record_pool must be default-constructible and copyable. If you don't like it, you can always wrap it to std::unique_ptr.