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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.