mcs/class/referencesource/System.Xml/System/Xml/Schema/BitSet.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="BitSet.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 //------------------------------------------------------------------------------
   7
   8 namespace System.Xml.Schema {
   9
  10     using System.Text;
  11     using System.Diagnostics;
  12
  13     internal sealed class BitSet {
  14         private const int bitSlotShift = 5;
  15         private const int bitSlotMask = (1 << bitSlotShift) - 1;
  16
  17         private int      count;
  18         private uint[]    bits;
  19
  20         private BitSet() {
  21         }
  22
  23         public BitSet(int count) {
  24             this.count = count;
  25             bits = new uint[Subscript(count + bitSlotMask)];
  26         }
  27
  28         public int Count {
  29             get { return count; }
  30         }
  31
  32         public bool this[int index] {
  33             get {
  34                 return Get(index);
  35             }
  36          }
  37
  38         public void Clear() {
  39             int bitsLength = bits.Length;
  40             for (int i = bitsLength; i-- > 0 ;) {
  41                 bits[i] = 0;
  42             }
  43         }
  44
  45         public void Clear(int index) {
  46             int nBitSlot = Subscript(index);
  47             EnsureLength(nBitSlot + 1);
  48             bits[nBitSlot] &= ~((uint)1 << (index & bitSlotMask));
  49         }
  50
  51         public void Set(int index) {
  52             int nBitSlot = Subscript(index);
  53             EnsureLength(nBitSlot + 1);
  54             bits[nBitSlot] |= (uint)1 << (index & bitSlotMask);
  55         }
  56
  57
  58         public bool Get(int index) {
  59             bool fResult = false;
  60             if (index < count) {
  61                 int nBitSlot = Subscript(index);
  62                 fResult = ((bits[nBitSlot] & (1 << (index & bitSlotMask))) != 0);
  63             }
  64             return fResult;
  65         }
  66
  67         public int NextSet(int startFrom) {
  68             Debug.Assert(startFrom >= -1 && startFrom <= count);
  69             int offset = startFrom + 1;
  70             if (offset == count) {
  71                 return -1;
  72             }
  73             int nBitSlot = Subscript(offset);
  74             offset &= bitSlotMask;
  75             uint word = bits[nBitSlot] >> offset;
  76             // locate non-empty slot
  77             while (word == 0) {
  78                 if ((++ nBitSlot) == bits.Length ) {
  79                     return -1;
  80                 }
  81                 offset = 0;
  82                 word = bits[nBitSlot];
  83             }
  84             while ((word & (uint)1) == 0) {
  85                 word >>= 1;
  86                 offset ++;
  87             }
  88             return (nBitSlot << bitSlotShift) + offset;
  89         }
  90
  91         public void And(BitSet other) {
  92             /*
  93              * Need to synchronize  both this and other->
  94              * This might lead to deadlock if one thread grabs them in one order
  95              * while another thread grabs them the other order.
  96              * Use a trick from Doug Lea's book on concurrency,
  97              * somewhat complicated because BitSet overrides hashCode().
  98              */
  99             if (this == other) {
 100                 return;
 101             }
 102             int bitsLength = bits.Length;
 103             int setLength = other.bits.Length;
 104             int n = (bitsLength > setLength) ? setLength : bitsLength;
 105             for (int i = n ; i-- > 0 ;) {
 106                 bits[i] &= other.bits[i];
 107             }
 108             for (; n < bitsLength ; n++) {
 109                 bits[n] = 0;
 110             }
 111         }
 112
 113
 114         public void Or(BitSet other) {
 115             if (this == other) {
 116                 return;
 117             }
 118             int setLength = other.bits.Length;
 119             EnsureLength(setLength);
 120             for (int i = setLength; i-- > 0 ;) {
 121                 bits[i] |= other.bits[i];
 122             }
 123         }
 124
 125         public override int GetHashCode() {
 126             int h = 1234;
 127             for (int i = bits.Length; --i >= 0;) {
 128                 h ^= (int)bits[i] * (i + 1);
 129             }
 130             return(int)((h >> 32) ^ h);
 131         }
 132
 133
 134         public override bool Equals(object obj) {
 135             // assume the same type
 136             if (obj != null) {
 137                 if (this == obj) {
 138                     return true;
 139                 }
 140                 BitSet other = (BitSet) obj;
 141
 142                 int bitsLength = bits.Length;
 143                 int setLength = other.bits.Length;
 144                 int n = (bitsLength > setLength) ? setLength : bitsLength;
 145                 for (int i = n ; i-- > 0 ;) {
 146                     if (bits[i] != other.bits[i]) {
 147                         return false;
 148                     }
 149                 }
 150                 if (bitsLength > n) {
 151                     for (int i = bitsLength ; i-- > n ;) {
 152                         if (bits[i] != 0) {
 153                             return false;
 154                         }
 155                     }
 156                 }
 157                 else {
 158                     for (int i = setLength ; i-- > n ;) {
 159                         if (other.bits[i] != 0) {
 160                             return false;
 161                         }
 162                     }
 163                 }
 164                 return true;
 165             }
 166             return false;
 167         }
 168
 169         public BitSet Clone() {
 170             BitSet newset = new BitSet();
 171             newset.count = count;
 172             newset.bits = (uint[])bits.Clone();
 173             return newset;
 174         }
 175
 176
 177         public bool IsEmpty {
 178             get {
 179                 uint k = 0;
 180                 for (int i = 0; i < bits.Length; i++) {
 181                     k |= bits[i];
 182                 }
 183                 return k == 0;
 184             }
 185         }
 186
 187         public bool Intersects(BitSet other) {
 188             int i = Math.Min(this.bits.Length, other.bits.Length);
 189             while (--i >= 0) {
 190                 if ((this.bits[i] & other.bits[i]) != 0) {
 191                     return true;
 192                 }
 193             }
 194             return false;
 195         }
 196
 197         private int Subscript(int bitIndex) {
 198             return bitIndex >> bitSlotShift;
 199         }
 200
 201         private void EnsureLength(int nRequiredLength) {
 202             /* Doesn't need to be synchronized because it's an internal method. */
 203             if (nRequiredLength > bits.Length) {
 204                 /* Ask for larger of doubled size or required size */
 205                 int request = 2 * bits.Length;
 206                 if (request < nRequiredLength)
 207                     request = nRequiredLength;
 208                 uint[] newBits = new uint[request];
 209                 Array.Copy(bits, newBits, bits.Length);
 210                 bits = newBits;
 211             }
 212         }
 213
 214 #if DEBUG
 215         public void Dump(StringBuilder bb) {
 216             for (int i = 0; i < count; i ++) {
 217                 bb.Append( Get(i) ? "1" : "0");
 218             }
 219         }
 220 #endif
 221     };
 222
 223 }
 224