PHP扩展开发-数组的使用以及HashTable简介

1      数组

本节我们讲一下php的数组，在php中，数组使用HashTable实现的。本节中我们先详细的介绍一下HashTable，然后再讲讲如何使用HastTable

1.1     变长结构体

所谓的变长结构体，其实是我们C语言结构体的一种特殊用法，并没有什么新奇之处。我们先来看一下变长结构体的一种通用定义方法。

typedef struct bucket {

    int n;

    char key[30];

    char value[1];

} Bucket;

我们定义了一个结构体Bucket，我们希望用这个结构体存放学生的个人简介。其中key用来存在学生的姓名，value用来存放学生的简介。大家可能很好奇，我们的value声明了长度为1. 1个char能存多少信息呀？

         其实，对于变长结构体，我们在使用的使用不能直接定义变量，例如：Bucket bucket; 您要是这样使用，value肯定存储不了多少信息。对于变长结构体，我们在使用的时候需要先声明一个变长结构体的指针，然后通过malloc函数分配函数空间，我们需要用到的空间长度是多少，我们就可以malloc多少。通用的使用方法如下：

Bucket* pBucket;

pBucket = malloc(sizeof(Bucket) + n * sizeof(char));

其中n就是你要使用value的长度。如果这样使用的话，value指向的字符串不久变长了吗！

 

1.2     Hashtable简介

我们先看一下HashTable的定义

struct _hashtable;

 

typedef struct bucket {

    ulong h;//当元素是数字索引时使用

    uint nKeyLength;//当使用字符串索引时，这个变量表示索引的长度，索引（字符串）保存在最后一个元素aKey

    void *pData;//用来指向保存的数据，如果保存的数据是指针的话，pDataPtr就指向这个数据，pData指向pDataPtr

    void *pDataPtr;

    struct bucket *pListNext; //上一个元素

    struct bucket *pListLast; //下一个元素

    struct bucket *pNext; //指向下一个bucket的指针

    struct bucket *pLast; //指向上一个bucket的指针

    char arKey[1]; //必须放在最后，主要是为了实现变长结构体

} Bucket;

 

typedef struct _hashtable {

    uint nTableSize;             //哈希表的大小

    uint nTableMask;             //数值上等于nTableSize- 1

    uint nNumOfElements;         //记录了当前HashTable中保存的记录数

    ulong nNextFreeElement;      //指向下一个空闲的Bucket

    Bucket *pInternalPointer;    //这个变量用于数组反转

    Bucket *pListHead;            //指向Bucket的头

    Bucket *pListTail;            //指向Bucket的尾

    Bucket **arBuckets;

    dtor_func_t pDestructor;     //函数指针，数组增删改查时自动调用，用于某些清理操作

    zend_bool persistent;         //是否持久

    unsigned char nApplyCount;

    zend_bool bApplyProtection;  //和nApplyCount一起起作用，防止数组遍历时无限递归

#if ZEND_DEBUG

    int inconsistent;

#endif

} HashTable;

希望大家能好好看看上面的定义，有些东西我将出来反而会说不明白，不如大家看看代码浅显明了。PHP的数组，其实是一个带有头结点的双向链表，其中HashTable是头，Bucket存储具体的结点信息。

1.3     HashTable内部函数分析

1.3.1    宏HASH_PROTECT_RECURSION

#defineHASH_PROTECT_RECURSION(ht)                                                     \

    if ((ht)->bApplyProtection) {                                                       \

        if ((ht)->nApplyCount++ >= 3){                                                \

            zend_error(E_ERROR, "Nestinglevel too deep - recursive dependency?"); \

        }                                                                               \

    }

这个宏主要用来防止循环引用。

1.3.2    宏ZEND_HASH_IF_FULL_DO_RESIZE

#defineZEND_HASH_IF_FULL_DO_RESIZE(ht)            \

    if ((ht)->nNumOfElements >(ht)->nTableSize) {  \

        zend_hash_do_resize(ht);                    \

    }

         这个宏的作用是检查目前HashTable中的元素个数是否大于了总的HashTable的大小，如果个数大于了HashTable的大小，那么我们就重新分配空间。我们看一下zend_hash_do_resize

static int zend_hash_do_resize(HashTable *ht)

{

    Bucket **t;

    IS_CONSISTENT(ht);

    if ((ht->nTableSize 0) {   /* Let's double the table size */

        t = (Bucket**) perealloc_recoverable(ht->arBuckets,

(ht->nTableSize persistent);

        if (t) {

            HANDLE_BLOCK_INTERRUPTIONS();

            ht->arBuckets = t;

            ht->nTableSize = (ht->nTableSize

            ht->nTableMask = ht->nTableSize - 1;

            zend_hash_rehash(ht);

            HANDLE_UNBLOCK_INTERRUPTIONS();

            return SUCCESS;

        }

        return FAILURE;

    }

    return SUCCESS;

}  

         从上面的代码中我们可以看出，HashTable在分配空间的时候，新分配的空间等于原有空间的2倍。

1.3.3    函数 _zend_hash_init

这个函数是用来初始化HashTable的，我们先看一下代码：

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)

{

    uint i = 3; //HashTable的大小默认无2的3次方

    Bucket **tmp;

 

    SET_INCONSISTENT(HT_OK);

 

    if (nSize >= 0x80000000) {

        ht->nTableSize = 0x80000000;

    } else {

        while ((1U

            i++;

        }

        ht->nTableSize = 1

    }

 

    ht->nTableMask = ht->nTableSize- 1;

    ht->pDestructor = pDestructor;

    ht->arBuckets = NULL;

    ht->pListHead = NULL;

    ht->pListTail = NULL;

    ht->nNumOfElements = 0;

    ht->nNextFreeElement = 0;

    ht->pInternalPointer = NULL;

    ht->persistent = persistent;

    ht->nApplyCount = 0;

    ht->bApplyProtection = 1;

   

    /* Uses ecalloc() so that Bucket* == NULL */

    if (persistent) {

        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket*));

        if (!tmp) {

            return FAILURE;

        }

        ht->arBuckets = tmp;

    } else {

        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket*));

        if (tmp) {

            ht->arBuckets = tmp;

        }

    }

   

    return SUCCESS;

}

可以看出，HashTable的大小被初始化为2的n次方，另外我们看到有两种内存方式，一种是calloc，一种是ecalloc_rel，这两中内存分配方式我们细讲了，有兴趣的话大家可以自己查一查。

1.3.4    函数_zend_hash_add_or_update

这个函数向HashTable中添加或者修改元素信息

ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)

{

    ulong h;

    uint nIndex;

    Bucket *p;

 

    IS_CONSISTENT(ht);

 

    if (nKeyLength

#if ZEND_DEBUG

        ZEND_PUTS("zend_hash_update: Can't put inempty key\n");

#endif

        return FAILURE;

    }

 

    h = zend_inline_hash_func(arKey, nKeyLength);

    nIndex = h & ht->nTableMask;

 

    p = ht->arBuckets[nIndex];

    while (p != NULL) {

        if ((p->h == h) && (p->nKeyLength == nKeyLength)) {

            if (!memcmp(p->arKey, arKey, nKeyLength)) {

                if (flag & HASH_ADD) {

                    return FAILURE;

                }

                HANDLE_BLOCK_INTERRUPTIONS();

#if ZEND_DEBUG

                if (p->pData == pData) {

                    ZEND_PUTS("Fatal error in zend_hash_update:p->pData == pData\n");

                    HANDLE_UNBLOCK_INTERRUPTIONS();

                    return FAILURE;

                }

#endif

                if (ht->pDestructor) {

                    ht->pDestructor(p->pData);

                }

                UPDATE_DATA(ht, p, pData, nDataSize);

                if (pDest) {

                    *pDest = p->pData;

                }

                HANDLE_UNBLOCK_INTERRUPTIONS();

                return SUCCESS;

            }

        }

        p = p->pNext;

    }

   

    p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);

    if (!p) {

        return FAILURE;

    }

    memcpy(p->arKey, arKey, nKeyLength);

    p->nKeyLength = nKeyLength;

    INIT_DATA(ht, p, pData, nDataSize);

    p->h = h;

    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);

    if (pDest) {

        *pDest = p->pData;

    }

 

    HANDLE_BLOCK_INTERRUPTIONS();

    CONNECT_TO_GLOBAL_DLLIST(p, ht);

    ht->arBuckets[nIndex] = p;

    HANDLE_UNBLOCK_INTERRUPTIONS();

 

    ht->nNumOfElements++;

    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */

    return SUCCESS;

}

1.3.5    宏CONNECT_TO_BUCKET_DLLIST

#define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \

    (element)->pNext= (list_head);                         \

    (element)->pLast= NULL;                                \

    if((element)->pNext) {                                 \

        (element)->pNext->pLast =(element);                \

    }

这个宏是将bucket加入到bucket链表中

1.3.6    其他函数或者宏定义

我们只是简单的介绍一下HashTable，如果你想细致的了解HashTable的话，建议您看看php的源代码，关于HashTable的代码在Zend/zend_hash.h 和Zend/zend_hash.c中。

zend_hash_add_empty_element 给函数增加一个空元素

zend_hash_del_key_or_index 根据索引删除元素

zend_hash_reverse_apply  反向遍历HashTable

zend_hash_copy  拷贝

_zend_hash_merge  合并

zend_hash_find  字符串索引方式查找

zend_hash_index_find  数值索引方法查找

zend_hash_quick_find  上面两个函数的封装

zend_hash_exists  是否存在索引

zend_hash_index_exists  是否存在索引

zend_hash_quick_exists  上面两个方法的封装

1.4     C扩展常用HashTable函数

虽然HashTable看起来有点复杂，但是使用却是很方便的，我们可以用下面的函数对HashTable进行初始化和赋值。

2005 年地方院校招生人数

PHP语法

C语法

意义

$arr = array()

array_init(arr);

初始化数组

$arr[] = NULL;

add_next_index_null(arr);

 

$arr[] = 42;

add_next_index_long(arr, 42);

 

$arr[] = true;

add_next_index_bool(arr, 1);

 

$arr[] = 3.14;

add_next_index_double(3.14);

 

$arr[] = ‘foo’;

add_next_index_string(arr, “foo”, 1);

1的意思进行字符串拷贝

$arr[] = $myvar;

add_next_index_zval(arr, myvar);

 

$arr[0] = NULL;

add_index_null(arr, 0);

 

$arr[1] = 42;

add_index_long(arr, 1, 42);

 

$arr[2] = true;

add_index_bool(arr, 2, 1);

 

$arr[3] = 3.14;

add_index_double(arr, 3, 3,14);

 

$arr[4] = ‘foo’;

add_index_string(arr, 4, “foo”, 1);

 

$arr[5] = $myvar;

add_index_zval(arr, 5, myvar);

 

$arr[“abc”] = NULL;

add_assoc_null(arr, “abc”);

 

$arr[“def”] = 711;

add_assoc_long(arr, “def”, 711);

 

$arr[“ghi”] = true;

add_assoc_bool(arr, ghi”, 1);

 

$arr[“jkl”] = 1.44;

add_assoc_double(arr, “jkl”, 1.44);

 

$arr[“mno”] = ‘baz’;

add_assoc_string(arr, “mno”, “baz”, 1);

 

$arr[‘pqr’] = $myvar;

add_assoc_zval(arr, “pqr”, myvar);

 

1.5     任务和实验

说了这么多，我们实验一下。

任务：返回一个数组，数组中的数据如下：

Array

(

   [0] => for test

   [42] => 123

   [for test. for test.] => 1

   [array] => Array

       (

           [0] => 3.34

       )

)

代码实现：

PHP_FUNCTION(test)

{

    zval* t;

 

    array_init(return_value);

    add_next_index_string(return_value, "for test", 1);

    add_index_long(return_value, 42, 123);

    add_assoc_double(return_value, "for test. for test.", 1.0);

   

    ALLOC_INIT_ZVAL(t);

    array_init(t);

    add_next_index_double(t, 3.34);

 

    add_assoc_zval(return_value, "array", t);

}

很简单吧，还记得return_value吗？