编程语言的类型可分为强类型和弱类型两种,强类型变量声明时已确定变量类型,运行过程中不能随便将其他类型变量赋值于它(涉及到类型强制转换等除外),C/C++/Java属于强类型语言;而PHP/Python/JS属于弱类型语言,变量可以表示任意类型。本文介绍PHP变量的内部实现数据结构,如何表示各种数据类型。

1、PHP变量类型及存储结构
PHP虽然是弱类型语言,我们在使用时也会指明它的类型,比如bool/array/object/resource/null等。PHP底层使用C语言实现,变量的值存储到以下所示zval结构体中:

typedef struct _zval_struct zval;
struct _zval_struct {
    zvalue_value value;         /* 存储变量的值 */
    zend_uint refcount__gc;     /* 表示引用计数 */
    zend_uchar type;            /* 变量具体的类型 */
    zend_uchar is_ref__gc;      /* 表示是否为引用 */ 
};

变量类型type: IS_NULL、IS_BOOL、IS_LONG、IS_DOUBLE、IS_STRING、IS_ARRAY、IS_OBJECT和IS_RESOURCE 之一。

前面提到变量的值存储在zvalue_value联合体中,结构体定义如下:

typedef union _zvalue_value {
    long lval;                  /* long */
    double dval;                /* double */
    struct { 
        char *val;
        int len;
    } str;                      /* string*/
    HashTable *ht;              /* hash table */
    zend_object_value obj;      /* object */
} zvalue_value;

PHP的弱变量容器的实现方式是兼容并包的形式体现,针对每种类型的变量都有其对应的标记和存储空间。 使用强类型的语言在效率上通常会比弱类型高,因为很多信息能在运行之前就能确定,这也能帮助排除程序错误。 而这带来的问题是编写代码相对会受制约。

2、哈希表(HashTable)
PHP内核中的哈希表是十分重要的数据结构,PHP的大部分的语言特性都是基于哈希表实现的, 例如:变量的作用域、函数表、类的属性、方法等,Zend引擎内部的很多数据都是保存在哈希表中的。哈希表是一种通过哈希函数,将特定的键映射到特定值的一种数据结构,它维护键和值之间一一对应关系。哈希表可以理解为数组的扩展或者关联数组,通过hash(key)映射到元素存储位置。
20160912224513.jpg

HashTable实现的重点是hash函数和冲突的解决,hash函数通过key得到哈希;出现冲突时如何解决要依据实际场景。装载因子是哈希表保存的元素数量和哈希表容量的比,通常采用拉链法解决冲突的哈希表的装载 因子最好不要大于1,而采用开放寻址法的哈希表最好不要大于0.5。

3、PHP HashTable
PHP使用如下两个数据结构来实现哈希表,HashTable结构体用于保存整个哈希表需要的基本信息, 而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;

HashTable中的nNumOfElements字段很好理解,每插入一个元素或者unset删掉元素时会更新这个字段。 这样在进行count()函数统计数组元素个数时就能快速的返回。

下面是Bucket的数据结构,Bucket保存了hash结点元素数据。

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字符串,这个字段只能定义在最后,实现变长结构体
    const char *arKey;              
} Bucket;

h字段保存哈希表key哈希后的值,arKey保存key值。在Zend引擎中HashTable的使用非常频繁,这得益于他良好的查找性能,Zend引擎的哈希表实现是哈希表和双链表的混合实现,这也是为了方便哈希表的遍历。

4、扩展开发demo

  • zend_hash_index_find:普通数组
    zval **zv_dest;
    if (zend_hash_index_find(array->value.ht,idx,(void **) &zv_dest) == SUCCESS)
    {
        php_printf("%s\n",Z_LVAL(**zv_dest));
    }
  • zend_hash_find:关联数组
    zval **zv_dest;
    if(zend_hash_find(array->value.ht,"key",sizeof("key"),(void **) &zv_dest)==SUCCESS)
    {
        php_printf("%s\n",Z_STRVAL(**zv_dest));
    }

后记:很久没碰数据结构,初看PHP HashTable花了些时间。不过TIPI总结的很详细,可惜的是TIPI后面可能不会更新了,本文的许多内容也参考TIPI。如果不熟悉底层数据结构,扩展开发中zval取值赋值比较麻烦,好在Zend提供了许多宏,方便开发者进行zval取值、赋值及类型判断。

参考资料:

标签: Zend, 内核, 变量

评论已关闭