Semantic Web Notes

说说C语言和内存对齐

我看东西，看得快，忘得也奇快。大概2星期重新研究过内存对齐，现在都快忘光了，于是赶紧再回忆一下。

所谓内存对齐，即使得数据所在内存地址的起点应尽量对齐(是某个值的公倍数)，而不是凌乱不堪的。一般我们把8个bit看成1一个byte，用byte来做存储的单位，其实也是一种内存对齐的机制——这样处理器访问数据只需要访问8的倍数即可。

内存对齐的目的很简单，这样有利于提供访问的速度（特别是在栈中）。对于对齐的内存地址，处理器访问一次即可得到，而未对齐的地址，可能需要访问两次才行。

那内存对齐的最小单位是什么呢？其实不同平台上不同的编译器都有自己的决定(猜的)，编译器的这个决定叫做默认对齐系数。我们在自己编写程序的时候很少会去注意到这个对齐问题，这个很正常，因为这机制本身就应该是对程序员透明的。但是，我们还是能够在程序中觉察到对齐机制的存在。如果程序员没有正确意识到对齐机制的存在，有的时候它甚至会让程序的行为不正确。我举个小小的例子来说明下。
假设有这样一个结构体

typedef struct ex{
	int c1;
	char c2;
        int c3;
}ve;  /*  1  */

我的运行环境是gcc4.0+, ubuntu8.04, 32位单核cpu，sizeof(char)是1，sizeof(int)是4，猜猜sizeof(ve)的值会是多少？如果程序员不清楚内存对齐的概念的话会认为这个值是6，但其实是12。在这里面，有4个成员需要对齐，c1,c2,c3,ve，c1,c2,c3跟ve的对齐规则并不一致。

c1,c2,c3的对齐过程如下（对齐系数是4的前提下）：假设第一个成员放在offset为0的位置，那么c1所占的内存就是[0~3]，而c2所占的内存是[4]，c3所占的内存不是[5~8]，而是[8~12]，但如果c3是char类型的话，c3所占的内存就是[5]。

所以结构体内成员的对齐规则如下：假设第一个成员的offset是0，则之后成员的对齐系数是系统的对齐系数（可以通过pragma pack(x)来指定）和自身长度两者间较小的值。比如，系统的对齐系数是4，而char的长度是1，那么char就按1对齐。而int的长度是4，于系统对齐系数一致，则按4对齐。

从上面这个规则，我们可以看到一个有趣的问题，在结构体内，成员的摆放顺序不同，结构体所占空间是不同的。比如，

typedef struct ex{
	char c1;
	char c2;
        int c3;
}ve; /*  2  */

与

typedef struct ex{
	char c1;
	int c3;
        char c2;
}ve; /*  3  */

，前者所占的空间是8，而后者所占空间是12。但是对于程序的逻辑而言，两者的定义是完全一致的。了解对齐规则是有好处的，至少我们写出来的结构体空间占用更小些。

说完了c1,c2,c3的对齐，下面说ve的对齐。sizeof(ve)的值事实上并不是如我们分析的c1,c2,c3对齐完之后所占空间的累加，它自身也是需要对齐的。结构体的对齐规则如下：取其成员中占用空间最长的值，我们的例子中是int类型，值是4，然后跟系统的对齐系数比较，取较小值为ve的对齐系数。如果我们在结构体2中，语句int c3;后面再加一句char temp;我们可以算出成员所占的空间是9，而ve所占的空间是12。

Posted in C/C++ | 4 Comments »

easyC-API中关于动态数组(Vector)的实现与使用方法简介

动态数组在C语言中是比较常用的，实现起来也是很简单明了的，这篇文章我简单给出一个动态数组的实现(easyC-API中的实现与此基本一致，稍稍复杂些)。首先，定义动态数组如下：

typedef struct easyc_vector{
    int size;
    int base_size;
    int actual_size;
    eType *base;
    eType (*get)(int, const struct easyc_vector *);
    void (*set)(int,eType,const struct easyc_vector *);
    eType (*remove)(int,struct easyc_vector *);
    void (*sort)(int (*compare)(const void *,const void *),struct easyc_vector *s);
    void (*add)(eType,struct easyc_vector *);
}c_vector;

eType是数据类型，这里我们假设它是整型。
动态数组的初始化由函数make_vector负责，具体函数的实现我就不给出了。可以看出这个结构支持动态数组的创建，插入，查找，删除，添加，取长度，及排序等基本操作。这些操作对于数组而言，已经是相当够用了。

可能有朋友对它的排序如何实现感兴趣，这里排序是通过系统标准库中的qsort实现的。这是一个小技巧。可以看到排序函数的定义如下：

void (*sort)(int (*compare)(const void *,const void *),struct easyc_vector *s);

，需要的参数是一个用户实现的比较大小的函数，及一个指向动态数组的指针。我们来看看它是如何把排序的工作委托给qsort的，以下是这个函数的实现：

void easyc_vector_sort(int(*compare)(const void *a ,const void *b),c_vector *s){
	qsort(s->base,s->size,sizeof(eType),compare);
	return;
}

感谢函数指针，使得我们能把功能的委托变的更加容易与自然。

以下的代码是对这个动态数组简单的使用，可以看到，使用起来还是蛮自然的。

#include
#include"easyc_ds.h"
int cmp(const void*a,const void *b){
	return *(eType *)a-*(eType *)b;
}
int main(){
	c_vector s;
	s=make_vector(1);
	s.add(1,&s);
	s.add(5,&s);
	s.add(3,&s);
	s.sort(cmp,&s);
	printf("%d\n",s.get(0,&s));
	printf("%d\n",s.get(1,&s));
	printf("%d\n",s.get(2,&s));
	return 0;
}

easyc_ds.h定义了所有数据结构的结构，声明了所有的方法。当然您在编译以上测试代码的时候还需要使用我们的静态库(libeasyc_ds.a)。

如果您对我们的代码有兴趣，可以去easyC-API的主页上获取最新的源代码，二进制库文件，测试代码及makefile文件。如果您使用的是windows系统，我们编译好的二进制文件会不兼容，请您在自己编译器上重新编译，至于源代码，它是跨平台的。

Posted in C/C++ | No Comments »

关于C语言的typedef

注：本文的内容只是对自己学习到知识的一些简单总结，并没有考证过C的规范和手册进行求证。

很多文章，甚至于很多教材，对c语言的typedef的解释是有错误的，以致于许多学习C语言的人对typedef的理解往往有偏差。

一种最常见的错误观点是typedef定义了现有类型的一个别名（alias），比如

typedef int EType;/* (1) */

是给int类型取了一个EType的别名。在这种情况下，似乎也能解释的通，但是，如果碰到这样一个typedef定义呢：

typedef int (*f)(double,int); /* (2) */

观其名，识其行，看typedef的名字就明白它的意思是定义类型。typedef不是简单的给现有类型取一个别名，或者简单的进行字符替换，typedef是利用现有的数据类型类定义一个新的类型。比如语句（1），从概念上我们应当认为是定义了一种新的数据类型，只是这种新类型跟int类型是吻合的。而语句（2）定义了一种新的类型f，f这种类型是一个参数为double,int，返回值是int的函数指针类型。

那么如何去分析，识别typedef定义的类型呢？我从Tony Bai的文章中学到了蛮好的方法。方法就是看看去掉typedef之后，剩下的语句中把相应的变量(记为p)变成了什么类型，那么加上typedef之后，这个p就成了这种类型的名字。

举语句(2)的例子，把typedef去掉，原句就成了

int (*f)(double,int); /* (3) */

，这是一个很普通的函数指针的定义，这个时候f就是指向一个参数为double,int返回值为int的函数指针变量，那么加上typedef之后，f就是指向…..的函数指针类型。

再举一个通俗的例子，将语句(1)的typedef去掉，就成了

int EType;/* (4) */

我们可以清楚的看到，EType是一个int类型的变量，那么加上typedef，EType实际上就成了一个int类型。

Posted in C/C++ | 6 Comments »

easyC-API项目介绍

/*—————————————————————————————————————
*-Version :1.0
*-Auther : Chen Ju
*-Auther Email: sammy105{@}gmail.com
*-Auther Site : http://www.kylogs.com/blog
*—————————————————————————————————————
*/

easyC-API的目的及内容

easyC-API的目的是要建立一个C语言的实用包，使得C使用起来更加的简便。它主要包括5个部分：

1. 常见的数据结构及其基本函数库
2. 更好更方便的字符串处理函数库
3. 数值计算函数库（包括高精度计算）
4. 解析器（XML, RSS, RDF的解析）
5. 正则表达式函数库

easyC-API遵循的协议

GPL Version 3(访问)

easyC-API目前完成的情况

项目刚刚开始，目前仅完成了stack及linkedlist部分

easyC-API目前的成员

• sammy105
• palwang723

参与easyC-API的开发

需要说明的是easyC-API并不是具有太多难度的项目，如果您只是抱着学习与练习的目的，我们也欢迎您的加入。您可以从http://easyc-api.googlecode.com/svn/trunk获得最新的源代码及测试代码。如果需要参与开发，可以发信给我，或者在本文章下留言，我会跟您信件联系。

参与easyC-API开发需要掌握的知识

1. 由于easyC-API是C语言的项目，所以您需要比较熟悉C语言，请务必要清楚C与C++之间的分别。
2. 最好的情况下，您还需要掌握gcc的使用方法，makefile的编写方法，及make的使用方法。
3. 最好的情况下，您还需要明白C的静态库，动态库的概念及生成方法。
4. 当您成为了我们的commiter，我们会提供一些简单的学习资料，这些资料都可以从网上获得。

当然，2跟3不是必须的，因为您也可以使用集成开发工具来进行编程，比如,DEVC++，或者Eclipse with CDT等等。

下一篇介绍easyC-API的开发指南。

Posted in C/C++ | No Comments »

C函数指针的偏门作用

C语言的指针不仅可以指向数据域，也可以指向一个函数。很多C的初学者并不清楚这个特性，在看一些源代码的时候常常会觉得困惑。

C的函数最常用的是提供函数Callback的能力，比如，C的”stdlib”中声明的qsort函数，用来对数值进行排序。显然，顺序还是降序，元素谁大谁小这些问题，库程序员在编写qsort的时候不可能决定。这些问题是要在用户调用这个函数的时候才能够决定。那边qsort如何保证通用性和灵活性呢?采用的办法是让函数的使用者来制定排序规则。qsort的声明如下：

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

其中

int ( * comparator ) ( const void *, const void * )

便是一个函数指针，指向某个用户自定义的比较函数。参考C++ Reference的例子如下：

/* qsort example */
int values[] = { 40, 10, 100, 90, 20, 25 };
 
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
 
int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0;n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

除了提供回调的能力之外，C函数指针也有其他有趣的用途，比如，利用它来进行面向对象式的编程，比如，利用它来避免C名字空间的冲突。
参考上文，我提供的stack结构体的定义如下

typedef struct easyc_stack{
               int base_size;
               int point;
               int * base;
               int size;
               int  (*pop)(struct easyc_stack *);
               int  (*push)(int,struct easyc_stack *);
               int  (*get_top)(struct easyc_stack );
        }c_stack;

在初始化完之后，用户调用这个结构体上的pop函数，只需要 s.pop(&s)即可。即使这个时候，工程内部有另外一个函数名字也叫pop，他们之间是不会发生名字上的冲突的。原因很简单，因为结构体中的函数指针pop指向的函数名字可能是

int ugly_stupid_no_one_will_use_this_name_pop(c_stack *)

，只是stack的用户是不知道他在调用s.pop(&s)，实际上起作用的是这样一个有着冗长名字的函数。

函数指针这种避免命名冲突上的额外好处对于一些库函数的编写者是很有意义的，因为库可能被很多的用户在许多不同的环境下使用，这样就能有效的避免冲突而保证库的可用性。

认领 BANGD2569BE2B2E8A4BC39F1189CXIANGUO

Posted in C/C++ | 8 Comments »

C与C++在函数指针上的区别

最近为C语言写一些数据结构相关的库，遇到一个有趣的问题。我最初版本的代码能够在GCC下用纯C编译通过，但是却不能用C++编译通过，尝试用Visual C++6.0编译，也是报一样的错。我还一直以为C++能够完全的兼容C呢，看来观点需要变化了。
下面详细说明下。

我定义了一个stack结构体(最初的定义)如下：

1
2
3
4
5
6
7
8
9

typedef struct easyc_stack{
               int inc_size;
               int point;
               int * base;
               int size;
               int  (*pop)();
               int  (*push)();
               int  (*get_top)();
        }c_stack;

在另外的代码里我声明了一个函数

1

int ugly_easyc_pop(c_stack *);

然后编写一个stack创建函数

1
2
3
4
5
6
7

c_stack make_stack(int size){
    c_stack s;
    .....//some code
    s.pop=ugly_easyc_pop;
    .....//some code
    return s;
}

在纯C编译器中，这样的做法毫无问题，经过测试，push, pop也能正常工作。
但是在用C++编译器编译就出问题了，看错误信息是类型不匹配，C++编译器认为 int (*)()与 int (*)(c_stack *)是不一样的类型，而C编译器觉得无所谓。因此，要在C和C++中都正常编译，需要修改c_stack中函数指针的定义，修改如下：

1
2
3
4
5
6
7
8
9

typedef struct easyc_stack{
               int base_size;
               int point;
               int * base;
               int size;
               int  (*pop)(struct easyc_stack *);
               int  (*push)(int,struct easyc_stack *);
               int  (*get_top)(struct easyc_stack );
        }c_stack;

我猜C++这样做的原因可能是因为它支持函数的overload，因而，同函数名，不同的参数被认为是不同的类型了。
认领 BANGD2569BE2B2E8A4BC39F1189CXIANGUO

Posted in C/C++ | No Comments »