Class ScyllaTrie<TValue>

Concrete trie (prefix tree) that maps string keys to values of type TValue with O(k) insert, lookup, and removal (where k is the key length), efficient prefix existence tests, and lexicographically ordered enumeration via CopyKeysTo(Span<string>), CopyKeyValuePairsTo(Span<KeyValuePair<string, TValue>>), and CopyMatches(string, Span<string>). This is the map variant; for key-only set storage use ScyllaTrie. Unsynchronized by default; use AsSynchronized(object) to obtain a thread-safe wrapper.

Inheritance

object

ScyllaTrie<TValue>

Implements

IScyllaTrie<TValue>

IScyllaCollection

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Scylla.Core.Structures

Assembly: ScyllaCore.dll

Syntax

public sealed class ScyllaTrie<TValue> : IScyllaTrie<TValue>, IScyllaCollection

Type Parameters

Name	Description
TValue	The type of value associated with each stored key. May be any type including reference types, value types, and `null`-able types. When a key is removed, cleared, or the trie is reset, the stored value is set to `default(TValue)` to avoid holding stale object references.

Remarks

Internal storage model: identical to ScyllaTrie but each terminal Node additionally holds a TValue field. All the same node/edge free-list, capacity-growth, sorted-edge-list, and case-normalisation behaviours apply.

Add vs set: TryAdd(string, TValue) inserts a new key/value pair and fails if the key already exists. TrySet(string, TValue) updates the value of an existing key and fails if the key does not exist. Neither method is an upsert; use both in sequence when upsert semantics are required.

Thread safety: this class is not thread-safe. Call AsSynchronized(object) to obtain a ScyllaTrie<TValue>.SynchronizedScyllaTrie wrapper that locks all operations on a shared monitor.

// Direct construction
var trie = new ScyllaTrie<int>(nodeCapacity: 64, fixedCapacity: true, ignoreCase: true);
// Using fluent builder for complex configuration
var trie = ScyllaTrie<string>.CreateBuilder()
    .WithNodeCapacity(128)
    .IgnoreCase()
    .FixedCapacity()
    .Synchronized()
    .Build();

Constructors

ScyllaTrie(int, bool, bool)

Initializes a new ScyllaTrie<TValue> with the specified with the specified initial capacity, growth policy, and case-sensitivity settings.

Declaration

public ScyllaTrie(int nodeCapacity = 16, bool fixedCapacity = false, bool ignoreCase = false)

Parameters

Type	Name	Description
int	nodeCapacity	The initial number of node slots to allocate. Values less than `1` are clamped to `1`. The internal edge array is initialised to `max(32, nodeCapacity * 2)` slots because a typical trie has approximately twice as many edges as nodes. Defaults to `16`.
bool	fixedCapacity	When `true`, the trie will never grow its internal arrays beyond the initial allocation. TryAdd(string, TValue) returns `false` instead of resizing when the arrays are full. Defaults to `false` (automatic doubling growth).
bool	ignoreCase	When `true`, every character is converted to upper-case using ToUpperInvariant(char) before traversal, making all lookups and prefix searches case-insensitive. Original key casing is preserved in stored `Node.Key` strings. Defaults to `false` (case-sensitive).

Properties

Capabilities

Gets the capability flags that describe which optional operations this trie instance supports.

Declaration

public ScyllaCollectionCapabilities Capabilities { get; }

Property Value

Type	Description
ScyllaCollectionCapabilities	Always includes HasCapacity, SupportsContains, SupportsCopyTo, and SupportsKeyLookup.

Count

Gets the number of key/value pairs currently stored in the trie.

Declaration

public int Count { get; }

Property Value

Type	Description
int	A non-negative integer representing the current key count. Incremented by successful TryAdd(string, TValue) calls and decremented by successful TryRemove(string) calls.

EdgeCapacity

Gets the current total number of edge slots allocated in the internal edge array.

Declaration

public int EdgeCapacity { get; }

Property Value

Type	Description
int	The length of the internal edge array. In dynamic mode this doubles whenever exhausted. In fixed-capacity mode it never changes after construction.

IgnoreCase

Gets a value indicating whether this trie performs case-insensitive character matching using invariant-culture upper-case normalisation.

Declaration

public bool IgnoreCase { get; }

Property Value

Type	Description
bool	`true` if every character is converted via ToUpperInvariant(char) before traversal; `false` for exact (case-sensitive) character matching. Keys are always stored with their original casing regardless of this setting.

IsEmpty

Gets a value indicating whether the trie contains no keys.

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool	`true` when Count is `0`; `false` otherwise.

IsFixedCapacity

Gets a value indicating whether this trie is operating in fixed-capacity mode, where the internal node and edge arrays will never grow beyond their initial allocation.

Declaration

public bool IsFixedCapacity { get; }

Property Value

Type	Description
bool	`true` if the trie was constructed with `fixedCapacity: true`; `false` if the arrays may double in size automatically when exhausted.

NodeCapacity

Gets the current total number of node slots allocated in the internal node array.

Declaration

public int NodeCapacity { get; }

Property Value

Type	Description
int	The length of the internal node array. In dynamic mode this doubles whenever exhausted. In fixed-capacity mode it never changes after construction.

SyncRoot

Gets the synchronization root for this trie.

Declaration

public object SyncRoot { get; }

Property Value

Type	Description
object	Always `null` for the unsynchronized ScyllaTrie<TValue>. A non-null value is only returned by the ScyllaTrie<TValue>.SynchronizedScyllaTrie wrapper.

ThreadSafety

Gets the thread-safety guarantee for this trie instance.

Declaration

public ScyllaCollectionThreadSafety ThreadSafety { get; }

Property Value

Type	Description
ScyllaCollectionThreadSafety	Always Unsynchronized for this class. Use AsSynchronized(object) to obtain a wrapper that reports Synchronized.

Methods

AsSynchronized(object)

Creates and returns a thread-safe synchronized wrapper around this trie. All operations on the returned wrapper are protected by a lock, making them safe for concurrent access.

Declaration

public ScyllaTrie<TValue>.SynchronizedScyllaTrie AsSynchronized(object syncRoot = null)

Parameters

Type	Name	Description
object	syncRoot	Optional external lock object to use for synchronization. If null, the wrapper creates and owns a private lock. When provided, allows coordinating access with other synchronized operations using the same lock.

Returns

Type	Description
ScyllaTrie<TValue>.SynchronizedScyllaTrie	A thread-safe wrapper that synchronizes all operations

Clear()

Removes all keys and their associated values from the trie, resetting it to an empty state without releasing the internal node and edge arrays. All terminal key string references and value references are cleared to allow garbage collection.

Declaration

public void Clear()

Remarks

This method is a no-op if the trie is already empty and only the root node exists. Array sizes (NodeCapacity / EdgeCapacity) are unchanged.

ContainsKey(string)

Determines whether the trie contains the specified key as an exact, complete match.

Declaration

public bool ContainsKey(string key)

Parameters

Type	Name	Description
string	key	The key to search for. Must not be `null`. An empty string is a valid key and returns `true` only if an empty string was previously inserted.

Returns

Type	Description
bool	`true` if a terminal node is reached by traversing every character of `key`; `false` otherwise.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `key` is `null`.

ContainsPrefix(string)

Determines whether the trie contains at least one key whose characters begin with prefix.

Declaration

public bool ContainsPrefix(string prefix)

Parameters

Type	Name	Description
string	prefix	The prefix to test. Must not be `null`. An empty string returns `true` whenever the trie holds any key.

Returns

Type	Description
bool	`true` if the node reached by traversing `prefix` exists and is either terminal or has at least one outgoing edge; `false` otherwise.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `prefix` is `null`.

CopyKeyValuePairsTo(Span<KeyValuePair<string, TValue>>)

Copies all stored key/value pairs in ascending lexicographic order (by key) into destination, stopping when the span is full or all pairs have been written.

Declaration

public int CopyKeyValuePairsTo(Span<KeyValuePair<string, TValue>> destination)

Parameters

Type	Name	Description
Span<KeyValuePair<string, TValue>>	destination	The target span of KeyValuePair<TKey, TValue> to write into. If shorter than Count, only the first `destination.Length` pairs are written.

Returns

Type	Description
int	The number of pairs written. Returns `0` if the trie is empty or the span has length zero.

CopyKeysTo(Span<string>)

Copies all stored keys in ascending lexicographic order into destination, stopping when the span is full or all keys have been written.

Declaration

public int CopyKeysTo(Span<string> destination)

Parameters

Type	Name	Description
Span<string>	destination	The target span to write keys into. If shorter than Count, only the first `destination.Length` keys are written.

Returns

Type	Description
int	The number of keys written. Returns `0` if the trie is empty or the span has length zero.

CopyKeysTo(string[], int)

Copies all stored keys in ascending lexicographic order into destination starting at destinationIndex.

Declaration

public int CopyKeysTo(string[] destination, int destinationIndex)

Parameters

Type	Name	Description
string[]	destination	The target array to write keys into. Must not be `null`.
int	destinationIndex	The zero-based index in `destination` at which writing begins. Must be in the range `[0, destination.Length]`.

Returns

Type	Description
int	The number of keys written. Returns `0` if the trie is empty or no space is available starting at `destinationIndex`.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `destination` is `null`.
ArgumentOutOfRangeException	Thrown when `destinationIndex` is negative or greater than the array length.

CopyMatches(string, Span<KeyValuePair<string, TValue>>)

Copies all key/value pairs whose key starts with prefix in ascending lexicographic order (by key) into destinationPairs, stopping when the span is full or all matching pairs have been written. Use this overload when both the key name and associated value are needed for each autocomplete result.

Declaration

public int CopyMatches(string prefix, Span<KeyValuePair<string, TValue>> destinationPairs)

Parameters

Type	Name	Description
string	prefix	The prefix to filter by. Must not be `null`. An empty string matches all stored pairs and is equivalent to calling CopyKeyValuePairsTo(Span<KeyValuePair<string, TValue>>).
Span<KeyValuePair<string, TValue>>	destinationPairs	The target span of KeyValuePair<TKey, TValue> to write matching pairs into. If shorter than the number of matching entries, only the first `destinationPairs.Length` matches are written.

Returns

Type	Description
int	The number of pairs written. Returns `0` if no key matches the prefix, the trie is empty, or the span has length zero.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `prefix` is `null`.

CopyMatches(string, Span<string>)

Copies all keys that start with prefix in ascending lexicographic order into destinationKeys, stopping when the span is full or all matching keys have been written. Use this overload when only key names are needed for autocomplete.

Declaration

public int CopyMatches(string prefix, Span<string> destinationKeys)

Parameters

Type	Name	Description
string	prefix	The prefix to filter by. Must not be `null`. An empty string matches all stored keys and is equivalent to calling CopyKeysTo(Span<string>).
Span<string>	destinationKeys	The target span to write matching keys into. If shorter than the number of matching keys, only the first `destinationKeys.Length` matches are written.

Returns

Type	Description
int	The number of keys written. Returns `0` if no key matches the prefix, the trie is empty, or the span has length zero.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `prefix` is `null`.

CreateBuilder()

Creates a new fluent builder for configuring and constructing a ScyllaTrie instance. The builder provides a discoverable API for setting node capacity, fixed-capacity mode, case sensitivity, and synchronized wrappers.

Declaration

public static ScyllaTrie<TValue>.Builder CreateBuilder()

Returns

Type	Description
ScyllaTrie<TValue>.Builder	A new builder instance for configuring ScyllaTrie construction

Remarks

var trie = ScyllaTrie<int>.CreateBuilder()
.WithNodeCapacity(64)
.IgnoreCase()
.FixedCapacity()
.Build();

EnsureCapacity(int, int)

Ensures the internal node and edge arrays can each accommodate at least the specified number of slots without a future resize, growing them immediately if necessary.

Declaration

public void EnsureCapacity(int minNodeCapacity, int minEdgeCapacity)

Parameters

Type	Name	Description
int	minNodeCapacity	The minimum required node-array length. If the current NodeCapacity already meets or exceeds this value, no node-array growth occurs.
int	minEdgeCapacity	The minimum required edge-array length. If the current EdgeCapacity already meets or exceeds this value, no edge-array growth occurs.

Exceptions

Type	Condition
InvalidOperationException	Thrown when IsFixedCapacity is `true` and at least one of the requested capacities exceeds the current array size.

TryAdd(string, TValue)

Attempts to insert a new key/value pair into the trie. Does not modify an existing entry; use TrySet(string, TValue) to update a value in place.

Declaration

public bool TryAdd(string key, TValue value)

Parameters

Type	Name	Description
string	key	The key to add. Must not be `null`. An empty string is a valid key; it marks the root node as terminal. If IgnoreCase is active, the characters used for traversal are normalised to upper-case, but the original-casing string is stored on the terminal node.
TValue	value	The value to associate with `key`. May be any value valid for `TValue`, including `null` for reference types.

Returns

Type	Description
bool	`true` if the key/value pair was successfully inserted. `false` if the key already exists, or if IsFixedCapacity is `true` and there are insufficient free slots to complete the insertion.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `key` is `null`.

TryGetValue(string, out TValue)

Attempts to retrieve the value associated with the specified key.

Declaration

public bool TryGetValue(string key, out TValue value)

Parameters

Type	Name	Description
string	key	The key to look up. Must not be `null`. An empty string is a valid key; it succeeds only if an empty string was previously inserted.
TValue	value	When this method returns `true`, contains the value associated with `key`. When this method returns `false`, contains `default(TValue)`.

Returns

Type	Description
bool	`true` if the key was found and `value` was set; `false` otherwise.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `key` is `null`.

TryRemove(string)

Attempts to remove the specified key and its associated value from the trie and prune any internal nodes and edges that are no longer reachable by any stored key.

Declaration

public bool TryRemove(string key)

Parameters

Type	Name	Description
string	key	The key to remove. Must not be `null`. An empty string is a valid key and clears the terminal flag on the root node when present, also resetting its value to `default(TValue)`.

Returns

Type	Description
bool	`true` if the key existed and was removed; `false` if the key does not exist.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `key` is `null`.

TrySet(string, TValue)

Attempts to update the value associated with an existing key in the trie. Does not insert a new entry if the key is absent; use TryAdd(string, TValue) to add a new key.

Declaration

public bool TrySet(string key, TValue value)

Parameters

Type	Name	Description
string	key	The key whose value should be updated. Must not be `null`. An empty string is a valid key and succeeds only if an empty string was previously inserted.
TValue	value	The new value to associate with `key`. May be any value valid for `TValue`, including `null` for reference types.

Returns

Type	Description
bool	`true` if the key was found and its value was updated; `false` if the key does not exist in the trie.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `key` is `null`.

Implements

IScyllaTrie<TValue>

IScyllaCollection

Extension Methods

FileExtensions.SaveSecureToFileAsync<T>(T, string, string, CancellationToken)

FileExtensions.SaveSecureToFile<T>(T, string, string)

FileExtensions.SaveToFileAsync<T>(T, string, CancellationToken)

FileExtensions.SaveToFile<T>(T, string)

FileExtensions.SaveToFile<T>(T, string, SerializationSettings)