Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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 };
- };
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement