Solved

How to Design the TR-069 Data Structure

Posted on 2008-11-02
20
1,473 Views
Last Modified: 2012-05-05
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
Comment
Question by:TKD
  • 10
  • 10
20 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22865050
Tree of structs is the way to go
0
 

Author Comment

by:TKD
ID: 22865195
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22865227
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22865240
And ofcourse, I missed out pointers to children for the literal nodes
0
 

Author Comment

by:TKD
ID: 22865490
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22865694
>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
 

Author Comment

by:TKD
ID: 22865984
Sorry, I don't really understand "Thread the tree as per your needs".

0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22866003
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
 

Author Comment

by:TKD
ID: 22872801
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
 

Author Comment

by:TKD
ID: 22873524
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 45

Expert Comment

by:sunnycoder
ID: 22873776
Is there a reason you want to use binary trees? Why not use n-ary trees.
0
 

Author Comment

by:TKD
ID: 22873833
I will use n-ary trees. But I can't find the samples code or reference. So I study the binary tree first.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22873848
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
 

Author Comment

by:TKD
ID: 22874486
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
 

Author Comment

by:TKD
ID: 22874604
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22882759
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22882760
>"An array of object" right?
Thats correct
0
 

Author Comment

by:TKD
ID: 22882939
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
 
LVL 45

Accepted Solution

by:
sunnycoder earned 200 total points
ID: 22900621
>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
 

Author Closing Comment

by:TKD
ID: 31512606
Thank you. I will follow the suggestions.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

This article describes some very basic things about SQL Server filegroups.
Shadow IT is coming out of the shadows as more businesses are choosing cloud-based applications. It is now a multi-cloud world for most organizations. Simultaneously, most businesses have yet to consolidate with one cloud provider or define an offic…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now