Глубокая копия структуры графика

Question

Глубокая копия структуры графика

Я имею структуру графика в C и хочу сделать глубокую копию из него (включая узлы и края).

Структура похожа на это:

struct li_list {
    struct li_node n;
};

struct li_node {
    struct li_node *next, *prev;
};

struct gr_graph {
    struct li_list nodes;
    int nodecount;
};

struct gr_node {
    struct li_node node;
    struct gr_graph *graph;
    int pred_count, succ_count;
    struct li_list pred, succ;
};

struct gr_edge {
    struct li_node succ, pred;
    struct gr_node *from, *to;
    unsigned long marks;
};

Эти структуры не существуют как сами, но "наследованный" в другой структуре, как это:

struct ex_node {
    struct gr_node _; // "Superclass"
    int id;
    struct ex_node *union_find_parent;
    ...
}

Существует ли изящное решение создания глубокой копии такая структура, включая обновление ссылок на копии?

Примечание: Члены вложенных структур не указывают на корневую структуру, которую это содержит, но на их связанную вложенную структуру (например, ex_node._.pred.n.next точки к a ex_edge._.pred). Это подразумевает утомительную адресную арифметику с указателями, когда они должны быть обновлены.

Мое решение до сих пор

Memcopy все структуры
Выполните итерации через все копии
Назовите набор макросов для всех полей, которые содержат ссылки (Из-за недостающего RTTI в C, я, вероятно, не приду это),
Использование макросов
- offsetof вычислить адрес корневой структуры
- Получите адрес скопированного эквивалента
- offsetof заставить указатель указать на корректную вложенную структуру

Там какой-либо более легкий путь состоит в том, чтобы сделать это? Я также боюсь, что забываю добавлять макро-вызов, когда я добавляю больше полей.

5

c

задан Meinersbur 7 February 2010 в 15:37

3 ответа

Другие вопросы по тегам:

c

Похожие вопросы:

score 1 · Answer 1

Звучит нормально. Мои 0,02 доллара США:

Не знаю, зачем вам нужны оба li_list и li_node . Кроме того, разве вам не нужен член данных для li_node ?
Общая структура выглядит немного сложной (конечно, я не знаю ваших требований) и пахнет дизайном в стиле C ++ (простите меня , если я ошибаюсь)
memcpy не требуется. Достаточно простого задания.
Определите член-указатель функции для каждой структуры с элементами-указателями, чтобы вы могли:

Итак:

struct foo {
   int datum;
   int *p;
   foo_copy pfoo;
};

typedef void (*foo_copy)(const struct foo *src, struct foo *dst);

void foo_cp(const struct foo *src, struct foo *dst)
{ 
    *dst = *src; // copy non-pointer data
    dst->p = malloc(sizeof *dst->p);
    dst->p = *src->p;
}


// somewhere else
struct foo s;
// initalize
struct foo *t = malloc(sizeof *t);  
s.copy(&s, &t);

и вложенные типы вызывают соответствующие методы копирования элементов ...

score 1 · Answer 2

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

Надеюсь, это поможет, С уважением, Том.

score 1 · Answer 3

memcpy все структуры и создать отсортированный список, где каждая запись содержит адрес исходной структуры и адрес копии структуры.

Теперь пройдите через все копии. Для каждой переменной указателя во всех скопированных структурах выполнить поиск указателя в отсортированном списке и заменить его на адрес его копии.