PHP扩展开发（五）哈希表和数组API

用户2131907

发布于 2019-02-27 13:32:49

8830

发布于 2019-02-27 13:32:49

Zend Hash API是以zend_hash_*样式的函数定义，注意的是，这里的zend_hash_*并不是函数，而是宏定义，对应的函数一般为_zend_hash_*，哈希表相关操作源文件在 zend_hash.h/zend_hash.c 中。

哈希表结构

struct _hashtable;

typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 整个hash表的下一元素
    struct bucket *pListLast;   // 整个哈希表该元素的上一个元素
    struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素
    struct bucket *pLast;       // 同一个哈希bucket的上一个元素
    // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
    char arKey[1];
} Bucket;

typedef struct _hashtable {
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

哈希表操作API

哈希表创建

int zend_hash_init(
    HashTable *ht,              /* 声明的HashTable变量指针 */
    uint nSize,                 /* 哈希表可能存储的最大元素数量 */
    hash_func_t pHashFunction,  /* 使用的哈希函数，现在一律使用NULL（DJBX33A） */
    dtor_func_t pDestructor,    /* 从哈希表移除元素时的回调函数 */
    zend_bool persistent        /* 该哈希表是持久化的还是每请求的 */
)

其中，nSize参数要为实际可能存储的元素数，如果超过该数目，将重新扩展哈希表为2倍大小。nSize 应该为2的整数倍，如果不是的话，将会自动设置为下一个2的整数倍数。

nSize取值: nSize = pow(2, ceil(log(nSize, 2)));

这里的pDestructor 参数是一个函数指针，该函数会在从哈希表移除元素的时候调用，比如zend_hash_del， zend_hash_update，该函数的原型必须为：

void method_name(void *pElement); /* pElement为要移除的元素 */

另外，最后一个参数persistent如果设置为持久化的话，该哈希表变量ht必须是使用pemalloc()分配内存的。

例如，在每个PHP请求开始的时候，都会对EG(symbol_table)全局符号表进行初始化，这时会调用该函数：

zend_hash_init(&EG(symbol_table), 50, NULL, ZVAL_PTR_DTOR, 0);

这里的nSize为50，因此会被自动扩展为64。

哈希表填充

对哈希表的填充操作，主要有四个函数：

int zend_hash_add(
  HashTable *ht,        /* 要操作的哈希表指针 */
  char *arKey,          /* 数组的Key，这里是字符型key */
  uint nKeyLen,         /* 数组Key长度 */
  void **pData,         /* 实际存储的数据 */
  uint nDataSize,       /* 数据大小 */
  void *pDest           /* 如果指定，则为指向data的副本的指针 */
);
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);

这里需要注意的是，前两个函数是对非数字key的数组操作的，后两个是对数值索引数组操作的。

zend_hash_add和zend_hash_update的区别在于，一个是新增元素，一个是更新元素，如果arKey 已经存在了的话，zend_hash_add将会失败。

/* $foo['bar'] = 'baz'; */
zend_hash_add(fooHashTbl, "bar", sizeof("bar"), &barZval, sizeof(zval*), NULL);

使用zend_hash_index_update() 的例子:

ulong nextid = zend_hash_next_free_element(ht);
zend_hash_index_update(ht, nextid, &data, sizeof(data), NULL);

哈希表查找

由于哈希表有两种使用方式（数值索引/关联索引），因此，对于哈希表查找，也有两种查找函数：

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

例如：

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) {
       /* Should never happen */
       return;
   }
   if(zend_hash_index_find(ht, targetID, (void **)&data2) == FAILURE) {
       /* Very unlikely since we just added this element */
       return;
   }
   /* data1 != data2, 但是 *data1 == *data2 */
}

相比查找数组中的值，通常，我们还会经常用到判断数组中是否存在某个索引，这时，使用下面两个函数：

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

例如：

/* 该部分代码实现功能与isset($foo)类似 */
if (zend_hash_exists(EG(active_symbol_table),
                                "foo", sizeof("foo"))) {
    /* $foo is set */
} else {
    /* $foo does not exist */
}

快速填充和查找

要实现快速的填充和查找，这里采用的方法是首先使用zend_get_hash_value()函数计算出哈希索引值，在接下来对数组的操作中，直接使用quick系列函数，避免每次操作都重新计算哈希值。

ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength);

快速操作函数如下：

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);

int zend_hash_quick_del(HashTable *ht, char *arKey, unit nKeyLength, ulong hashval);

例如：

void php_sample_hash_copy(HashTable *hta, HashTable *htb,
                    char *arKey, uint nKeyLen TSRMLS_DC)
{
    /* 事先计算出key的哈希值 */
    ulong hashval = zend_get_hash_value(arKey, nKeyLen);
    zval **copyval;

    if (zend_hash_quick_find(hta, arKey, nKeyLen,
                hashval, (void**)&copyval) == FAILURE) {
        /* arKey doesn't actually exist */
        return;
    }
    /* The zval* is about to be owned by another hash table */
    (*copyval)->refcount++;
    zend_hash_quick_update(htb, arKey, nKeyLen, hashval,
                copyval, sizeof(zval*), NULL);
}

zval* 数组API

在PHP扩展中，对哈希表的操作中95%的操作都是对用户空间的数据进行存取。因此PHP创建了一系列简单的宏和助手函数用于对数组进行操作。

数组创建

int array_init(zval *arg);

该函数原型实际上是zend API定义的一个宏，其实现代码如下所示：

/* zend_API.h:347 */
#define array_init(arg)         _array_init((arg), 0 ZEND_FILE_LINE_CC)

/* zend_API.c:958 */
ZEND_API int _array_init(zval *arg, uint size ZEND_FILE_LINE_DC) /* {{{ */
{
    ALLOC_HASHTABLE_REL(Z_ARRVAL_P(arg)); /* 首先分配一个哈希表 */

    /* 调用zend_hash_init完成哈希表的初始化 */
    _zend_hash_init(Z_ARRVAL_P(arg), size, NULL, ZVAL_PTR_DTOR, 0 ZEND_FILE_LINE_RELAY_CC);
    Z_TYPE_P(arg) = IS_ARRAY;/* 设置变量的数据类型为数组 */
    return SUCCESS;
}

使用范例:

PHP_FUNCTION(sample_array)
{
    array_init(return_value);
}

数组填充

对与关联数组，提供了如下API：

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

注意：上述API为宏定义，为了直观展示，用函数定义的形式展现。

对于数值索引数组，提供了如下API，这些API都是函数定义：

ZEND_API int add_index_long(zval *arg, ulong idx, long n);
ZEND_API int add_index_null(zval *arg, ulong idx);
ZEND_API int add_index_bool(zval *arg, ulong idx, int b);
ZEND_API int add_index_resource(zval *arg, ulong idx, int r);
ZEND_API int add_index_double(zval *arg, ulong idx, double d);
ZEND_API int add_index_string(zval *arg, ulong idx, const char *str, int duplicate);
ZEND_API int add_index_stringl(zval *arg, ulong idx, const char *str, uint length, int duplicate);
ZEND_API int add_index_zval(zval *arg, ulong index, zval *value);

注意： Zend提供的数组API函数并不仅仅只有这些，还有更多方便实用的API请查看源文件: zend_API.h 346-431行。

范例：

PHP_FUNCTION(sample_array)
{
    zval *subarray;

    array_init(return_value);

    /* Add some scalars */
    add_assoc_long(return_value, "life", 42);
    add_index_bool(return_value, 123, 1);
    add_next_index_double(return_value, 3.1415926535);

    /* Toss in a static string, dup'd by PHP */
    add_next_index_string(return_value, "Foo", 1);

    /* Now a manually dup'd string */
    add_next_index_string(return_value, estrdup("Bar"), 0);

    /* Create a subarray */
    MAKE_STD_ZVAL(subarray);
    array_init(subarray);

    /* Populate it with some numbers */
    add_next_index_long(subarray, 1);
    add_next_index_long(subarray, 20);
    add_next_index_long(subarray, 300);

    /* Place the subarray in the parent */
    add_index_zval(return_value, 444, subarray);
}

上述代码片段创建的数组var_dump之后如下:

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)
  }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-03-12，如有侵权请联系 cloudcommunity@tencent.com 删除

api