2009年8月12日

问题描述:
对任意一个排列Pi,利用两个数的交换,最少多少次能将该排列变成一个升序排列。例子:
2 3 5 4 1--> 1 3 5 4 2 -->1 3 2 4 5 --> 1 2 3 4 5,最少经过三次交换,得到一个升序列。
算法:置换群和环
{3 ,7 ,1 ,6 ,2 ,4 ,8 ,5 }再和标准序列
{1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }比较
找出其中所有的"环"
这里的"环"就是指它们互相交换之后能成为标准序列的最小集合
比如 这里{1,3}是一个"环", {7,2,5,8}是一个"环"。
具体找法很简单 首先确定一个不在已找出"环"中的数字 
例如第一次从3开始,3对应标准序列的1 再找1对应的标准序列3 3回到了开始的数字 那么这个环就是{1,3}
第二次从7开始,7->2 2->5 5->8 8->7 所以第二个环是{7,2,5,8}
第三个环是{6,4}
这样所有的数字都在环中了
交换的次数=(数字总数-环数)=8-3=5

posted @ 2009-08-12 11:37 newstar 阅读(302) | 评论 (0)编辑 收藏

2009年8月7日

LIS(最长递增序列问题 nlogn)
P:0<=i<n;k是序列a[0:i]的最长递增子序列的长度;b[k]是序列a[0:i]中所有长度为k的递增子序列中最小结尾元素的值。在有i-1到i的循环中,当a[i] >= b[k]时,k = k+1,b[k] = a[i];当a[i] < b[k]时,应当在b[1:k]中找到一个位置j,使得b[j-1]<=a[i]<b[j],将b[j] = a[i],使得b序列满足性质.也就是说在b[1:k]序列中找到第一个比a[i]大的元素,将这个元素置为a[i]。为什么呢? 因为有b序列的性质可以得到,b[k]是序列a[0:i]中所有长度为k的递增子序列中最小结尾元素的值,那么如果存在b[j-1]<=a[i]<b[j],说明在a[0:i-1]中,长度为j-1的子序列的最小结束元素是b[j-1],长度为j的子序列的最小结束元素是b[j],i>j>j-1且b[j]>a[i]>b[j-1],所以在a[0:i]中长度为j的子序列的最小结束元素是a[i],因为它比b[j]小。从这也可以看出 b序列是有序的,可以用二分求解出a[i]放入的位置此算法关键:维护b序列的性质,二分求解
posted @ 2009-08-07 21:01 newstar 阅读(469) | 评论 (1)编辑 收藏

2009年7月9日

题目描述:
"4Blocks" is a two player cooperative game played on a special board. The board is a grid composed of 1x1 square cells. There are two different kinds of blocks: '1' blocks and '4' blocks. '1' blocks are 1x1, and '4' blocks are 2x2:


You must place blocks on the board so that their sides are aligned to the grid lines and no two blocks overlap. The final score is the sum of the values in each cell. '1' blocks are worth 1 point, and '4' blocks are worth 16 points because they cover 4 cells and each cell is worth 4 points.

Your friend has taken his turn and placed a number of '1' blocks on the board. The current configuration is given in the vector <string> grid. The j-th character of the i-th element of grid is '.' if the cell at row i, column j is empty, and '1' if your friend placed a '1' block in that cell. It is now your turn, and you can place any number of '1' or '4' blocks on the board, but you cannot remove any of the blocks that have already been placed. Return the maximum score that can be achieved. For example, the following images show one possible starting state, and the optimal placement of blocks from that state:



The final score would be 4*16 + 6*1 = 70
想法:求解最大的得分,也就是求出在这些空格中,可以摆放的最大的blocks的个数c,然后 16*c + n*m - 4*c既是其最大的得分。采用动态规划求解,设dp[x][y][s]表示在从方格(x,y)开始,y列的前一列的摆放状态为s,按列遍历到最后,能够摆放blocks最多有多少个。
转移方程:(x,y)的摆放状态只与前一列相关。如果(x,y)被blocks覆盖,即判断前一列状态s&(1<<x)是否为真,如果为真,则说明(X,Y)被覆盖,则dp[x][y][s] = dp[x+1][y][mask], mask = s ^(1<<x); 判断(x,y)能否摆放blocks,如果不能,dp[x][y][s] = dp[x+1][y][s],如果能,则 dp[x][y][s] = max{dp[x+1][y][s],dp[x+2][y][s']   s' = s | (1<<x) | (1<<(x+1))}
//Yings 代码
int a[30][30][1<<10];
class FourBlocks{
public:
    
int n,m;
    vector
<string> g;
    
int dp(int x,int y,int mask)
    {
        
int &ret = a[x][y][mask];
        
if(ret >= 0return ret;
        ret 
= 0;
        
if(y == m-1return ret = 0;
        
if(x == n) return ret = dp(0,y+1,mask);
        
int nm = mask;
        
if(mask & (1 << x))
        {
            nm 
^= (1<<x);
            
return ret = dp(x+1,y,nm);
        }
        
if(x == n-1 || g[x][y] == '1' || g[x][y+1== '1')
            
return ret = dp(x+1,y,nm);
        
if(g[x+1][y]=='1' || g[x+1][y+1== '1' || (mask & (1<<(x+1))))
            
return ret = dp(x+1,y,nm);
        ret 
= dp(x+1,y,nm);
        
int temp = 1 + dp(x+2,y,nm | (1<<x) | (1<<(x+1)));
        
if(temp > ret)
            ret 
= temp;
        
return ret;
    }
    
int maxScore(vector<string> grid)
    {
        g 
= grid;
        n 
= (int)g.size();
        m 
= (int)g[0].size();
        memset(a,
0xff,sizeof(a));
        
        
int c = dp(0,0,0);
        printf(
"%d\n",c);
        
return 12 * c + n*m;
    }
};

posted @ 2009-07-09 16:00 newstar 阅读(165) | 评论 (0)编辑 收藏

2009年7月5日

     摘要: 注:    写得实在太好了!    原文出处:http://blog.csdn.net/rstevens/archive/2007/10/14/1824785.aspx1.   概述 根据以前学习内核源码的经验,在学习文件系统实现之前,我大概定了个目标:1、  建立一个清晰的全局...  阅读全文
posted @ 2009-07-05 01:12 newstar 阅读(93) | 评论 (0)编辑 收藏
 
陈皓 (CSDN)

概述
——

什么是makefile?或许很多Winodws的程序员都不知道这个东西,因为那些Windows的IDE都为你做了这个工作,但我觉得要作一个好的和 professional的程序员,makefile还是要懂。这就好像现在有这么多的HTML的编辑器,但如果你想成为一个专业人士,你还是要了解 HTML的标识的含义。特别在Unix下的软件编译,你就不能不自己写makefile了,会不会写makefile,从一个侧面说明了一个人是否具备完成大型工程的能力。

因为,makefile关系到了整个工程的编译规则。一个工程中的源文件不计数,其按类型、功能、模块分别放在若干个目录中,makefile定义了一系列的规则来指定,哪些文件需要先编译,哪些文件需要后编译,哪些文件需要重新编译,甚至于进行更复杂的功能操作,因为 makefile就像一个Shell脚本一样,其中也可以执行操作系统的命令。

makefile带来的好处就是——“自动化编译”,一旦写好,只需要一个make命令,整个工程完全自动编译,极大的提高了软件开发的效率。make是一个命令工具,是一个解释makefile中指令的命令工具,一般来说,大多数的IDE都有这个命令,比如:Delphi的make,Visual C++的nmake,Linux下GNU的make。可见,makefile都成为了一种在工程方面的编译方法。

现在讲述如何写 makefile的文章比较少,这是我想写这篇文章的原因。当然,不同产商的make各不相同,也有不同的语法,但其本质都是在“文件依赖性”上做文章,这里,我仅对GNU的make进行讲述,我的环境是RedHat Linux 8.0,make的版本是3.80。必竟,这个make是应用最为广泛的,也是用得最多的。而且其还是最遵循于IEEE 1003.2-1992 标准的(POSIX.2)。

在这篇文档中,将以C/C++的源码作为我们基础,所以必然涉及一些关于C/C++的编译的知识,相关于这方面的内容,还请各位查看相关的编译器的文档。这里所默认的编译器是UNIX下的GCC和CC。



关于程序的编译和链接
——————————

在此,我想多说关于程序编译的一些规范和方法,一般来说,无论是C、C++、还是pas,首先要把源文件编译成中间代码文件,在Windows下也就是 .obj 文件,UNIX下是 .o 文件,即 Object File,这个动作叫做编译(compile)。然后再把大量的Object File合成执行文件,这个动作叫作链接(link)。

编译时,编译器需要的是语法的正确,函数与变量的声明的正确。对于后者,通常是你需要告诉编译器头文件的所在位置(头文件中应该只是声明,而定义应该放在C/C++文件中),只要所有的语法正确,编译器就可以编译出中间目标文件。一般来说,每个源文件都应该对应于一个中间目标文件(O文件或是OBJ文件)。

链接时,主要是链接函数和全局变量,所以,我们可以使用这些中间目标文件(O文件或是OBJ文件)来链接我们的应用程序。链接器并不管函数所在的源文件,只管函数的中间目标文件(Object File),在大多数时候,由于源文件太多,编译生成的中间目标文件太多,而在链接时需要明显地指出中间目标文件名,这对于编译很不方便,所以,我们要给中间目标文件打个包,在Windows下这种包叫“库文件”(Library File),也就是 .lib 文件,在UNIX下,是Archive File,也就是 .a 文件。

总结一下,源文件首先会生成中间目标文件,再由中间目标文件生成执行文件。在编译时,编译器只检测程序语法,和函数、变量是否被声明。如果函数未被声明,编译器会给出一个警告,但可以生成Object File。而在链接程序时,链接器会在所有的Object File中找寻函数的实现,如果找不到,那到就会报链接错误码(Linker Error),在VC下,这种错误一般是:Link 2001错误,意思说是说,链接器未能找到函数的实现。你需要指定函数的Object File.

好,言归正传,GNU的make有许多的内容,闲言少叙,还是让我们开始吧。



Makefile 介绍
———————

make命令执行时,需要一个 Makefile 文件,以告诉make命令需要怎么样的去编译和链接程序。

首先,我们用一个示例来说明Makefile的书写规则。以便给大家一个感兴认识。这个示例来源于GNU的make使用手册,在这个示例中,我们的工程有8个C文件,和3个头文件,我们要写一个Makefile来告诉make命令如何编译和链接这几个文件。我们的规则是:
1)如果这个工程没有编译过,那么我们的所有C文件都要编译并被链接。
2)如果这个工程的某几个C文件被修改,那么我们只编译被修改的C文件,并链接目标程序。
3)如果这个工程的头文件被改变了,那么我们需要编译引用了这几个头文件的C文件,并链接目标程序。

只要我们的Makefile写得够好,所有的这一切,我们只用一个make命令就可以完成,make命令会自动智能地根据当前的文件修改的情况来确定哪些文件需要重编译,从而自己编译所需要的文件和链接目标程序。


一、Makefile的规则

在讲述这个Makefile之前,还是让我们先来粗略地看一看Makefile的规则。

target ... : prerequisites ...
command
...
...

target也就是一个目标文件,可以是Object File,也可以是执行文件。还可以是一个标签(Label),对于标签这种特性,在后续的“伪目标”章节中会有叙述。

prerequisites就是,要生成那个target所需要的文件或是目标。

command也就是make需要执行的命令。(任意的Shell命令)

这是一个文件的依赖关系,也就是说,target这一个或多个的目标文件依赖于prerequisites中的文件,其生成规则定义在command中。说白一点就是说,prerequisites中如果有一个以上的文件比target文件要新的话,command所定义的命令就会被执行。这就是 Makefile的规则。也就是Makefile中最核心的内容。

说到底,Makefile的东西就是这样一点,好像我的这篇文档也该结束了。呵呵。还不尽然,这是Makefile的主线和核心,但要写好一个Makefile还不够,我会以后面一点一点地结合我的工作经验给你慢慢到来。内容还多着呢。:)


二、一个示例

正如前面所说的,如果一个工程有3个头文件,和8个C文件,我们为了完成前面所述的那三个规则,我们的Makefile应该是下面的这个样子的。

edit : main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o
cc -o edit main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

main.o : main.c defs.h
cc -c main.c
kbd.o : kbd.c defs.h command.h
cc -c kbd.c
command.o : command.c defs.h command.h
cc -c command.c
display.o : display.c defs.h buffer.h
cc -c display.c
insert.o : insert.c defs.h buffer.h
cc -c insert.c
search.o : search.c defs.h buffer.h
cc -c search.c
files.o : files.c defs.h buffer.h command.h
cc -c files.c
utils.o : utils.c defs.h
cc -c utils.c
clean :
rm edit main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

反斜杠(\)是换行符的意思。这样比较便于Makefile的易读。我们可以把这个内容保存在文件为“Makefile”或“makefile”的文件中,然后在该目录下直接输入命令“make”就可以生成执行文件edit。如果要删除执行文件和所有的中间目标文件,那么,只要简单地执行一下“make clean”就可以了。

在这个makefile中,目标文件(target)包含:执行文件edit和中间目标文件(*.o),依赖文件(prerequisites)就是冒号后面的那些 .c 文件和 .h文件。每一个 .o 文件都有一组依赖文件,而这些 .o 文件又是执行文件 edit 的依赖文件。依赖关系的实质上就是说明了目标文件是由哪些文件生成的,换言之,目标文件是哪些文件更新的。

在定义好依赖关系后,后续的那一行定义了如何生成目标文件的操作系统命令,一定要以一个Tab键作为开头。记住,make并不管命令是怎么工作的,他只管执行所定义的命令。make会比较targets文件和prerequisites文件的修改日期,如果prerequisites文件的日期要比targets文件的日期要新,或者target不存在的话,那么,make就会执行后续定义的命令。

这里要说明一点的是,clean不是一个文件,它只不过是一个动作名字,有点像C语言中的lable一样,其冒号后什么也没有,那么,make就不会自动去找文件的依赖性,也就不会自动执行其后所定义的命令。要执行其后的命令,就要在make命令后明显得指出这个lable的名字。这样的方法非常有用,我们可以在一个makefile中定义不用的编译或是和编译无关的命令,比如程序的打包,程序的备份,等等。



三、make是如何工作的

在默认的方式下,也就是我们只输入make命令。那么,

1、make会在当前目录下找名字叫“Makefile”或“makefile”的文件。
2、如果找到,它会找文件中的第一个目标文件(target),在上面的例子中,他会找到“edit”这个文件,并把这个文件作为最终的目标文件。
3、如果edit文件不存在,或是edit所依赖的后面的 .o 文件的文件修改时间要比edit这个文件新,那么,他就会执行后面所定义的命令来生成edit这个文件。
4、如果edit所依赖的.o文件也存在,那么make会在当前文件中找目标为.o文件的依赖性,如果找到则再根据那一个规则生成.o文件。(这有点像一个堆栈的过程)
5、当然,你的C文件和H文件是存在的啦,于是make会生成 .o 文件,然后再用 .o 文件生命make的终极任务,也就是执行文件edit了。

这就是整个make的依赖性,make会一层又一层地去找文件的依赖关系,直到最终编译出第一个目标文件。在找寻的过程中,如果出现错误,比如最后被依赖的文件找不到,那么make就会直接退出,并报错,而对于所定义的命令的错误,或是编译不成功,make根本不理。make只管文件的依赖性,即,如果在我找了依赖关系之后,冒号后面的文件还是不在,那么对不起,我就不工作啦。

通过上述分析,我们知道,像clean这种,没有被第一个目标文件直接或间接关联,那么它后面所定义的命令将不会被自动执行,不过,我们可以显示要make执行。即命令——“make clean”,以此来清除所有的目标文件,以便重编译。

于是在我们编程中,如果这个工程已被编译过了,当我们修改了其中一个源文件,比如file.c,那么根据我们的依赖性,我们的目标file.o会被重编译(也就是在这个依性关系后面所定义的命令),于是file.o的文件也是最新的啦,于是file.o的文件修改时间要比edit要新,所以edit也会被重新链接了(详见edit目标文件后定义的命令)。

而如果我们改变了“command.h”,那么,kdb.o、command.o和files.o都会被重编译,并且,edit会被重链接。


四、makefile中使用变量

在上面的例子中,先让我们看看edit的规则:

edit : main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o
cc -o edit main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

我们可以看到[.o]文件的字符串被重复了两次,如果我们的工程需要加入一个新的[.o]文件,那么我们需要在两个地方加(应该是三个地方,还有一个地方在 clean中)。当然,我们的makefile并不复杂,所以在两个地方加也不累,但如果makefile变得复杂,那么我们就有可能会忘掉一个需要加入的地方,而导致编译失败。所以,为了makefile的易维护,在makefile中我们可以使用变量。makefile的变量也就是一个字符串,理解成 C语言中的宏可能会更好。

比如,我们声明一个变量,叫objects, OBJECTS, objs, OBJS, obj, 或是 OBJ,反正不管什么啦,只要能够表示obj文件就行了。我们在makefile一开始就这样定义:

objects = main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

于是,我们就可以很方便地在我们的makefile中以“$(objects)”的方式来使用这个变量了,于是我们的改良版makefile就变成下面这个样子:

objects = main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

edit : $(objects)
cc -o edit $(objects)
main.o : main.c defs.h
cc -c main.c
kbd.o : kbd.c defs.h command.h
cc -c kbd.c
command.o : command.c defs.h command.h
cc -c command.c
display.o : display.c defs.h buffer.h
cc -c display.c
insert.o : insert.c defs.h buffer.h
cc -c insert.c
search.o : search.c defs.h buffer.h
cc -c search.c
files.o : files.c defs.h buffer.h command.h
cc -c files.c
utils.o : utils.c defs.h
cc -c utils.c
clean :
rm edit $(objects)


于是如果有新的 .o 文件加入,我们只需简单地修改一下 objects 变量就可以了。

关于变量更多的话题,我会在后续给你一一道来。


五、让make自动推导

GNU的make很强大,它可以自动推导文件以及文件依赖关系后面的命令,于是我们就没必要去在每一个[.o]文件后都写上类似的命令,因为,我们的make会自动识别,并自己推导命令。

只要make看到一个[.o]文件,它就会自动的把[.c]文件加在依赖关系中,如果make找到一个whatever.o,那么whatever.c,就会是whatever.o的依赖文件。并且 cc -c whatever.c 也会被推导出来,于是,我们的makefile再也不用写得这么复杂。我们的是新的makefile又出炉了。


objects = main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

edit : $(objects)
cc -o edit $(objects)

main.o : defs.h
kbd.o : defs.h command.h
command.o : defs.h command.h
display.o : defs.h buffer.h
insert.o : defs.h buffer.h
search.o : defs.h buffer.h
files.o : defs.h buffer.h command.h
utils.o : defs.h

.PHONY : clean
clean :
rm edit $(objects)

这种方法,也就是make的“隐晦规则”。上面文件内容中,“.PHONY”表示,clean是个伪目标文件。

关于更为详细的“隐晦规则”和“伪目标文件”,我会在后续给你一一道来。


六、另类风格的makefile

即然我们的make可以自动推导命令,那么我看到那堆[.o]和[.h]的依赖就有点不爽,那么多的重复的[.h],能不能把其收拢起来,好吧,没有问题,这个对于make来说很容易,谁叫它提供了自动推导命令和文件的功能呢?来看看最新风格的makefile吧。

objects = main.o kbd.o command.o display.o \
insert.o search.o files.o utils.o

edit : $(objects)
cc -o edit $(objects)

$(objects) : defs.h
kbd.o command.o files.o : command.h
display.o insert.o search.o files.o : buffer.h

.PHONY : clean
clean :
rm edit $(objects)

这种风格,让我们的makefile变得很简单,但我们的文件依赖关系就显得有点凌乱了。鱼和熊掌不可兼得。还看你的喜好了。我是不喜欢这种风格的,一是文件的依赖关系看不清楚,二是如果文件一多,要加入几个新的.o文件,那就理不清楚了。


七、清空目标文件的规则

每个Makefile中都应该写一个清空目标文件(.o和执行文件)的规则,这不仅便于重编译,也很利于保持文件的清洁。这是一个“修养”(呵呵,还记得我的《编程修养》吗)。一般的风格都是:

clean:
rm edit $(objects)

更为稳健的做法是:

.PHONY : clean
clean :
-rm edit $(objects)

前面说过,.PHONY意思表示clean是一个“伪目标”,。而在rm命令前面加了一个小减号的意思就是,也许某些文件出现问题,但不要管,继续做后面的事。当然,clean的规则不要放在文件的开头,不然,这就会变成make的默认目标,相信谁也不愿意这样。不成文的规矩是——“clean从来都是放在文件的最后”。


上面就是一个makefile的概貌,也是makefile的基础,下面还有很多makefile的相关细节,准备好了吗?准备好了就来。

Makefile 总述
———————

一、Makefile里有什么?

Makefile里主要包含了五个东西:显式规则、隐晦规则、变量定义、文件指示和注释。

1、显式规则。显式规则说明了,如何生成一个或多的的目标文件。这是由Makefile的书写者明显指出,要生成的文件,文件的依赖文件,生成的命令。

2、隐晦规则。由于我们的make有自动推导的功能,所以隐晦的规则可以让我们比较粗糙地简略地书写Makefile,这是由make所支持的。

3、变量的定义。在Makefile中我们要定义一系列的变量,变量一般都是字符串,这个有点你C语言中的宏,当Makefile被执行时,其中的变量都会被扩展到相应的引用位置上。

4、文件指示。其包括了三个部分,一个是在一个Makefile中引用另一个Makefile,就像C语言中的include一样;另一个是指根据某些情况指定Makefile中的有效部分,就像C语言中的预编译#if一样;还有就是定义一个多行的命令。有关这一部分的内容,我会在后续的部分中讲述。

5、注释。Makefile中只有行注释,和UNIX的Shell脚本一样,其注释是用“#”字符,这个就像C/C++中的“//”一样。如果你要在你的Makefile中使用“#”字符,可以用反斜框进行转义,如:“\#”。

最后,还值得一提的是,在Makefile中的命令,必须要以[Tab]键开始。


二、Makefile的文件名

默认的情况下,make命令会在当前目录下按顺序找寻文件名为“GNUmakefile”、“makefile”、“Makefile”的文件,找到了解释这个文件。在这三个文件名中,最好使用“Makefile”这个文件名,因为,这个文件名第一个字符为大写,这样有一种显目的感觉。最好不要用 “GNUmakefile”,这个文件是GNU的make识别的。有另外一些make只对全小写的“makefile”文件名敏感,但是基本上来说,大多数的make都支持“makefile”和“Makefile”这两种默认文件名。

当然,你可以使用别的文件名来书写Makefile,比如:“Make.Linux”,“Make.Solaris”,“Make.AIX”等,如果要指定特定的Makefile,你可以使用make的“- f”和“--file”参数,如:make -f Make.Linux或make --file Make.AIX。


三、引用其它的Makefile

在Makefile使用include关键字可以把别的Makefile包含进来,这很像C语言的#i nclude,被包含的文件会原模原样的放在当前文件的包含位置。include的语法是:

include <filename>

filename可以是当前操作系统Shell的文件模式(可以保含路径和通配符)

在include 前面可以有一些空字符,但是绝不能是[Tab]键开始。include和<filename>可以用一个或多个空格隔开。举个例子,你有这样几个Makefile:a.mk、b.mk、c.mk,还有一个文件叫foo.make,以及一个变量$(bar),其包含了e.mk和f.mk,那么,下面的语句:

include foo.make *.mk $(bar)

等价于:

include foo.make a.mk b.mk c.mk e.mk f.mk

make 命令开始时,会把找寻include所指出的其它Makefile,并把其内容安置在当前的位置。就好像C/C++的#i nclude指令一样。如果文件都没有指定绝对路径或是相对路径的话,make会在当前目录下首先寻找,如果当前目录下没有找到,那么,make还会在下面的几个目录下找:

1、如果make执行时,有“-I”或“--include-dir”参数,那么make就会在这个参数所指定的目录下去寻找。
2、如果目录<prefix>/include(一般是:/usr/local/bin或/usr/include)存在的话,make也会去找。

如果有文件没有找到的话,make会生成一条警告信息,但不会马上出现致命错误。它会继续载入其它的文件,一旦完成makefile的读取,make会再重试这些没有找到,或是不能读取的文件,如果还是不行,make才会出现一条致命信息。如果你想让make不理那些无法读取的文件,而继续执行,你可以在 include前加一个减号“-”。如:

-include <filename>
其表示,无论include过程中出现什么错误,都不要报错继续执行。和其它版本make兼容的相关命令是sinclude,其作用和这一个是一样的。


四、环境变量 MAKEFILES 

如果你的当前环境中定义了环境变量MAKEFILES,那么,make会把这个变量中的值做一个类似于include的动作。这个变量中的值是其它的 Makefile,用空格分隔。只是,它和include不同的是,从这个环境变中引入的Makefile的“目标”不会起作用,如果环境变量中定义的文件发现错误,make也会不理。

但是在这里我还是建议不要使用这个环境变量,因为只要这个变量一被定义,那么当你使用make时,所有的 Makefile都会受到它的影响,这绝不是你想看到的。在这里提这个事,只是为了告诉大家,也许有时候你的Makefile出现了怪事,那么你可以看看当前环境中有没有定义这个变量。


五、make的工作方式

GNU的make工作时的执行步骤入下:(想来其它的make也是类似)

1、读入所有的Makefile。
2、读入被include的其它Makefile。
3、初始化文件中的变量。
4、推导隐晦规则,并分析所有规则。
5、为所有的目标文件创建依赖关系链。
6、根据依赖关系,决定哪些目标要重新生成。
7、执行生成命令。

1- 5步为第一个阶段,6-7为第二个阶段。第一个阶段中,如果定义的变量被使用了,那么,make会把其展开在使用的位置。但make并不会完全马上展开, make使用的是拖延战术,如果变量出现在依赖关系的规则中,那么仅当这条依赖被决定要使用了,变量才会在其内部展开。

当然,这个工作方式你不一定要清楚,但是知道这个方式你也会对make更为熟悉。有了这个基础,后续部分也就容易看懂了。



书写规则
————

规则包含两个部分,一个是依赖关系,一个是生成目标的方法。

在Makefile 中,规则的顺序是很重要的,因为,Makefile中只应该有一个最终目标,其它的目标都是被这个目标所连带出来的,所以一定要让make知道你的最终目标是什么。一般来说,定义在Makefile中的目标可能会有很多,但是第一条规则中的目标将被确立为最终的目标。如果第一条规则中的目标有很多个,那么,第一个目标会成为最终的目标。make所完成的也就是这个目标。

好了,还是让我们来看一看如何书写规则。


一、规则举例

foo.o : foo.c defs.h # foo模块
cc -c -g foo.c

看到这个例子,各位应该不是很陌生了,前面也已说过,foo.o是我们的目标,foo.c和defs.h是目标所依赖的源文件,而只有一个命令“cc -c -g foo.c”(以Tab键开头)。这个规则告诉我们两件事:

1、文件的依赖关系,foo.o依赖于foo.c和defs.h的文件,如果foo.c和defs.h的文件日期要比foo.o文件日期要新,或是foo.o不存在,那么依赖关系发生。
2、如果生成(或更新)foo.o文件。也就是那个cc命令,其说明了,如何生成foo.o这个文件。(当然foo.c文件include了defs.h文件)


二、规则的语法

targets : prerequisites
command
...

或是这样: 

targets : prerequisites ; command
command
...

targets是文件名,以空格分开,可以使用通配符。一般来说,我们的目标基本上是一个文件,但也有可能是多个文件。

command是命令行,如果其不与“target: prerequisites”在一行,那么,必须以[Tab键]开头,如果和prerequisites在一行,那么可以用分号做为分隔。(见上)

prerequisites也就是目标所依赖的文件(或依赖目标)。如果其中的某个文件要比目标文件要新,那么,目标就被认为是“过时的”,被认为是需要重生成的。这个在前面已经讲过了。

如果命令太长,你可以使用反斜框(‘\’)作为换行符。make对一行上有多少个字符没有限制。规则告诉make两件事,文件的依赖关系和如何成成目标文件。

一般来说,make会以UNIX的标准Shell,也就是/bin/sh来执行命令。


三、在规则中使用通配符

如果我们想定义一系列比较类似的文件,我们很自然地就想起使用通配符。make支持三各通配符:“*”,“?”和“[...]”。这是和Unix的B-Shell是相同的。

波浪号(“~”)字符在文件名中也有比较特殊的用途。如果是“~/test”,这就表示当前用户的$HOME目录下的test目录。而 “~hchen/test”则表示用户hchen的宿主目录下的test目录。(这些都是Unix下的小知识了,make也支持)而在Windows或是 MS-DOS下,用户没有宿主目录,那么波浪号所指的目录则根据环境变量“HOME”而定。

通配符代替了你一系列的文件,如“*.c”表示所以后缀为c的文件。一个需要我们注意的是,如果我们的文件名中有通配符,如:“*”,那么可以用转义字符“\”,如“\*”来表示真实的“*”字符,而不是任意长度的字符串。

好吧,还是先来看几个例子吧:

clean:
rm -f *.o

上面这个例子我不不多说了,这是操作系统Shell所支持的通配符。这是在命令中的通配符。

print: *.c
lpr -p $?
touch print

上面这个例子说明了通配符也可以在我们的规则中,目标print依赖于所有的[.c]文件。其中的“$?”是一个自动化变量,我会在后面给你讲述。

objects = *.o

上面这个例子,表示了,通符同样可以用在变量中。并不是说[*.o]会展开,不!objects的值就是“*.o”。Makefile中的变量其实就是 C/C++中的宏。如果你要让通配符在变量中展开,也就是让objects的值是所有[.o]的文件名的集合,那么,你可以这样:

objects := $(wildcard *.o)

这种用法由关键字“wildcard”指出,关于Makefile的关键字,我们将在后面讨论。


四、文件搜寻

在一些大的工程中,有大量的源文件,我们通常的做法是把这许多的源文件分类,并存放在不同的目录中。所以,当make需要去找寻文件的依赖关系时,你可以在文件前加上路径,但最好的方法是把一个路径告诉make,让make在自动去找。

Makefile文件中的特殊变量“VPATH”就是完成这个功能的,如果没有指明这个变量,make只会在当前的目录中去找寻依赖文件和目标文件。如果定义了这个变量,那么,make就会在当当前目录找不到的情况下,到所指定的目录中去找寻文件了。

VPATH = src:../headers

上面的的定义指定两个目录,“src”和“../headers”,make会按照这个顺序进行搜索。目录由“冒号”分隔。(当然,当前目录永远是最高优先搜索的地方)

另一个设置文件搜索路径的方法是使用make的“vpath”关键字(注意,它是全小写的),这不是变量,这是一个make的关键字,这和上面提到的那个 VPATH变量很类似,但是它更为灵活。它可以指定不同的文件在不同的搜索目录中。这是一个很灵活的功能。它的使用方法有三种:

1、vpath <pattern> <directories>

为符合模式<pattern>的文件指定搜索目录<directories>。

2、vpath <pattern>

清除符合模式<pattern>的文件的搜索目录。

3、vpath

清除所有已被设置好了的文件搜索目录。

vapth 使用方法中的<pattern>需要包含“%”字符。“%”的意思是匹配零或若干字符,例如,“%.h”表示所有以“.h”结尾的文件。 <pattern>指定了要搜索的文件集,而<directories>则指定了<pattern>的文件集的搜索的目录。例如:

vpath %.h ../headers

该语句表示,要求make在“../headers”目录下搜索所有以“.h”结尾的文件。(如果某文件在当前目录没有找到的话)

我们可以连续地使用vpath语句,以指定不同搜索策略。如果连续的vpath语句中出现了相同的<pattern>,或是被重复了的<pattern>,那么,make会按照vpath语句的先后顺序来执行搜索。如:

vpath %.c foo
vpath % blish
vpath %.c bar

其表示“.c”结尾的文件,先在“foo”目录,然后是“blish”,最后是“bar”目录。

vpath %.c foo:bar
vpath % blish

而上面的语句则表示“.c”结尾的文件,先在“foo”目录,然后是“bar”目录,最后才是“blish”目录。


五、伪目标

最早先的一个例子中,我们提到过一个“clean”的目标,这是一个“伪目标”,

clean:
rm *.o temp

正像我们前面例子中的“clean”一样,即然我们生成了许多文件编译文件,我们也应该提供一个清除它们的“目标”以备完整地重编译而用。 (以“make clean”来使用该目标)

因为,我们并不生成“clean”这个文件。“伪目标”并不是一个文件,只是一个标签,由于“伪目标”不是文件,所以make无法生成它的依赖关系和决定它是否要执行。我们只有通过显示地指明这个“目标”才能让其生效。当然,“伪目标”的取名不能和文件名重名,不然其就失去了“伪目标”的意义了。

当然,为了避免和文件重名的这种情况,我们可以使用一个特殊的标记“.PHONY”来显示地指明一个目标是“伪目标”,向make说明,不管是否有这个文件,这个目标就是“伪目标”。

.PHONY : clean

只要有这个声明,不管是否有“clean”文件,要运行“clean”这个目标,只有“make clean”这样。于是整个过程可以这样写:

.PHONY: clean
clean:
rm *.o temp

伪目标一般没有依赖的文件。但是,我们也可以为伪目标指定所依赖的文件。伪目标同样可以作为“默认目标”,只要将其放在第一个。一个示例就是,如果你的 Makefile需要一口气生成若干个可执行文件,但你只想简单地敲一个make完事,并且,所有的目标文件都写在一个Makefile中,那么你可以使用“伪目标”这个特性:

all : prog1 prog2 prog3
.PHONY : all

prog1 : prog1.o utils.o
cc -o prog1 prog1.o utils.o

prog2 : prog2.o
cc -o prog2 prog2.o

prog3 : prog3.o sort.o utils.o
cc -o prog3 prog3.o sort.o utils.o

我们知道,Makefile中的第一个目标会被作为其默认目标。我们声明了一个“all”的伪目标,其依赖于其它三个目标。由于伪目标的特性是,总是被执行的,所以其依赖的那三个目标就总是不如“all”这个目标新。所以,其它三个目标的规则总是会被决议。也就达到了我们一口气生成多个目标的目的。 “.PHONY : all”声明了“all”这个目标为“伪目标”。

随便提一句,从上面的例子我们可以看出,目标也可以成为依赖。所以,伪目标同样也可成为依赖。看下面的例子:

.PHONY: cleanall cleanobj cleandiff

cleanall : cleanobj cleandiff
rm program

cleanobj :
rm *.o

cleandiff :
rm *.diff

“make clean”将清除所有要被清除的文件。“cleanobj”和“cleandiff”这两个伪目标有点像“子程序”的意思。我们可以输入“make cleanall”和“make cleanobj”和“make cleandiff”命令来达到清除不同种类文件的目的。

六、多目标

Makefile 的规则中的目标可以不止一个,其支持多目标,有可能我们的多个目标同时依赖于一个文件,并且其生成的命令大体类似。于是我们就能把其合并起来。当然,多个目标的生成规则的执行命令是同一个,这可能会可我们带来麻烦,不过好在我们的可以使用一个自动化变量“$@”(关于自动化变量,将在后面讲述),这个变量表示着目前规则中所有的目标的集合,这样说可能很抽象,还是看一个例子吧。

bigoutput littleoutput : text.g
generate text.g -$(subst output,,$@) > $@

上述规则等价于:

bigoutput : text.g
generate text.g -big > bigoutput
littleoutput : text.g
generate text.g -little > littleoutput

其中,-$(subst output,,$@)中的“$”表示执行一个Makefile的函数,函数名为subst,后面的为参数。关于函数,将在后面讲述。这里的这个函数是截取字符串的意思,“$@”表示目标的集合,就像一个数组,“$@”依次取出目标,并执于命令。


七、静态模式

静态模式可以更加容易地定义多目标的规则,可以让我们的规则变得更加的有弹性和灵活。我们还是先来看一下语法:

<targets ...>: <target-pattern>: <prereq-patterns ...>
<commands>
...


targets定义了一系列的目标文件,可以有通配符。是目标的一个集合。

target-parrtern是指明了targets的模式,也就是的目标集模式。

prereq-parrterns是目标的依赖模式,它对target-parrtern形成的模式再进行一次依赖目标的定义。

这样描述这三个东西,可能还是没有说清楚,还是举个例子来说明一下吧。如果我们的<target-parrtern>定义成“%.o”,意思是我们的<target>集合中都是以“.o”结尾的,而如果我们的<prereq-parrterns>定义成“%.c”,意思是对<target-parrtern>所形成的目标集进行二次定义,其计算方法是,取<target-parrtern>模式中的“%”(也就是去掉了[.o]这个结尾),并为其加上[.c]这个结尾,形成的新集合。

所以,我们的“目标模式”或是“依赖模式”中都应该有“%”这个字符,如果你的文件名中有“%”那么你可以使用反斜杠“\”进行转义,来标明真实的“%”字符。

看一个例子:

objects = foo.o bar.o

all: $(objects)

$(objects): %.o: %.c
$(CC) -c $(CFLAGS) $< -o $@


上面的例子中,指明了我们的目标从$object中获取,“%.o”表明要所有以“.o”结尾的目标,也就是“foo.o bar.o”,也就是变量$object集合的模式,而依赖模式“%.c”则取模式“%.o”的“%”,也就是“foo bar”,并为其加下“.c”的后缀,于是,我们的依赖目标就是“foo.c bar.c”。而命令中的“$<”和“$@”则是自动化变量,“$<”表示所有的依赖目标集(也就是“foo.c bar.c”),“$@”表示目标集(也就是“foo.o bar.o”)。于是,上面的规则展开后等价于下面的规则:

foo.o : foo.c
$(CC) -c $(CFLAGS) foo.c -o foo.o
bar.o : bar.c
$(CC) -c $(CFLAGS) bar.c -o bar.o

试想,如果我们的“%.o”有几百个,那种我们只要用这种很简单的“静态模式规则”就可以写完一堆规则,实在是太有效率了。“静态模式规则”的用法很灵活,如果用得好,那会一个很强大的功能。再看一个例子:


files = foo.elc bar.o lose.o

$(filter %.o,$(files)): %.o: %.c
$(CC) -c $(CFLAGS) $< -o $@
$(filter %.elc,$(files)): %.elc: %.el
emacs -f batch-byte-compile $<


$(filter %.o,$(files))表示调用Makefile的filter函数,过滤“$filter”集,只要其中模式为“%.o”的内容。其的它内容,我就不用多说了吧。这个例字展示了Makefile中更大的弹性。


八、自动生成依赖性

在Makefile中,我们的依赖关系可能会需要包含一系列的头文件,比如,如果我们的main.c中有一句“#i nclude "defs.h"”,那么我们的依赖关系应该是:

main.o : main.c defs.h

但是,如果是一个比较大型的工程,你必需清楚哪些C文件包含了哪些头文件,并且,你在加入或删除头文件时,也需要小心地修改Makefile,这是一个很没有维护性的工作。为了避免这种繁重而又容易出错的事情,我们可以使用C/C++编译的一个功能。大多数的C/C++编译器都支持一个“-M”的选项,即自动找寻源文件中包含的头文件,并生成一个依赖关系。例如,如果我们执行下面的命令:

cc -M main.c

其输出是:

main.o : main.c defs.h

于是由编译器自动生成的依赖关系,这样一来,你就不必再手动书写若干文件的依赖关系,而由编译器自动生成了。需要提醒一句的是,如果你使用GNU的C/C++编译器,你得用“-MM”参数,不然,“-M”参数会把一些标准库的头文件也包含进来。

gcc -M main.c的输出是:

main.o: main.c defs.h /usr/include/stdio.h /usr/include/features.h \
/usr/include/sys/cdefs.h /usr/include/gnu/stubs.h \
/usr/lib/gcc-lib/i486-suse-linux/2.95.3/include/stddef.h \
/usr/include/bits/types.h /usr/include/bits/pthreadtypes.h \
/usr/include/bits/sched.h /usr/include/libio.h \
/usr/include/_G_config.h /usr/include/wchar.h \
/usr/include/bits/wchar.h /usr/include/gconv.h \
/usr/lib/gcc-lib/i486-suse-linux/2.95.3/include/stdarg.h \
/usr/include/bits/stdio_lim.h


gcc -MM main.c的输出则是:

main.o: main.c defs.h

那么,编译器的这个功能如何与我们的Makefile联系在一起呢。因为这样一来,我们的Makefile也要根据这些源文件重新生成,让Makefile 自已依赖于源文件?这个功能并不现实,不过我们可以有其它手段来迂回地实现这一功能。GNU组织建议把编译器为每一个源文件的自动生成的依赖关系放到一个文件中,为每一个“name.c”的文件都生成一个“name.d”的Makefile文件,[.d]文件中就存放对应[.c]文件的依赖关系。

于是,我们可以写出[.c]文件和[.d]文件的依赖关系,并让make自动更新或自成[.d]文件,并把其包含在我们的主Makefile中,这样,我们就可以自动化地生成每个文件的依赖关系了。

这里,我们给出了一个模式规则来产生[.d]文件:

%.d: %.c
@set -e; rm -f $@; \
$(CC) -M $(CPPFLAGS) $< > $@.$$$$; \
sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.$$$$ > $@; \
rm -f $@.$$$$


这个规则的意思是,所有的[.d]文件依赖于[.c]文件,“rm -f $@”的意思是删除所有的目标,也就是[.d]文件,第二行的意思是,为每个依赖文件“$<”,也就是[.c]文件生成依赖文件,“$@”表示模式 “%.d”文件,如果有一个C文件是name.c,那么“%”就是“name”,“$$$$”意为一个随机编号,第二行生成的文件有可能是 “name.d.12345”,第三行使用sed命令做了一个替换,关于sed命令的用法请参看相关的使用文档。第四行就是删除临时文件。

总而言之,这个模式要做的事就是在编译器生成的依赖关系中加入[.d]文件的依赖,即把依赖关系:

main.o : main.c defs.h

转成:

main.o main.d : main.c defs.h

于是,我们的[.d]文件也会自动更新了,并会自动生成了,当然,你还可以在这个[.d]文件中加入的不只是依赖关系,包括生成的命令也可一并加入,让每个 [.d]文件都包含一个完赖的规则。一旦我们完成这个工作,接下来,我们就要把这些自动生成的规则放进我们的主Makefile中。我们可以使用 Makefile的“include”命令,来引入别的Makefile文件(前面讲过),例如:

sources = foo.c bar.c

include $(sources:.c=.d)

上述语句中的“$(sources:.c=.d)”中的“.c=.d”的意思是做一个替换,把变量$(sources)所有[.c]的字串都替换成 [.d],关于这个“替换”的内容,在后面我会有更为详细的讲述。当然,你得注意次序,因为include是按次来载入文件,最先载入的[.d]文件中的目标会成为默认目标。


书写命令
————

每条规则中的命令和操作系统Shell的命令行是一致的。make会一按顺序一条一条的执行命令,每条命令的开头必须以[Tab]键开头,除非,命令是紧跟在依赖规则后面的分号后的。在命令行之间中的空格或是空行会被忽略,但是如果该空格或空行是以Tab键开头的,那么make会认为其是一个空命令。

我们在UNIX下可能会使用不同的Shell,但是make的命令默认是被“/bin/sh”——UNIX的标准Shell解释执行的。除非你特别指定一个其它的Shell。Makefile中,“#”是注释符,很像C/C++中的“//”,其后的本行字符都被注释。

一、显示命令

通常,make会把其要执行的命令行在命令执行前输出到屏幕上。当我们用“@”字符在命令行前,那么,这个命令将不被make显示出来,最具代表性的例子是,我们用这个功能来像屏幕显示一些信息。如:

@echo 正在编译XXX模块......

当make执行时,会输出“正在编译XXX模块......”字串,但不会输出命令,如果没有“@”,那么,make将输出:

echo 正在编译XXX模块......
正在编译XXX模块......

如果make执行时,带入make参数“-n”或“--just-print”,那么其只是显示命令,但不会执行命令,这个功能很有利于我们调试我们的Makefile,看看我们书写的命令是执行起来是什么样子的或是什么顺序的。

而make参数“-s”或“--slient”则是全面禁止命令的显示。



二、命令执行

当依赖目标新于目标时,也就是当规则的目标需要被更新时,make会一条一条的执行其后的命令。需要注意的是,如果你要让上一条命令的结果应用在下一条命令时,你应该使用分号分隔这两条命令。比如你的第一条命令是cd命令,你希望第二条命令得在cd之后的基础上运行,那么你就不能把这两条命令写在两行上,而应该把这两条命令写在一行上,用分号分隔。如:

示例一:
exec:
cd /home/hchen
pwd

示例二:
exec:
cd /home/hchen; pwd

当我们执行“make exec”时,第一个例子中的cd没有作用,pwd会打印出当前的Makefile目录,而第二个例子中,cd就起作用了,pwd会打印出“/home/hchen”。

make 一般是使用环境变量SHELL中所定义的系统Shell来执行命令,默认情况下使用UNIX的标准Shell——/bin/sh来执行命令。但在MS- DOS下有点特殊,因为MS-DOS下没有SHELL环境变量,当然你也可以指定。如果你指定了UNIX风格的目录形式,首先,make会在SHELL所指定的路径中找寻命令解释器,如果找不到,其会在当前盘符中的当前目录中寻找,如果再找不到,其会在PATH环境变量中所定义的所有路径中寻找。MS- DOS中,如果你定义的命令解释器没有找到,其会给你的命令解释器加上诸如“.exe”、“.com”、“.bat”、“.sh”等后缀。



三、命令出错

每当命令运行完后,make会检测每个命令的返回码,如果命令返回成功,那么make会执行下一条命令,当规则中所有的命令成功返回后,这个规则就算是成功完成了。如果一个规则中的某个命令出错了(命令退出码非零),那么make就会终止执行当前规则,这将有可能终止所有规则的执行。

有些时候,命令的出错并不表示就是错误的。例如mkdir命令,我们一定需要建立一个目录,如果目录不存在,那么mkdir就成功执行,万事大吉,如果目录存在,那么就出错了。我们之所以使用mkdir的意思就是一定要有这样的一个目录,于是我们就不希望mkdir出错而终止规则的运行。

为了做到这一点,忽略命令的出错,我们可以在Makefile的命令行前加一个减号“-”(在Tab键之后),标记为不管命令出不出错都认为是成功的。如:

clean:
-rm -f *.o

还有一个全局的办法是,给make加上“-i”或是“--ignore-errors”参数,那么,Makefile中所有命令都会忽略错误。而如果一个规则是以“.IGNORE”作为目标的,那么这个规则中的所有命令将会忽略错误。这些是不同级别的防止命令出错的方法,你可以根据你的不同喜欢设置。

还有一个要提一下的make的参数的是“-k”或是“--keep-going”,这个参数的意思是,如果某规则中的命令出错了,那么就终目该规则的执行,但继续执行其它规则。



四、嵌套执行make

在一些大的工程中,我们会把我们不同模块或是不同功能的源文件放在不同的目录中,我们可以在每个目录中都书写一个该目录的Makefile,这有利于让我们的Makefile变得更加地简洁,而不至于把所有的东西全部写在一个Makefile中,这样会很难维护我们的Makefile,这个技术对于我们模块编译和分段编译有着非常大的好处。

例如,我们有一个子目录叫subdir,这个目录下有个Makefile文件,来指明了这个目录下文件的编译规则。那么我们总控的Makefile可以这样书写:

subsystem:
cd subdir && $(MAKE)

其等价于:

subsystem:
$(MAKE) -C subdir

定义$(MAKE)宏变量的意思是,也许我们的make需要一些参数,所以定义成一个变量比较利于维护。这两个例子的意思都是先进入“subdir”目录,然后执行make命令。

我们把这个Makefile叫做“总控Makefile”,总控Makefile的变量可以传递到下级的Makefile中(如果你显示的声明),但是不会覆盖下层的Makefile中所定义的变量,除非指定了“-e”参数。

如果你要传递变量到下级Makefile中,那么你可以使用这样的声明:

export <variable ...>

如果你不想让某些变量传递到下级Makefile中,那么你可以这样声明: 

unexport <variable ...>

如:

示例一:

export variable = value

其等价于:

variable = value
export variable

其等价于:

export variable := value

其等价于:

variable := value
export variable

示例二:

export variable += value

其等价于:

variable += value
export variable

如果你要传递所有的变量,那么,只要一个export就行了。后面什么也不用跟,表示传递所有的变量。

需要注意的是,有两个变量,一个是SHELL,一个是MAKEFLAGS,这两个变量不管你是否export,其总是要传递到下层Makefile中,特别是MAKEFILES变量,其中包含了make的参数信息,如果我们执行“总控Makefile”时有make参数或是在上层Makefile中定义了这个变量,那么MAKEFILES变量将会是这些参数,并会传递到下层Makefile中,这是一个系统级的环境变量。

但是make命令中的有几个参数并不往下传递,它们是“-C”,“-f”,“-h”“-o”和“-W”(有关Makefile参数的细节将在后面说明),如果你不想往下层传递参数,那么,你可以这样来:

subsystem:
cd subdir && $(MAKE) MAKEFLAGS=

如果你定义了环境变量MAKEFLAGS,那么你得确信其中的选项是大家都会用到的,如果其中有“-t”,“-n”,和“-q”参数,那么将会有让你意想不到的结果,或许会让你异常地恐慌。

还有一个在“嵌套执行”中比较有用的参数,“-w”或是“--print-directory”会在make的过程中输出一些信息,让你看到目前的工作目录。比如,如果我们的下级make目录是“/home/hchen/gnu/make”,如果我们使用“make -w”来执行,那么当进入该目录时,我们会看到:

make: Entering directory `/home/hchen/gnu/make'.

而在完成下层make后离开目录时,我们会看到:

make: Leaving directory `/home/hchen/gnu/make'

当你使用“-C”参数来指定make下层Makefile时,“-w”会被自动打开的。如果参数中有“-s”(“--slient”)或是“--no-print-directory”,那么,“-w”总是失效的。



五、定义命令包

如果Makefile中出现一些相同命令序列,那么我们可以为这些相同的命令序列定义一个变量。定义这种命令序列的语法以“define”开始,以“endef”结束,如:

define run-yacc
yacc $(firstword $^)
mv y.tab.c $@
endef

这里,“run-yacc”是这个命令包的名字,其不要和Makefile中的变量重名。在“define”和“endef”中的两行就是命令序列。这个命令包中的第一个命令是运行Yacc程序,因为Yacc程序总是生成“y.tab.c”的文件,所以第二行的命令就是把这个文件改改名字。还是把这个命令包放到一个示例中来看看吧。

foo.c : foo.y
$(run-yacc)

我们可以看见,要使用这个命令包,我们就好像使用变量一样。在这个命令包的使用中,命令包“run-yacc”中的“$^”就是“foo.y”,“$@”就是“foo.c”(有关这种以 “$”开头的特殊变量,我们会在后面介绍),make在执行命令包时,命令包中的每个命令会被依次独立执行。

posted @ 2009-07-05 00:22 newstar 阅读(91) | 评论 (0)编辑 收藏

2009年7月1日

TCP是面向连接的,所谓面向连接,就是当计算机双方通信时必需先建立连接,然后数据传送,最后拆除连接三个过程 

并且TCP在建立连接时又分三步走: 

第一步是请求端(客户端)发送一个包含SYN即同步(Synchronize)标志的TCP报文,SYN同步报文会指明客户端使用的端口以及TCP连接的初始序号;  

第二步,服务器在收到客户端的SYN报文后,将返回一个SYN+ACK的报文,表示客户端的请求被接受,同时TCP序号被加一,ACK即确认(Acknowledgement)。  

第三步,客户端也返回一个确认报文ACK给服务器端,同样TCP序列号被加一,到此一个TCP连接完成。 然后才开始通信的第二步:数据处理。 

这就是所说的TCP三次握手(Three-way Handshake)。  

简单的说就是:(C:客户端,S:服务端) 

C:SYN到S 

S:如成功--返回给C(SYN+ACK) 

C:如成功---返回给S(ACK) 

以上是正常的建立连接方式,但如下: 

假设一个C向S发送了SYN后无故消失了,那么S在发出SYN+ACK应答报文后是无法收到C的ACK报文的(第三次握手无法完成),这种情况下S一般会重试(再次发送SYN+ACK给客户端)并等待一段时间后丢弃这个未完成的连接,这段时间的长度我们称为SYN Timeout,一般来说这个时间是分钟的数量级(大约为30秒-2分钟);一个C出现异常导致S的一个线程等待1分钟并不是什么很大的问题,但如果有一个恶意的攻击者大量模拟这种情况,S将为了维护一个非常大的半连接列表而消耗非常多的资源----数以万计的半连接,即使是简单的保存并遍历也会消耗非常多的CPU时间和内存,何况还要不断对这个列表中的IP进行SYN+ACK的重试。实际上如果S的TCP/IP栈不够强大,最后的结果往往是堆栈溢出崩溃---即使S的系统足够强大,S也将忙于处理攻击者伪造的TCP连接请求而无暇理睬客户的正常请求(毕竟C的正常请求比率非常之小),此时从正常客户的角度看来,S失去响应,这种情况我们称作:服务器端受到了SYN Flood攻击(SYN洪水攻击)。  

以上的例子常被称作DoS(拒绝服务攻击)与DDoS(分布式拒绝服务攻击) 

注意:其中这儿的C和S都是相对的,对于现在的计算机来讲,只要自己的计算机建立任一服务,在一定情况下都可被称为S 
posted @ 2009-07-01 11:10 newstar 阅读(272) | 评论 (0)编辑 收藏
 
  1 #include <sys/cdefs.h>;
  2 #include <string.h>;
  3 
  4 /*
  5 * sizeof(word) MUST BE A POWER OF TWO
  6 * SO THAT wmask BELOW IS ALL ONES
  7 */
  8 typedef    int word;        /* "word" used for optimal copy speed */
  9 
 10 #define    wsize    sizeof(word)
 11 #define    wmask    (wsize - 1)
 12 
 13 /*
 14 * Copy a block of memory, handling overlap.
 15 * This is the routine that actually implements
 16 * (the portable versions of) bcopy, memcpy, and memmove. 
 17 * length 以Byte作为度量单位
 18 */
 19 #ifdef MEMCOPY
 20 void *
 21 memcpy(dst0, src0, length)
 22 #else
 23 #ifdef MEMMOVE
 24 void *
 25 memmove(dst0, src0, length)
 26 #else
 27 void
 28 bcopy(src0, dst0, length)
 29 #endif
 30 #endif
 31     void *dst0;
 32     const void *src0;
 33     register size_t length;
 34 {
 35     register char *dst = dst0;
 36     register const char *src = src0;
 37     register size_t t;
 38 
 39     if (length == 0 || dst == src)        /* nothing to do */
 40         goto done;
 41 
 42     /*
 43      * Macros: loop-t-times; and loop-t-times, t>;0
 44      */
 45 #define    TLOOP(s) if (t) TLOOP1(s)
 46 #define    TLOOP1(s) do { s; } while (--t)
 47 
 48     if ((unsigned long)dst < (unsigned long)src) {
 49         /*
 50          * Copy forward.
 51          */
 52         t = (int)src;    /* only need low bits */
 53                 /*这样做的目的是由于下面的TLOOP(*(word *)dst = *(word *)src; src += wsize; dst += wsize)拷贝用的是32位为一个单位
 54                  *所以 这是的指针所指向的地址是最后两位是00(这个想法我还没验证)所以在匹配之前一定要将DES 和 SRC指针对齐到最后两位为00才行
 55                  */
 56         if ((t | (int)dst) & wmask) {  // 如果源和目标地址的最后两位不是00的话
 57             /* 对齐操作数???   
 58              * Try to align operands.  This cannot be done
 59              * unless the low bits match.
 60              */
 61             if ((t ^ (int)dst) & wmask || length < wsize)   
 62                 t = length;               //如果目标和源的地址最后两位参差不齐如 11 10 只能以Byte为单位拷贝
 63             else
 64                 t = wsize - (t & wmask);  //如果目标和源的地址最后两位如 10 10相等的话 把他们同时移到00来做 
 65             length -= t;
 66             TLOOP1(*dst++ = *src++);
 67         }
 68         /*
 69          * Copy whole words, then mop up any trailing bytes.
 70          */
 71         t = length / wsize;
 72         TLOOP(*(word *)dst = *(word *)src; src += wsize; dst += wsize);
 73         t = length & wmask;
 74         TLOOP(*dst++ = *src++);
 75     } else {
 76         /*
 77          * Copy backwards.  Otherwise essentially the same.
 78          * Alignment works as before, except that it takes
 79          * (t&wmask) bytes to align, not wsize-(t&wmask).
 80          */
 81         src += length;
 82         dst += length;
 83         t = (int)src;
 84         if ((t | (int)dst) & wmask) {
 85             if ((t ^ (int)dst) & wmask || length <= wsize)
 86                 t = length;
 87             else
 88                 t &= wmask;
 89             length -= t;
 90             TLOOP1(*--dst = *--src);
 91         }
 92         t = length / wsize;
 93         TLOOP(src -= wsize; dst -= wsize; *(word *)dst = *(word *)src);
 94         t = length & wmask;
 95         TLOOP(*--dst = *--src);
 96     }
 97 done:
 98 #if defined(MEMCOPY) || defined(MEMMOVE)
 99     return (dst0);
100 #else
101     return;
102 #endif
103 }

BSD的memcpy是经过优化的代码,主要是从SRC到DES的赋值操作时,使用了WORD(也就是INT)型指针,每次拷贝32位。他正好符合CACHE中32位的原则,效率比较高。大概是8位赋值的效率的好几倍。
   但是计算机架构中,数据项只能存在于于地址是数据项的大小的整数倍上,如DOUBLE型只能存在于8的整数倍如8008而不能存在于1006的地址上,如果跨界存取就有可能使原子数据项跨越一个页或CACHE的边界,不但会影响拷贝性能,严重时还会产生BUS ERROR(core dumped)的错误,所以在使用WORD指针前一定要将DES和SRC指针对齐到被4(sizeof(int) = 4 对于32位系统而言) 整除的位置。但如果DES和SRC的最后两位不相等的话,不管怎么移都不可能保证DES和SRC指针移动相等的长度后都可以被4整除,所以这时只能采用每8位拷贝一次,只能采用CHAR 型指针。
posted @ 2009-07-01 10:41 newstar 阅读(692) | 评论 (0)编辑 收藏
 
一个定义为volatile的变量是说这变量可能会被意想不到地改变,这样,编译器就不会去假设这个变量的值了。精确地说就是,优化器在用到这个变量时必须每次都小心地重新读取这个变量的值,而不是使用保存在寄存器里的备份。下面是volatile变量的几个例子: 
    1). 并行设备的硬件寄存器(如:状态寄存器) 
    2). 一个中断服务子程序中会访问到的非自动变量(Non-automatic variables) 
    3). 多线程应用中被几个任务共享的变量 
    回答不出这个问题的人是不会被雇佣的。我认为这是区分C程序员和嵌入式系统程序员的最基本的问题。嵌入式系统程序员经常同硬件、中断、RTOS等等打交道,所用这些都要求volatile变量。不懂得volatile内容将会带来灾难。 
    假设被面试者正确地回答了这是问题(嗯,怀疑这否会是这样),我将稍微深究一下,看一下这家伙是不是直正懂得volatile完全的重要性。 
    1). 一个参数既可以是const还可以是volatile吗?解释为什么。 
    2). 一个指针可以是volatile 吗?解释为什么。 
    3). 下面的函数有什么错误: 
         int square(volatile int *ptr) 
         { 
              return *ptr * *ptr; 
         } 
    下面是答案: 
    1). 是的。一个例子是只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。 
    2). 是的。尽管这并不很常见。一个例子是当一个中服务子程序修该一个指向一个buffer的指针时。 
    3). 这段代码的有个恶作剧。这段代码的目的是用来返指针*ptr指向值的平方,但是,由于*ptr指向一个volatile型参数,编译器将产生类似下面的代码: 
    int square(volatile int *ptr)  
    { 
         int a,b; 
         a = *ptr; 
         b = *ptr; 
         return a * b; 
     } 
    由于*ptr的值可能被意想不到地该变,因此a和b可能是不同的。结果,这段代码可能返不是你所期望的平方值!正确的代码如下: 
     long square(volatile int *ptr)  
     { 
            int a; 
            a = *ptr; 
            return a * a; 
     } 
讲讲我的理解: (欢迎打板子...~~!) 

关键在于两个地方:      
  
1. 编译器的优化  (请高手帮我看看下面的理解) 

在本次线程内, 当读取一个变量时,为提高存取速度,编译器优化时有时会先把变量读取到一个寄存器中;以后,再取变量值时,就直接从寄存器中取值; 

当变量值在本线程里改变时,会同时把变量的新值copy到该寄存器中,以便保持一致 

当变量在因别的线程等而改变了值,该寄存器的值不会相应改变,从而造成应用程序读取的值和实际的变量值不一致 

当该寄存器在因别的线程等而改变了值,原变量的值不会改变,从而造成应用程序读取的值和实际的变量值不一致  


举一个不太准确的例子:  

发薪资时,会计每次都把员工叫来登记他们的银行卡号;一次会计为了省事,没有即时登记,用了以前登记的银行卡号;刚好一个员工的银行卡丢了,已挂失该银行卡号;从而造成该员工领不到工资  

员工 -- 原始变量地址  
银行卡号 -- 原始变量在寄存器的备份  


2. 在什么情况下会出现(如1楼所说) 

    1). 并行设备的硬件寄存器(如:状态寄存器)  
    2). 一个中断服务子程序中会访问到的非自动变量(Non-automatic variables)  
    3). 多线程应用中被几个任务共享的变量  
     

补充: volatile应该解释为“直接存取原始内存地址”比较合适,“易变的”这种解释简直有点误导人;  

“易变”是因为外在因素引起的,象多线程,中断等,并不是因为用volatile修饰了的变量就是“易变”了,假如没有外因,即使用volatile定义,它也不会变化; 

而用volatile定义之后,其实这个变量就不会因外因而变化了,可以放心使用了; 大家看看前面那种解释(易变的)是不是在误导人 


------------简明示例如下:------------------ 

volatile关键字是一种类型修饰符,用它声明的类型变量表示可以被某些编译器未知的因素更改,比如:操作系统、硬件或者其它线程等。遇到这个关键字声明的变量,编译器对访问该变量的代码就不再进行优化,从而可以提供对特殊地址的稳定访问。 
使用该关键字的例子如下: 
int volatile nVint; 
>>>>当要求使用volatile 声明的变量的值的时候,系统总是重新从它所在的内存读取数据,即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存。 
例如: 
volatile int i=10; 
int a = i; 
... 
//其他代码,并未明确告诉编译器,对i进行过操作 
int b = i; 
>>>>volatile 指出 i是随时可能发生变化的,每次使用它的时候必须从i的地址中读取,因而编译器生成的汇编代码会重新从i的地址读取数据放在b中。而优化做法是,由于编译器发现两次从i读数据的代码之间的代码没有对i进行过操作,它会自动把上次读的数据放在b中。而不是重新从i里面读。这样以来,如果i是一个寄存器变量或者表示一个端口数据就容易出错,所以说volatile可以保证对特殊地址的稳定访问。 
>>>>注意,在vc6中,一般调试模式没有进行代码优化,所以这个关键字的作用看不出来。下面通过插入汇编代码,测试有无volatile关键字,对程序最终代码的影响: 
>>>>首先,用classwizard建一个win32 console工程,插入一个voltest.cpp文件,输入下面的代码: 
>> 
#i nclude <stdio.h> 
void main() 

int i=10; 
int a = i; 
printf("i= %d",a); 
//下面汇编语句的作用就是改变内存中i的值,但是又不让编译器知道 
__asm { 
mov dword ptr [ebp-4], 20h 

int b = i; 
printf("i= %d",b); 
}       
然后,在调试版本模式运行程序,输出结果如下: 
i = 10 
i = 32 
然后,在release版本模式运行程序,输出结果如下: 
i = 10 
i = 10 
输出的结果明显表明,release模式下,编译器对代码进行了优化,第二次没有输出正确的i值。下面,我们把 i的声明加上volatile关键字,看看有什么变化: 
#i nclude <stdio.h> 
void main() 

volatile int i=10; 
int a = i; 
printf("i= %d",a); 
__asm { 
mov dword ptr [ebp-4], 20h 

int b = i; 
printf("i= %d",b); 
}       
分别在调试版本和release版本运行程序,输出都是: 
i = 10 
i = 32 
这说明这个关键字发挥了它的作用! 

------------------------------------ 


volatile对应的变量可能在你的程序本身不知道的情况下发生改变 
比如多线程的程序,共同访问的内存当中,多个程序都可以操纵这个变量 
你自己的程序,是无法判定合适这个变量会发生变化 
还比如,他和一个外部设备的某个状态对应,当外部设备发生操作的时候,通过驱动程序和中断事件,系统改变了这个变量的数值,而你的程序并不知道。 
对于volatile类型的变量,系统每次用到他的时候都是直接从对应的内存当中提取,而不会利用cache当中的原有数值,以适应它的未知何时会发生的变化,系统对这种变量的处理不会做优化——显然也是因为它的数值随时都可能变化的情况。 

-------------------------------------------------------------------------------- 

典型的例子 
for ( int i=0; i<100000; i++); 
这个语句用来测试空循环的速度的 
但是编译器肯定要把它优化掉,根本就不执行 
如果你写成  
for ( volatile int i=0; i<100000; i++); 
它就会执行了 

volatile的本意是“易变的”  
由于访问寄存器的速度要快过RAM,所以编译器一般都会作减少存取外部RAM的优化。比如: 

static int i=0; 

int main(void) 

... 
while (1) 

if (i) dosomething(); 



/* Interrupt service routine. */ 
void ISR_2(void) 

i=1; 


程序的本意是希望ISR_2中断产生时,在main当中调用dosomething函数,但是,由于编译器判断在main函数里面没有修改过i,因此 
可能只执行一次对从i到某寄存器的读操作,然后每次if判断都只使用这个寄存器里面的“i副本”,导致dosomething永远也不会被 
调用。如果将将变量加上volatile修饰,则编译器保证对此变量的读写操作都不会被优化(肯定执行)。此例中i也应该如此说明。 

一般说来,volatile用在如下的几个地方: 

1、中断服务程序中修改的供其它程序检测的变量需要加volatile; 

2、多任务环境下各任务间共享的标志应该加volatile; 

3、存储器映射的硬件寄存器通常也要加volatile说明,因为每次对它的读写都可能由不同意义; 

另外,以上这几种情况经常还要同时考虑数据的完整性(相互关联的几个标志读了一半被打断了重写),在1中可以通过关中断来实 
现,2中可以禁止任务调度,3中则只能依靠硬件的良好设计了。 
posted @ 2009-07-01 10:20 newstar 阅读(177) | 评论 (0)编辑 收藏
仅列出标题