4
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I just threw up in my mouth a little: 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\$ – Martin York Mar 18 at 18:00
  • 4
    \$\begingroup\$ @MartinYork Please put all critiques in answers, not comments. \$\endgroup\$ – 200_success Mar 18 at 18:33
  • 1
    \$\begingroup\$ @Deduplicator The standard does reserve names that begin with an underscore and is followed by either another underscore or an uppercase character. That applies to all scopes. The standard also reserves names beginning with an underscore specifically in the global scope. (11, 14, 17, Latest Revision) \$\endgroup\$ – Snowhawk Mar 18 at 23:51
  • 1
    \$\begingroup\$ @Martin York That's in the test code though, not the actual class. \$\endgroup\$ – Errorsatz Mar 19 at 0:14
  • \$\begingroup\$ @MartinYork: I am frasmotic, anispeptic, even compunctuous for having caused you such pericombobulation! \$\endgroup\$ – rashmatash Mar 19 at 9:09
2
\$\begingroup\$

With the proviso that it will fail unpredictably if mis-used (ex: deleting an index and then accessing it), the implementation seems reasonable for the most part.

size however, is misleading since it doesn't take removals into account: list size 5 -> add 10 items -> remove 10 items -> list size 15. You could easily track the correct value in add / remove, so I'd suggest doing that.

Related to that, there's no way to traverse the list, or to see whether a particular index is valid. For the purposes you're using it, that might not matter, but it does limit the usage.

Adding a method to convert the contents to a gap-less vector, or to a map (key = index) would give a way to do that. Adding a method to check the validity of a given index is also an option, but at O(n) for each one it's not an efficient way to traverse the contents.

I would definitely suggest removing the implicit (incorrect) conversion to vector though! Treating a free_list_vector with any elements deleted as a normal vector will blow up as soon as you try to traverse it.

\$\endgroup\$
  • \$\begingroup\$ Thank you. Please see my edit to my original post addressing your points. \$\endgroup\$ – rashmatash Mar 19 at 8:55
  • \$\begingroup\$ I agree. This class should only be used with valid ids, and throwing away invalid ids being the user's responsibility is why I'm uncomfortable using this container in production code. Removing size() as well as the implicit conversion operator would prevent users from traversing the array linearly (they don't know how many elements are in there to traverse). This way it behaves more like a templated memory allocator which gives you 32-bit opaque handles instead of pointers. I believe this would make the free list a lot safer to use. Any other suggestions are very welcome! \$\endgroup\$ – rashmatash Mar 19 at 10:00

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.