Task #1187
Updated by Junxiao Shi about 10 years ago
Develop the NameTree. NameTree provides a unified data structure for FIB, PIT, and Measurements. Each NameTree **Entry** contains: * a Name * zero or one `fib::Entry` * zero or more `pit::Entry` * zero or one `measurements::Entry` The **NameTree** should provide methods to: * exact match: given a Name, return the NameTree entry with that Name, or determine that such entry does not exist * longest prefix match: given a query Name, return the NameTree entry whose Name is a prefix of the query Name; the entry returned should have the longest Name among candidate entries * insert: given a Name, return the NameTree entry with that Name; insert a new entry if such entry does not exist * delete: given a Name or a NameTree entry, delete that entry if it exists * full enumerate: iterate over all NameTree entries * partial enumerate: list children: given a query Name, iterate over NameTree entries under this that have one component longer Name prefix than the query * get parent: given a NameTree entry, return a NameTree entry whose Name equals this entry's Name minus the last component; insert a new entry if such entry does not exist * get ancestor: given a NameTree entry, return an existing NameTree entry whose Name is a prefix of this entry's Name minus the last component; the entry returned should have the longest Name among candidate entries * count: return the total number of NameTree entries The design should have reasonable performance. The physical data structure of NameTree is not specified. It's up to the assignee. 