โปรดให้คำแนะนำว่าฉันควรใช้โครงสร้างข้อมูลแบบใด

รหัสอยู่ใน C ฉันมีออบเจ็กต์สองประเภท (structs) ที่มีความสัมพันธ์ระหว่างพ่อแม่และลูก ประเภทผู้ปกครองหนึ่งประเภทสามารถมีประเภทลูกได้ 0 หรือมากกว่านั้น เด็กไม่สามารถมีลูกของตัวเองได้ ฉันต้องการ O(1) parent lookup (โดย uID struct member) และ child lookup (รวมถึง uID struct member) โดยไม่รู้ว่าใครคือ parent เมื่อฉันได้ตัวชี้ไปยังผู้ปกครองแล้ว ฉันต้องการที่จะสามารถทำซ้ำผ่านลูก ๆ ของมันได้ และเมื่อฉันมีตัวชี้ไปที่เด็ก ฉันต้องการที่จะรู้ว่าใครเป็นผู้ปกครอง ในระหว่างการทำงานของโปรแกรม เด็กหรือผู้ปกครองสามารถลบหรือแทรกได้ และเด็กสามารถเปลี่ยนผู้ปกครองได้ เมื่อพาเรนต์ถูกลบออก ลูกของพาเรนต์ก็ควรถูกลบออกด้วย และทั้งหมดนี้ควรทำในสภาพแวดล้อมแบบมัลติเธรด ดังนั้นฉันต้องการการอ่านแบบเธรดที่ปลอดภัย (ฉันจะใช้การล็อคแบบอ่านอย่างเดียวสำหรับการค้นหาคีย์ และการล็อคการอ่าน-เขียนสำหรับการแทรก/การลบ/การพาเรนต์ใหม่) คุณจะแนะนำโครงสร้างข้อมูลใด

เพิ่ม:

ขณะนี้ฉันกำลังพยายามใช้งานโดยใช้ไลบรารี 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
แนวทางที่ไร้เดียงสา: ให้เด็กแต่ละคนมีตัวชี้ก่อนหน้า ถัดไป และผู้ปกครอง และให้ผู้ปกครองแต่ละคนชี้ไปที่ลูกคนแรก เช่น เก็บรายชื่อเด็กที่มีการเชื่อมโยงแบบทวีคูณ พอยน์เตอร์ทั้งหมดควรเป็นแบบอะตอมมิก เพื่อให้สามารถจัดการโครงสร้างความสัมพันธ์ได้โดยไม่มีการล็อก   -  person Kerrek SB    schedule 06.04.2012
comment
โดยการค้นหาฉันหมายถึงหากวัตถุ (พาเรนต์หรือลูก) มี uID XXXX และฉันมี uID นั้น ฉันต้องการรับที่อยู่ของวัตถุโครงสร้างในหน่วยความจำ   -  person    schedule 06.04.2012
comment
ฉันเห็น. ฉันคิดว่าการค้นหา O(1) สามารถทำได้ด้วยตารางแฮช หาก ID ติดกัน อาเรย์ธรรมดาก็อาจช่วยได้เช่นกัน (เช่น ตารางแฮชที่มีฟังก์ชันแฮชเล็กๆ น้อยๆ ที่สมบูรณ์แบบ)   -  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) มากนัก แต่จะใกล้เคียงกัน คุณอาจใช้ไลบรารี่ที่มีอยู่และสวยงามดีสำหรับพวกมันได้

ในแง่ของความปลอดภัยของเธรด คุณสามารถมี mutexes สำหรับแฮชทั้งสอง (สำหรับการแทรก/การลบรายการ) และ mutex ในพาเรนต์แต่ละตัวเมื่อใดหรือรายการย่อยใด ๆ ถูกจัดการ ระวังการหยุดชะงัก เช่น: เช่น หากการเปลี่ยนผู้ปกครองของเด็กจำเป็นต้องล็อคผู้ปกครองทั้งเก่าและใหม่ ตรวจสอบให้แน่ใจว่าคุณทำตามลำดับที่สอดคล้องกัน!

การค้นหาโครงสร้างที่ปราศจากการล็อคจะดีกว่านี้แน่นอน แต่ฉันไม่สามารถแนะนำคุณได้จริงๆ ยกเว้นการค้นคว้าและดูว่าคุณจะพบสิ่งที่ดูเหมือนจะเหมาะสมหรือไม่

person Edmund    schedule 06.04.2012
comment
ขอบคุณ ใช่แล้ว การเขียนโปรแกรมแบบมัลติเธรดนั้นเกิดข้อผิดพลาดได้ง่ายมาก - person ; 06.04.2012
comment
B+Trees ล็อคฟรีหรือเปล่า หรือว่าพวกมันจะเกินความจำเป็นสำหรับปัญหานี้? - person ; 06.04.2012
comment
B+ Trees (และต้นไม้โดยทั่วไป) สามารถมีได้มากกว่าสองระดับ ดังนั้นโหนดจึงสามารถเป็นผู้ปกครองและลูกได้ในเวลาเดียวกัน ดูเหมือนจะไม่ตรงตามข้อกำหนดของคุณ - 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