2
\$\begingroup\$

I'm trying to implement a fixed sized array that uses versioned keys for dangling safety. This structure is similar to a slot map data structure, with the exception that this does not automatically compact and rearrange the data array. I have no need to iterate over this structure, and so compaction isn't necessary.

versioned_key.h

#pragma once

#include <cstdint>
#include <memory>

using bool_t = bool; // For consistency with another library

namespace nonstd
{
    struct versioned_key
    {
        template<class, size_t, typename> friend class slot_array;
        template<class, size_t, typename> friend class keyed_array;

    public:
        versioned_key() = default;

        bool_t is_null()  const noexcept { return (m_version == 0); }
        operator bool_t() const noexcept { return (m_version != 0); }

    private:
        versioned_key(
            uint32_t version,
            uint16_t index,
            uint16_t meta_data)
            : m_version(version)
            , m_index(index)
            , m_meta_data(meta_data)
        {
            // Pass
        }

        uint32_t m_version;
        uint16_t m_index;

    protected:
        uint16_t m_meta_data; // User data field, hidden unless overridden
    };
}

keyed_array.h

#pragma once

#include <array>
#include <cstdint>
#include <limits>
#include <memory>
#include <stdexcept>
#include <tuple>

#include "versioned_key.h"

namespace nonstd
{
    template<class T, size_t Capacity, typename Key = versioned_key>
    class keyed_array
    {
        static const size_t max_index = std::numeric_limits<uint16_t>::max();
        static_assert(Capacity <= max_index, "keyed_array capacity too large");
        static const uint16_t invalid_index = max_index;

    public:
        keyed_array()
            : m_data()
            , m_versions()
            , m_free()
            , m_size()
            , m_free_head()
        {
            // Initialize the in-place free list
            for (uint16_t pos = 0; pos < (Capacity - 1); ++pos)
                m_free[pos] = (pos + 1);
            m_free[Capacity - 1] = invalid_index;
        }

        // This is a big, fixed data structure for holding resources
        keyed_array(const keyed_array& rhs)            = delete;
        keyed_array& operator=(const keyed_array& rhs) = delete;
        keyed_array(keyed_array&& rhs)                 = delete;
        keyed_array& operator=(keyed_array&& rhs)      = delete;

        constexpr bool     empty()    const { return m_size == 0; }
        constexpr uint16_t size()     const { return m_size; }
        constexpr uint16_t max_size() const { return Capacity; }

        /// <summary>
        /// Inserts a value into the keyed array.
        /// Optionally provide a meta_data value to inscribe into the key.
        /// </summary>
        template<typename ... Args>
        std::tuple<Key, T&> emplace(Args&& ... args, uint16_t meta_data = 0)
        {
            if ((m_size >= Capacity) || (m_free_head == invalid_index))
                throw std::out_of_range("keyed_array has no free slots");
            const uint16_t index = m_free_head;

            // We could probably recover by just orphaning this slot, but
            // that would make insertion O(n) as we'd have to find the next.
            // Otherwise this is fatal as it makes all key handles unsafe.
            if (increment_version(m_versions[index]) == false)
                throw std::overflow_error("keyed_array version overflow");

            // Store data and update structure status information
            T& entry =
                *::new(std::addressof(m_data[m_size]))
                T(std::forward<Args>(args) ...);
            m_free_head = m_free[index];
            m_free[index] = invalid_index;
            ++m_size;

            Key key = { m_versions[index], index, meta_data };
            return std::forward_as_tuple(key, entry);
        }

        /// <summary>
        /// Tries to get a value at the given key.
        /// Will return a nullptr if the key did not match any values.
        /// </summary>
        T* try_get(Key key)
        {
            if (evaluate_key(key) == false)
                return nullptr;
            return std::addressof(m_data[key.m_index]);
        }

        /// <summary>
        /// Tries to get a value at the given key.
        /// Will return a nullptr if the key did not match any values.
        /// </summary>
        const T* try_get(Key key) const
        {
            if (evaluate_key(key) == false)
                return nullptr;
            return std::addressof(m_data[key.m_index]);
        }

        /// <summary>
        /// Tries to remove a given key. 
        /// Returns false if no value was found.
        /// </summary>
        bool_t try_remove(Key key)
        {
            if (evaluate_key(key) == false)
                return false;
            const uint16_t index = key.m_index;

            // Destroy the stored data in-place and update the free list
            std::destroy_at(std::addressof(m_data[key.m_index]));
            m_free[index] = m_free_head;
            m_free_head = index;
            --m_size;

            return true;
        }

    private:
        static bool_t increment_version(uint32_t& version)
        {
            return (++version > 0);
        }

        bool_t evaluate_key(Key key) const
        {
            if (key.m_index >= Capacity)
                return false;
            if (key.m_version != m_versions[key.m_index])
                return false;
            return true;
        }

        std::array<T,        Capacity> m_data;
        std::array<uint32_t, Capacity> m_versions;
        std::array<uint16_t, Capacity> m_free;

        uint16_t m_size;
        uint16_t m_free_head;
    };
}

Questions:

  1. Are placement new and placement delete safe in this case? Do I have to worry about alignment in this array?

  2. Do I have to use std::launder? I'm really trying to avoid using std::aligned_storage/std::launder, mostly due to complication and loss of both optimization and some compile time safety checking.

  3. Anything else major or glaring that I'm missing?

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.