Created
November 1, 2023 13:36
-
-
Save ArtemAvramenko/6935a0211662c17066b41921711cbb49 to your computer and use it in GitHub Desktop.
BitArray implementation that allows to store more than 2^32 values
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class LargeBitArray | |
{ | |
private readonly int _bucketSize; | |
private readonly long _capacity; | |
public LargeBitArray(long capacity = int.MaxValue) // ~272 MB for 2^31 values | |
{ | |
if (capacity < 1 || capacity > (long)2e18) | |
{ | |
throw new ArgumentException("Capacity is out of range"); | |
} | |
_capacity = capacity; | |
const double bucketRatio = 64; // 8 bits in 1 byte, 8 pointers in 64 bytes | |
var optimalSize = Math.Min(int.MaxValue, Math.Sqrt(capacity * bucketRatio)); | |
_bucketSize = (int)optimalSize; | |
_buckets = Array.Empty<System.Collections.BitArray>(); | |
} | |
private System.Collections.BitArray?[] _buckets; | |
public bool this[long i] | |
{ | |
get | |
{ | |
if (i < 0 || i >= _capacity) | |
{ | |
throw new IndexOutOfRangeException(); | |
} | |
var bucketNo = (int)(i / _bucketSize); | |
if (bucketNo >= _buckets.Length) | |
{ | |
return false; | |
} | |
var bucket = _buckets[bucketNo]; | |
return bucket != null && bucket[(int)(i % _bucketSize)]; | |
} | |
set | |
{ | |
if (i < 0 || i > _capacity) | |
{ | |
throw new IndexOutOfRangeException(); | |
} | |
var bucketNo = (int)(i / _bucketSize); | |
if (bucketNo >= _buckets.Length) | |
{ | |
Array.Resize(ref _buckets, bucketNo + 1); | |
} | |
var bucket = _buckets[bucketNo]; | |
if (bucket == null) | |
{ | |
if (!value) | |
{ | |
return; | |
} | |
bucket = new System.Collections.BitArray(_bucketSize); | |
_buckets[bucketNo] = bucket; | |
} | |
bucket[(int)(i % _bucketSize)] = value; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment