搜索
在数组和哈希表上工作在C语言中,有两种不同的基础方法用来在一个结构体中存储任意数量的独立数据元素.两种方法都有赞成者和反对者.向量Vs.链表应用的编写通常基于特定类型数据的特性的选择,需要存储多少数据,以及需要多快速度的检索.为了能够有对等的认知,我们先来看看简单的看看这些存储机制.向量向量是一块连续的内存空间,它们包含的数据有规律的间隔.向量最常见的例子就是字符串变量(char*或char[]),它包含了一个接着一个的字符(字节)序列.charfoo[4]=bar;这里,foo[0]包含了字符'b';紧接着,你将在foo[1]中找到字符'a',最后在foo[3]中是一个空字符'\0'.将指向其他结构的指针存储到向量中的用法几乎是无所不在的,比如在上一章,使用zend_get_parameters_array_ex()函数时,就使用了一个zval的向量.那里,我们看到var_dump()定义了一个zval***的函数变量,接着为它分配空间用来存储zval**指针(最终的数据来自zend_get_parameters_ex()调用)zval***args=safe_emalloc(ZEND_NUM_ARGS(),sizeof(zval**),0);和访问字符串中的数组一样,var_dump()实现中使用args[i]依次传递每个zval**元素到内部函数php_var_dump().向量最大的优点在于运行时单个元素的访问速度.args[i]这样的变量引用,可以很快的计算出它的数据地址(args+i*sizeof(args[0]).这个索引结构的空间分配和释放是在单次,高效的调用中完成的.链表另外一种常见的存储数据的方式是链表.对于链表而言,每个数据元素都是一个至少有两个属性的结构体:一个指向链表中的下一个节点,一个则是实际的数据.考虑下面假设的数据结构:typedefstruct_namelistnamelist;struct{structnamelist*next;char*name;}_namelist;使用这个数据结构的引用需要定义一个变量:staticnamelist*people;链表中的第一个名字可以通过检查people变量的name属性得到:people-name;第二个名字则访问next属性:people-next-name,依此类推:people-next-next-name等等,直到next为NULL表示链表中已经没有其他名字了.更常见的用法是使用循环迭代链表:voidname_show(namelist*p){while(p){printf(Name:%s\n,p-name);p=p-next;}}这种链表非常适合于FIFO的链式结构,新的数据被追加到链表的末尾,从另外一端线性的消耗数据:staticnamelist*people=NULL,*last_person=NULL;voidname_add(namelist*person){person-next=NULL;if(!last_person){/*链表中没有数据*/people=last_person=person;return;}/*向链表末尾增加新的数据*/last_person-next=person;/*更新链表尾指针*/last_person=person;}namelist*name_pop(void){namelist*first_person=people;if(people){people=people-next;}returnfirst_person;}新的namelist结构可以从这个链表中多次插入或弹出,而不用调整结构的大小或在某些位置间块拷贝元素.前面你看到的链表只是一个单链表,虽然它有一些有趣的特性,但它有致命的缺点.给出链表中一项的指针,将它从链中剪切出来并确保前面的元素正确的链接上下一个元素就变得比较困难.为了知道它的前一个元素,就需要遍历整个链表直到找到一个元素的next指针指向要被删除的元素.对于大的链表,这可能需要可观的CPU时间.一个简单的相对廉价的解决方案是双链表.对于双链表而言,每个元素增加了一个指针元素,它指向链表中的前一个元素:typedefstruct_namelistnamelist;struct{namelist*next,*prev;char*name;}_namelist;一个元素被添加到双链表的时候,这两个指针相应的都被更新:voidname_add(namelist*person){person-next=NULL;if(!last_person){/*链表中没有元素*/people=last_person=person;person-prev=NULL;return;}/*在链表尾增加一个新元素*/last_person-next=person;person-prev=last_person;/*更新链表尾指针*/last_person=person;}迄今为止,你还没有看到这种数据结构的任何优势,但是现在你可以想想,给出people链表中间的一条任意的namelist记录,怎样删除它.对于单链表,你需要这样做:voidname_remove(namelist*person){namelist*p;if(person==people){/*要删除链表头指针*/people=person-next;if(last_person==person){/*要删除的节点同时还是尾指针*/last_person=NULL;}return;}/*搜索要删除节点的前一个节点*/p=people;while(p){if(p-next==person){/*删除*/p-next=person-next;if(last_person==person){/*要删除的节点是头指针*/last_person=p;}return;}p=p-next;}/*链表中没有找到对应元素*/}现在和双链表的代码比较一下:voidname_remove(namelist*person){if(people==person){people=person-next;}if(last_person==person){last_person=person-prev;}if(person-prev){person-prev-next=person-next;}if(person-next){person-next-prev=person-prev;}}不是很长,也没有循环,从链表中删除一个元素只需要简单的执行条件语句中的重新赋值语句.与此过程相逆的过程就可以同样高效的将元素插入到链表的任意点.最好的是HashTable虽然在你的应用中你完全可以使用向量或链表,但有另外一种集合数据类型,最终你可能会更多的使用:HashTable.HashTable是一种特殊的双链表,它增加了前面看到的向量方式的高效查找.HashTable在Zend引擎和php内核中使用的非常多,整个ZendAPI都子例程都主要在处理这些结构.如你在第2章变量的里里外外中所见,所有的用户空间变量都存储在一个zval*指针的HashTable中.后面章节中你可以看到Zend引擎使用HashTable存储用户空间函数,类,资源,自动全局标记以及其他结构.回顾第2章,Zend引擎的HashTable可以原文存储任意大小的任意数据片.比如,函数存储了完整的结构.自动全局变量只是很少几个字节的元素,然而其他的结构,比如php5的类定义则只是简单的存储了指针.本章后面我们将学习构成ZendHashAPI的函数调用,你可以在你的扩展中使用这些函数.ZendHashAPIZendHashAPI被分为几个基本的打雷,除了几个特殊的,这些函数通常都返回SUCCESS或FAILURE.创建每个HashTable都通过一个公用的构造器初始化:intzend_hash_init(HashTable*ht,uintnSize,hash_func_tpHashFunction,dtor_func_tpDestructor,zend_boolpersistent)ht是一个指向HashTable变量的指针,它可以定义为直接值形式,也可以通过emalloc()/pemalloc()动态分配,或者更常见的是使用ALLOC_HASHTABLE(ht).ALLOC_HASHTABLE()宏使用了一个特定内存池的预分配块来降低内存分配所需的时间,相比于ht=emalloc(sizeof(HashTable));它通常是首选.nSize应该被设置为HashTable期望存储的最大元素个数.如果向这个HashTable中尝试增加多于这个数的元素,它将会自动增长,不过有一点需要注意的是,这里Zend重建整个新扩展的HashTable的索引的过程需要耗费不少的处理时间.如果nSize不是2的幂,它将被按照下面公式扩展为下一个2的幂:nSize=pow(2,ceil(log(nSize,2)));pHashFunction是旧版本Zend引擎的遗留参数,它不在使用,因此这个值应该被设置为NULL.在早期的Zend引擎中,这个值指向一个用以替换标准的DJBX33A(一种常见的抗碰撞哈希算法,用来将任意字符串key转换到可重演的整型值)的可选哈希算法.pDestructor指向当从HashTable删除元素时应该被调用的函数,比如当使用zend_hash_del()删除或使用zend_hash_update()替换.析构器函数的原型如下:voidmethod_name(void*pElement);pElement指向指向要从HashTable中删除的元素.最后一个选项是persistent,它只是一个简单的标记,引擎会直接传递给在第3章内存管理中学习的pemalloc()函数.所有需要保持跨请求可用的HashTable都必须设置这个标记,并且必须调用pemalloc()分配.这个方法的使用在所有php请求周期开始的时候都可以看到:EG(symbol_table)全局变量的初始化:zend_hash_init(&EG(symbol_table),50,NULL,ZVAL_PTR_DTOR,0);这里,你可以看到,当从符号表删除一个元素时,比如可能是对unset($foo)的处理;在HashTable中存储的zval*指针都会被发送给zval_ptr_dtor()(ZVAL_PTR_DTOR展开就是它.).因为50并不是2的幂,因此实际初始化的全局符号表是2的下一个幂64.填充有4个主要的函数用于插入和更新HashTable的数据:intzend_hash_add(HashTable*ht,char*arKey,uintnKeyLen,void**pData,uintnDataSize,void*pDest);intzend_hash_update(HashTable*ht,char*arKey,uintnKeyLen,void*pData,uintnDataSize,void**pDest);intzend_hash_index_update(HashTable*ht,ulongh,void*pData,uintnDataSize,void**pDest);intzend_hash_next_index_insert(HashTable*ht,void*pData,uintnDataSize,void**pDest);这里的前两个函数用于新增关联索引数据,比如$foo['bar']='baz';对应的C语言代码如下:zend_hash_add(fooHashTbl,bar,sizeof(bar),&barZval,sizeof(zval*),NULL);zend_hash_add()和zend_hash_update()唯一的区别是如果key存在,z