You use the patricia tree functions to access either the JUNOS system data or your own local data. (For general information about patricia trees, see The Patricia Tree.)
To use the patricia tree functions, you need two basic data structures:
patroot) patnode)patroot is hidden; the implementation of patnode is public, but applications should avoid accessing the internals.
You embed the patnode structure in your own structure along with a key for accessing the values. You can embed the key in two ways:
patnode stucture:
struct foo {
...;
patnode patricia;
u_char key[KEYSIZE];
...;
}
struct bar {
...;
patnode patricia;
sockaddr_un key_ptr;
...;
}
In either case, you can also specify an offset to the actual key.
For example, the Hello World application uses the messages as the key and defines the node structure as follows:
typedef struct helloworld_data_s {
patnode node;
char message[MESSAGE_STR_SIZE];
} helloworld_data_t;
patricia_root_init(). If you do not pass a patroot pointer, JUNOS allocates and returns one; otherwise, the root pointer you specify is filled in.For example, here is how the Hello World sample application initializes its tree:
static patroot root;
...
void
init_messages_ds (void)
{
patricia_root_init(&root, FALSE, MESSAGE_STR_SIZE, 0);
}
The parameters give the address of the root, indicate that the key is not a pointer, specify the size of the key, and give the offset to the key from the end of the patricia tree node structure.
You can use your own allocate and free routines for the patroot structure by calling patricia_set_allocator().
For each node that you wish to add to the tree, you must first initialize the node with a call to patricia_node_init_length(), passing the node and the length of the associated key in bytes. You can also call patricia_node_init() if the key length was fixed at root initialization.
patricia_node_init() has been called, you can call patricia_add() to add the node to the tree. Once you make this call, the patnode maintains the whole data structure in the tree.
After calling patricia_add(), you cannot change the key.
The following function from the Hello World application allocates memory for its data, adds it to the tree, and performs basic error checking (INSIST_ERR is defined in junos_trace.h in libjunos-sdk):
static helloworld_data_t *
add_message (const char * message)
{
helloworld_data_t *data;
/* allocate & initialize data */
data = calloc(1, sizeof(helloworld_data_t)); /* calloc zeros mem */
INSIST_ERR(data != NULL); /* check that allocation worked */
INSIST_ERR(strlen(message) < MESSAGE_STR_SIZE); /* check for length */
strcpy(data->message, message);
/* add to data_root patricia tree */
patricia_node_init_length(&data->node,
strlen(data->message) + 1);
if (!patricia_add(&root, &data->node)) {
return NULL;
}
return data;
}
patricia_add() patricia_delete() patricia_get() patricia_getnext() patricia_find_next() patricia_find_prev() patricia_subtree_match() patricia_subtree_next() patricia_add() function adds a node to the tree. Applications initialize the node before adding it. For example, the Hello World application first calls patricia_node_init_length() to initialize the node with a pointer of the specified length, and then adds a message to the tree as follows:
static helloworld_data_t *
add_message (const char * message)
{
helloworld_data_t *data;
/* allocate & initialize data */
data = calloc(1, sizeof(helloworld_data_t)); /* calloc zeros mem */
INSIST_ERR(data != NULL); /* check that allocation worked */
INSIST_ERR(strlen(message) < MESSAGE_STR_SIZE); /* check for length */
strcpy(data->message, message);
/* add to data_root patricia tree */
patricia_node_init_length(&data->node,
strlen(data->message) + 1);
if (!patricia_add(&root, &data->node)) {
free(data);
return NULL;
}
return data;
}
patricia_get() looks up a node having the specified key and key length in bytes.patricia_getnext(), given a key and key length in bytes, returns a node in the tree at least as large as the key specified.patricia_find_next(), given a node in the tree, finds the node with the next numerically larger key.patricia_find_prev(), given a node in the tree, finds the node with the next numerically smaller key.patricia_subtree_match(), given a prefix and a prefix length in bits, finds the node with the numerically smallest key in the tree which includes this prefix.patricia_subtree_next(), given a node in the tree and a prefix length in bits, returns the next numerically larger node in the tree that shares a prefix with the node specified.PATNODE_TO_STRUCT macro to map the tree back to the structure that holds your data, avoiding the necessity of working directly with the tree. That is, this macro allows you to define functions that hide the patricia structure from the rest of your code. The macro is defined as:
#define PATNODE_TO_STRUCT ( procname, structname, fieldname )
When you call PATNODE_TO_STRUCT, the compiler generates a function for which procname, structname, and fieldname are replaced by the parameter values you pass. For example, the Hello World application invokes the macro as follows to map the tree to its helloworld_data_t structure:
PATNODE_TO_STRUCT(data_entry, helloworld_data_t, node)
PATNODE_TO_STRUCT macro to avoid producing a semicolon at the end of the generated function.
static inline helloworld_data_t * data_entry (patnode *ptr)
{
assert(STRUCT_SIZEOF(helloworld_data_t, node) == sizeof(patnode));
if (ptr)
return((helloworld_data_t *) (((u_char *) ptr) - offsetof(helloworld_data_t, node)));
return(NULL);
}
The application now has a static inline function called data_entry(), which takes a pointer to a node in the tree and returns a pointer to a data item of type helloworld_data_t.
The application uses the generated function when it needs to retrieve data from the tree. For example, the following code retrieves the first Hello message stored by the daemon and returns a pointer to the first entry in the tree if one exists:
helloworld_data_t *
first_message (void)
{
return data_entry(patricia_find_next(&root, NULL));
}
patricia_delete() function deletes a node from the tree. When you are finished using the tree, you can call patricia_root_delete() on the empty tree to deallocate the root information if the root was allocated at initialization time.The Hello World application deletes a message node as follows:
static int
delete_message (helloworld_data_t *data)
{
/* remove data from patricia tree */
if (!patricia_delete(&root, &data->node)) {
free(data);
return EFAIL;
}
free(data);
return SUCCESS;
}
To delete all the nodes in the tree, the application calls delete_message() in a loop in the clear_messages() function:
static int
clear_messages (void)
{
helloworld_data_t *data = NULL;
while ((data = first_message()) != NULL) {
if(delete_message(data) == EFAIL) {
return EFAIL;
}
}
return SUCCESS;
}
The patricia tree functions are in sandbox/src/JUNOS/lib/libjuniper/h/jnx/patricia.h in your backing sandbox. Additional functions are defined to perform more specialized operations in patricia.h . See the library reference documentation for details.