Iox #859 implement prefix tree

[MatthiasKillat]

Pre-Review Checklist for the PR Author

1. [x] Code follows the coding style of CONTRIBUTING.md
2. [x] Tests follow the best practice for testing
3. [x] Changelog updated in the unreleased section including API breaking changes
4. [x] Branch follows the naming format (iox-#123-this-is-a-branch)
5. [x] Commits messages are according to this guideline
   • [x] Commit messages have the issue ID (iox-#123 commit text)
   • [x] Commit messages are signed (git commit -s)
   • [x] Commit author matches Eclipse Contributor Agreement (and ECA is signed)
6. [x] Update the PR title
   • Follow the same conventions as for commit messages
   • Link to the relevant issue
7. [x] Relevant issues are linked
8. [x] Add sensible notes for the reviewer
9. [ ] All checks have passed (except task-list-completed)
10. [x] Assign PR to reviewer

Notes for Reviewer

Checklist for the PR Reviewer

• [ ] Commits are properly organized and messages are according to the guideline
• [ ] Code according to our coding style and naming conventions
• [ ] Unit tests have been written for new behavior
  • [ ] Each unit test case has a unique UUID
• [ ] Public API changes are documented via doxygen
• [ ] Copyright owner are updated in the changed files
• [ ] PR title describes the changes

Post-review Checklist for the PR Author

1. [ ] All open points are addressed and tracked via issues

Review notes

1. introduced a TypedAllocator as a building block for the prefix tree (but is more generally useful), should be reviewed first
2. introduced a PrefixTree, how it works may require some more explanation but I am hesitant to create a design document since it is a known data structure (with additional complications due to our static memory restrictions)
3. objects of both classes are relocatable and I am working on writing a general recipe (*.md) to obtain those kind of structures in a formulaic way, this is not included here

References

• Closes #859

[MatthiasKillat]

@elBoberido Yes, I will create a design document. It shall contain the requirements and high level ideas but I will avoid code there. I usually distinguish between abstract/high-level design for the ideas and concepts and detailed design for e.g. interfaces and implementation details (should be used sparingly since they are subject to change).

I will create a high-level design document.

Note that I am first and foremost interested in whether we can live with the public interface for now. The functionality will not change much I think, but the interface is up to discussion (to a degree, we will not get the "perfect" now).

[elBoberido]

@MatthiasKillat what would be extremely helpful is a class diagram and a diagram similar to what you had in your C++ talk, showing the interaction of the Nodes and how a simple lookup will be performed. This would make it much easier to build a mental model for the code to review

[MatthiasKillat]

@elBoberido Class diagram makes sense. Not sure what kind of diagram you had in mind for he lookup. Since it relies on proper positioning it may be hard to generate with PlantUML. Sketching it in ascii will work of course. I am on it, please stop reviewing until then.

[elBoberido]

@MatthiasKillat I meant sketching in ascii. Using PlantUML for this would be horrible

[MatthiasKillat]

@elBoberido added a design document which hopefully explains the intended behavior, use case and design decisions and helps building the mental model needed to understand the underlying algorithms.

I avoided code there and have no class diagram yet. Class interfaces and interaction are of little concern here, the node structure is. Diagrams can be added though, if needed. Boils down to the interfaces and some "has_a" relations though, do we want that?

[elBoberido]

@MatthiasKillat I'm not sure if we need a simple class diagram. Maybe it is necessary for certification.

[elBoberido]

@MatthiasKillat you once mentioned you wanted to split this up into multiple PR with preparation work being merged first. Is this still your plan or are you waiting for review?

[MatthiasKillat]

@elBoberido Yes, I want to split at least the memory allocator part as I would like to have it as a clean abstraction for the future (could also be used in posh, maybe). I need to think how to continue with the tree, there is no immediate need. Ideally we would have some of thse data structures for shared memory usage and I would also like to benchmark them. But this has lower priority.

[MatthiasKillat]

@elBoberido I still have the plan to move the allocator from this PR to another PR and then probably close this one. However, I had no time yet due to other priorities. It is also not urgent.

We can close this one regardless. Still, I consider part of the work important for future data types (just not now with current priorities).

[MatthiasKillat]

Currently it is not needed, has diverged considerably and is relatively complex to review. The basic ideas will be revisited for strategies to create tree structures for iceoryx and as shared memory types.

The data structure could be useful for string indexing internally, and more specifically in a service discovery refactoring.