c - 请就我应该使用哪种数据结构提出建议

Question

代码在 C 中。我有两种具有父子关系的对象(结构)，一种父类型可以有 0 或更多子对象-类型，一个 child 不能有自己的 child 。我需要 O(1) 父查找(通过 uID 结构成员)和子查找(也通过 uID 结构成员)而不知道谁是它的父.一旦获得指向父项的指针，我希望能够遍历其子项。当我有一个指向 child 的指针时，我希望能够知道谁是它的 parent 。在程序执行期间，可以删除或插入任何子项或任何父项，并且子项可以更改其父项。当 parent 被移除时，它的 child 也应该被移除。所有这一切都应该在多线程环境中完成，所以我需要线程安全的读取(我将使用只读锁进行键搜索，使用读写锁进行插入/删除/重新设置)。你会推荐什么数据结构？

添加:

目前我正在尝试使用 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;

问题是当一个新的 child 到达时它最终在尾部并且与其“兄弟”无关。

Answer 1

怎么样:

1. parent 的哈希表。
2. 一个单独的 child 哈希表。
3. 每个子项与其父项的链接。
4. 每个 child 与其下一个和 previous sibling 姐妹的链接(双链表)。
5. 每个父项中指向其第一个子项的链接。

哈希表可能不是完全 O(1) 查找，但它们会很接近。您或许可以为它们使用一个现有的、完善的库。

在线程安全方面，您可以为两个散列(用于项目插入/删除)设置互斥锁，并且在每个父代中也有一个互斥锁，以便在操作它或它的任何子代时使用。当然要小心死锁:例如如果更改 child 的 parent 需要同时锁定旧 parent 和新 parent ，请确保以一致的顺序进行!

当然，找到无锁结构会更好，但我不能在这方面给你真正的建议，除非你研究一下，看看你是否能找到任何看起来合适的结构。