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