CODEWITHSUNDEEP
cdata-structuresstruct
user963395
user963395

Reputation:

Please give an advice over which data structure should I use

The code is in C. I have two type of objects (structs) that have parent-child relationship, one parent-type can have 0 or more child-types, a child can't have its own children. I need O(1) parent lookup (by uID struct member) and child lookup (also by uID struct member) without knowing who's its parent. Once I've got a pointer to a parent, I want to be able to iterate through its children. And when I have a pointer to a child, I want to be able to know who's its parent. During the execution of the program any child or any parent can be removed or inserted, and a child can change its parent. When parent is removed, its children should be also removed. And all this should be done it multi-threaded environment, so I need thread-safe reads (I will use read-only lock for key searching and read-write lock for insertion/deletion/re-parenting). What data structure would you recommend?

Added:

Currently I'm trying to implement it using uthash library ( 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;

The problem is when a new child arrives it ends up being at the tail and is not connected with its "brothers".

Upvotes: 2

Views: 254

Answers (2)

Edmund
Edmund

Reputation: 10829

How about:

  1. A hash table for parents.
  2. A separate hash table for children.
  3. A link in each child to its parent.
  4. A link in each child to its next and prev siblings (double linked list).
  5. A link in each parent to its first child.

The hash tables may not be quite O(1) lookup, but they will be close. You can probably use an existing, well-polished library for them.

In terms of thread safety, you could have mutexes for both hashes (for item insertion/deletion), and also a mutex in each parent, for when it or any of its children are being manipulated. Beware of deadlocks, of course: e.g. if changing a child's parent requires locking both the old and new parents, make sure you do them in a consistent order!

Finding lock-free structures would be even better, of course, but I can't really advise you there, except to research and see if you can find any that seem to fit.

Upvotes: 1

C2H5OH
C2H5OH

Reputation: 5612

If I understood correctly:

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

Maybe it's too simplistic, specially when it comes to reparenting as you will have to shift array slices, but it may be a good start. Or you could preallocate (i.e. amortized allocation) and link together (by array index) all free array positions to minimize memory moves.

Upvotes: 0

Related Questions