C++ Radix Tree Implementation - Cemetech | Forum | Calculator Programming [Topic]

» Forum > Calculator Programming

»
» View previous topic :: View next topic

elfprince13
2
OVER NINE THOUSAND! (Posts: 11872)

C++ Radix Tree Implementation
16 Mar 2011 01:30:43 am
Last edited by elfprince13 on 13 Apr 2011 07:24:34 pm; edited 2 times in total

Hey everyone, I'm implementing a radix tree to handle the cache lookups and insertions in FreeBuild. Anyone mind lending a second set of eyes to my find (and the other ones as I go) method to look for logic errors?

[edit]
I think this is working correctly =)

Code:

LDCacheNode * LDCacheNode::find(string nodeName, int depth) {


        string ds("");


        const char * dsc;


        if(depth >= 0){


                depth++;


                ds = string(depth,' ');


        }


        dsc = ds.c_str();


        string commonPrefix = findCommonPrefix(mPrefix,nodeName);


        int cpS = commonPrefix.size();


        int nnS = nodeName.size();


        int mpS = mPrefix.size();


        LDCacheNode * retNode;


        if(depth >= 0){


                Con::printf("%sLooking for %s, mPrefix is \"%s\"",dsc, nodeName.c_str(), mPrefix.c_str());


                Con::printf("%s- Node has children - ",dsc);


                for(set<LDCacheNode*,STLDereferencer>::iterator it = mSuffixes.begin(); (*it) != NULL && it != mSuffixes.end(); it++){


                        Con::printf("%s-- --- %s",dsc,(*it)->mPrefix.c_str());


                }


                


        }


        if(nnS == mpS && mpS == cpS){ // Same


                if(depth >= 0) Con::printf("%s - Found it",dsc);


                retNode = this;


        } else if((cpS == nnS) || mSuffixes.size() == 0){ // Not in the tree.


                if(depth >= 0) Con::printf("%s - the search is the full common prefix, but we don't match this",dsc);


                retNode = NULL;


        } else {


                string suffix = nodeName.substr(cpS, nnS - cpS);


                


                retNode = NULL;


                


                for(set<LDCacheNode*,STLDereferencer>::iterator checkNode = mSuffixes.begin();


                        (*checkNode) != NULL && checkNode != mSuffixes.end();


                        checkNode++) {


                        


                        if(findCommonPrefix((*checkNode)->mPrefix,suffix) != ""){


                                if(depth >= 0) Con::printf("%s - found matching prefix \"%s\"",dsc,(*checkNode)->mPrefix.c_str());


                                retNode = (*checkNode)->find(suffix,depth);


                                break;


                        }


                }


        }





        return retNode;


}

elfprince13
2
OVER NINE THOUSAND! (Posts: 11872)

16 Mar 2011 02:43:39 pm
Last edited by elfprince13 on 13 Apr 2011 07:25:04 pm; edited 1 time in total

Here's my insert method if anyone cares to take a look at this or the previous method.
[edit]
The posted version appears to be working, but I'm still not entirely sure about the find method. I'll consider implementing delete as well, but I'm not convinced it is necessary for this use. I'm also not satisfied with the structure of my if statements being as clean as possible, so any suggestions are welcome on that front.

Code:

LDCacheNode * LDCacheNode::insert(string nodeName, LDFileData * contents, int depth){


        string ds;


        const char * dsc;


        if(depth >= 0){


                depth++;


                ds = string(depth,' ');


        }


        dsc = ds.c_str();


        string commonPrefix = findCommonPrefix(mPrefix,nodeName);


        string curSuffix;


        AssertFatal(commonPrefix != "" || mPrefix == "", "We have arrived at a non-root node, and the common prefix is empty. This should never happen");


        int cpS = commonPrefix.size();


        int nnS = nodeName.size();


        int mpS = mPrefix.size();


        LDCacheNode * retNode;


        if((mpS == 0 && cpS == 0) || (cpS < nnS && cpS == mpS)){ // ("","something") or ("cat","catsup")


                curSuffix = nodeName.substr(cpS, nnS - cpS);


                LDCacheNode * sufNode = new LDCacheNode(curSuffix);


                LDCacheNode * checkNode = NULL;


                for(set<LDCacheNode*,STLDereferencer>::iterator checkIt = mSuffixes.begin();


                        (*checkIt) != NULL && checkIt != mSuffixes.end(); 


                        checkIt++) {


                        


                        checkNode = *checkIt;


                        if(findCommonPrefix(curSuffix,checkNode->mPrefix) == "") checkNode = NULL;


                        else break;


                }


                if(checkNode == NULL){


                        mSuffixes.insert(sufNode);


                        sufNode->setContents(contents);


                        retNode = sufNode;


                } else {


                        retNode = checkNode->insert(curSuffix, contents, depth);


                        delete sufNode;


                }


                        


        }else if(nnS == cpS && cpS == mpS){ // ("catsup","catsup")


                AssertFatal(mContents == NULL || contents == NULL,"Overwriting LDCacheNode contents. This shouldn't happen, and the error is with whoever thought the same file needed to be inserted twice (see callstack).");


                if(contents != NULL){


                        if(mContents != NULL) Con::errorf("LDCacheNode::insert() - Overwriting LDCacheNode contents. This should never happen - try running in DEBUG mode.");


                        mContents = contents;


                }


                retNode = this;


        } else if (cpS > 0 && cpS < mpS){ // ("catsup","cat")


                // We split!


                curSuffix = mPrefix.substr(cpS, mpS - cpS);


                LDCacheNode * newChild = new LDCacheNode(curSuffix, mContents);


                newChild->mSuffixes = mSuffixes;


                


                mSuffixes.clear();


                mSuffixes.insert(newChild);


                mPrefix = commonPrefix;


                if(nnS == cpS){


                        mContents = contents;


                        retNode = this;


                } else{


                        curSuffix = nodeName.substr(cpS, nnS - cpS);


                        retNode = new LDCacheNode(curSuffix, contents);


                        mSuffixes.insert(retNode);


                }


        } else{ // WTF?


                retNode = NULL;


                Con::errorf("LDCacheNode::insert() - This is a peculiar circumstance. Try running in DEBUG mode");


                Con::errorf("LDCacheNode::insert() - node has %s, trying to insert %s (common prefix %s)",


                                        mPrefix.c_str(), nodeName.c_str(), commonPrefix.c_str());


                Con::errorf("LDCacheNode::insert() - Node has children - ");


                for(set<LDCacheNode*,STLDereferencer>::iterator it = mSuffixes.begin(); (*it) != NULL && it != mSuffixes.end(); it++){


                        Con::errorf("LDCacheNode::insert() --- %s",(*it)->mPrefix.c_str());


                }


                AssertFatal(false, "LDCacheNode::insert() - This is a peculiar circumstance. Please inspect me in the Debugger");


        }


        


        return retNode;


}

KermMartian
Site Admin (Posts: 64055)

19 Mar 2011 12:19:44 am

Great progress here, Elfprince! I'm excited for near and far future Freebuild progress, and I remain confident that one day we will get to implement trains.

elfprince13
2
OVER NINE THOUSAND! (Posts: 11872)

13 Apr 2011 07:29:54 pm

Updated this. I've rewritten both find and insert to iterate linearly over child nodes rather than attempting to get performance which is logarithmic in the number of children using the lower_bound() iterator available to std::set (which is implemented with a Red/Black tree). This makes the code slightly slower at the benefit of greatly improved readability and maintainability.

To be clear: I'm not iterating linearly over the whole tree (which would utterly defeat the purpose of having a tree), but when I'm looking at the children of a specific node I iterate linearly over the set of children for that node.

KermMartian
Site Admin (Posts: 64055)

13 Apr 2011 08:07:44 pm

Excellent, that makes perfect sense. Do you have any performance numbers on how it worked out, or not particularly?

elfprince13
2
OVER NINE THOUSAND! (Posts: 11872)

13 Apr 2011 08:57:02 pm

KermMartian wrote:

Excellent, that makes perfect sense. Do you have any performance numbers on how it worked out, or not particularly?

It's difficult to say. There was a bug somewhere in my code with the lower_bound() stuff, and fixing it resulted in huge improvements to the code which was calling it externally (saving ~100MB in duplicate entries) but I'm certain that I decreased the internal performance. Iterating begin() to end() is going to be heavier, O(n), than calling lower_bound(), O(log(n)), and then checking it and one entry on either side.

If I knew exactly where the bug was hiding in the old code I might revert to the older version, but I'm quite content with the current performance.

Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page

C++ Radix Tree Implementation

Reply to topic

»
» View previous topic :: View next topic

Page 1 of 1

» All times are UTC - 5 Hours

Jump to:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum