Use better data structures (incomplete)

5 files changed, 55 insertions, 29 deletions

diff --git a/ext/spl/php_spl.c b/ext/spl/php_spl.c
index 5927e05562..de787ae7b6 100644
--- a/ext/spl/php_spl.c
+++ b/ext/spl/php_spl.c
@@ -454,12 +454,24 @@ PHP_FUNCTION(spl_autoload_call)
 } /* }}} */
 
 #define HT_MOVE_TAIL_TO_HEAD(ht)							\
-	(ht)->pListTail->pListNext = (ht)->pListHead;			\
-	(ht)->pListHead = (ht)->pListTail;						\
-	(ht)->pListTail = (ht)->pListHead->pListLast;			\
-	(ht)->pListHead->pListNext->pListLast = (ht)->pListHead;\
-	(ht)->pListTail->pListNext = NULL;						\
-	(ht)->pListHead->pListLast = NULL;
+	do {													\
+		uint first = 0;										\
+		uint last = (ht)->nNumUsed;							\
+		while (first < last) {								\
+			if ((ht)->arData[first].xData) break;			\
+			first++;										\
+		}													\
+		while (last > first) {								\
+			last--;											\
+			if ((ht)->arData[last].xData) break;			\
+		}													\
+		if (first != last) {								\
+			Bucket tmp = (ht)->arData[first];				\
+			(ht)->arData[first] = (ht)->arData[last];		\
+			(ht)->arData[last] = tmp;						\
+			zend_hash_rehash(ht);							\
+		}													\
+	} while (0)
 
 /* {{{ proto bool spl_autoload_register([mixed autoload_function = "spl_autoload" [, throw = true [, prepend]]])
  Register given function as __autoload() implementation */
diff --git a/ext/spl/spl_array.c b/ext/spl/spl_array.c
index 9270132ff7..541f7b67a7 100644
--- a/ext/spl/spl_array.c
+++ b/ext/spl/spl_array.c
@@ -101,33 +101,39 @@ static inline HashTable *spl_array_get_hash_table(spl_array_object* intern, int
 
 static void spl_array_rewind(spl_array_object *intern TSRMLS_DC);
 
-static void spl_array_update_pos(spl_array_object* intern) /* {{{ */
+static void spl_array_update_pos(HashTable *ht, spl_array_object* intern) /* {{{ */
 {
-	Bucket *pos = intern->pos;
-	if (pos != NULL) {
-		intern->pos_h = pos->h;
+	uint pos = intern->pos;
+	if (pos != INVALID_IDX) {
+		intern->pos_h = ht->arData[pos].h;
 	}
 } /* }}} */
 
-static void spl_array_set_pos(spl_array_object* intern, HashPosition pos) /* {{{ */
+static void spl_array_set_pos(spl_array_object* intern, HashTable *ht, HashPosition pos) /* {{{ */
 {
 	intern->pos = pos;
-	spl_array_update_pos(intern);
+	spl_array_update_pos(ht, intern);
 } /* }}} */
 
 SPL_API int spl_hash_verify_pos_ex(spl_array_object * intern, HashTable * ht TSRMLS_DC) /* {{{ */
 {
-	Bucket *p;
+	uint idx;
 
 /*	IS_CONSISTENT(ht);*/
 
 /*	HASH_PROTECT_RECURSION(ht);*/
-	p = ht->arBuckets[intern->pos_h & ht->nTableMask];
-	while (p != NULL) {
-		if (p == intern->pos) {
+	if (ht->flags & HASH_FLAG_PACKED) {
+		if (intern->pos_h == intern->pos && ht->arData[intern->pos_h].xData) {
 			return SUCCESS;
 		}
-		p = p->pNext;
+	} else {
+		idx = ht->arHash[intern->pos_h & ht->nTableMask].idx;
+		while (idx != INVALID_IDX) {		
+			if (idx == intern->pos) {
+				return SUCCESS;
+			}
+			idx = ht->arData[idx].next;
+		}
 	}
 /*	HASH_UNPROTECT_RECURSION(ht); */
 	spl_array_rewind(intern TSRMLS_CC);
@@ -667,7 +673,7 @@ static inline int spl_array_object_verify_pos_ex(spl_array_object *object, HashT
 		return FAILURE;
 	}
 
-	if (object->pos && (object->ar_flags & SPL_ARRAY_IS_REF) && spl_hash_verify_pos_ex(object, ht TSRMLS_CC) == FAILURE) {
+	if (object->pos != INVALID_IDX && (object->ar_flags & SPL_ARRAY_IS_REF) && spl_hash_verify_pos_ex(object, ht TSRMLS_CC) == FAILURE) {
 		php_error_docref(NULL TSRMLS_CC, E_NOTICE, "%sArray was modified outside object and internal position is no longer valid", msg_prefix);
 		return FAILURE;
 	}
@@ -734,8 +740,10 @@ void spl_array_iterator_append(zval *object, zval *append_value TSRMLS_DC) /* {{
 	}
 
 	spl_array_write_dimension(object, NULL, append_value TSRMLS_CC);
-	if (!intern->pos) {
-		spl_array_set_pos(intern, aht->pListTail);
+	if (intern->pos == INVALID_IDX) {
+		if (aht->nNumUsed && aht->arData[aht->nNumUsed-1].xData) {
+			spl_array_set_pos(intern, aht, aht->nNumUsed - 1);
+		}
 	}
 } /* }}} */
 
@@ -932,7 +940,7 @@ static int spl_array_skip_protected(spl_array_object *intern, HashTable *aht TSR
 				return FAILURE;
 			}
 			zend_hash_move_forward_ex(aht, &intern->pos);
-			spl_array_update_pos(intern);
+			spl_array_update_pos(aht, intern);
 		} while (1);
 	}
 	return FAILURE;
@@ -941,7 +949,7 @@ static int spl_array_skip_protected(spl_array_object *intern, HashTable *aht TSR
 static int spl_array_next_no_verify(spl_array_object *intern, HashTable *aht TSRMLS_DC) /* {{{ */
 {
 	zend_hash_move_forward_ex(aht, &intern->pos);
-	spl_array_update_pos(intern);
+	spl_array_update_pos(aht, intern);
 	if (Z_TYPE_P(intern->array) == IS_OBJECT) {
 		return spl_array_skip_protected(intern, aht TSRMLS_CC);
 	} else {
@@ -1064,7 +1072,7 @@ static void spl_array_rewind_ex(spl_array_object *intern, HashTable *aht TSRMLS_
 {
 
 	zend_hash_internal_pointer_reset_ex(aht, &intern->pos);
-	spl_array_update_pos(intern);
+	spl_array_update_pos(aht, intern);
 	spl_array_skip_protected(intern, aht TSRMLS_CC);
 
 } /* }}} */
@@ -1381,10 +1389,10 @@ int static spl_array_object_count_elements_helper(spl_array_object *intern, long
 		pos = intern->pos;
 		*count = 0;
 		spl_array_rewind(intern TSRMLS_CC);
-		while(intern->pos && spl_array_next(intern TSRMLS_CC) == SUCCESS) {
+		while(intern->pos != INVALID_IDX && spl_array_next(intern TSRMLS_CC) == SUCCESS) {
 			(*count)++;
 		}
-		spl_array_set_pos(intern, pos);
+		spl_array_set_pos(intern, aht, pos);
 		return SUCCESS;
 	} else {
 		*count = zend_hash_num_elements(aht);
diff --git a/ext/spl/spl_directory.c b/ext/spl/spl_directory.c
index 4abbdf9df8..6ec094ac3c 100644
--- a/ext/spl/spl_directory.c
+++ b/ext/spl/spl_directory.c
@@ -2232,9 +2232,14 @@ static int spl_filesystem_file_is_empty_line(spl_filesystem_object *intern TSRML
 		case IS_ARRAY:
 			if (SPL_HAS_FLAG(intern->flags, SPL_FILE_OBJECT_READ_CSV)
 			&& zend_hash_num_elements(Z_ARRVAL_P(intern->u.file.current_zval)) == 1) {
-				zval ** first = Z_ARRVAL_P(intern->u.file.current_zval)->pListHead->pData;
-					
-				return Z_TYPE_PP(first) == IS_STRING && Z_STRLEN_PP(first) == 0;
+				uint idx = 0;
+				zval *first;
+
+				while (Z_ARRVAL_P(intern->u.file.current_zval)->arData[idx].xData == NULL) {
+					idx++;
+				}
+				first = Z_ARRVAL_P(intern->u.file.current_zval)->arData[idx].xData;
+				return Z_TYPE_P(first) == IS_STRING && Z_STRLEN_P(first) == 0;
 			}
 			return zend_hash_num_elements(Z_ARRVAL_P(intern->u.file.current_zval)) == 0;
 		case IS_NULL:
diff --git a/ext/spl/spl_functions.c b/ext/spl/spl_functions.c
index f1e59c0234..1a3134f85f 100644
--- a/ext/spl/spl_functions.c
+++ b/ext/spl/spl_functions.c
@@ -58,7 +58,7 @@ PHPAPI void spl_register_sub_class(zend_class_entry ** ppce, zend_class_entry *
 	zend_class_entry ce;
 	
 	INIT_CLASS_ENTRY_EX(ce, class_name, strlen(class_name), function_list);
-	*ppce = zend_register_internal_class_ex(&ce, parent_ce, NULL TSRMLS_CC);
+	*ppce = zend_register_internal_class_ex(&ce, parent_ce TSRMLS_CC);
 
 	/* entries changed by initialize */
 	if (obj_ctor) {
diff --git a/ext/spl/spl_observer.c b/ext/spl/spl_observer.c
index 1a706f7642..3882deb229 100644
--- a/ext/spl/spl_observer.c
+++ b/ext/spl/spl_observer.c
@@ -258,6 +258,7 @@ static zend_object_value spl_object_storage_new_ex(zend_class_entry *class_type,
 
 	intern = emalloc(sizeof(spl_SplObjectStorage));
 	memset(intern, 0, sizeof(spl_SplObjectStorage));
+	intern->pos = INVALID_IDX;
 	*obj = intern;
 
 	zend_object_std_init(&intern->std, class_type TSRMLS_CC);