Multi-Key Radix PATRICIA Fast Search
rdx is a library of routines for building a data structure based on the radix PATRICIA algorithm(modified) for storing data nodes accessible by an arbitrary number of keys of arbitrary length. The search algorithm characteristics for all keys is identical. Among 8 routines is rdx_pat_verify()
that at any time can be used to verify the integrity of the data structure with 25 checks.
See article “Using multikey radix PATRICIA fast search” by Richard Hogaboom, June 2007, Embedded Systems Programming /Embedded Systems Design magazine.
Download the latest Github code.
Multi-key Radix PATRICIA Fast Search – OO C++ – A header only class(MKRdxPat.hpp)
The MKRdxPat class allows the allocation of a fixed sized contiguous data store that holds data nodes of an arbitrary structure that may be accessed with any number of keys of any size with the PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric)(1,2,3) fast search algorithm. MKRdxPat is particularly suited to applications that require complex data structures be contiguously stored and accessed with an algorithm of known fast character with any of several possible keys, either singly of several simultaneously. MKRdxPat is unique, as far as I know, in allowing search with multiple keys of any length. If the application only requires a single key, this is OK; just set num_keys to 1 in the constructor call.
Github repo: https://github.com/rahogaboom/rdx
“Check out https://github.com/rahogaboom/rdx for the latest release.n The Author: Richard A Hogaboom”
“Go to https://github.com/rahogaboom/rdx for the release of a fully OO C++ version of Multi-Key Radix PATRICIA Fast Search. This version allows creation in the same compilation unit of any number of tries, each with their own specification of the numb
“08/29/2016 Go to https://github.com/rahogaboom/rdx for the v1.1.4 release. Improvements to doc, cut/paste example test code, performance test(real BGP prefix data) and additional member functions(clone to larger trie, accessor functions) The Auth
“2019/01/18 Go to github.com/rahogaboom for the v1.1.5 release – a C++ header file only class.”