eclipse-iceoryx / eclipse-iceoryx/iceoryx
Implement a prefix tree for fast string search
- Dominant language
- C++
- Stars
- 2.2k
- Forks
- 492
- Avg merge
- 18h 57m
- Merged PRs (30d)
- 1
Description
## Brief feature description
Prefix Tree (Trie)
Allows fast searching of strings, to be used in Service Registry (but can generally used everywhere where data is indexed by strings).
String search is then performed in time proportional to the string to be searched.
## General Constraints
- relocatable - we want to use it in shared memory
- not thread safe - too much effort / runtime cost
- keys are always strings
- values are generic
- multiple values for a key (hence it is not really a unique key, but the user is free to ensure keys are unique)
- self contained memory, static memory
## Operations
1. Insert key, value O(#key + #values to key)
2. Find all values to a key O(#key + #values to key)
3. Remove all values to a key O(#key + #values removed)
4. Remove a specific value to a key O(#key + #values to key)
- \# denotes the size of the specific quantity, i.e. \#key the length of the key and \#values to key the number of values corresponding to a key (some abuse of notation for simplicity)
- generally the effort is proportional to the length of the key plus the size of the result set (which is theoretically optimal)
- this is a substantial improvement compared to (multi)maps with O(log(#elements in map)) where each key comparison is also a string comparison of cost O(#key)
## Detailed information
- string type for API? - probably template parameterized `cxx::string`, internally we should use `char*` for efficiency
- uses tree tree structure internally for fast search
- tree nodes must be available to support insert operations up to specified capacity (this leads to wasted memory but is inevitable for static memory setup)
- tree nodes must be as compact as possible to reduce memory overhead
Contributor guide
Assessment
This issue has not been assessed yet.