State propagation(bottom-up) in multi-walk tree

Question

Using the Tree representation(mentioned below),

typedef enum {Running, Warning, Critical}Status;

struct TreeNode;

typedef struct List{
  int childCount;
  struct treeNode **childList;
}List;

typedef struct Resource{
  char *resourceName;
  Status resourceStatus;
}Resource;

typedef struct treeNode{
  struct treeNode *parent;
  Resource *ITInfraResource;
  List *childList;
}Node;

typedef struct MultiWalkTree{
  Node *root;
  int size;
}Tree;

---

Consider below tree constructed,

where the resourceStatus value of Level 1 nodes is updated based on resourceStatus value of their immediate children.

Example- if resourceStatus member of Memory node under Router-1 node turns Critical then resourceStatus in Router-1 node should also show the same status value. resourceStatus should further propagate to root node

My question:

Assuming the resourceStatus in the leaf nodes gets updated frequently(using SNMP protocol, say), Using C,

What should be the approach to make Tree intelligent that it update its parent node resourceStatus automatically on change of status of its children?

Note: I was thinking about callback functions, but yet to get clear idea

Answer 1

With C, your data structure is and will remain dumb. This is not a value judgment : I mean that if some code has the address of a treeNode *x, it can change x->ITInfraResource->resourceStatus without anything else happening.

Encapsulate data

In order to control this situation, and make your structure intelligent, you must first encapsulate your structure, in such a way that the using code always has to use some of your function to change the status.

In practice, there are several ways to achieve this. For example, you could modularize your structure using separate compilation. You would use in your headers only a forward declaration of your Resource structure. This allows the using code to use pointers to a Resource, but forbids to access its content directly:

typedef struct Resource Resource;   

void change_resource_status (treeNode *n, Status s);  // must use to access content

And in the compilation unit where change_resource_status() and similar functions would be implemented, you could then define the structure, keeping it private for the outside world:

struct Resource {
  char *resourceName;
  Status resourceStatus;
}; 

You are then in control of all the changes made, and you can propagate the change in your tree using various approaches

Propagation strategies

If you'd be in an object oriented design, I'd perhaps recommend you an observer pattern, or an event loop using a command pattern. But in a non-object world, for such a tree structure I'd definitively recommend a simpler approach that doesn't require use of function pointers and callback functions.

Based on the encapsulation, the easiest way would be to iterate through the parent nodes to update them either directly or by calling a function to recalculate them.

Two techniques could minimize the recalculations:

• conditional recalculation: for example, if the parent has to be updated with the max status of the children, then the parent needs to be updated only if the new status of the children is higher than its old one (or if the old children status correspond to the max value of the parent).

• asynchronous recalculation: for any change, you could set a dirty flag in the node that is changed and the nodes that have to be recalculated. In a second step, when all the changes are done, or periodically, you would go through your tree, and recalculate all the dirty nodes.

If you can't opt for the encapsulation

One way to do handle the changes would then to have a second "shadow" status.

Every once a while (for example using a multi threading approach ?), a recalculation algorithm could explore the nodes where the status is different from the shadow status (i.e. the "dirty" nodes) and start the recalculation process.

But without proper encapsulation, your recalculation algorithm would remain vulnerable to misuse of the shadow status.