Algorithm/steps to find Longest Prefix search in Patricia Trie

Question

Hello,

I am implementing Patricia tries for IP prefix lookup, I could get the code working for complete key match, but facing problems with prefix search, when there are keys which are prefixes of other keys, like:

1.2.3.0
1.2.0.0

Can anyone help me with the algorithm for prefix searches in the above case Should I consider these as keys of separate length (i.e, /24 and 16) ?

Answer 1

This library might give you some ideas.

Answer 2

Take a look at Net-Patricia. This is an implementation of a Patricia trie to look up IP addresses. The interface is perl, but the underlying code is in C. Here is a link, but many CPAN archives should have it:

http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15%5F07/libpatricia/patricia.c