Saturday, July 17, 2004

 

Some C++ interview questions - 5

I.
Write a program whose printed output is an exact copy of the source. Needless
to say, merely echoing the actual source file is not allowed.

1.
“打印自身的程序”杂谈
By 撰文/葛永
From CSDN 5/2004

“写一个程序,其执行结果是把程序自身打印出来。”
这个论题我在网上看到过若干次,不过真正意义上
的回答却从来没看见过。学过计算理论的高手们应该都
知道答案,但是大多数程序员可能没有精力去啃理论书
籍,就让我对这个有趣的命题来做个介绍吧。
首先要澄清:什么是“打印”,什么是“自身”,以
及程序执行环境有哪些限制。
对“打印”可以有各种理解,比如向屏幕输出、向
磁盘输出、向打印机输出、向内存输出,但本质上
都是一样的。
对“自身”的一种理解是源程序,另一种理解是机
器码。提到“机器码”这个名词,你可能立刻就想到了
“病毒”了吧?对,病毒就是最典型的自我打印程序,病
毒的起源“磁芯大战”就是从各个程序在存储器中复制
自己抢地盘,发展到现在更是丰富多彩,从传统的文件
到时髦的Email,病毒抢网络带宽,抢磁盘容量,抢内
存空间,删除其它文件,破坏操作系统,无所不用
其极。
但是各种病毒型的自打印程序都有一个限制,即需
要宿主系统提供的服务才能完成关键的“得到自己”的
动作。如果自身代码在内存中,如何才能知道其起始地
址呢?问操作系统吧。或者读取指令指针的值再做调整,
这其实也是利用了执行环境之一的“指令指针”。又如邮
件病毒,甚至不需要知道自己在哪里,只要调用软件的
“转发”接口就行了。作为病毒当然是不错的构思,但是
要作为“打印自身”的题解,显然就是耍赖皮了。推向
极端,操作系统提供一个“把我自己打出来”的API,程
序调用一下不就完了?
因此,限定程序的执行环境是讨论问题的必要前提。
现代计算机和操作系统的“外部环境”实在太复杂了,搬
出图灵机理论在这里也不太适合,干脆就这么定义命
题:使用某种高级语言(比如说C语言),除了屏幕输出
(如printf函数)以外不得使用其他系统相关函数和IO函
数,打印出程序自身的源代码。虽说这种定义细究下去
也有许多含糊的地方(比如,C语言规定全局变量的初
值会自动赋为零值,这个特性就不应该被允许),我们还
是把它抛到一边,赶紧进入正题吧。
为了简化讨论,我们假设有一种智能的PRINT语
句,所谓智能就是说,看到语句PRINT X时,程序会自
动根据X的类型按照常规把X的内容打出来,还有就是
可以随着我们讨论的进行它可以自动获得我们希望它有
的特性,这样我就不用一上来就很突兀地给它定义很多
特性。
好,不管怎样,程序里一定是会有一句打印语句的:
PRINT X [1]
执行后屏幕上就出现了X的内容。
为了满足“打印自身”的要求,必定还有一句把上
面那句中的“PRINT”给打出来:
PRINT Y [2]
最简单的当然是写成这样:
PRINT PRINT X
这里,第一个PRINT自动认出了后面的是一个字符
串常量,将之打印出来。
我想,你一定意识到了,这样做是行不通的,因为
每次都会多出一个PRINT,这样下去就陷入了无限。
[花絮]
如果允许无限长的程序话,倒真是可以这么写程序:
PRINT
PRINT PRINT
PRINT PRINT PRINT
......

第一个PRINT因为没有参数,所以什么也不打。还有
一种特殊的程序是“空”,就是一句话也没有的程序。呵
呵,这篇文章以趣味性为主,千万不要找我抬杠哟。
因此,[2]中的Y必然不能是常量,而是间接引用的变
量。或者说就是一段存储,里边放着一个串“PRINT”,
后面跟着X的内容。给这段存储起个名字叫做S,类型
是字符串,这样,[2]就成为:
PRINT S [3]
现在[1]已经由[3]打印出来了,[3]又由谁来打印呢?只
有[1]了。于是,我们的程序变成:
PRINT PRINT S [4]
PRINT S [5]
虽然看上去有循环依赖的嫌疑,但是关键点在于,
[5]是个间接打印,只是把某个固定起始地址的串发送到
屏幕上,是个完全固定的操作,并不依赖于其他语句!
更进一步,[5]也不一定非要是PRINT语句不可,可以换
成任何固定的对S的操作序列,而[4]只需要把[5]的语
句原汁原味打印出来就可以了:
PRINT A(S) B(S) C(S) [6]
A(S) B(S) C(S) [7]
[6][7]就是解决“自我打印”的基本方案。也许并不
是非常明显,让我对它做一个特殊的解释就清楚了。
假定S不是普通内存,而是字符模式下的“显存”,
也就是里边有什么字符屏幕上就会出现什么字符;而A
(S) B(S) C(S)是作用在字符串S上的一连串操作代码,
对S操作完成后S的新值成为 PRINT S [换行] S。在这
种解释下,[6][7]就是一个“自我打印”程序。
紧接着我们用一个简单的技巧把“显存”给干掉:
S=A(S) B(S) C(S) [8]
A(S) B(S) C(S) [9]
[8]不直接打印到屏幕,而是打印到字符串S。[9]中,
A(S) B(S) C(S)把S变换为 'S'={S} [换行] {S}(其中'S'
指单个字符S,{S}指S的内容),然后在屏幕上打印出S。
这就是“打印自身”的一个解的模式,可以适用于
任何高级语言。如果把A(S) B(S) C(S)具体写出来的话,
就是这样的伪码:
S= S="S="+{S}+"\n"+{S} PRINT S [10]
S="S="+{S}+"\n"+{S} PRINT S [11]
当然这个写法中的语法是需要“灵活理解”的,如
果真的要用现实的编程语言来写的话,还有许多细节要
处理。文章最后附有一个我用C语言写的程序,有兴趣
的话可以自行分析。核心思想就是[10][11],只是用了很多
技巧来处理字符。
主题内容讲完了,接下来就是杂谈了。
其实,如果用自然语言来描述程序的思想,其实可
以写成这样:
把下面这个字符串抄两遍,并且在第二句上加上引号。
“把下面这个字符串抄两遍,并且在第二句上加上引号。”
之所以要用两句话,是因为程序语言中没有“把我
自己抄一遍”的对应物。抽象的“自我指称”可是很危
险的东西哟,“罗素悖论”就是这么来的。
一个很迷惑人的观点是,机床比螺丝复杂,汽车厂
比汽车复杂,创造者要比被创造者复杂。而生命是可以
自我复制的(繁殖),因此生命无法用机械原理来理解。
假如是在1950年(DNA是1953年发现的),你该如何反驳
呢?我们的“自我打印”程序证明了,“创造者要比被创
造者复杂”是错误的。我们的程序加以扩展,可以携带
任意的信息,执行任意额外的动作,而仍可以完全复制
自身,这就是计算理论中的“递归定理”。二十世纪三四
十年代,在现代电子计算机还没有诞生的时候,计算理
论的先行者图灵、丘奇、哥德尔等就已经解决了“什么
是计算”、“什么是可计算的”等深刻的问题。我们这些
现代的程序员,在解决了“编程技巧”、“项目管理”等
吃饭相关的问题之余,如果不花点时间去领略一下计算
理论的美丽与神奇,不是太可惜了吗?
附:“打印自身”的C语言程序,其中的注释和#if
0 / #endif 中的文字是帮助阅读的,并不是代码的一部
分,也不会被打印出来。
#include
char buf[100][1000];
int cur=-1;
void P1(char *p)
{ sprintf(buf[++cur],p); //record p to buf
}
void P2(char *p) {
{ printf(p); //print p and change line
putchar(10);
}

void P3()
{
int i;
for(i=0;i<=cur;i++)
{
putchar(80);putchar(49);
putchar(40);putchar(34);
printf(buf[i]);putchar(34);
putchar(41);putchar(59);
putchar(10);
}
for(i=0;i< cur;i++)
{
putchar(80);putchar(50);
putchar(40);putchar(34);
printf(buf[i]);putchar(34);
putchar(41);putchar(59);
putchar(10);
}
printf(buf[cur]);putchar(10);
putchar(125);putchar(10);
}
void main()
{
P1("#include ");
P1("char buf[100][1000]; int cur=-1;");
P1("void P1(char *p) {sprintf(buf[++cur],p);}");
P1("void P2(char *p) { printf(p); putchar(10);}");
//以下打印一个很长的字串,其内容为程序代码
P1("void P3() {
int i;
for(i=0;i<=cur;i++)
{
putchar(80);putchar(49);
putchar(40);putchar(34);
printf(buf[i]);putchar(34);
putchar(41);putchar(59);
putchar(10);
}
for(i=0;i< cur;i++)
{
putchar(80);putchar(50);
putchar(40);putchar(34);
printf(buf[i]);putchar(34);
putchar(41);putchar(59);
putchar(10);
}
printf(buf[cur]);
putchar(10);
putchar(125);
putchar(10);
}");
P1("void main() {");
P1("P3();");
P2("#include ");
P2("char buf[100][1000]; int cur=-1;");
P2("void P1(char *p) {sprintf(buf[++cur],p);}");
P2("void P2(char *p) { printf(p); putchar(10);}");
//以下打印一个很长的字串,其内容为程序代码
P2("void P3() {
Int i;
for(i=0;i<=cur;i++)
{
putchar(80);putchar(49);
putchar(40);putchar(34);
printf(buf[i]);putchar(34);
putchar(41);putchar(59);
putchar(10);
}
for(i=0;i< cur;i++)
{
putchar(80);putchar(50);
putchar(40);putchar(34);
printf(buf[i]);putchar(34);
putchar(41);putchar(59);
putchar(10);
}
printf(buf[cur]);
putchar(10);
putchar(125);
putchar(10);
}");
P2("void main() {");
P3();
}
#if 0 //read P3() convinently
void P3()
{
int i;
for(i=0;i<=cur;i++)
{
putchar(80); //'P'
putchar(49); //'1'
putchar(40); //'('
putchar(34); //'"'
printf(buf[i]);
putchar(34); //'"'
putchar(41); //')'
putchar(59); //';'
putchar(10); //'\n'
}
for(i=0;i< cur;i++)
{
putchar(80); //'P'
putchar(50); //'2'
putchar(40); //'('
putchar(34); //'"'
printf(buf[i]);
putchar(34); //'"'
putchar(41); //')'
putchar(59); //';'
putchar(10); //'\n'
}
printf(buf[cur]); //for P3();
putchar(10);
putchar(125); //'}'
putchar(10);
}
#endif
注意:
为便于读者阅读,文中很长的字串被回车键分开了,读者在敲入这
些字串时请不要加入回车而连续输入,否则将无法编译通过(因为
C/C++不允许在字串当中换行),这部分代码以斜体标出。

2.
在 ld (昵称) 的大作中提到: 】
: 转载
: main(_){printf(_,34,_="main(_){printf(_,34,_=%c%s%c,34);}",34);}
: 【 在 oOOo (\_/o!o\_/) 的大作中提到: 】
: : a small program i wrote years ago, hope it still works with today's compiler
: : #include
: : char*temp[3]={
: : "#include",
: : "char*temp[3]={",
: : "main(){cout<< temp[0]<< endl<< temp[1]<< endl<< char(34)
: : << temp[0]<< char(34)<< char(44)<< endl<< char(34)
: : << temp[1]<< char(34)<< char(44)<< endl<< char(34)
: : << temp[2]<< char(34)<< char(125)<< char(59)<< endl
: : << endl<< temp[2]<< char(59)<< char(125)<< endl"};
: : main(){cout<< temp[0]<< endl<< temp[1]<< endl<< char(34)
: : << temp[0]<< char(34)<< char(44)<< endl<< char(34)
: : << temp[1]<< char(34)<< char(44)<< endl<< char(34)
: : << temp[2]<< char(34)<< char(125)<< char(59)<< endl
: : << endl<< temp[2]<< char(59)<< char(125)<< endl;}


--
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 67.124.]

II.

循环??负担??
From http://www.allaboutprogram.com

循环本身也是一个很大的开销,尤其是当循环体本身的运行速度很快的时候。这里讨论了一些避免额外开销的方式。

循环,不夸张地说,是每个程序员每天都要遇到的。作为结构化编程的三个主要结构之一,循环出现在每一个软件项目的几乎每一个源程序里。当一件事被放入循环的时候,就表明这件事可能会被做很多次,这也使得循环往往是优化的最佳位置。

很少有人想过,循环本身也是一个很大的开销。尤其是当循环体本身的运行速度很快的时候。譬如说,下面这个函数,可能每个人都曾经写过:

以下是代码:
int search( const int* pi, int iSize, int iValue )
{
for ( int i = 0; i < iSize; ++i )
if ( pi[ i ] == iValue )
return i;
return -1;
}

这个函数用来在一个整型数组里查找第一个与给定值相等的整数的索引值。如果我们把这个函数用更直接(对编译器来说)的方法写出来,可能是

以下是代码:
int expanded_search( const int* pi, int iSize, int iValue )
{
int i = 0;
goto judge;
loop:
if ( pi[ i ] == iValue )
return i;
judge:
++i;
if ( i < iSize )
goto loop;
return -1;
}

请注意,循环代码本身和循环体几乎消耗了相同的时间。也就是说,如果我们能够避免这种循环方式(循环本身是不可能避免的)的话,我们可以获得几乎100%的速度提升。Ronald E. Knuth在他的巨著The Art of Computer Programming中提到了这样一种方法:

以下是代码:
int guard_search( int* pi, int iSize, int iValue )
{
int* p = pi;
p[ iSize ] = iValue;
while ( *p != iValue )
++p;
return p == pi + iSize ? -1 : p - pi;
}

与其它方法相比,唯一的要求是:供搜索的数组最后必须有一个元素是空的。这在实际程序里非常容易实现,尤其是在需要以此来换取执行速度的情况下。从测试结果(如下)可以看到,优化的效果相当显著。

search :380
expanded_search :371
guard_search :190

有的时候,你没有办法实现设定一个守护(guard)变量,或者你无法提供那个最后的空元素。例如下面的这个函数:

以下是代码:
void assign( int* piDest, const int* piSrc, int iSize )
{
for ( int i = 0; i < iSize; ++i )
*piDest++ = *piSrc++ + 1;
}

在这种情况下,Knuth算法就不能使用了。这时,我们可以使用Duff's Device----由Duff提出了一个算法。修改后的函数如下:

以下是代码:
void duff_assign( int* piDest, const int* piSrc, int iSize )
{
int i;
switch ( iSize % 4 )
{
case 0:
for ( i = 0; i < iSize / 4; ++i )
{
*piDest++ = *piSrc+++1;
case 1:
*piDest++ = *piSrc+++1;
case 2:
*piDest++ = *piSrc+++1;
case 3:
*piDest++ = *piSrc+++1;
}
}
}

可以看到,这个函数非常"丑陋",第一眼看上去,甚至怀疑它是否能通过编译。事实上,这是对C/C++语法的一种"特殊"使用方式,其主要目的是,减少在循环里的跳转和判断,以在每次循环执行时循环体获得更多的比重。

测试结果如下:

不使用Duff's Device:10235
使用Duff's Device:9263

提高了大约10%,虽然不多,但是如果能通过这样简单的改动,就可以使核心代码执行效率提高的话,也是很值得的。

III.
重载,覆盖和隐藏

那就再说一遍吧,呵呵,也算自己复习。

1.
重载,称overload,指在同一类中,函数名相同的函数。由不同的参数决定调用那个函数。函数可要不可要Virtual关键字。和全局函数同名的函数不叫重载。如果在类中调用同名的全局函数,必须用全局引用符号::引用。

2.
覆盖是指派生类函数覆盖基类函数,称override、redefine。条件是

函数名相同;

参数相同;(注意:C++标准允许返回值不同的情况,但是很少编译器支持这个)

基类函数必须有Virtual关键字;

3.
隐藏,称hide,是指派生类屏蔽了基类的同名函数

3.1. 函数名相同,但参数不同,此时不论基类有无Virtual关键字,基类函数将被隐藏。
3.2. 函数名相同,参数也相同,但基类无Virtual关键字(有就是覆盖),基类函数将被隐藏。

重要的是隐藏之后,派生类无法call基类的同名函数,这一点C++与Java不同。Java没有hide的概念。hide的目的主要是阻止不正确的类型转化。C#等.Net语言支持hide。

C++并不能禁止在子类中改写(这里确实不好描述,只好用这么一个词)一个函数。即使是被声明为private virtual的函数也可以被改写。但是严格意义上,这不能称为overload,因为两者在不同的scope。

4.
忠告:

4.1 尽量不要overload virtual function,否则每个派生类都要写一边所有的overloaded funciton,太累。
4.2 S. Meyers. Effective C++: 50 Specific Ways to Improve Your Programs and Design, 2nd edition (Addison-Wesley, 1998); Item 37: "Never redefine an inherited non-virtual function."

IV.
A C++ Constructor Question

发信人: arya (死火山下), 信区: Programming
标 题: Re: A C++ Constructor Question
发信站: Unknown Space - 未名空间 (Wed May 25 01:36:21 2005), 转信

The latter is not a form of constructor in C++. Instead it is a form of
declaration of a function accepting no arguments and returning a B object.
【 在 haveagoodday (Offer) 的大作中提: 】
: What is the difference between:
: B b;
: and
: B b();
: where B is a class name?
: Thanks.

V.
New Cast Operators

From http://www.informit.com/guides/printerfriendly.asp?g=cplusplus&seqNum=134&rl=1

Last updated May 26, 2005.
New Cast Operators
Originally, the C++ standardization committee wanted to deprecate C-style casting, thereby enforcing the use of the new cast operators exclusively. However, because C-style casts are widely used in legacy code and because many C++ compilers serve as C compilers, the committee decided against doing so. That said, C++ programmers are encouraged to use the new cast operators.

Before I present these operators, let's see why C-style cast has fallen out of favor. Consider the following code listing:

void *p=&x;
int n=(int)p; //C-style cast The C-style cast seems harmless at first sight. Yet, it has several potential dangers. First, it performs different operations in different contexts. For example, it may perform a safe int to double promotion, but it can also perform inherently dangerous operations such as casting void* to a numeric value (as in the example above). The programmer can't always tell from the source code if the cast is safe or inherently dangerous.

Worse, a C-style cast may perform multiple operations at once. In the following example, not only does it cast char * to unsigned char *, but it also removes the const qualifier at the same time:

const char *msg="don't touch!";
unsigned char *p=(unsigned char*) msg; // intentional?Again, you cannot tell whether this was the programmer's intention or an oversight.

The New Cast Operators
The ailments of C-style cast have been known for years. C++ offers a superior alternative in the form of new cast operators. They document the programmer's intent more clearly while preserving the compiler's ability to catch potential bugs like the ones shown above. C++ has four new cast operators:

static_cast
const_cast
reinterpret_cast
dynamic_castThe dynamic_cast operator is unique, as it introduces new functionality that C-style cast doesn't support. I'll get to that momentarily.

static_cast
static_cast performs safe and relatively portable casts. For example, you use static_cast to explicitly document a cast that would otherwise take place automatically. Consider the following example:

bool b=true;
int n=static_cast (b);C++ automatically casts bool to int in this context so the use of static_cast in this case isn't necessary. However, by using it, programmers document their intention explicitly.

In other contexts, static_cast is mandatory. For example, when you cast void* to a different pointer type, as in the following example:

int n=4;
void *pv=&n;
int pi2 = static_cast (pv); //mandatorystatic_cast uses the information available at compile time to perform the required type conversion. Therefore, the target and the source might not be identical in their binary representation. Consider a float to int conversion. The binary representation of the floating number 10.0 is quite different from the equivalent integer value of 10. static_cast performs the necessary adjustments when casting one to the other.

The use of static_cast enables the compiler to catch programmers' mistakes such as this:

const char *msg="don't touch!";
unsigned char *p=
static_cast (msg); //errorHere the compiler issues an error message indicating that the cast operation attempts to remove the const qualifier of msg -- something that the programmer probably didn't intend anyway.

const_cast
The removal of const requires a special cast operator called const_cast. This operator may perform only the following operations:

Remove the const and or volatile qualification

Add const and or volatile qualification

For example

struct A
{
void func(){} // non-const member function
};

void f(const A& a)
{
a.func(); // error, calling a non-const function
}Clearly, this is a design mistake. The member function func() should have been declared const in the first place. However, such code does exist in third-party libraries; when innocent programmers try to use it, they have to resort to brute force casts. To overcome this problem, you may remove the const qualifier of a and then call func() as follows:

A &ref = const_cast (a); // remove const
ref.func(); // now fine Trying to perform any other conversion with const_cast will result a compilation error. Remember also that while const_cast may remove the const qualifier of an object, this doesn't mean that you're allowed to modify it. In fact, trying to modify a const object causes undefined behavior. Therefore, use const_cast cautiously when it is used for the removal of const or volatile.

reinterpret_cast
As opposed to static_cast, reinterpret_cast performs relatively dangerous and nonportable casts. reinterpret_cast doesn't change the binary representation of the source object. Therefore, it is often used in low-level applications that convert objects and other data to a stream of bytes (and vice versa). In the following example, reinterpret_cast is used to "cheat" the compiler, enabling the programmer to examine the individual bytes of a float variable:

float f=10;
unsigned char *p = reinterpret_cast (&f);
for (int j=0; j<4; ++j)
cout<< p[j]<< endl;The use of reinterpret_cast explicitly warns the reader that an unsafe (and probably a nonportable) conversion is taking place. When using reinterpret_cast, the programmer -- rather than the compiler -- is responsible for the results.

dynamic_cast
As previously said, dynamic_cast differs from all other three cast operators. You use it when the conversion must access the runtime type information of an object rather than its static type (for more information on static vs. dynamic typing, please refer to the "Runtime Type Information (RTTI)" section). Two common scenarios that necessitate the use of dynamic_cast are a downcast i.e., casting a base class pointer or reference to a pointer or reference of a derived class and a crosscast in which the programmer converts a multiply-inherited object to one of its secondary base classes.

Summary
C-style cast is neither safe nor explicit enough, as I have shown. It disables the compiler's type-safety checks, its syntactic form doesn't express the intended conversion clearly, and it cannot perform a dynamic cast. For all these reasons, you should avoid using it in new code.

Instead, use static_cast for safe and rather portable casts, const_cast to remove or add only the const/volatile qualifiers of an object, and reinterpret_cast for low-level, unsafe and nonportable casts. Use dynamic_cast for conversions that must access the dynamic type of an object and RTTI capability-queries.

VI.
·¢ÐÅÈË: xxxyyyzzz (2005 ÕÒµ½ºÃ¹¤×÷), ÐÅÇø: Programming
±ê Ìâ: Re: [תÔØ] C++ interview question :)
·¢ÐÅÕ¾: Unknown Space - δÃû¿Õ¼ä (Sat Apr 16 17:07:13 2005), תÐÅ


Circular buffer is especially useful to inter-* communications
Below is a simple circular buffer implemented by Stelian Pop for Linux
2.6. We can see the must have variables are

+struct kfifo {
+ unsigned int head;
+ unsigned int tail;
+ unsigned int size; //the size of the internal buffer.
+ unsigned int len; //the length of the data to be added.
+ spinlock_t lock;
+ unsigned char *buffer; //the data to be added.
+};

The spinlock here is a frequently neglected data members. However, to
guarantee the synchronization of the operations, it is essential.
However, there are lots of things to do beyond S. Pop's work if we want a
practical circular buffer. We at least have to
1) notify that the buffer is full
2) increase/decrease the buffer size if needed
3) clear the buffere if needed
......




Éñ°¡£¬¸øÎÒÒ»·ÝºÃ¹¤×÷°É£¡

¡¾ ÔÚ kreisler (little Kreisler) µÄ´ó×÷ÖÐÌáµ½: ¡¿
: ¡¾ ÒÔÏÂÎÄ×ÖתÔØ×Ô JobHunting ÌÖÂÛÇø,Ô­ÎÄÈçÏ ¡¿
: ·¢ÐÅÈË: arrows (¼ýЦ½­ºþ), ÐÅÇø: JobHunting
: ±ê Ìâ: C++ interview question :)
: ·¢ÐÅÕ¾: Unknown Space - δÃû¿Õ¼ä (Thu Apr 14 18:49:59 2005) WWW-POST
: in C++, implement a generic circular buffer class
: using array. Items can be added/removed at both ends
: of the buffer, and the buffer are able to double its
: size when it is full.
: What are the necessary data members of this class?
: What constructors do you have to write?
: Can you still implement the class with all the functions
: above, if pointer data member inside the class is not
: allowed? Why or why not?


Appendix A A circular buffer designed by Stelian Pop

--- /dev/null 2004-02-23 22:02:56.000000000 +0100
+++ linux-2.6/include/linux/kfifo.h 2004-09-13 14:58:37.000000000 +0200
@@ -0,0 +1,179 @@
+/*
+ * A simple kernel FIFO implementation.
+ *
+ * Copyright (C) 2004 Stelian Pop
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _LINUX_KFIFO_H
+#define _LINUX_KFIFO_H
+
+#ifdef __KERNEL__
+
+#include
+#include
+#include
+
+/*
+ * This is a simple FIFO implementation using a circular buffer.
+ */
+struct kfifo {
+ unsigned int head;
+ unsigned int tail;
+ unsigned int size;
+ unsigned int len;
+ spinlock_t lock;
+ unsigned char *buffer;
+};
+
+/*
+ * kfifo_alloc - allocates a new FIFO
+ * @size: the size of the internal buffer.
+ *
+ * Note that the allocation uses kmalloc(GFP_KERNEL).
+ */
+static inline struct kfifo *kfifo_alloc(unsigned int size) {
+ struct kfifo *fifo;
+
+ fifo = kmalloc(sizeof(struct kfifo), GFP_KERNEL);
+ if (!fifo)
+ return NULL;
+
+ fifo->buffer = kmalloc(size, GFP_KERNEL);
+ if (!fifo->buffer) {
+ kfree(fifo);
+ return NULL;
+ }
+
+ fifo->head = fifo->tail = 0;
+ fifo->size = size;
+ fifo->len = 0;
+ fifo->lock = SPIN_LOCK_UNLOCKED;
+
+ return fifo;
+}
+
+/*
+ * kfifo_free - frees the FIFO
+ * @fifo: the fifo to be freed.
+ */
+static inline void kfifo_free(struct kfifo *fifo) {
+ kfree(fifo->buffer);
+ kfree(fifo);
+}
+
+/*
+ * kfifo_reset - removes the entire FIFO contents
+ * @fifo: the fifo to be emptied.
+ */
+static inline void kfifo_reset(struct kfifo *fifo) {
+ unsigned long flags;
+
+ spin_lock_irqsave(&fifo->lock, flags);
+
+ fifo->head = fifo->tail = 0;
+ fifo->len = 0;
+
+ spin_unlock_irqrestore(&fifo->lock, flags);
+}
+
+/*
+ * kfifo_put - puts some data into the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: the data to be added.
+ * @len: the length of the data to be added.
+ *
+ * This function copies at most 'len' bytes from the 'buffer' into
+ * the FIFO depending on the free space, and returns the number of
+ * bytes copied.
+ */
+static inline unsigned int kfifo_put(struct kfifo *fifo,
+ unsigned char *buffer, unsigned int len) {
+ unsigned long flags;
+ unsigned int total, remaining;
+
+ spin_lock_irqsave(&fifo->lock, flags);
+
+ total = remaining = min(len, fifo->size - fifo->len);
+ while (remaining > 0) {
+ unsigned int l = min(remaining, fifo->size - fifo->tail);
+ memcpy(fifo->buffer + fifo->tail, buffer, l);
+ fifo->tail += l;
+ fifo->tail %= fifo->size;
+ fifo->len += l;
+ buffer += l;
+ remaining -= l;
+ }
+
+ spin_unlock_irqrestore(&fifo->lock, flags);
+
+ return total;
+}
+
+/*
+ * kfifo_get - gets some data from the FIFO
+ * @fifo: the fifo to be used.
+ * @buffer: where the data must be copied.
+ * @len: the size of the destination buffer.
+ *
+ * This function copies at most 'len' bytes from the FIFO into the
+ * 'buffer' and returns the number of copied bytes.
+ */
+static inline unsigned int kfifo_get(struct kfifo *fifo,
+ unsigned char *buffer, unsigned int len) {
+ unsigned long flags;
+ unsigned int total, remaining;
+
+ spin_lock_irqsave(&fifo->lock, flags);
+
+ total = remaining = min(len, fifo->len);
+ while (remaining > 0) {
+ unsigned int l = min(remaining, fifo->size - fifo->head);
+ memcpy(buffer, fifo->buffer + fifo->head, l);
+ fifo->head += l;
+ fifo->head %= fifo->size;
+ fifo->len -= l;
+ buffer += l;
+ remaining -= l;
+ }
+
+ spin_unlock_irqrestore(&fifo->lock, flags);
+
+ return total;
+}
+
+/*
+ * kfifo_len - returns the number of bytes available in the FIFO
+ * @fifo: the fifo to be used.
+ */
+static inline unsigned int kfifo_len(struct kfifo *fifo) {
+ unsigned long flags;
+ unsigned int result;
+
+ spin_lock_irqsave(&fifo->lock, flags);
+
+ result = fifo->len;

VII.
发信人: autumnrain (Daisy), 信区: JobHunting
标 题: Re: 另一个paypal面试题
发信站: BBS 未名空间站 (Sun Sep 11 00:56:49 2005)

(char)(char *)((int *)0 + 1)

【 在 hongyu70 (hongyu70) 的大作中提到: 】
: Given a computer and a compiler, how to test the length of the integer
: without using function like sizeof.



<< Home

This page is powered by Blogger. Isn't yours?