The Labs \ Source Viewer \ SSCLI \ System.Xml \ BitStack

  1. //------------------------------------------------------------------------------
  2. // <copyright file="BitStack.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
  16. {
  17.     using System;
  18.     using System.Diagnostics;
  19.    
  20.    
  21.     /// <summary>
  22.     /// Manages a stack of bits. Exposes push, pop, and peek operations.
  23.     /// </summary>
  24.     internal class BitStack
  25.     {
  26.         private uint[] bitStack;
  27.         private int stackPos;
  28.         private uint curr;
  29.        
  30.         /// <summary>
  31.         /// Initialize stack.
  32.         /// </summary>
  33.         public BitStack()
  34.         {
  35.             // Set sentinel bit in 1st position. As bits are shifted onto this.curr, this sentinel
  36.             // bit shifts to the left. When it's about to overflow, this.curr will be pushed
  37.             // onto an unsigned int stack and the sentinel bit will be reset to 0x1.
  38.             this.curr = 1;
  39.         }
  40.        
  41.         /// <summary>
  42.         /// Push a 0 or 1 bit onto the stack.
  43.         /// </summary>
  44.         public void PushBit(bool bit)
  45.         {
  46.             if ((this.curr & 2147483648u) != 0) {
  47.                 // If sentinel bit has reached the last position, push this.curr
  48.                 PushCurr();
  49.             }
  50.            
  51.             // Shift new bit onto this.curr (which must have at least one open position)
  52.             this.curr = (this.curr << 1) | (bit ? 1u : 0u);
  53.         }
  54.        
  55.         /// <summary>
  56.         /// Pop the top bit from the stack and return it.
  57.         /// </summary>
  58.         public bool PopBit()
  59.         {
  60.             bool bit;
  61.             Debug.Assert(this.curr != 1, "Stack empty");
  62.            
  63.             // Shift rightmost bit from this.curr
  64.             bit = (this.curr & 1) != 0;
  65.            
  66.             this.curr >>= 1;
  67.            
  68.             if (this.curr == 1) {
  69.                 // If sentinel bit has reached the rightmost position, pop this.curr
  70.                 PopCurr();
  71.             }
  72.            
  73.             return bit;
  74.         }
  75.        
  76.         /// <summary>
  77.         /// Return the top bit on the stack without pushing or popping.
  78.         /// </summary>
  79.         public bool PeekBit()
  80.         {
  81.             Debug.Assert(this.curr != 1, "Stack empty");
  82.             return (this.curr & 1) != 0;
  83.         }
  84.        
  85.         /// <summary>
  86.         /// Return true if there are currently no bits on the stack.
  87.         /// </summary>
  88.         public bool IsEmpty {
  89.             get { return this.curr == 1; }
  90.         }
  91.        
  92.         /// <summary>
  93.         /// this.curr has enough space for 31 bits (minus 1 for sentinel bit). Once this space is
  94.         /// exhausted, a uint stack is created to handle the overflow.
  95.         /// </summary>
  96.         private void PushCurr()
  97.         {
  98.             int len;
  99.            
  100.             if (this.bitStack == null) {
  101.                 this.bitStack = new uint[16];
  102.             }
  103.            
  104.             // Push current unsigned int (which has been filled) onto a stack
  105.             // and initialize this.curr to be used for future pushes.
  106.             this.bitStack[this.stackPos++] = this.curr;
  107.             this.curr = 1;
  108.            
  109.             // Resize stack if necessary
  110.             len = this.bitStack.Length;
  111.             if (this.stackPos >= len) {
  112.                 uint[] bitStackNew = new uint[2 * len];
  113.                 Array.Copy(this.bitStack, bitStackNew, len);
  114.                 this.bitStack = bitStackNew;
  115.             }
  116.         }
  117.        
  118.         /// <summary>
  119.         /// If all bits have been popped from this.curr, then pop the previous uint value from the stack in
  120.         /// order to provide another 31 bits.
  121.         /// </summary>
  122.         private void PopCurr()
  123.         {
  124.             if (this.stackPos > 0)
  125.                 this.curr = this.bitStack[--this.stackPos];
  126.         }
  127.     }
  128. }

Developer Fusion