A Performant Flexible Tree Structure with Type-Segregated Storage
When working with hierarchical or tree-structured data, developers often face a trade-off between flexibility and performance. Traditional approaches either use:
- Concrete types for strict schemas and fast access, but limited flexibility.
- Dynamic objects for flexible, schema-less data, but with runtime overhead and boxing of value types.
AdhocTree attempts to provide the best of both worlds. It's a tree data structure that combines the flexibility of dynamic objects with the performance benefits of type-specific storage.
What Is It?
AdhocTree is a tree-like data structure designed to store arbitrary named values at each node, supporting a wide range of value types. It achieves this by:
- Storing values in separate arrays by type (e.g., one array for
int, another fordouble, etc.), avoiding boxing of value types. - Maintaining a mapping from names to (type, index) pairs, so each name points to the correct array and position.
- Supporting recursive subnodes as first-class values, enabling hierarchical data.
- Providing fast, type-safe access without runtime binding or reflection.
- Offering a compaction method to reclaim memory by removing overwritten or unused values.
Why Use AdhocTree?
1. Performance Without Boxing
In many dynamic or dictionary-based structures, value types like integers or floats are stored as object, causing boxing and heap allocations. AdhocTree stores each type in its own array, so value types remain unboxed and memory-efficient.
2. Flexible Schema
Unlike rigid concrete types, AdhocTree lets you add or overwrite named values of any supported type at runtime, without predefining classes or schemas.
3. Hierarchical Data
You can nest AdhocTree instances inside each other, building complex trees with arbitrary depth and structure.
4. Memory Management
Over time, overwriting values leaves "dead" entries in arrays. AdhocTree provides a GetShrankCopy() method to create a compacted copy, defragmenting and freeing memory.
How Does It Work?
Each node maintains:
- Multiple typed lists: one for each supported value type (
int,double,string,AdhocTree, etc.). - A dictionary mapping each name to a
(Type, index)tuple, indicating which list and position holds the value.
When you Set a value:
- If the name already exists with the same type, the value is updated in place.
- If the name exists with a different type, the old reference is nulled (to aid GC), and the new value is appended to the appropriate typed list.
- The mapping is updated accordingly.
When you Get a value:
- The mapping is used to find the correct typed list and index.
- The value is returned with no boxing or dynamic dispatch.
Example Usage
var root = new AdhocTree(); root.Set("a", 123); root.Set("b", 3.14); root.Set("c", "hello"); root.Set("d", new DateTime(2025, 7, 30));
assert(root.Get("a", out int intA)); assert(123 == intA); assert(root.Get("b", out double doubleB)); assert(3.14 == doubleB); assert("hello" == root.Get<string>("c")); assert(new DateTime(2025, 7, 30) == (DateTime?)root.Get("d"));
// Overwrite with different type. root.Set("a", 2.718); assert(root.Get("a", out double doubleA)); assert(2.718 == doubleA);
// Check subnodes. var node = root.AddNode("MyNode"); node.Set("x", 42);
assert(root.GetNode("MyNode", out var n)); assert(node == n); assert(n.Get("x", out int intX)); assert(42 == intX);
// Shrink the tree and check that the values are kept. var next = root.GetShrankCopy();
assert(next.Get("a", out doubleA)); assert(2.718 == doubleA); assert(next.Get("b", out doubleB)); assert(3.14 == doubleB); assert("hello" == next.Get<string>("c")); assert(new DateTime(2025, 7, 30) == (DateTime?)next.Get("d"));
// Check subnodes. assert(next.GetNode("MyNode", out var subnode)); assert(node != subnode); assert(n.Get("x", out intX)); assert(42 == intX);
Compacting the Tree
Over time, overwriting values leaves unused entries in the internal arrays. To reclaim memory, you can create a compacted copy:
var compacted = root.GetShrankCopy();
This returns a new AdhocTree instance containing only the currently referenced values, recursively compacting all subnodes.
When to Use AdhocTree?
- You need dynamic, schema-less hierarchical data.
- You want to avoid boxing overhead for value types.
- You want fast, type-safe access without reflection or dynamic binding.
- You want to manage memory efficiently in long-lived or frequently updated trees.
Summary
AdhocTree is a hybrid data structure that blends the flexibility of dynamic dictionaries with the performance of typed arrays. It’s ideal for scenarios where you want to store complex, hierarchical data with mixed types, but still care about runtime efficiency and memory usage.
If you’re building applications involving dynamic configurations, hierarchical metadata, or flexible data models, AdhocTree might be the perfect fit!
Class Code In Full
public class AdhocTree
{
// Arrays for each known value type.
private readonly List<sbyte>? sbytes;
private readonly List<byte>? bytes;
private readonly List<short>? shorts;
private readonly List<ushort>? ushorts;
private readonly List<int>? ints;
private readonly List<uint>? uints;
private readonly List<long>? longs;
private readonly List<ulong>? ulongs;
private readonly List<float>? floats;
private readonly List<double>? doubles;
private readonly List<decimal>? decimals;
private readonly List<bool>? bools;
private readonly List<char>? chars;
//private readonly List<nint> nints;
//private readonly List<nuint> nuints;
// Arrays for reference types.
private readonly List<string?>? strings;
private readonly List<object?>? objects;
private readonly List<AdhocTree?>? nodes;
// Mapping: name -> (type, index in corresponding array)
private readonly Dictionary<string, (Type type, int index)> names = [];
public static AdhocTree Empty { get; } = new AdhocTree(0);
public AdhocTree()
{
sbytes = [];
bytes = [];
shorts = [];
ushorts = [];
ints = [];
uints = [];
longs = [];
ulongs = [];
floats = [];
doubles = [];
decimals = [];
bools = [];
chars = [];
strings = [];
objects = [];
nodes = [];
}
private AdhocTree(int _)
{
sbytes = null;
bytes = null;
shorts = null;
ushorts = null;
ints = null;
uints = null;
longs = null;
ulongs = null;
floats = null;
doubles = null;
decimals = null;
bools = null;
chars = null;
strings = null;
objects = null;
nodes = null;
}
public void Set(string name, sbyte value) => SetValue(typeof(sbyte), sbytes, name, value);
public void Set(string name, byte value) => SetValue(typeof(byte), bytes, name, value);
public void Set(string name, short value) => SetValue(typeof(short), shorts, name, value);
public void Set(string name, ushort value) => SetValue(typeof(ushort), ushorts, name, value);
public void Set(string name, int value) => SetValue(typeof(int), ints, name, value);
public void Set(string name, uint value) => SetValue(typeof(uint), uints, name, value);
public void Set(string name, long value) => SetValue(typeof(long), longs, name, value);
public void Set(string name, ulong value) => SetValue(typeof(ulong), ulongs, name, value);
public void Set(string name, float value) => SetValue(typeof(float), floats, name, value);
public void Set(string name, double value) => SetValue(typeof(double), doubles, name, value);
public void Set(string name, decimal value) => SetValue(typeof(decimal), decimals, name, value);
public void Set(string name, bool value) => SetValue(typeof(bool), bools, name, value);
public void Set(string name, char value) => SetValue(typeof(char), chars, name, value);
public void Set(string name, string? value) => SetValue(typeof(string), strings, name, value);
public void Set(string name, object? value) => SetValue(typeof(object), objects, name, value);
public void Set(string name, AdhocTree value) => SetValue(typeof(AdhocTree), nodes, name, value);
private void SetValue<T>(Type type, List<T>? list, string name, T value)
{
// Check if the name already exists.
if (names.TryGetValue(name, out var entry))
{
// If it is already of this type, then reuse the existing entry.
if (entry.type == type)
{
list![entry.index] = value;
return;
}
// If it is a reference type, then nullify the existing value to aid garbage collection.
if (entry.type == typeof(string))
strings![entry.index] = null;
else if (entry.type == typeof(object))
objects![entry.index] = null;
else if (entry.type == typeof(AdhocTree))
nodes![entry.index] = null;
}
names[name] = (type, list!.Count);
list.Add(value);
}
public bool Get(string name, out sbyte value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(sbyte))
{
value = sbytes![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out byte value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(byte))
{
value = bytes![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out short value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(short))
{
value = shorts![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out ushort value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(ushort))
{
value = ushorts![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out int value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(int))
{
value = ints![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out uint value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(uint))
{
value = uints![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out long value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(long))
{
value = longs![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out ulong value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(ulong))
{
value = ulongs![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out float value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(float))
{
value = floats![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out double value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(double))
{
value = doubles![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out decimal value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(decimal))
{
value = decimals![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out bool value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(bool))
{
value = bools![entry.index];
return true;
}
value = default;
return false;
}
public bool Get(string name, out char value)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(char))
{
value = chars![entry.index];
return true;
}
value = default;
return false;
}
public object? Get(string name)
{
if (names.TryGetValue(name, out var entry))
{
if (entry.type == typeof(string))
return strings![entry.index];
if (entry.type == typeof(AdhocTree))
return nodes![entry.index];
return objects![entry.index];
}
return default;
}
public T? Get<T>(string name) where T : class? => (T?)Get(name);
public AdhocTree AddNode(string name)
{
var node = new AdhocTree();
Set(name, node);
return node;
}
public bool GetNode(string name, out AdhocTree node)
{
if (names.TryGetValue(name, out var entry) && entry.type == typeof(AdhocTree))
{
var n = nodes![entry.index];
if (n != null)
{
node = n;
return true;
}
}
node = Empty;
return false;
}
public AdhocTree GetShrankCopy()
{
var copy = new AdhocTree();
foreach (var kvp in names)
{
var name = kvp.Key;
var (type, index) = kvp.Value;
if (type == typeof(sbyte)) copy.Set(name, sbytes![index]);
else if (type == typeof(byte)) copy.Set(name, bytes![index]);
else if (type == typeof(short)) copy.Set(name, shorts![index]);
else if (type == typeof(ushort)) copy.Set(name, ushorts![index]);
else if (type == typeof(int)) copy.Set(name, ints![index]);
else if (type == typeof(uint)) copy.Set(name, uints![index]);
else if (type == typeof(long)) copy.Set(name, longs![index]);
else if (type == typeof(ulong)) copy.Set(name, ulongs![index]);
else if (type == typeof(float)) copy.Set(name, floats![index]);
else if (type == typeof(double)) copy.Set(name, doubles![index]);
else if (type == typeof(decimal)) copy.Set(name, decimals![index]);
else if (type == typeof(bool)) copy.Set(name, bools![index]);
else if (type == typeof(char)) copy.Set(name, chars![index]);
else if (type == typeof(string)) copy.Set(name, strings![index]);
else if (type == typeof(object)) copy.Set(name, objects![index]);
else copy.Set(name, nodes![index]!.GetShrankCopy());
}
return copy;
}
}
