colder Mon Feb 25 23:39:09 2008 UTC Added files: (Branch: PHP_5_3) /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: MFH: SplHeap, SplMinHeap, SplMaxHeap, SplPriorityQueue implementation
http://cvs.php.net/viewvc.cgi/php-src/ext/spl/config.m4?r1=1.13.2.4.2.3.2.1&r2=1.13.2.4.2.3.2.2&diff_format=u Index: php-src/ext/spl/config.m4 diff -u php-src/ext/spl/config.m4:1.13.2.4.2.3.2.1 php-src/ext/spl/config.m4:1.13.2.4.2.3.2.2 --- php-src/ext/spl/config.m4:1.13.2.4.2.3.2.1 Tue Jan 15 09:38:15 2008 +++ php-src/ext/spl/config.m4 Mon Feb 25 23:39:08 2008 @@ -1,4 +1,4 @@ -dnl $Id: config.m4,v 1.13.2.4.2.3.2.1 2008/01/15 09:38:15 colder Exp $ +dnl $Id: config.m4,v 1.13.2.4.2.3.2.2 2008/02/25 23:39:08 colder Exp $ dnl config.m4 for extension SPL PHP_ARG_ENABLE(spl, enable SPL suppport, @@ -26,7 +26,7 @@ CPPFLAGS=$old_CPPFLAGS 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.7.6.1&r2=1.7.6.2&diff_format=u Index: php-src/ext/spl/config.w32 diff -u php-src/ext/spl/config.w32:1.7.6.1 php-src/ext/spl/config.w32:1.7.6.2 --- php-src/ext/spl/config.w32:1.7.6.1 Tue Jan 15 09:38:15 2008 +++ php-src/ext/spl/config.w32 Mon Feb 25 23:39:08 2008 @@ -1,4 +1,4 @@ -// $Id: config.w32,v 1.7.6.1 2008/01/15 09:38:15 colder Exp $ +// $Id: config.w32,v 1.7.6.2 2008/02/25 23:39:08 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.52.2.28.2.17.2.12&r2=1.52.2.28.2.17.2.13&diff_format=u Index: php-src/ext/spl/php_spl.c diff -u php-src/ext/spl/php_spl.c:1.52.2.28.2.17.2.12 php-src/ext/spl/php_spl.c:1.52.2.28.2.17.2.13 --- php-src/ext/spl/php_spl.c:1.52.2.28.2.17.2.12 Mon Feb 4 17:07:06 2008 +++ php-src/ext/spl/php_spl.c Mon Feb 25 23:39:08 2008 @@ -16,7 +16,7 @@ +----------------------------------------------------------------------+ */ -/* $Id: php_spl.c,v 1.52.2.28.2.17.2.12 2008/02/04 17:07:06 helly Exp $ */ +/* $Id: php_spl.c,v 1.52.2.28.2.17.2.13 2008/02/25 23:39:08 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" @@ -157,6 +158,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); \ @@ -749,6 +754,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