Re: Nary trees

["Eric M. Monsler" <emonsler beamreachnetworks com>]

etienne buxin wrote:
> hi,
>
> i'd like to use a structure similar to glib's Nary tree, but with the difference that many parent
> nodes can share one or several children nodes.
> any clue?


This is going to be rather difficult.

Unless you enforce a policy that only sibling-nodes can share child 
nodes, you are going to have a lot of trouble.  Even then, any trivial 
operation on a child node (e.g., remove from tree) will require 
searching over the full set of parent-siblings and checking the child 
pointers against the full set of siblings for the child-node.

Don't do it.

If a fellow developer at work suggested such a data-storage approach, I 
would require a tone of convincing that this was a reasonable thing to do.

If you do, I strongly suggest that you do not base it off of the current 
glib n-ary tree implimentation.  At a minimum, I would enforce a policy 
that a node has a numbered depth N, that all children are depth N+1 and 
parents are N-1.  This may seem obvious, but in a multi-parent scenario 
it would be easy to violate if moving a set of nodes within the tree.

A suggested structure:

struct eb_manymany {
  uint			node_level;
  uint			num_parents;
  uint			num_par_max;
  struct eb_manymany	**par_ptr_array;
  uint			num_children;
  uint			num_child_max;
  struct eb_manymany	**chd_ptr_array;
  gpointer		data;
}

That lets you reference count the parents and children, so that, for 
example, when removing a node you can go to all the parents and remove 
that child from their list of children.

The _max allows dynamix allocation of the pointer arrays, if you 
previously allocated space for 12 children and need a 13th, you can 
reallocate that array up to size 24 or somthing, with 13 places occupied.

If the above doesn't make sense after a few readings, you're not ready 
to tackle this.  I have done a two-level parent-child that was 
many-to-many, where entities were by definitions either parents or 
children, and by the time I had the appropriate API and error checking 
all in place it was very cumersome.

For example, what policy do you generically implement if a the last 
parent of a node is freed?  In my application, that meant that the child 
was now a discard and could be freed, but that may or may not be 
appropriate for a generic storage library.  Specify a calllback for the 
child node in that situation, defaulting to freeing?  Complexity!

If you do get it working as infinite level many-to-many, please post the 
code. :)

Eric