dbm_patricia.h File Reference

Patricia tree APIs. More...

#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include "dbm_offset.h"

Data Structures

struct  dbm_patnode_
 Patricia tree node. More...
struct  dbm_patroot_
 Patricia tree root. More...

Defines

#define DBM_PAT_MAXKEY   256
 The maximum length of a key, in bytes.
#define DBM_PATRICIA_LEN_TO_BIT(len)   ((u_int16_t) ((((len) - 1) << 8) | 0xff))
 A macro to initialize the `length' in a dbm_patnode at compile time given the length of a key.
#define DBM_PAT_NOBIT   (0)
 Bit number when no external node.
#define DBM_STRUCT_SIZEOF(_structure, _element)   (sizeof(((_structure*)0)->_element))
 Returns the sizeof for an element in a structure.
#define DBM_STRUCT_OFFSET(_structure, _elt1, _elt2)
 Returns the offset of _elt2 from the END of _elt1 within structure.
#define DBM_PATNODE_TO_STRUCT(procname, structname, fieldname)
 Macro to define an inline to map from a dbm_patnode entry back to the containing data structure.
#define DBM_PATRICIA_ROOT_INIT(_rootptr, _bool_key_is_ptr, _nodestruct, _nodeelement, _keyelt)
 Initialize a patricia root with a little more compile-time checking.
#define dbm_patricia_init_root(keybytes)   dbm_patricia_root_init(NULL, FALSE, (u_int16_t) (keybytes), 0)
#define dbm_patricia_delete_root(root)   dbm_patricia_root_delete ((root))
#define dbm_patricia_lookup_least(root)   dbm_patricia_find_next ((root), NULL)
#define dbm_patricia_lookup_greatest(root)   dbm_patricia_find_prev ((root), NULL)
#define dbm_patricia_get_next(root, node)   dbm_patricia_find_next ((root), (node))
#define dbm_patricia_get_previous(root, node)   dbm_patricia_find_prev((root), (node))
#define dbm_patricia_cons_lookup_least(root)   dbm_patricia_cons_find_next ((root), NULL)
#define dbm_patricia_cons_lookup_least(root)   dbm_patricia_cons_find_next ((root), NULL)
#define dbm_patricia_cons_lookup_greatest(root)   dbm_patricia_cons_find_prev ((root), NULL)
#define dbm_patricia_cons_get_next(root, node)   dbm_patricia_cons_find_next ((root), (node))
#define dbm_patricia_cons_get_previous(root, node)   dbm_patricia_cons_find_prev((root), (node))

Typedefs

typedef dbm_patnode_ dbm_patnode
 Patricia tree node.
typedef dbm_patroot_ dbm_patroot
 Patricia tree root.
typedef dbm_patroot *(* dbm_patricia_root_alloc_fn )(void)
typedef void(* dbm_patricia_root_free_fn )(dbm_patroot *)
typedef dbm_patnode_ dbm_patnode_t
typedef dbm_patroot_ dbm_patroot_t

Functions

dbm_patrootdbm_patricia_root_init (dbm_patroot *root, boolean key_is_ptr, u_int16_t key_bytes, u_int8_t key_offset)
 Initializes a patricia tree root.
void dbm_patricia_root_delete (dbm_patroot *root)
 Deletes a patricia tree root.
void dbm_patricia_node_init_length (dbm_patnode *node, u_int16_t key_bytes)
 Initializes a patricia tree node as having a key with that is the specified number of bytes in length.
boolean dbm_patricia_add (dbm_patroot *root, dbm_patnode *node)
 Adds a new node to the tree.
boolean dbm_patricia_delete (dbm_patroot *root, dbm_patnode *node)
 Deletes a node from the tree.
dbm_patnodedbm_patricia_find_next (dbm_patroot *root, dbm_patnode *node)
 Given a node in the tree, find the node with the next numerically larger key.
dbm_patnodedbm_patricia_find_prev (dbm_patroot *root, dbm_patnode *node)
 Given a node in the tree, find the node with the next numerically smaller key.
dbm_patnodedbm_patricia_subtree_match (dbm_patroot *root, u_int16_t prefix_len, const void *prefix)
 Given a prefix and a prefix length in bits, find the node with the numerically smallest key in the tree which includes this prefix.
dbm_patnodedbm_patricia_subtree_next (dbm_patroot *root, dbm_patnode *node, u_int16_t prefix_len)
 Given a node in the tree, and a prefix length in bits, return the next numerically larger node in the tree which shares a prefix with the node specified.
dbm_patnodedbm_patricia_get (dbm_patroot *root, u_int16_t key_bytes, const void *key)
 Looks up a node having the specified key and key length in bytes.
dbm_patnodedbm_patricia_getnext (dbm_patroot *root, u_int16_t key_bytes, const void *key, boolean return_eq)
 Given a key and key length in bytes, return a node in the tree which is at least as large as the key specified.
boolean dbm_patricia_node_in_tree (const dbm_patnode *node)
 Determines if a patricia tree node is contained within a tree.
int dbm_patricia_compare_nodes (dbm_patroot *root, dbm_patnode *left, dbm_patnode *right)
 Given two patricia tree nodes, determine if the first has a key which is numerically lesser, equal, or greater than the key of the second.
void dbm_patricia_set_allocator (dbm_patricia_root_alloc_fn my_alloc, dbm_patricia_root_free_fn my_free)
 Sets allocation and free routines for patricia tree root structures.
const dbm_patnodedbm_patricia_cons_get (const dbm_patroot *root, const u_int16_t key_bytes, const void *key)
 Constant tree form of dbm_patricia_get().
const dbm_patnodedbm_patricia_cons_find_next (const dbm_patroot *root, const dbm_patnode *node)
 Constant tree form of dbm_patricia_find_next().
const dbm_patnodedbm_patricia_cons_find_prev (const dbm_patroot *root, const dbm_patnode *node)
 Constant tree form of dbm_patricia_find_prev().
const dbm_patnodedbm_patricia_cons_subtree_match (const dbm_patroot *root, const u_int16_t prefix_len, const void *prefix)
 Constant tree form of dbm_patricia_subtree_match().
const dbm_patnodedbm_patricia_cons_subtree_next (const dbm_patroot *root, const dbm_patnode *node, const u_int16_t prefix_len)
 Constant tree form of dbm_patricia_subtree_next().

Variables

const u_int8_t dbm_patricia_hi_bit_table []


Detailed Description

Patricia tree APIs.

This file contains the public data structures for the patricia tree package. This package is applicable to searching a non-overlapping keyspace of pseudo-random data with fixed size keys. The patricia tree is not balanced, so this package is NOT appropriate for highly skewed data. The package can deal with variable length (in byte increments) keys, but only when it can be guaranteed that no key in the tree is a prefix of another (null-terminated strings have this property if you include the '\0' in the key).

This package supports keys up to 256 bytes in length. For random data, all operations are O(log n). There are two necessary data structures: one is the root of a tree (type patroot), and the contents of this are hidden from you. The other is a node (type patnode). The contents of this data structure are (unfortunately) public to make the compiler happy.

To use this package: First imbed the patnode structure in your data structure. You have two choices for the key. The first is to embed the key into the data structure immediately following the patnode stucture, as in:

                struct foobar {
                    ...;
                    dbm_patnode patricia;
                    u_char  key[KEYSIZE];
                    ...;
                }

The other choice is to embed a pointer to the key material immediately following the data structure, as in

                struct blech {
                    ...;
                    dbm_patnode patricia;
                    dbm_offset_t key_ptr;
                    ...;
                }

In either case you can also specify an offset to the actual key material. The choice of key location and offset, and the length of keys stored in the tree if this is fixed, is specified in a call to dbm_patricia_root_init(). If no patroot pointer is passed in one is allocated and returned, otherwise the specified root pointer is filled in.

If you want to use your own allocate & free routines for patroots, set them using dbm_patricia_set_allocator().

For each node that you wish to add to the tree, you must first initialize the node with a call to dbm_patricia_node_init_length() with the node and the length of the associated key, in bytes. You can also call dbm_patricia_node_init() if the key length was fixed at root initialization. Then, once the key is installed in the node, you may call dbm_patricia_add(). Note that after calling dbm_patricia_add(), you may NOT change the key. You should also note that the entire key field to the length specified to dbm_patricia_length() (or all the way to `KEYSIZE' if the tree is built with fixed-length keys) may be examined.

Once the tree is initialized you can use the following functions:

dbm_patricia_add() dbm_patricia_delete() dbm_patricia_get() dbm_patricia_getnext() dbm_patricia_find_next() dbm_patricia_find_prev() dbm_patricia_subtree_match() dbm_patricia_subtree_next()

When you're done with the tree, you can call dbm_patricia_root_delete() on an empty tree to get rid of the root information if the root was allocated at initialization time.

Generally you will not want to deal with the patricia structure directly, so it's helpful to be able to be able to get back to the primary structure. This can be done with the DBM_PATNODE_TO_STRUCT() macro. Using this, you can then easily define functions which completely hide the patricia structure from the rest of your code. This is STRONGLY recommended.


Define Documentation

#define DBM_PATNODE_TO_STRUCT procname,
structname,
fieldname   ) 
 

Value:

static inline structname * procname (dbm_patnode *ptr)\
    {\
        assert(DBM_STRUCT_SIZEOF(structname, fieldname) == sizeof(dbm_patnode));\
        if (ptr)\
            return(QUIET_CAST(structname *, ((u_char *) ptr) - \
                                    offsetof(structname, fieldname))); \
        return(NULL); \
     }
Macro to define an inline to map from a dbm_patnode entry back to the containing data structure.

This is just a handy way of defining the inline, which will return NULL if the dbm_patnode pointer is NULL, or the enclosing structure if not.

The assert() will be removed by the compiler unless your code is broken -- this is quite useful as a way to validate that you've given the right field for fieldname (a common mistake is to give the KEY field instead of the NODE field). It's harmless.

#define DBM_PATRICIA_LEN_TO_BIT len   )     ((u_int16_t) ((((len) - 1) << 8) | 0xff))
 

A macro to initialize the `length' in a dbm_patnode at compile time given the length of a key.

Good for the keyword tree. Note the length must be greater than zero.

#define DBM_PATRICIA_ROOT_INIT _rootptr,
_bool_key_is_ptr,
_nodestruct,
_nodeelement,
_keyelt   ) 
 

Value:

dbm_patricia_root_init(_rootptr, _bool_key_is_ptr,              \
                      DBM_STRUCT_SIZEOF(_nodestruct, _keyelt),          \
                      DBM_STRUCT_OFFSET(_nodestruct, _nodeelement, _keyelt))
Initialize a patricia root with a little more compile-time checking.

#define DBM_STRUCT_OFFSET _structure,
_elt1,
_elt2   ) 
 

Value:

(offsetof(_structure, _elt2) - (offsetof(_structure, _elt1) + \
                                      DBM_STRUCT_SIZEOF(_structure, _elt1)))
Returns the offset of _elt2 from the END of _elt1 within structure.


Function Documentation

boolean dbm_patricia_add dbm_patroot root,
dbm_patnode node
 

Adds a new node to the tree.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
TRUE if the node is successfully added; FALSE if the key you are adding is the same as, or overlaps with (variable length keys), something already in the tree.

int dbm_patricia_compare_nodes dbm_patroot root,
dbm_patnode left,
dbm_patnode right
 

Given two patricia tree nodes, determine if the first has a key which is numerically lesser, equal, or greater than the key of the second.

Parameters:
[in] root Pointer to patricia tree root
[in] left Pointer to patricia tree node
[in] right Pointer to patricia tree node
Returns:
Result of the comparison:
  • -1 if the key of the left node is numerically lesser than the right
  • 0 if the keys match
  • 1 if the left key is numerically greater than the right

const dbm_patnode* dbm_patricia_cons_find_next const dbm_patroot root,
const dbm_patnode node
 

Constant tree form of dbm_patricia_find_next().

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if a match is not found; Otherwise a const pointer to the next patricia tree node.
See also:
patricia_find_next

const dbm_patnode* dbm_patricia_cons_find_prev const dbm_patroot root,
const dbm_patnode node
 

Constant tree form of dbm_patricia_find_prev().

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if a match is not found; Otherwise a const pointer to the previous patricia tree node.
See also:
dbm_patricia_find_prev

const dbm_patnode* dbm_patricia_cons_get const dbm_patroot root,
const u_int16_t  key_bytes,
const void *  key
 

Constant tree form of dbm_patricia_get().

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Number of bytes in key
[in] key Pointer to key value
Returns:
NULL if a match is not found; Otherwise a const pointer to the matching patricia tree node.
See also:
patricia_get

const dbm_patnode* dbm_patricia_cons_subtree_match const dbm_patroot root,
const u_int16_t  prefix_len,
const void *  prefix
 

Constant tree form of dbm_patricia_subtree_match().

Parameters:
[in] root Pointer to patricia tree root
[in] prefix_len Length of prefix, in bits
[in] prefix Pointer to prefix
Returns:
NULL if no node in the tree has the prefix; Otherwise a pointer to the patricia tree node with the numerically smallest key which includes the prefix.
See also:
dbm_patricia_subtree_match

const dbm_patnode* dbm_patricia_cons_subtree_next const dbm_patroot root,
const dbm_patnode node,
const u_int16_t  prefix_len
 

Constant tree form of dbm_patricia_subtree_next().

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
[in] prefix_len Length of prefix, in bits
Returns:
A const pointer to next numerically larger patricia tree node.
See also:
dbm_patricia_subtree_next

boolean dbm_patricia_delete dbm_patroot root,
dbm_patnode node
 

Deletes a node from the tree.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
TRUE if the node is successfully deleted; FALSE if the specified node is not in the tree.

dbm_patnode* dbm_patricia_find_next dbm_patroot root,
dbm_patnode node
 

Given a node in the tree, find the node with the next numerically larger key.

If the given node is NULL, the numerically smallest node in the tree will be returned.

Note:
Good for tree walks.
Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if the specified node is already the largest; otherwise a pointer to the node with the next numerically larger key.

dbm_patnode* dbm_patricia_find_prev dbm_patroot root,
dbm_patnode node
 

Given a node in the tree, find the node with the next numerically smaller key.

If the given node is NULL, returns the numerically largest node in the tree.

Note:
The definitions of dbm_patricia_find_next() and dbm_patricia_find_prev() are such that
 node == dbm_patricia_find_prev(root, dbm_patricia_find_next(root, node));

will always be TRUE for any node in the tree or NULL.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if the specified node was the smallest; otherwise a pointer to the patricia tree node with next numerically smaller key.

dbm_patnode* dbm_patricia_get dbm_patroot root,
u_int16_t  key_bytes,
const void *  key
 

Looks up a node having the specified key and key length in bytes.

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Number of bytes in key
[in] key Pointer to key value
Returns:
NULL if a match is not found; otherwise a pointer to the matching patricia tree node

dbm_patnode* dbm_patricia_getnext dbm_patroot root,
u_int16_t  key_bytes,
const void *  key,
boolean  return_eq
 

Given a key and key length in bytes, return a node in the tree which is at least as large as the key specified.

The call has a parameter which modifies its behaviour when an exact match is found in the tree; you can either choose to have it return the exact match, if there is one, or you can have it always return a node with a larger key (a la SNMP getnext).

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Number of bytes in key
[in] key Pointer to key value
[in] return_eq FALSE for classic getnext
Returns:
A pointer to patricia tree node.

boolean dbm_patricia_node_in_tree const dbm_patnode node  ) 
 

Determines if a patricia tree node is contained within a tree.

Parameters:
[in] node Pointer to patricia tree node
Returns:
TRUE if the node is in the tree; FALSE otherwise.

void dbm_patricia_node_init_length dbm_patnode node,
u_int16_t  key_bytes
 

Initializes a patricia tree node as having a key with that is the specified number of bytes in length.

Parameters:
[in] node Pointer to patricia tree node
[in] key_bytes Length of the key, in bytes

void dbm_patricia_root_delete dbm_patroot root  ) 
 

Deletes a patricia tree root.

Note:
An assertion failure will occur if the tree is not empty when this function is called.
Parameters:
[in] root Pointer to patricia tree root

dbm_patroot* dbm_patricia_root_init dbm_patroot root,
boolean  key_is_ptr,
u_int16_t  key_bytes,
u_int8_t  key_offset
 

Initializes a patricia tree root.

Parameters:
[in] root Pointer to patricia tree root
[in] key_is_ptr Indicator that the key located at the offset is actually a pointer or not
[in] key_bytes Number of bytes in the key
[in] key_offset Offset to the key from the end of the patricia tree node structure
Returns:
A pointer to the patricia tree root.

void dbm_patricia_set_allocator dbm_patricia_root_alloc_fn  my_alloc,
dbm_patricia_root_free_fn  my_free
 

Sets allocation and free routines for patricia tree root structures.

Parameters:
[in] my_alloc Function to call when patricia tree root is allocated
[in] my_free Function to call when patricia tree root is freed

dbm_patnode* dbm_patricia_subtree_match dbm_patroot root,
u_int16_t  prefix_len,
const void *  prefix
 

Given a prefix and a prefix length in bits, find the node with the numerically smallest key in the tree which includes this prefix.

Parameters:
[in] root Pointer to patricia tree root
[in] prefix_len Length of prefix, in bits
[in] prefix Pointer to prefix
Returns:
NULL if no node in the tree has the prefix; otherwise a pointer to the patricia tree node with the numerically smallest key which includes the prefix.

dbm_patnode* dbm_patricia_subtree_next dbm_patroot root,
dbm_patnode node,
u_int16_t  prefix_len
 

Given a node in the tree, and a prefix length in bits, return the next numerically larger node in the tree which shares a prefix with the node specified.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
[in] prefix_len Length of prefix, in bits
Returns:
A pointer to next numerically larger patricia tree node.


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:23:19 2010 for libddl-access by Doxygen 1.4.5