Skip to content

Instantly share code, notes, and snippets.

@ArtemAvramenko
Created November 1, 2023 13:36
Show Gist options
  • Save ArtemAvramenko/6935a0211662c17066b41921711cbb49 to your computer and use it in GitHub Desktop.
Save ArtemAvramenko/6935a0211662c17066b41921711cbb49 to your computer and use it in GitHub Desktop.
BitArray implementation that allows to store more than 2^32 values
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