any<\/em> template type - including pointers, and handle the disposal as needed.<\/p>\nI've made adjustments like this for the dkit::pool<\/tt> where I handled plain-old-datatypes as well as pointers, and disposed of the pointer values properly. I needed to be able to do the same thing for the trie.<\/p>\n
The second improvement this time around is to stop trying to make the trie do everything<\/em> associated with processing of its contents. In the past, I'd had the trie scan the Messages for symbol limits, values, etc. This was very<\/em><\/strong> inefficient, as it was all in the trie, and therefore very<\/em><\/strong> specific. I needed to move away from this and use functors that could be passed into the trie, and then operated on each of the valid elements in the trie. This is a far<\/em> better scheme as it allows the user to make any<\/em> processing on the Nodes in the trie, and this is far more flexible than trying to implement the methods in the trie itself.<\/p>\nThe solution to this was to define a class within the templates trie so that I could create functors like this:<\/p>\n
class<\/span> counter :<\/span> public<\/span> dkit::<\/span>trie<\/span><<\/span>blob *<\/span>, dkit::<\/span>uint64_key<\/span>><\/span>::<\/span>functor<\/span>\n {<\/span>\n public<\/span>:<\/span>\n counter(<\/span>)<\/span> :<\/span> _cnt(<\/span>0<\/span>)<\/span> {<\/span> }<\/span>\n virtual<\/span> ~counter(<\/span>)<\/span> {<\/span> }<\/span>\n virtual<\/span> bool<\/span> process(<\/span>\n volatile<\/span> dkit::<\/span>trie<\/span><<\/span>blob *<\/span>, dkit::<\/span>uint64_key<\/span>><\/span>::<\/span>Node<\/span> &<\/span> aNode )<\/span>\n {<\/span>\n ++<\/span>_cnt;<\/span>\n return<\/span> true<\/span>;<\/span>\n }<\/span>\n uint64_t<\/span> getCount(<\/span>)<\/span> {<\/span> return<\/span> _cnt;<\/span> }<\/span>\n private<\/span>:<\/span>\n uint64_t<\/span> _cnt;<\/span>\n }<\/span>;<\/span><\/pre>\nThey are easy to create, and you can apply them to all the elements in the trie with a simple call:<\/p>\n
counter worker;<\/span>\n m.apply<\/span>(<\/span>worker)<\/span>;<\/span><\/pre>\nThe final improvement was to switch from loop-based indexing into the trie to recursion-based accessing. There are a few reasons for this - but the most is flexibility and code simplicity. When you have a fixed key length, and you use looping to traverse the trie, you have a fixed series of nested for loops. This seems all well and good, but it makes for a very fixed<\/em> structure and the code isn't all the easy to read.<\/p>\nBy going with a better class structure for building the trie, we're able to take advantage of recursion, and then the only parameter to the \"depth\" of the trie, and the corresponding size of the key, is the number of branches<\/em> used in the construction of the tree in the trie. If we put the parameter in the creation method then there's a single point where we stop creating branches, and instead make the leaf nodes. From this point, the same code that traverses a 64-bit key trie works for a 128-bit trie.<\/p>\nAt least insofar as the movement in the trie.<\/p>\n
Once I got it all working, the next thing was to look at the recursion vs. looping design. I wanted to make sure that I had the most performant design. What I found was that the recursion was about 25% faster<\/em> than the looping structure. I'm guessing it's due to tail-recursion optimization by the compiler, but I'm not positive. I repeated the tests, and the difference is real, that's good enough for me.<\/p>\nOnce it was all done, I wondered how hard it might be to make the key size another<\/em> parameter in the template. Well\u2026 since we're using recursion, and therefore, the size of the key space is only used in one space, the solution was pretty simple. Start by defining the different sizes we'll accept:<\/p>\n namespace<\/span> dkit {<\/span>\n enum<\/span> trie_key_size {<\/span>\n uint16_key =<\/span> 2<\/span>,\n uint32_key =<\/span> 4<\/span>,\n uint64_key =<\/span> 8<\/span>,\n uint128_key =<\/span> 16<\/span>,\n }<\/span>;<\/span>\n }<\/span> \/\/ end of namespace dkit<\/span><\/pre>\nand then we convert this to the test we need in the branch creation:<\/p>\n
enum<\/span> {<\/span>\n eLastBranch =<\/span> (<\/span>N -<\/span> 2<\/span>)<\/span>\n }<\/span>;<\/span><\/pre>\nIn the code, we then have:<\/p>\n
virtual<\/span> volatile<\/span> Node *<\/span>getOrCreateNodeForKey(<\/span> const<\/span> uint8_t<\/span> aKey[<\/span>]<\/span>,\n uint16_t<\/span> aStep )<\/span>\n {<\/span>\n volatile<\/span> Node *<\/span>n =<\/span> NULL<\/span>;<\/span>\n \n \/\/ get the index we're working on (re-used a few times)<\/span>\n uint8_t<\/span> idx =<\/span> aKey[<\/span>aStep]<\/span>;<\/span>\n Component *<\/span>curr =<\/span> __sync_or_and_fetch(<\/span>&<\/span>kids[<\/span>idx]<\/span>, 0x0<\/span>)<\/span>;<\/span>\n if<\/span> (<\/span>curr ==<\/span> NULL<\/span>)<\/span> {<\/span>\n \/\/ create a new Branch or Leaf for this part of the trie<\/span>\n bool<\/span> createBranch =<\/span> true<\/span>;<\/span>\n if<\/span> (<\/span>aStep <<\/span> eLastBranch)<\/span> {<\/span>\n curr =<\/span> new<\/span> Branch(<\/span>)<\/span>;<\/span>\n }<\/span> else<\/span> {<\/span>\n curr =<\/span> new<\/span> Leaf(<\/span>)<\/span>;<\/span>\n createBranch =<\/span> false<\/span>;<\/span>\n }<\/span>\n \/\/ throw a runtime exception if we couldn't make it<\/span>\n if<\/span> (<\/span>curr ==<\/span> NULL<\/span>)<\/span> {<\/span>\n if<\/span> (<\/span>createBranch)<\/span> {<\/span>\n throw<\/span> std::<\/span>runtime_error<\/span>(<\/span>"[Branch::getOrCreateNodeForKey] "<\/span>\n "Unable to create new Branch for the trie!"<\/span>)<\/span>;<\/span>\n }<\/span> else<\/span> {<\/span>\n throw<\/span> std::<\/span>runtime_error<\/span>(<\/span>"[Branch::getOrCreateNodeForKey] "<\/span>\n "Unable to create new Leaf for the trie!"<\/span>)<\/span>;<\/span>\n }<\/span>\n }<\/span>\n \/\/ see if we can put this new one in the right place<\/span>\n if<\/span> (<\/span>!<\/span>__sync_bool_compare_and_swap(<\/span>&<\/span>kids[<\/span>idx]<\/span>, NULL<\/span>, curr)<\/span>)<\/span> {<\/span>\n \/\/ someone beat us to it! Delete what we just made...<\/span>\n delete<\/span> curr;<\/span>\n \/\/ ...and get what is there now<\/span>\n curr =<\/span> __sync_or_and_fetch(<\/span>&<\/span>kids[<\/span>idx]<\/span>, 0x0<\/span>)<\/span>;<\/span>\n }<\/span>\n }<\/span>\n \n \/\/ now pass down to that next branch the request to fill<\/span>\n if<\/span> (<\/span>curr !<\/span>=<\/span> NULL<\/span>)<\/span> {<\/span>\n n =<\/span> curr-<\/span>><\/span>getOrCreateNodeForKey(<\/span>aKey, (<\/span>aStep +<\/span>
![\"DKit](\"http:\/\/bobbeaty.com\/wp\/wp-content\/uploads\/2012\/03\/DKit.jpg\" "\\"DKit.jpg\\"")
<\/p>\n