Sunday, August 15, 2010
全国哀悼日
Thursday, July 15, 2010
Windbg学习笔记之一:构建环境
Windbg是Windows平台上功能极度全面的Debug工具,此乃居家旅行,杀人越货之必备产品。
在学习如何使用Windbg之前,首先要有个实验的环境,但是安装Windbg,并且使Windbg正常工作不是件容易事。通过这几天的研究,我将列举出安装Windbg和使用Windbg初期常见的问题。
问题一:哪里下载?
回答: https://www.microsoft.com/whdc/DevTools/Debugging/default.mspx上面的链接通常是一个web installer,但是也提供了ISO下载。这套工具中包括了kd,ntsd, cdb,和万能的Windbg,当然也包含了很多其他常见的工具。
问题二:装完之后怎么用?
回答:Windbg自然是用来Debug的,但是它也可以用来观察系统是如何运作的。要让Windbg正常的工作起来,还是有一定难度的,首先要做的一件事情就是把symbol path设定好。
什么是symbol path?编译原理中提到的符号表就是编译器用来找符号对应地址时候用的,同时在debug的时候,符号也能够用来帮助我们定位变量和函数的具体位置。如今的软件动辄几个GB,为了不增加最终用户磁盘空间的压力,所以把符号表和其他相关的信息存储到了另一个文件上(通常是dbg或pdb文件)。这样就确保最终编译出来的文件又小又快。
Windbg有很多中设定symbol path的方法,这里只需要介绍两种。
方法一:_NT_SYMBOL_PATH
把_NT_SYMBOL_PATH添加到环境变量中去,如_NT_SYMBOL_PATH=SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols
其中d:\symbols\7600是缓存,而http://msdl.microsoft.com/download/symbols是符号的下载地址。这里需要注意的是一定要使用管理员权限去打开debugger,否则无法读出环境变量。
方法二:.sympath
在任意个一个debugger中的命令行中键入:.sympath SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols 也能达到同样的效果。
直接通过下载符号可以保证符号是正确的,但是这也造成了不小的负担,所以可以先下载已有的符号当缓存用:http://www.microsoft.com/whdc/devtools/debugging/symbolpkg.mspx但是这个缓存通常不是最新的,这也就是设定网络路径的好处了。
通过使用命令:!sym noisy可以使debugger把查询符号的位置和是否匹配的结果列出来。这样可以马上知道什么原因无法找到符号。比如ntdll.dll时常更新,7600里面的版本号和新的ntdll不匹配会导致无法找到符号。
Monday, June 21, 2010
写给自己看之三:AVL树的插入
AVL树(平衡树)的定义:
如何才能做到这点呢?
我读的教材所采用的方法是多设一个节点信息叫BF(Balance Factor)作为枚举类型。三个值分别为:LH(Left High),EH(Equal High)和RH(Right High)并采用递归插入。说实话,作者能写出这么牛的递归并且保证正确相信难倒了不少学生(包括我)。
还有一本经典教材,采取不同的方法解决这个问题:节点增设高度信息。然后对插入路径进行高度平衡。我比较青睐这种做法。
然而这种做法却需要一个额外的节点来表示空节点,否则无法正确处理高度差。所以自然而然想到了null object这个模式。
好了,现在开始解决插入中最麻烦的问题:平衡高度。
一共4中情况(OMG!)但是都只需要知道失去平衡的最小的祖先节点就可以了(这就是回溯插入路径):
- 受影响的节点从1增加到2,左子树的树高是1。也就是插入的这个左子树的左边。这种情况只要对高度差为2的节点进行一次向右旋转就可以了。
- 受影响的节点从-1增加到-2,右子树的树高是-1。也就是插入这个右子树右边。这种情况需要对高度差为2的节点进行一次向左的旋转。
- 受影响的节点从1增加到2,左子树的树高是-1.也就是插入的是这个左子树的右边。这种情况比较复杂。为了保持中序遍历的正确性(很重要),需要先对这个左子树做一次向左的旋转。然后问题转化为1的情况。
- 受影响的节点从-1增加到-2,右子树树高是1.也就是插入这个右子树的左边。这种情况需要对这个右子树做一次向右的旋转,转化为情况2。
现在的问题是怎么旋转?
先看图:
对这种情况下的x节点做一次向左的旋转。
结果图:
从结果可以看出唯一一个需要变动的字节点就是q,别的节点原来在什么位置现在还在什么位置。一开始听到旋转我马上就晕眩了。现在把图画出来自己研究一下,也就只需要变动一个节点,这样的操作显然不是很困难。但是边界检查很重要。这时有两种情况:
- x的父节点是空。也就是x本身是root,那么把root指向y就可以了。
- q是个空节点。这是不需要对q的parent节点进行操作。
private void Rotate_to_Left(Node x)
{
Node y = x.RChild;
Node z = x.Parent;
Node q = y.LChild;
if (z == NULL_NODE)
{
this.root = y;
}
else
{
if (z.LChild == x)
{
z.LChild = y;
}
else
{
z.RChild = y;
}
}
y.Parent = z;
y.LChild = x;
x.Parent = y;
x.RChild = q;
if (q != NULL_NODE)
{
q.Parent = x;
}
}
右旋转也一样只有一个子节点需要改变,代码如下:
private void Rotate_to_Right(Node x)
{
Node y = x.LChild;
Node z = x.Parent;
Node q = y.RChild;
if (z == NULL_NODE)
{
this.root = y;
}
else
{
if (z.LChild == x)
{
z.LChild = y;
}
else
{
z.RChild = y;
}
}
y.Parent = z;
y.RChild = x;
x.Parent = y;
x.LChild = q;
if (q != NULL_NODE)
{
q.Parent = x;
};
}
接着的关键问题就是如何计算节点的高度了,问题不难,但是注意我有一个null object: NULL_NODE。这个节点没有父,左,右和高度信息。
public int Height
{
get
{
if (this == NULL_NODE)
{
return 0;
}
List< Node > nodes = new List< Node >() { this };
List< List < Node > > height = new List< List< Node > >() { nodes };
while (true)
{
nodes = new List< Node >();
foreach (Node n in height[height.Count - 1])
{
if (n.LChild != NULL_NODE)
{
nodes.Add(n.LChild);
}
if(n.RChild != NULL_NODE)
{
nodes.Add(n.RChild);
}
}
if (nodes.Count != 0)
{
height.Add(nodes);
}
else
{
break;
}
}
return height.Count;
}
}
下面处理如何使这颗树回复平衡:
private void balance(Node x)
{
int balance_factor = x.LChild.Height - x.RChild.Height;
//There are 4 cases:
//1. balance factor increased form 1 to 2; do a roatation toward right can address the problem
//2. balance factor increased from -1 to -2; do a rotation toward left can address the problem
if (balance_factor == 2)
{
if (x.LChild.LChild.Height < x.LChild.RChild.Height)
{
this.Rotate_to_Left(x.LChild);
}
this.Rotate_to_Right(x);
}
if (balance_factor == -2)
{
if (x.RChild.LChild.Height > x.RChild.RChild.Height)
{
this.Rotate_to_Right(x.RChild);
}
this.Rotate_to_Left(x);
}
}
和二叉搜索树插入唯一不同的一点就是在插入结束的时候回溯到根节点:
public void Add(Node n)
{
Node p = this.root;
Node q = NULL_NODE;
if (p == NULL_NODE)
{
this.root = n;
}
else
{
while (p != NULL_NODE)
{
q = p;
if (n.Key > p.Key)
{
p = p.RChild;
}
else
{
p = p.LChild;
}
}
if (n.Key > q.Key)
{
q.RChild = n;
}
else
{
q.LChild = n;
}
n.Parent = q;
}
n = n.Parent;
while (n != NULL_NODE)
{
balance(n);
n = n.Parent;
}
}
Sunday, June 20, 2010
写给自己看之二:二叉搜索树的删除操作
- 被删除节点n没有孩子。这种情况直接删除就可以。把n.Parent的左或右设成空就可以了。
- 被删除节点n只有一个孩子。需要区分左右,然后穿越就可以了。
- 被删除节点n有两个孩子。最麻烦了,这个情况下有两种策略,也就是用前驱或后继替换这个节点,然后删除这个前驱或后继。不同的教材使用不同的策略,但是普遍都采用替换数据的方法。我也觉得替换链接要考虑的东西太多了,还容易出错,不如直接替换节点。再说,树的建立本身就不是为了频繁的插入和删除,而是为了快速的访问节点。
答案很简单:假设这个有两个孩子的节点的后继节点有左子树,那么必然可以在这个左子树中找到一个比该后继更小但是又比原节点大的节点,这样就矛盾了。同理证明前驱没有右子树。(这个结论是MIT里面的一个证明题,国内的教材似乎没有强调这一点,导致我看得很晕乎)。
好了现在再回过头看这算中情况,第一第二种情况下,n最多只有一个子节点。在看情况三,也是只有一个字节点。那么这两个有相同的地方了。
其实这个时候只要能把握住总共只有一个子节点这个问题,就可以比较简单的处理这个问题了。
Node p, child;
//This block set p as the node to be deleted.
if (n.LChild == null || n.RChild == null)
{
p = n;
}
else
{
p = Successor(n);
}
//In all 3 cases, there will be at most one child for n
if (p.LChild != null)
{
child = p.LChild;
}
else
{
child = p.RChild;
}
//Set the parent of the child
if (child != null)
{
child.Parent = p.Parent;
}
//Is the node to be deleted a root?
if (p.Parent == null)
{
this.root = child;
}
else
{
if (p.Parent.LChild == p)
{
p.Parent.LChild = child;
}
else
{
p.Parent.RChild = child;
}
}
//If the node to be deleted is not the paramter,
//this means an extra content replacement needs to be made.
if (p != n)
{
n.Key = p.Key;
}
写给自己看之一:非递归遍历二叉搜索树(栈)
先看一段代码(本以为看了代码就能理解怎么写这么个循环遍历):
Status InOrderTraverse(BiTree T, Status ( *Visit)(TElemType e)){
InitStack(S); p = T;
while(p || !StackEmpty(S)){
if (p) { Push(S, p); p = p->lchild; }
else {
Pop(S, p);
if(!Visit(p->data)) return ERROR;
p = p->rchild;
}
}
return OK
}
应该是一段很简洁高效的C/C++代码,但是看得我瞬间晕倒。我根本没看懂是怎么回事情。
再回头想一想什么才算利用栈写循环遍历呢?
首先,作为中序遍历,必然总要走所有的左子树。
Stack< Node > stack = new Stack< Node >();
Node n = this.root;
while (n != null)
{
stack.Push(n);
n = n.LChild;
}
这一步必然是这样的。
其次,当栈找完所有的左子树的时候,就要打印出该节点的值(这个没问题)。这个时候其实相当于在访问中间节点,因为如果把空的左节点看成非空,那么其实就是打印一个空值,也就是说正真的打印其实是中节点。那么此时只需要遍历该节点的右子树就可以了。
while (stack.Count != 0)
{
n = stack.Pop();
_visit(n);
stack.Push(n);
}
但是,光这段代码不可能继续去遍历这颗右子树啊!怎么办?这个时候看看原来的C/C++代码,有点感觉了。只要把这两个循环结合在一起就可以解决这个问题。灵感来自最后那句stack.Push,只要重新复制n就解决了,不过这其实是一个揣测的操作,我是一点理论根据也没有,就算对了,我感觉依然没有完全搞懂的样子。
while (n != null || stack.Count != 0)
{
if (n != null)
{
stack.Push(n);
n = n.LChild;
}
else
{
n = stack.Pop();
_visit(n);
n = n.RChild;
}
}
Wednesday, June 9, 2010
ArrayList和Hashtable
为Hashtable做铺垫的ArrayList(这个是我蓄意写的泛型版本):
一点就能看,不想看别点
class MyArrayList< T >
{
private const int INIT_SIZE = 2;
public int Length { get; private set; }
public int Capacity { get; private set; }
private T[] array;
public MyArrayList():this(INIT_SIZE)
{
}
private MyArrayList(int size)
{
array = new T[size];
this.Length = 0;
this.Capacity = size;
}
public T this[int i] {
get
{
if (i < 0 || i > this.Length - 1)
throw new IndexOutOfRangeException();
return this.array[i];
}
}
private void CheckCapcity()
{
if (this.Length >= this.Capacity)
{
if (this.Length == int.MaxValue)
throw new OverflowException();
int i = this.Length - 1;
if (this.Length < int.MaxValue / 2)
{
this.Capacity *= 2;
}
else
{
this.Capacity = int.MaxValue;
}
Debug.Print("Expand to {0}", this.Capacity);
T[] newArray = new T[this.Capacity];
while (i >= 0)
{
newArray[i] = array[i];
i--;
}
this.array = newArray;
GC.Collect();
}
}
public void Add(T t)
{
this.CheckCapcity();
this.array[this.Length++] = t;
}
public T[] ToArray()
{
T[] a = new T[this.Length];
for (int i = 0; i < this.Length; i++)
{
a[i] = this.array[i];
}
return a;
}
public void Remove(int position)
{
if (position < 0 || position >= this.Length)
{
throw new IndexOutOfRangeException();
}
for (int i = position; i < this.Length - 1; i++)
{
this.array[i] = this.array[i + 1];
}
this.Length--;
}
public void Clear()
{
for (int i = 0; i < this.Length; i++)
{
this.array = null;
}
this.Length = 0;
}
}
以下为一个Hashtable:
class MyHashtable
{
private MyArrayList< object > keys;
private ValueChain[] values;
private class ValueChain
{
public object Value { get; set; }
public object Key { get; set; }
public ValueChain next;
public ValueChain(object key, object value)
{
this.Key = key;
this.Value = value;
this.next = null;
}
}
//Apparently this is way too samll, it can ensure that Collision happens.
private const int SIZE = 4;
private MyHashtable(int size)
{
this.keys = new MyArrayList< object >();
this.values = new ValueChain[size];
}
public object[] Keys
{
get
{
return this.keys.ToArray();
}
}
public object[] Values
{
get
{
MyArrayList< object > values = new MyArrayList< object >();
foreach (object k in this.Keys)
{
values.Add(this[k]);
}
return values.ToArray();
}
}
public object this[object k]
{
get
{
int h = hash(k);
if (this.values[h] == null)
{
throw new IndexOutOfRangeException();
}
else
{
ValueChain p = this.values[h];
while (p != null)
{
if (p.Key == k)
return p.Value;
p = p.next;
}
throw new IndexOutOfRangeException();
}
}
set
{
this.Add(k, value);
}
}
public MyHashtable()
: this(SIZE)
{
}
public void Add(object key, object value)
{
int h = hash(key);
ValueChain v = new ValueChain(key, value);
if (values[h] == null)
{
values[h] = v;
keys.Add(key);
}
else
{
ValueChain p = values[h];
ValueChain q = null;
while (p != null)
{
if (p.Key == key)
{
p.Value = value;
return;
}
q = p;
p = p.next;
}
q.next = v;
keys.Add(key);
Debug.Print("Collision: {0}", key);
}
}
private int hash(object key)
{
//Obviously, this is a dumb idea.
return Math.Abs(key.GetHashCode()) % SIZE;
}
}
很明显的一点就是在比较Key的时候泛型就不管用了,这个时候要么用IComparable和IComparer两个接口,要么就用object一了百了。显然图省事就是object啦~