mcs/class/referencesource/mscorlib/system/collections/bitarray.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 /*=============================================================================
   7 **
   8 ** Class: BitArray
   9 **
  10 ** <OWNER>Microsoft</OWNER>
  11 **
  12 **
  13 ** Purpose: The BitArray class manages a compact array of bit values.
  14 **
  15 **
  16 =============================================================================*/
  17 namespace System.Collections {
  18
  19     using System;
  20     using System.Security.Permissions;
  21     using System.Diagnostics.Contracts;
  22     // A vector of bits.  Use this to store bits efficiently, without having to do bit
  23     // shifting yourself.
  24 [System.Runtime.InteropServices.ComVisible(true)]
  25     [Serializable()] public sealed class BitArray : ICollection, ICloneable {
  26         private BitArray() {
  27         }
  28
  29         /*=========================================================================
  30         ** Allocates space to hold length bit values. All of the values in the bit
  31         ** array are set to false.
  32         **
  33         ** Exceptions: ArgumentException if length < 0.
  34         =========================================================================*/
  35         public BitArray(int length)
  36             : this(length, false) {
  37         }
  38
  39         /*=========================================================================
  40         ** Allocates space to hold length bit values. All of the values in the bit
  41         ** array are set to defaultValue.
  42         **
  43         ** Exceptions: ArgumentOutOfRangeException if length < 0.
  44         =========================================================================*/
  45         public BitArray(int length, bool defaultValue) {
  46             if (length < 0) {
  47                 throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  48             }
  49             Contract.EndContractBlock();
  50
  51             m_array = new int[GetArrayLength(length, BitsPerInt32)];
  52             m_length = length;
  53
  54             int fillValue = defaultValue ? unchecked(((int)0xffffffff)) : 0;
  55             for (int i = 0; i < m_array.Length; i++) {
  56                 m_array[i] = fillValue;
  57             }
  58
  59             _version = 0;
  60         }
  61
  62         /*=========================================================================
  63         ** Allocates space to hold the bit values in bytes. bytes[0] represents
  64         ** bits 0 - 7, bytes[1] represents bits 8 - 15, etc. The LSB of each byte
  65         ** represents the lowest index value; bytes[0] & 1 represents bit 0,
  66         ** bytes[0] & 2 represents bit 1, bytes[0] & 4 represents bit 2, etc.
  67         **
  68         ** Exceptions: ArgumentException if bytes == null.
  69         =========================================================================*/
  70         public BitArray(byte[] bytes) {
  71             if (bytes == null) {
  72                 throw new ArgumentNullException("bytes");
  73             }
  74             Contract.EndContractBlock();
  75             // this value is chosen to prevent overflow when computing m_length.
  76             // m_length is of type int32 and is exposed as a property, so
  77             // type of m_length can't be changed to accommodate.
  78             if (bytes.Length > Int32.MaxValue / BitsPerByte) {
  79                 throw new ArgumentException(Environment.GetResourceString("Argument_ArrayTooLarge", BitsPerByte), "bytes");
  80             }
  81
  82             m_array = new int[GetArrayLength(bytes.Length, BytesPerInt32)];
  83             m_length = bytes.Length * BitsPerByte;
  84
  85             int i = 0;
  86             int j = 0;
  87             while (bytes.Length - j >= 4) {
  88                 m_array[i++] = (bytes[j] & 0xff) |
  89                               ((bytes[j + 1] & 0xff) << 8) |
  90                               ((bytes[j + 2] & 0xff) << 16) |
  91                               ((bytes[j + 3] & 0xff) << 24);
  92                 j += 4;
  93             }
  94
  95             Contract.Assert(bytes.Length - j >= 0, "BitArray byteLength problem");
  96             Contract.Assert(bytes.Length - j < 4, "BitArray byteLength problem #2");
  97
  98             switch (bytes.Length - j) {
  99                 case 3:
 100                     m_array[i] = ((bytes[j + 2] & 0xff) << 16);
 101                     goto case 2;
 102                     // fall through
 103                 case 2:
 104                     m_array[i] |= ((bytes[j + 1] & 0xff) << 8);
 105                     goto case 1;
 106                     // fall through
 107                 case 1:
 108                     m_array[i] |= (bytes[j] & 0xff);
 109             break;
 110             }
 111
 112             _version = 0;
 113         }
 114
 115         public BitArray(bool[] values) {
 116             if (values == null) {
 117                 throw new ArgumentNullException("values");
 118             }
 119             Contract.EndContractBlock();
 120
 121             m_array = new int[GetArrayLength(values.Length, BitsPerInt32)];
 122             m_length = values.Length;
 123
 124             for (int i = 0;i<values.Length;i++) {
 125                 if (values[i])
 126                     m_array[i/32] |= (1 << (i%32));
 127             }
 128
 129             _version = 0;
 130
 131         }
 132
 133         /*=========================================================================
 134         ** Allocates space to hold the bit values in values. values[0] represents
 135         ** bits 0 - 31, values[1] represents bits 32 - 63, etc. The LSB of each
 136         ** integer represents the lowest index value; values[0] & 1 represents bit
 137         ** 0, values[0] & 2 represents bit 1, values[0] & 4 represents bit 2, etc.
 138         **
 139         ** Exceptions: ArgumentException if values == null.
 140         =========================================================================*/
 141         public BitArray(int[] values) {
 142             if (values == null) {
 143                 throw new ArgumentNullException("values");
 144             }
 145             Contract.EndContractBlock();
 146             // this value is chosen to prevent overflow when computing m_length
 147             if (values.Length > Int32.MaxValue / BitsPerInt32) {
 148                 throw new ArgumentException(Environment.GetResourceString("Argument_ArrayTooLarge", BitsPerInt32), "values");
 149             }
 150
 151             m_array = new int[values.Length];
 152             m_length = values.Length * BitsPerInt32;
 153
 154             Array.Copy(values, m_array, values.Length);
 155
 156             _version = 0;
 157         }
 158
 159         /*=========================================================================
 160         ** Allocates a new BitArray with the same length and bit values as bits.
 161         **
 162         ** Exceptions: ArgumentException if bits == null.
 163         =========================================================================*/
 164         public BitArray(BitArray bits) {
 165             if (bits == null) {
 166                 throw new ArgumentNullException("bits");
 167             }
 168             Contract.EndContractBlock();
 169
 170             int arrayLength = GetArrayLength(bits.m_length, BitsPerInt32);
 171             m_array = new int[arrayLength];
 172             m_length = bits.m_length;
 173
 174             Array.Copy(bits.m_array, m_array, arrayLength);
 175
 176             _version = bits._version;
 177         }
 178
 179         public bool this[int index] {
 180                 get {
 181                     return Get(index);
 182                 }
 183                 set {
 184                     Set(index,value);
 185                 }
 186          }
 187
 188         /*=========================================================================
 189         ** Returns the bit value at position index.
 190         **
 191         ** Exceptions: ArgumentOutOfRangeException if index < 0 or
 192         **             index >= GetLength().
 193         =========================================================================*/
 194         public bool Get(int index) {
 195             if (index < 0 || index >= Length) {
 196                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
 197             }
 198             Contract.EndContractBlock();
 199
 200             return (m_array[index / 32] & (1 << (index % 32))) != 0;
 201         }
 202
 203         /*=========================================================================
 204         ** Sets the bit value at position index to value.
 205         **
 206         ** Exceptions: ArgumentOutOfRangeException if index < 0 or
 207         **             index >= GetLength().
 208         =========================================================================*/
 209         public void Set(int index, bool value) {
 210             if (index < 0 || index >= Length) {
 211                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
 212             }
 213             Contract.EndContractBlock();
 214
 215             if (value) {
 216                 m_array[index / 32] |= (1 << (index % 32));
 217             } else {
 218                 m_array[index / 32] &= ~(1 << (index % 32));
 219             }
 220
 221             _version++;
 222         }
 223
 224         /*=========================================================================
 225         ** Sets all the bit values to value.
 226         =========================================================================*/
 227         public void SetAll(bool value) {
 228             int fillValue = value ? unchecked(((int)0xffffffff)) : 0;
 229             int ints = GetArrayLength(m_length, BitsPerInt32);
 230             for (int i = 0; i < ints; i++) {
 231                 m_array[i] = fillValue;
 232             }
 233
 234             _version++;
 235         }
 236
 237         /*=========================================================================
 238         ** Returns a reference to the current instance ANDed with value.
 239         **
 240         ** Exceptions: ArgumentException if value == null or
 241         **             value.Length != this.Length.
 242         =========================================================================*/
 243         public BitArray And(BitArray value) {
 244             if (value==null)
 245                 throw new ArgumentNullException("value");
 246             if (Length != value.Length)
 247                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
 248             Contract.EndContractBlock();
 249
 250             int ints = GetArrayLength(m_length, BitsPerInt32);
 251             for (int i = 0; i < ints; i++) {
 252                 m_array[i] &= value.m_array[i];
 253             }
 254
 255             _version++;
 256             return this;
 257         }
 258
 259         /*=========================================================================
 260         ** Returns a reference to the current instance ORed with value.
 261         **
 262         ** Exceptions: ArgumentException if value == null or
 263         **             value.Length != this.Length.
 264         =========================================================================*/
 265         public BitArray Or(BitArray value) {
 266             if (value==null)
 267                 throw new ArgumentNullException("value");
 268             if (Length != value.Length)
 269                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
 270             Contract.EndContractBlock();
 271
 272             int ints = GetArrayLength(m_length, BitsPerInt32);
 273             for (int i = 0; i < ints; i++) {
 274                 m_array[i] |= value.m_array[i];
 275             }
 276
 277             _version++;
 278             return this;
 279         }
 280
 281         /*=========================================================================
 282         ** Returns a reference to the current instance XORed with value.
 283         **
 284         ** Exceptions: ArgumentException if value == null or
 285         **             value.Length != this.Length.
 286         =========================================================================*/
 287         public BitArray Xor(BitArray value) {
 288             if (value==null)
 289                 throw new ArgumentNullException("value");
 290             if (Length != value.Length)
 291                 throw new ArgumentException(Environment.GetResourceString("Arg_ArrayLengthsDiffer"));
 292             Contract.EndContractBlock();
 293
 294             int ints = GetArrayLength(m_length, BitsPerInt32);
 295             for (int i = 0; i < ints; i++) {
 296                 m_array[i] ^= value.m_array[i];
 297             }
 298
 299             _version++;
 300             return this;
 301         }
 302
 303         /*=========================================================================
 304         ** Inverts all the bit values. On/true bit values are converted to
 305         ** off/false. Off/false bit values are turned on/true. The current instance
 306         ** is updated and returned.
 307         =========================================================================*/
 308         public BitArray Not() {
 309             int ints = GetArrayLength(m_length, BitsPerInt32);
 310             for (int i = 0; i < ints; i++) {
 311                 m_array[i] = ~m_array[i];
 312             }
 313
 314             _version++;
 315             return this;
 316         }
 317
 318         public int Length {
 319             get {
 320                 Contract.Ensures(Contract.Result<int>() >= 0);
 321                 return m_length;
 322             }
 323             set {
 324                 if (value < 0) {
 325                     throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
 326                 }
 327                 Contract.EndContractBlock();
 328
 329                 int newints = GetArrayLength(value, BitsPerInt32);
 330                 if (newints > m_array.Length || newints + _ShrinkThreshold < m_array.Length) {
 331                     // grow or shrink (if wasting more than _ShrinkThreshold ints)
 332                     int[] newarray = new int[newints];
 333                     Array.Copy(m_array, newarray, newints > m_array.Length ? m_array.Length : newints);
 334                     m_array = newarray;
 335                 }
 336
 337                 if (value > m_length) {
 338                     // clear high bit values in the last int
 339                     int last = GetArrayLength(m_length, BitsPerInt32) - 1;
 340                     int bits = m_length % 32;
 341                     if (bits > 0) {
 342                         m_array[last] &= (1 << bits) - 1;
 343                     }
 344
 345                     // clear remaining int values
 346                     Array.Clear(m_array, last + 1, newints - last - 1);
 347                 }
 348
 349                 m_length = value;
 350                 _version++;
 351             }
 352         }
 353
 354         // ICollection implementation
 355         public void CopyTo(Array array, int index)
 356         {
 357             if (array == null)
 358                 throw new ArgumentNullException("array");
 359
 360             if (index < 0)
 361                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
 362
 363             if (array.Rank != 1)
 364                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
 365
 366             Contract.EndContractBlock();
 367
 368             if (array is int[])
 369             {
 370                 Array.Copy(m_array, 0, array, index, GetArrayLength(m_length, BitsPerInt32));
 371             }
 372             else if (array is byte[])
 373             {
 374                 int arrayLength = GetArrayLength(m_length, BitsPerByte);
 375                 if ((array.Length - index) < arrayLength)
 376                      throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
 377
 378                 byte [] b = (byte[])array;
 379                 for (int i = 0; i < arrayLength; i++)
 380                     b[index + i] = (byte)((m_array[i/4] >> ((i%4)*8)) & 0x000000FF); // Shift to bring the required byte to LSB, then mask
 381             }
 382             else if (array is bool[])
 383             {
 384                 if (array.Length - index < m_length)
 385                      throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
 386
 387                 bool [] b = (bool[])array;
 388                 for (int i = 0;i<m_length;i++)
 389                     b[index + i] = ((m_array[i/32] >> (i%32)) & 0x00000001) != 0;
 390             }
 391             else
 392                 throw new ArgumentException(Environment.GetResourceString("Arg_BitArrayTypeUnsupported"));
 393         }
 394
 395         public int Count
 396         {
 397             get
 398             {
 399                 Contract.Ensures(Contract.Result<int>() >= 0);
 400
 401                 return m_length;
 402             }
 403         }
 404
 405         public Object Clone()
 406         {
 407             Contract.Ensures(Contract.Result<Object>() != null);
 408             Contract.Ensures(((BitArray)Contract.Result<Object>()).Length == this.Length);
 409
 410             BitArray bitArray = new BitArray(m_array);
 411             bitArray._version = _version;
 412             bitArray.m_length = m_length;
 413             return bitArray;
 414         }
 415
 416         public Object SyncRoot
 417         {
 418              get
 419              {
 420                 if( _syncRoot == null) {
 421                     System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
 422                 }
 423                 return _syncRoot;
 424              }
 425         }
 426
 427         public bool IsReadOnly
 428         {
 429             get
 430             {
 431                 return false;
 432             }
 433         }
 434
 435         public bool IsSynchronized
 436         {
 437             get
 438             {
 439                 return false;
 440             }
 441         }
 442
 443         public IEnumerator GetEnumerator()
 444         {
 445             return new BitArrayEnumeratorSimple(this);
 446         }
 447
 448         // XPerY=n means that n Xs can be stored in 1 Y.
 449         private const int BitsPerInt32 = 32;
 450         private const int BytesPerInt32 = 4;
 451         private const int BitsPerByte = 8;
 452
 453         /// <summary>
 454         /// Used for conversion between different representations of bit array.
 455         /// Returns (n+(div-1))/div, rearranged to avoid arithmetic overflow.
 456         /// For example, in the bit to int case, the straightforward calc would
 457         /// be (n+31)/32, but that would cause overflow. So instead it's
 458         /// rearranged to ((n-1)/32) + 1, with special casing for 0.
 459         ///
 460         /// Usage:
 461         /// GetArrayLength(77, BitsPerInt32): returns how many ints must be
 462         /// allocated to store 77 bits.
 463         /// </summary>
 464         /// <param name="n"></param>
 465         /// <param name="div">use a conversion constant, e.g. BytesPerInt32 to get
 466         /// how many ints are required to store n bytes</param>
 467         /// <returns></returns>
 468         private static int GetArrayLength(int n, int div) {
 469             Contract.Assert(div > 0, "GetArrayLength: div arg must be greater than 0");
 470             return n > 0 ? (((n - 1) / div) + 1) : 0;
 471         }
 472
 473         [Serializable]
 474         private class BitArrayEnumeratorSimple : IEnumerator, ICloneable
 475         {
 476             private BitArray bitarray;
 477             private int index;
 478             private int version;
 479             private bool currentElement;
 480
 481             internal BitArrayEnumeratorSimple(BitArray bitarray) {
 482                 this.bitarray = bitarray;
 483                 this.index = -1;
 484                 version = bitarray._version;
 485             }
 486
 487             public Object Clone() {
 488                 return MemberwiseClone();
 489             }
 490
 491             public virtual bool MoveNext() {
 492                 if (version != bitarray._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
 493                 if (index < (bitarray.Count-1)) {
 494                     index++;
 495                     currentElement = bitarray.Get(index);
 496                     return true;
 497                 }
 498                 else
 499                     index = bitarray.Count;
 500
 501                 return false;
 502             }
 503
 504             public virtual Object Current {
 505                 get {
 506                     if (index == -1)
 507                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
 508                     if (index >= bitarray.Count)
 509                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
 510                     return currentElement;
 511                 }
 512             }
 513
 514             public void Reset() {
 515                 if (version != bitarray._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
 516                 index = -1;
 517             }
 518         }
 519
 520         private int[] m_array;
 521         private int m_length;
 522         private int _version;
 523         [NonSerialized]
 524         private Object _syncRoot;
 525
 526         private const int _ShrinkThreshold = 256;
 527     }
 528
 529 }