Annotation of embedaddon/php/ext/spl/spl_heap.c, revision 1.1
1.1 ! misho 1: /*
! 2: +----------------------------------------------------------------------+
! 3: | PHP Version 5 |
! 4: +----------------------------------------------------------------------+
! 5: | Copyright (c) 1997-2012 The PHP Group |
! 6: +----------------------------------------------------------------------+
! 7: | This source file is subject to version 3.01 of the PHP license, |
! 8: | that is bundled with this package in the file LICENSE, and is |
! 9: | available through the world-wide-web at the following url: |
! 10: | http://www.php.net/license/3_01.txt |
! 11: | If you did not receive a copy of the PHP license and are unable to |
! 12: | obtain it through the world-wide-web, please send a note to |
! 13: | license@php.net so we can mail you a copy immediately. |
! 14: +----------------------------------------------------------------------+
! 15: | Authors: Etienne Kneuss <colder@php.net> |
! 16: +----------------------------------------------------------------------+
! 17: */
! 18:
! 19: /* $Id: spl_heap.c 321634 2012-01-01 13:15:04Z felipe $ */
! 20:
! 21: #ifdef HAVE_CONFIG_H
! 22: # include "config.h"
! 23: #endif
! 24:
! 25: #include "php.h"
! 26: #include "zend_exceptions.h"
! 27:
! 28: #include "php_spl.h"
! 29: #include "spl_functions.h"
! 30: #include "spl_engine.h"
! 31: #include "spl_iterators.h"
! 32: #include "spl_heap.h"
! 33: #include "spl_exceptions.h"
! 34:
! 35: #define PTR_HEAP_BLOCK_SIZE 64
! 36:
! 37: #define SPL_HEAP_CORRUPTED 0x00000001
! 38:
! 39: #define SPL_PQUEUE_EXTR_MASK 0x00000003
! 40: #define SPL_PQUEUE_EXTR_BOTH 0x00000003
! 41: #define SPL_PQUEUE_EXTR_DATA 0x00000001
! 42: #define SPL_PQUEUE_EXTR_PRIORITY 0x00000002
! 43:
! 44: zend_object_handlers spl_handler_SplHeap;
! 45: zend_object_handlers spl_handler_SplPriorityQueue;
! 46:
! 47: PHPAPI zend_class_entry *spl_ce_SplHeap;
! 48: PHPAPI zend_class_entry *spl_ce_SplMaxHeap;
! 49: PHPAPI zend_class_entry *spl_ce_SplMinHeap;
! 50: PHPAPI zend_class_entry *spl_ce_SplPriorityQueue;
! 51:
! 52: typedef void *spl_ptr_heap_element;
! 53:
! 54: typedef void (*spl_ptr_heap_dtor_func)(spl_ptr_heap_element TSRMLS_DC);
! 55: typedef void (*spl_ptr_heap_ctor_func)(spl_ptr_heap_element TSRMLS_DC);
! 56: typedef int (*spl_ptr_heap_cmp_func)(spl_ptr_heap_element, spl_ptr_heap_element, void* TSRMLS_DC);
! 57:
! 58: typedef struct _spl_ptr_heap {
! 59: spl_ptr_heap_element *elements;
! 60: spl_ptr_heap_ctor_func ctor;
! 61: spl_ptr_heap_dtor_func dtor;
! 62: spl_ptr_heap_cmp_func cmp;
! 63: int count;
! 64: int max_size;
! 65: int flags;
! 66: } spl_ptr_heap;
! 67:
! 68: typedef struct _spl_heap_object spl_heap_object;
! 69: typedef struct _spl_heap_it spl_heap_it;
! 70:
! 71: struct _spl_heap_object {
! 72: zend_object std;
! 73: spl_ptr_heap *heap;
! 74: zval *retval;
! 75: int flags;
! 76: zend_class_entry *ce_get_iterator;
! 77: zend_function *fptr_cmp;
! 78: zend_function *fptr_count;
! 79: HashTable *debug_info;
! 80: };
! 81:
! 82: /* define an overloaded iterator structure */
! 83: struct _spl_heap_it {
! 84: zend_user_iterator intern;
! 85: int flags;
! 86: spl_heap_object *object;
! 87: };
! 88:
! 89: /* {{{ spl_ptr_heap */
! 90: static void spl_ptr_heap_zval_dtor(spl_ptr_heap_element elem TSRMLS_DC) { /* {{{ */
! 91: if (elem) {
! 92: zval_ptr_dtor((zval **)&elem);
! 93: }
! 94: }
! 95: /* }}} */
! 96:
! 97: static void spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC) { /* {{{ */
! 98: Z_ADDREF_P((zval *)elem);
! 99: }
! 100: /* }}} */
! 101:
! 102: static int spl_ptr_heap_cmp_cb_helper(zval *object, spl_heap_object *heap_object, zval *a, zval *b, long *result TSRMLS_DC) { /* {{{ */
! 103: zval *result_p = NULL;
! 104:
! 105: zend_call_method_with_2_params(&object, heap_object->std.ce, &heap_object->fptr_cmp, "compare", &result_p, a, b);
! 106:
! 107: if (EG(exception)) {
! 108: return FAILURE;
! 109: }
! 110:
! 111: convert_to_long(result_p);
! 112: *result = Z_LVAL_P(result_p);
! 113:
! 114: zval_ptr_dtor(&result_p);
! 115:
! 116: return SUCCESS;
! 117: }
! 118: /* }}} */
! 119:
! 120: static zval **spl_pqueue_extract_helper(zval **value, int flags) /* {{{ */
! 121: {
! 122: if ((flags & SPL_PQUEUE_EXTR_BOTH) == SPL_PQUEUE_EXTR_BOTH) {
! 123: return value;
! 124: } else if ((flags & SPL_PQUEUE_EXTR_BOTH) > 0) {
! 125:
! 126: if ((flags & SPL_PQUEUE_EXTR_DATA) == SPL_PQUEUE_EXTR_DATA) {
! 127: zval **data;
! 128: if (zend_hash_find(Z_ARRVAL_PP(value), "data", sizeof("data"), (void **) &data) == SUCCESS) {
! 129: return data;
! 130: }
! 131: } else {
! 132: zval **priority;
! 133: if (zend_hash_find(Z_ARRVAL_PP(value), "priority", sizeof("priority"), (void **) &priority) == SUCCESS) {
! 134: return priority;
! 135: }
! 136: }
! 137: }
! 138:
! 139: return NULL;
! 140: }
! 141: /* }}} */
! 142:
! 143: static int spl_ptr_heap_zval_max_cmp(spl_ptr_heap_element a, spl_ptr_heap_element b, void* object TSRMLS_DC) { /* {{{ */
! 144: zval result;
! 145:
! 146: if (EG(exception)) {
! 147: return 0;
! 148: }
! 149:
! 150: if (object) {
! 151: spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object((zval *)object TSRMLS_CC);
! 152: if (heap_object->fptr_cmp) {
! 153: long lval = 0;
! 154: if (spl_ptr_heap_cmp_cb_helper((zval *)object, heap_object, (zval *)a, (zval *)b, &lval TSRMLS_CC) == FAILURE) {
! 155: /* exception or call failure */
! 156: return 0;
! 157: }
! 158: return lval;
! 159: }
! 160: }
! 161:
! 162: INIT_ZVAL(result);
! 163: compare_function(&result, (zval *)a, (zval *)b TSRMLS_CC);
! 164: return Z_LVAL(result);
! 165: }
! 166: /* }}} */
! 167:
! 168: static int spl_ptr_heap_zval_min_cmp(spl_ptr_heap_element a, spl_ptr_heap_element b, void* object TSRMLS_DC) { /* {{{ */
! 169: zval result;
! 170:
! 171: if (EG(exception)) {
! 172: return 0;
! 173: }
! 174:
! 175: if (object) {
! 176: spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object((zval *)object TSRMLS_CC);
! 177: if (heap_object->fptr_cmp) {
! 178: long lval = 0;
! 179: if (spl_ptr_heap_cmp_cb_helper((zval *)object, heap_object, (zval *)a, (zval *)b, &lval TSRMLS_CC) == FAILURE) {
! 180: /* exception or call failure */
! 181: return 0;
! 182: }
! 183: return lval;
! 184: }
! 185: }
! 186:
! 187: INIT_ZVAL(result);
! 188: compare_function(&result, (zval *)b, (zval *)a TSRMLS_CC);
! 189: return Z_LVAL(result);
! 190: }
! 191: /* }}} */
! 192:
! 193: static int spl_ptr_pqueue_zval_cmp(spl_ptr_heap_element a, spl_ptr_heap_element b, void* object TSRMLS_DC) { /* {{{ */
! 194: zval result;
! 195: zval **a_priority_pp = spl_pqueue_extract_helper((zval **)&a, SPL_PQUEUE_EXTR_PRIORITY);
! 196: zval **b_priority_pp = spl_pqueue_extract_helper((zval **)&b, SPL_PQUEUE_EXTR_PRIORITY);
! 197:
! 198: if ((!a_priority_pp) || (!b_priority_pp)) {
! 199: zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
! 200: return 0;
! 201: }
! 202: if (EG(exception)) {
! 203: return 0;
! 204: }
! 205:
! 206: if (object) {
! 207: spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
! 208: if (heap_object->fptr_cmp) {
! 209: long lval = 0;
! 210: if (spl_ptr_heap_cmp_cb_helper((zval *)object, heap_object, *a_priority_pp, *b_priority_pp, &lval TSRMLS_CC) == FAILURE) {
! 211: /* exception or call failure */
! 212: return 0;
! 213: }
! 214: return lval;
! 215: }
! 216: }
! 217:
! 218: INIT_ZVAL(result);
! 219: compare_function(&result, *a_priority_pp, *b_priority_pp TSRMLS_CC);
! 220: return Z_LVAL(result);
! 221: }
! 222: /* }}} */
! 223:
! 224: 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) /* {{{ */
! 225: {
! 226: spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
! 227:
! 228: heap->dtor = dtor;
! 229: heap->ctor = ctor;
! 230: heap->cmp = cmp;
! 231: heap->elements = safe_emalloc(sizeof(spl_ptr_heap_element), PTR_HEAP_BLOCK_SIZE, 0);
! 232: heap->max_size = PTR_HEAP_BLOCK_SIZE;
! 233: heap->count = 0;
! 234: heap->flags = 0;
! 235:
! 236: return heap;
! 237: }
! 238: /* }}} */
! 239:
! 240: static void spl_ptr_heap_insert(spl_ptr_heap *heap, spl_ptr_heap_element elem, void *cmp_userdata TSRMLS_DC) { /* {{{ */
! 241: int i;
! 242:
! 243: if (heap->count+1 > heap->max_size) {
! 244: /* we need to allocate more memory */
! 245: heap->elements = (void **) safe_erealloc(heap->elements, sizeof(spl_ptr_heap_element), (heap->max_size), (sizeof(spl_ptr_heap_element) * (heap->max_size)));
! 246: heap->max_size *= 2;
! 247: }
! 248:
! 249: heap->ctor(elem TSRMLS_CC);
! 250:
! 251: /* sifting up */
! 252: for(i = heap->count++; i > 0 && heap->cmp(heap->elements[(i-1)/2], elem, cmp_userdata TSRMLS_CC) < 0; i = (i-1)/2) {
! 253: heap->elements[i] = heap->elements[(i-1)/2];
! 254: }
! 255:
! 256: if (EG(exception)) {
! 257: /* exception thrown during comparison */
! 258: heap->flags |= SPL_HEAP_CORRUPTED;
! 259: }
! 260:
! 261: heap->elements[i] = elem;
! 262:
! 263: }
! 264: /* }}} */
! 265:
! 266: static spl_ptr_heap_element spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */
! 267: if (heap->count == 0) {
! 268: return NULL;
! 269: }
! 270:
! 271: return heap->elements[0];
! 272: }
! 273: /* }}} */
! 274:
! 275: static spl_ptr_heap_element spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *cmp_userdata TSRMLS_DC) { /* {{{ */
! 276: int i, j;
! 277: const int limit = (heap->count-1)/2;
! 278: spl_ptr_heap_element top;
! 279: spl_ptr_heap_element bottom;
! 280:
! 281: if (heap->count == 0) {
! 282: return NULL;
! 283: }
! 284:
! 285: top = heap->elements[0];
! 286: bottom = heap->elements[--heap->count];
! 287:
! 288: for( i = 0; i < limit; i = j)
! 289: {
! 290: /* Find smaller child */
! 291: j = i*2+1;
! 292: if(j != heap->count && heap->cmp(heap->elements[j+1], heap->elements[j], cmp_userdata TSRMLS_CC) > 0) {
! 293: j++; /* next child is bigger */
! 294: }
! 295:
! 296: /* swap elements between two levels */
! 297: if(heap->cmp(bottom, heap->elements[j], cmp_userdata TSRMLS_CC) < 0) {
! 298: heap->elements[i] = heap->elements[j];
! 299: } else {
! 300: break;
! 301: }
! 302: }
! 303:
! 304: if (EG(exception)) {
! 305: /* exception thrown during comparison */
! 306: heap->flags |= SPL_HEAP_CORRUPTED;
! 307: }
! 308:
! 309: heap->elements[i] = bottom;
! 310: heap->dtor(top TSRMLS_CC);
! 311: return top;
! 312: }
! 313: /* }}} */
! 314:
! 315: static spl_ptr_heap *spl_ptr_heap_clone(spl_ptr_heap *from TSRMLS_DC) { /* {{{ */
! 316: int i;
! 317:
! 318: spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
! 319:
! 320: heap->dtor = from->dtor;
! 321: heap->ctor = from->ctor;
! 322: heap->cmp = from->cmp;
! 323: heap->max_size = from->max_size;
! 324: heap->count = from->count;
! 325: heap->flags = from->flags;
! 326:
! 327: heap->elements = safe_emalloc(sizeof(spl_ptr_heap_element),from->max_size,0);
! 328: memcpy(heap->elements, from->elements, sizeof(spl_ptr_heap_element)*from->max_size);
! 329:
! 330: for (i=0; i < heap->count; ++i) {
! 331: heap->ctor(heap->elements[i] TSRMLS_CC);
! 332: }
! 333:
! 334: return heap;
! 335: }
! 336: /* }}} */
! 337:
! 338: static void spl_ptr_heap_destroy(spl_ptr_heap *heap TSRMLS_DC) { /* {{{ */
! 339: int i;
! 340:
! 341: for (i=0; i < heap->count; ++i) {
! 342: heap->dtor(heap->elements[i] TSRMLS_CC);
! 343: }
! 344:
! 345: efree(heap->elements);
! 346: efree(heap);
! 347: }
! 348: /* }}} */
! 349:
! 350: static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */
! 351: return heap->count;
! 352: }
! 353: /* }}} */
! 354: /* }}} */
! 355:
! 356: zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC);
! 357:
! 358: static void spl_heap_object_free_storage(void *object TSRMLS_DC) /* {{{ */
! 359: {
! 360: int i;
! 361: spl_heap_object *intern = (spl_heap_object *)object;
! 362:
! 363: zend_object_std_dtor(&intern->std TSRMLS_CC);
! 364:
! 365: for (i = 0; i < intern->heap->count; ++i) {
! 366: if (intern->heap->elements[i]) {
! 367: zval_ptr_dtor((zval **)&intern->heap->elements[i]);
! 368: }
! 369: }
! 370:
! 371: spl_ptr_heap_destroy(intern->heap TSRMLS_CC);
! 372:
! 373: zval_ptr_dtor(&intern->retval);
! 374:
! 375: if (intern->debug_info != NULL) {
! 376: zend_hash_destroy(intern->debug_info);
! 377: efree(intern->debug_info);
! 378: }
! 379:
! 380: efree(object);
! 381: }
! 382: /* }}} */
! 383:
! 384: 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) /* {{{ */
! 385: {
! 386: zend_object_value retval;
! 387: spl_heap_object *intern;
! 388: zval *tmp;
! 389: zend_class_entry *parent = class_type;
! 390: int inherited = 0;
! 391:
! 392: intern = ecalloc(1, sizeof(spl_heap_object));
! 393: *obj = intern;
! 394: ALLOC_INIT_ZVAL(intern->retval);
! 395:
! 396: zend_object_std_init(&intern->std, class_type TSRMLS_CC);
! 397: zend_hash_copy(intern->std.properties, &class_type->default_properties, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
! 398:
! 399: intern->flags = 0;
! 400: intern->fptr_cmp = NULL;
! 401: intern->debug_info = NULL;
! 402:
! 403: if (orig) {
! 404: spl_heap_object *other = (spl_heap_object*)zend_object_store_get_object(orig TSRMLS_CC);
! 405: intern->ce_get_iterator = other->ce_get_iterator;
! 406:
! 407: if (clone_orig) {
! 408: int i;
! 409: intern->heap = spl_ptr_heap_clone(other->heap TSRMLS_CC);
! 410: for (i = 0; i < intern->heap->count; ++i) {
! 411: if (intern->heap->elements[i]) {
! 412: Z_ADDREF_P((zval *)intern->heap->elements[i]);
! 413: }
! 414: }
! 415: } else {
! 416: intern->heap = other->heap;
! 417: }
! 418:
! 419: intern->flags = other->flags;
! 420: } else {
! 421: intern->heap = spl_ptr_heap_init(spl_ptr_heap_zval_max_cmp, spl_ptr_heap_zval_ctor, spl_ptr_heap_zval_dtor);
! 422: }
! 423:
! 424: retval.handlers = &spl_handler_SplHeap;
! 425:
! 426: while (parent) {
! 427: if (parent == spl_ce_SplPriorityQueue) {
! 428: intern->heap->cmp = spl_ptr_pqueue_zval_cmp;
! 429: intern->flags = SPL_PQUEUE_EXTR_DATA;
! 430: retval.handlers = &spl_handler_SplPriorityQueue;
! 431: break;
! 432: }
! 433:
! 434: if (parent == spl_ce_SplMinHeap) {
! 435: intern->heap->cmp = spl_ptr_heap_zval_min_cmp;
! 436: break;
! 437: }
! 438:
! 439: if (parent == spl_ce_SplMaxHeap) {
! 440: intern->heap->cmp = spl_ptr_heap_zval_max_cmp;
! 441: break;
! 442: }
! 443:
! 444: if (parent == spl_ce_SplHeap) {
! 445: break;
! 446: }
! 447:
! 448: parent = parent->parent;
! 449: inherited = 1;
! 450: }
! 451:
! 452: retval.handle = zend_objects_store_put(intern, (zend_objects_store_dtor_t)zend_objects_destroy_object, spl_heap_object_free_storage, NULL TSRMLS_CC);
! 453:
! 454: if (!parent) { /* this must never happen */
! 455: php_error_docref(NULL TSRMLS_CC, E_COMPILE_ERROR, "Internal compiler error, Class is not child of SplHeap");
! 456: }
! 457:
! 458: if (inherited) {
! 459: zend_hash_find(&class_type->function_table, "compare", sizeof("compare"), (void **) &intern->fptr_cmp);
! 460: if (intern->fptr_cmp->common.scope == parent) {
! 461: intern->fptr_cmp = NULL;
! 462: }
! 463: zend_hash_find(&class_type->function_table, "count", sizeof("count"), (void **) &intern->fptr_count);
! 464: if (intern->fptr_count->common.scope == parent) {
! 465: intern->fptr_count = NULL;
! 466: }
! 467: }
! 468:
! 469: return retval;
! 470: }
! 471: /* }}} */
! 472:
! 473: static zend_object_value spl_heap_object_new(zend_class_entry *class_type TSRMLS_DC) /* {{{ */
! 474: {
! 475: spl_heap_object *tmp;
! 476: return spl_heap_object_new_ex(class_type, &tmp, NULL, 0 TSRMLS_CC);
! 477: }
! 478: /* }}} */
! 479:
! 480: static zend_object_value spl_heap_object_clone(zval *zobject TSRMLS_DC) /* {{{ */
! 481: {
! 482: zend_object_value new_obj_val;
! 483: zend_object *old_object;
! 484: zend_object *new_object;
! 485: zend_object_handle handle = Z_OBJ_HANDLE_P(zobject);
! 486: spl_heap_object *intern;
! 487:
! 488: old_object = zend_objects_get_address(zobject TSRMLS_CC);
! 489: new_obj_val = spl_heap_object_new_ex(old_object->ce, &intern, zobject, 1 TSRMLS_CC);
! 490: new_object = &intern->std;
! 491:
! 492: zend_objects_clone_members(new_object, new_obj_val, old_object, handle TSRMLS_CC);
! 493:
! 494: return new_obj_val;
! 495: }
! 496: /* }}} */
! 497:
! 498: static int spl_heap_object_count_elements(zval *object, long *count TSRMLS_DC) /* {{{ */
! 499: {
! 500: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
! 501:
! 502: if (intern->fptr_count) {
! 503: zval *rv;
! 504: zend_call_method_with_0_params(&object, intern->std.ce, &intern->fptr_count, "count", &rv);
! 505: if (rv) {
! 506: zval_ptr_dtor(&intern->retval);
! 507: MAKE_STD_ZVAL(intern->retval);
! 508: ZVAL_ZVAL(intern->retval, rv, 1, 1);
! 509: convert_to_long(intern->retval);
! 510: *count = (long) Z_LVAL_P(intern->retval);
! 511: return SUCCESS;
! 512: }
! 513: *count = 0;
! 514: return FAILURE;
! 515: }
! 516:
! 517: *count = spl_ptr_heap_count(intern->heap);
! 518:
! 519: return SUCCESS;
! 520: }
! 521: /* }}} */
! 522:
! 523: static HashTable* spl_heap_object_get_debug_info_helper(zend_class_entry *ce, zval *obj, int *is_temp TSRMLS_DC) { /* {{{ */
! 524: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(obj TSRMLS_CC);
! 525: zval *tmp, zrv, *heap_array;
! 526: char *pnstr;
! 527: int pnlen;
! 528: int i;
! 529:
! 530: *is_temp = 0;
! 531:
! 532: if (intern->debug_info == NULL) {
! 533: ALLOC_HASHTABLE(intern->debug_info);
! 534: ZEND_INIT_SYMTABLE_EX(intern->debug_info, zend_hash_num_elements(intern->std.properties) + 1, 0);
! 535: }
! 536:
! 537: if (intern->debug_info->nApplyCount == 0) {
! 538: INIT_PZVAL(&zrv);
! 539: Z_ARRVAL(zrv) = intern->debug_info;
! 540:
! 541: zend_hash_copy(intern->debug_info, intern->std.properties, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
! 542:
! 543: pnstr = spl_gen_private_prop_name(ce, "flags", sizeof("flags")-1, &pnlen TSRMLS_CC);
! 544: add_assoc_long_ex(&zrv, pnstr, pnlen+1, intern->flags);
! 545: efree(pnstr);
! 546:
! 547: pnstr = spl_gen_private_prop_name(ce, "isCorrupted", sizeof("isCorrupted")-1, &pnlen TSRMLS_CC);
! 548: add_assoc_bool_ex(&zrv, pnstr, pnlen+1, intern->heap->flags&SPL_HEAP_CORRUPTED);
! 549: efree(pnstr);
! 550:
! 551: ALLOC_INIT_ZVAL(heap_array);
! 552: array_init(heap_array);
! 553:
! 554: for (i = 0; i < intern->heap->count; ++i) {
! 555: add_index_zval(heap_array, i, (zval *)intern->heap->elements[i]);
! 556: Z_ADDREF_P(intern->heap->elements[i]);
! 557: }
! 558:
! 559: pnstr = spl_gen_private_prop_name(ce, "heap", sizeof("heap")-1, &pnlen TSRMLS_CC);
! 560: add_assoc_zval_ex(&zrv, pnstr, pnlen+1, heap_array);
! 561: efree(pnstr);
! 562: }
! 563:
! 564: return intern->debug_info;
! 565: }
! 566: /* }}} */
! 567:
! 568: static HashTable* spl_heap_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{ */
! 569: {
! 570: return spl_heap_object_get_debug_info_helper(spl_ce_SplHeap, obj, is_temp TSRMLS_CC);
! 571: }
! 572: /* }}} */
! 573:
! 574: static HashTable* spl_pqueue_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{ */
! 575: {
! 576: return spl_heap_object_get_debug_info_helper(spl_ce_SplPriorityQueue, obj, is_temp TSRMLS_CC);
! 577: }
! 578: /* }}} */
! 579:
! 580: /* {{{ proto int SplHeap::count() U
! 581: Return the number of elements in the heap. */
! 582: SPL_METHOD(SplHeap, count)
! 583: {
! 584: long count;
! 585: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 586:
! 587: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 588: return;
! 589: }
! 590:
! 591: count = spl_ptr_heap_count(intern->heap);
! 592: RETURN_LONG(count);
! 593: }
! 594: /* }}} */
! 595:
! 596: /* {{{ proto int SplHeap::isEmpty() U
! 597: Return true if the heap is empty. */
! 598: SPL_METHOD(SplHeap, isEmpty)
! 599: {
! 600: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 601:
! 602: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 603: return;
! 604: }
! 605:
! 606: RETURN_BOOL(spl_ptr_heap_count(intern->heap)==0);
! 607: }
! 608: /* }}} */
! 609:
! 610: /* {{{ proto bool SplHeap::insert(mixed $value) U
! 611: Push $value on the heap */
! 612: SPL_METHOD(SplHeap, insert)
! 613: {
! 614: zval *value;
! 615: spl_heap_object *intern;
! 616:
! 617: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) == FAILURE) {
! 618: return;
! 619: }
! 620:
! 621: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 622:
! 623: if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
! 624: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 625: return;
! 626: }
! 627:
! 628: SEPARATE_ARG_IF_REF(value);
! 629:
! 630: spl_ptr_heap_insert(intern->heap, value, getThis() TSRMLS_CC);
! 631:
! 632: RETURN_TRUE;
! 633: }
! 634: /* }}} */
! 635:
! 636: /* {{{ proto mixed SplHeap::extract() U
! 637: extract the element out of the top of the heap */
! 638: SPL_METHOD(SplHeap, extract)
! 639: {
! 640: zval *value;
! 641: spl_heap_object *intern;
! 642:
! 643: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 644: return;
! 645: }
! 646:
! 647: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 648:
! 649: if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
! 650: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 651: return;
! 652: }
! 653:
! 654: value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
! 655:
! 656: if (!value) {
! 657: zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
! 658: return;
! 659: }
! 660:
! 661: RETURN_ZVAL(value, 1, 1);
! 662: }
! 663: /* }}} */
! 664:
! 665: /* {{{ proto bool SplPriorityQueue::insert(mixed $value, mixed $priority) U
! 666: Push $value with the priority $priodiry on the priorityqueue */
! 667: SPL_METHOD(SplPriorityQueue, insert)
! 668: {
! 669: zval *data, *priority, *elem;
! 670: spl_heap_object *intern;
! 671:
! 672: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &data, &priority) == FAILURE) {
! 673: return;
! 674: }
! 675:
! 676: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 677:
! 678: if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
! 679: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 680: return;
! 681: }
! 682:
! 683: SEPARATE_ARG_IF_REF(data);
! 684: SEPARATE_ARG_IF_REF(priority);
! 685:
! 686: ALLOC_INIT_ZVAL(elem);
! 687:
! 688: array_init(elem);
! 689: add_assoc_zval_ex(elem, "data", sizeof("data"), data);
! 690: add_assoc_zval_ex(elem, "priority", sizeof("priority"), priority);
! 691:
! 692: spl_ptr_heap_insert(intern->heap, elem, getThis() TSRMLS_CC);
! 693:
! 694: RETURN_TRUE;
! 695: }
! 696: /* }}} */
! 697:
! 698: /* {{{ proto mixed SplPriorityQueue::extract() U
! 699: extract the element out of the top of the priority queue */
! 700: SPL_METHOD(SplPriorityQueue, extract)
! 701: {
! 702: zval *value, *value_out, **value_out_pp;
! 703: spl_heap_object *intern;
! 704:
! 705: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 706: return;
! 707: }
! 708:
! 709: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 710:
! 711: if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
! 712: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 713: return;
! 714: }
! 715:
! 716: value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
! 717:
! 718: if (!value) {
! 719: zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
! 720: return;
! 721: }
! 722:
! 723: value_out_pp = spl_pqueue_extract_helper(&value, intern->flags);
! 724:
! 725:
! 726: if (!value_out_pp) {
! 727: zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
! 728: zval_ptr_dtor(&value);
! 729: return;
! 730: }
! 731:
! 732: value_out = *value_out_pp;
! 733:
! 734: Z_ADDREF_P(value_out);
! 735: zval_ptr_dtor(&value);
! 736:
! 737: RETURN_ZVAL(value_out, 1, 1);
! 738: }
! 739: /* }}} */
! 740:
! 741: /* {{{ proto mixed SplPriorityQueue::top() U
! 742: Peek at the top element of the priority queue */
! 743: SPL_METHOD(SplPriorityQueue, top)
! 744: {
! 745: zval *value, **value_out;
! 746: spl_heap_object *intern;
! 747:
! 748: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 749: return;
! 750: }
! 751:
! 752: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 753:
! 754: if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
! 755: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 756: return;
! 757: }
! 758:
! 759: value = (zval *)spl_ptr_heap_top(intern->heap);
! 760:
! 761: if (!value) {
! 762: zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
! 763: return;
! 764: }
! 765:
! 766: value_out = spl_pqueue_extract_helper(&value, intern->flags);
! 767:
! 768: if (!value_out) {
! 769: zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
! 770: return;
! 771: }
! 772:
! 773: RETURN_ZVAL(*value_out, 1, 0);
! 774: }
! 775: /* }}} */
! 776:
! 777: /* {{{ proto int SplPriorityQueue::setIteratorMode($flags) U
! 778: Set the flags of extraction*/
! 779: SPL_METHOD(SplPriorityQueue, setExtractFlags)
! 780: {
! 781: long value;
! 782: spl_heap_object *intern;
! 783:
! 784: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &value) == FAILURE) {
! 785: return;
! 786: }
! 787:
! 788: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 789:
! 790: intern->flags = value & SPL_PQUEUE_EXTR_MASK;
! 791:
! 792: RETURN_LONG(intern->flags);
! 793: }
! 794: /* }}} */
! 795:
! 796: /* {{{ proto int SplHeap::recoverFromCorruption() U
! 797: Recover from a corrupted state*/
! 798: SPL_METHOD(SplHeap, recoverFromCorruption)
! 799: {
! 800: spl_heap_object *intern;
! 801:
! 802: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 803: return;
! 804: }
! 805:
! 806: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 807:
! 808: intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED;
! 809:
! 810: RETURN_TRUE;
! 811: }
! 812: /* }}} */
! 813:
! 814: /* {{{ proto bool SplPriorityQueue::compare(mixed $a, mixed $b) U
! 815: compare the priorities */
! 816: SPL_METHOD(SplPriorityQueue, compare)
! 817: {
! 818: zval *a, *b;
! 819:
! 820: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
! 821: return;
! 822: }
! 823:
! 824: RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
! 825: }
! 826: /* }}} */
! 827:
! 828: /* {{{ proto mixed SplHeap::top() U
! 829: Peek at the top element of the heap */
! 830: SPL_METHOD(SplHeap, top)
! 831: {
! 832: zval *value;
! 833: spl_heap_object *intern;
! 834:
! 835: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
! 836: return;
! 837: }
! 838:
! 839: intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 840:
! 841: if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
! 842: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 843: return;
! 844: }
! 845:
! 846: value = (zval *)spl_ptr_heap_top(intern->heap);
! 847:
! 848: if (!value) {
! 849: zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
! 850: return;
! 851: }
! 852:
! 853: RETURN_ZVAL(value, 1, 0);
! 854: }
! 855: /* }}} */
! 856:
! 857: /* {{{ proto bool SplMinHeap::compare(mixed $a, mixed $b) U
! 858: compare the values */
! 859: SPL_METHOD(SplMinHeap, compare)
! 860: {
! 861: zval *a, *b;
! 862:
! 863: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
! 864: return;
! 865: }
! 866:
! 867: RETURN_LONG(spl_ptr_heap_zval_min_cmp(a, b, NULL TSRMLS_CC));
! 868: }
! 869: /* }}} */
! 870:
! 871: /* {{{ proto bool SplMaxHeap::compare(mixed $a, mixed $b) U
! 872: compare the values */
! 873: SPL_METHOD(SplMaxHeap, compare)
! 874: {
! 875: zval *a, *b;
! 876:
! 877: if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
! 878: return;
! 879: }
! 880:
! 881: RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
! 882: }
! 883: /* }}} */
! 884:
! 885: static void spl_heap_it_dtor(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
! 886: {
! 887: spl_heap_it *iterator = (spl_heap_it *)iter;
! 888:
! 889: zend_user_it_invalidate_current(iter TSRMLS_CC);
! 890: zval_ptr_dtor((zval**)&iterator->intern.it.data);
! 891:
! 892: efree(iterator);
! 893: }
! 894: /* }}} */
! 895:
! 896: static void spl_heap_it_rewind(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
! 897: {
! 898: /* do nothing, the iterator always points to the top element */
! 899: }
! 900: /* }}} */
! 901:
! 902: static int spl_heap_it_valid(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
! 903: {
! 904: spl_heap_it *iterator = (spl_heap_it *)iter;
! 905:
! 906: return (iterator->object->heap->count != 0 ? SUCCESS : FAILURE);
! 907: }
! 908: /* }}} */
! 909:
! 910: static void spl_heap_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
! 911: {
! 912: spl_heap_it *iterator = (spl_heap_it *)iter;
! 913: zval **element = (zval **)&iterator->object->heap->elements[0];
! 914:
! 915: if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
! 916: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 917: return;
! 918: }
! 919:
! 920: if (iterator->object->heap->count == 0 || !*element) {
! 921: *data = NULL;
! 922: } else {
! 923: *data = element;
! 924: }
! 925: }
! 926: /* }}} */
! 927:
! 928: static void spl_pqueue_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
! 929: {
! 930: spl_heap_it *iterator = (spl_heap_it *)iter;
! 931: zval **element = (zval **)&iterator->object->heap->elements[0];
! 932:
! 933: if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
! 934: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 935: return;
! 936: }
! 937:
! 938: if (iterator->object->heap->count == 0 || !*element) {
! 939: *data = NULL;
! 940: } else {
! 941: *data = spl_pqueue_extract_helper(element, iterator->object->flags);
! 942: if (!*data) {
! 943: zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
! 944: }
! 945: }
! 946: }
! 947: /* }}} */
! 948:
! 949: static int spl_heap_it_get_current_key(zend_object_iterator *iter, char **str_key, uint *str_key_len, ulong *int_key TSRMLS_DC) /* {{{ */
! 950: {
! 951: spl_heap_it *iterator = (spl_heap_it *)iter;
! 952:
! 953: *int_key = (ulong) iterator->object->heap->count;
! 954: return HASH_KEY_IS_LONG;
! 955: }
! 956: /* }}} */
! 957:
! 958: static void spl_heap_it_move_forward(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
! 959: {
! 960: zval *object = (zval*)((zend_user_iterator *)iter)->it.data;
! 961: spl_heap_it *iterator = (spl_heap_it *)iter;
! 962: spl_ptr_heap_element elem;
! 963:
! 964: if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
! 965: zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
! 966: return;
! 967: }
! 968:
! 969: elem = spl_ptr_heap_delete_top(iterator->object->heap, object TSRMLS_CC);
! 970:
! 971: if (elem != NULL) {
! 972: zval_ptr_dtor((zval **)&elem);
! 973: }
! 974:
! 975: zend_user_it_invalidate_current(iter TSRMLS_CC);
! 976: }
! 977: /* }}} */
! 978:
! 979: /* {{{ proto int SplHeap::key() U
! 980: Return current array key */
! 981: SPL_METHOD(SplHeap, key)
! 982: {
! 983: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 984:
! 985: if (zend_parse_parameters_none() == FAILURE) {
! 986: return;
! 987: }
! 988:
! 989: RETURN_LONG(intern->heap->count - 1);
! 990: }
! 991: /* }}} */
! 992:
! 993: /* {{{ proto void SplHeap::next() U
! 994: Move to next entry */
! 995: SPL_METHOD(SplHeap, next)
! 996: {
! 997: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 998: spl_ptr_heap_element elem = spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
! 999:
! 1000: if (zend_parse_parameters_none() == FAILURE) {
! 1001: return;
! 1002: }
! 1003:
! 1004: if (elem != NULL) {
! 1005: zval_ptr_dtor((zval **)&elem);
! 1006: }
! 1007: }
! 1008: /* }}} */
! 1009:
! 1010: /* {{{ proto bool SplHeap::valid() U
! 1011: Check whether the datastructure contains more entries */
! 1012: SPL_METHOD(SplHeap, valid)
! 1013: {
! 1014: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 1015:
! 1016: if (zend_parse_parameters_none() == FAILURE) {
! 1017: return;
! 1018: }
! 1019:
! 1020: RETURN_BOOL(intern->heap->count != 0);
! 1021: }
! 1022: /* }}} */
! 1023:
! 1024: /* {{{ proto void SplHeap::rewind() U
! 1025: Rewind the datastructure back to the start */
! 1026: SPL_METHOD(SplHeap, rewind)
! 1027: {
! 1028: if (zend_parse_parameters_none() == FAILURE) {
! 1029: return;
! 1030: }
! 1031: /* do nothing, the iterator always points to the top element */
! 1032: }
! 1033: /* }}} */
! 1034:
! 1035: /* {{{ proto mixed|NULL SplHeap::current() U
! 1036: Return current datastructure entry */
! 1037: SPL_METHOD(SplHeap, current)
! 1038: {
! 1039: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 1040: zval *element = (zval *)intern->heap->elements[0];
! 1041:
! 1042: if (zend_parse_parameters_none() == FAILURE) {
! 1043: return;
! 1044: }
! 1045:
! 1046: if (!intern->heap->count || !element) {
! 1047: RETURN_NULL();
! 1048: } else {
! 1049: RETURN_ZVAL(element, 1, 0);
! 1050: }
! 1051: }
! 1052: /* }}} */
! 1053:
! 1054: /* {{{ proto mixed|NULL SplPriorityQueue::current() U
! 1055: Return current datastructure entry */
! 1056: SPL_METHOD(SplPriorityQueue, current)
! 1057: {
! 1058: spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
! 1059: zval **element = (zval **)&intern->heap->elements[0];
! 1060:
! 1061: if (zend_parse_parameters_none() == FAILURE) {
! 1062: return;
! 1063: }
! 1064:
! 1065: if (!intern->heap->count || !*element) {
! 1066: RETURN_NULL();
! 1067: } else {
! 1068: zval **data = spl_pqueue_extract_helper(element, intern->flags);
! 1069:
! 1070: if (!data) {
! 1071: zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
! 1072: RETURN_NULL();
! 1073: }
! 1074:
! 1075: RETURN_ZVAL(*data, 1, 0);
! 1076: }
! 1077: }
! 1078: /* }}} */
! 1079:
! 1080: /* iterator handler table */
! 1081: zend_object_iterator_funcs spl_heap_it_funcs = {
! 1082: spl_heap_it_dtor,
! 1083: spl_heap_it_valid,
! 1084: spl_heap_it_get_current_data,
! 1085: spl_heap_it_get_current_key,
! 1086: spl_heap_it_move_forward,
! 1087: spl_heap_it_rewind
! 1088: };
! 1089:
! 1090: zend_object_iterator_funcs spl_pqueue_it_funcs = {
! 1091: spl_heap_it_dtor,
! 1092: spl_heap_it_valid,
! 1093: spl_pqueue_it_get_current_data,
! 1094: spl_heap_it_get_current_key,
! 1095: spl_heap_it_move_forward,
! 1096: spl_heap_it_rewind
! 1097: };
! 1098:
! 1099: zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
! 1100: {
! 1101: spl_heap_it *iterator;
! 1102: spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
! 1103:
! 1104: if (by_ref) {
! 1105: zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
! 1106: return NULL;
! 1107: }
! 1108:
! 1109: Z_ADDREF_P(object);
! 1110:
! 1111: iterator = emalloc(sizeof(spl_heap_it));
! 1112: iterator->intern.it.data = (void*)object;
! 1113: iterator->intern.it.funcs = &spl_heap_it_funcs;
! 1114: iterator->intern.ce = ce;
! 1115: iterator->intern.value = NULL;
! 1116: iterator->flags = heap_object->flags;
! 1117: iterator->object = heap_object;
! 1118:
! 1119: return (zend_object_iterator*)iterator;
! 1120: }
! 1121: /* }}} */
! 1122:
! 1123: zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
! 1124: {
! 1125: spl_heap_it *iterator;
! 1126: spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
! 1127:
! 1128: if (by_ref) {
! 1129: zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
! 1130: return NULL;
! 1131: }
! 1132:
! 1133: Z_ADDREF_P(object);
! 1134:
! 1135: iterator = emalloc(sizeof(spl_heap_it));
! 1136: iterator->intern.it.data = (void*)object;
! 1137: iterator->intern.it.funcs = &spl_pqueue_it_funcs;
! 1138: iterator->intern.ce = ce;
! 1139: iterator->intern.value = NULL;
! 1140: iterator->flags = heap_object->flags;
! 1141: iterator->object = heap_object;
! 1142:
! 1143: return (zend_object_iterator*)iterator;
! 1144: }
! 1145: /* }}} */
! 1146:
! 1147: ZEND_BEGIN_ARG_INFO(arginfo_heap_insert, 0)
! 1148: ZEND_ARG_INFO(0, value)
! 1149: ZEND_END_ARG_INFO()
! 1150:
! 1151: ZEND_BEGIN_ARG_INFO(arginfo_heap_compare, 0)
! 1152: ZEND_ARG_INFO(0, a)
! 1153: ZEND_ARG_INFO(0, b)
! 1154: ZEND_END_ARG_INFO()
! 1155:
! 1156: ZEND_BEGIN_ARG_INFO(arginfo_pqueue_insert, 0)
! 1157: ZEND_ARG_INFO(0, value)
! 1158: ZEND_ARG_INFO(0, priority)
! 1159: ZEND_END_ARG_INFO()
! 1160:
! 1161: ZEND_BEGIN_ARG_INFO(arginfo_pqueue_setflags, 0)
! 1162: ZEND_ARG_INFO(0, flags)
! 1163: ZEND_END_ARG_INFO()
! 1164:
! 1165: ZEND_BEGIN_ARG_INFO(arginfo_splheap_void, 0)
! 1166: ZEND_END_ARG_INFO()
! 1167:
! 1168: static const zend_function_entry spl_funcs_SplMinHeap[] = {
! 1169: SPL_ME(SplMinHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
! 1170: {NULL, NULL, NULL}
! 1171: };
! 1172: static const zend_function_entry spl_funcs_SplMaxHeap[] = {
! 1173: SPL_ME(SplMaxHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
! 1174: {NULL, NULL, NULL}
! 1175: };
! 1176:
! 1177: static const zend_function_entry spl_funcs_SplPriorityQueue[] = {
! 1178: SPL_ME(SplPriorityQueue, compare, arginfo_heap_compare, ZEND_ACC_PUBLIC)
! 1179: SPL_ME(SplPriorityQueue, insert, arginfo_pqueue_insert, ZEND_ACC_PUBLIC)
! 1180: SPL_ME(SplPriorityQueue, setExtractFlags, arginfo_pqueue_setflags, ZEND_ACC_PUBLIC)
! 1181: SPL_ME(SplPriorityQueue, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1182: SPL_ME(SplPriorityQueue, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1183: SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1184: SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1185: SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1186: SPL_ME(SplPriorityQueue, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1187: SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1188: SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1189: SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1190: SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1191: {NULL, NULL, NULL}
! 1192: };
! 1193:
! 1194: static const zend_function_entry spl_funcs_SplHeap[] = {
! 1195: SPL_ME(SplHeap, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1196: SPL_ME(SplHeap, insert, arginfo_heap_insert, ZEND_ACC_PUBLIC)
! 1197: SPL_ME(SplHeap, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1198: SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1199: SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1200: SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1201: SPL_ME(SplHeap, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1202: SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1203: SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1204: SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1205: SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
! 1206: ZEND_FENTRY(compare, NULL, NULL, ZEND_ACC_PROTECTED|ZEND_ACC_ABSTRACT)
! 1207: {NULL, NULL, NULL}
! 1208: };
! 1209: /* }}} */
! 1210:
! 1211: PHP_MINIT_FUNCTION(spl_heap) /* {{{ */
! 1212: {
! 1213: REGISTER_SPL_STD_CLASS_EX(SplHeap, spl_heap_object_new, spl_funcs_SplHeap);
! 1214: memcpy(&spl_handler_SplHeap, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
! 1215:
! 1216: spl_handler_SplHeap.clone_obj = spl_heap_object_clone;
! 1217: spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
! 1218: spl_handler_SplHeap.get_debug_info = spl_heap_object_get_debug_info;
! 1219:
! 1220: REGISTER_SPL_IMPLEMENTS(SplHeap, Iterator);
! 1221: REGISTER_SPL_IMPLEMENTS(SplHeap, Countable);
! 1222:
! 1223: spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
! 1224:
! 1225: REGISTER_SPL_SUB_CLASS_EX(SplMinHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMinHeap);
! 1226: REGISTER_SPL_SUB_CLASS_EX(SplMaxHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMaxHeap);
! 1227:
! 1228: spl_ce_SplMaxHeap->get_iterator = spl_heap_get_iterator;
! 1229: spl_ce_SplMinHeap->get_iterator = spl_heap_get_iterator;
! 1230:
! 1231: REGISTER_SPL_STD_CLASS_EX(SplPriorityQueue, spl_heap_object_new, spl_funcs_SplPriorityQueue);
! 1232: memcpy(&spl_handler_SplPriorityQueue, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
! 1233:
! 1234: spl_handler_SplPriorityQueue.clone_obj = spl_heap_object_clone;
! 1235: spl_handler_SplPriorityQueue.count_elements = spl_heap_object_count_elements;
! 1236: spl_handler_SplPriorityQueue.get_debug_info = spl_pqueue_object_get_debug_info;
! 1237:
! 1238: REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Iterator);
! 1239: REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Countable);
! 1240:
! 1241: spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
! 1242:
! 1243: REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_BOTH", SPL_PQUEUE_EXTR_BOTH);
! 1244: REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_PRIORITY", SPL_PQUEUE_EXTR_PRIORITY);
! 1245: REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_DATA", SPL_PQUEUE_EXTR_DATA);
! 1246:
! 1247: return SUCCESS;
! 1248: }
! 1249: /* }}} */
! 1250:
! 1251: /*
! 1252: * Local variables:
! 1253: * tab-width: 4
! 1254: * c-basic-offset: 4
! 1255: * End:
! 1256: * vim600: fdm=marker
! 1257: * vim: noet sw=4 ts=4
! 1258: */
! 1259:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to spl_heap.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / spl