From cb51a844183fcb97ecced02e69f9b463752edc6c Mon Sep 17 00:00:00 2001 From: Etienne Kneuss Date: Mon, 25 Feb 2008 23:36:36 +0000 Subject: [PATCH] SplHeap, SplMinHeap, SplMaxHeap, SplPriorityQueue implementation --- ext/spl/config.m4 | 4 +- ext/spl/config.w32 | 2 +- ext/spl/php_spl.c | 6 + ext/spl/spl_heap.c | 1192 +++++++++++++++++++++++++++++++++ ext/spl/spl_heap.h | 44 ++ ext/spl/tests/heap_001.phpt | 52 ++ ext/spl/tests/heap_002.phpt | 52 ++ ext/spl/tests/heap_003.phpt | 46 ++ ext/spl/tests/heap_004.phpt | 69 ++ ext/spl/tests/heap_005.phpt | 123 ++++ ext/spl/tests/heap_006.phpt | 123 ++++ ext/spl/tests/heap_007.phpt | 33 + ext/spl/tests/heap_008.phpt | 36 + ext/spl/tests/pqueue_001.phpt | 98 +++ ext/spl/tests/pqueue_002.phpt | 69 ++ ext/spl/tests/pqueue_003.phpt | 33 + ext/spl/tests/pqueue_004.phpt | 56 ++ 17 files changed, 2035 insertions(+), 3 deletions(-) create mode 100644 ext/spl/spl_heap.c create mode 100644 ext/spl/spl_heap.h create mode 100644 ext/spl/tests/heap_001.phpt create mode 100644 ext/spl/tests/heap_002.phpt create mode 100644 ext/spl/tests/heap_003.phpt create mode 100644 ext/spl/tests/heap_004.phpt create mode 100644 ext/spl/tests/heap_005.phpt create mode 100644 ext/spl/tests/heap_006.phpt create mode 100644 ext/spl/tests/heap_007.phpt create mode 100644 ext/spl/tests/heap_008.phpt create mode 100644 ext/spl/tests/pqueue_001.phpt create mode 100644 ext/spl/tests/pqueue_002.phpt create mode 100644 ext/spl/tests/pqueue_003.phpt create mode 100644 ext/spl/tests/pqueue_004.phpt diff --git a/ext/spl/config.m4 b/ext/spl/config.m4 index 370b3c0bcb..a21d91958a 100755 --- a/ext/spl/config.m4 +++ b/ext/spl/config.m4 @@ -29,7 +29,7 @@ int main(int argc, char **argv) { 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 diff --git a/ext/spl/config.w32 b/ext/spl/config.w32 index 8a04a962bb..ebed9c6bc5 100644 --- a/ext/spl/config.w32 +++ b/ext/spl/config.w32 @@ -7,6 +7,6 @@ if (PHP_SPL != "no") { 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); } diff --git a/ext/spl/php_spl.c b/ext/spl/php_spl.c index cda385dc3f..5503f74056 100755 --- a/ext/spl/php_spl.c +++ b/ext/spl/php_spl.c @@ -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 @@ PHP_FUNCTION(class_implements) 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_FUNCTION(spl) 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; diff --git a/ext/spl/spl_heap.c b/ext/spl/spl_heap.c new file mode 100644 index 0000000000..227d2343a1 --- /dev/null +++ b/ext/spl/spl_heap.c @@ -0,0 +1,1192 @@ +/* + +----------------------------------------------------------------------+ + | 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 | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Etienne Kneuss | + +----------------------------------------------------------------------+ + */ + +/* $Id$ */ + +#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 + */ + diff --git a/ext/spl/spl_heap.h b/ext/spl/spl_heap.h new file mode 100644 index 0000000000..c1d403c69f --- /dev/null +++ b/ext/spl/spl_heap.h @@ -0,0 +1,44 @@ +/* + +----------------------------------------------------------------------+ + | 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 | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Etienne Kneuss | + +----------------------------------------------------------------------+ + */ + +/* $Id$ */ + +#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 + */ diff --git a/ext/spl/tests/heap_001.phpt b/ext/spl/tests/heap_001.phpt new file mode 100644 index 0000000000..3b4316ffd8 --- /dev/null +++ b/ext/spl/tests/heap_001.phpt @@ -0,0 +1,52 @@ +--TEST-- +SPL: SplMaxHeap: std operations +--SKIPIF-- + +--FILE-- +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=== + +--EXPECTF-- +Exception: Can't extract from an empty heap +5 +3 +3 +3 +2 +1 +0 +-- +4 +===DONE=== diff --git a/ext/spl/tests/heap_002.phpt b/ext/spl/tests/heap_002.phpt new file mode 100644 index 0000000000..815f5fd90f --- /dev/null +++ b/ext/spl/tests/heap_002.phpt @@ -0,0 +1,52 @@ +--TEST-- +SPL: SplMinHeap: std operations +--SKIPIF-- + +--FILE-- +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=== + +--EXPECTF-- +Exception: Can't extract from an empty heap +5 +1 +2 +3 +3 +3 +0 +-- +4 +===DONE=== diff --git a/ext/spl/tests/heap_003.phpt b/ext/spl/tests/heap_003.phpt new file mode 100644 index 0000000000..b81c043ca4 --- /dev/null +++ b/ext/spl/tests/heap_003.phpt @@ -0,0 +1,46 @@ +--TEST-- +SPL: SplHeap: comparison callback +--SKIPIF-- + +--FILE-- + $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=== + +--EXPECTF-- +10 +9 +8 +7 +6 +5 +4 +3 +2 +1 +0 +===DONE=== diff --git a/ext/spl/tests/heap_004.phpt b/ext/spl/tests/heap_004.phpt new file mode 100644 index 0000000000..55aca4ccb3 --- /dev/null +++ b/ext/spl/tests/heap_004.phpt @@ -0,0 +1,69 @@ +--TEST-- +SPL: SplHeap: exceptions +--SKIPIF-- + +--FILE-- +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=== + +--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=== diff --git a/ext/spl/tests/heap_005.phpt b/ext/spl/tests/heap_005.phpt new file mode 100644 index 0000000000..575ddba4ce --- /dev/null +++ b/ext/spl/tests/heap_005.phpt @@ -0,0 +1,123 @@ +--TEST-- +SPL: SplMinHeap: large unordered input iterated +--SKIPIF-- + +--FILE-- +insert($i); +} + +foreach ($h as $k => $o) { + echo "$k => $o\n"; +} +?> +===DONE=== + +--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=== diff --git a/ext/spl/tests/heap_006.phpt b/ext/spl/tests/heap_006.phpt new file mode 100644 index 0000000000..08162ff357 --- /dev/null +++ b/ext/spl/tests/heap_006.phpt @@ -0,0 +1,123 @@ +--TEST-- +SPL: SplMaxHeap: large unordered input iterated +--SKIPIF-- + +--FILE-- +insert($i); +} + +foreach ($h as $k => $o) { + echo "$k => $o\n"; +} +?> +===DONE=== + +--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=== diff --git a/ext/spl/tests/heap_007.phpt b/ext/spl/tests/heap_007.phpt new file mode 100644 index 0000000000..594ffc0180 --- /dev/null +++ b/ext/spl/tests/heap_007.phpt @@ -0,0 +1,33 @@ +--TEST-- +SPL: SplHeap: iteration through methods +--SKIPIF-- + +--FILE-- +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=== + +--EXPECTF-- +count($h) = 4 +$h->count() = 4 +4=>5 +3=>4 +2=>1 +1=>0 +===DONE=== diff --git a/ext/spl/tests/heap_008.phpt b/ext/spl/tests/heap_008.phpt new file mode 100644 index 0000000000..2b3c9a4a3c --- /dev/null +++ b/ext/spl/tests/heap_008.phpt @@ -0,0 +1,36 @@ +--TEST-- +SPL: SplHeap: var_dump +--SKIPIF-- + +--FILE-- +insert(1); +$h->insert(5); +$h->insert(0); +$h->insert(4); + +var_dump($h); +?> +===DONE=== + +--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=== diff --git a/ext/spl/tests/pqueue_001.phpt b/ext/spl/tests/pqueue_001.phpt new file mode 100644 index 0000000000..8dae2ef510 --- /dev/null +++ b/ext/spl/tests/pqueue_001.phpt @@ -0,0 +1,98 @@ +--TEST-- +SPL: SplPriorityQueue: std operations and extract flags +--SKIPIF-- + +--FILE-- +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=== + +--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=== diff --git a/ext/spl/tests/pqueue_002.phpt b/ext/spl/tests/pqueue_002.phpt new file mode 100644 index 0000000000..c47a6fe5c8 --- /dev/null +++ b/ext/spl/tests/pqueue_002.phpt @@ -0,0 +1,69 @@ +--TEST-- +SPL: SplPriorityQueue: exceptions +--SKIPIF-- + +--FILE-- +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=== + +--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=== diff --git a/ext/spl/tests/pqueue_003.phpt b/ext/spl/tests/pqueue_003.phpt new file mode 100644 index 0000000000..87d9eda223 --- /dev/null +++ b/ext/spl/tests/pqueue_003.phpt @@ -0,0 +1,33 @@ +--TEST-- +SPL: SplPriorityQueue: iteration through methods +--SKIPIF-- + +--FILE-- +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=== + +--EXPECTF-- +count($h) = 4 +$h->count() = 4 +4=>5 +3=>4 +2=>1 +1=>0 +===DONE=== diff --git a/ext/spl/tests/pqueue_004.phpt b/ext/spl/tests/pqueue_004.phpt new file mode 100644 index 0000000000..3e781ddc14 --- /dev/null +++ b/ext/spl/tests/pqueue_004.phpt @@ -0,0 +1,56 @@ +--TEST-- +SPL: SplPriorityQueue: var_dump +--SKIPIF-- + +--FILE-- +insert("a", 0); +$pq->insert("b", 1); +$pq->insert("c", 5); +$pq->insert("d", -2); + +var_dump($pq); +?> +===DONE=== + +--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=== -- 2.50.1