2013年2月2日星期六

RHEL6.3上kvm的配置过程

RHEL6.3装好后，发现kvm还是不能直接用，需要进行一些配置。这个过程可以说满满都是坑，写一篇blog来记录下。

首先，使用yum来安装相应的package。



先把selinux暂时关闭。



编辑/etc/sysctl.conf，把ipv4_ip_forward改为1。



然后使之生效。


好了之后，新建一个叫qemu的用户。后面的操作都必须在qemu的home目录下面，不然就会有权限错误。

试着启动下libvirt服务，下面的操作都必须在libvirtd服务开启的状态。



接下来就可以在虚拟机上安装OS了。


如果使用ssh来连接host机，那么需要把vnc的输出到别的机器上，才能顺利安装。修改/etc/libvirt/qemu.conf文件，把下面一条反注释。



这样就可以在windows机器上使用vncview来继续安装过程了。

接下来，就是配置kvm的网络了，有两种网络配置模式，一是默认的NAT转发模式，二是birdge模式。一般都是使用birdge模式，把虚拟机直接暴露在网络上，和真实机器处于同一地位。

用ifconfig查看可以看到一个virbr0网络接口，这个是专门为NAT转发准备的，需要先删除。然后重启libvirtd服务。



接下来，在/etc/sysconfig/network-scripts下创建ifcfg-br0，内容如下：



再修改同一目录下的ifcfg-eth0,里面增加下面一句。



然后重启网络，bridge模式就配好了。



但是现在guest还是只能通过vnc来访问，host来可以通过virsh console guestname来访问guest，但是不配置还不能使用。于是在guest上进行配置。在/etc/securetty里面增加一行。



然后再修改/etc/grub.conf，增加console=ttyS0。



再在这个文件最后一行，增加



再重启libvirtd服务，然后就可以通过virsh console访问guest了。

登陆进guest后，ifconfig可以看到guest使用的网络接口，比如eth2，那么，在guest的/etc/sysconfig/network-script下面创建并修改ifcfg-eth2文件，修改HWADDR和DEVICE的值，使之和ifconfig相符。

之后重启guest的网络服务，就可以了。

发帖者 时间： 没有评论:
标签： , ,

2012年12月23日星期日

NUMA基础知识


这一周开始涉猎一些服务器性能调优的工作，主要是NUMA机器上的scalability的问题，比较有意思，所以在此记录一下。
NUMA是Non-Uniform Memory Access 的简称，是一种多核处理器机器的架构。和SMP不同，SMP是一种Uniform Memory Access，即所有CPU访问同一内存地址的时间一样，而NUMA上不同CPU访问同一地址所需要的时间是不同的。SMP是没有办法添加太多CPU了，因为内存的带宽有限，过多CPU造成的竞争没法解决，而NUMA突破了SMP机器上架构上的限制，可以有几十个甚至上百个CPU。
具有 4 个处理器的 NUMA 节点
NUMA把若干CPU归为一个node，每个node都有专属自己的local memory和系统总线。处于同一node的CPU访问自属于这个node的local memory速度是一致的，而且是最快的。一旦到了需要访问其它node的memory时，这种内存访问称为remote memory access，其速度就会比访问local memory慢很多，因为它需要通过系统总线和memory hub。
可以使用这条命令来看local memory access和remote memory access的区别。
numactl –cpunodebind=0 numademo 256m memset
结果如下
[xxx@xxx ~]$ numactl –cpunodebind=0 numademo 256m memset
2 nodes available
memory with no policy memset Avg 7571.95 MB/s Max 8428.64 MB/s Min 5787.87 MB/s
local memory memset Avg 7987.18 MB/s Max 8430.76 MB/s Min 6215.51 MB/s
memory interleaved on all nodes memset Avg 5723.35 MB/s Max 6364.35 MB/s Min 4109.17 MB/s
memory on node 0 memset Avg 7766.91 MB/s Max 8434.21 MB/s Min 6094.71 MB/s
memory on node 1 memset Avg 4592.07 MB/s Max 5134.67 MB/s Min 3922.37 MB/s
memory interleaved on 0 1 memset Avg 6035.05 MB/s Max 6366.01 MB/s Min 5416.59 MB/s
setting preferred node to 0
memory without policy memset Avg 7813.53 MB/s Max 8430.76 MB/s Min 6219.83 MB/s
setting preferred node to 1
memory without policy memset Avg 4705.41 MB/s Max 5103.24 MB/s Min 3813.17 MB/s
manual interleaving to all nodes memset Avg 5557.70 MB/s Max 6357.11 MB/s Min 4561.12 MB/s
manual interleaving on node 0/1 memset Avg 5895.08 MB/s Max 6417.76 MB/s Min 4903.92 MB/s
current interleave node 0
running on node 0, preferred node 0
local memory memset Avg 7691.27 MB/s Max 8460.79 MB/s Min 6435.14 MB/s
memory interleaved on all nodes memset Avg 5836.12 MB/s Max 6368.58 MB/s Min 4561.97 MB/s
memory interleaved on node 0/1 memset Avg 5646.38 MB/s Max 6361.78 MB/s Min 4572.77 MB/s
alloc on node 1 memset Avg 4634.88 MB/s Max 5101.78 MB/s Min 4013.63 MB/s
local allocation memset Avg 7135.54 MB/s Max 8310.44 MB/s Min 5955.31 MB/s
setting wrong preferred node memset Avg 4719.06 MB/s Max 5100.43 MB/s Min 3942.65 MB/s
setting correct preferred node memset Avg 7773.80 MB/s Max 8435.27 MB/s Min 6498.70 MB/s
running on node 1, preferred node 0
local memory memset Avg 8502.54 MB/s Max 8581.70 MB/s Min 8416.49 MB/s
memory interleaved on all nodes memset Avg 6376.26 MB/s Max 6450.60 MB/s Min 6339.40 MB/s
memory interleaved on node 0/1 memset Avg 6497.49 MB/s Max 6507.53 MB/s Min 6474.41 MB/s
alloc on node 0 memset Avg 5204.73 MB/s Max 5219.64 MB/s Min 5181.85 MB/s
local allocation memset Avg 8624.27 MB/s Max 8641.09 MB/s Min 8579.78 MB/s
setting wrong preferred node memset Avg 5200.46 MB/s Max 5211.43 MB/s Min 5176.95 MB/s
setting correct preferred node memset Avg 8620.58 MB/s Max 8641.37 MB/s Min 8579.50 MB/s
基本上，scalability的问题都是由内存访问速度不一致导致的，MIT的人在这方面做了一个很经典的研究（链接），我现在也基本遵循了他们的方法来做。他们发现的两个问题都非常典型，首先是spin lock，这种test&set全局变量的操作，导致很多CPU都在做cache cohernet，然后做cache一致性时需要的全局变量的值需要remote memory access，导致了性能的剧烈下降。第二个例子是reference counting，导致性能下降的原因也和spin lock相同。
一般调优NUMA上的性能就使用numactl命令，把进程绑定到某一节点上，这样可以解决大部分的问题。可以先通过numactl –show或者numactl –hardware来查看硬件信息，而numastat可以看到开机运行到现在的内存分配的locality。
numactl –localalloc –cpunodebind=nodeid progname
现在还只有一些初步了解，希望可以快速学习相关知识，追上大家的脚步。
PS:关于DL980准确的硬件描述应该如下，拷贝自HP的文档：
The above table shows the logical processor assignments for the first two processors from a 64-core DL980 (8 processors with 8 cores per processor) with Hyper-threading enabled. The Physical ID is the physical processor socket. Core ID is the processing core on a particular physical processor. Thus, logical processor numbers 0 and 64 are the two threads on the first core on the first physical processor.
发帖者 时间： 没有评论:
标签：

2012年3月30日星期五

How to learn Haskell


I’m going to order this guide by the level of skill you have in haskell, going from an absolute beginner right up to an expert. Note that this process will take many months (years?), so it is rather long.我将根据你的haskell水平写这个指导，从初级菜鸟到专家级别。注意这个修炼过程很长，需要很多个月（年？）来达成。
Absolute Beginner
完全新手
Firstly, haskell is capable of anything, with enough skill. It is very fast (behind only c and c++ in my experience), and can be used from anything from simulations, servers, guis and web applications.
首先，只要水平到家，haskell适用于任何领域。它非常快（据我的经验，只比C和C++慢点），而且可以用在任何领域，从模拟计算，服务器，界面直到web应用。
However there are some problems that are easier to write for a beginner in haskell than others. Mathematical problems and list process programs are good candidates for this, as they only require the most basic of haskell knowledge to be able to write.
但是对于初学者来说，有些问题用haskell更容易些。数学问题和列表处理程序就是代表，它们只需要最基本的haskell知识。
Firstly, a good guide to learning the very basics of haskell is the first 6 chapters of learn you a haskell. While reading this, it is a very good idea to also be solving simple problems with what you know.
首先，关于haskell基础知识有个非常好的教程，就是的前六章。在阅读它的同时，最好也用你学到的知识来解决些简单的问题。
A good list of problems to try is the haskell 99 problems page. These start off very basic, and get more difficult as you go on. It is very good practice doing a lot of those, as they let you practice your skills in recursion and higher order functions. I would recommend skipping any problems that require randomness as that is a bit more difficult in haskell.
有一个很好的问题集，是haskell 99 problems page。它从最基本的开始，一点一点增加难度。多做些上面的题目是很好的实践，因为你可以练习递归和高阶函数的技巧。我推荐如果遇到需要随机数的题目，就先跳过它，因为这个在haskell里有点搞。
Once you have done a few of those, you could move on to doing a few of the Project Euler problems. These are sorted by how many people have completed them, which is a fairly good indication of difficulty. These test your logic and haskell more than the previous problems, but you should still be able to do the first few. A big advantage haskell has with these problems is Integers aren’t limited in size. To complete some of these problems, it will be useful to have read chapters 7 and 8 of learn you a haskell as well.
当你做好了一些题，也可以考虑转战 Project Euler. 这里的题目是按照完成人数来排序的，也显示它们的难度。它们要比前面的题目要更考验你的逻辑和haskell技术,但是你也应该可以完成比较靠前的题目。用haskell做这些题目有个优势，就是Integers没有size限制。你可能需要读读的第七和第八章。
Beginner
初学者
After that you should have a fairly good handle on recursion and higher order functions, so it would be a good time to start doing some more real world problems. A very good place to start is Real World Haskell (online book, you can also purchase a hard copy). I found the first few chapters introduced too much too quickly for someone who has never done functional programming/used recursion before. However with the practice you would have had from doing the previous problems you should find it perfectly understandable.
当你比较了解递归和高阶函数之后，差不多是时候来解决点真正的问题了。（有在线的免费版本，也可以上书店买印刷版）是一个很好的开始。如果你以前没有接触过函数式编程，不了解递归的概念，前几章会很吃力，但是如果你已经有了前面的练习，你就会发现它很好理解。
Working through the problems in the book is a great way of learning how to manage abstractions and building reusable components in haskell. This is vital for people used to object-orientated (oo) programming, as the normal oo abstraction methods (oo classes) don’t appear in haskell (haskell has type classes, but they are very different to oo classes, more like oo interfaces). I don’t think it is a good idea to skip chapters, as each introduces a lot new ideas that are used in later chapters.
理解这本书上的问题是学习如何在haskell中管理抽象和构建可复用组件的好方法。对于那些习惯于面向对象编程的人尤为重要，因为haskell并不包含通常的面向对象抽象方法(haskell中有type类，但是它和class完全不同，更像是interface)。我觉得最好不要跳过章节，因为每一章都介绍了很多新内容，会在后面的章节用到。
After a while you will get to chapter 14, the dreaded monads chapter (dum dum dummmm). Almost everyone who learns haskell has trouble understanding monads, due to how abstract the concept is. I can’t think of any concept in another language that is as abstract as monads are in functional programming. Monads allows many ideas (such as IO operations, computations that might fail, parsing,…) to be unified under one idea. So don’t feel discouraged if after reading the monads chapter you don’t really understand them. I found it useful to read many different explanations of monads; each one gives a new perspective on the problem. Here is a very good list of monad tutorials. I highly recommend the All About Monads, but the others are also good.
不一会你就到了第14章，传说中令人畏惧的monads。基本上每一个haskell学习者在曾在理解monads上有过困难，因为这个概念太抽象了。我没见过其它什么语言里有比这还抽象的概念。Monads允许很多不同的概念（比如IO操作，可能失败的计算，解析等）都被统一到一个大的概念下。所以当你读完这一章觉得没有弄懂时，不要灰心。读读其它的对monads的解说会有些帮助，通常都会展示一个新的视角。这里有一个monad教程的列表list of monad tutorials。我很推崇这篇All About Monads，不过其它的也不错。
Also, it takes a while for the concepts to truly sink in. This comes through use, but also through time. I find that sometimes sleeping on a problem helps more than anything else! Eventually, the idea will click, and you will wonder why you struggled to understand a concept that in reality is incredibly simple. It is awesome when this happens, and when it does, you might find haskell to be your favorite imperative programming language :)
当然，真正完全理解还需要一段时间。理解通常需要练习，这也需要时间。我发现有时候带着问题睡觉非常有用。最终，当灵感来了，你会奇怪为什么你会在这么简单的概念上挣扎这么久。这种感觉很带劲，当你有这种感觉时，你大概觉得haskell是你的最爱了。
To make sure that you are understanding Haskell type system perfectly, you should try to solve 20 intermediate haskell exercises. Those exercises using fun names of functions like “furry” and “banana” and helps you to have a good understanding of some basic functional programming concepts if you don’t have them already. Nice way to spend your evening with list of paper covered with arrows, unicorns, sausages and furry bananas.
如果想要完全理解haskell的类型系统，你应该去试试 20 intermediate haskell exercises. 在这些练习里，函数名都很有趣，比如”furry”还有”banana”，帮助你理解基本的函数式编程概念。晚上花些时间在这些箭头，独角兽，香肠和香蕉皮（应该都是函数名）上是个不错的选择。
Intermediate
中级
Once you understand Monads, I think you have made the transition from a beginner haskell programmer to an intermediate haskeller. So where to go from here? The first thing I would recommend (if you haven’t already learnt them from learning monads) is the various types of monads, such as Reader, Writer and State. Again, Real world haskell and All about monads gives great coverage of this. To complete your monad training learning about monad transformers is a must. These let you combine different types of Monads (such as a Reader and State monad) into one. This may seem useless to begin with, but after using them for a while you will wonder how you lived without them.
一旦你理解了monads，我认为你就从haskell初学者转变为中级水平了。现在应该怎么走？首先我推荐的是不同类型的monads（如果你在学习时还没学到的话），比如Reader,Writer和State。覆盖全部这些。nonad变换也是monad学习中的必须一部分。它们让你把不同类型的monads合并到一起（比如Reader和State monads）。开始可能觉得没有什么用，但是用了一阵后就觉得离不开它们了。
Now you can finish the real world haskell book if you want. Skipping chapters now though doesn’t really matter, as long as you have monads down pat. Just choose what you are interested in.
如果你想，现在你可以把看完了。只要你弄明白了monads，跳跳章节没问题，选择自己感兴趣的看看。
With the knowledge you would have now, you should be able to use most of the packages on cabal (well the documented ones at least…), as well as most of the libraries that come with haskell. A list of interesting libraries to try would be:
以你现在的知识，可以去玩玩大多数的cabal里的package了，包括大多数的haskell库。下面是一些有意思的库：
  • Parsec: for parsing programs and text. Much better than using regexps. Excellent documentation, also has a real world haskell chapter.
  • Quickcheck: A very cool testing program. What you do is write a predicate that should always be true (eg length (reverse lst) == length lst). You then pass the predicate the quickCheck, and it will generate a lot of random values (in this case lists) and test that the predicate is true for all results. See also the online manual.
  • HUnit: Unit testing in haskell.
  • gtk2hs: The most popular gui framework for haskell, lets you write gtk applications in haskell.
  • happstack: A web development framework for haskell. Doesn’t use databases, instead a data type store. Pretty good docs (another framework would be Turbinado, haven’t tried it yet though).
  • Parsec: Parser库，比正则表达式强多了，文档很棒，而且在real world haskell中有一章介绍。
  • Quickcheck:一个很酷的测试程序。只需要指定真断言(比如length (reverse lst) == length lst)， 然后把这个断言传给quickCheck，然后它会产生随机数据（这个例子里是list）来测试这个断言是否为真，可以看在线文档 online manual.
  • HUnit:haskell单元测试。
  • gtk2hs:最流行的gui框架，可以用haskell写gtk程序。
  • happstack: 一个haskell web开发框架，没有使用数据库，而是使用data type store。文档很棒。（另一个是Turbinado, 不过没有试过）
Also, there are many concepts (like the Monad concept) that you should eventually learn. This will be easier than learning Monads the first time, as your brain will be used to dealing with the level of abstraction involved. A very good overview for learning about these high level concepts and how they fit together is the typeclassopedia article (about half way through, pdf)
而且你最终还会学到很多概念（就像monad）。因为你头脑已经适应这种程度的抽象了，所以不会像当初学习monads时那么难。一个很好的关于这些高阶概念的总结和它们怎么结合在一起的文档是typeclassopedia article
  • Applicative: An interface like Monads, but less powerful. Every Monad is Applicative, but not vice versa. This is useful as there are some types that are Applicative but are not Monads. Also, code written using the Applicative functions is often more composable than writing the equivalent code using the Monad functions. SeeFunctors, Applicative Functors and Monoids from the learn you a haskell guide.
  • Foldable,Traversable: Typeclasses that abstract many of the operations of lists, so that the same functions can be applied to other container types. See also the haskell wiki explaination.
  • Monoid: A Monoid is a type that has a zero (or mempty) value, and an operation that joins two Monoids together, such that operation x mempty = x. Many types are Monoids, such as numbers, with mempty = 0 and operation = plus. This is useful in many situations.
  • Arrows: Arrows are a way of representing computations that take an input and return an output. A function is the most basic type of arrow, but there are many other types. The library also has many very useful functions for manipulating arrows – they are very useful even if only used with plain old haskell functions.
  • Arrays: the various mutable/immutable arrays in haskell.
  • ST Monad: lets you write code with a mutable state that runs very quickly, while still remaining pure outside the monad. See the link for more details.
  • FRP: Functional Reactive Programming, a new, experimental way of writing code that handles events, triggers, inputs and outputs (such as a gui). I don’t know much about this though.
  • Applicative:一个类似的monads的接口，没有那么强大。每个monad都是Applicative，但是反过来不是。当某些类型是Applicative但是不是monads时，这个概念就很有用。而且，利用applicative写程序要比相同的功能用monads来实现要容易理解，比如haskell趣学指南中的Functors, Applicative Functors and Monoids
  • Foldable,Traversable: 抽象了很多list操作的Typeclasses，这样相同的函数可以作用在很多不同的容器类型上。可见到 haskell wiki explaination.
  • Monoid:只包含0（或者mempty）的monads和一个操作把两个Monoids合并，比如operation x mempty = x.很多类型都是Monoids，比如Number加上mempty = 0和operation=plus。这些在很多情况上都有用。
  • Arrows:一种表示拿一个输入在return一个输出的计算。函数是最为基本的arrow，当然也有其它的类型。库里也有很多操作arrows的函数，这些函数对于操作普通haskell函数也很有用。
  • Arrays:haskell中可变和不可变的队列。
  • ST Monad:可以在一个快速的可变状态中编程，而对于外部还是纯函数的。
  • FRP:函数式反应编程，一种新的，实验性的编程方法。可以处理事件，触发器，输入和输出（比如gui）
There are a lot of new language features you should have a look at. I’ll just list them, you can find lots of info about them from google, the haskell wikibook, the haskellwiki.org site and ghc documentation.
有很多语言特性，你可以去研究。我列出了一些，你可以自行google之，或者查haskell wikibook, the haskellwiki.org site 和 ghc documentation.
  • Multiparameter type classes/functional dependencies
  • Type families
  • Existentially quantified types
  • Phantom types
  • GADTS
  • others…
  • 多参数type classed/函数依赖
  • 类型族
  • 存在限定类型
  • 影子类型
  • GADTS
  • 其它….
A lot of haskell is based around category theory, so you may want to look into that. Unfortunately I don’t know any good links for learning category theory for beginners.
haskell基本都是建立在范畴论上的，所以你也可能需要看看。可惜我不知道有什么资料推荐给初学者。
Finally you will want to learn more about the various haskell tools. These include:
最后你也要学点haskell的工具，包括：
  • ghc (and all its features)
  • cabal: the haskell package system
  • darcs: a distributed version control system written in haskell, very popular for haskell programs.
  • haddock: a haskell automatic documentation generator
  • ghc 和它的特性
  • cabal haskell包系统
  • darcs:haskell写的分布式版本管理系统，haskell界很流行
  • haddock:haskell的自动文档生成
While learning all these new libraries and concepts, it is very useful to be writing a moderate-sized project in haskell. It can be anything (eg a small game, data analyser, website, compiler). Working on this will allow you to apply many of the things you are now learning. You stay at this level for ages (this is where I’m at).
当学习这些库和概念时，写个中型项目会比较好。随便什么都好（比如小游戏，数据分析，网站，编译器）。做这些可以把你所学的都用上。你可能会在这个阶段停留很久（我就是这样）
Expert
专家
It will take you years to get to this stage (hello from 2009!), but from here I’m guessing you start writing phd papers, new ghc extensions, and coming up with new abstractions.
这个可要好多年才能到这个阶段，到了这个阶段，你大概在写博士论文，新的ghc扩展，和新的抽象结构。
Getting Help
寻求帮助
Finally, while at any stage of learning, there are multiple places for getting information. These are:
最后，在学习过程中，很多地方可以获得帮助，包括：
  • the #haskell irc channel
  • the mailing lists. These are worth signing up for just to read the discussions that take place – some are very interesting.
  • other places listed on the haskell.org home page
  • #haskell irc频道
  • 邮件组，很值得去注册，很多讨论很有趣，值得一读。
  • haskell.org上列出来一些地方
Conclusion
结论
Well this turned out longer than I expected… Anyway, I think it is a very good idea to become proficient in haskell. It takes a long time, but that is mainly because you are learning a completely new way of thinking by doing so. It is not like learning ruby after learning java, but like learning java after learning c. Also, I am finding that my object-orientated programming skills have improved as a result of learning haskell, as I am seeing many new ways of abstracting ideas.
我写得比我打算的要长点…不管怎样，我觉得熟练掌握haskell是个很棒的主意。需要很长的时间，但是这是因为你在学习一种全新的思考方式，和学完java之后学习ruby不一样，比较像学完C后学习java。而且，学了haskell后，我觉得我的面向对象功力也增长了，因为我有了很多新的抽象概念。
发帖者 时间： 没有评论:
标签：

2010年12月2日星期四

Not so bad

KingSoft announced the openSource of defense software today (http://code.ijinshan.com). No matter what the purpose they have, it's a big thing in our industry.

But I saw a post http://www.cnblogs.com/MichaelPeng/archive/2010/12/02/1893999.html , criticized the quality of the source code.

But I just think it's not so bad. I checked several abstract class. I found that all the abstract class have such form.

class IInterface {
virtual void method1() = 0;
virtual void method2() = 0;
...
};

It means that they only use abstract class as a interface (just like Java's interface), never mix up with its implementation. All the abstract classes with an "I" as a prefix, only have pure virtual functions. It's a good habit. KingSoft can deliver so many products through their source code's quality is very good, but as we can see, it's not so bad.
发帖者 时间： 没有评论:

2010年11月24日星期三

restart from here

Let's restart from here.

It's a shame to look back to the old articles I posted. Poor understanding about .NET and the history of computer software platform. Life before .NET is not primitive society, I just ignore other operating systems (like Unix/Linux) and other language platforms (like Java). Now I'm not a windows programmer, and I know that I have a lot of things to learn.

I started so many topics, but I never finished even one (included my another blog hosted on Javaeye). I must change it. I plan to write my blog with my pity English every Saturday night. So, let's just restart from here.
发帖者 时间： 没有评论:

2010年2月24日星期三

Avl树实现的续

接着看删除部分，删除部分比插入要更难搞一些。对于删除，同样需要分情况讨论。 
1.如果是在一个平衡节点下删除，只要把这个节点的高度信息修改就可以了 
2.如果是在较长的子树下删除，就把这个节点的高度信息修改成平衡 
以上两种情况都不需要进行旋转。 
3.如果是在较短的子树下删除，除了更新高度信息外，还需要旋转节点。这时又分3种情况讨论。 
3种情况的图如下，直接针对编程就可以了 

 

 

 

与插入一样，删除时不必从树根开始更新，记录一个path_top即可。如果某个节点是平衡的，那么删除不会影响到它以上的节点，如果某个节点下的情况和图1相同，那么删除也不会影响到它以上的节点。这时可以把path_top设为该节点。另外，treep是指向删除节点右子树中最小的节点，如果用中序遍历，就是下个节点，将用它的值来代替删除节点。 

C代码  收藏代码
  1. int avl_delete(node *treep, value_t target)  
  2. {  
  3.     /* delete the target from the tree, returning 1 on success or 0 if 
  4.      * it wasn't found 
  5.      */  
  6.     node tree = *treep, targetn;  
  7.     node *path_top = treep;  
  8.     node *targetp = NULL;  
  9.     direction dir;  
  10.       
  11.     while (tree) {  
  12.         dir = (target > tree->value);  
  13.         if (target == tree->value)  
  14.             targetp = treep;  
  15.         if (tree->next[dir] == NULL)  
  16.             break;  
  17.         if (Balanced(tree)  
  18.             || (tree->longer == (1-dir) && Balanced(tree->next[1-dir]))  
  19.             ) path_top = treep;  
  20.         treep = &tree->next[dir];  
  21.         tree = *treep;  
  22.     }  
  23.     if (!targetp)  
  24.         return 0;  
  25.   
  26.     /* adjust balance, but don't lose 'targetp' */  
  27.     targetp = avl_rebalance_del(path_top, target, targetp);  
  28.   
  29.     /* We have re-balanced everything, it remains only to  
  30.      * swap the end of the path (*treep == treep) with the deleted item 
  31.      * (*targetp == targetn) 
  32.      */  
  33.     avl_swap_del(targetp, treep, dir);  
  34.   
  35.     return 1;  
  36. }  


这一段代码负责重新平衡树，除了最后一个node更新之外(tree-next[dir] == NULL)，其余的都要更新高度信息，如有必要，还有旋转。 
C代码  收藏代码
  1. node *avl_rebalance_del(node *treep, value_t target, node *targetp)  
  2. {  
  3.     /* each node from treep down towards target, but 
  4.      * excluding the last, will have a subtree grow 
  5.      * and need rebalancing 
  6.      */  
  7.     node targetn = *targetp;  
  8.   
  9.     while (1) {  
  10.         node tree = *treep;  
  11.         direction dir = (target > tree->value);  
  12.   
  13.         if (tree->next[dir]==NULL)  
  14.             break;  
  15.   
  16.         if (Balanced(tree))  
  17.             tree->longer = 1-dir;  
  18.         else if (tree->longer == dir)  
  19.             tree->longer = NEITHER;  
  20.         else {  
  21.                         // 对比图可以看到，这个是第三幅图的场景  
  22.             if (tree->next[1-dir]->longer == dir)  
  23.                 avl_rotate_3_shrink(treep, dir);  
  24.             else // 第一二幅图  
  25.                 avl_rotate_2_shrink(treep, dir);  
  26.                         // 这一句的作用，用targetp本身也在旋转过程中时，需要把它更新，targetp作为旋转的顶，而且三幅图里，都是转到&(*treep)->next[dir]  
  27.             if (tree == targetn)  
  28.                 targetp = &(*treep)->next[dir];  
  29.         }  
  30.                 // 为什么这里是tree而不是treep?  
  31.                 // 是treep也可以，但是旋转后treep是tree的，这样要多遍历一个节点  
  32.         treep = &tree->next[dir];  
  33.     }  
  34.     return targetp;  
  35. }  


交换并删除的代码比较简单，如下 
C代码  收藏代码
  1. void avl_swap_del(node *targetp, node *treep, direction dir)  
  2. {  
  3.     node targetn = *targetp;  
  4.     node tree = *treep;  
  5.   
  6.     *targetp = tree;  
  7.     *treep = tree->next[1-dir];  
  8.     tree->next[LEFT] = targetn->next[LEFT];  
  9.     tree->next[RIGHT]= targetn->next[RIGHT];  
  10.     tree->longer = targetn->longer;  
  11.   
  12.     free(targetn);  
  13. }  


最后是后种旋转的代码实现，都比较直观，如果对着图看。 
C代码  收藏代码
  1. void avl_rotate_2_shrink(node *path_top, direction dir)  
  2. {  
  3.     node D, B, C;  
  4.   
  5.     D = *path_top;  
  6.     B = D->next[1-dir];  
  7.     C = B->next[dir];  
  8.   
  9.     *path_top = B;  
  10.     B->next[dir] = D;  
  11.     D->next[1-dir] = C;  
  12.   
  13.     if (Balanced(B)) {  
  14.         B->longer = dir;  
  15.         D->longer = 1-dir;  
  16.     } else {  
  17.         B->longer = NEITHER;  
  18.         D->longer = NEITHER;  
  19.     }  
  20. }  
  21.   
  22. void avl_rotate_3_shrink(node *path_top, direction dir)  
  23. {  
  24.     node B, C, D, E, F;  
  25.     F = *path_top;  
  26.     B = F->next[1-dir];  
  27.     D = B->next[dir];  
  28.     C = D->next[1-dir];  
  29.     E = D->next[dir];  
  30.   
  31.     *path_top = D;  
  32.     D->next[1-dir] = B;  
  33.     D->next[dir] = F;  
  34.     B->next[dir] = C;  
  35.     F->next[1-dir] = E;  
  36.   
  37.     B->longer = NEITHER;  
  38.     F->longer = NEITHER;  
  39.     if (D->longer == dir)  
  40.         B->longer = 1-dir;  
  41.     if (D->longer == 1-dir)  
  42.         F->longer = dir;  
  43.     D->longer = NEITHER;  
  44. }  
发帖者 时间： 没有评论:
标签：
订阅： 博文 (Atom)