[Translation] [php extension development and embedded] Chapter 8 - Working on Arrays and Hash Tables

Working with Arrays and Hash Tables

In C, there are two different basic methods for storing any number of independent data elements in a structure. Both methods are supported Pros and cons.

Vectors Vs. Linked Lists

Applications are often written based on choices about the characteristics of a particular type of data, how much data needs to be stored, and how fast it needs to be retrieved. In order to be able to have To understand peer-to-peer, let’s first take a brief look at these storage mechanisms.

Vector

Vector is a continuous memory space, and the data they contain is regularly spaced. Vector The most common example is a string variable (char * or char []), which contains a sequence of characters (bytes) one after another.

char foo[4] = "bar";

Here, foo[0] contains the character 'b' ; Immediately afterwards, you will find the character 'a' in foo[1], and finally a null character '\0' in foo[3].

Store pointers to other structures into the vector The usage is almost ubiquitous. For example, in the previous chapter, when using the zend_get_parameters_array_ex() function, a zval vector was used. There, we saw that var_dump() defined a zval *** function variable, and then for it Allocate space to store the zval ** pointer (the final data comes from the zend_get_parameters_ex() call)

zval ***args = safe_emalloc(ZEND_NUM_ARGS(), sizeof(zval**), 0);

Same as accessing the array in the string, var_dump() implementation uses args[i] to pass each zval in turn **Elements to the internal function php_var_dump().

The biggest advantage of vectors is the access speed of a single element during runtime. Variable references such as args[i] can quickly calculate its data address (args + i * sizeof(args[0]). The space allocation and release of this index structure is completed in a single, efficient call.

Linked list

Another common storage The form of data is a linked list. For a linked list, each data element is a structure with at least two attributes: one points to the next node in the linked list, and the other is the actual data. Consider the following hypothetical data structure:

typedef struct _namelist namelist;  
struct {  
    struct namelist *next;  
    char *name;  
} _namelist;

Using a reference to this data structure requires defining a variable:

static namelist *people;

The first name in the linked list can be obtained by checking the name attribute of the people variable: people->name; The second For a name, access the next attribute: people->next->name, and so on: people->next->next->name, etc., until next is NULL, indicating that there are no other names in the linked list. A more common usage is to use a loop to iterate a linked list:

void name_show(namelist *p)  
{  
    while (p) {  
        printf("Name: %s\n", p->name);  
        p = p->next;  
    }  
}

This kind of linked list is very suitable for the FIFO chain structure. New data is appended to the end of the linked list and the data is consumed linearly from the other end:

static namelist *people = NULL, *last_person = NULL;  
void name_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;  
    }  
    return first_person;  
}

The new namelist structure can be inserted or popped from this linked list multiple times without having to adjust the size of the structure or block-copy elements at certain locations.

The linked list you saw earlier is just a single Linked lists, although they have some interesting properties, have a fatal flaw. Given a pointer to an item in the linked list, it becomes difficult to cut it out of the chain and ensure that the previous element is correctly linked to the next element. .

In order to know its previous element, you need to traverse the entire linked list until you find an element whose next pointer points to the element to be deleted. For large linked lists, this may require considerable CPU time. A simple A relatively cheap solution is a double linked list.

For a double linked list, each element adds a pointer element, which points to the previous element in the linked list:

typedef struct _namelist namelist;  
struct {  
    namelist *next, *prev;  
    char *name;  
} _namelist;

An element is added When reaching the double linked list, both pointers are updated accordingly:

void name_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;  
}

So far, you have not seen any advantages of this data structure, but now you can think about it, given the people linked list An arbitrary namelist record in the middle, how to delete it. For a singly linked list, you need to do this:

void name_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;  
    }  
    /* 链表中没有找到对应元素 */  
}

Now compare it with the code for a doubly linked list:

void name_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;  
    }  
}

is not very long, and there is no Looping, deleting an element from the linked list only requires a simple reassignment statement in the conditional statement. The reverse process of this process can equally efficiently insert the element into any point of the linked list.

Best The best is HashTable

Although you can definitely use vectors or linked lists in your application, there is another collection data type that you may end up using more: HashTable.

HashTable It is a special double linked list, which adds efficient search in vector mode as seen earlier. HashTable is used a lot in the Zend engine and PHP kernel, and the entire ZendAPI subroutines are mainly used to process these structures.

As you saw in Chapter 2 "Ins and Outs of Variables", all user space variables are stored in a HashTable of zval * pointers. In later chapters you can see that the Zend engine uses HashTable to store users Spatial functions, classes, resources, automatic global tags and other structures.

Recall Chapter 2, the Zend engine's HashTable can store any data piece of any size in the original text. For example, the function stores the complete structure. Automatic global Variables are just elements of a few bytes, while other structures, such as php5 class definitions, simply store pointers.

Later in this chapter we will learn about the function calls that make up the Zend Hash API. You can Use these functions in your extension.

Zend Hash API

The Zend Hash API is divided into several basic ones. Except for a few special ones, these functions usually return SUCCESS or FAILURE .

create

每个HashTable都通过一个公用的构造器初始化:

int zend_hash_init(HashTable *ht, uint nSize,  
    hash_func_t pHashFunction,  
    dtor_func_t pDestructor, zend_bool persistent)

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()替换. 析构器函数的原型如下:

void method_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的数据:

int zend_hash_add(HashTable *ht, char *arKey, uint nKeyLen,  
                void **pData, uint nDataSize, void *pDest);  
  
int zend_hash_update(HashTable *ht, char *arKey, uint nKeyLen,  
                void *pData, uint nDataSize, void **pDest);  
int zend_hash_index_update(HashTable *ht, ulong h,  
                void *pData, uint nDataSize, void **pDest);  
int zend_hash_next_index_insert(HashTable *ht,  
                void *pData, uint nDataSize, 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()函数获得:

ulong nextid = 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 */  
void zend_hash_display_string(const HashTable *ht)  
{  
    Bucket *p;   
    uint i;  
  
    if (UNEXPECTED(ht->nNumOfElements == 0)) {  
        zend_output_debug_string(0, "The hash is empty");  
        return;  
    }     
    for (i = 0; i < ht->nTableSize; 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 -d extension=sample.so -r 'sample_ht();'

译注: 得到如下输出

key: 0x7feef4d17bd8 ABCDEFG  
value: 0x7feef4d15aa0 0123456789  
pDest: 0x7feef4d17da0  
ABCDEFG[0x1AE58CF22D2E61] <==> 0123456789  
ABCDEFG[hash = 0x1AE58CF22D2E61, pointer = 0x7feef4d17d38] <==> 0123456789[pointer = 0x7feef4d17da0]

找回

因为HashTable有两种不同的方式组织索引, 因此就相应的有两种方法提取数据:

int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength,  
                                        void **pData);  
int zend_hash_index_find(HashTable *ht, ulong h, void **pData);

你可能已经猜到了, 第一种用来维护关联索引的数组, 第二种用于数字索引. 回顾第2章, 当数据被增加到HashTable时, 为它分配一块新的内存并将数据拷贝到其中; 当提取数据的时候, 这个数据指针将被返回. 下面的代码片段向HashTable增加了data1, 接着在程序的末尾提取它, *data2包含了和*data1相同的内容, 虽然它们指向不同的内存地址.

void hash_sample(HashTable *ht, sample_data *data1)  
  
{  
   sample_data *data2;  
   ulong targetID = 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 */  
}

通常, 取回存储的数据和检查它是否存在一样重要; 有两个函数用于检查是否存在:

int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLen);  
int zend_hash_index_exists(HashTable *ht, ulong h);

这两个函数并不会返回SUCCESS/FAILURE, 而是返回1标识请求的key/index存在, 0标识不存在, 下面代码片段的执行等价于isset($foo):

if (zend_hash_exists(EG(active_symbol_table),  
                                "foo", sizeof("foo"))) {  
    /* $foo is set */  
} else {  
    /* $foo does not exist */  
}

快速的填充和取回

ulong zend_get_hash_value(char *arKey, uint nKeyLen);

在相同的关联key上执行多次操作时, 可以先使用zend_get_hash_value()计算出哈希值. 它的结果可以被传递给一组"快速"的函数, 它们的行为与对应的非快速版本一致, 但是使用预先计算好的哈希值, 而不是每次重新计算.

int zend_hash_quick_add(HashTable *ht,  
    char *arKey, uint nKeyLen, ulong hashval,  
    void *pData, uint nDataSize, void **pDest);  
int zend_hash_quick_update(HashTable *ht,  
    char *arKey, uint nKeyLen, ulong hashval,  
    void *pData, uint nDataSize, void **pDest);  
int zend_hash_quick_find(HashTable *ht,  
    char *arKey, uint nKeyLen, ulong hashval, void **pData);  
int zend_hash_quick_exists(HashTable *ht,  
    char *arKey, uint nKeyLen, ulong hashval);

奇怪的是没有zend_hash_quick_del(). 下面的代码段从hta(zval *的HashTable)拷贝一个特定的元素到htb, 它演示了"快速"版本的哈希函数使用:

void php_sample_hash_copy(HashTable *hta, HashTable *htb,  
                    char *arKey, uint nKeyLen TSRMLS_DC)  
{  
    ulong hashval = zend_get_hash_value(arKey, nKeyLen);  
    zval **copyval;  
  
    if (zend_hash_quick_find(hta, arKey, nKeyLen,  
                hashval, (void**)©val) == FAILURE) {  
        /* arKey不存在 */  
        return;  
    }  
    /* zval现在同时被另外一个哈希表持有引用 */  
    (*copyval)->refcount++;  
    zend_hash_quick_update(htb, arKey, nKeyLen, hashval,  
                copyval, sizeof(zval*), NULL);  
}

译注: 下面的例子是译者对上面例子的修改, 应用在数组上, 对外暴露了用户空间接口.

/* php_sample.h中定义的arg info */  
#ifdef ZEND_ENGINE_2  
ZEND_BEGIN_ARG_INFO(sample_array_copy_arginfo, 0)  
    ZEND_ARG_ARRAY_INFO(1, "a", 0)  
    ZEND_ARG_ARRAY_INFO(1, "b", 0)  
    ZEND_ARG_PASS_INFO(0)  
ZEND_END_ARG_INFO()  
#else  
static unsigned char    sample_array_copy_arginfo[] =  
    {3, BYREF_FORCE, BYREF_FORCE, 0};  
#endif  
PHP_FUNCTION(sample_array_copy);  
  
/* sample.c中在php_sample_functions中增加的对外暴露接口说明 */  
PHP_FE(sample_array_copy, sample_array_copy_arginfo)  
  
/* 函数逻辑实现 */  
PHP_FUNCTION(sample_array_copy)  
{  
    zval    *a1, *a2, **z;  
    char    *key;  
    int     key_len;  
    ulong   h;    
  
    if ( zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "aas", &a1, &a2, &key, &key_len) == FAILURE ) {   
        RETURN_FALSE;  
    }     
  
    h   = zend_get_hash_value(key, key_len + 1);   
  
    if ( zend_hash_quick_find(Z_ARRVAL_P(a1), key, key_len + 1, h, (void **)&z) == FAILURE ) {   
        RETURN_FALSE;  
    }     
  
    Z_SET_REFCOUNT_PP(z, Z_REFCOUNT_PP(z) + 1);   
    Z_SET_ISREF_PP(z); /* 这里设置为引用类型, 读者可以注释这一行比较结果, 增强对变量引用的理解. */  
    zend_hash_quick_update(Z_ARRVAL_P(a2), key, key_len + 1, h, z, sizeof(zval *), NULL);  
  
    RETURN_TRUE;  
}

拷贝和合并

前面的任务是从一个HashTable拷贝一个元素到另一个HashTable, 这是很常见的, 并且通常都是批量去做. 为了避免重复的取回和设置值的循环操作, 有3个帮助函数:

typedef void (*copy_ctor_func_t)(void *pElement);  
void zend_hash_copy(HashTable *target, HashTable *source,  
            copy_ctor_func_t pCopyConstructor,  
            void *tmp, uint size);

source中的每个元素都会被拷贝到target中, 接着通过pCopyConstructor函数处理. 对于用户空间数组变量这样的HashTable, 这里提供了增加引用计数的机会, 因此当zval *从一个HashTable中移除的时候, 它并不会被提前销毁. 如果在目标HashTable中已经存在了相同的元素, 将使用新元素覆盖. 其他已有的没有被覆盖的元素也不会被隐式的移除.

tmp应该是一个指针, 它指向的内存区域将被zend_hash_copy()函数在执行过程中作为临时空间使用. php 4.0.3之后, 这个临时空间不再使用. 如果确认你的扩展不会在4.0.3之前的php中使用, 就将它设置为NULL.

size是每个成员元素所占的字节数. 对于用户空间变量Hash的情况, 它应该是sizeof(zval *).

void zend_hash_merge(HashTable *target, HashTable *source,  
            copy_ctor_func_t pCopyConstructor,  
            void *tmp, uint size, int overwrite);

zend_hash_merge()与zend_hash_copy()唯一的不同在于最后的overwrite参数. 当将它设置为非0值时, zend_hash_merge()的行为和zend_hash_copy()一致. 当它设置为0时, 跳过已经存在的元素.

typedef zend_bool (*merge_checker_func_t)(HashTable *target_ht,  
    void *source_data, zend_hash_key *hash_key, void *pParam);  
void zend_hash_merge_ex(HashTable *target, HashTable *source,  
            copy_ctor_func_t pCopyConstructor, uint size,  
            merge_checker_func_t pMergeSource, void *pParam);

这一组函数中的最后一个, 允许使用一个合并检查函数有选择的拷贝. 下面的例子展示了zend_hash_merge_ex()用于仅拷贝源HashTable中关联索引成员的例子:

zend_bool associative_only(HashTable *ht, void *pData,  
            zend_hash_key *hash_key, void *pParam)  
{  
    /* True if there's a key, false if there's not */  
    return (hash_key->arKey && hash_key->nKeyLength);  
}  
void merge_associative(HashTable *target, HashTable *source)  
{  
    zend_hash_merge_ex(target, source, zval_add_ref,  
                sizeof(zval*), associative_only, NULL);  
}

使用Hash Apply迭代

就像用户空间一样, 有多种方式去迭代数据集合. 首先, 最简单的方法就是类似于用户空间的foreach()结构, 使用回调系统. 系统涉及两个部分, 一部分是你要编写的回调函数, 它扮演的角色相当于foreach循环内嵌的代码, 另一部分则是对3个Hash应用API函数的调用.

typedef int (*apply_func_t)(void *pDest TSRMLS_DC);  
void zend_hash_apply(HashTable *ht,  
        apply_func_t apply_func TSRMLS_DC);

Hash apply族函数中最简单的格式是通过迭代ht, 将当前迭代到的元素指针作为参数pDest传递, 调用apply_func.

typedef int (*apply_func_arg_t)(void *pDest,  
                            void *argument TSRMLS_DC);  
void zend_hash_apply_with_argument(HashTable *ht,  
        apply_func_arg_t apply_func, void *data TSRMLS_DC);

下一种Hash apply的格式是与迭代元素一起传递另外一个参数. 这通常用于多目的的Hash apply函数, 它的行为依赖于额外的参数而不同.

回调函数并不关心使用哪个迭代函数, 它只有3种可能的返回值:

下面是一个简单的用户空间foreach()循环:

<?php  
foreach($arr as $val) {  
    echo "The value is: $val\n";  
}  
?>

它被翻译成对应的C代码如下:

int php_sample_print_zval(zval **val TSRMLS_DC)  
{  
    /* 复制一份zval, 使得原来的结构不被破坏 */  
    zval tmpcopy = **val;  
  
    zval_copy_ctor(&tmpcopy);  
    /* 重置引用计数并进行类型转换 */  
    INIT_PZVAL(&tmpcopy);  
    convert_to_string(&tmpcopy);  
    /* 输出 */  
  
    php_printf("The value is: ");  
    PHPWRITE(Z_STRVAL(tmpcopy), Z_STRLEN(tmpcopy));  
    php_printf("\n");  
    /* 释放拷贝 */  
    zval_dtor(&tmpcopy);  
    /* 继续下一个 */  
    return ZEND_HASH_APPLY_KEEP;  
}

我们使用下面的函数进行迭代:

zend_hash_apply(arrht, php_sample_print_zval TSRMLS_CC);

虽然函数的调用只使用一级间访, 但它定义的参数仍然是zval **, 这是因为变量在HashTable中存储时, 实际上只拷贝了zval 的指针, 而HashTable自身并没有触及zval的内容. 如果还不清楚为什么这样做, 请参考第2章.

typedef int (*apply_func_args_t)(void *pDest,  
        int num_args, va_list args, zend_hash_key *hash_key);  
void zend_hash_apply_with_arguments(HashTable *ht,  
        apply_func_args_t apply_func, int numargs, ...);

为了在循环过程中和值一起接受key, 就必须使用zend_hash_apply()的第三种格式. 例如, 扩展上面的理智, 支持key的输出:

<?php  
foreach($arr as $key => $val) {  
    echo "The value of $key is: $val\n";  
}  
?>

当前的迭代回调无法处理$key的获取. 切换到zend_hash_apply_with_arguments(), 回调函数的原型和实现修改如下:

int php_sample_print_zval_and_key(zval **val,  
        int num_args, va_list args, zend_hash_key *hash_key)  
{  
    /* 复制zval以使原来的内容不被破坏 */  
    zval tmpcopy = **val;  
    /* 输出函数需要tsrm_ls */  
    TSRMLS_FETCH();  
  
    zval_copy_ctor(&tmpcopy);  
    /* 重置引用计数并进行类型转换 */  
    INIT_PZVAL(&tmpcopy);  
    convert_to_string(&tmpcopy);  
    /* 输出 */  
    php_printf("The value of ");  
    if (hash_key->nKeyLength) {  
        /* 关联类型的key */  
        PHPWRITE(hash_key->arKey, hash_key->nKeyLength);  
    } else {  
        /* 数值key */  
        php_printf("%ld", hash_key->h);  
    }  
    php_printf(" is: ");  
    PHPWRITE(Z_STRVAL(tmpcopy), Z_STRLEN(tmpcopy));  
    php_printf("\n");  
    /* 释放拷贝 */  
    zval_dtor(&tmpcopy);  
    /* 继续 */  
    return ZEND_HASH_APPLY_KEEP;  
}

译注: 译者使用的php-5.4.9中不需要TSRMLS_FETCH()一行, 回调原型中已经定义了TSRMLS_DC.

使用下面的函数调用进行迭代:

zend_hash_apply_with_arguments(arrht,  
                    php_sample_print_zval_and_key, 0);

这个示例比较特殊, 不需要传递参数; 对于从va_list args中提取可变参数, 请参考POSIX文档的va_start(), va_arg(), va_end().

注意用于测试一个key是否是关联类型的, 使用的是nKeyLength, 而不是arKey. 这是因为在Zend HashTable的实现中, 可能会在arKey中遗留数据. 同时, nKeyLength还可以安全的处理空字符串的key(比如$foo[''] = 'bar';), 因为nKeyLength包含了末尾的NULL字节.

向前推移的迭代

我们也可以不使用回调进行HashTable的迭代. 此时, 你就需要记得HashTable中一个常常被忽略的概念: 内部指针.

在用户空间, 函数reset(), key(), current(), next(), prev(), each(), end()可以用于访问数组内的元素, 它们依赖于一个不可访问的"当前"位置.

<?php  
    $arr = array(&#39;a&#39;=>1, &#39;b&#39;=>2, &#39;c&#39;=>3);  
    reset($arr);  
    while (list($key, $val) = each($arr)) {  
        /* Do something with $key and $val */  
    }  
    reset($arr);  
    $firstkey = key($arr);  
    $firstval = current($arr);  
    $bval = next($arr);  
    $cval = next($arr);  
?>

这些函数都是对同名的Zend Hash API函数的封装.

/* reset() */  
void zend_hash_internal_pointer_reset(HashTable *ht);  
/* key() */  
int zend_hash_get_current_key(HashTable *ht,  
        char **strIdx, unit *strIdxLen,  
        ulong *numIdx, zend_bool duplicate);  
/* current() */  
int zend_hash_get_current_data(HashTable *ht, void **pData);  
/* next()/each() */  
int zend_hash_move_forward(HashTable *ht);  
/* prev() */  
int zend_hash_move_backwards(HashTable *ht);  
/* end() */  
void zend_hash_internal_pointer_end(HashTable *ht);  
/* Other... */  
int zend_hash_get_current_key_type(HashTable *ht);  
int zend_hash_has_more_elements(HashTable *ht);

next(), prev(), end()三个用户空间语句实际上映射到的是内部的向前/向后移动, 接着调用zend_hash_get_current_data(). each()执行和next()相同的步骤, 但是同时调用zend_hash_get_current_key()并返回.

通过向前移动的方式实现的迭代实际上和foreach()循环更加相似, 下面是对前面print_zval_and_key示例的再次实现:

void php_sample_print_var_hash(HashTable *arrht)  
{  
  
    for(zend_hash_internal_pointer_reset(arrht);  
    zend_hash_has_more_elements(arrht) == SUCCESS;  
    zend_hash_move_forward(arrht)) {  
        char *key;  
        uint keylen;  
        ulong idx;  
        int type;  
        zval **ppzval, tmpcopy;  
  
        type = zend_hash_get_current_key_ex(arrht, &key, &keylen,  
                                                  &idx, 0, NULL);  
        if (zend_hash_get_current_data(arrht, (void**)&ppzval) == FAILURE) {  
            /* 应该永远不会失败, 因为key是已知存在的. */  
            continue;  
        }  
        /* 复制zval以使原来的内容不被破坏 */  
        tmpcopy = **ppzval;  
        zval_copy_ctor(&tmpcopy);  
        /* 重置引用计数, 并进行类型转换 */  
        INIT_PZVAL(&tmpcopy);  
        convert_to_string(&tmpcopy);  
        /* 输出 */  
        php_printf("The value of ");  
        if (type == HASH_KEY_IS_STRING) {  
            /* 关联类型, 输出字符串key. */  
            /* 译注: 这里传递给PHPWRITE的keylen应该要减1才合适, 因为HashTable中的key长度包含 
             * 末尾的NULL字节, 而正常的php字符串长度不包含这个NULL字节, 不过这里打印通常不会有 
             * 问题, 因为NULL字节一般打印出是空的 */  
            PHPWRITE(key, keylen);  
        } else {  
            /* 数值key */  
            php_printf("%ld", idx);  
        }  
        php_printf(" is: ");  
        PHPWRITE(Z_STRVAL(tmpcopy), Z_STRLEN(tmpcopy));  
        php_printf("\n");  
        /* 释放拷贝 */  
        zval_dtor(&tmpcopy);  
    }  
}

这个代码片段对你来说应该是比较熟悉的了. 没有接触过的是zend_hash_get_current_key()的返回值. 调用时, 这个函数可能返回下表中3个返回值之一:

保留内部指针

在迭代HashTable时, 尤其是当它包含用户空间变量时, 少数情况下会碰到循环引用或者说自交的循环. 如果一个迭代上下文的循环开始后, HashTable的内部指针被调整, 接着内部启动了对同一个HashTable的迭代循环, 它就会擦掉原有的当前内部指针位置, 内部的迭代将导致外部的迭代被异常终止.

对于使用zend_hash_apply样式的实现以及自定义的向前移动的用法, 均可以通过外部的HashPosition变量的方式来解决这个问题.

前面列出的zend_hash_*()函数均有对应的zend_hash_*_ex()实现, 它们可以接受一个HashPosition类型的参数. 因为HashPosition变量很少在短生命周期的循环之外使用, 因此将它定义为直接变量就足够了. 接着可以取地址进行使用, 如下示例:

void php_sample_print_var_hash(HashTable *arrht)  
{  
    HashPosition pos;  
    for(zend_hash_internal_pointer_reset_ex(arrht, &pos);  
    zend_hash_has_more_elements_ex(arrht, &pos) == SUCCESS;  
    zend_hash_move_forward_ex(arrht, &pos)) {  
        char *key;  
        uint keylen;  
        ulong idx;  
        int type;  
  
        zval **ppzval, tmpcopy;  
  
        type = zend_hash_get_current_key_ex(arrht,  
                                &key, &keylen,  
                                &idx, 0, &pos);  
        if (zend_hash_get_current_data_ex(arrht,  
                    (void**)&ppzval, &pos) == FAILURE) {  
            /* 应该永远不会失败, 因为key已知是存在的 */  
            continue;  
        }  
        /* 复制zval防止原来的内容被破坏 */  
        tmpcopy = **ppzval;  
        zval_copy_ctor(&tmpcopy);  
        /* 重置引用计数并进行类型转换 */  
        INIT_PZVAL(&tmpcopy);  
        convert_to_string(&tmpcopy);  
        /* 输出 */  
        php_printf("The value of ");  
        if (type == HASH_KEY_IS_STRING) {  
            /* 关联方式的字符串key */  
            PHPWRITE(key, keylen);  
        } else {  
            /* 数值key */  
            php_printf("%ld", idx);  
        }  
        php_printf(" is: ");  
        PHPWRITE(Z_STRVAL(tmpcopy), Z_STRLEN(tmpcopy));  
        php_printf("\n");  
        /* 释放拷贝 */  
        zval_dtor(&tmpcopy);  
    }  
}

通过这些轻微的修改, HashTable真正的内部指针将被保留, 它就可以保持为刚刚进入函数时的状态不变. 在用户空间变量的HashTable(数组)上工作时, 这些额外的步骤很可能就是决定脚本执行结果是否与预期一致的关键点.

析构

你需要关注的析构函数只有4个. 前两个用于从一个HashTable中移除单个元素:

int zend_hash_del(HashTable *ht, char *arKey, uint nKeyLen);  
int zend_hash_index_del(HashTable *ht, ulong h);

你应该可以猜到, 这里体现了HashTable独立的索引设计, 它为关联和数值方式的索引元素分别提供了删除函数. 两者均应该返回SUCCESS或FAILURE.

回顾前面, 当一个元素从HashTable中移除时, HashTable的析构函数将被调用, 传递的参数是指向元素的指针

void zend_hash_clean(HashTable *ht);

要完全清空HashTable时, 最快的方式是调用zend_hash_clean(), 它将迭代所有的元素调用zend_hash_del():

void zend_hash_destroy(HashTable *ht);

通常, 清理HashTable时, 你会希望将它整个都清理掉. 调用zend_hash_destroy()将会执行zend_hash_clean()的所有步骤, 同时还会释放zend_hash_init()分配的其他结构.

下面的代码演示了一个完整的HashTable生命周期:

int sample_strvec_handler(int argc, char **argv TSRMLS_DC)  
{  
    HashTable *ht;  
    /* 分配一块内存用于HashTable结构 */  
    ALLOC_HASHTABLE(ht);  
    /* 初始化HashTable的内部状态 */  
    if (zend_hash_init(ht, argc, NULL,  
                        ZVAL_PTR_DTOR, 0) == FAILURE) {  
        FREE_HASHTABLE(ht);  
        return FAILURE;  
    }  
    /* 将传入的字符串数组, 顺次以字符串的zval *放入到HashTable中 */  
    while (argc) {  
        zval *value;  
        MAKE_STD_ZVAL(value);  
        ZVAL_STRING(value, argv[argc], 1);  
        argv++;  
        if (zend_hash_next_index_insert(ht, (void**)&value,  
                            sizeof(zval*)) == FAILURE) {  
            /* 添加失败则静默的跳过 */  
            zval_ptr_dtor(&value);  
        }  
    }  
    /* 执行一些其他工作(业务) */  
    process_hashtable(ht);  
    /* 销毁HashTable, 释放所有需要释放的zval */  
    zend_hash_destroy(ht);  
  
    /* 释放HashTable自身 */  
    FREE_HASHTABLE(ht);  
    return SUCCESS;  
}

排序, 比较

在Zend Hash API中还存在其他一些回调. 第一个是用来处理同一个HashTable中两个元素或者不同HashTable相同位置元素的比较的:

typedef int (*compare_func_t)(void *a, void *b TSRMLS_DC);

就像用户空间的usort()回调一样, 这个函数期望你使用自己的逻辑比较两个值a和b, 返回-1表示a小于b, 返回1表示b小于a, 返回0表示两者相等.

int zend_hash_minmax(HashTable *ht, compare_func_t compar,  
                        int flag, void **pData TSRMLS_DC);

使用这个回调的最简单的API函数是zend_hash_minmax(), 顾名思义, 它将基于多次对比较回调的调用, 最终返回HashTable的最大值/最小值元素. flag为0时返回最小值, flag非0时返回最大值.

下面的例子中, 对已注册的用户空间函数以函数名排序, 并返回(函数名)最小和最大的函数(大小写不敏感):

int fname_compare(zend_function *a, zend_function *b TSRMLS_DC)  
{  
    return strcasecmp(a->common.function_name, b->common.function_name);  
}  
void php_sample_funcname_sort(TSRMLS_D)  
{  
    zend_function *fe;  
    if (zend_hash_minmax(EG(function_table), fname_compare,  
                0, (void **)&fe) == SUCCESS) {  
        php_printf("Min function: %s\n", fe->common.function_name);  
    }  
    if (zend_hash_minmax(EG(function_table), fname_compare,  
                1, (void **)&fe) == SUCCESS) {  
        php_printf("Max function: %s\n", fe->common.function_name);  
    }  
}

译注: 原书中的示例在译者的环境(php-5.4.9)中不能运行, 经过跟踪检查, 发现zend_hash_minmax传递给fname_compare的两个参数类型是Bucket **, 而非这里的zend_function *, 为了避免读者疑惑, 下面给出译者修改后的示例供参考.

static int sample_fname_compare(Bucket **p1, Bucket **p2 TSRMLS_DC) {  
    zend_function   *zf1, *zf2;    zf1 = (zend_function *)(*p1)->pData;  
    zf2 = (zend_function *)(*p2)->pData;  
    return strcasecmp(zf1->common.function_name, zf2->common.function_name);  
}  
PHP_FUNCTION(sample_funcname_sort)  
{  
    zend_function   *zf;  
  
    if ( zend_hash_minmax(EG(function_table), (compare_func_t)sample_fname_compare, 0, (void **)&zf TSRMLS_CC) == SUCCESS )  
        php_printf("Min function: %s\n", zf->common.function_name);    
        if ( zend_hash_minmax(EG(function_table), (compare_func_t)sample_fname_compare, 1, (void **)&zf TSRMLS_CC) == SUCCESS )  
        php_printf("Max function: %s\n", zf->common.function_name);  
          
    RETURN_TRUE;  
}

哈希比较函数还会用于zend_hash_compare()中, 它会评估两个HashTable中的每个元素进行比较. 如果hta大于htb, 返回1, 如果htb大于hta, 返回-1, 如果两者相等, 返回0.

int zend_hash_compare(HashTable *hta, HashTable *htb,  
        compare_func_t compar, zend_bool ordered TSRMLS_DC);

这个函数首先会比较两个HashTable的元素个数. 如果其中一个元素个数多于另外一个, 则直接认为它比另外一个大, 快速返回.

接下来, 循环遍历hta. 如果设置了ordered标记, 它将hta的第一个元素和htb的第一个元素的key长度进行比较, 接着使用memcmp()二进制安全的比较key内容. 如果key相等, 则使用提供的compar回调函数比较两个元素的值.

如果没有设置ordered标记, 则遍历hta得到一个元素后, 从htb中查找key/index相等的元素, 如果存在, 对它们的值调用传入的compar回调函数, 否则, 则认为hta比htb大, 直接返回1.

如果上面的处理结束后, hta和htb一致都被认为是相等的, 则从hta中遍历下一个元素重复上面过程, 直到找到不同, 或者所有的元素耗尽, 此时认为它们相等返回0.

这一族的回调函数中第二个是排序函数:

typedef void (*sort_func_t)(void **Buckets, size_t numBuckets,  
            size_t sizBucket, compare_func_t comp TSRMLS_DC);

这个回调将被触发一次, 它以向量方式接受HashTable中所有Bucket(元素)的指针. 这些Bucket可以在向量内部按照排序函数自己的逻辑(与是否使用比较回调无关)进行交换. 实际上, sizBucket总是等于sizeof(Bucket *)

除非你计划实现自己的冒泡或其他排序算法, 否则不需要自己实现排序函数. php内核中已经有一个预定义的排序函数: zend_qsort, 它可以作为zend_hash_sort()的回调函数, 这样, 你就只需要实现比较函数.

int zend_hash_sort(HashTable *ht, sort_func_t sort_func,  
        compare_func_t compare_func, int renumber TSRMLS_DC);

zend_hash_sort()的最后一个参数被设置后, 将会导致在排序后, 原来的关联key以及数值下表都被按照排序结果重置为数值索引. 用户空间的sort()实现就以下面的方式使用了zend_hash_sort():

zend_hash_sort(target_hash, zend_qsort,  
                        array_data_compare, 1 TSRMLS_CC);

不过, array_data_compare只是一个简单的compare_func_t实现, 它只是依据HashTable中zval *的值进行排序.

zval *数组API

你在开发php扩展时, 95%以上的HashTable引用都是用于存储和检索用户空间变量的. 反过来说, 你的多数HashTable自身都将被包装在zval中.

简单的数组创建

为了辅助这些常见的HashTable的创建和操作, PHP API暴露了一些简单的宏和辅助函数, 我们从array_init(zval *arrval)开始看. 这个函数分配了一个HashTable, 以适用于用户空间变量哈希的参数调用zend_hash_init(), 并将新创建的结构设置到zval *中.

这里不需要特殊的析构函数, 因为在zval最后一个refcount失去后, 通过调用zval_dtor()/zval_ptr_dtor(), 引擎会自动的调用zend_hash_destroy()和FREE_HASHTABLE().

联合array_init()方法和第6章"返回值"中已经学习的从函数返回值的技术:

PHP_FUNCTION(sample_array)  
{  
    array_init(return_value);  
}

因为return_value是一个预分配的zval *, 因此不需要在它上面做其他工作. 并且由于它唯一的引用就是你的函数返回, 因此不要担心它的清理.

简单的数组构造

和所有的HashTable一样, 你需要迭代增加元素来构造数组. 由于用户空间变量的特殊性, 你需要回到你已经知道的C语言中的基础数据类型. 有3种格式的函数: add_assoc_*(), add_index_*(), add_next_index_*(), 对于已知的ZVAL_*(), RETVAL_*(), RETURN_*()宏所支持的每种数据类型, 都有对应的这3种格式的函数. 例如:

add_assoc_long(zval *arrval, char *key, long lval);  
add_index_long(zval *arrval, ulong idx, long lval);  
add_next_index_long(zval *arrval, long lval);

每种情况中, 数组zval *都是第一个参数, 接着是关联key名或数值下标, 或者对于next_index变种来说, 两者都不需要. 最后是数据元素自身, 最终它将被包装为一个新分配的zval *, 并使用zend_hash_update(), zend_hash_index_update(), zend_hash_next_index_insert()增加到数组中.

add_assoc_*()函数变种以及它们的函数原型如下. 其他两种格式则将assoc替换为index或next_index, 并对应调整key/index参数即可.

add_assoc_null(zval *aval, char *key);  
add_assoc_bool(zval *aval, char *key, zend_bool bval);  
add_assoc_long(zval *aval, char *key, long lval);  
add_assoc_double(zval *aval, char *key, double dval);  
add_assoc_string(zval *aval, char *key, char *strval, int dup);  
add_assoc_stringl(zval *aval, char *key,  
                    char *strval, uint strlen, int dup);  
add_assoc_zval(zval *aval, char *key, zval *value);

这些函数的最后一个版本允许你自己准备一个任意类型(包括资源, 对象, 数组)的zval, 将它增加到数组中. 现在尝试在你的sample_array()函数中做一些额外的工作.

PHP_FUNCTION(sample_array)  
{  
    zval *subarray;  
  
    array_init(return_value);  
    /* 增加一些标量值 */  
    add_assoc_long(return_value, "life", 42);  
    add_index_bool(return_value, 123, 1);  
    add_next_index_double(return_value, 3.1415926535);  
    /* 增加一个静态字符串, 由php去复制 */  
    add_next_index_string(return_value, "Foo", 1);  
    /* 手动复制的字符串 */  
    add_next_index_string(return_value, estrdup("Bar"), 0);  
  
    /* 创建一个子数组 */  
    MAKE_STD_ZVAL(subarray);  
    array_init(subarray);  
    /* 增加一些数值 */  
    add_next_index_long(subarray, 1);  
    add_next_index_long(subarray, 20);  
    add_next_index_long(subarray, 300);  
    /* 将子数组放入到父数组中 */  
    add_index_zval(return_value, 444, subarray);  
}

如果在这个函数的返回值上调用var_dump()将得到下面输出:

$ php -r 'var_dump(sample_array());'  
array(6) {  
  ["life"]=>  
  int(42)  
  [123]=>  
  bool(true)  
  [124]=>  
  float(3.1415926535)  
  [125]=>  
  string(3) "Foo"  
  [126]=>  
  string(3) "Bar"  
  [444]=>  
  array(3) {  
    [0]=>  
    int(1)  
    [1]=>  
    int(20)  
    [2]=>  
    int(300)  
  }  
}

这些add_*()函数还可以用于简单对象的内部公共属性. 在第10章"php 4对象"中我们可以看到它们.

小结

你已经花费了一些时间学习了很长的一章, 本章介绍了Zend引擎和php内核中仅次于zval *的通用数据结构. 本章还比较了不同的数据存储机制, 并介绍了很多未来将多次使用的API.

现在你已经有了足够的积累, 可以实现一些相当一部分标准扩展了. 后面的几章将完成剩余的zval数据类型(资源和对象)的学习.

以上就是 [翻译][php扩展开发和嵌入式]第8章-在数组和哈希表上工作的内容，更多相关内容请关注PHP中文网（www.php.cn）！