using System.Collections.Generic; using System.Diagnostics; using System.Runtime.CompilerServices; namespace Stashbox.Utils.Data { [System.Runtime.CompilerServices.NullableContext(1)] [System.Runtime.CompilerServices.Nullable(0)] [DebuggerTypeProxy(typeof(HashTreeDebugView<, >))] internal sealed class HashTree<TKey, [System.Runtime.CompilerServices.Nullable(2)] TValue> where TKey : class { [System.Runtime.CompilerServices.Nullable(0)] private class Node { public readonly int StoredHash; public readonly TKey StoredKey; public TValue StoredValue; [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 0, 0 })] public Node Left; [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 0, 0 })] public Node Right; public int Height; [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1, 1 })] public ExpandableArray<TKey, TValue> Collisions; public Node(TKey key, TValue value, int hash) { StoredValue = value; StoredKey = key; StoredHash = hash; Height = 1; } } [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 0, 0 })] private Node root; public void Add(TKey key, TValue value, bool byRef = true) { root = Add(root, key, byRef ? RuntimeHelpers.GetHashCode(key) : key.GetHashCode(), value, byRef); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [return: System.Runtime.CompilerServices.Nullable(2)] public TValue GetOrDefaultByValue(TKey key) { if (root == null) return default(TValue); Node node = root; int hashCode = key.GetHashCode(); while (node != null && node.StoredHash != hashCode) { node = ((hashCode < node.StoredHash) ? node.Left : node.Right); } if (node == null || !object.Equals(key, node.StoredKey)) { if (node?.Collisions != null) return node.Collisions.GetOrDefaultByValue(key); return default(TValue); } return node.StoredValue; } private static int CalculateHeight([System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] Node node) { if (node.Left != null && node.Right != null) return 1 + ((node.Left.Height > node.Right.Height) ? node.Left.Height : node.Right.Height); if (node.Left == null && node.Right == null) return 1; return 1 + (node.Left?.Height ?? node.Right.Height); } private static int GetBalance([System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] Node node) { if (node.Left != null && node.Right != null) return node.Left.Height - node.Right.Height; if (node.Left == null && node.Right == null) return 0; return node.Left?.Height ?? (node.Right.Height * -1); } [return: System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] private static Node RotateLeft([System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] Node node) { Node right = node.Right; Node left = right.Left; right.Left = node; node.Right = left; right.Height = CalculateHeight(right); node.Height = CalculateHeight(node); return right; } [return: System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] private static Node RotateRight([System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] Node node) { Node left = node.Left; Node right = left.Right; left.Right = node; node.Left = right; left.Height = CalculateHeight(left); node.Height = CalculateHeight(node); return left; } [return: System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] private static Node Add([System.Runtime.CompilerServices.Nullable(new byte[] { 2, 0, 0 })] Node node, TKey key, int hash, TValue value, bool byRef) { if (node == null) return new Node(key, value, hash); if (node.StoredHash == hash) { CheckCollisions(node, key, value, byRef); return node; } if (node.StoredHash > hash) node.Left = Add(node.Left, key, hash, value, byRef); else node.Right = Add(node.Right, key, hash, value, byRef); node.Height = CalculateHeight(node); int balance = GetBalance(node); if (balance < 2) { if (balance <= -2) { if (GetBalance(node.Right) == 1) { node.Right = RotateRight(node.Right); node = RotateLeft(node); } else node = RotateLeft(node); } } else if (GetBalance(node.Left) == -1) { node.Left = RotateLeft(node.Left); node = RotateRight(node); } else { node = RotateRight(node); } return node; } private static void CheckCollisions([System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 0 })] Node node, TKey key, TValue value, bool byRef) { if ((byRef && key == node.StoredKey) || (!byRef && object.Equals(key, node.StoredKey))) node.StoredValue = value; else { if (node.Collisions == null) node.Collisions = new ExpandableArray<TKey, TValue>(); node.Collisions.Add(new ReadOnlyKeyValue<TKey, TValue>(key, value)); } } public IEnumerable<TValue> Walk() { if (this.root != null) { switch (this.root.Height) { case 1: yield return this.root.StoredValue; break; case 2: if (this.root.Left != null) yield return this.root.Left.StoredValue; yield return this.root.StoredValue; if (this.root.Right != null) yield return this.root.Right.StoredValue; break; default: { Node[] nodes = new Node[this.root.Height - 2]; Node currentNode4 = this.root; int index = -1; while (true) { if (currentNode4 != null) { if (currentNode4.Height == 2) { if (currentNode4.Left != null) yield return currentNode4.Left.StoredValue; yield return currentNode4.StoredValue; if (currentNode4.Right != null) yield return currentNode4.Right.StoredValue; if (index == -1) break; Node[] array = nodes; int num = index; index = num - 1; currentNode4 = array[num]; yield return currentNode4.StoredValue; currentNode4 = currentNode4.Right; } else if (currentNode4.Height == 1) { yield return currentNode4.StoredValue; if (index == -1) break; Node[] array2 = nodes; int num = index; index = num - 1; currentNode4 = array2[num]; yield return currentNode4.StoredValue; currentNode4 = currentNode4.Right; } else { Node[] array3 = nodes; int num = index + 1; index = num; array3[num] = currentNode4; currentNode4 = currentNode4.Left; } } else { if (index == -1) break; Node[] array4 = nodes; int num = index; index = num - 1; currentNode4 = array4[num]; yield return currentNode4.StoredValue; currentNode4 = currentNode4.Right; } } break; } } } } } }