The Labs \ Source Viewer \ SSCLI \ System.Xml.Schema \ BitSet

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

Developer Fusion