2

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

添加：

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

问题是当一个新孩子到来时，它最终会被排在后面，并且与它的“兄弟”没有联系。

4

2 回答 2

1

怎么样：

  1. 父母的哈希表。
  2. 一个单独的儿童哈希表。
  3. 每个孩子都有一个到其父母的链接。
  4. 每个孩子中的一个链接到它的下一个和上一个兄弟姐妹（双链表）。
  5. 每个父级到其第一个子级的链接。

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

在线程安全方面，您可以为哈希（用于项目插入/删除）设置互斥锁，在每个父级中也可以使用互斥锁，以便在操作它或其任何子级时使用。当然要当心死锁：例如，如果更改孩子的父母需要同时锁定新父母和新父母，请确保按照一致的顺序进行操作！

当然，找到无锁结构会更好，但我不能在那里给你真正的建议，除了研究，看看你是否能找到任何似乎合适的结构。

于 2012-04-06T10:55:22.840 回答
0

如果我理解正确：

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 */

也许这太简单了，特别是在重新设置父级时，因为您必须移动数组切片，但这可能是一个好的开始。或者您可以预先分配（即摊销分配）并将所有空闲数组位置链接在一起（通过数组索引）以最小化内存移动。

于 2012-04-06T10:49:06.903 回答