Apr
8
翻译自:How To Read C Declarations 英文原文
p.s. 以前还真没注意到这篇文章最后提到的vtable是啥意思……
就算是非常有经验的C程序员,也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说,下面这个是一个指针的数组,还是一个数组的指针?
下面这货到底是什么?
当然了,这货是一个指针,指向一个数组,这个数组的每个元素是一个指针,指向一个函数,函数的返回值类型是int :)
这篇短文希望能够教会你一个非常简单地读懂复杂声明的方法。我99%肯定我在80年代读过这篇,但是不记得具体是在什么地方读到的了。我怀疑是我自己发现这个的(尽管我总会被计算机语言结构和神秘的事物搞得很兴奋)。然而我的确记得,能够写出一个程序,将任何声明转换成英语。
== 黄金法则 ==
这个法则是这样说的:
最简单的情况是这样的:
从 i 开始,你向右看,啥都没看到;然后就向左看,看到了int,说出来:i是一个int。
然后看个复杂一点的:
从 a 开始:向右看,说“是一个包含3个元素的数组”;向左看,说“数组的每个元素是指针”;向右看,啥都没;向左看,说“指针指向int”。综合起来就是: a 是一个包含3个元素的数组,每个元素是一个指针,指向int。
加上一对括号让它看起来更怪异点儿:
像在普通表达式中一样,括号改变了阅读/计算的顺序。从 a 开始:向右看,遇到括号了,往回;向左看,说“是一个指针”,遇到(括号,跳出来;向右看,[3],说“指向一个包含3个元素的数组”;向左看,int,说“数组的每个元素是int”。综合起来:a是一个指针,指向一个包含3个元素的数组,数组的每个元素是一个int。
好,再来看看这个:
赞,你说:foo是一个函数,返回一个指针,指向int。
接下来跳一步:就像我们可以定义一个指向int的指针,我们也可以定义一个指向函数的指针。在这种情况下,不需要extern了(因为不是函数的前向引用声明),而是一个变量的定义。这是一个基本的函数指针:
从foo开始:向右看,遇到括号,往回;向左看,*,说“是一个指针”,遇到左括号,跳出来;向右看,(),说“指向一个函数”;向左看,int,说“函数返回int”。综合起来:foo是一个指针,指向一个函数,函数返回int。
下面是一个数组,每个元素是一个指针,指向函数,函数返回int:
你还需要最后一个,诡异的难以置信的声明:
这是一个指针,指向一个数组,数组的每个元素是个指针,指向一个函数,函数的返回值是int。发现了吗?这货就是上面那个object_vtable的指针,也就是你定义的每一个对象需要的虚函数表(vtable)的指针。
这个指向vtable的指针是一个vtable的地址,例如,&Truck_vtable (就是某个Truck类的实例虚函数表的指针)。
== 总结 ==
接下来的例子总结了所有C++为了实现多态性所建造的虚函数表需要的所有情形(就像最初的C Front - C++转C翻译器)。
p.s. 以前还真没注意到这篇文章最后提到的vtable是啥意思……
就算是非常有经验的C程序员,也对那些比简单数组/指针更复杂一些的声明感到头疼。比如说,下面这个是一个指针的数组,还是一个数组的指针?
int *a[10];
下面这货到底是什么?
int (*(*vtable)[])();
当然了,这货是一个指针,指向一个数组,这个数组的每个元素是一个指针,指向一个函数,函数的返回值类型是int :)
这篇短文希望能够教会你一个非常简单地读懂复杂声明的方法。我99%肯定我在80年代读过这篇,但是不记得具体是在什么地方读到的了。我怀疑是我自己发现这个的(尽管我总会被计算机语言结构和神秘的事物搞得很兴奋)。然而我的确记得,能够写出一个程序,将任何声明转换成英语。
== 黄金法则 ==
这个法则是这样说的:
引用
从标识符开始(或者最内层的结构,如果不存在标识符的话,通常出现于函数指针),首先向右看,直到遇到 ) 括号或者结束,看到什么就说出来;然后向左看,直到遇到 ( 括号或者回到行首,看到什么就说出来。跳出一层括号,重复上述过程:右看看,说出来;左看看,说出来。直到你说出变量的类型或者返回值(针对函数指针),也就表示你把声明都读完了。
最简单的情况是这样的:
int i;
从 i 开始,你向右看,啥都没看到;然后就向左看,看到了int,说出来:i是一个int。
然后看个复杂一点的:
int *a[3];
从 a 开始:向右看,说“是一个包含3个元素的数组”;向左看,说“数组的每个元素是指针”;向右看,啥都没;向左看,说“指针指向int”。综合起来就是: a 是一个包含3个元素的数组,每个元素是一个指针,指向int。
加上一对括号让它看起来更怪异点儿:
int (*a)[3];
像在普通表达式中一样,括号改变了阅读/计算的顺序。从 a 开始:向右看,遇到括号了,往回;向左看,说“是一个指针”,遇到(括号,跳出来;向右看,[3],说“指向一个包含3个元素的数组”;向左看,int,说“数组的每个元素是int”。综合起来:a是一个指针,指向一个包含3个元素的数组,数组的每个元素是一个int。
好,再来看看这个:
extern int *foo();
赞,你说:foo是一个函数,返回一个指针,指向int。
接下来跳一步:就像我们可以定义一个指向int的指针,我们也可以定义一个指向函数的指针。在这种情况下,不需要extern了(因为不是函数的前向引用声明),而是一个变量的定义。这是一个基本的函数指针:
int (*foo)();
从foo开始:向右看,遇到括号,往回;向左看,*,说“是一个指针”,遇到左括号,跳出来;向右看,(),说“指向一个函数”;向左看,int,说“函数返回int”。综合起来:foo是一个指针,指向一个函数,函数返回int。
下面是一个数组,每个元素是一个指针,指向函数,函数返回int:
int (*Object_vtable[])();
你还需要最后一个,诡异的难以置信的声明:
int (*(*vtable)[])();
这是一个指针,指向一个数组,数组的每个元素是个指针,指向一个函数,函数的返回值是int。发现了吗?这货就是上面那个object_vtable的指针,也就是你定义的每一个对象需要的虚函数表(vtable)的指针。
这个指向vtable的指针是一个vtable的地址,例如,&Truck_vtable (就是某个Truck类的实例虚函数表的指针)。
== 总结 ==
接下来的例子总结了所有C++为了实现多态性所建造的虚函数表需要的所有情形(就像最初的C Front - C++转C翻译器)。
int *ptr_to_int;
int *func_returning_ptr_to_int();
int (*ptr_to_func_returning_int)();
int (*array_of_ptr_to_func_returning_int[])();
int (*(*ptr_to_an_array_of_ptr_to_func_returning_int)[])();
int *func_returning_ptr_to_int();
int (*ptr_to_func_returning_int)();
int (*array_of_ptr_to_func_returning_int[])();
int (*(*ptr_to_an_array_of_ptr_to_func_returning_int)[])();
Jan
12
对于没有GC的语言来说,这实在是最让人头疼的事情了,毕竟内存泄漏是最难处理的问题(之一?),对于一个后台server,即使只是一个小小的泄漏,日积月累,也会导致灾难性的后果。有个传闻说的是,某公司的某下载软件的某后台server,由于有个无法定位的内存泄漏问题,导致服务的内存占用不断增加,以至于只能每隔一段时间重启之。
有人说,C/C++程序员有一半的工作量是花在处理内存泄漏上面,但是很遗憾,内存泄漏仍然屡见不鲜。一旦出现泄漏,能做的事情不多,上述处理方式是消极做法之一,有效,但治标不治本。积极一点的,也不外乎这两个:一是看代码,反复看代码,请别人看代码,请别人反复看代码;或是借助valgrind之类的工具来跟踪内存的分配/释放(而且并不适用于所有程序,例如某些程序寄希望于在其终止时让OS来释放那些只需申请一次且无需释放的内存)。一些额外的测试工作也许能帮助缩小查看代码的范围,但也只能这样了。
既是如此,在程序运行之前,就应该先把好关。
对于C语言,这确实是个比较痛苦的事情。毕竟C语言只是汇编的高级语言封装,语言本身提供的能力很有限。
假定有一个函数申请了多次内存,那么每次遇到错误需要退出的时候,为了避免内存泄漏,必须将其之前申请的所有内存都释放。所以你也许会看到或者写出过这样蛋疼的程序:
于是万恶的goto出场了。为了解决上面的问题,引入goto可以使得每个资源只需要写一份对应的释放代码,例如: 什么意思呢?假定在第一步,给 a 分配内存的时候失败了,那么还没来得及去定义 b 并给其初始化赋值,就跳转到了wtf这儿,而在wtf下面的第二行,却引用了 b 这个变量,对于编译器而言,这便无法处理了。正确的代码应该是:
对变量就近定义的好坏见仁见智了,但是goto毕竟不是个好东西,所以看过内核代码的同学可能会发现另外一种替代性的结构:do-while(0) 。乍一看这个结构似乎没有意义,有点奇怪,但是却很好用,很适合用来消除goto语句,例如上面的代码可以这么做:
但是do-while(0)和goto一样,不是万金油,对于很多较复杂的情况也不能很好的解决,甚至会使得程序更加晦涩难懂。对于do-while(0),如果在这个结构内还有一个循环,循环里面出错想要跳出do-while(0),break就不奏效了(至于为什么,你懂的),这时代码怎么写都恶心,只能羡慕Java里面的break label语法了;而对于比较复杂的资源,比如上文中申请到的内存是 a->b->c 这样嵌套的,那么如何安排内存释放代码,又要让人头疼了。合理的使用goto/do-while(0),将过长的代码拆分成多个函数等都可以起到一定的帮助。
只是很可惜,C语言的能力大概就只能走到这里了。想走得更远,就得借助C++来完成了。虽然C++没有gc,但是由于其OO的特性,使得RAII的实现变得可能。
所谓RAII,即 Resource Acquizition Is Initialization。很晦涩吧?其实具体实现很简单:把资源封装成一个类,在其构造函数中分配,在析构函数中释放。当需要使用的时候,在栈上初始化一个对象,当这个对象生命周期结束的时候,其析构函数会被调用,自动完成资源的释放。对于前面提到的例子,可以把A/B/C封装成一个class,对应的a/b/c就是实例化得到的三个对象,当func函数结束的时候,abc对应的内存就会被释放。同样的方法也适用于锁、互斥量、文件指针等其他类型的资源。下面这段代码以pthread_mutex为例,演示了RAII的使用:
不过程序中因为各种原因常需要使用 new 来分配资源(内存、对象等),这样对应的指针还是得在其生命周期结束的时候被释放,总不能为每一个指针再封装一个struct吧。幸而C++的泛型在这里又为RAII提供了绝佳的方法。实际上在第一版STL里面就包含了一个 auto_ptr 容器,实例化一个auto_ptr的时候可以赋予一个任意类型指针ptr(但是必须是使用new获得的,特别注意:new[]分配的不行),auto_ptr对象将ptr包装起来,并重载了 * 和 -> 两个操作符,使得该对象能像指针一样被使用,并且在该对象被生命周期的时候,其析构函数会delete ptr。 下面是auto_ptr的一个简单实现和使用:
既然说到auto_ptr,为什么不用它来写例子呢?因为auto_ptr的某些特性导致其有大坑,在很多地方不受待见,以至于在 c++11 标准里,auto_ptr被废弃了,因此不建议在项目中使用它了。有兴趣的同学可以去翻看《C++标准程序库》对auto_ptr的介绍。
本来计划写到这里要告一段落了,但是上面的 x_ptr 有坑,无奈只好继续……为什么说有坑呢?举两个例子:
针对func1的问题,可以通过私有化其拷贝函数、拷贝构造函数来禁止x_ptr的拷贝,代码如下
而针对func2的问题,解决方法呢,要么是写一个x_ptr_arr,使用delete[]来处理;要么是在x_ptr的构造函数里加一个flag,用来指定是否是new[]分配的,当然,为了方便,可以设置一个默认值false.....
补充一句,这里的x_ptr其实是boost::scoped_ptr的缩水版了,有兴趣的同学可以自行Google了解更多,关于内存泄漏的话题,这篇大概就说这么多了吧。
最后,感谢Sandy同学的 C++中利用RAII在stack上管理资源I ,本篇有多处参考该文。希望他能抽出时间把 II 给写完吧 :P
有人说,C/C++程序员有一半的工作量是花在处理内存泄漏上面,但是很遗憾,内存泄漏仍然屡见不鲜。一旦出现泄漏,能做的事情不多,上述处理方式是消极做法之一,有效,但治标不治本。积极一点的,也不外乎这两个:一是看代码,反复看代码,请别人看代码,请别人反复看代码;或是借助valgrind之类的工具来跟踪内存的分配/释放(而且并不适用于所有程序,例如某些程序寄希望于在其终止时让OS来释放那些只需申请一次且无需释放的内存)。一些额外的测试工作也许能帮助缩小查看代码的范围,但也只能这样了。
既是如此,在程序运行之前,就应该先把好关。
对于C语言,这确实是个比较痛苦的事情。毕竟C语言只是汇编的高级语言封装,语言本身提供的能力很有限。
假定有一个函数申请了多次内存,那么每次遇到错误需要退出的时候,为了避免内存泄漏,必须将其之前申请的所有内存都释放。所以你也许会看到或者写出过这样蛋疼的程序:
void func(){
void *a = malloc(sizeof(A));
if (NULL == a) {
return;
}
void *b = malloc(sizeof(B));
if (NULL == b) {
free(a);
return;
}
void *c = malloc(sizeof(C));
if (NULL == c) {
free(a);
free(b);
return;
}
......
}
有效,但是不靠谱。当这个函数长达数百行、有多处申请内存的时候,其可维护性是相当低的。当然,使用 alloca 这个非标准的内存分配函数可以在某些情况下解决问题,但是如果申请的内存较大(栈空间不够)、或者分配到的内存被用于较复杂的结构(比如还包含其他资源的指针)、资源不是内存(比如文件指针、锁等同样需要在生命周期结束被释放的资源),alloca就无能为力了。void *a = malloc(sizeof(A));
if (NULL == a) {
return;
}
void *b = malloc(sizeof(B));
if (NULL == b) {
free(a);
return;
}
void *c = malloc(sizeof(C));
if (NULL == c) {
free(a);
free(b);
return;
}
......
}
于是万恶的goto出场了。为了解决上面的问题,引入goto可以使得每个资源只需要写一份对应的释放代码,例如:
void func(){
void *a = malloc(sizeof(A));
if (NULL == a) goto wtf;
void *b = malloc(sizeof(B));
if (NULL == b) goto wtf;
void *c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
看起来很棒对不对?但是实际上并不能通过编译,gcc会提示类似这样的错误:void *a = malloc(sizeof(A));
if (NULL == a) goto wtf;
void *b = malloc(sizeof(B));
if (NULL == b) goto wtf;
void *c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
引用
cross.c:14: error: jump to label ‘wtf’
cross.c:9: error: from here
cross.c:11: error: crosses initialization of ‘void* c’
cross.c:9: error: from here
cross.c:11: error: crosses initialization of ‘void* c’
void func(){
void *a = NULL, *b = NULL, *c = NULL;
a = malloc(sizeof(A));
if (NULL == a) goto wtf;
b = malloc(sizeof(B));
if (NULL == b) goto wtf;
c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
这样一来便要求所有在 goto 之后被用到的变量都必须在第一个goto之前定义,并赋初值。这就类似c89/pascal的做法了,强制要求所有变量在函数的开头定义,失去了变量就近定义的便捷性和一些其他的好处(sandy的说法是“局部性”,但是窃以为变量的就近定义跟局部性关系不大,更多的是在C++中,对象的就近定义可以在一些情况下避免不必要的初始化,并且可能需要之前的一些处理结果)。这儿有个更复杂的例子,作者指出,在驱动/linux内核中大量使用了这种方式来释放资源。注意,稍有不同的是,这个例子有多种资源,函数末尾有多个label,按照资源申请顺序的倒序释放资源(为什么呢,看代码吧~)void *a = NULL, *b = NULL, *c = NULL;
a = malloc(sizeof(A));
if (NULL == a) goto wtf;
b = malloc(sizeof(B));
if (NULL == b) goto wtf;
c = malloc(sizeof(C));
if (NULL == c) goto wtf;
......
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
对变量就近定义的好坏见仁见智了,但是goto毕竟不是个好东西,所以看过内核代码的同学可能会发现另外一种替代性的结构:do-while(0) 。乍一看这个结构似乎没有意义,有点奇怪,但是却很好用,很适合用来消除goto语句,例如上面的代码可以这么做:
void func(){
void *a = NULL, *b = NULL, *c = NULL;
do {
a = malloc(sizeof(A));
if (NULL == a) break;
b = malloc(sizeof(B));
if (NULL == b) break;
c = malloc(sizeof(C));
if (NULL == c) break;
......
} while (0);
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
既消除了“不法分子”,也达到了避免冗余的目的。对于这个结构,其实还有更多的好处,详见这里。void *a = NULL, *b = NULL, *c = NULL;
do {
a = malloc(sizeof(A));
if (NULL == a) break;
b = malloc(sizeof(B));
if (NULL == b) break;
c = malloc(sizeof(C));
if (NULL == c) break;
......
} while (0);
wtf:
if (a != NULL) free(a);
if (b != NULL) free(b);
if (c != NULL) free(c);
}
但是do-while(0)和goto一样,不是万金油,对于很多较复杂的情况也不能很好的解决,甚至会使得程序更加晦涩难懂。对于do-while(0),如果在这个结构内还有一个循环,循环里面出错想要跳出do-while(0),break就不奏效了(至于为什么,你懂的),这时代码怎么写都恶心,只能羡慕Java里面的break label语法了;而对于比较复杂的资源,比如上文中申请到的内存是 a->b->c 这样嵌套的,那么如何安排内存释放代码,又要让人头疼了。合理的使用goto/do-while(0),将过长的代码拆分成多个函数等都可以起到一定的帮助。
只是很可惜,C语言的能力大概就只能走到这里了。想走得更远,就得借助C++来完成了。虽然C++没有gc,但是由于其OO的特性,使得RAII的实现变得可能。
所谓RAII,即 Resource Acquizition Is Initialization。很晦涩吧?其实具体实现很简单:把资源封装成一个类,在其构造函数中分配,在析构函数中释放。当需要使用的时候,在栈上初始化一个对象,当这个对象生命周期结束的时候,其析构函数会被调用,自动完成资源的释放。对于前面提到的例子,可以把A/B/C封装成一个class,对应的a/b/c就是实例化得到的三个对象,当func函数结束的时候,abc对应的内存就会被释放。同样的方法也适用于锁、互斥量、文件指针等其他类型的资源。下面这段代码以pthread_mutex为例,演示了RAII的使用:
class Mutexer {
private:
pthread_mutex_t *mutex;
public:
Mutexer(pthread_mutex_t *m) { mutex = m; }
~Mutexer() { Unlock(); }
Lock() { pthread_mutex_lock(mutex); }
Unlock() { pthread_mutex_unlock(mutex); }
};
//Global mutex
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void func() {
Mutexer mtx(&mutex);
mtx::lock();
if (sth. failed) {
return;
}
}
private:
pthread_mutex_t *mutex;
public:
Mutexer(pthread_mutex_t *m) { mutex = m; }
~Mutexer() { Unlock(); }
Lock() { pthread_mutex_lock(mutex); }
Unlock() { pthread_mutex_unlock(mutex); }
};
//Global mutex
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void func() {
Mutexer mtx(&mutex);
mtx::lock();
if (sth. failed) {
return;
}
}
不过程序中因为各种原因常需要使用 new 来分配资源(内存、对象等),这样对应的指针还是得在其生命周期结束的时候被释放,总不能为每一个指针再封装一个struct吧。幸而C++的泛型在这里又为RAII提供了绝佳的方法。实际上在第一版STL里面就包含了一个 auto_ptr 容器,实例化一个auto_ptr的时候可以赋予一个任意类型指针ptr(但是必须是使用new获得的,特别注意:new[]分配的不行),auto_ptr对象将ptr包装起来,并重载了 * 和 -> 两个操作符,使得该对象能像指针一样被使用,并且在该对象被生命周期的时候,其析构函数会delete ptr。 下面是auto_ptr的一个简单实现和使用:
template <typename T>
class x_ptr
{
private:
T* x;
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; }
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
void func(){
x_ptr<int> p(new int);
*p = 3;
}
代码的最后无需显式调用 delete 需释放分配的那个int,却照样避免了内存的泄漏。class x_ptr
{
private:
T* x;
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; }
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
void func(){
x_ptr<int> p(new int);
*p = 3;
}
既然说到auto_ptr,为什么不用它来写例子呢?因为auto_ptr的某些特性导致其有大坑,在很多地方不受待见,以至于在 c++11 标准里,auto_ptr被废弃了,因此不建议在项目中使用它了。有兴趣的同学可以去翻看《C++标准程序库》对auto_ptr的介绍。
本来计划写到这里要告一段落了,但是上面的 x_ptr 有坑,无奈只好继续……为什么说有坑呢?举两个例子:
void func1() {
x_ptr<int> p(new int), q(new int);
*p = 1;
*q = 2;
p = q;
}
void func2() {
x_ptr<int> p(new int[10]);
}
在 func1 中,由于进行了拷贝(其实拷贝构造也一样),导致 p 对应的那块空间会被泄漏,而 q 对应的那块空间会被释放2次;在 func2 中,x_ptr试图用delete去释放由new[]分配的内存空间,其结果是未定义的(比如不是基本元素而是某个class,程序可能会直接崩溃)。x_ptr<int> p(new int), q(new int);
*p = 1;
*q = 2;
p = q;
}
void func2() {
x_ptr<int> p(new int[10]);
}
针对func1的问题,可以通过私有化其拷贝函数、拷贝构造函数来禁止x_ptr的拷贝,代码如下
template <typename T>
class x_ptr
{
private:
T* x;
x_ptr(const x_ptr&);
x_ptr& operator= (const x_ptr& v);
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; };
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
class x_ptr
{
private:
T* x;
x_ptr(const x_ptr&);
x_ptr& operator= (const x_ptr& v);
public:
typedef T ele_type;
explicit x_ptr(T* _x): x(_x) {}
~x_ptr() { delete x; };
T & operator * () { return *x; }
T * operator ->() const { return x; }
};
而针对func2的问题,解决方法呢,要么是写一个x_ptr_arr,使用delete[]来处理;要么是在x_ptr的构造函数里加一个flag,用来指定是否是new[]分配的,当然,为了方便,可以设置一个默认值false.....
补充一句,这里的x_ptr其实是boost::scoped_ptr的缩水版了,有兴趣的同学可以自行Google了解更多,关于内存泄漏的话题,这篇大概就说这么多了吧。
最后,感谢Sandy同学的 C++中利用RAII在stack上管理资源I ,本篇有多处参考该文。希望他能抽出时间把 II 给写完吧 :P
Dec
23
这程序写了好几次了,干脆贴出来吧~附上exe。
下载文件 (已下载 1084 次)
#include <stdio.h>
#include <stdlib.h>
char str[65536];
int main() {
int i;
for (i = 0; i < 65536; i++) str[i] = '1';
str[65535] = '\0';
i = 0;
while (1) {
i++;
if (i % 3000 == 0) {
sleep(1);
}
puts(str);
}
return 0;
}
#include <stdlib.h>
char str[65536];
int main() {
int i;
for (i = 0; i < 65536; i++) str[i] = '1';
str[65535] = '\0';
i = 0;
while (1) {
i++;
if (i % 3000 == 0) {
sleep(1);
}
puts(str);
}
return 0;
}

Nov
15
@2019-03-19 STL里的lowerbound算法简单有效。
该元素在数组中不一定存在,只是要找一个i,使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
该元素在数组中不一定存在,只是要找一个i,使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
//区间是 [s, e),左闭右开,类似STL。
int binsearch(int arr[], int t, int s, int e)
{
int left = s, right = e, mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (arr[mid] == t)
return mid;
else if (arr[mid] < t)
{
//right most OR ...right here
if (mid + 1 >= right || t < arr[mid + 1])
return mid;
else
left = mid + 1;
}
else /* arr[mid] > t */
{ //left most OR ...right here
if (mid - 1 < left || arr[mid - 1] <= t)
return mid - 1;
else
//11.18.DELETED: right = mid - 1;
right = mid; //[11.18.update]发现这里是个BUG……
}
}
return -2; //bad range
}
int binsearch(int arr[], int t, int s, int e)
{
int left = s, right = e, mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (arr[mid] == t)
return mid;
else if (arr[mid] < t)
{
//right most OR ...right here
if (mid + 1 >= right || t < arr[mid + 1])
return mid;
else
left = mid + 1;
}
else /* arr[mid] > t */
{ //left most OR ...right here
if (mid - 1 < left || arr[mid - 1] <= t)
return mid - 1;
else
//11.18.DELETED: right = mid - 1;
right = mid; //[11.18.update]发现这里是个BUG……
}
}
return -2; //bad range
}
Oct
13
Translated to ENGLISH VERSION
源于这两篇文章:
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
这个算法看了三天,终于理解了,在这里记录一下自己的思路,免得以后忘了又要想很久- -.
首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个'\0'所以正好OK,但其他语言可能会导致越界)。
下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:
那么怎么计算P[i]呢?该算法增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中 id 为已知的 {右边界最大} 的回文子串的中心,mx则为id+P[id],也就是这个子串的右边界。
然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点,理解起来会简单很多:
当然光看代码还是不够清晰,还是借助图来理解比较容易。
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。

当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。

对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。
于是代码如下:
OVER.
#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出,由于 P[id] = mx,所以 S[id-mx] != S[id+mx],那么当 P[j] > mx - i 的时候,可以肯定 P[i] = mx - i ,不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点,也只是多一次匹配(必然会fail),但是却要多加一个分支,所以上面的代码就不改了。
源于这两篇文章:
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
这个算法看了三天,终于理解了,在这里记录一下自己的思路,免得以后忘了又要想很久- -.
首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个'\0'所以正好OK,但其他语言可能会导致越界)。
下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";
然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
(p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)
那么怎么计算P[i]呢?该算法增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中 id 为已知的 {右边界最大} 的回文子串的中心,mx则为id+P[id],也就是这个子串的右边界。
然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点,理解起来会简单很多:
//记j = 2 * id - i,也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。
当然光看代码还是不够清晰,还是借助图来理解比较容易。
当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。
当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。
对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。
于是代码如下:
//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx) {
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
OVER.
#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出,由于 P[id] = mx,所以 S[id-mx] != S[id+mx],那么当 P[j] > mx - i 的时候,可以肯定 P[i] = mx - i ,不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点,也只是多一次匹配(必然会fail),但是却要多加一个分支,所以上面的代码就不改了。
Jul
22
#include <stdio.h>
int main()
{
int a, b;
scanf("%d%*[, ]%d", &a, &b);
printf("%d + %d = %d\n", a, b, a + b);
return 0;
}
int main()
{
int a, b;
scanf("%d%*[, ]%d", &a, &b);
printf("%d + %d = %d\n", a, b, a + b);
return 0;
}
<= 1 2
=> 1 + 2 = 3
<= 1,2
=> 1 + 2 = 3
<= 1 , 2
=> 1 + 2 = 3
Jun
20
=> How to call a php function in a php extension
详细的说明参见:
[php-5.2.17]
/Zend/zend_execute_API.c +623 & +636 call_user_function_ex
/ext/standard/basic_functions.c +5174 PHP_FUNCTION(call_user_func_array)
/ext/pcre/pcre.c +833 (in function "preg_do_repl_func")
http://man.chinaunix.net/develop/php/php_manual_zh/html/zend.calling-user-functions.html
http://www.phpfreaks.com/forums/index.php?topic=10272.0
详细的说明参见:
[php-5.2.17]
/Zend/zend_execute_API.c +623 & +636 call_user_function_ex
/ext/standard/basic_functions.c +5174 PHP_FUNCTION(call_user_func_array)
/ext/pcre/pcre.c +833 (in function "preg_do_repl_func")
http://man.chinaunix.net/develop/php/php_manual_zh/html/zend.calling-user-functions.html
http://www.phpfreaks.com/forums/index.php?topic=10272.0
PHP_FUNCTION (caller)
{
//call_user_function_ex
zval *function, *str, *arr;
zval **params[10];
MAKE_STD_ZVAL(function);
ZVAL_STRING(function, "var_dump", 1); //I wanna call var_dump
/* //pass a string as its param
MAKE_STD_ZVAL(str);
ZVAL_STRING(str, "Hello, world!", 1);
params[0] = &str;
*/
//pass an array as its param
MAKE_STD_ZVAL(arr);
array_init(arr);
add_assoc_string(arr, "name", "felix021", 1);
params[0] = &arr;
zval *ret;
if (call_user_function_ex(CG(function_table), NULL,
function, &ret, 2, params, 0, NULL TSRMLS_CC) != FAILURE)
{
*return_value = *ret;
zval_copy_ctor(return_value);
zval_ptr_dtor(&ret);
return;
}
else {
RETURN_FALSE;
}
}
{
//call_user_function_ex
zval *function, *str, *arr;
zval **params[10];
MAKE_STD_ZVAL(function);
ZVAL_STRING(function, "var_dump", 1); //I wanna call var_dump
/* //pass a string as its param
MAKE_STD_ZVAL(str);
ZVAL_STRING(str, "Hello, world!", 1);
params[0] = &str;
*/
//pass an array as its param
MAKE_STD_ZVAL(arr);
array_init(arr);
add_assoc_string(arr, "name", "felix021", 1);
params[0] = &arr;
zval *ret;
if (call_user_function_ex(CG(function_table), NULL,
function, &ret, 2, params, 0, NULL TSRMLS_CC) != FAILURE)
{
*return_value = *ret;
zval_copy_ctor(return_value);
zval_ptr_dtor(&ret);
return;
}
else {
RETURN_FALSE;
}
}
Jun
18
网上摘下来的代码,没什么好说的了(因为那一堆 mcrypt_* 函数太乱了,用就是了):
<?php
class DES
{
public static function pkcs5_pad ($text, $blocksize) {
$pad = $blocksize - (strlen($text) % $blocksize);
return $text . str_repeat(chr($pad), $pad);
}
public static function pkcs5_unpad($text) {
$pad = ord($text{strlen($text)-1});
if ($pad > strlen($text)) {
return false;
}
if (strspn($text, chr($pad), strlen($text) - $pad) != $pad) {
return false;
}
return substr($text, 0, -1 * $pad);
}
public static function encrypt($key, $data) {
$size = mcrypt_get_block_size('des', 'ecb');
$data = DES::pkcs5_pad($data, $size);
$td = mcrypt_module_open('des', '', 'ecb', '');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
@mcrypt_generic_init($td, $key, $iv);
$data = mcrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
return $data;
}
public static function decrypt($key, $data) {
$td = mcrypt_module_open('des','','ecb','');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
$ks = mcrypt_enc_get_key_size($td);
@mcrypt_generic_init($td, $key, $iv);
$decrypted = mdecrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
$result = DES::pkcs5_unpad($decrypted);
return $result;
}
}
/* test code
$in = "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw==";
$des = base64_decode($in);
echo DES::decrypt("12345678", $des);
echo "\n";
$in = "cea3e8e1659582206e0be32539729e9f";
$des = DES::encrypt("12345678", $in);
$out = base64_encode($des);
echo $out;
echo "\n";
// */
?>
class DES
{
public static function pkcs5_pad ($text, $blocksize) {
$pad = $blocksize - (strlen($text) % $blocksize);
return $text . str_repeat(chr($pad), $pad);
}
public static function pkcs5_unpad($text) {
$pad = ord($text{strlen($text)-1});
if ($pad > strlen($text)) {
return false;
}
if (strspn($text, chr($pad), strlen($text) - $pad) != $pad) {
return false;
}
return substr($text, 0, -1 * $pad);
}
public static function encrypt($key, $data) {
$size = mcrypt_get_block_size('des', 'ecb');
$data = DES::pkcs5_pad($data, $size);
$td = mcrypt_module_open('des', '', 'ecb', '');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
@mcrypt_generic_init($td, $key, $iv);
$data = mcrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
return $data;
}
public static function decrypt($key, $data) {
$td = mcrypt_module_open('des','','ecb','');
$iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
$ks = mcrypt_enc_get_key_size($td);
@mcrypt_generic_init($td, $key, $iv);
$decrypted = mdecrypt_generic($td, $data);
mcrypt_generic_deinit($td);
mcrypt_module_close($td);
$result = DES::pkcs5_unpad($decrypted);
return $result;
}
}
/* test code
$in = "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw==";
$des = base64_decode($in);
echo DES::decrypt("12345678", $des);
echo "\n";
$in = "cea3e8e1659582206e0be32539729e9f";
$des = DES::encrypt("12345678", $in);
$out = base64_encode($des);
echo $out;
echo "\n";
// */
?>