Лучшая практика реализации общей структуры данных в C
В своих приключениях по реализации универсальных структур данных на 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
Да, чтобы хранить указатели на данные с автоматическим сроком хранения, вам нужно знать размер элементов в контейнере, а также выделять и копировать данные, на которые указывает указатель.
Самый простой способ — просто выделить и скопировать во всех случаях, при необходимости используя указанную пользователем функцию clone() или create() для создания глубоких копий, если это необходимо. Это также влечет за собой использование указанной пользователем функции destroy() для правильной утилизации копий (опять же, при необходимости).
Чтобы иметь возможность избежать выделения, вы должны иметь какую-то переменную состояния, которая позволяет узнать, должен ли контейнер выделять или просто копировать само значение указателя.
Обратите внимание, что это должно относиться к объекту контейнер, а не к отдельным узлам или элементам. Если контейнер хранит данные тем или иным способом, он должен хранить все данные таким же образом. См. Принцип наименьшего удивления.
Это более сложный подход, поскольку вы должны быть уверены, что используете правильный процесс добавления и удаления элементов на основе переменной состояния. Обычно гораздо проще просто убедиться, что вы никогда не передаете указатель на значение с автоматическим сроком хранения.
Используйте смешанный стиль; например не делайте данные частью узла, а часть узла данных:
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;
}
Если объект имеет статическую продолжительность хранения, то он никуда не денется, и вам не нужно беспокоиться о его копировании. Если у него есть автоматическая продолжительность хранения, тогда да, вы должны выделить и скопировать.