Generic containers without pointer to void

Question:

I've been thinking about the following problem.

Now I am working on a library of generalized containers and algorithms, I do it in C because it is physically impossible to use pluses where this library will be used. Using GLib is also undesirable.

Almost the entire library has already been written, and I had time to think about some of the subtleties of the implementation.

I know C ++ and STL well, therefore, when implementing containers and algorithms, I often focus on the performance of STL as a benchmark, so that the C version of the container is not slower and not more gluttonous.

But in some cases this is not easy to achieve.

For example, judging by the tests, std::vector contains a pointer to a solid block of memory that stores the objects themselves, not pointers to them. This is easily implemented in C as well. And it works even a little faster than the plus option.

But is it possible to implement generalized linked lists, hash tables, and trees in C without using an extra pointer to void ?

For example, for a linked list node to contain not three pointers – prev , next , data , but two pointers and a data block of a given size and alignment?

In some cases, this would reduce memory consumption (but this is inaccurate), and in most cases it would increase the speed of data access (this is also inaccurate) …

But to implement this in C , apparently, you need to use black macro magic, which takes into account the size of the pointer, the alignment required for the node data, and other subtleties.

I've been fiddling with GLib , and pretty much everything uses a simple version of a generic node, such as a linked list:

struct s_node
{
    struct s_node *prev, *next;
    void *data;
};

The same applies to nodes in trees and hash tables.

Why is it so? Is it only because the storage in the linked list node of the N-byte data itself with the necessary alignment requires bad crutches? Or is it related to something else?

Answer:

It's not clear what the catch is. Take and make a block with two pointers and a place for user data. Alternatively, node_header can be embedded in user data on its side, in which case it would be an intrusive list.

struct node;
typedef struct node node_t;

struct node_header;
typedef struct node_header node_header_t;

struct node_header
{
    node_t * p_prev;
    node_t * p_next;
};

node_t * make_node(size_t const data_size)
{
    char * const p_block = calloc(1, sizeof(node_header_t) + data_size);
    return (node_t *) p_block;
}

node_t * get_next(node_t * const p_node)
{
    node_t * p_next = NULL;
    if(p_node)
    {
        p_next = ((node_header_t *) p_node)->p_next;
    }
    return p_next;
}

void * get_data(node_t * const p_node)
{
    void * p_data = NULL;
    if(p_node)
    {
         p_data = (void *)(((char *) p_node) + sizeof(node_header_t));
    }
    return p_data;
}