Пожалуйста, дайте совет, какую структуру данных я должен использовать

Код написан на C. У меня есть два типа объектов (structs), которые имеют отношение родитель-потомок, один родительский тип может иметь 0 или более дочерних типов, дочерний элемент не может иметь своих собственных дочерних элементов. Мне нужен O(1) родительский поиск (по uID члену структуры) и дочерний поиск (также по uID члену структуры), не зная, кто его родитель. Как только у меня есть указатель на родителя, я хочу иметь возможность перебирать его дочерние элементы. И когда у меня есть указатель на дочерний элемент, я хочу знать, кто его родитель. Во время выполнения программы любой потомок или любой родитель может быть удален или вставлен, а потомок может изменить своего родителя. Когда родитель удаляется, его дети также должны быть удалены. И все это должно быть сделано в многопоточной среде, поэтому мне нужно потокобезопасное чтение (я буду использовать блокировку только для чтения для поиска ключа и блокировку чтения-записи для вставки/удаления/повторного родителя). Какую структуру данных вы бы порекомендовали?

Добавлен:

В настоящее время я пытаюсь реализовать его с помощью библиотеки uthash ( http://uthash.sourceforge.net/):

struct parent
{
    uint64_t uid;
    time_t mtime;
    struct ldata data;
    struct child *first_child;
    UT_hash_handle hh;
};

struct child
{
    uint64_t uid;
    time_t mtime;
    struct ldata data;
    struct parent *parent;
    UT_hash_handle hh;
};

struct parent *parents_list = NULL;
struct child *children_list = NULL;

Проблема в том, что когда появляется новый ребенок, он оказывается в хвосте и не связан со своими «братьями».


c struct data-structures
person Community    schedule 06.04.2012    source источник
comment
Что вы имеете в виду под поиском?   -  person Kerrek SB    schedule 06.04.2012
comment
Наивный подход: пусть у каждого дочернего элемента есть указатель prev, next и parent, и дайте каждому родителю указатель на первого дочернего элемента, т.е. сохраните двусвязный список дочерних элементов. Все указатели должны быть атомарными, чтобы можно было безблокировочно манипулировать структурами отношений.   -  person Kerrek SB    schedule 06.04.2012
comment
Под поиском я подразумеваю, что если объект (родительский или дочерний) имеет uID XXXX, и у меня есть этот uID, я хочу получить адрес объекта структуры в памяти.   -  person    schedule 06.04.2012
comment
Я понимаю. Я полагаю, что поиск O (1) можно выполнить с помощью хеш-таблицы. Если идентификаторы являются смежными, простой массив может даже помочь. (То есть хэш-таблица с тривиальной идеальной хеш-функцией.)   -  person Kerrek SB    schedule 06.04.2012
comment
Идентификаторы не являются смежными, это 64-битные уникальные идентификаторы. И да, я также склонен использовать хеш-таблицы.   -  person    schedule 06.04.2012

Ответы (2)


arrow_upward
1
arrow_downward

Как насчет:

  1. Хэш-таблица для родителей.
  2. Отдельная хеш-таблица для детей.
  3. Ссылка в каждом дочернем элементе на его родителя.
  4. Ссылка в каждом дочернем элементе на его следующего и предыдущего братьев и сестер (двойной связанный список).
  5. Ссылка в каждом родителе на его первого потомка.

Хеш-таблицы могут быть не совсем O(1), но они будут близки. Вы, вероятно, можете использовать для них существующую, хорошо отполированную библиотеку.

С точки зрения безопасности потоков, у вас могут быть мьютексы для обоих хэшей (для вставки/удаления элементов), а также мьютекс в каждом родительском элементе, когда им или любым из его дочерних элементов манипулируют. Остерегайтесь взаимоблокировок, конечно: например. если изменение родителя ребенка требует блокировки как старых, так и новых родителей, убедитесь, что вы делаете это в последовательном порядке!

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

person Edmund    schedule 06.04.2012
comment
Спасибо, да, многопоточное программирование очень подвержено ошибкам - person ; 06.04.2012
comment
Являются ли блокировки B+Tree свободными или они будут излишними для этой проблемы? - person ; 06.04.2012
comment
Деревья B+ (и деревья в целом) могут иметь более двух уровней, поэтому узел может быть одновременно родительским и дочерним. Кажется, он не соответствует вашим характеристикам. - person C2H5OH; 06.04.2012

arrow_upward
0
arrow_downward

Если я правильно понял:

struct child;  /* Forward declaration */

struct parent {
    int child_count;
    /* Other info */
    struct child child[];  /* Flex array, must be the last field */
};

struct child {
    struct parent *parent;
    /* Other info */
};

struct parent *parent_registry;  /* Array of parents, index is the ID */
struct child *child_registry;  /* Array of children, index is the ID */

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

person C2H5OH    schedule 06.04.2012
comment
Спасибо, друг, я не знал об этих гибких массивах, ушел в rtfm :) - person ; 06.04.2012