|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using Roslyn.Utilities;
using Word = System.UInt64;
namespace Microsoft.CodeAnalysis
{
[DebuggerDisplay("{GetDebuggerDisplay(), nq}")]
internal struct BitVector : IEquatable<BitVector>
{
private const Word ZeroWord = 0;
private const int Log2BitsPerWord = 6;
public const int BitsPerWord = 1 << Log2BitsPerWord;
// Cannot expose the following two field publicly because this structure is mutable
// and might become not null/empty, unless we restrict access to it.
private static Word[] s_emptyArray => Array.Empty<Word>();
private static readonly BitVector s_nullValue = default;
private static readonly BitVector s_emptyValue = new(0, s_emptyArray, 0);
private Word _bits0;
private Word[] _bits;
private int _capacity;
private BitVector(Word bits0, Word[] bits, int capacity)
{
int requiredWords = WordsForCapacity(capacity);
Debug.Assert(requiredWords == 0 || requiredWords <= bits.Length);
_bits0 = bits0;
_bits = bits;
_capacity = capacity;
Check();
}
public bool Equals(BitVector other)
{
// Bit arrays only equal if their underlying sets are of the same size
return _capacity == other._capacity
// and have the same set of bits set
&& _bits0 == other._bits0
&& _bits.AsSpan().SequenceEqual(other._bits.AsSpan());
}
public override bool Equals(object? obj)
{
return obj is BitVector other && Equals(other);
}
public static bool operator ==(BitVector left, BitVector right)
{
return left.Equals(right);
}
public static bool operator !=(BitVector left, BitVector right)
{
return !left.Equals(right);
}
public override int GetHashCode()
{
int bitsHash = _bits0.GetHashCode();
if (_bits != null)
{
for (int i = 0; i < _bits.Length; i++)
{
bitsHash = Hash.Combine(_bits[i].GetHashCode(), bitsHash);
}
}
return Hash.Combine(_capacity, bitsHash);
}
private static int WordsForCapacity(int capacity)
{
if (capacity <= 0) return 0;
int lastIndex = (capacity - 1) >> Log2BitsPerWord;
return lastIndex;
}
public int Capacity => _capacity;
[Conditional("DEBUG_BITARRAY")]
private void Check()
{
Debug.Assert(_capacity == 0 || WordsForCapacity(_capacity) <= _bits.Length);
}
public void EnsureCapacity(int newCapacity)
{
if (newCapacity > _capacity)
{
int requiredWords = WordsForCapacity(newCapacity);
if (requiredWords > _bits.Length) Array.Resize(ref _bits, requiredWords);
_capacity = newCapacity;
Check();
}
Check();
}
public IEnumerable<Word> Words()
{
if (_capacity > 0)
{
yield return _bits0;
}
for (int i = 0, n = _bits?.Length ?? 0; i < n; i++)
{
yield return _bits![i];
}
}
public IEnumerable<int> TrueBits()
{
Check();
if (_bits0 != 0)
{
for (int bit = 0; bit < BitsPerWord; bit++)
{
Word mask = ((Word)1) << bit;
if ((_bits0 & mask) != 0)
{
if (bit >= _capacity) yield break;
yield return bit;
}
}
}
for (int i = 0; i < _bits.Length; i++)
{
Word w = _bits[i];
if (w != 0)
{
for (int b = 0; b < BitsPerWord; b++)
{
Word mask = ((Word)1) << b;
if ((w & mask) != 0)
{
int bit = ((i + 1) << Log2BitsPerWord) | b;
if (bit >= _capacity) yield break;
yield return bit;
}
}
}
}
}
public static BitVector FromWords(Word bits0, Word[] bits, int capacity)
{
return new BitVector(bits0, bits, capacity);
}
/// <summary>
/// Create BitArray with at least the specified number of bits.
/// </summary>
public static BitVector Create(int capacity)
{
int requiredWords = WordsForCapacity(capacity);
Word[] bits = (requiredWords == 0) ? s_emptyArray : new Word[requiredWords];
return new BitVector(0, bits, capacity);
}
/// <summary>
/// return a bit array with all bits set from index 0 through bitCount-1
/// </summary>
/// <param name="capacity"></param>
/// <returns></returns>
public static BitVector AllSet(int capacity)
{
if (capacity == 0)
{
return Empty;
}
int requiredWords = WordsForCapacity(capacity);
Word[] bits = (requiredWords == 0) ? s_emptyArray : new Word[requiredWords];
int lastWord = requiredWords - 1;
Word bits0 = ~ZeroWord;
for (int j = 0; j < lastWord; j++)
bits[j] = ~ZeroWord;
int numTrailingBits = capacity & ((BitsPerWord) - 1);
if (numTrailingBits > 0)
{
Debug.Assert(numTrailingBits <= BitsPerWord);
Word lastBits = ~((~ZeroWord) << numTrailingBits);
if (lastWord < 0)
{
bits0 = lastBits;
}
else
{
bits[lastWord] = lastBits;
}
}
else if (requiredWords > 0)
{
bits[lastWord] = ~ZeroWord;
}
return new BitVector(bits0, bits, capacity);
}
/// <summary>
/// Make a copy of a bit array.
/// </summary>
/// <returns></returns>
public BitVector Clone()
{
Word[] newBits;
if (_bits is null || _bits.Length == 0)
{
newBits = s_emptyArray;
}
else
{
newBits = (Word[])_bits.Clone();
}
return new BitVector(_bits0, newBits, _capacity);
}
/// <summary>
/// Invert all the bits in the vector.
/// </summary>
public void Invert()
{
_bits0 = ~_bits0;
if (!(_bits is null))
{
for (int i = 0; i < _bits.Length; i++)
{
_bits[i] = ~_bits[i];
}
}
}
/// <summary>
/// Is the given bit array null?
/// </summary>
public bool IsNull
{
get
{
return _bits == null;
}
}
public static BitVector Null => s_nullValue;
public static BitVector Empty => s_emptyValue;
/// <summary>
/// Modify this bit vector by bitwise AND-ing each element with the other bit vector.
/// For the purposes of the intersection, any bits beyond the current length will be treated as zeroes.
/// Return true if any changes were made to the bits of this bit vector.
/// </summary>
public bool IntersectWith(in BitVector other)
{
bool anyChanged = false;
int otherLength = other._bits.Length;
var thisBits = _bits;
int thisLength = thisBits.Length;
if (otherLength > thisLength)
otherLength = thisLength;
// intersect the inline portion
{
var oldV = _bits0;
var newV = oldV & other._bits0;
if (newV != oldV)
{
_bits0 = newV;
anyChanged = true;
}
}
// intersect up to their common length.
for (int i = 0; i < otherLength; i++)
{
var oldV = thisBits[i];
var newV = oldV & other._bits[i];
if (newV != oldV)
{
thisBits[i] = newV;
anyChanged = true;
}
}
// treat the other bit array as being extended with zeroes
for (int i = otherLength; i < thisLength; i++)
{
if (thisBits[i] != 0)
{
thisBits[i] = 0;
anyChanged = true;
}
}
Check();
return anyChanged;
}
/// <summary>
/// Modify this bit vector by '|'ing each element with the other bit vector.
/// </summary>
/// <returns>
/// True if any bits were set as a result of the union.
/// </returns>
public bool UnionWith(in BitVector other)
{
bool anyChanged = false;
if (other._capacity > _capacity)
EnsureCapacity(other._capacity);
Word oldbits = _bits0;
_bits0 |= other._bits0;
if (oldbits != _bits0)
anyChanged = true;
for (int i = 0; i < other._bits.Length; i++)
{
oldbits = _bits[i];
_bits[i] |= other._bits[i];
if (_bits[i] != oldbits)
anyChanged = true;
}
Check();
return anyChanged;
}
public bool this[int index]
{
get
{
if (index < 0)
throw new IndexOutOfRangeException();
if (index >= _capacity)
return false;
int i = (index >> Log2BitsPerWord) - 1;
var word = (i < 0) ? _bits0 : _bits[i];
return IsTrue(word, index);
}
set
{
if (index < 0)
throw new IndexOutOfRangeException();
if (index >= _capacity)
EnsureCapacity(index + 1);
int i = (index >> Log2BitsPerWord) - 1;
int b = index & (BitsPerWord - 1);
Word mask = ((Word)1) << b;
if (i < 0)
{
if (value)
_bits0 |= mask;
else
_bits0 &= ~mask;
}
else
{
if (value)
_bits[i] |= mask;
else
_bits[i] &= ~mask;
}
}
}
public void Clear()
{
_bits0 = 0;
if (_bits != null) Array.Clear(_bits, 0, _bits.Length);
}
public static bool IsTrue(Word word, int index)
{
int b = index & (BitsPerWord - 1);
Word mask = ((Word)1) << b;
return (word & mask) != 0;
}
public static int WordsRequired(int capacity)
{
if (capacity <= 0) return 0;
return WordsForCapacity(capacity) + 1;
}
internal string GetDebuggerDisplay()
{
var value = new char[_capacity];
for (int i = 0; i < _capacity; i++)
{
value[_capacity - i - 1] = this[i] ? '1' : '0';
}
return new string(value);
}
}
}
|