eclipse-iceoryx / eclipse-iceoryx/iceoryx

Implement a prefix tree for fast string search

Open
#859 2 comments 1 reaction 1 assignee Claimed by @MatthiasKillat View on GitHub
enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.