Skip to content

Fast, robust and memory-savvy IP radix tree (Patricia trie) implementation in Java

License

Notifications You must be signed in to change notification settings

openstat/ip-radix-tree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

This project provides a fast, robust and memory-savvy implementation of IPv4 radix tree (AKA Patricia trie) in Java.

The API roughly follows Java Collections API and can be easily demonstrated in a following snippet:

IPv4RadixIntTree tr = new IPv4RadixIntTree();
tr.put(0x0a000000, 0xffffff00, 42);
tr.put(0x0a000000, 0xff000000, 69);
tr.put("10.0.3.0/24", 123);
int v1 = tr.selectValue(0x0a202020); // => 69, as 10.32.32.32 belongs to 10.0.0.0/8
int v2 = tr.selectValue(0x0a000020); // => 42, as 10.0.0.32 belongs to 10.0.0.0/24
int v3 = tr.selectValue("10.0.3.5"); // => 123, as 10.0.3.5 belongs to 10.0.3.0/24

Memory consumption

Memory consumption for this implementation is tuned to be the lowest possible. No Java internal objects or object references are used, as they consume too much memory per node (on 64-bit JVM, it's something like 32 bytes per object).

We use pre-allocated simple Java int[] arrays, one for left branch pointers, one for right branch pointers and one for values. It takes exactly 3 * 4 = 12 bytes per node.

Number of nodes in a tree greatly depends on tree topology: a rough estimate for generic IPv4 routing trees is something like from 3 up to 8 times the number of IP prefixes.

For example, a test case included with this distribution has 392415 IP prefixes and it generates up to 946225 nodes in memory, thus consuming about 10.8 megabytes of heap.

About

Fast, robust and memory-savvy IP radix tree (Patricia trie) implementation in Java

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages