Лучшие практики для реализации общей структуры данных в C - PullRequest
Новая
       43

Лучшие практики для реализации общей структуры данных в C

1 голос
/ 07 апреля 2019

В моих приключениях по реализации общих структур данных в C я столкнулся с дилеммой.Например, в следующем коде: 

void add_something(avl_tree_t * my_tree) {
        int new_element = 123;

        avl_insert(my_tree, (void*)&new_element);
}

int main() {
        avl_tree_t * my_tree = avl_create();

        add_something(my_tree);

        // do stuff

        avl_print(my_tree, function_that_prints_ints);

        exit(0);
}

, в котором avl_insert определен как 

void avl_insert(avl_tree_t * tree, void * data) {
        avl_node_t * new_node = malloc(sizeof(struct avl_node));

        new_node->data = data;
        // do tree balancing stuff
}

Чтобы моя универсальная функция вставки работала, я должен передать ееvoid * предмет для хранения.Однако для того, чтобы это сработало, в этом случае мне нужно передать адрес нового элемента int, который я добавляю, чтобы затем я мог разыменовать его до void *.Если я не ошибаюсь, когда мы вернемся к функции main, адрес памяти, в котором я сохранил мой новый элемент, будет скомпрометирован.

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

Еще одна вещь, которая работает, - это использование только структуры данных в диапазоне одной функции, которая, очевидно, нежизнеспособна.

У меня такой вопрос: как лучше всего хранить статически распределенные данные в общей структуре данных, будь то базовые типы C или пользовательские структуры?

Заранее спасибо.

Ответы [ 2 ]

1 голос
/ 07 апреля 2019

Используйте смешанный стиль;например, не делайте данные частью узла, а узлом частью данных: 

struct avl_node {
    struct avl_node *parent;
    struct avl_node *left;
    struct avl_node *right;
};

struct person {
    char const *name;
    struct avl_node node;
};

struct animal {
    struct avl_node node;
    int dangerousness;
};

Конструкторы для animal похожи на 

struct animal *animal_create(double d)
{
    struct animal *animal = malloc(sizeof *animal);

    *animal = (struct animal) {
        .node = AVL_NODE_INIT(),
        .dangerousness = d,
    };

    return animal;
}

Общие операции дерева AVL могут выглядеть следующим образом

void avl_tree_insert(struct avl_node **root, struct avl_node *node, 
                     int (*cmp)(struct avl_node const *a, struct avl_node const *b))
{
    /* .... */
}

и функция cmp для animal как 

int animal_cmp(struct avl_node const *a_, struct avl_node const *b_)
{
     struct animal const *a = container_of(a_, struct animal, node);
     struct animal const *b = container_of(b_, struct animal, node);

     return a->dangerousness - b->dangerousness;
}
1 голос
/ 07 апреля 2019

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

Самый простой способ - просто выделять и копировать во всех случаях, при необходимости используя пользовательскую функцию clone() или create() для создания глубоких копий, если это необходимо. Это также влечет за собой использование указанной пользователем функции destroy() для правильного удаления копий (опять же, если необходимо).

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

Обратите внимание, что это должно применяться к объекту container , а не к отдельным узлам или элементам. Если контейнер хранит данные тем или иным способом, он должен хранить все данные таким образом. См. Принцип Наименьшего Изумления .

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

...