I'm trying to implement a free list by using a std::vector
as its growable buffer. The reason I made this instead of just adding/removing elements directly into a vector, is because I'd like the indices to remain valid after an item is removed. Please take a look at the code below. I think it works pretty well with my use cases and tests. However it requires the data type, which is stored in the buffer, to always have a default constructor. I'd appreciate any improvements/fixes to this code as well as any alternative ideas to do this.
#pragma once
#include <vector>
#include <stdint.h>
#include <assert.h>
using u32 = uint32_t;
constexpr u32 u32_invalid_id{ 0xffffffff };
template <typename T>
class free_list_vector
{
static_assert(sizeof(T) >= sizeof(u32));
public:
explicit free_list_vector() = default;
explicit free_list_vector(size_t n)
{
_array.reserve(n);
_next_free_index = u32_invalid_id;
}
~free_list_vector() { clear(); }
template<class... params>
u32 add(params&&... p)
{
u32 id{ u32_invalid_id };
if (_next_free_index == u32_invalid_id)
{
id = (u32)_array.size();
_array.emplace_back(std::forward<params>(p)...);
}
else
{
id = _next_free_index;
assert(id < _array.size() && already_removed(id));
_next_free_index = read_index(id);
new (&_array[id]) T(std::forward<params>(p)...);
}
return id;
}
constexpr void remove(u32 id)
{
assert(id < _array.size() && !already_removed(id));
T& item{ _array[id] };
item.~T();
write_index(id, _next_free_index);
_next_free_index = id;
}
constexpr void clear()
{
clear_removed_items();
_array.clear();
}
constexpr decltype(auto) size() const { return _array.size(); }
[[nodiscard]] T& operator[](u32 id)
{
assert(id < _array.size());
return _array[id];
}
[[nodiscard]] const T& operator[](u32 id) const
{
assert(id < _array.size());
return _array[id];
}
constexpr operator const std::vector<T>&() const
{
return _array;
}
private:
constexpr void write_index(u32 id, u32 next_free_id)
{
debug_op(memset(&_array[id], 0xcc, sizeof(T)));
u32 *const p{ reinterpret_cast<u32 *const>(&_array[id]) };
*p = next_free_id;
}
constexpr u32 read_index(u32 id) const
{
return *reinterpret_cast<const u32 *const>(&_array[id]);
}
constexpr void clear_removed_items()
{
while (_next_free_index != u32_invalid_id)
{
const u32 id{ _next_free_index };
_next_free_index = read_index(id);
new (&_array[id]) T{};
}
}
#ifdef _DEBUG
constexpr bool already_removed(u32 id) const
{
u32 i{ sizeof(u32) }; // skip the first 4 bytes
const u8 *const p{ reinterpret_cast<const u8 *const>(&_array[id]) };
while ((p[i] == 0xcc) && (i < sizeof(T))) ++i;
return i == sizeof(T);
}
#endif
std::vector<T> _array;
u32 _next_free_index{ u32_invalid_id };
};
Here is a little test:
struct _1 {
explicit _1() = default;
explicit _1(ID3DBlob* b, u32 size)
:res1{ b }, blah{ size }
{
}
DISABLE_COPY(_1); // deletes copy constructor and copy assignment operator
explicit _1(_1&& o)
{
*this = std::move(o);
}
~_1() { reset(); }
_1& operator=(_1&& o)
{
reset();
res1 = o.res1;
blah = o.blah;
new (&o) _1{}; // we don't want to release the COM-object after a move
return *this;
}
ID3DBlob *const blob() { return res1; }
private:
void reset()
{
if (res1)
{
res1->Release();
res1 = nullptr;
}
}
ID3DBlob* res1{ nullptr };
u32 blah{ u32_invalid_id };
};
void free_list_test()
{
free_list_vector<_1> list;
for (u32 i = 0; i < 10; ++i)
{
ID3DBlob* b;
D3DCreateBlob(4096, &b);
list.add(b, 4096);
}
{
u32 indices[]{ 3, 5, 8, 1, 6 };
for (u32 i = 0; i < _countof(indices); ++i)
{
list.remove(indices[i]);
}
}
for (u32 i = 0; i < 40; ++i)
{
ID3DBlob* b;
D3DCreateBlob(4096, &b);
list.add(b, 4096);
}
size_t sizes{ 0 };
for (u32 i = 0; i < 45; ++i)
{
sizes += list[i].blob()->GetBufferSize();
}
assert(sizes == 45 * 4096);
{
u32 indices[]{ 23, 35, 18, 11, 26 };
for (u32 i = 0; i < _countof(indices); ++i)
{
list.remove(indices[i]);
}
}
}
int main(){
free_list_test();
return 0;
}
struct _1 {
. That's bad on so many levels. 1: It makes the code unreadable. 2: There are already libraries out there (for special use cases that use _1). 2: Its a reserved identifier so illegal to use in user code. 3: I am just gob smacked. \$\endgroup\$