3

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,

enter image description here

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

  • 1
    Is the status of a node the maximum of the statuses of its children? Can Router-1 be Critical state even if neither Memory nor NIC interface is in Critical state? If so, do you need a 'node status' and 'tree status'? You can propagate status changes up the tree as long as: either a node such as Router-1 doesn't have independent state; or the independent state is recorded separately from the composite state based on the separate state and the (revised) status of its children. You don't need a callback to modify the statuses up the tree; you can use a generic function. – Jonathan Leffler Dec 17 '16 at 6:52
  • @JonathanLeffler 1) status of node is maximum of status of its children. router-1 status will be Warning, if memory status is Warning and NIC status is Running. 2) router-1 node status is decided based on composite state of its children. 3) Router-1 status cannot have its own independent state. 4) Status of leaf nodes(Memory/NIC/MIB) can be assumed to be frequently changed based on snmp protocol request for state. Word assume is used because code for snmp request id not given in the query – overexchange Dec 17 '16 at 14:19
2

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.

| improve this answer | |
  • Yes, I generally follow Encapsulation(different aspect from given query) in my code using extern keyword in header file(example). I did not show it in query, as it was not necessary. – overexchange Dec 17 '16 at 16:20
  • Under 'conditional recalculation'...suppose one leaf node was at Critical (and all other leaf nodes were at state Running) and the one leaf node now changes back to Running. Then you need to propagate the changes up the tree to set the higher nodes to Running status once more. I think your text denies the need for doing that. – Jonathan Leffler Dec 17 '16 at 19:44
  • @JonathanLeffler Indeed, thanks for pointing this out ! – Christophe Dec 17 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.