Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1486
  • Last Modified:

How to Design the TR-069 Data Structure

Hi,
I implement a TR-069-Enabled Device, and store the TR-106 parameters in SQLite3 database. But, I am asked to get rid of the SQLite3 and to design a data structure to store all the parameters. Could someone tell me which data structure is better? Any help would be appreciated.
tr-106.pdf
0
TKD
Asked:
TKD
  • 10
  • 10
1 Solution
 
sunnycoderCommented:
Tree of structs is the way to go
0
 
TKDAuthor Commented:
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.
0
 
sunnycoderCommented:
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.
0
Configuration Guide and Best Practices

Read the guide to learn how to orchestrate Data ONTAP, create application-consistent backups and enable fast recovery from NetApp storage snapshots. Version 9.5 also contains performance and scalability enhancements to meet the needs of the largest enterprise environments.

 
sunnycoderCommented:
And ofcourse, I missed out pointers to children for the literal nodes
0
 
TKDAuthor Commented:
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?
0
 
sunnycoderCommented:
>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?
0
 
TKDAuthor Commented:
Sorry, I don't really understand "Thread the tree as per your needs".

0
 
sunnycoderCommented:
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.
0
 
TKDAuthor Commented:
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.

0
 
TKDAuthor Commented:
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.


0
 
sunnycoderCommented:
Is there a reason you want to use binary trees? Why not use n-ary trees.
0
 
TKDAuthor Commented:
I will use n-ary trees. But I can't find the samples code or reference. So I study the binary tree first.
0
 
sunnycoderCommented:
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.
0
 
TKDAuthor Commented:
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;
}

Open in new window

0
 
TKDAuthor Commented:
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.
0
 
sunnycoderCommented:
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.
0
 
sunnycoderCommented:
>"An array of object" right?
Thats correct
0
 
TKDAuthor Commented:
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;
                }
        }

Open in new window

0
 
sunnycoderCommented:
>My idea is right! Yes?
I havent thoroughly examined the code but data structures do look right.

>AddObject RPC method, I don't know how to decide the num_entries.
Thats ok ... you dont have to know num_entries in advance. In AddObject RPC call, you resize the array of pointers and increment the num_entries value ... accordingly, in DeleteObject you would again resize and decrement. A more elegant approach would be to keep two values - capacity and used. That way you dont have to resize your array every time.

Two obvious fallouts are
- array needs to be allocated dynamically
- deletion would require you to shift some elements in the array - If you expect frequent deletions and dont need random access much, a linked list might be better suited.

>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
2 is the way to go. I have explained the options above.
0
 
TKDAuthor Commented:
Thank you. I will follow the suggestions.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 10
  • 10
Tackle projects and never again get stuck behind a technical roadblock.
Join Now