翻译php扩展开发和嵌入式第8章在数组和哈希表上工作.docx
《翻译php扩展开发和嵌入式第8章在数组和哈希表上工作.docx》由会员分享,可在线阅读,更多相关《翻译php扩展开发和嵌入式第8章在数组和哈希表上工作.docx(36页珍藏版)》请在冰点文库上搜索。
翻译php扩展开发和嵌入式第8章在数组和哈希表上工作
本书目前在github上由laruence()和walu(http:
//www.walu.cc)两位大牛组织翻译.该翻译项目地址为:
本书在github上的地址:
未来本书将可能部分合并到phpbook项目中,同时保留一份独立版本.
原书名:
原作者:
SaraGolemon
译者:
goosman.lei(雷果国)
译者Email:
lgg860911@
译者Blog:
在数组和哈希表上工作
在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的函数调用,你可以在你的扩展中使用这些函数.
ZendHashAPI
ZendHashAPI被分为几个基本的打雷,除了几个特殊的,这些函数通常都返回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存在,zend_hash_add()将会失败.
接下来的两个函数以类似的方式处理数值索引的HashTable.这两行之间的区别在于是否指定索引或者说是否自动赋值为下一个可用索引.
如果需要存储使用zend_hash_next_index_insert()插入的元素的索引值,可以调用zend_hash_next_free_element()函数获得:
ulongnextid=zend_hash_next_free_element(ht);
zend_hash_index_update(ht,nextid,&data,sizeof(data),NULL);
对于上面这些插入和更新函数,如果给pDest传递了值,则pDest指向的void*数据元素将被填充为指向被拷贝数据的指针.这个参数和你已经见到过的zend_hash_find()的pData参数是相同的用法(也会有相同的结果).
译注:
下面的例子及输出可能对理解pDest有帮助
/*拷贝自Zend/zend_hash.c*/
voidzend_hash_display_string(constHashTable*ht)
{
Bucket*p;
uinti;
if(UNEXPECTED(ht->nNumOfElements==0)){
zend_output_debug_string(0,"Thehashisempty");
return;
}
for(i=0;inTableSize;i++){
p=ht->arBuckets[i];
while(p!
=NULL){
zend_output_debug_string(0,"%s[0x%lX]<==>%s",p->arKey,p->h,(char*)p->pData);
p=p->pNext;
}
}
p=ht->pListTail;
while(p!
=NULL){
zend_output_debug_string(0,"%s[hash=0x%lX,pointer=%p]<==>%s[pointer=%p]",p->arKey,p->h,p->arKey,(char*)p->pData,p->pData);
p=p->pListLast;
}
}
PHP_FUNCTION(sample_ht)
{
HashTable*ht0;
char*key;
char*value;
void*pDest;
key=emalloc(16);
value=emalloc(32);
ALLOC_HASHTABLE(ht0);
zend_hash_init(ht0,50,NULL,NULL,0);
strcpy(key,"ABCDEFG");
strcpy(value,"0123456789");
printf("key:
%p%s\n",key,key);
printf("value:
%p%s\n",value,value);
zend_hash_add(ht0,key,8,value,11,&pDest);
printf("pDest:
%p\n",pDest);
zend_hash_display_string(ht0);
zend_hash_destroy(ht0);
FREE_HASHTABLE(ht0);
efree(value);
efree(key);
RETURN_NULL();
}
译注:
在sample.c以及php_sample.h中增加对应的php_sample_functions条目及声明,重新编译这个扩展.执行下面命令:
php-dextension=sample.so-r'sample_ht();'
译注:
得到如下输出
key:
0x7feef4d17bd8ABCDEFG
value:
0x7feef4d15aa00123456789
pDest:
0x7feef4d17da0
ABCDEFG[0x1AE58CF22D2E61]<==>0123456789
ABCDEFG[hash=0x1AE58CF22D2E61,pointer=0x7feef4d17d38]<==>0123456789[pointer=0x7feef4d17da0]
找回
因为HashTable有两种不同的方式组织索引,因此就相应的有两种方法提取数据:
intzend_hash_find(HashTable*ht,char*arKey,uintnKeyLength,
void**pData);
intzend_hash_index_find(HashTable*ht,ulongh,void**pData);
你可能已经猜到了,第一种用来维护关联索引的数组,第二种用于数字索引.回顾第2章,当数据被增加到HashTable时,为它分配一块新的内存并将数据拷贝到其中;当提取数据的时候,这个数据指针将被返回.下面的代码片段向HashTable增加了data1,接着在程序的末尾提取它,*data2包含了和*data1相同的内容,虽然它们指向不同的内存地址.
voidhash_sample(HashTable*ht,sample_data*data1)
{
sample_data*data2;
ulongtargetID=zend_hash_next_free_element(ht);
if(zend_hash_index_update(ht,targetID,
data1,sizeof(sample_data),NULL)==FAILURE){
/*应该不会发生*/
return;
}
if(zend_hash_index_find(ht,targetID,(void**)&data2)==FAILURE){
/*同样不太可能,因为我们只是增加了一个元素*/
return;
}
/*data1!
=data2,however*data1==*data2*/
}
通常,取回存储的数据和检查它是否存在一样重要;有两个函数用于检查是否存在:
intzend_hash_exists(HashTable*ht,char*arKey,uintnKeyLen);
intzend_hash_index_exists(HashTable*ht,ulongh);
这两个函数并不会返回SUCCESS/FAILURE,而是返回1标识请求的key/index存在,0标识不存在,下面代码片段的执行等价于isset($foo):
if(zend_hash_exists(EG(active_symbol_table),
"foo",sizeof("foo"))){
/*$fooisset*/
}else{
/*$foodoesnotexist*/
}
快速的填充和取回
ulongzend_get_hash_value(char*arKey,uintnKeyLen);
在相同的关联key上执行多次操作时,可以先使用zend_get_hash_value()计算出哈希值.它的结果可以被传递给一组"快速"的函数,它们的行为与对应的非快速版本一致,但是使用预先计算好的哈希值,而不是每次重新计算.
intzend_hash_quick_add(HashTable*ht,
char*arKey,uintnKeyLen,ulonghashval,
void*pData,uintnDataSize,void**pDest);
intzend_hash_quick_update(HashTable*ht,
char*arKey,uintnKeyLen,ulonghashval,
void*pData,uintnDataSize,void**pDest);
intzend_hash_quick_find(HashTable*ht,
char*arKey,uintnKeyLen,ulonghashval,void**pData);
intzend_hash_quick_exists(HashTable*ht,
char*arKey,uintnKeyLen,ulonghashval);
奇怪的是没有zend_hash_quick_del().下面的代码段从hta(zval*的Has