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。
下载文件 (已下载 1058 次)
#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;
}
下载文件 (已下载 1058 次)
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";
// */
?>
