Типовые общие структуры данных в обычном C?

Ответ 1

Вариант 1 - это подход, используемый большинством реализаций C общих контейнеров, которые я вижу. Набор драйверов для Windows и ядро ​​Linux используют макрос, чтобы разрешить связывание контейнеров в любой точке структуры с помощью макроса, используемого для получения указателя структуры от указателя на поле ссылки:

• list_entry() макрос в Linux
• CONTAINING_RECORD() макрос в Windows

Вариант 2 - это привязка, выполняемая BSD tree.h и реализация контейнера queue.h:

• http://openbsd.su/src/sys/sys/queue.h
• http://openbsd.su/src/sys/sys/tree.h

Я не думаю, что рассмотрю любой из этих подходов типа safe. Полезно, но не безопасно.

Ответ 2

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

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

Итак, здесь есть и другая эстетика, а также различные проблемы, и я бы рекомендовал изменить мышление, когда вы работаете на C. Чтобы действительно оценить это, я бы предложил делать то, что многие считают само собой разумеющимся дней, например, реализовать собственный распределитель памяти или драйвер устройства. Когда вы работаете на таком низком уровне, вы не можете не смотреть на все, как на макеты памяти битов и байтов, в отличие от "объектов" с прикрепленными поведением. Кроме того, в таком низкоуровневом коде управления бит/байтом может появиться точка, где C становится легче понимать, чем код С++, заваленный reinterpret_casts, например.

Что касается примера связанного списка, я бы предложил неинтрузивную версию связанного node (тот, который не требует хранения указателей списка в тип элемента, T, сам, позволяя логику связанного списка и представление, которое должно быть отделено от самого T), например:

struct ListNode
{
    struct ListNode* prev;
    struct ListNode* next;
    MAX_ALIGN char element[1]; // Watch out for alignment here.
                               // see your compiler specific info on 
                               // aligning data members.
};

Теперь мы можем создать список node следующим образом:

struct ListNode* list_new_node(int element_size)
{
    // Watch out for alignment here.
    return malloc_max_aligned(sizeof(struct ListNode) + element_size - 1);
}

// create a list node for 'struct Foo'
void foo_init(struct Foo*);
struct ListNode* foo_node = list_new_node(sizeof(struct Foo));
foo_init(foo_node->element);

Чтобы извлечь элемент из списка как T *:

T* element = list_node->element;

Так как это C, там нет проверки типа при указании на кастрюлю таким образом, и это, вероятно, также вызовет у вас непростое чувство, если вы исходите из фона С++.

Трудная часть здесь - убедиться, что этот член element правильно выровнен для любого типа, который вы хотите сохранить. Когда вы сможете решить эту проблему как можно более мобильно, у вас будет мощное решение для создания эффективных макетов памяти и распределителей. Часто это означает, что вы просто используете максимальное выравнивание для всего, что может показаться расточительным, но обычно это не так, если вы используете соответствующие структуры данных и распределители, которые не оплачивают эти накладные расходы для множества небольших элементов на индивидуальной основе.

Теперь это решение по-прежнему связано с литьем типа. Там мало что можно сделать, если у вас есть отдельная версия кода этого списка node и соответствующая логика для работы с ним для каждого типа T, который вы хотите поддержать (за исключением динамического полиморфизма). Однако он не требует дополнительного уровня косвенности, как вы могли подумать, и по-прежнему выделяет весь список node и элемент в одном распределении.

И я бы рекомендовал этот простой способ добиться универсальности в C во многих случаях. Просто замените T на буфер, длина которого соответствует sizeof(T) и правильно выровнена. Если у вас достаточно портативный и безопасный способ, который вы можете обобщить для обеспечения правильного выравнивания, у вас будет очень мощный способ работы с памятью, который часто улучшает хиты кеша, уменьшает частоту распределения/освобождения кучи, количество требуемое направление, время сборки и т.д.

Если вам нужна дополнительная автоматизация, например, list_new_node автоматически инициализировать struct Foo, я бы рекомендовал создать общую структуру таблицы типов, которую вы можете передать, в которой содержится информация, такая как большой T, указатель функции, указывающий на функцию создать экземпляр по умолчанию для T, другой - для копирования T, клонирования T, уничтожения T, компаратора и т.д. В С++ вы можете автоматически генерировать эту таблицу с использованием шаблонов и встроенных языковых понятий, таких как конструкторы копирования и деструкторы. C требует немного большего ручного усилия, но вы все равно можете немного уменьшить его шаблон с помощью макросов.

Еще один трюк, который может быть полезен, если вы переходите с помощью маршрута генерации более макроориентированного кода - это использовать префикс или суффиксное соглашение об именах идентификаторов. Например, CLONE (Type, ptr) может быть определен для возврата Type##Clone(ptr), поэтому CLONE(Foo, foo) может вызывать FooClone(foo). Это своего рода чит, чтобы получить что-то вроде функции перегрузки в C и полезно при генерации кода навалом (когда CLONE используется для реализации другого макроса) или даже немного копирования и вставки кода шаблонного типа, по крайней мере, улучшить однородность шаблона.

Ответ 3

Вариант 1, использующий void * или некоторый вариант union, используется большинством программ на C, и он может дать вам более высокую производительность, чем стиль С++/macro, имеющий несколько реализаций для разных типов, поскольку он имеет меньше дублирование кода и, следовательно, меньшее давление icache и меньшее количество промахов icache.

Ответ 4

GLib имеет кучу общих структур данных в нем, http://www.gtk.org/

В CCAN есть куча полезных фрагментов и http://ccan.ozlabs.org/

Ответ 5

Ваш вариант 1 - это то, к чему будут стремиться самые старые программисты времени, возможно, соленые с небольшим количеством 2, чтобы сократить повторяющуюся типизацию, и просто возможно использовать несколько указателей на функции для вкуса полиморфизма.

Ответ 6

Существует общий вариант для варианта 1, который более эффективен, так как он использует союзы для хранения значений в узлах списка, то есть нет дополнительной косвенности. Это имеет недостаток, что список принимает только значения определенных типов и потенциально отнимает некоторую память, если типы имеют разные размеры.

Тем не менее, можно избавиться от union, используя вместо этого гибкий член массива, если вы хотите нарушить строгий псевдоним. Пример кода C99:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ll_node
{
    struct ll_node *next;
    long long data[]; // use `long long` for alignment
};

extern struct ll_node *ll_unshift(
    struct ll_node *head, size_t size, void *value);

extern void *ll_get(struct ll_node *head, size_t index);

#define ll_unshift_value(LIST, TYPE, ...) \
    ll_unshift((LIST), sizeof (TYPE), &(TYPE){ __VA_ARGS__ })

#define ll_get_value(LIST, INDEX, TYPE) \
    (*(TYPE *)ll_get((LIST), (INDEX)))

struct ll_node *ll_unshift(struct ll_node *head, size_t size, void *value)
{
    struct ll_node *node = malloc(sizeof *node + size);
    if(!node) assert(!"PANIC");

    memcpy(node->data, value, size);
    node->next = head;

    return node;
}

void *ll_get(struct ll_node *head, size_t index)
{
    struct ll_node *current = head;
    while(current && index--)
        current = current->next;
    return current ? current->data : NULL;
}

int main(void)
{
    struct ll_node *head = NULL;
    head = ll_unshift_value(head, int, 1);
    head = ll_unshift_value(head, int, 2);
    head = ll_unshift_value(head, int, 3);

    printf("%i\n", ll_get_value(head, 0, int));
    printf("%i\n", ll_get_value(head, 1, int));
    printf("%i\n", ll_get_value(head, 2, int));

    return 0;
}

Ответ 7

Старый вопрос, я знаю, но в случае, если он все еще интересует: я экспериментировал с опцией 2) (макросы перед процессором) сегодня, и придумал пример, который я буду вставлять ниже. Немного неуклюже, но не страшно. Код не полностью безопасен по типу, но содержит проверки работоспособности для обеспечения разумного уровня безопасности. И работа с сообщениями об ошибках компилятора при записи была умеренной по сравнению с тем, что я видел при запуске шаблонов С++. Вероятно, вам лучше всего начать читать это в примере кода использования в "основной" функции.

#include <stdio.h>

#define LIST_ELEMENT(type) \
    struct \
    { \
        void *pvNext; \
        type value; \
    }

#define ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement) \
    do { \
        (void)(&(pElement)->value  == (type *)&(pElement)->value); \
        (void)(sizeof(*(pElement)) == sizeof(LIST_ELEMENT(type))); \
    } while(0)

#define SET_POINTER_TO_LIST_ELEMENT(type, pDest, pSource) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \
        void **pvDest = (void **)&(pDest); \
        *pvDest = ((void *)(pSource)); \
    } while(0)

#define LINK_LIST_ELEMENT(type, pDest, pSource) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \
        (pDest)->pvNext = ((void *)(pSource)); \
    } while(0)

#define TERMINATE_LIST_AT_ELEMENT(type, pDest) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \
        (pDest)->pvNext = NULL; \
    } while(0)

#define ADVANCE_POINTER_TO_LIST_ELEMENT(type, pElement) \
    do { \
        ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement); \
        void **pvElement = (void **)&(pElement); \
        *pvElement = (pElement)->pvNext; \
    } while(0)

typedef struct { int a; int b; } mytype;

int main(int argc, char **argv)
{
    LIST_ELEMENT(mytype) el1;
    LIST_ELEMENT(mytype) el2;
    LIST_ELEMENT(mytype) *pEl;
    el1.value.a = 1;
    el1.value.b = 2;
    el2.value.a = 3;
    el2.value.b = 4;
    LINK_LIST_ELEMENT(mytype, &el1, &el2);
    TERMINATE_LIST_AT_ELEMENT(mytype, &el2);
    printf("Testing.\n");
    SET_POINTER_TO_LIST_ELEMENT(mytype, pEl, &el1);
    if (pEl->value.a != 1)
        printf("pEl->value.a != 1: %d.\n", pEl->value.a);
    ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl);
    if (pEl->value.a != 3)
        printf("pEl->value.a != 3: %d.\n", pEl->value.a);
    ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl);
    if (pEl != NULL)
        printf("pEl != NULL.\n");
    printf("Done.\n");
    return 0;
}

Ответ 8

Я использую указатели void (void *) для представления общих структур данных, определенных с помощью structs и typedefs. Ниже я расскажу о своей реализации lib, над которым я работаю.

С такой реализацией вы можете думать о каждом новом типе, определенном с помощью typedef, как псевдокласс. Здесь этот псевдокласс - это набор исходного кода (some_type_implementation.c) и его заголовочный файл (some_type_implementation.h).

В исходном коде вам нужно определить структуру, которая будет представлять новый тип. Обратите внимание на структуру в исходном файле node.c. Там я сделал указатель void на атрибут "info". Этот указатель может нести любой тип указателя (я думаю), но цена, которую вы должны заплатить, является идентификатором типа внутри структуры (тип int) и всеми коммутаторами, чтобы сделать дескриптор подсказки каждого определенного типа. Итак, в заголовочном файле node.h "я определил тип" Node "(просто чтобы не набирать struct node каждый раз), а также мне пришлось определять константы" EMPTY_NODE ", COMPLEX_NODE" и "MATRIX_NODE".

Вы можете выполнить компиляцию вручную с помощью "gcc *.c -lm".

main.c Исходный файл

#include <stdio.h>
#include <math.h>

#define PI M_PI

#include "complex.h"
#include "matrix.h"
#include "node.h" 


int main()
{
    //testCpx();
    //testMtx();
    testNode();

    return 0;
}

node.c Исходный файл

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "node.h"
#include "complex.h"
#include "matrix.h"

#define PI M_PI


struct node
{
    int type;

    void* info;
};


Node* newNode(int type,void* info)
{
    Node* newNode = (Node*) malloc(sizeof(Node));

    newNode->type = type;

    if(info != NULL)
    {
        switch(type)
        {
            case COMPLEX_NODE:
                newNode->info = (Complex*) info;
            break;

            case MATRIX_NODE:
                newNode->info = (Matrix*) info;
            break;
        }
    }
    else
        newNode->info = NULL;

    return newNode;
}

int emptyInfoNode(Node* node)
{
    return (node->info == NULL);
}

void printNode(Node* node)
{
    if(emptyInfoNode(node))
    {
        printf("Type:%d\n",node->type);
        printf("Empty info\n");
    }
    else
    {
        switch(node->type)
        {
            case COMPLEX_NODE:
                printCpx(node->info);
            break;

            case MATRIX_NODE:
                printMtx(node->info);
            break;
        }
    }
}

void testNode()
{
    Node *node1,*node2, *node3;
    Complex *Z;
    Matrix *M;

    Z = mkCpx(POLAR,5,3*PI/4);

    M = newMtx(3,4,PI);

    node1 = newNode(COMPLEX_NODE,Z);
    node2 = newNode(MATRIX_NODE,M);
    node3 = newNode(EMPTY_NODE,NULL);



    printNode(node1);
    printNode(node2);
    printNode(node3);
}

node.h Файл заголовка

#define EMPTY_NODE   0
#define COMPLEX_NODE 1
#define MATRIX_NODE  2


typedef struct node Node;


Node* newNode(int type,void* info);
int emptyInfoNode(Node* node);
void printNode(Node* node);
void testNode();

matrix.c Исходный файл

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "matrix.h"

struct matrix
{
    // Meta-information about the matrix 
    int rows;
    int cols;

    // The elements of the matrix, in the form of a vector 
    double** MTX;
};

Matrix* newMtx(int rows,int cols,double value)
{
    register int row , col;
    Matrix* M = (Matrix*)malloc(sizeof(Matrix));

    M->rows = rows;
    M->cols = cols;
    M->MTX = (double**) malloc(rows*sizeof(double*));

    for(row = 0; row < rows ; row++)
    {
        M->MTX[row] = (double*) malloc(cols*sizeof(double));

        for(col = 0; col < cols ; col++) 
            M->MTX[row][col] = value;
    }

    return M;
}

Matrix* mkMtx(int rows,int cols,double** MTX)
{   
    Matrix* M;
    if(MTX == NULL)
    {
        M = newMtx(rows,cols,0);
    }
    else
    {
        M = (Matrix*)malloc(sizeof(Matrix));
        M->rows = rows;
        M->cols = cols;
        M->MTX  = MTX;
    }
    return M;
}

double getElemMtx(Matrix* M , int row , int col)
{
    return M->MTX[row][col];
}

void printRowMtx(double* row,int cols)
{
    register int j;
    for(j = 0 ; j < cols ; j++) 
        printf("%g ",row[j]);           
}

void printMtx(Matrix* M)
{
    register int row = 0, col = 0;

    printf("\vSize\n");
    printf("\tRows:%d\n",M->rows);
    printf("\tCols:%d\n",M->cols);
    printf("\n");
    for(; row < M->rows ; row++)
    {
        printRowMtx(M->MTX[row],M->cols);
        printf("\n");
    }

    printf("\n");
}

void testMtx()
{
    Matrix* M = mkMtx(10,10,NULL);
    printMtx(M);
}

matrix.h Файл заголовка

typedef struct matrix Matrix;

Matrix* newMtx(int rows,int cols,double value);
Matrix* mkMatrix(int rows,int cols,double** MTX);
void print(Matrix* M);
double getMtx(Matrix* M , int row , int col);
void printRowMtx(double* row,int cols);
void printMtx(Matrix* M);
void testMtx();

complex.c Исходный файл

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "complex.h"

struct complex
{
    int type;

    double a;
    double b;
};

Complex* mkCpx(int type,double a,double b)
{
    /** Doc - {{{
     * This function makes a new Complex number.
     * 
     * @params:
     * |-->type: Is an interger that denotes if the number is in
     * |         the analitic or in the polar form.
     * |         ANALITIC:0
     * |         POLAR   :1
     * |
     * |-->a: Is the real part if type = 0 and is the radius if 
     * |      type = 1
     * |
     * `-->b: Is the imaginary part if type = 0 and is the argument
     *        if type = 1
     * 
     * @return:
     *      Returns the new Complex number initialized with the values 
     *      passed
     *}}} */

    Complex* number = (Complex*)malloc(sizeof(Complex));

    number->type = type;
    number->a    = a;
    number->b    = b;

    return number;
}

void printCpx(Complex* number)
{
    switch(number->type)
    {
        case ANALITIC:
            printf("Re:%g | Im:%g\n",number->a,number->b);
        break;

        case POLAR:
            printf("Radius:%g | Arg:%g\n",number->a,number->b);
        break;
    }
}

void testCpx()
{
    Complex* Z = mkCpx(ANALITIC,3,2);
    printCpx(Z);
}

complex.h Файл заголовка

#define ANALITIC 0 
#define POLAR    1 

typedef struct complex Complex;

Complex* mkCpx(int type,double a,double b);
void printCpx(Complex* number);
void testCpx();

Надеюсь, я ничего не пропустил.

Ответ 9

Я хотел бы запрограммировать мои будущие "низкоуровневые" проекты на C, а не на С++...

Почему? Не хватает ли вашей цели компилятора С++ или среды выполнения С++?

Ответ 10

Я использую вариант 2 для пары высокопроизводительных коллекций, и это занимает очень много времени, работая над количеством макро логики, необходимой для того, чтобы сделать что-то действительно компилируемое и общее. Я делаю это исключительно для сырой производительности (игр). Используется метод X-macro.

Болезненная проблема, которая постоянно возникает в Варианте 2, заключается в следующем: "Если предположить некоторое конечное число опций, например 8/16/32/64 бит-ключей, я делаю указанное значение константой и определяю несколько функций, каждый с другим элемент этого набора значений, который может принимать константа, или я просто делаю его переменной-членом?" Первый означает менее эффективный кеш команд, так как у вас много повторяющихся функций с одним или двумя номерами, а последнее означает, что вам нужно ссылаться на выделенные переменные, которые в худшем случае означают промах кэша данных. Поскольку вариант 1 является чисто динамическим, вы будете делать такие переменные-члены, даже не задумываясь об этом. Однако это действительно микро-оптимизация.

Также учитывайте компромисс между возвращающими указателями и значениями: последний наиболее эффективен, когда размер элемента данных меньше или равен размеру указателя; тогда как если элемент данных больше, то, скорее всего, лучше возвращать указатели, чем принудительно копировать большой объект, возвращая значение.

Я бы настоятельно предложил перейти к Варианту 1 в любом сценарии, где вы не на 100% уверены, что производительность коллекции будет вашим узким местом. Даже при использовании Варианта 2 библиотека моих коллекций предоставляет "быструю настройку", которая похожа на вариант 1, т.е. Использование значений void * в моем списке и карте. Этого достаточно для 90%% обстоятельств.