colder Mon Feb 25 23:36:36 2008 UTC
Added files:
/php-src/ext/spl spl_heap.c spl_heap.h
/php-src/ext/spl/tests heap_001.phpt heap_002.phpt heap_003.phpt
heap_004.phpt heap_005.phpt heap_006.phpt
heap_007.phpt heap_008.phpt pqueue_001.phpt
pqueue_002.phpt pqueue_003.phpt
pqueue_004.phpt
Modified files:
/php-src/ext/spl config.m4 config.w32 php_spl.c
Log:
SplHeap, SplMinHeap, SplMaxHeap, SplPriorityQueue implementation
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/config.m4?r1=1.23&r2=1.24&diff_format=u
Index: php-src/ext/spl/config.m4
diff -u php-src/ext/spl/config.m4:1.23 php-src/ext/spl/config.m4:1.24
--- php-src/ext/spl/config.m4:1.23 Tue Jan 15 09:37:50 2008
+++ php-src/ext/spl/config.m4 Mon Feb 25 23:36:36 2008
@@ -1,4 +1,4 @@
-dnl $Id: config.m4,v 1.23 2008/01/15 09:37:50 colder Exp $
+dnl $Id: config.m4,v 1.24 2008/02/25 23:36:36 colder Exp $
dnl config.m4 for extension SPL
PHP_ARG_ENABLE(spl, enable SPL suppport,
@@ -29,7 +29,7 @@
PHP_INSTALL_HEADERS([ext/spl/])
AC_DEFINE_UNQUOTED(HAVE_PACKED_OBJECT_VALUE, $ac_result, [Whether struct
_zend_object_value is packed])
AC_DEFINE(HAVE_SPL, 1, [Whether you want SPL (Standard PHP Library)
support])
- PHP_NEW_EXTENSION(spl, php_spl.c spl_functions.c spl_engine.c
spl_iterators.c spl_array.c spl_directory.c spl_sxe.c spl_exceptions.c
spl_observer.c spl_dllist.c, no)
- PHP_INSTALL_HEADERS([ext/spl], [php_spl.h spl_array.h spl_directory.h
spl_engine.h spl_exceptions.h spl_functions.h spl_iterators.h spl_observer.h
spl_sxe.h spl_dllist.h])
+ PHP_NEW_EXTENSION(spl, php_spl.c spl_functions.c spl_engine.c
spl_iterators.c spl_array.c spl_directory.c spl_sxe.c spl_exceptions.c
spl_observer.c spl_dllist.c spl_heap.c, no)
+ PHP_INSTALL_HEADERS([ext/spl], [php_spl.h spl_array.h spl_directory.h
spl_engine.h spl_exceptions.h spl_functions.h spl_iterators.h spl_observer.h
spl_sxe.h spl_dllist.h spl_heap.h])
PHP_ADD_EXTENSION_DEP(spl, pcre, true)
fi
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/config.w32?r1=1.8&r2=1.9&diff_format=u
Index: php-src/ext/spl/config.w32
diff -u php-src/ext/spl/config.w32:1.8 php-src/ext/spl/config.w32:1.9
--- php-src/ext/spl/config.w32:1.8 Tue Jan 15 09:37:50 2008
+++ php-src/ext/spl/config.w32 Mon Feb 25 23:36:36 2008
@@ -1,4 +1,4 @@
-// $Id: config.w32,v 1.8 2008/01/15 09:37:50 colder Exp $
+// $Id: config.w32,v 1.9 2008/02/25 23:36:36 colder Exp $
// vim:ft=javascript
ARG_ENABLE("spl", "SPL (Standard PHP Library) support", "yes");
@@ -7,6 +7,6 @@
if (PHP_SPL_SHARED) {
ERROR("SPL cannot be compiled as a shared ext");
}
- EXTENSION("spl", "php_spl.c spl_functions.c spl_engine.c
spl_iterators.c spl_array.c spl_directory.c spl_sxe.c spl_exceptions.c
spl_observer.c spl_dllist.c");
+ EXTENSION("spl", "php_spl.c spl_functions.c spl_engine.c
spl_iterators.c spl_array.c spl_directory.c spl_sxe.c spl_exceptions.c
spl_observer.c spl_dllist.c spl_heap.c");
AC_DEFINE('HAVE_SPL', 1);
}
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/php_spl.c?r1=1.125&r2=1.126&diff_format=u
Index: php-src/ext/spl/php_spl.c
diff -u php-src/ext/spl/php_spl.c:1.125 php-src/ext/spl/php_spl.c:1.126
--- php-src/ext/spl/php_spl.c:1.125 Mon Feb 4 15:58:12 2008
+++ php-src/ext/spl/php_spl.c Mon Feb 25 23:36:36 2008
@@ -16,7 +16,7 @@
+----------------------------------------------------------------------+
*/
-/* $Id: php_spl.c,v 1.125 2008/02/04 15:58:12 helly Exp $ */
+/* $Id: php_spl.c,v 1.126 2008/02/25 23:36:36 colder Exp $ */
#ifdef HAVE_CONFIG_H
#include "config.h"
@@ -36,6 +36,7 @@
#include "spl_exceptions.h"
#include "spl_observer.h"
#include "spl_dllist.h"
+#include "spl_heap.h"
#include "zend_exceptions.h"
#include "zend_interfaces.h"
#include "ext/standard/md5.h"
@@ -151,6 +152,10 @@
SPL_ADD_CLASS(SplDoublyLinkedList, z_list, sub, allow, ce_flags); \
SPL_ADD_CLASS(SplQueue, z_list, sub, allow, ce_flags); \
SPL_ADD_CLASS(SplStack, z_list, sub, allow, ce_flags); \
+ SPL_ADD_CLASS(SplHeap, z_list, sub, allow, ce_flags); \
+ SPL_ADD_CLASS(SplMinHeap, z_list, sub, allow, ce_flags); \
+ SPL_ADD_CLASS(SplMaxHeap, z_list, sub, allow, ce_flags); \
+ SPL_ADD_CLASS(SplPriorityQueue, z_list, sub, allow, ce_flags); \
SPL_ADD_CLASS(BadFunctionCallException, z_list, sub, allow, ce_flags); \
SPL_ADD_CLASS(BadMethodCallException, z_list, sub, allow, ce_flags); \
SPL_ADD_CLASS(CachingIterator, z_list, sub, allow, ce_flags); \
@@ -768,6 +773,7 @@
PHP_MINIT(spl_directory)(INIT_FUNC_ARGS_PASSTHRU);
PHP_MINIT(spl_sxe)(INIT_FUNC_ARGS_PASSTHRU);
PHP_MINIT(spl_dllist)(INIT_FUNC_ARGS_PASSTHRU);
+ PHP_MINIT(spl_heap)(INIT_FUNC_ARGS_PASSTHRU);
PHP_MINIT(spl_observer)(INIT_FUNC_ARGS_PASSTHRU);
return SUCCESS;
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/spl_heap.c?view=markup&rev=1.1
Index: php-src/ext/spl/spl_heap.c
+++ php-src/ext/spl/spl_heap.c
/*
+----------------------------------------------------------------------+
| PHP Version 5 |
+----------------------------------------------------------------------+
| Copyright (c) 1997-2008 The PHP Group |
+----------------------------------------------------------------------+
| This source file is subject to version 3.01 of the PHP license, |
| that is bundled with this package in the file LICENSE, and is |
| available through the world-wide-web at the following url: |
| http://www.php.net/license/3_01.txt |
| If you did not receive a copy of the PHP license and are unable to |
| obtain it through the world-wide-web, please send a note to |
| [EMAIL PROTECTED] so we can mail you a copy immediately. |
+----------------------------------------------------------------------+
| Authors: Etienne Kneuss <[EMAIL PROTECTED]> |
+----------------------------------------------------------------------+
*/
/* $Id: spl_heap.c,v 1.1 2008/02/25 23:36:36 colder Exp $ */
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#include "php.h"
#include "zend_exceptions.h"
#include "php_spl.h"
#include "spl_functions.h"
#include "spl_engine.h"
#include "spl_iterators.h"
#include "spl_heap.h"
#include "spl_exceptions.h"
#define PTR_HEAP_BLOCK_SIZE 64
#define SPL_HEAP_CORRUPTED 0x00000001
#define SPL_PQUEUE_EXTR_MASK 0x00000003
#define SPL_PQUEUE_EXTR_BOTH 0x00000003
#define SPL_PQUEUE_EXTR_DATA 0x00000001
#define SPL_PQUEUE_EXTR_PRIORITY 0x00000002
zend_object_handlers spl_handler_SplHeap;
zend_object_handlers spl_handler_SplPriorityQueue;
PHPAPI zend_class_entry *spl_ce_SplHeap;
PHPAPI zend_class_entry *spl_ce_SplMaxHeap;
PHPAPI zend_class_entry *spl_ce_SplMinHeap;
PHPAPI zend_class_entry *spl_ce_SplPriorityQueue;
typedef void *spl_ptr_heap_element;
typedef void (*spl_ptr_heap_dtor_func)(spl_ptr_heap_element TSRMLS_DC);
typedef void (*spl_ptr_heap_ctor_func)(spl_ptr_heap_element TSRMLS_DC);
typedef int (*spl_ptr_heap_cmp_func)(spl_ptr_heap_element,
spl_ptr_heap_element, void* TSRMLS_DC);
typedef struct _spl_ptr_heap {
spl_ptr_heap_element *elements;
spl_ptr_heap_ctor_func ctor;
spl_ptr_heap_dtor_func dtor;
spl_ptr_heap_cmp_func cmp;
int count;
int max_size;
int flags;
} spl_ptr_heap;
typedef struct _spl_heap_object spl_heap_object;
typedef struct _spl_heap_it spl_heap_it;
struct _spl_heap_object {
zend_object std;
spl_ptr_heap *heap;
zval *retval;
int flags;
zend_class_entry *ce_get_iterator;
zend_function *fptr_cmp;
};
/* define an overloaded iterator structure */
struct _spl_heap_it {
zend_user_iterator intern;
int flags;
spl_heap_object *object;
};
/* {{{ spl_ptr_heap */
static void spl_ptr_heap_zval_dtor(spl_ptr_heap_element elem TSRMLS_DC) { /*
{{{ */
if (elem) {
zval_ptr_dtor((zval **)&elem);
}
}
/* }}} */
static void spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC) { /*
{{{ */
Z_ADDREF_P((zval *)elem);
}
/* }}} */
static int spl_ptr_heap_cmp_cb_helper(zval *object, spl_heap_object
*heap_object, zval *a, zval *b, long *result TSRMLS_DC) { /* {{{ */
zval *result_p = NULL;
zend_call_method_with_2_params(&object, heap_object->std.ce,
&heap_object->fptr_cmp, "compare", &result_p, a, b);
if (EG(exception)) {
return FAILURE;
}
convert_to_long(result_p);
*result = Z_LVAL_P(result_p);
zval_ptr_dtor(&result_p);
return SUCCESS;
}
/* }}} */
static zval **spl_pqueue_extract_helper(zval **value, int flags) /* {{{ */
{
if ((flags & SPL_PQUEUE_EXTR_BOTH) == SPL_PQUEUE_EXTR_BOTH) {
return value;
} else if ((flags & SPL_PQUEUE_EXTR_BOTH) > 0) {
if ((flags & SPL_PQUEUE_EXTR_DATA) == SPL_PQUEUE_EXTR_DATA) {
zval **data;
if (zend_hash_find(Z_ARRVAL_PP(value), "data",
sizeof("data"), (void **) &data) == SUCCESS) {
return data;
}
} else {
zval **priority;
if (zend_hash_find(Z_ARRVAL_PP(value), "priority",
sizeof("priority"), (void **) &priority) == SUCCESS) {
return priority;
}
}
}
return NULL;
}
/* }}} */
static int spl_ptr_heap_zval_max_cmp(spl_ptr_heap_element a,
spl_ptr_heap_element b, void* object TSRMLS_DC) { /* {{{ */
zval result;
if (EG(exception)) {
return 0;
}
if (object) {
spl_heap_object *heap_object =
(spl_heap_object*)zend_object_store_get_object((zval *)object TSRMLS_CC);
if (heap_object->fptr_cmp) {
long lval = 0;
if (spl_ptr_heap_cmp_cb_helper((zval *)object,
heap_object, (zval *)a, (zval *)b, &lval TSRMLS_CC) == FAILURE) {
/* exception or call failure */
return 0;
}
return lval;
}
}
INIT_ZVAL(result);
compare_function(&result, (zval *)a, (zval *)b TSRMLS_CC);
return Z_LVAL(result);
}
/* }}} */
static int spl_ptr_heap_zval_min_cmp(spl_ptr_heap_element a,
spl_ptr_heap_element b, void* object TSRMLS_DC) { /* {{{ */
zval result;
if (EG(exception)) {
return 0;
}
if (object) {
spl_heap_object *heap_object =
(spl_heap_object*)zend_object_store_get_object((zval *)object TSRMLS_CC);
if (heap_object->fptr_cmp) {
long lval = 0;
if (spl_ptr_heap_cmp_cb_helper((zval *)object,
heap_object, (zval *)a, (zval *)b, &lval TSRMLS_CC) == FAILURE) {
/* exception or call failure */
return 0;
}
return lval;
}
}
INIT_ZVAL(result);
compare_function(&result, (zval *)b, (zval *)a TSRMLS_CC);
return Z_LVAL(result);
}
/* }}} */
static int spl_ptr_pqueue_zval_cmp(spl_ptr_heap_element a, spl_ptr_heap_element
b, void* object TSRMLS_DC) { /* {{{ */
zval result;
zval **a_priority_pp = spl_pqueue_extract_helper((zval **)&a,
SPL_PQUEUE_EXTR_PRIORITY);
zval **b_priority_pp = spl_pqueue_extract_helper((zval **)&b,
SPL_PQUEUE_EXTR_PRIORITY);
if ((!a_priority_pp) || (!b_priority_pp)) {
zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the
PriorityQueue node");
return 0;
}
if (EG(exception)) {
return 0;
}
if (object) {
spl_heap_object *heap_object =
(spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
if (heap_object->fptr_cmp) {
long lval = 0;
if (spl_ptr_heap_cmp_cb_helper((zval *)object,
heap_object, *a_priority_pp, *b_priority_pp, &lval TSRMLS_CC) == FAILURE) {
/* exception or call failure */
return 0;
}
return lval;
}
}
INIT_ZVAL(result);
compare_function(&result, *a_priority_pp, *b_priority_pp TSRMLS_CC);
return Z_LVAL(result);
}
/* }}} */
static spl_ptr_heap *spl_ptr_heap_init(spl_ptr_heap_cmp_func cmp,
spl_ptr_heap_ctor_func ctor, spl_ptr_heap_dtor_func dtor) /* {{{ */
{
spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
heap->dtor = dtor;
heap->ctor = ctor;
heap->cmp = cmp;
heap->elements = (void **) safe_emalloc(sizeof(spl_ptr_heap_element),
PTR_HEAP_BLOCK_SIZE, 0);
heap->max_size = PTR_HEAP_BLOCK_SIZE;
heap->count = 0;
heap->flags = 0;
return heap;
}
/* }}} */
static void spl_ptr_heap_insert(spl_ptr_heap *heap, spl_ptr_heap_element elem,
void *cmp_userdata TSRMLS_DC) { /* {{{ */
int i;
if (heap->count+1 > heap->max_size) {
/* we need to allocate more memory */
heap->elements = (void **) safe_erealloc(heap->elements,
sizeof(spl_ptr_heap_element), (heap->max_size), (sizeof(spl_ptr_heap_element) *
(heap->max_size)));
heap->max_size *= 2;
}
heap->ctor(elem TSRMLS_CC);
/* sifting up */
for(i = heap->count++; i > 0 && heap->cmp(heap->elements[(i-1)/2],
elem, cmp_userdata TSRMLS_CC) < 0; i = (i-1)/2) {
heap->elements[i] = heap->elements[(i-1)/2];
}
if (EG(exception)) {
/* exception thrown during comparison */
heap->flags |= SPL_HEAP_CORRUPTED;
}
heap->elements[i] = elem;
}
/* }}} */
static spl_ptr_heap_element spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */
if (heap->count == 0) {
return NULL;
}
return heap->elements[0];
}
/* }}} */
static spl_ptr_heap_element spl_ptr_heap_delete_top(spl_ptr_heap *heap, void
*cmp_userdata TSRMLS_DC) { /* {{{ */
int i, j;
const int limit = (heap->count-1)/2;
if (heap->count == 0) {
return NULL;
}
spl_ptr_heap_element top = heap->elements[0];
spl_ptr_heap_element bottom = heap->elements[--heap->count];
for( i = 0; i < limit; i = j)
{
/* Find smaller child */
j = i*2+1;
if(j != heap->count && heap->cmp(heap->elements[j+1],
heap->elements[j], cmp_userdata TSRMLS_CC) > 0) {
j++; /* next child is bigger */
}
/* swap elements between two levels */
if(heap->cmp(bottom, heap->elements[j], cmp_userdata TSRMLS_CC)
< 0) {
heap->elements[i] = heap->elements[j];
} else {
break;
}
}
if (EG(exception)) {
/* exception thrown during comparison */
heap->flags |= SPL_HEAP_CORRUPTED;
}
heap->elements[i] = bottom;
heap->dtor(top TSRMLS_CC);
return top;
}
/* }}} */
static spl_ptr_heap *spl_ptr_heap_clone(spl_ptr_heap *from TSRMLS_DC) { /* {{{
*/
int i;
spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
heap->dtor = from->dtor;
heap->ctor = from->ctor;
heap->cmp = from->cmp;
heap->max_size = from->max_size;
heap->count = from->count;
heap->flags = from->flags;
heap->elements = (void **)
safe_emalloc(sizeof(spl_ptr_heap_element),from->max_size,0);
memcpy(heap->elements, from->elements,
sizeof(spl_ptr_heap_element)*from->max_size);
for (i=0; i < heap->count; ++i) {
heap->ctor(heap->elements[i] TSRMLS_CC);
}
return heap;
}
/* }}} */
static void spl_ptr_heap_destroy(spl_ptr_heap *heap TSRMLS_DC) { /* {{{ */
int i;
for (i=0; i < heap->count; ++i) {
heap->dtor(heap->elements[i] TSRMLS_CC);
}
efree(heap->elements);
efree(heap);
}
/* }}} */
static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */
return heap->count;
}
/* }}} */
/* }}} */
zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object,
int by_ref TSRMLS_DC);
static void spl_heap_object_free_storage(void *object TSRMLS_DC) /* {{{ */
{
int i;
spl_heap_object *intern = (spl_heap_object *)object;
zend_object_std_dtor(&intern->std TSRMLS_CC);
for (i = 0; i < intern->heap->count; ++i) {
if (intern->heap->elements[i]) {
zval_ptr_dtor((zval **)&intern->heap->elements[i]);
}
}
spl_ptr_heap_destroy(intern->heap TSRMLS_CC);
zval_ptr_dtor(&intern->retval);
efree(object);
}
/* }}} */
static zend_object_value spl_heap_object_new_ex(zend_class_entry *class_type,
spl_heap_object **obj, zval *orig, int clone_orig TSRMLS_DC) /* {{{ */
{
zend_object_value retval;
spl_heap_object *intern;
zval *tmp;
zend_class_entry *parent = class_type;
int inherited = 0;
intern = ecalloc(1, sizeof(spl_heap_object));
ALLOC_INIT_ZVAL(intern->retval);
zend_object_std_init(&intern->std, class_type TSRMLS_CC);
zend_hash_copy(intern->std.properties, &class_type->default_properties,
(copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
intern->flags = 0;
intern->fptr_cmp = NULL;
if (orig) {
spl_heap_object *other =
(spl_heap_object*)zend_object_store_get_object(orig TSRMLS_CC);
intern->ce_get_iterator = other->ce_get_iterator;
if (clone_orig) {
intern->heap = spl_ptr_heap_clone(other->heap
TSRMLS_CC);
} else {
intern->heap = other->heap;
}
intern->flags = other->flags;
} else {
intern->heap = spl_ptr_heap_init(spl_ptr_heap_zval_max_cmp,
spl_ptr_heap_zval_ctor, spl_ptr_heap_zval_dtor);
}
retval.handlers = &spl_handler_SplHeap;
while (parent) {
if (parent == spl_ce_SplPriorityQueue) {
intern->heap->cmp = spl_ptr_pqueue_zval_cmp;
intern->flags = SPL_PQUEUE_EXTR_DATA;
retval.handlers = &spl_handler_SplPriorityQueue;
break;
}
if (parent == spl_ce_SplMinHeap) {
intern->heap->cmp = spl_ptr_heap_zval_min_cmp;
break;
}
if (parent == spl_ce_SplMaxHeap) {
intern->heap->cmp = spl_ptr_heap_zval_max_cmp;
break;
}
if (parent == spl_ce_SplHeap) {
break;
}
parent = parent->parent;
inherited = 1;
}
retval.handle = zend_objects_store_put(intern,
(zend_objects_store_dtor_t)zend_objects_destroy_object,
spl_heap_object_free_storage, NULL TSRMLS_CC);
if (!parent) { /* this must never happen */
php_error_docref(NULL TSRMLS_CC, E_COMPILE_ERROR, "Internal
compiler error, Class is not child of SplHeap");
}
if (inherited) {
zend_hash_find(&class_type->function_table, "compare",
sizeof("compare"), (void **) &intern->fptr_cmp);
if (intern->fptr_cmp->common.scope == parent) {
intern->fptr_cmp = NULL;
}
}
return retval;
}
/* }}} */
static zend_object_value spl_heap_object_new(zend_class_entry *class_type
TSRMLS_DC) /* {{{ */
{
spl_heap_object *tmp;
return spl_heap_object_new_ex(class_type, &tmp, NULL, 0 TSRMLS_CC);
}
/* }}} */
static zend_object_value spl_heap_object_clone(zval *zobject TSRMLS_DC) /* {{{
*/
{
zend_object_value new_obj_val;
zend_object *old_object;
zend_object *new_object;
zend_object_handle handle = Z_OBJ_HANDLE_P(zobject);
spl_heap_object *intern;
old_object = zend_objects_get_address(zobject TSRMLS_CC);
new_obj_val = spl_heap_object_new_ex(old_object->ce, &intern, zobject,
1 TSRMLS_CC);
new_object = &intern->std;
zend_objects_clone_members(new_object, new_obj_val, old_object, handle
TSRMLS_CC);
return new_obj_val;
}
/* }}} */
static int spl_heap_object_count_elements(zval *object, long *count TSRMLS_DC)
/* {{{ */
{
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
*count = spl_ptr_heap_count(intern->heap);
return SUCCESS;
}
/* }}} */
static HashTable* spl_heap_object_get_debug_info_helper(zend_class_entry *ce,
zval *obj, int *is_temp TSRMLS_DC) { /* {{{ */
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(obj TSRMLS_CC);
HashTable *rv;
zval *tmp, zrv, *heap_array;
zstr pnstr;
int pnlen;
int i;
*is_temp = 1;
ALLOC_HASHTABLE(rv);
ZEND_INIT_SYMTABLE_EX(rv,
zend_hash_num_elements(intern->std.properties) + 1, 0);
INIT_PZVAL(&zrv);
Z_ARRVAL(zrv) = rv;
zend_hash_copy(rv, intern->std.properties, (copy_ctor_func_t)
zval_add_ref, (void *) &tmp, sizeof(zval *));
pnstr = spl_gen_private_prop_name(ce, "flags", sizeof("flags")-1,
&pnlen TSRMLS_CC);
add_u_assoc_long_ex(&zrv, ZEND_STR_TYPE, pnstr, pnlen+1, intern->flags);
efree(pnstr.v);
pnstr = spl_gen_private_prop_name(ce, "isCorrupted",
sizeof("isCorrupted")-1, &pnlen TSRMLS_CC);
add_u_assoc_bool_ex(&zrv, ZEND_STR_TYPE, pnstr, pnlen+1,
intern->heap->flags&SPL_HEAP_CORRUPTED);
efree(pnstr.v);
ALLOC_INIT_ZVAL(heap_array);
array_init(heap_array);
for (i = 0; i < intern->heap->count; ++i) {
add_index_zval(heap_array, i, (zval
*)intern->heap->elements[i]);
Z_ADDREF_P(intern->heap->elements[i]);
}
pnstr = spl_gen_private_prop_name(ce, "heap", sizeof("heap")-1, &pnlen
TSRMLS_CC);
add_u_assoc_zval_ex(&zrv, ZEND_STR_TYPE, pnstr, pnlen+1, heap_array);
efree(pnstr.v);
return rv;
}
/* }}} */
static HashTable* spl_heap_object_get_debug_info(zval *obj, int *is_temp
TSRMLS_DC) /* {{{ */
{
return spl_heap_object_get_debug_info_helper(spl_ce_SplHeap, obj,
is_temp TSRMLS_CC);
}
/* }}} */
static HashTable* spl_pqueue_object_get_debug_info(zval *obj, int *is_temp
TSRMLS_DC) /* {{{ */
{
return spl_heap_object_get_debug_info_helper(spl_ce_SplPriorityQueue,
obj, is_temp TSRMLS_CC);
}
/* }}} */
/* {{{ proto int SplHeap::count() U
Return the number of elements in the heap. */
SPL_METHOD(SplHeap, count)
{
long count;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
spl_heap_object_count_elements(getThis(), &count TSRMLS_CC);
RETURN_LONG(count);
}
/* }}} */
/* {{{ proto int SplHeap::isEmpty() U
Return true if the heap is empty. */
SPL_METHOD(SplHeap, isEmpty)
{
long count;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
spl_heap_object_count_elements(getThis(), &count TSRMLS_CC);
RETURN_BOOL(count==0);
}
/* }}} */
/* {{{ proto bool SplHeap::insert(mixed $value) U
Push $value on the heap */
SPL_METHOD(SplHeap, insert)
{
zval *value;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) ==
FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
SEPARATE_ARG_IF_REF(value);
spl_ptr_heap_insert(intern->heap, value, getThis() TSRMLS_CC);
RETURN_TRUE;
}
/* }}} */
/* {{{ proto mixed SplHeap::extract() U
extract the element out of the top of the heap */
SPL_METHOD(SplHeap, extract)
{
zval *value;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis()
TSRMLS_CC);
if (!value) {
zend_throw_exception(spl_ce_RuntimeException, "Can't extract
from an empty heap", 0 TSRMLS_CC);
return;
}
RETURN_ZVAL(value, 1, 1);
}
/* }}} */
/* {{{ proto bool SplPriorityQueue::insert(mixed $value, mixed $priority) U
Push $value with the priority $priodiry on the priorityqueue */
SPL_METHOD(SplPriorityQueue, insert)
{
zval *data, *priority, *elem;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &data,
&priority) == FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
SEPARATE_ARG_IF_REF(data);
SEPARATE_ARG_IF_REF(priority);
ALLOC_INIT_ZVAL(elem);
array_init(elem);
add_assoc_zval_ex(elem, "data", sizeof("data"), data);
add_assoc_zval_ex(elem, "priority", sizeof("priority"), priority);
spl_ptr_heap_insert(intern->heap, elem, getThis() TSRMLS_CC);
RETURN_TRUE;
}
/* }}} */
/* {{{ proto mixed SplPriorityQueue::extract() U
extract the element out of the top of the priority queue */
SPL_METHOD(SplPriorityQueue, extract)
{
zval *value, *value_out, **value_out_pp;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis()
TSRMLS_CC);
if (!value) {
zend_throw_exception(spl_ce_RuntimeException, "Can't extract
from an empty heap", 0 TSRMLS_CC);
return;
}
value_out_pp = spl_pqueue_extract_helper(&value, intern->flags);
if (!value_out_pp) {
zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the
PriorityQueue node");
zval_ptr_dtor(&value);
return;
}
value_out = *value_out_pp;
Z_ADDREF_P(value_out);
zval_ptr_dtor(&value);
RETURN_ZVAL(value_out, 1, 1);
}
/* }}} */
/* {{{ proto mixed SplPriorityQueue::top() U
Peek at the top element of the priority queue */
SPL_METHOD(SplPriorityQueue, top)
{
zval *value, **value_out;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
value = (zval *)spl_ptr_heap_top(intern->heap);
if (!value) {
zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an
empty heap", 0 TSRMLS_CC);
return;
}
value_out = spl_pqueue_extract_helper(&value, intern->flags);
if (!value_out) {
zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the
PriorityQueue node");
return;
}
RETURN_ZVAL(*value_out, 1, 0);
}
/* }}} */
/* {{{ proto int SplPriorityQueue::setIteratorMode($flags) U
Set the flags of extraction*/
SPL_METHOD(SplPriorityQueue, setExtractFlags)
{
long value;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &value) ==
FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
intern->flags = value & SPL_PQUEUE_EXTR_MASK;
RETURN_LONG(intern->flags);
}
/* }}} */
/* {{{ proto int SplHeap::recoverFromCorruption() U
Recover from a corrupted state*/
SPL_METHOD(SplHeap, recoverFromCorruption)
{
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED;
RETURN_TRUE;
}
/* }}} */
/* {{{ proto bool SplPriorityQueue::compare(mixed $a, mixed $b) U
compare the priorities */
SPL_METHOD(SplPriorityQueue, compare)
{
zval *a, *b;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) ==
FAILURE) {
return;
}
RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
}
/* }}} */
/* {{{ proto mixed SplHeap::top() U
Peek at the top element of the heap */
SPL_METHOD(SplHeap, top)
{
zval *value;
spl_heap_object *intern;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
return;
}
intern = (spl_heap_object*)zend_object_store_get_object(getThis()
TSRMLS_CC);
if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
value = (zval *)spl_ptr_heap_top(intern->heap);
if (!value) {
zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an
empty heap", 0 TSRMLS_CC);
return;
}
RETURN_ZVAL(value, 1, 0);
}
/* }}} */
/* {{{ proto bool SplMinHeap::compare(mixed $a, mixed $b) U
compare the values */
SPL_METHOD(SplMinHeap, compare)
{
zval *a, *b;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) ==
FAILURE) {
return;
}
RETURN_LONG(spl_ptr_heap_zval_min_cmp(a, b, NULL TSRMLS_CC));
}
/* }}} */
/* {{{ proto bool SplMaxHeap::compare(mixed $a, mixed $b) U
compare the values */
SPL_METHOD(SplMaxHeap, compare)
{
zval *a, *b;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) ==
FAILURE) {
return;
}
RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
}
/* }}} */
static void spl_heap_it_dtor(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator = (spl_heap_it *)iter;
zend_user_it_invalidate_current(iter TSRMLS_CC);
zval_ptr_dtor((zval**)&iterator->intern.it.data);
efree(iterator);
}
/* }}} */
static void spl_heap_it_rewind(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
{
/* do nothing, the iterator always points to the top element */
}
/* }}} */
static int spl_heap_it_valid(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator = (spl_heap_it *)iter;
return (iterator->object->heap->count != 0 ? SUCCESS : FAILURE);
}
/* }}} */
static void spl_heap_it_get_current_data(zend_object_iterator *iter, zval
***data TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator = (spl_heap_it *)iter;
zval **element = (zval **)&iterator->object->heap->elements[0];
if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
if (iterator->object->heap->count == 0 || !*element) {
*data = NULL;
} else {
*data = element;
}
}
/* }}} */
static void spl_pqueue_it_get_current_data(zend_object_iterator *iter, zval
***data TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator = (spl_heap_it *)iter;
zval **element = (zval **)&iterator->object->heap->elements[0];
if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
if (iterator->object->heap->count == 0 || !*element) {
*data = NULL;
} else {
*data = spl_pqueue_extract_helper(element,
iterator->object->flags);
if (!*data) {
zend_error(E_RECOVERABLE_ERROR, "Unable to extract from
the PriorityQueue node");
}
}
}
/* }}} */
static int spl_heap_it_get_current_key(zend_object_iterator *iter, zstr
*str_key, uint *str_key_len, ulong *int_key TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator = (spl_heap_it *)iter;
*int_key = (ulong) iterator->object->heap->count;
return HASH_KEY_IS_LONG;
}
/* }}} */
static void spl_heap_it_move_forward(zend_object_iterator *iter TSRMLS_DC) /*
{{{ */
{
zval *object = (zval*)((zend_user_iterator
*)iter)->it.data;
spl_heap_it *iterator = (spl_heap_it *)iter;
if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
zend_throw_exception(spl_ce_RuntimeException, "Heap is
corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
return;
}
spl_ptr_heap_element elem =
spl_ptr_heap_delete_top(iterator->object->heap, object TSRMLS_CC);
if (elem != NULL) {
zval_ptr_dtor((zval **)&elem);
}
zend_user_it_invalidate_current(iter TSRMLS_CC);
}
/* }}} */
/* {{{ proto int SplHeap::key() U
Return current array key */
SPL_METHOD(SplHeap, key)
{
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
RETURN_LONG(intern->heap->count);
}
/* }}} */
/* {{{ proto void SplHeap::next() U
Move to next entry */
SPL_METHOD(SplHeap, next)
{
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
spl_ptr_heap_element elem = spl_ptr_heap_delete_top(intern->heap,
getThis() TSRMLS_CC);
if (elem != NULL) {
zval_ptr_dtor((zval **)&elem);
}
}
/* }}} */
/* {{{ proto bool SplHeap::valid() U
Check whether the datastructure contains more entries */
SPL_METHOD(SplHeap, valid)
{
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
RETURN_BOOL(intern->heap->count != 0);
}
/* }}} */
/* {{{ proto void SplHeap::rewind() U
Rewind the datastructure back to the start */
SPL_METHOD(SplHeap, rewind)
{
/* do nothing, the iterator always points to the top element */
}
/* }}} */
/* {{{ proto mixed|NULL SplHeap::current() U
Return current datastructure entry */
SPL_METHOD(SplHeap, current)
{
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
zval *element = (zval *)intern->heap->elements[0];
if (!intern->heap->count || !element) {
RETURN_NULL();
} else {
RETURN_ZVAL(element, 1, 0);
}
}
/* }}} */
/* {{{ proto mixed|NULL SplPriorityQueue::current() U
Return current datastructure entry */
SPL_METHOD(SplPriorityQueue, current)
{
spl_heap_object *intern =
(spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
zval **element = (zval **)&intern->heap->elements[0];
if (!intern->heap->count || !*element) {
RETURN_NULL();
} else {
zval **data = spl_pqueue_extract_helper(element, intern->flags);
if (!data) {
zend_error(E_RECOVERABLE_ERROR, "Unable to extract from
the PriorityQueue node");
RETURN_NULL();
}
RETURN_ZVAL(*data, 1, 0);
}
}
/* }}} */
/* iterator handler table */
zend_object_iterator_funcs spl_heap_it_funcs = {
spl_heap_it_dtor,
spl_heap_it_valid,
spl_heap_it_get_current_data,
spl_heap_it_get_current_key,
spl_heap_it_move_forward,
spl_heap_it_rewind
};
zend_object_iterator_funcs spl_pqueue_it_funcs = {
spl_heap_it_dtor,
spl_heap_it_valid,
spl_pqueue_it_get_current_data,
spl_heap_it_get_current_key,
spl_heap_it_move_forward,
spl_heap_it_rewind
};
zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object,
int by_ref TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator;
spl_heap_object *heap_object =
(spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
if (by_ref) {
zend_throw_exception(spl_ce_RuntimeException, "An iterator
cannot be used with foreach by reference", 0 TSRMLS_CC);
return NULL;
}
Z_ADDREF_P(object);
iterator = emalloc(sizeof(spl_heap_it));
iterator->intern.it.data = (void*)object;
iterator->intern.it.funcs = &spl_heap_it_funcs;
iterator->intern.ce = ce;
iterator->intern.value = NULL;
iterator->flags = heap_object->flags;
iterator->object = heap_object;
return (zend_object_iterator*)iterator;
}
/* }}} */
zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval
*object, int by_ref TSRMLS_DC) /* {{{ */
{
spl_heap_it *iterator;
spl_heap_object *heap_object =
(spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
if (by_ref) {
zend_throw_exception(spl_ce_RuntimeException, "An iterator
cannot be used with foreach by reference", 0 TSRMLS_CC);
return NULL;
}
Z_ADDREF_P(object);
iterator = emalloc(sizeof(spl_heap_it));
iterator->intern.it.data = (void*)object;
iterator->intern.it.funcs = &spl_pqueue_it_funcs;
iterator->intern.ce = ce;
iterator->intern.value = NULL;
iterator->flags = heap_object->flags;
iterator->object = heap_object;
return (zend_object_iterator*)iterator;
}
/* }}} */
static
ZEND_BEGIN_ARG_INFO(arginfo_heap_insert, 0)
ZEND_ARG_INFO(0, value)
ZEND_END_ARG_INFO()
static
ZEND_BEGIN_ARG_INFO(arginfo_heap_compare, 0)
ZEND_ARG_INFO(0, a)
ZEND_ARG_INFO(0, b)
ZEND_END_ARG_INFO()
static
ZEND_BEGIN_ARG_INFO(arginfo_pqueue_insert, 0)
ZEND_ARG_INFO(0, value)
ZEND_ARG_INFO(0, priority)
ZEND_END_ARG_INFO()
static
ZEND_BEGIN_ARG_INFO(arginfo_pqueue_setflags, 0)
ZEND_ARG_INFO(0, flags)
ZEND_END_ARG_INFO()
static const zend_function_entry spl_funcs_SplMinHeap[] = {
SPL_ME(SplMinHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
{NULL, NULL, NULL}
};
static const zend_function_entry spl_funcs_SplMaxHeap[] = {
SPL_ME(SplMaxHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
{NULL, NULL, NULL}
};
static const zend_function_entry spl_funcs_SplPriorityQueue[] = {
SPL_ME(SplPriorityQueue, compare, arginfo_heap_compare,
ZEND_ACC_PUBLIC)
SPL_ME(SplPriorityQueue, insert, arginfo_pqueue_insert,
ZEND_ACC_PUBLIC)
SPL_ME(SplPriorityQueue, setExtractFlags,
arginfo_pqueue_setflags, ZEND_ACC_PUBLIC)
SPL_ME(SplPriorityQueue, top, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplPriorityQueue, extract, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, count, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, isEmpty, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, rewind, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplPriorityQueue, current, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, key, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, next, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, valid, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, recoverFromCorruption, NULL,
ZEND_ACC_PUBLIC)
{NULL, NULL, NULL}
};
static const zend_function_entry spl_funcs_SplHeap[] = {
SPL_ME(SplHeap, extract, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, insert, arginfo_heap_insert,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, top, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, count, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, isEmpty, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, rewind, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, current, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, key, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, next, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, valid, NULL,
ZEND_ACC_PUBLIC)
SPL_ME(SplHeap, recoverFromCorruption, NULL,
ZEND_ACC_PUBLIC)
ZEND_FENTRY(compare, NULL, NULL, ZEND_ACC_PROTECTED|ZEND_ACC_ABSTRACT)
{NULL, NULL, NULL}
};
/* }}} */
PHP_MINIT_FUNCTION(spl_heap) /* {{{ */
{
REGISTER_SPL_STD_CLASS_EX(SplHeap, spl_heap_object_new,
spl_funcs_SplHeap);
memcpy(&spl_handler_SplHeap, zend_get_std_object_handlers(),
sizeof(zend_object_handlers));
spl_handler_SplHeap.clone_obj = spl_heap_object_clone;
spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
spl_handler_SplHeap.get_debug_info = spl_heap_object_get_debug_info;
REGISTER_SPL_IMPLEMENTS(SplHeap, Iterator);
REGISTER_SPL_IMPLEMENTS(SplHeap, Countable);
spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
REGISTER_SPL_SUB_CLASS_EX(SplMinHeap, SplHeap,
spl_heap_object_new, spl_funcs_SplMinHeap);
REGISTER_SPL_SUB_CLASS_EX(SplMaxHeap, SplHeap,
spl_heap_object_new, spl_funcs_SplMaxHeap);
REGISTER_SPL_STD_CLASS_EX(SplPriorityQueue, spl_heap_object_new,
spl_funcs_SplPriorityQueue);
memcpy(&spl_handler_SplPriorityQueue, zend_get_std_object_handlers(),
sizeof(zend_object_handlers));
spl_handler_SplPriorityQueue.clone_obj = spl_heap_object_clone;
spl_handler_SplPriorityQueue.count_elements =
spl_heap_object_count_elements;
spl_handler_SplPriorityQueue.get_debug_info =
spl_pqueue_object_get_debug_info;
REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Iterator);
REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Countable);
spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_BOTH",
SPL_PQUEUE_EXTR_BOTH);
REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_PRIORITY",
SPL_PQUEUE_EXTR_PRIORITY);
REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_DATA",
SPL_PQUEUE_EXTR_DATA);
return SUCCESS;
}
/*
* Local variables:
* tab-width: 4
* c-basic-offset: 4
* End:
* vim600: fdm=marker
* vim: noet sw=4 ts=4
*/
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/spl_heap.h?view=markup&rev=1.1
Index: php-src/ext/spl/spl_heap.h
+++ php-src/ext/spl/spl_heap.h
/*
+----------------------------------------------------------------------+
| PHP Version 5 |
+----------------------------------------------------------------------+
| Copyright (c) 1997-2008 The PHP Group |
+----------------------------------------------------------------------+
| This source file is subject to version 3.01 of the PHP license, |
| that is bundled with this package in the file LICENSE, and is |
| available through the world-wide-web at the following url: |
| http://www.php.net/license/3_01.txt |
| If you did not receive a copy of the PHP license and are unable to |
| obtain it through the world-wide-web, please send a note to |
| [EMAIL PROTECTED] so we can mail you a copy immediately. |
+----------------------------------------------------------------------+
| Authors: Etienne Kneuss <[EMAIL PROTECTED]> |
+----------------------------------------------------------------------+
*/
/* $Id: spl_heap.h,v 1.1 2008/02/25 23:36:36 colder Exp $ */
#ifndef SPL_HEAP_H
#define SPL_HEAP_H
#include "php.h"
#include "php_spl.h"
PHPAPI zend_class_entry *spl_ce_SplHeap;
PHPAPI zend_class_entry *spl_ce_SplMinHeap;
PHPAPI zend_class_entry *spl_ce_SplMaxHeap;
PHPAPI zend_class_entry *spl_ce_SplPriorityQueue;
PHP_MINIT_FUNCTION(spl_heap);
#endif /* SPL_HEAP_H */
/*
* Local Variables:
* c-basic-offset: 4
* tab-width: 4
* End:
* vim600: fdm=marker
* vim: noet sw=4 ts=4
*/
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_001.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_001.phpt
+++ php-src/ext/spl/tests/heap_001.phpt
--TEST--
SPL: SplMaxHeap: std operations
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$h = new SplMaxHeap();
// errors
try {
$h->extract();
} catch (RuntimeException $e) {
echo "Exception: ".$e->getMessage()."\n";
}
$h->insert(1);
$h->insert(2);
$h->insert(3);
$h->insert(3);
$h->insert(3);
echo $h->count()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->count()."\n";
echo "--\n";
$b = 4;
$h->insert($b);
$b = 5;
echo $h->extract()."\n";
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
Exception: Can't extract from an empty heap
5
3
3
3
2
1
0
--
4
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_002.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_002.phpt
+++ php-src/ext/spl/tests/heap_002.phpt
--TEST--
SPL: SplMinHeap: std operations
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$h = new SplMinHeap();
// errors
try {
$h->extract();
} catch (RuntimeException $e) {
echo "Exception: ".$e->getMessage()."\n";
}
$h->insert(1);
$h->insert(2);
$h->insert(3);
$h->insert(3);
$h->insert(3);
echo $h->count()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->extract()."\n";
echo $h->count()."\n";
echo "--\n";
$b = 4;
$h->insert($b);
$b = 5;
echo $h->extract()."\n";
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
Exception: Can't extract from an empty heap
5
1
2
3
3
3
0
--
4
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_003.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_003.phpt
+++ php-src/ext/spl/tests/heap_003.phpt
--TEST--
SPL: SplHeap: comparison callback
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
class myHeap extends SplHeap {
public function compare($a, $b) {
if ($a > $b) {
$result = 1;
} else if ($a < $b) {
$result = -1;
} else {
$result = 0;
}
return $result;
}
}
$h = new myHeap;
$in = range(0,10);
shuffle($in);
foreach ($in as $i) {
$h->insert($i);
}
foreach ($h as $out) {
echo $out."\n";
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
10
9
8
7
6
5
4
3
2
1
0
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_004.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_004.phpt
+++ php-src/ext/spl/tests/heap_004.phpt
--TEST--
SPL: SplHeap: exceptions
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
class myHeap extends SplHeap {
public function compare($a, $b) {
throw new exception("foo");
}
}
$h = new myHeap;
try {
$h->insert(1);
echo "inserted 1\n";
$h->insert(2);
echo "inserted 2\n";
$h->insert(3);
echo "inserted 3\n";
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
$h->insert(4);
echo "inserted 4\n";
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
echo "Recovering..\n";
$h->recoverFromCorruption();
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
inserted 1
Exception: foo
Exception: Heap is corrupted, heap properties are no longer ensured.
Exception: Heap is corrupted, heap properties are no longer ensured.
Exception: Heap is corrupted, heap properties are no longer ensured.
Recovering..
int(1)
int(2)
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_005.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_005.phpt
+++ php-src/ext/spl/tests/heap_005.phpt
--TEST--
SPL: SplMinHeap: large unordered input iterated
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$input = range(1,100);
shuffle($input);
$h = new SplMinHeap();
foreach($input as $i) {
$h->insert($i);
}
foreach ($h as $k => $o) {
echo "$k => $o\n";
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
100 => 1
99 => 2
98 => 3
97 => 4
96 => 5
95 => 6
94 => 7
93 => 8
92 => 9
91 => 10
90 => 11
89 => 12
88 => 13
87 => 14
86 => 15
85 => 16
84 => 17
83 => 18
82 => 19
81 => 20
80 => 21
79 => 22
78 => 23
77 => 24
76 => 25
75 => 26
74 => 27
73 => 28
72 => 29
71 => 30
70 => 31
69 => 32
68 => 33
67 => 34
66 => 35
65 => 36
64 => 37
63 => 38
62 => 39
61 => 40
60 => 41
59 => 42
58 => 43
57 => 44
56 => 45
55 => 46
54 => 47
53 => 48
52 => 49
51 => 50
50 => 51
49 => 52
48 => 53
47 => 54
46 => 55
45 => 56
44 => 57
43 => 58
42 => 59
41 => 60
40 => 61
39 => 62
38 => 63
37 => 64
36 => 65
35 => 66
34 => 67
33 => 68
32 => 69
31 => 70
30 => 71
29 => 72
28 => 73
27 => 74
26 => 75
25 => 76
24 => 77
23 => 78
22 => 79
21 => 80
20 => 81
19 => 82
18 => 83
17 => 84
16 => 85
15 => 86
14 => 87
13 => 88
12 => 89
11 => 90
10 => 91
9 => 92
8 => 93
7 => 94
6 => 95
5 => 96
4 => 97
3 => 98
2 => 99
1 => 100
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_006.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_006.phpt
+++ php-src/ext/spl/tests/heap_006.phpt
--TEST--
SPL: SplMaxHeap: large unordered input iterated
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$input = range(1,100);
shuffle($input);
$h = new SplMaxHeap();
foreach($input as $i) {
$h->insert($i);
}
foreach ($h as $k => $o) {
echo "$k => $o\n";
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
100 => 100
99 => 99
98 => 98
97 => 97
96 => 96
95 => 95
94 => 94
93 => 93
92 => 92
91 => 91
90 => 90
89 => 89
88 => 88
87 => 87
86 => 86
85 => 85
84 => 84
83 => 83
82 => 82
81 => 81
80 => 80
79 => 79
78 => 78
77 => 77
76 => 76
75 => 75
74 => 74
73 => 73
72 => 72
71 => 71
70 => 70
69 => 69
68 => 68
67 => 67
66 => 66
65 => 65
64 => 64
63 => 63
62 => 62
61 => 61
60 => 60
59 => 59
58 => 58
57 => 57
56 => 56
55 => 55
54 => 54
53 => 53
52 => 52
51 => 51
50 => 50
49 => 49
48 => 48
47 => 47
46 => 46
45 => 45
44 => 44
43 => 43
42 => 42
41 => 41
40 => 40
39 => 39
38 => 38
37 => 37
36 => 36
35 => 35
34 => 34
33 => 33
32 => 32
31 => 31
30 => 30
29 => 29
28 => 28
27 => 27
26 => 26
25 => 25
24 => 24
23 => 23
22 => 22
21 => 21
20 => 20
19 => 19
18 => 18
17 => 17
16 => 16
15 => 15
14 => 14
13 => 13
12 => 12
11 => 11
10 => 10
9 => 9
8 => 8
7 => 7
6 => 6
5 => 5
4 => 4
3 => 3
2 => 2
1 => 1
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_007.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_007.phpt
+++ php-src/ext/spl/tests/heap_007.phpt
--TEST--
SPL: SplHeap: iteration through methods
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$h = new SplMaxHeap();
$h->insert(1);
$h->insert(5);
$h->insert(0);
$h->insert(4);
$h->rewind();
echo "count(\$h) = ".count($h)."\n";
echo "\$h->count() = ".$h->count()."\n";
while ($h->valid()) {
$k = $h->key();
$v = $h->current();
echo "$k=>$v\n";
$h->next();
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
count($h) = 4
$h->count() = 4
4=>5
3=>4
2=>1
1=>0
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/heap_008.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/heap_008.phpt
+++ php-src/ext/spl/tests/heap_008.phpt
--TEST--
SPL: SplHeap: var_dump
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$h = new SplMaxHeap();
$h->insert(1);
$h->insert(5);
$h->insert(0);
$h->insert(4);
var_dump($h);
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
object(SplMaxHeap)#1 (3) {
["flags":"SplHeap":private]=>
int(0)
["isCorrupted":"SplHeap":private]=>
bool(false)
["heap":"SplHeap":private]=>
array(4) {
[0]=>
int(5)
[1]=>
int(4)
[2]=>
int(0)
[3]=>
int(1)
}
}
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/pqueue_001.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/pqueue_001.phpt
+++ php-src/ext/spl/tests/pqueue_001.phpt
--TEST--
SPL: SplPriorityQueue: std operations and extract flags
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$pq = new SplPriorityQueue();
// errors
try {
$pq->extract();
} catch (RuntimeException $e) {
echo "Exception: ".$e->getMessage()."\n";
}
$pq->insert("a", 1);
$pq->insert("b", 2);
$pq->insert("c", 0);
foreach ($pq as $k=>$v) {
echo "$k=>".print_r($v, 1)."\n";
}
echo "EXTR_BOTH\n";
$pq1 = new SplPriorityQueue();
$pq1->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$pq1->insert("a", 1);
$pq1->insert("b", 2);
$pq1->insert("c", 0);
foreach ($pq1 as $k=>$v) {
echo "$k=>".print_r($v, 1)."\n";
}
echo "EXTR_DATA\n";
$pq2 = new SplPriorityQueue();
$pq2->setExtractFlags(SplPriorityQueue::EXTR_DATA);
$pq2->insert("a", 1);
$pq2->insert("b", 2);
$pq2->insert("c", 0);
foreach ($pq2 as $k=>$v) {
echo "$k=>".print_r($v, 1)."\n";
}
echo "EXTR_PRIORITY\n";
$pq3 = new SplPriorityQueue();
$pq3->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
$pq3->insert("a", 1);
$pq3->insert("b", 2);
$pq3->insert("c", 0);
foreach ($pq3 as $k=>$v) {
echo "$k=>".print_r($v, 1)."\n";
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
Exception: Can't extract from an empty heap
3=>b
2=>a
1=>c
EXTR_BOTH
3=>Array
(
[data] => b
[priority] => 2
)
2=>Array
(
[data] => a
[priority] => 1
)
1=>Array
(
[data] => c
[priority] => 0
)
EXTR_DATA
3=>b
2=>a
1=>c
EXTR_PRIORITY
3=>2
2=>1
1=>0
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/pqueue_002.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/pqueue_002.phpt
+++ php-src/ext/spl/tests/pqueue_002.phpt
--TEST--
SPL: SplPriorityQueue: exceptions
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
class myPQueue extends SplPriorityQueue {
public function compare($a, $b) {
throw new exception("foo");
}
}
$h = new myPQueue;
try {
$h->insert(1, 1);
echo "inserted 1\n";
$h->insert(2, 1);
echo "inserted 2\n";
$h->insert(3, 1);
echo "inserted 3\n";
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
$h->insert(4, 1);
echo "inserted 4\n";
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
echo "Recovering..\n";
$h->recoverFromCorruption();
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
try {
var_dump($h->extract());
} catch(Exception $e) {
echo "Exception: ".$e->getMessage()."\n";
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
inserted 1
Exception: foo
Exception: Heap is corrupted, heap properties are no longer ensured.
Exception: Heap is corrupted, heap properties are no longer ensured.
Exception: Heap is corrupted, heap properties are no longer ensured.
Recovering..
int(1)
int(2)
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/pqueue_003.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/pqueue_003.phpt
+++ php-src/ext/spl/tests/pqueue_003.phpt
--TEST--
SPL: SplPriorityQueue: iteration through methods
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$h = new SplPriorityQueue();
$h->insert(1, 1);
$h->insert(5, 5);
$h->insert(0, 0);
$h->insert(4, 4);
$h->rewind();
echo "count(\$h) = ".count($h)."\n";
echo "\$h->count() = ".$h->count()."\n";
while ($h->valid()) {
$k = $h->key();
$v = $h->current();
echo "$k=>$v\n";
$h->next();
}
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
count($h) = 4
$h->count() = 4
4=>5
3=>4
2=>1
1=>0
===DONE===
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/tests/pqueue_004.phpt?view=markup&rev=1.1
Index: php-src/ext/spl/tests/pqueue_004.phpt
+++ php-src/ext/spl/tests/pqueue_004.phpt
--TEST--
SPL: SplPriorityQueue: var_dump
--SKIPIF--
<?php if (!extension_loaded("spl")) print "skip"; ?>
--FILE--
<?php
$pq = new SplPriorityQueue();
$pq->insert("a", 0);
$pq->insert("b", 1);
$pq->insert("c", 5);
$pq->insert("d", -2);
var_dump($pq);
?>
===DONE===
<?php exit(0); ?>
--EXPECTF--
object(SplPriorityQueue)#1 (3) {
["flags":"SplPriorityQueue":private]=>
int(1)
["isCorrupted":"SplPriorityQueue":private]=>
bool(false)
["heap":"SplPriorityQueue":private]=>
array(4) {
[0]=>
array(2) {
["data"]=>
string(1) "c"
["priority"]=>
int(5)
}
[1]=>
array(2) {
["data"]=>
string(1) "a"
["priority"]=>
int(0)
}
[2]=>
array(2) {
["data"]=>
string(1) "b"
["priority"]=>
int(1)
}
[3]=>
array(2) {
["data"]=>
string(1) "d"
["priority"]=>
int(-2)
}
}
}
===DONE===
--
PHP CVS Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
