using System.Runtime.CompilerServices; namespace Stashbox.Utils.Data { internal sealed class HashTree<TKey, TValue> { private class Node { public readonly int storedHash; public readonly TKey storedKey; public TValue storedValue; public Node left; public Node right; public int height; public ExpandableArray<TKey, TValue> collisions; public Node(TKey key, TValue value, int hash) { storedValue = value; storedKey = key; storedHash = hash; height = 1; } } 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)] 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(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(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); } private static Node RotateLeft(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; } private static Node RotateRight(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; } private static Node Add(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 (GetBalance(node.left) == -1) { node.left = RotateLeft(node.left); node = RotateRight(node); } else node = RotateRight(node); } if (balance <= -2) { if (GetBalance(node.right) == 1) { node.right = RotateRight(node.right); node = RotateLeft(node); } else node = RotateLeft(node); } return node; } private static void CheckCollisions(Node node, TKey key, TValue value, bool byRef) { if ((byRef && (object)key == (object)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 KeyValue<TKey, TValue>(key, value)); } } } }