How to Design the TR-069 Data Structure

Tree of structs is the way to go

Could you give me some samples to let me feel how to implement?

Device
   DeviceSummary
   DeviceInfo
   ManagementServer
  Time
   UserInterface
   LAN
   Services
      ABCServiceNumberOfEntries = 1
      ABCService.1
            ABCServiceSpecificObjects
      XYZServiceNumberOfEntries = 1
      XYZService.1
            XYZServiceSpecificObjects

How to design the tree? I need the detail of the implementation.
Any help would be appreciated.

The TR-* data models are all hierarchical and naturally fit into a tree hierarchy ... This would essentially be n-ary tree with different node types which can be identified by a type field. If you were using C++, your task would have been considerably easier since you could have used virtual functions and RTTI to implement most of the functionality.

In C you are would have to organize the data model as a tree of structs. If you are you using other features such as access control etc as defined in TR069 then you would need some additional code for them too.

a sample implementation could be

enum type {
    .. //types of values suported
}

struct node_info {
    enum type node_type;
    char * value;
}

struct collection_info {
  int num_entries;
  struct node * entries_array;
}  

union node_details {
    struct node_info ninfo;
    struct collection_info  cinfo;
}

struct node {
    char * name;
    bool is_collection;
    union node_details details;
}

Its been a few yrs since I worked with TR069 (worked on it when it was still being drafted) so I might have missed out on few nuances but this should be a good start.

And ofcourse, I missed out pointers to children for the literal nodes

struct node_info
{
    enum type node_type;
    char * value;
}

struct collection_info {
   int num_entries;
   struct node * entries_array;
}  

union node_details {
    struct node_info ninfo;
    struct collection_info  cinfo;
}

struct node {
   char *name;
   bool is_collection;
   union node_detail details;

   /* Added*/   struct node * parent;   struct node * firstchild;   struct node * nextsibling;
};

enum type {
    .. //types of values suported
}

type means string,int,unsignedInt,boolean,... right?

>type means string,int,unsignedInt,boolean,... right?
Yes ... this is the field that would help interpret the value stored in char * value

>  /* Added*/
>  struct node * parent;
>  struct node * firstchild;
>  struct node * nextsibling;

Thread the tree as per your needs ... would you need nextsibling?

Sorry, I don't really understand "Thread the tree as per your needs".

threading the tree refers to adding references to parent/siblings/other relatives ... the pointers serve as threads (figuratively speaking) using which you can traverse the tree in different ways ... Without this thread you cant directly access the parent of a given node.

I reference the "Binary tree - Wikipedia : Encoding n-ary trees as binary trees".
"The binary tree can be thought of as the original tree tilted sideways, with the black left edges representing first child and the blue right edges representing next sibling."

If there is no nextsibling pointer, how could I get the sibling node? Sorry, I am a newbie. Any help would be appreciated.

C see many binary tree source code, such as: http://www.codeproject.com/KB/architecture/binarytreeintro.aspx.  I don't find any appropriate source code to reference for hierarchy data.  
Could someone give me some guidelines or books to reference?  Any help would be appreciated.

Is there a reason you want to use binary trees? Why not use n-ary trees.

I will use n-ary trees. But I can't find the samples code or reference. So I study the binary tree first.

Implementing n-ary tree as binary tree for TR* data models will be more work as compared to using n-ary tree.
b-trees are example n-ary trees .. you can use a count and array of pointers to have a variable fanout.

Hi,
The attach code snippet is my idea to use n-ary tree to construct the tr-069 data. Is the idea right?
But I meet a problem how to deal with the collection, such as LAN.DHCPOption.{i}.
Any help would be appreciated.

* n_array_tree.h
#ifndef N_ARRAY_TREE_H
#define N_ARRAY_TREE_H
 
typedef enum {FALSE, TRUE} boolean;
 
enum type {
	COLLECTION,
	OBJECT,
	STRING,
	INT,
	UNSIGNEDINT,
	BOOLEAN,
	DATETIME,
	BASE64
};
 
struct node_info
{
   enum type node_type;
   char * value;
   boolean is_writable;
};
 
struct collection_info {
  int num_entries;
  struct node * entries_array;
};
 
union node_detail {
   struct node_info ninfo;
   struct collection_info  cinfo;
};
 
struct node {
  char *name;
  boolean is_collection;
  union node_detail detail;
 
  struct node * parent;	
  struct node * firstchild;
  struct node * nextsibling;
};
 
struct node *newnode(char *name, enum type type_value, char *default_value);
void insert(struct node *parent, struct node *child);
 
#endif
 
* n_array_tree.c
#include "n_array_tree.h"
#include <string.h>
#include <stdlib.h>
 
struct node *newnode(char *name, enum type type_value, char *default_value, boolean is_writable)
{
	struct node *temp;
 
	temp = (struct node *) malloc (sizeof(struct node));
	temp->name = (char *) malloc (strlen(name) + 1);
	strcpy(temp->name, name);
 
	if (type_value == COLLECTION) {
		temp->is_collection = TRUE;
		if (default_value != NULL) {
			temp->detail.cinfo.num_entries = atoi(default_value);
			temp->detail.cinfo.entries_array = (struct node *) malloc (sizeof(struct node) * atoi(default_value));
		} 
		else {
			temp->detail.cinfo.num_entries = 0;
			temp->detail.cinfo.entries_array = NULL;
		}
	}
	else {
		temp->detail.ninfo.node_type = type_value;
		temp->is_collection = FALSE;
		if (default_value != NULL) {
			temp->detail.ninfo.value = (char *) malloc (strlen(default_value) + 1);
			strcpy(temp->detail.ninfo.value, default_value);
		}
		else
			temp->detail.ninfo.value = "";
		temp->detail.ninfo.is_writable = is_writable;
	}
	
	temp->parent = NULL;
	temp->firstchild = NULL;
	temp->nextsibling = NULL;
 
	return temp;
}
 
void insert(struct node *parent, struct node *child)
{
	struct node *temp;
	
	/* parent has no child */
	if (parent->firstchild==NULL) {
		parent->firstchild = child;
	}
	/* parent has children, add the new child to the node next to the last child */
	else {
		/* get the last child */
		temp = parent->firstchild;
		while (temp->nextsibling!=NULL) 
			temp = temp->nextsibling;
 
		/* add the new child */
		temp->nextsibling = child;
	}
	child->parent = parent;
 
	return child;
}
 
* main.c
#include "n_array_tree.h"
#include <stdlib.h>
 
int main()
{
	struct node *root, *deviceinfo, *lan, *dhcpoption; 
	
	root = newnode("Device", OBJECT, "", FALSE);	
 
	/* DeviceInfo object */
	deviceinfo = newnode("DeviceInfo", OBJECT, "", FALSE);
	insert(deviceinfo, newnode("Manufacturer", STRING, "XXX", FALSE));
	insert(deviceinfo, newnode("ManufacturerOUI", STRING, "YYY", FALSE));
	/* ... and so on */
 
	/* LAN object */
	lan = newnode("LAN", OBJECT, "", FALSE);
	insert(lan, newnode("AddressingType", STRING, "DHCP", TRUE));
	dhcpoption = newnode("DHCPOption", COLLECTION, "3", TRUE);
	/* How to deal with the .LAN.DHCPOption.{i}. */
 
	insert(root, deviceinfo);
	insert(root, lan);
	
	system("pause");
	return 0;
}

Select allOpen in new window

Hi, Could I ask you a question ? Does you call "Collection" as a "Object" or "an array of Object" ?
? "An array of object" right? Thank you.

struct collection_info {
  int num_entries;
  struct node * entries_array;
};

This would handle collections for you ... num_entries tells you how many entries are there in the collection and entries_array holds pointers to those nodes

You can use void * to avoid all the potential cast warnings you would get - which also means you need to be very careful in writing those segments of code.

>"An array of object" right?
Thats correct

My idea is right! Yes?


"This would handle collections for you ... num_entries tells you how many entries are there in the collection and entries_array holds pointers to those nodes."

When I call newnode function to create a collection node, I have no idea to decide how many entries are there in the collection.  Because new entries maybe be added to collection by AddObject RPC method, I don't know how to decide the num_entries.

                                                                     /  Request
Device -LAN-DHCPOptions- Node{0} - Tag
                                                                     \ Value

                                                                      / Request
                                                    Node{1} - Tag
                                                                      \ Value
                                                     ....
                                                                      / Request
                                                    Node{N} - Tag
                                                                      \ Value
 
If the value of num_entries is 3 and there is already 3 entries in the collection, at this time, I need to AddObject to the collection. I think that I need to reallocate entries_array memory and relink the node.

I don't know which way is better.
1) Choice the big num_entries value
2) Choise the small num_entries value and reallocate memory for need

        if (type_value == COLLECTION) {
                temp->is_collection = TRUE;
                if (default_value != NULL) {
                        temp->detail.cinfo.num_entries = atoi(default_value);
                        temp->detail.cinfo.entries_array = (struct node *) malloc (sizeof(struct node) * atoi(default_value));
                } 
                else {
                        temp->detail.cinfo.num_entries = 0;
                        temp->detail.cinfo.entries_array = NULL;
                }
        }

Select allOpen in new window

Thank you. I will follow the suggestions.