1  using System;
  2  using System.Threading;
  3  
  4  namespace Ryujinx.Memory.Tracking
  5  {
  6      /// <summary>
  7      /// A bitmap that can be safely modified from multiple threads.
  8      /// </summary>
  9      internal class ConcurrentBitmap
 10      {
 11          public const int IntSize = 64;
 12  
 13          public const int IntShift = 6;
 14          public const int IntMask = IntSize - 1;
 15  
 16          /// <summary>
 17          /// Masks representing the bitmap. Least significant bit first, 64-bits per mask.
 18          /// </summary>
 19          public readonly long[] Masks;
 20  
 21          /// <summary>
 22          /// Create a new multithreaded bitmap.
 23          /// </summary>
 24          /// <param name="count">The number of bits to reserve</param>
 25          /// <param name="set">Whether the bits should be initially set or not</param>
 26          public ConcurrentBitmap(int count, bool set)
 27          {
 28              Masks = new long[(count + IntMask) / IntSize];
 29  
 30              if (set)
 31              {
 32                  Array.Fill(Masks, -1L);
 33              }
 34          }
 35  
 36          /// <summary>
 37          /// Check if any bit in the bitmap is set.
 38          /// </summary>
 39          /// <returns>True if any bits are set, false otherwise</returns>
 40          public bool AnySet()
 41          {
 42              for (int i = 0; i < Masks.Length; i++)
 43              {
 44                  if (Interlocked.Read(ref Masks[i]) != 0)
 45                  {
 46                      return true;
 47                  }
 48              }
 49  
 50              return false;
 51          }
 52  
 53          /// <summary>
 54          /// Check if a bit in the bitmap is set.
 55          /// </summary>
 56          /// <param name="bit">The bit index to check</param>
 57          /// <returns>True if the bit is set, false otherwise</returns>
 58          public bool IsSet(int bit)
 59          {
 60              int wordIndex = bit >> IntShift;
 61              int wordBit = bit & IntMask;
 62  
 63              long wordMask = 1L << wordBit;
 64  
 65              return (Interlocked.Read(ref Masks[wordIndex]) & wordMask) != 0;
 66          }
 67  
 68          /// <summary>
 69          /// Check if any bit in a range of bits in the bitmap are set. (inclusive)
 70          /// </summary>
 71          /// <param name="start">The first bit index to check</param>
 72          /// <param name="end">The last bit index to check</param>
 73          /// <returns>True if a bit is set, false otherwise</returns>
 74          public bool IsSet(int start, int end)
 75          {
 76              if (start == end)
 77              {
 78                  return IsSet(start);
 79              }
 80  
 81              int startIndex = start >> IntShift;
 82              int startBit = start & IntMask;
 83              long startMask = -1L << startBit;
 84  
 85              int endIndex = end >> IntShift;
 86              int endBit = end & IntMask;
 87              long endMask = (long)(ulong.MaxValue >> (IntMask - endBit));
 88  
 89              long startValue = Interlocked.Read(ref Masks[startIndex]);
 90  
 91              if (startIndex == endIndex)
 92              {
 93                  return (startValue & startMask & endMask) != 0;
 94              }
 95  
 96              if ((startValue & startMask) != 0)
 97              {
 98                  return true;
 99              }
100  
101              for (int i = startIndex + 1; i < endIndex; i++)
102              {
103                  if (Interlocked.Read(ref Masks[i]) != 0)
104                  {
105                      return true;
106                  }
107              }
108  
109              long endValue = Interlocked.Read(ref Masks[endIndex]);
110  
111              if ((endValue & endMask) != 0)
112              {
113                  return true;
114              }
115  
116              return false;
117          }
118  
119          /// <summary>
120          /// Set a bit at a specific index to either true or false.
121          /// </summary>
122          /// <param name="bit">The bit index to set</param>
123          /// <param name="value">Whether the bit should be set or not</param>
124          public void Set(int bit, bool value)
125          {
126              int wordIndex = bit >> IntShift;
127              int wordBit = bit & IntMask;
128  
129              long wordMask = 1L << wordBit;
130  
131              if (value)
132              {
133                  Interlocked.Or(ref Masks[wordIndex], wordMask);
134              }
135              else
136              {
137                  Interlocked.And(ref Masks[wordIndex], ~wordMask);
138              }
139          }
140  
141          /// <summary>
142          /// Clear the bitmap entirely, setting all bits to 0.
143          /// </summary>
144          public void Clear()
145          {
146              for (int i = 0; i < Masks.Length; i++)
147              {
148                  Interlocked.Exchange(ref Masks[i], 0);
149              }
150          }
151      }
152  }