Channels ▼
RSS

C/C++

Patricia Tries

Source Code Accompanies This Article. Download It Now.


Konstantin Knizhnik is a software engineer at McObject. He can be reached at knizhnik@mcobject.com.


A B-Tree can locate keys with a specified prefix; for example, finding all stock symbols starting with "AAA." But some applications require the opposite search—locating keys that represent the longest prefixes of a specified value. Here a B-tree could perform several iterations, searching for different prefixes of the specified value starting from the longest, but this is inefficient. A much better index for prefix searches is the Patricia trie, which is a variation of a binary tree. Typically, the Patricia trie is used for performing two tasks—phone routing and IP filtering. In the first case, given an incoming phone call and a table of operators with known prefixes, the right operator must be selected to handle the call. The second case deals with IP addresses: Given IP masks for valid/rejected domains, a received HTTP request should be classified as accepted, rejected, redirected, and so on. The following is a schema definition for a routing table. The mask is represented by a vector of bits (Booleans).

class Route
{
	Vector<bool> dest;
	uint4 gateway;
	uint4 interf;
	uint2 metric;
	unique patricia<dest> by_dest;
};

To locate the proper route for the received IP address, the following search is performed in eXtremeDB using a Patricia trie:


mco_cursor_t csr;
if (MCO_S_OK == Route_by_dest_index_cursor(trans, &csr)) {
    uint1 mask[4];
    make_mask(mask, ip, 32);
    /* find routes which mask match this IP address */
    if (MCO_S_OK == Route_by_dest_prefix_match(trans, &csr, mask,32);
        Route route;
        Route_from_cursor(trans, &csr, &route);
        ...
    }
}

The following code (from McObject's eXtremeDB embedded database; www.mcobject.com) converts the integer number representing the IP address into an array of bits:


void make_mask(uint1* mask, uint4 val, int bitnum)
{
    int i;
    val = val >> (32-bitnum);
    memset(mask, 0, 4);
    for (i = 0; i < bitnum; i++, val = val >> 1)
    {
         mask[i >> 3] |= (val&1) << (i&7);
    }
}


Knowledge of specialized indexes enables faster development, more efficient code, and the ability to work with more complex data structures.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video