PHP源码阅读笔记二十八：类结构和继承

PHP源码阅读笔记二十八：类结构和继承
作为面向对象中一个非常关键也非常纠结的特性，我们需要了解一些
在PHP5中，从一开始就有了继承的概念，今天我们从PHP源码出发，了解他是怎么实现的。
在了解类的继承之前，我们需要知道类在PHP源码中是以哪种方式存储的。
找到zend/zend.h 418行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

 
struct _zend_class_entry {
	char type;
	char *name;	/* 类名 */
	zend_uint name_length;	/* 类名字符串长度 */
	struct _zend_class_entry *parent; /* 父类 */
	int refcount; /* 引用计数 */
	zend_bool constants_updated;
	zend_uint ce_flags;	/* 类的访问控制 */
 
	HashTable function_table;	/*	类的成员函数 */
	HashTable default_properties;	/*	类的默认属性 */
	HashTable properties_info;	/*	类的属性信息 如访问控制等 */
	HashTable default_static_members;/*	静态成员列表 */
	HashTable *static_members;
	HashTable constants_table;	/* 常量列表 */
	const struct _zend_function_entry *builtin_functions;
 
	union _zend_function *constructor;	/*	构造函数*/
	union _zend_function *destructor;	/*	析构函数*/
	union _zend_function *clone;		/*	克隆方法*/
 
	/*	魔术方法 */
	union _zend_function *__get;
	union _zend_function *__set;
	union _zend_function *__unset;
	union _zend_function *__isset;
	union _zend_function *__call;
	union _zend_function *__callstatic;
	union _zend_function *__tostring;
	union _zend_function *serialize_func;
	union _zend_function *unserialize_func;
 
	zend_class_iterator_funcs iterator_funcs;
 
	/* handlers */
	zend_object_value (*create_object)(zend_class_entry *class_type TSRMLS_DC);
	zend_object_iterator *(*get_iterator)(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC);
	int (*interface_gets_implemented)(zend_class_entry *iface, zend_class_entry *class_type TSRMLS_DC); /* a class implements this interface */
	union _zend_function *(*get_static_method)(zend_class_entry *ce, char* method, int method_len TSRMLS_DC);
 
	/* serializer callbacks */
	int (*serialize)(zval *object, unsigned char **buffer, zend_uint *buf_len, zend_serialize_data *data TSRMLS_DC);
	int (*unserialize)(zval **object, zend_class_entry *ce, const unsigned char *buf, zend_uint buf_len, zend_unserialize_data *data TSRMLS_DC);
 
	zend_class_entry **interfaces;	/*	类实现的接口 */
	zend_uint num_interfaces;	/*	类实现的接口数 */
 
	/*	类所在文件信息 */
	char *filename;
	zend_uint line_start;
	zend_uint line_end;
	char *doc_comment;
	zend_uint doc_comment_len;
 
	struct _zend_module_entry *module;
};

从PHP自带的SPL中，我们可以看到有类的继承，从这里出发，可以找到我们所需要的实现过程
从手册中选择CachingIterator类作为切入点。
CachingIterator extends IteratorIterator implements OuterIterator , Traversable , Iterator , ArrayAccess , Countable
跟踪过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

//在ext/spl/spl_iterators.c 3246行，
REGISTER_SPL_SUB_CLASS_EX(CachingIterator, IteratorIterator, spl_dual_it_new, spl_funcs_CachingIterator);
 
//    ext/spl/spl_functions.h 34行
#define REGISTER_SPL_SUB_CLASS_EX(class_name, parent_class_name, obj_ctor, funcs) \
    spl_register_sub_class(&spl_ce_ ## class_name, spl_ce_ ## parent_class_name, # class_name, obj_ctor, funcs TSRMLS_CC);
 
//    ext/spl/spl_functions.c 56行
PHPAPI void spl_register_sub_class(zend_class_entry ** ppce, zend_class_entry * parent_ce, char * class_name, void *obj_ctor, const zend_function_entry * function_list TSRMLS_DC)
*ppce = zend_register_internal_class_ex(&ce, parent_ce, NULL TSRMLS_CC);
 
//    zend/zend_API.c  2196行
ZEND_API zend_class_entry *zend_register_internal_class_ex(zend_class_entry *class_entry, zend_class_entry *parent_ce, char *parent_name TSRMLS_DC)
zend_do_inheritance(register_class, parent_ce TSRMLS_CC);
 
//    zend/zend_compile.c 2784行
 
ZEND_API void zend_do_inheritance(zend_class_entry *ce, zend_class_entry *parent_ce TSRMLS_DC)
{
    /* 接口不能继承类 */
    if ((ce->ce_flags & ZEND_ACC_INTERFACE)
   	 && !(parent_ce->ce_flags & ZEND_ACC_INTERFACE)) {
   	 zend_error(E_COMPILE_ERROR, "Interface %s may not inherit from class (%s)", ce->name, parent_ce->name);
    }
 
    /* final类不能继承 */
    if (parent_ce->ce_flags & ZEND_ACC_FINAL_CLASS) {
   	 zend_error(E_COMPILE_ERROR, "Class %s may not inherit from final class (%s)", ce->name, parent_ce->name);
    }
 
    ce->parent = parent_ce;
    /* 拷贝序列化和反序列化回调函数 */
    if (!ce->serialize) {
   	 ce->serialize   = parent_ce->serialize;
    }
    if (!ce->unserialize) {
   	 ce->unserialize = parent_ce->unserialize;
    }
 
    /* 继承父类的接口 在此处有停下来思考，为何要这么做 */
    zend_do_inherit_interfaces(ce, parent_ce TSRMLS_CC);
 
    /* 继承父类的属性  */
    zend_hash_merge(&ce->default_properties, &parent_ce->default_properties, (void (*)(void *)) zval_add_ref, NULL, sizeof(zval *), 0);
    if (parent_ce->type != ce->type) {
   	 /* 用户自定义的类从内部类继承 */
   	 zend_update_class_constants(parent_ce  TSRMLS_CC);
   	 zend_hash_apply_with_arguments(CE_STATIC_MEMBERS(parent_ce) TSRMLS_CC, (apply_func_args_t)inherit_static_prop, 1, &ce->default_static_members);
    } else {
   	 zend_hash_apply_with_arguments(&parent_ce->default_static_members TSRMLS_CC, (apply_func_args_t)inherit_static_prop, 1, &ce->default_static_members);
    }
    zend_hash_merge_ex(&ce->properties_info, &parent_ce->properties_info, (copy_ctor_func_t) (ce->type & ZEND_INTERNAL_CLASS ? zend_duplicate_property_info_internal : zend_duplicate_property_info), sizeof(zend_property_info), (merge_checker_func_t) do_inherit_property_access_check, ce);
 
    /* 合并常量和成员函数 */
    zend_hash_merge(&ce->constants_table, &parent_ce->constants_table, (void (*)(void *)) zval_add_ref, NULL, sizeof(zval *), 0);
    zend_hash_merge_ex(&ce->function_table, &parent_ce->function_table, (copy_ctor_func_t) do_inherit_method, sizeof(zend_function), (merge_checker_func_t) do_inherit_method_check, ce);
 
    do_inherit_parent_constructor(ce);
 
    if (ce->ce_flags & ZEND_ACC_IMPLICIT_ABSTRACT_CLASS && ce->type == ZEND_INTERNAL_CLASS) {
   	 ce->ce_flags |= ZEND_ACC_EXPLICIT_ABSTRACT_CLASS;
    } else if (!(ce->ce_flags & ZEND_ACC_IMPLEMENT_INTERFACES)) {
   	 /* The verification will be done in runtime by ZEND_VERIFY_ABSTRACT_CLASS */
   	 zend_verify_abstract_class(ce TSRMLS_CC);
    }
}

关于上面do_inherit_parent_constructor(ce)
此方法实现魔术方法继承，如果子类中没有相关的魔术方法，则继承父类的对应方法。如下所示的PHP代码为子类没构造函数的情况

1
2
3
4
5
6
7
8
9
10
11

class Base {
	public function __construct() {
    	echo 'Base __construct<br />';
	}
}
 
class Foo extends Base {
 
}
 
$foo = new Foo();

如上，会输出：Base __construct
显然继承了父类的构造方法，如果子类有自己的构造方法，并且需要调用父类的构造方法时，需要在子类的构造方法中调用父类的构造方法，PHP不会自动调用。

算法设计技术：一维模式识别

算法设计技术：一维模式识别
最近重温经典《编程珠玑》，在第8章算法设计技术中一维模式识别实例，书中举出了5种不同的解法，解法不断优化，不断的变得高效，不断得变得更优雅，看完感触良深。已经三年没有和算法有过直接沟通了，也淡忘了，从记忆中唤起，再次遇到，发现有些思想已经深入到骨子里了。
回正题。
【问题描述】
输入n个数的序列，输出这n个数的任意连续子序列的最大和。在这里我们假设序列的数都为整数（包括正和负）
如序列： 31 -41 59 26 -53 58 97 -93 -23 84
从[2..6]的总和187为最大

【解法一：穷举法】
最简单的方法，穷举法：即对所有满足0 <= i <= j < n 的(i, j)整数对进行迭代。对于每个整数对，程序都要计算x[i..j]的总和，并检验该总和是否大于迄今为止的最大总和。 其PHP实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

<?php
/**
 * 一维模式识别算法一，穷举法
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$len = count($seq);
 
	for ($i = 0; $i < $len; $i++) {
		for ($j = $i; $j < $len; $j++) {
			$sum = 0;
			for ($k = $i; $k <= $j; $k++) {
				$sum += $seq[$k];
			}
 
			if($sum > $maxsofar) {
				$maxsofar = $sum;
			}
		}
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

算法一优点是非常清晰明了，一眼就看出其思路，并且实现简单。
但是其时间复杂度为O(n的立方)，如果数据量稍微大一点，整个程序的效率将会巨慢。

【解法二：】
x[i..j]的总和与前面已计算的总和x[i..j-1]密切相关，即x[i..j] = x[i..j-1] + x[j]
于是我们有了解法二。
如下所示PHP代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

<?php
/**
 * 一维模式识别算法二，穷举法的优化算法，将时间复杂度变为n的平方
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$len = count($seq);
 
	for ($i = 0; $i < $len; $i++) {
		$sum = 0;
		for ($j = $i; $j < $len; $j++) {
			$sum += $seq[$j];
 
			if($sum > $maxsofar) {
				$maxsofar = $sum;
			}
		}
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

【解法三：预处理】
同样是根据x[i..j]的总和与前面已计算的总和x[i..j-1]密切相关，即x[i..j] = x[i..j-1] + x[j]
不过我们使用另外一种表示：预处理数据，计算cumarr[i] = x[0..i]，则x[i..j] = cumarr[j] – cumarr[i - 1]
然后再如解法二一样遍历比较，算出最大的值。
如下所示代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

<?php
/**
 * 一维模式识别算法三，穷举法的优化算法，将时间复杂度变为n的平方
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$len = count($seq);
 
	/* 预处理数据 */
	$cumarr[-1] = 0;
	for ($i = 0; $i < $len; $i++) {
		$cumarr[$i] = $cumarr[$i - 1] + $seq[$i];
	}
 
	for ($i = 0; $i < $len; $i++) {
		for ($j = $i; $j < $len; $j++) {
			$sum = $cumarr[$j] - $cumarr[$i - 1];
 
			if($sum > $maxsofar) {
				$maxsofar = $sum;
			}
		}
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

【解法四：分治算法】
分治原理：要解决规模为n的问题，可递归地解决两个规模近似为n/2的子问题，然后对它们的答案进行合并以得到整个问题的答案。
首先创建两个子序列a和b,然后递归找出a,b中元素总和最大的子向量，分别称为ma和mb，也许我们可能找到最后的解了，可是也有可能答案所在的子序列一部分在ma，一部分在mb，对于这种跨越边界的序列我们将其称之为mc。
我们的分治算法将递归地计算ma和mb，并通过其它方法计算mc，然后返回3个总各和中的最大者。
其PHP实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

<?php
/**
 * 一维模式识别算法四，分治算法
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq, $left, $right) {
	if($left > $right) {
		return 0;	//	已没有元素 递归返回
	}
 
	if($left == $right) {
		return max(0, $seq[$left]);	//	只有一个元素，返回这个元素与0之间的较大值
	}
 
	$middle = floor(($left + $right) / 2);
 
	/* 左边从中间开始的最大子序列和 */
	$lmax = $sum = 0;
	for($i = $middle; $i >= $left; $i--) {
		$sum += $seq[$i];
		$lmax = max($lmax, $sum);
	}
 
	/* 右边从中间开始的最大子序列和 */
	$rmax = $sum = 0;
	for($i = $middle + 1; $i <= $right; $i++) {
		$sum += $seq[$i];
		$rmax = max($rmax, $sum);
	}
 
	return max($lmax + $rmax, maxsofar($seq, $left, $middle), maxsofar($seq, $middle + 1, $right));
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq, 0, count($seq) - 1);
die();

对于mc的计算，通过观察发现，mc在a中包含右边界的最大子序列，而mc在了中包含左边界的最大子序列
此解法的时间复杂度为O(nlogn)

【解法五：扫描算法】
最大总和的初始值设为0，假设我们已解决了x[0..i-1]的问题，那么最大总各子序列要么在前i-1个元素中，要么其结束位置为i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<?php
/**
 * 一维模式识别算法五，扫描算法
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$maxendinghere = 0;
	$len = count($seq);
 
	for($i = 0; $i < $len; $i++) {
		$maxendinghere = max($maxendinghere + $seq[$i], 0);
		$maxsofar = max($maxsofar, $maxendinghere);
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

理解这个程序的关键在于变量$maxendinghere。
在循环中的第一个赋值语句之前，$maxendinghere是结束位置为i-1的最大子序列的和；赋值语句将其改为结束位置为i的最大子序列的和。
其时间复杂度为O(n)，对于这种时间复杂度为O(n)的算法，一般称其为线性算法。

【后记】
从立方算法到线性算法，这是一个质的飞跃。
虽然现在的工作中可能用不到算法，但是在写程序的过程中能够不自觉的优化自己的代码，这也是一种好的习惯。
《编程珠玑》值得多看几次。

PHP扩展开发：简单类实现

PHP扩展开发：简单类实现
话说之前有写过如何在vs2008下开发PHP扩展，今天我们来实现一个简单类。
对于一个类，一般包括类定义，声明成员变量，声明成员函数，定义类常量，
对于类继承，重载，接口实现等不在这里说明。
首先我们看下这个简单类的PHP实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<?php
/**
 * 简单类示例的PHP实现  2010-11-03 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                               
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
class Phppan {
 
    private $_name;
 
    CONST URL = 'http://www.phppan.com';
 
    public function __construct() {
    }
 
    public function getName() {
        return $this->_name;
    }
 
    public function setName($name) {
        $this->_name = $name;
    }
}

我们同样使用在之前创建的martin扩展
下面说明其实现过程：
1、声明类的成员函数
在php_martin.h文件中声明类的成员函数，如下所示代码：

1
2
3
4
5

 
PHP_METHOD(phppan, __construct);                                      
PHP_METHOD(phppan, __destruct);
PHP_METHOD(phppan, getName);
PHP_METHOD(phppan, setName);

2、定义类的成员函数
在martin.c文件中给出这4个函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

 
 
/** {{{ 
*/
PHP_METHOD(phppan, __construct) {
 
}
/* }}} */
 
/** {{{ 
*/
PHP_METHOD(phppan, __destruct) {
}
/* }}} */
 
/** {{{ 
*/
PHP_METHOD(phppan, getName) {
	zval *self, *name;
 
	self = getThis();
 
	name = zend_read_property(Z_OBJCE_P(self), self, ZEND_STRL("_name"), 0 TSRMLS_CC);
 
	RETURN_STRING(Z_STRVAL_P(name), 0);
}
/* }}} */
 
/** {{{ 
*/
PHP_METHOD(phppan, setName) {
	char *arg = NULL;
	int arg_len;
	zval *value, *self;
 
	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "s", &arg, &arg_len) == FAILURE) {
		WRONG_PARAM_COUNT;
	}
 
	self = getThis();
 
	MAKE_STD_ZVAL(value);
	ZVAL_STRING(value, arg, arg_len, 0);
 
	SEPARATE_ZVAL_TO_MAKE_IS_REF(&value);
	zend_update_property(Z_OBJCE_P(self), self, ZEND_STRL("_name"), value TSRMLS_CC);
 
	RETURN_TRUE;
}
/* }}} */

3、注册这些函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14

 
/* {{{ martin_functions[]
 *
 * Every user visible function must have an entry in martin_functions[].
 */
const zend_function_entry martin_functions[] = {
	PHP_FE(martin_echo,	NULL)		
	PHP_ME(phppan, __construct, 	NULL, ZEND_ACC_PUBLIC|ZEND_ACC_CTOR) 
	PHP_ME(phppan, __destruct,  	NULL, ZEND_ACC_PUBLIC|ZEND_ACC_DTOR) 
	PHP_ME(phppan, getName, 	 	 	NULL, ZEND_ACC_PUBLIC) 
	PHP_ME(phppan, setName, 	 	 	setName_args, ZEND_ACC_PUBLIC) 
	{NULL, NULL, NULL}	/* Must be the last line in martin_functions[] */
};
/* }}} */

4、在扩展模块初始化时初始化类，并声明成员变量和常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

zend_class_entry *phppan_ce;
 
/* 类方法的参数 */
ZEND_BEGIN_ARG_INFO(setName_args, 0)
	ZEND_ARG_INFO(0, name)
ZEND_END_ARG_INFO()
 
/* {{{ PHP_MINIT_FUNCTION
 */
PHP_MINIT_FUNCTION(martin)
{
	/* If you have INI entries, uncomment these lines 
	REGISTER_INI_ENTRIES();
	*/
	zend_class_entry phppan;
 
	INIT_CLASS_ENTRY(phppan, "Phppan", martin_functions);
	phppan_ce = zend_register_internal_class_ex(&phppan, NULL, NULL TSRMLS_CC);
 
 
	/* 声明常量URL */
	zend_declare_class_constant_stringl(phppan_ce, ZEND_STRL("URL"), ZEND_STRL("http://www.phppan.com") TSRMLS_CC);
 
	/* 声明私有成员变量 _name  */
	zend_declare_property_null(phppan_ce, ZEND_STRL("_name"), ZEND_ACC_PRIVATE TSRMLS_CC);
 
 
	return SUCCESS;
}
/* }}} */

以上为所有代码
在这些代码里面有一些东西需要说明一下：
1、类方法的定义与php的单个函数的定义一样，使用zend_function_entry结构数组，不同的是单个方法使用PHP_FE宏，
类方法的定义使用PHP_ME宏，在h文件中使用ZEND_METHOD声明，普通的函数使用ZEND_FUNCTION声明。
PHP_ME宏
定义在php.h中
#define PHP_ME ZEND_ME
#define ZEND_ME(classname, name, arg_info, flags) ZEND_FENTRY(name, ZEND_MN(classname##_##name), arg_info, flags)
2、在注册类时把该结构体作为参数交给相关的类注册方法即可
ZEND_BEGIN_ARG_INFO(setName_args, 0)
ZEND_ARG_INFO(0, name)
ZEND_END_ARG_INFO()
3、取this变量使用getThis();
4、使用zend_read_property读取类成员变量，返回的是zval 指针类型
5、使用zend_update_property更新类成员变量。
6、初始化类使用INIT_CLASS_ENTRY宏
7、注册类使用zend_register_internal_class_ex函数

function registration failed duplicate name.问题的解决方法：
这个由于我们在写这个简单类时偷了一下懒，将martin_functions作为模块的函数也将它作为了类的方法。
解决方法是替换上面的martin_functions数组，增加phppan_functions，并且在注册时使用phppan_functions，在模块的functions字段使用martin_functions

/* {{{ martin_functions[]
 *
 * Every user visible function must have an entry in martin_functions[].
 */
const zend_function_entry martin_functions[] = {
    {NULL, NULL, NULL}  /* Must be the last line in martin_functions[] */
};
 
const zend_function_entry phppan_functions[] = {
    PHP_ME(phppan, __construct,     NULL, ZEND_ACC_PUBLIC|ZEND_ACC_CTOR)
    PHP_ME(phppan, __destruct,      NULL, ZEND_ACC_PUBLIC|ZEND_ACC_DTOR)
    PHP_ME(phppan, getName,             NULL, ZEND_ACC_PUBLIC)
    PHP_ME(phppan, setName,             setName_args, ZEND_ACC_PUBLIC)
    {NULL, NULL, NULL}  /* Must be the last line in martin_functions[] */
};
/* }}} */
 
INIT_CLASS_ENTRY(phppan, "Phppan", phppan_functions);