7
\$\begingroup\$

Writing game engine as a hobby, I've come across many situations where I need a container like a map, but searchable by different keys: a block allocator where a block needs to be searched by either offset or size, or resources searchable by either name or file.

Having multiple maps for each of those keys is ugly and pain in the ass to erase an entry, so I came up with the following.

Implementation:

template <typename... T>
class omni_map
{
    static constexpr size_t num_element = sizeof...(T);

    using tuple_t = std::tuple<T...>;

    template <size_t I>
    using element_t = typename std::tuple_element_t<I, tuple_t>;

    struct node;

    struct branch {
        branch() : 
            left(nullptr), 
            right(nullptr) {}
        node* left;
        node* right;
    };

    struct node {
        node(T&&... t) :
            values(t...) {}
        tuple_t values;
        branch branches[num_element];
    };

public:
    template <size_t I>
    class iterator {
        friend class omni_map<T...>;
    public:
        iterator(node* n = nullptr) :
            curr(n) {}
        const tuple_t& operator*() {
            return curr->values;
        }
        const tuple_t& operator->() {
            return curr->values;
        }
        bool operator==(const iterator<I>& r) {
            return curr == r.curr;
        }
        bool operator!=(const iterator<I>& r) {
            return curr != r.curr;
        }
    private:
        node* curr;
    };

public:
    omni_map() : 
        m_roots{ nullptr } {}

    void emplace(T&&... t) {
        node* n = m_nodepool.construct(std::forward<T>(t)...);
        insert_node<0>(n);
    }

    template <size_t I>
    iterator<I> find(const element_t<I>& value) {
        node* curr = m_roots[I];
        while (curr)
            if (value < std::get<I>(curr->values))
                curr = curr->branches[I].left;
            else if (value > std::get<I>(curr->values))
                curr = curr->branches[I].right;
            else
                return iterator<I>(curr);
        return iterator<I>();
    }

    template <size_t I>
    void erase(iterator<I> it) {
        remove_node<0>(it.curr);
        m_nodepool.destroy(it.curr);
    }

    template <size_t I>
    iterator<I> begin() {
        node* curr = m_roots[I];
        while (curr->branches[I].left)
            curr = curr->branches[I].left;
        return iterator<I>(curr);
    }

    template <size_t I>
    iterator<I> end() {
        return iterator<I>();
    }

private:
    template <size_t I>
    void insert_node(node* n) {
        node** curr = &m_roots[I];
        while (*curr) {
            if (std::get<I>(n->values) <= std::get<I>((*curr)->values))
                curr = &(*curr)->branches[I].left;
            else
                curr = &(*curr)->branches[I].right;
        }
        *curr = n;
        insert_node<I + 1>(n);
    }

    template <>
    void insert_node<num_element>(node* n) {}

    template <size_t I>
    void remove_node(node* n) {
        node** curr = &m_roots[I];
        while (*curr != n)
            if (std::get<I>(n->values) <= std::get<I>((*curr)->values))
                curr = &(*curr)->branches[I].left;
            else
                curr = &(*curr)->branches[I].right;
        if (n->branches[I].left)
            if (n->branches[I].right) {
                node* left = n->branches[I].left;
                node* max_left = n->branches[I].left;
                while (max_left->branches[I].right)
                    max_left = max_left->branches[I].right;
                *curr = max_left;
                while (max_left->branches[I].left)
                    max_left = max_left->branches[I].left;
                max_left->branches[I].left = left;
            }
            else
                *curr = n->branches[I].left;
        else
            if (n->branches[I].right)
                *curr = n->branches[I].right;
            else
                *curr = nullptr;
        remove_node<I + 1>(n);
    }

    template <>
    void remove_node<num_element>(node* n) {}

private:
    mem_pool<node> m_nodepool;
    node* m_roots[num_element];
};

mem_pool is my implementation of free list memory pool allocator for data locality and fast allocation.

This implementation is basically a one big graph where each element has a binary search tree structure. A node has an left/right child node for each of the element. The values of each entry are stored as a tuple in each node.

emplace function creates a node with a tuple constructed with given arguments, and calls insert_node<0> which will insert the newly created node in the binary tree structure of the first element, then call insert_node<1> for second element, and so on recursively until insert_node<num_element>. The container accepts duplicate entries, which will be placed as the left child of already existing entry.

find<0> searches by the first element(int in the example code's case), find<1> searches by the second element(std::string in the example code's case) and so on; returning iterator<I> that points to the found entry.

erase function takes said iterator<I> to removes the node it points to. The function does so by calling remove_node<I> recursively before destroying the node, which will, for each element:

  1. find parent node.
  2. if one child, replace self with said child from parent.
  3. if two child, replace self with maximum value node from left branch (has to be maximum from left if duplicates are passed to the left, minimum from right if otherwise).

I gave the iterator an index template argument, so that it could iterate based on given Ith element. But I might not implement that feature since I won't ever have to iterate in my use cases.

Example Code:

#include <iostream>
#include "omni_map.h"

int main()
{
    util::omni_map<int, std::string> test_map;

    test_map.emplace(3, "three");
    test_map.emplace(2, "two");
    test_map.emplace(7, "seven");
    test_map.emplace(1, "one");
    test_map.emplace(6, "six");
    test_map.emplace(4, "four");
    test_map.emplace(5, "five");

    auto it0 = test_map.find<0>(4);
    auto it1 = test_map.find<1>("seven");
    std::cout << std::get<0>(*it0) << " " << std::get<1>(*it0) << std::endl;
    std::cout << std::get<0>(*it1) << " " << std::get<1>(*it1) << std::endl;

    test_map.emplace(25, "twenty-five");
    test_map.emplace(16, "sixteen");
    test_map.emplace(18, "eighteen");
    test_map.emplace(17, "seventeen");
    test_map.emplace(23, "twenty-three");
    test_map.emplace(21, "twenty_one");
    test_map.emplace(21, "twenty_one(1)");

    it0 = test_map.find<0>(25);
    std::cout << (it0 == test_map.end<0>() ? "true" : "false") << std::endl;
    test_map.erase(it0);
    it0 = test_map.find<0>(25);
    std::cout << (it0 == test_map.end<0>() ? "true" : "false") << std::endl;

    it0 = test_map.find<0>(21);
    it1 = test_map.find<1>("sixteen");
    std::cout << std::get<0>(*it0) << " " << std::get<1>(*it0) << std::endl;
    std::cout << std::get<0>(*it1) << " " << std::get<1>(*it1) << std::endl;
}

Above test code outputs as follows:

4 four
7 seven
false
true
21 twenty_one
16 sixteen

I have published the solution to my GitHub here to show the entire code.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to Code Review! Can you show a complete test program (with the needed #includes and the main function) and the command you use to compile the code? \$\endgroup\$
    – L. F.
    Nov 23, 2019 at 5:02
  • \$\begingroup\$ std::iterator is deprecated, anyway you have no iterator there... \$\endgroup\$
    – slepic
    Nov 23, 2019 at 7:54
  • 1
    \$\begingroup\$ @L.F. I published my solution to github here. \$\endgroup\$ Nov 23, 2019 at 9:23
  • \$\begingroup\$ @JoonghoLee: Why your rolled out your own alignment functions? Doesn't standard std::aligned_storage_t is enough for your purposes? Also, aligned_alloc and aligned_free is not used in alignment.h. \$\endgroup\$ Nov 24, 2019 at 8:29
  • \$\begingroup\$ @nomanpouigt Dynamically allocating with new operator doesn't seem to align the data, and std::aligned_new is not supported in MSVC, so I am using a code I copied from here. No good reason as to why I am not using the already declared aligned_alloc and aligned_free in the aligned_ptr implementation. As you can see from the commented out block of code below, I was experimenting with the allocation method, then didn't bother to change back after I decided to go with the original method. \$\endgroup\$ Nov 24, 2019 at 9:19

1 Answer 1

3
\$\begingroup\$

struct branch can have default and aggregate initialisation very simply:

struct branch {
    node* left = {};
    node* right = {};
};

struct node has forwarding-reference parameters, then forgets to forward them when constructing its values member. We should use std::forward here:

    node(T&&... t) :
        values(std::forward<T>(t)...) {}

omni_map owns memory through raw pointers in m_roots yet doesn't have a destructor to free all these, nor any copy constructor or assignment operator, so looks very vulnerable to all the usual pointer-ownership problems.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.