A Radix Tree implementation. More...

#include "llvm/ADT/RadixTree.h"

Inheritance diagram for llvm::RadixTree< KeyType, T >:

Public Types
using	key_type = KeyType
using	mapped_type = T
using	value_type = std::pair<const KeyType, mapped_type>
using	prefix_iterator = IteratorImpl<value_type>
using	const_prefix_iterator = IteratorImpl<const value_type>
using	iterator = typename ContainerType::iterator
using	const_iterator = typename ContainerType::const_iterator

Public Member Functions
	RadixTree ()=default
	RadixTree (RadixTree &&)=default
RadixTree &	operator= (RadixTree &&)=default
bool	empty () const
	Returns true if the tree is empty.
size_t	size () const
	Returns the number of elements in the tree.
size_t	countNodes () const
	Returns the number of nodes in the tree.
iterator	begin ()
	Returns an iterator to the first element.
const_iterator	begin () const
iterator	end ()
	Returns an iterator to the end of the tree.
const_iterator	end () const
template<typename... Ts>
std::pair< iterator, bool >	emplace (key_type &&Key, Ts &&...Args)
	Constructs and inserts a new element into the tree.
iterator_range< const_prefix_iterator >	find_prefixes (const key_type &Key) const
	Finds all elements whose keys are prefixes of the given Key.

Detailed Description

template<typename KeyType, typename T>
class llvm::RadixTree< KeyType, T >

A Radix Tree implementation.

A Radix Tree (also known as a compact prefix tree or radix trie) is a data structure that stores a dynamic set or associative array where keys are strings and values are associated with these keys. Unlike a regular trie, the edges of a radix tree can be labeled with sequences of characters as well as single characters. This makes radix trees more efficient for storing sparse data sets, where many nodes in a regular trie would have only one child.

This implementation supports arbitrary key types that can be iterated over (e.g., std::string, std::vector<char>, ArrayRef<char>). The key type must provide begin() and end() for iteration.

The tree stores std::pair<const KeyType, T> as its value type.

Example usage:

llvm::RadixTree<StringRef, int> Tree;
Tree.emplace("apple", 1);
Tree.emplace("grapefruit", 2);
Tree.emplace("grape", 3);
 
// Find prefixes
for (const auto &[Key, Value] : Tree.find_prefixes("grapefruit juice")) {
  // pair will be {"grape", 3}
  // pair will be {"grapefruit", 2}
  llvm::outs() << Key << ": " << Value << "\n";
}
 
// Iterate over all elements
for (const auto &[Key, Value] : Tree)
  llvm::outs() << Key << ": " << Value << "\n";

Note: The RadixTree takes ownership of the KeyType and T objects inserted into it. When an element is removed or the tree is destroyed, these objects will be destructed. However, if KeyType is a reference-like type, e.g., StringRef or range, the user must guarantee that the referenced data has a lifetime longer than the tree.

Definition at line 71 of file RadixTree.h.

Member Typedef Documentation

◆ const_iterator

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::const_iterator = typename ContainerType::const_iterator

Definition at line 275 of file RadixTree.h.

◆ const_prefix_iterator

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::const_prefix_iterator = IteratorImpl<const value_type>

Definition at line 272 of file RadixTree.h.

◆ iterator

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::iterator = typename ContainerType::iterator

Definition at line 274 of file RadixTree.h.

◆ key_type

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::key_type = KeyType

Definition at line 73 of file RadixTree.h.

◆ mapped_type

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::mapped_type = T

Definition at line 74 of file RadixTree.h.

◆ prefix_iterator

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::prefix_iterator = IteratorImpl<value_type>

Definition at line 271 of file RadixTree.h.

◆ value_type

template<typename KeyType, typename T>

using llvm::RadixTree< KeyType, T >::value_type = std::pair<const KeyType, mapped_type>

Definition at line 75 of file RadixTree.h.

Constructor & Destructor Documentation

◆ RadixTree() [1/2]

template<typename KeyType, typename T>

llvm::RadixTree< KeyType, T >::RadixTree ( )

default

Referenced by operator=(), and RadixTree().

◆ RadixTree() [2/2]

template<typename KeyType, typename T>

llvm::RadixTree< KeyType, T >::RadixTree ( RadixTree< KeyType, T > && )

default

References RadixTree().

Member Function Documentation

◆ begin() [1/2]

template<typename KeyType, typename T>

iterator llvm::RadixTree< KeyType, T >::begin ( )

inline

Returns an iterator to the first element.

Definition at line 290 of file RadixTree.h.

◆ begin() [2/2]

template<typename KeyType, typename T>

const_iterator llvm::RadixTree< KeyType, T >::begin ( ) const

inline

Definition at line 291 of file RadixTree.h.

◆ countNodes()

template<typename KeyType, typename T>

size_t llvm::RadixTree< KeyType, T >::countNodes ( ) const

inline

Returns the number of nodes in the tree.

This function counts all internal nodes in the tree. It can be useful for understanding the memory footprint or complexity of the tree structure.

Definition at line 287 of file RadixTree.h.

◆ emplace()

template<typename KeyType, typename T>

template<typename... Ts>

std::pair< iterator, bool > llvm::RadixTree< KeyType, T >::emplace	(	key_type &&	Key,
		Ts &&...	Args )

inline

Constructs and inserts a new element into the tree.

This function constructs an element in place within the tree. If an element with the same key already exists, the insertion fails and the function returns an iterator to the existing element along with false. Otherwise, the new element is inserted and the function returns an iterator to the new element along with true.

Parameters

Key	The key of the element to construct.
Args	Arguments to forward to the constructor of the mapped_type.

Returns: A pair consisting of an iterator to the inserted element (or to the element that prevented insertion) and a boolean value indicating whether the insertion took place.

Definition at line 311 of file RadixTree.h.

References llvm::HasValue(), llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key, and T.

◆ empty()

template<typename KeyType, typename T>

bool llvm::RadixTree< KeyType, T >::empty ( ) const

inline

Returns true if the tree is empty.

Definition at line 278 of file RadixTree.h.

◆ end() [1/2]

template<typename KeyType, typename T>

iterator llvm::RadixTree< KeyType, T >::end ( )

inline

Returns an iterator to the end of the tree.

Definition at line 294 of file RadixTree.h.

◆ end() [2/2]

template<typename KeyType, typename T>

const_iterator llvm::RadixTree< KeyType, T >::end ( ) const

inline

Definition at line 295 of file RadixTree.h.

◆ find_prefixes()

template<typename KeyType, typename T>

iterator_range< const_prefix_iterator > llvm::RadixTree< KeyType, T >::find_prefixes ( const key_type & Key ) const

inline

Finds all elements whose keys are prefixes of the given Key.

This function returns an iterator range over all elements in the tree whose keys are prefixes of the provided Key. For example, if the tree contains "abcde", "abc", "abcdefgh", and Key is "abcde", this function would return iterators to "abcde" and "abc".

Parameters

Key	The key to search for prefixes of.

Returns: An iterator_range of const_prefix_iterators, allowing iteration over the found prefix elements.

Note: The returned iterators reference the Key provided by the caller. The caller must ensure that Key remains valid for the lifetime of the iterators.

Definition at line 342 of file RadixTree.h.

References llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key.

◆ operator=()

template<typename KeyType, typename T>

RadixTree & llvm::RadixTree< KeyType, T >::operator= ( RadixTree< KeyType, T > && )

default

References RadixTree().

◆ size()

template<typename KeyType, typename T>

size_t llvm::RadixTree< KeyType, T >::size ( ) const

inline

Returns the number of elements in the tree.

Definition at line 281 of file RadixTree.h.

The documentation for this class was generated from the following file:

include/llvm/ADT/RadixTree.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_prefix_iterator

◆ iterator

◆ key_type

◆ mapped_type

◆ prefix_iterator

◆ value_type

Constructor & Destructor Documentation

◆ RadixTree() [1/2]

◆ RadixTree() [2/2]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ countNodes()

◆ emplace()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ find_prefixes()

◆ operator=()

◆ size()