Portable emulation of a flexible array element in C ++?

Question

I am writing a skip list .

What I have:

template<typename T>
struct SkipListNode
{
    T data;
    SkipListNode* next[32];
};

The problem with this code is that it is wasting space - it requires all nodes to contain 32 pointers. Especially considering that in a typical list for half of the nodes you need only one pointer.

C has a neat feature called a flexible member of an array that can solve this problem. If it existed in C ++ (even for trivial classes), I could write code like this:

template<typename T>
struct SkipListNode
{
    alignas(T) char buffer[sizeof(T)];
    SkipListNode* next[];
};

and then manually create nodes using the factory function and destroy them when you delete items.

What begs the question - how can you emulate such functions in portable mode, without undefined behavior in C ++?

malloc , - - malloc(sizeof(char) + sizeof(void*)*5), . , , ++.

: - node, , .

Answer 1

, , . - , ( AlignmentExtractor , ). place-new.

T AlignmentExtractor, offsetof .

#include <cstdlib>
#include <cstddef>
#include <utility>

template<typename T>
struct ErasedNodePointer
{
    void* ptr;
};

void* allocate(std::size_t size)
{
    return ::operator new(size);
}

void deallocate(void* ptr)
{
    return ::operator delete(ptr);
}

template<typename T>
struct AlignmentExtractor
{
    static_assert(alignof(T) <= alignof(std::max_align_t), "extended alignment types not supported");
    alignas(T) char data[sizeof(T)];
    ErasedNodePointer<T> next[1];
};

template<typename T>
T& get_data(ErasedNodePointer<T> node)
{
    return *reinterpret_cast<T*>(node.ptr);
}

template<typename T>
void destroy_node(ErasedNodePointer<T> node)
{
    get_data(node).~T();
    deallocate(node.ptr);
}

template<typename T>
ErasedNodePointer<T>& get_pointer(ErasedNodePointer<T> node, int pos)
{
    auto next = reinterpret_cast<ErasedNodePointer<T>*>(reinterpret_cast<char*>(node.ptr) + offsetof(AlignmentExtractor<T>, next));
    next += pos;
    return *next;
}

template<typename T, typename... Args>
ErasedNodePointer<T> create_node(std::size_t height, Args&& ...args)
{
    ErasedNodePointer<T> p = { nullptr };
    try
    {
        p.ptr = allocate(sizeof(AlignmentExtractor<T>) + sizeof(ErasedNodePointer<T>)*(height-1));
        ::new (p.ptr) T(std::forward<T>(args)...);
        for(std::size_t i = 0; i < height; ++i)
            get_pointer(p, i).ptr = nullptr;
        return p;
    }
    catch(...)
    {
        deallocate(p.ptr);
        throw;
    }
}

#include <iostream>
#include <string>

int main()
{
    auto p = create_node<std::string>(5, "Hello world");
    auto q = create_node<std::string>(2, "A");
    auto r = create_node<std::string>(2, "B");
    auto s = create_node<std::string>(1, "C");

    get_pointer(p, 0) = q;
    get_pointer(p, 1) = r;
    get_pointer(r, 0) = s;

    std::cout << get_data(p) << "\n";
    std::cout << get_data(get_pointer(p, 0)) << "\n";
    std::cout << get_data(get_pointer(p, 1)) << "\n";
    std::cout << get_data(get_pointer(get_pointer(p, 1), 0)) << "\n";

    destroy_node(s);
    destroy_node(r);
    destroy_node(q);
    destroy_node(p);
}

:

Hello world
A
B
C

:

node ( erasure). node N N .

, , , :

• .
• ( )
• ( )

, , malloc:

// 1. Allocating a block
int* p = (int*)malloc(5 * sizeof *p);
p[2] = 42;
free(p);

, malloc, int. - :

• malloc , .
• p , (int*)((char*)p + sizeof(int)) ( p + 1, ) .

node , N ErasedNodePointer ( ) T. create_node - ​​ sizeof(T) + sizeof(ErasedNodePointer<T>)*N , .

. - . AlignmentExtractor<T> .

AlignmentExtractor<T> - , :

// 2. Finding position
AlignmentExtractor<T>* p = (AlignmentExtractor<T>*)malloc(sizeof *p);
p->next[0].ptr = nullptr;
// or
void* q = (char*)p + offsetof(AlignmentExtractor<T>, next);
(ErasedTypePointer<T>*)q->ptr = nullptr;

, , .

:

• void* .
• char* .
• , char , .
• .

++.

, , offsetof(AlignmentExtractor<T>, next) , . "" ( , "1. " , int), . , "2. " next - .

, , . AlignmentExtractor<T> - .

, 1 2. , 3. 4. - node . newplace - create_node . destroy_node, .