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