NFD

20140214 conference call discussed four physical structures:

• Name Prefix hash table (used in ccnd)
• byte-based Patricia trie
• NameComponent-based trie (used in ndnSIM)
• binary Patricia trie

Name Prefix hash table demo code contains a hand-written hashtable, and an equivalent of ccnd nameprefix_seek function.

I identify the following problems with this demo code:

• The data structure is mixing hashtable node and entry. NamePrefixEntry::m_next is used to resolve hash collision; such field should not be mixed with the business logic (pointers to FIB/PIT/Measurements entries).
  A mature hashtable library such as boost::unordered_map could be used.
  If a hand-written hashtable is desired, those fields should be placed into private: section (and make NameTree a friend), so that they are not visible from outside.
• Longest prefix match, full/partial enumerate methods are missing.
• The hash key should be TLV-encoded Name, not URI.

When code is committed to the main repository, it need also follow CodeStyle, avoid using namespace, be placed into namespace nfd, and has unit testing.

Updated code at github repo

• lpm, full/partial enumeration functions added
• converted from std::string to Name
• todo: try hash table from boost

I would suggest you to submit code into NFD gerrit (you already have permission to submit patchsets: git push gerrit HEAD:refs/for/master). If you want, you can have your own branch to which you submit code and after it is done we will merge to master (or you can directly submit to be merged into master).

Got it. I will push the code to gerrit when the unit testing code is done.

Alex Afanasyev wrote:

I would suggest you to submit code into NFD gerrit (you already have permission to submit patchsets: git push gerrit HEAD:refs/for/master). If you want, you can have your own branch to which you submit code and after it is done we will merge to master (or you can directly submit to be merged into master).

Return type for full/partial enumerate is conceptually an iterable.

The exact C++ interface and type needs to be co-designed with FIB and management.

It's also okay to use Visitor pattern.

Suppose NameTree has entries /A and /A/B/C, getParent(/A/B/C) inserts /A/B and returns it, getAncestor(/A/B/C) returns /A.

If all intermediate levels are guaranteed to exist, there's no difference between these two operations.

It's best to clone the repository from Gerrit, although you can also push from a repository cloned from GitHub.

Before you push a patchset, please make sure code conforms to CodeStyle, unit tests are included and working.

My current plan is to store all the Name Entries in a C++ std::vector, and the return value would be the pointer to that vector. And currently, all the Name Tree Entry will be inserted to the vector (no matter whether it contains only a FIB, only a PIT, or both). What do you think?

• We might find that it is better to have fullEnumerateFIB() or fullEnumeratePIT() be helpful in the future, and we should be able to add them if needed.

Currenlty, seek() function has to be called before any lookup, which guarantees all the intermedia nodes are in the Name Tree. So there is no difference between getParent() and getAncestor(). And currently, getAncestor() is not implemented.

OK, I will clone the repository from Gerrit. I have tried to follow the code style, and I will review the code again before push it. But I guess there will probably be places that need to be revised or improved. Hope the feedback or codereview process could help on that. : )