Using the Patricia Tree Library

The JUNOS system stores its configuration data in patricia trees, and your applications can also store local data using these structures.

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:

The implementation of 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:

Initializing the Tree

You specify the key location and offset, and the length of keys stored in the tree if this is fixed, when you initialize the tree by calling 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.

Adding Data

Once both the key and the node are in the data structure, and 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;
}

Using the Functions

Once the tree is initialized, you can use functions such as the following to add, delete, and access data:

Adding Data

The 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;
}

Retrieving Data

There are various functions for retrieving data depending on how you need to search for it. Following is a sampling of the most common ones; see the library reference documentation for the complete set.

Using PATNODE_TO_STRUCT()

You can use the 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)

Note:
There is no semicolon after the PATNODE_TO_STRUCT macro to avoid producing a semicolon at the end of the generated function.
The following function is generated:

 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));
}

Deleting Data

The 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.


2007-2009 Juniper Networks, Inc. All rights reserved. The information contained herein is confidential information of Juniper Networks, Inc., and may not be used, disclosed, distributed, modified, or copied without the prior written consent of Juniper Networks, Inc. in an express license. This information is subject to change by Juniper Networks, Inc. Juniper Networks, the Juniper Networks logo, and JUNOS are registered trademarks of Juniper Networks, Inc. in the United States and other countries. All other trademarks, service marks, registered trademarks, or registered service marks are the property of their respective owners.
Generated on Sun May 30 20:26:47 2010 for Juniper Networks Partner Solution Development Platform JUNOS SDK 10.2R1 by Doxygen 1.4.5