Обобщенные контейнеры без указателя на void

#c #stl #containers

Я тут задумался над следующей проблемой.

Сейчас я работаю над библиотекой обобщенных контейнеров и алгоритмов, делаю это на
C потому, что там, где будет использоваться эта библиотека, плюсы использовать физически
невозможно. Использование GLib так же нежелательно.

Практически вся библиотека уже написана, и у меня появилось время подумать над некоторыми
тонкостями реализации.

Я хорошо знаю C++ и STL, поэтому при реализации контейнеров и алгоритмов часто ориентируюсь
на производительность STL как на эталон, чтобы сишный вариант контейнера был не медленнее
и не прожорливее.

Но в некоторых случаях этого добиться непросто.

Например, судя по тестам, std::vector содержит указатель на сплошной блок памяти,
в котором хранятся сами объекты, а не указатели на них. Это без проблем реализуется
и на C. И работает даже немного быстрее, чем плюсовой вариант.

Но можно ли реализовать на C обобщенные связные списки, хэш-таблицы и деревья без
использования лишнего указателя на void?

Например, чтобы узел связного списка содержал не три указателя - prev, next, data,
- а два указателя и блок данных заданного размера и выравнивания?

В ряде случаев это снизило бы потребление памяти (но это неточно), а так же в большинстве
случаев увеличилась бы скорость доступа к данным (это тоже неточно)...

Но реализовывать это в C, по всей видимости, нужно с использованием черной макросной
магии, которая учитывает размер указателя, требуемое для данных узла выравнивание и
прочие тонкости.

Я поковырял GLib, и там практически везде используется простой вариант обобщенного
узла, например, связного списка:

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


Это же относится к узлам деревьев и хэш-таблиц.

Почему это так? Только ли причина в том, что хранение в узле связного списка самих
данных N-байтного размера с нужным выравниванием требует нехороших костылей? Или это
связано с чем-то еще?
    

Ответы

Ответ 1

Непонятно, в чем загвоздка. Берите и делайте блок с двумя указателями и местом для
пользовательских данных. Как вариант, node_header может быть встроенным в пользовательские
данные на его стороне, тогда это будет интрузивный список.

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;
}