2

コードはCです。structs親子関係を持つ2つのタイプのオブジェクト（）があります。1つの親タイプは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 に答える