{"id":287,"date":"2020-12-15T13:30:41","date_gmt":"2020-12-15T13:30:41","guid":{"rendered":"https:\/\/michaeljohnsteiner.com\/?p=287"},"modified":"2020-12-16T03:56:05","modified_gmt":"2020-12-16T03:56:05","slug":"bighashset-cs","status":"publish","type":"post","link":"https:\/\/michaeljohnsteiner.com\/index.php\/2020\/12\/15\/bighashset-cs\/","title":{"rendered":"BigHashSet.cs"},"content":{"rendered":"\n<p>Big Hash Set based on <a href=\"https:\/\/michaeljohnsteiner.com\/index.php\/2020\/12\/14\/bigarray-cs\/\">BigArray.cs<\/a><\/p>\n\n\n\n<p>Uses two arrays, for a single array use <a href=\"https:\/\/michaeljohnsteiner.com\/index.php\/2020\/12\/16\/bighashsetsa-cs\/\">BigHashsetSa.cs<\/a><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"csharp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">using System;\nusing System.Collections;\nusing System.Collections.Generic;\nusing System.Diagnostics;\nusing System.Runtime.Serialization;\nusing System.Threading;\n[Serializable]\n[DebuggerDisplay(\"Count = {Count}\")]\n[Obsolete]\npublic class BigHashSet&lt;T> : MonitorActionFunc, IEnumerable&lt;T>, ISerializable, IDeserializationCallback\n{\n    private readonly SerializationInfo sInfo;\n    public volatile  Table             _table = new Table();\n    public BigHashSet() : this(BigArray&lt;T>.Granularity, new BigComparer&lt;T>())\n    {\n    }\n    public BigHashSet(long size) : this(size, new BigComparer&lt;T>())\n    {\n    }\n    public BigHashSet(IBigEqualityComparer&lt;T> comparer) : this(BigArray&lt;T>.Granularity, comparer)\n    {\n    }\n    public BigHashSet(long size, IBigEqualityComparer&lt;T> comparer)\n    {\n        Lock(this, () =>\n        {\n            if (size &lt; BigArray&lt;T>.Granularity)\n                size = BigArray&lt;T>.Granularity;\n            if (comparer == null)\n                comparer = new DynComparer64&lt;T>();\n            _table.Comparer                            = comparer;\n            _table.HashBuckets                         = new BigArray&lt;long>(size);\n            _table.Slots                               = new BigArray&lt;Slot>(size);\n            _table._count                              = 0;\n            _table.Position                            = -1;\n            _table.HashBuckets.OverrideAutoConcurrency = true;\n            _table.Slots.OverrideAutoConcurrency       = true;\n        });\n    }\n    public BigHashSet(IEnumerable&lt;T> collection)\n    {\n        Lock(this, () =>\n        {\n            var size = BigArray&lt;T>.Granularity;\n            _table.Comparer                            = new DynComparer64&lt;T>();\n            _table.HashBuckets                         = new BigArray&lt;long>(size);\n            _table.Slots                               = new BigArray&lt;Slot>(size);\n            _table._count                              = 0;\n            _table.Position                            = -1;\n            _table.HashBuckets.OverrideAutoConcurrency = true;\n            _table.Slots.OverrideAutoConcurrency       = true;\n            foreach (var item in collection)\n                Insert(item, true);\n        });\n    }\n    public BigHashSet(IEnumerable&lt;T> collection, IBigEqualityComparer&lt;T> comparer)\n    {\n        Lock(this, () =>\n        {\n            if (comparer == null)\n                comparer = new DynComparer64&lt;T>();\n            var size = BigArray&lt;T>.Granularity;\n            _table.Comparer                            = comparer;\n            _table.Comparer                            = new DynComparer64&lt;T>();\n            _table.HashBuckets                         = new BigArray&lt;long>(size);\n            _table.Slots                               = new BigArray&lt;Slot>(size);\n            _table._count                              = 0;\n            _table.Position                            = -1;\n            _table.HashBuckets.OverrideAutoConcurrency = true;\n            _table.Slots.OverrideAutoConcurrency       = true;\n            foreach (var item in collection)\n                Insert(item, true);\n        });\n    }\n    protected BigHashSet(SerializationInfo info, StreamingContext context)\n    {\n        sInfo = info;\n    }\n    public long Count\n    {\n        get\n        {\n            return Lock(this, () =>\n            {\n                return _table._count;\n            });\n        }\n        private set\n        {\n            Lock(this, () =>\n            {\n                _table._count = value;\n            });\n        }\n    }\n    public T this[T item]\n    {\n        get\n        {\n            return Lock(this, () =>\n            {\n                var pos = FindEntry(item);\n                if (pos == -1)\n                    throw new Exception($\"Getter: Index out of bounds {pos} must be contained within set.\");\n                return _table.Slots[pos]._value;\n            });\n        }\n        set => Insert(item, true);\n    }\n    public T this[long index]\n    {\n        get\n        {\n            return Lock(this, () =>\n            {\n                if (index > _table._count || _table._count == 0)\n                    SpinWait.SpinUntil(() => index &lt; _table._count &amp;&amp; _table._count > 0, 100);\n                if (index > _table._count)\n                    throw new Exception($\"Getter: Index out of bounds {index} must be less than {_table._count}\");\n                return _table.Slots[index]._value;\n            });\n        }\n    }\n    public void OnDeserialization(object sender)\n    {\n        Lock(this, () =>\n        {\n            if (sInfo == null)\n                return;\n            var size = sInfo.GetInt64(\"Capacity\");\n            if (size != 0)\n            {\n                Clear();\n                _table.HashBuckets = new BigArray&lt;long>(size);\n                _table.Slots       = new BigArray&lt;Slot>(size);\n                _table.Comparer    = (IBigEqualityComparer&lt;T>) sInfo.GetValue(\"Comparer\", typeof(IBigEqualityComparer&lt;T>));\n                _table._count      = sInfo.GetInt64(\"Count\");\n                _table.Position    = -1;\n                var array = (Slot[][]) sInfo.GetValue(\"Elements\", typeof(Slot[][]));\n                if (array == null)\n                    throw new SerializationException(\"Missing Elements.\");\n                var buckets = (long[][]) sInfo.GetValue(\"Buckets\", typeof(long[][]));\n                if (buckets == null)\n                    throw new SerializationException(\"Missing Buckets.\");\n                _table.Slots.FromArray(array);\n                _table.HashBuckets.FromArray(buckets);\n            }\n        });\n    }\n    IEnumerator&lt;T> IEnumerable&lt;T>.GetEnumerator()\n    {\n        return GetEnumerator();\n    }\n    IEnumerator IEnumerable.GetEnumerator()\n    {\n        return GetEnumerator();\n    }\n    public void GetObjectData(SerializationInfo info, StreamingContext context)\n    {\n        Lock(this, () =>\n        {\n            info.AddValue(\"Comparer\", _table.Comparer, typeof(IBigEqualityComparer&lt;T>));\n            info.AddValue(\"Capacity\", _table.HashBuckets.Length);\n            info.AddValue(\"Count\",    _table._count);\n            var array = _table.Slots.ToArray();\n            info.AddValue(\"Elements\", array, typeof(BigArray&lt;Slot>));\n            var buck = _table.HashBuckets.ToArray();\n            info.AddValue(\"Buckets\", buck, typeof(BigArray&lt;long>));\n        });\n    }\n    public void Clear()\n    {\n        Lock(this, () =>\n        {\n            var size = BigArray&lt;T>.Granularity;\n            _table.HashBuckets = new BigArray&lt;long>(size);\n            _table.Slots       = new BigArray&lt;Slot>(size);\n            _table._count      = 0;\n            _table.Position    = -1;\n        });\n    }\n    public bool Add(T item)\n    {\n        return Insert(item, true);\n    }\n    public void AddRange(IEnumerable&lt;T> collection)\n    {\n        Lock(this, () =>\n        {\n            foreach (var item in collection)\n                Insert(item, true);\n        });\n    }\n    public bool Contains(T item)\n    {\n        return Insert(item, false);\n    }\n    private long InternalGetHashCode(T item)\n    {\n        if (item == null)\n            return 0;\n        return _table.Comparer.GetHashCode(item) &amp; long.MaxValue;\n    }\n    internal bool Insert(T item, bool add)\n    {\n        return Lock(this, () =>\n        {\n            var hashCode = InternalGetHashCode(item);\n            if (FindEntry(item, hashCode) != -1)\n                return true;\n            _table.Position = -1;\n            if (add)\n            {\n                if (_table._count >= _table.Slots.Length)\n                {\n                    var newSize        = _table.HashBuckets.Length &lt;&lt; 1;\n                    var newHashBuckets = new BigArray&lt;long>(newSize);\n                    var newSlots       = new BigArray&lt;Slot>(newSize);\n                    for (var i = 0L; i &lt; _table._count; i++)\n                    {\n                        var pos = _table.Slots[i]._hashCode % newSize;\n                        newSlots[i]         = new Slot(_table.Slots[i]._hashCode, newHashBuckets[pos] - 1, _table.Slots[i]._value);\n                        newHashBuckets[pos] = i + 1;\n                    }\n                    _table.HashBuckets = newHashBuckets;\n                    _table.Slots       = newSlots;\n                }\n                var hashPos = hashCode % _table.HashBuckets.Length;\n                var news    = new Slot(hashCode, _table.HashBuckets[hashPos] - 1, item);\n                _table.Slots[_table._count] = news;\n                _table.HashBuckets[hashPos] = _table._count + 1;\n                _table.Position             = _table._count;\n                _table._count++;\n            }\n            return false;\n        });\n    }\n    private long FindEntry(T item, long hashCode)\n    {\n        return Lock(this, () =>\n        {\n            for (var position = _table.HashBuckets[hashCode % _table.HashBuckets.Length] - 1; position >= 0; position = _table.Slots[position]._next)\n                if (_table.Slots[position]._hashCode == hashCode &amp;&amp; Equals(_table.Slots[position]._value, item))\n                {\n                    _table.Position = position;\n                    return _table.Position;\n                }\n            return -1;\n        });\n    }\n    public T[] ToArray()\n    {\n        return Lock(this, () =>\n        {\n            var array = new T[Count];\n            for (var i = 0L; i &lt; Count; i++)\n                if (_table.Slots[i]._hashCode >= 0)\n                    array[i] = _table.Slots[i]._value;\n            return array;\n        });\n    }\n    public long FindEntry(T item)\n    {\n        return FindEntry(item, InternalGetHashCode(item));\n    }\n    public bool Remove(T item)\n    {\n        return Lock(this, () =>\n        {\n            var hashCode = _table.Comparer.GetHashCode(item) &amp; long.MaxValue;\n            for (var position = _table.HashBuckets[hashCode % _table.HashBuckets.Length] - 1; position >= 0; position = _table.Slots[position]._next)\n                if (_table.Slots[position]._hashCode == hashCode &amp;&amp; Equals(_table.Slots[position]._value, item))\n                {\n                    var hashPos = hashCode % _table.HashBuckets.Length;\n                    var news    = new Slot(0, -1, default);\n                    _table.Slots[position]      = news;\n                    _table.HashBuckets[hashPos] = -1;\n                    return true;\n                }\n            return false;\n        });\n    }\n    public IEnumerator&lt;T> GetEnumerator()\n    {\n        return Lock(this, () =>\n        {\n            return GetEnum();\n        });\n    }\n    public IEnumerator&lt;T> GetEnum()\n    {\n        for (var i = 0; i &lt; Count; i++)\n            if (_table.Slots[i]._hashCode >= 0)\n                yield return _table.Slots[i]._value;\n    }\n    public class Table\n    {\n        public            long                    _count;\n        internal          IBigEqualityComparer&lt;T> Comparer;\n        internal volatile BigArray&lt;long>          HashBuckets;\n        public            long                    Position;\n        internal volatile BigArray&lt;Slot>          Slots;\n    }\n    [Serializable]\n    internal struct Slot\n    {\n        public readonly long _hashCode;\n        public readonly long _next;\n        public readonly T    _value;\n        public Slot(long hashcode, long next, T value)\n        {\n            _hashCode = hashcode;\n            _next     = next;\n            _value    = value;\n        }\n    }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Big Hash Set based on BigArray.cs Uses two arrays, for a single array use BigHashsetSa.cs<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[140,58],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/287"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=287"}],"version-history":[{"count":4,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/287\/revisions"}],"predecessor-version":[{"id":293,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/287\/revisions\/293"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}