xref: /PHP-5.5/ext/spl/spl_heap.c (revision 1cbd25ca)
1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 5                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1997-2015 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$ */
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 */
spl_ptr_heap_zval_dtor(spl_ptr_heap_element elem TSRMLS_DC)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 
spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC)97 static void spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC) { /* {{{ */
98 	Z_ADDREF_P((zval *)elem);
99 }
100 /* }}} */
101 
spl_ptr_heap_cmp_cb_helper(zval * object,spl_heap_object * heap_object,zval * a,zval * b,long * result TSRMLS_DC)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 
spl_pqueue_extract_helper(zval ** value,int flags)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 
spl_ptr_heap_zval_max_cmp(spl_ptr_heap_element a,spl_ptr_heap_element b,void * object TSRMLS_DC)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 
spl_ptr_heap_zval_min_cmp(spl_ptr_heap_element a,spl_ptr_heap_element b,void * object TSRMLS_DC)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 
spl_ptr_pqueue_zval_cmp(spl_ptr_heap_element a,spl_ptr_heap_element b,void * object TSRMLS_DC)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 
spl_ptr_heap_init(spl_ptr_heap_cmp_func cmp,spl_ptr_heap_ctor_func ctor,spl_ptr_heap_dtor_func dtor)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 
spl_ptr_heap_insert(spl_ptr_heap * heap,spl_ptr_heap_element elem,void * cmp_userdata TSRMLS_DC)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 	heap->count++;
256 
257 	if (EG(exception)) {
258 		/* exception thrown during comparison */
259 		heap->flags |= SPL_HEAP_CORRUPTED;
260 	}
261 
262 	heap->elements[i] = elem;
263 
264 }
265 /* }}} */
266 
spl_ptr_heap_top(spl_ptr_heap * heap)267 static spl_ptr_heap_element spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */
268 	if (heap->count == 0) {
269 		return NULL;
270 	}
271 
272 	return heap->elements[0];
273 }
274 /* }}} */
275 
spl_ptr_heap_delete_top(spl_ptr_heap * heap,void * cmp_userdata TSRMLS_DC)276 static spl_ptr_heap_element spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *cmp_userdata TSRMLS_DC) { /* {{{ */
277 	int i, j;
278 	const int limit = (heap->count-1)/2;
279 	spl_ptr_heap_element top;
280 	spl_ptr_heap_element bottom;
281 
282 	if (heap->count == 0) {
283 		return NULL;
284 	}
285 
286 	top    = heap->elements[0];
287 	bottom = heap->elements[--heap->count];
288 
289 	for( i = 0; i < limit; i = j)
290 	{
291 		/* Find smaller child */
292 		j = i*2+1;
293 		if(j != heap->count && heap->cmp(heap->elements[j+1], heap->elements[j], cmp_userdata TSRMLS_CC) > 0) {
294 			j++; /* next child is bigger */
295 		}
296 
297 		/* swap elements between two levels */
298 		if(heap->cmp(bottom, heap->elements[j], cmp_userdata TSRMLS_CC) < 0) {
299 			heap->elements[i] = heap->elements[j];
300 		} else {
301 			break;
302 		}
303 	}
304 
305 	if (EG(exception)) {
306 		/* exception thrown during comparison */
307 		heap->flags |= SPL_HEAP_CORRUPTED;
308 	}
309 
310 	heap->elements[i] = bottom;
311 	heap->dtor(top TSRMLS_CC);
312 	return top;
313 }
314 /* }}} */
315 
spl_ptr_heap_clone(spl_ptr_heap * from TSRMLS_DC)316 static spl_ptr_heap *spl_ptr_heap_clone(spl_ptr_heap *from TSRMLS_DC) { /* {{{ */
317 	int i;
318 
319 	spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
320 
321 	heap->dtor     = from->dtor;
322 	heap->ctor     = from->ctor;
323 	heap->cmp      = from->cmp;
324 	heap->max_size = from->max_size;
325 	heap->count    = from->count;
326 	heap->flags    = from->flags;
327 
328 	heap->elements = safe_emalloc(sizeof(spl_ptr_heap_element),from->max_size,0);
329 	memcpy(heap->elements, from->elements, sizeof(spl_ptr_heap_element)*from->max_size);
330 
331 	for (i=0; i < heap->count; ++i) {
332 		heap->ctor(heap->elements[i] TSRMLS_CC);
333 	}
334 
335 	return heap;
336 }
337 /* }}} */
338 
spl_ptr_heap_destroy(spl_ptr_heap * heap TSRMLS_DC)339 static void spl_ptr_heap_destroy(spl_ptr_heap *heap TSRMLS_DC) { /* {{{ */
340 	int i;
341 
342 	for (i=0; i < heap->count; ++i) {
343 		heap->dtor(heap->elements[i] TSRMLS_CC);
344 	}
345 
346 	efree(heap->elements);
347 	efree(heap);
348 }
349 /* }}} */
350 
spl_ptr_heap_count(spl_ptr_heap * heap)351 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */
352 	return heap->count;
353 }
354 /* }}} */
355 /* }}} */
356 
357 zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC);
358 
spl_heap_object_free_storage(void * object TSRMLS_DC)359 static void spl_heap_object_free_storage(void *object TSRMLS_DC) /* {{{ */
360 {
361 	int i;
362 	spl_heap_object *intern = (spl_heap_object *)object;
363 
364 	zend_object_std_dtor(&intern->std TSRMLS_CC);
365 
366 	for (i = 0; i < intern->heap->count; ++i) {
367 		if (intern->heap->elements[i]) {
368 			zval_ptr_dtor((zval **)&intern->heap->elements[i]);
369 		}
370 	}
371 
372 	spl_ptr_heap_destroy(intern->heap TSRMLS_CC);
373 
374 	zval_ptr_dtor(&intern->retval);
375 
376 	if (intern->debug_info != NULL) {
377 		zend_hash_destroy(intern->debug_info);
378 		efree(intern->debug_info);
379 	}
380 
381 	efree(object);
382 }
383 /* }}} */
384 
spl_heap_object_new_ex(zend_class_entry * class_type,spl_heap_object ** obj,zval * orig,int clone_orig TSRMLS_DC)385 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) /* {{{ */
386 {
387 	zend_object_value  retval;
388 	spl_heap_object   *intern;
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 	object_properties_init(&intern->std, class_type);
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 
spl_heap_object_new(zend_class_entry * class_type TSRMLS_DC)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 
spl_heap_object_clone(zval * zobject TSRMLS_DC)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 
spl_heap_object_count_elements(zval * object,long * count TSRMLS_DC)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 
spl_heap_object_get_debug_info_helper(zend_class_entry * ce,zval * obj,int * is_temp TSRMLS_DC)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->std.properties) {
533 		rebuild_object_properties(&intern->std);
534 	}
535 
536 	if (intern->debug_info == NULL) {
537 		ALLOC_HASHTABLE(intern->debug_info);
538 		ZEND_INIT_SYMTABLE_EX(intern->debug_info, zend_hash_num_elements(intern->std.properties) + 1, 0);
539 	}
540 
541 	if (intern->debug_info->nApplyCount == 0) {
542 		INIT_PZVAL(&zrv);
543 		Z_ARRVAL(zrv) = intern->debug_info;
544 
545 		zend_hash_copy(intern->debug_info, intern->std.properties, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
546 
547 		pnstr = spl_gen_private_prop_name(ce, "flags", sizeof("flags")-1, &pnlen TSRMLS_CC);
548 		add_assoc_long_ex(&zrv, pnstr, pnlen+1, intern->flags);
549 		efree(pnstr);
550 
551 		pnstr = spl_gen_private_prop_name(ce, "isCorrupted", sizeof("isCorrupted")-1, &pnlen TSRMLS_CC);
552 		add_assoc_bool_ex(&zrv, pnstr, pnlen+1, intern->heap->flags&SPL_HEAP_CORRUPTED);
553 		efree(pnstr);
554 
555 		ALLOC_INIT_ZVAL(heap_array);
556 		array_init(heap_array);
557 
558 		for (i = 0; i < intern->heap->count; ++i) {
559 			add_index_zval(heap_array, i, (zval *)intern->heap->elements[i]);
560 			Z_ADDREF_P(intern->heap->elements[i]);
561 		}
562 
563 		pnstr = spl_gen_private_prop_name(ce, "heap", sizeof("heap")-1, &pnlen TSRMLS_CC);
564 		add_assoc_zval_ex(&zrv, pnstr, pnlen+1, heap_array);
565 		efree(pnstr);
566 	}
567 
568 	return intern->debug_info;
569 }
570 /* }}} */
571 
spl_heap_object_get_debug_info(zval * obj,int * is_temp TSRMLS_DC)572 static HashTable* spl_heap_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{ */
573 {
574 	return spl_heap_object_get_debug_info_helper(spl_ce_SplHeap, obj, is_temp TSRMLS_CC);
575 }
576 /* }}} */
577 
spl_pqueue_object_get_debug_info(zval * obj,int * is_temp TSRMLS_DC)578 static HashTable* spl_pqueue_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{ */
579 {
580 	return spl_heap_object_get_debug_info_helper(spl_ce_SplPriorityQueue, obj, is_temp TSRMLS_CC);
581 }
582 /* }}} */
583 
584 /* {{{ proto int SplHeap::count() U
585  Return the number of elements in the heap. */
SPL_METHOD(SplHeap,count)586 SPL_METHOD(SplHeap, count)
587 {
588 	long count;
589 	spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
590 
591 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
592 		return;
593 	}
594 
595 	count = spl_ptr_heap_count(intern->heap);
596 	RETURN_LONG(count);
597 }
598 /* }}} */
599 
600 /* {{{ proto int SplHeap::isEmpty() U
601  Return true if the heap is empty. */
SPL_METHOD(SplHeap,isEmpty)602 SPL_METHOD(SplHeap, isEmpty)
603 {
604 	spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
605 
606 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
607 		return;
608 	}
609 
610 	RETURN_BOOL(spl_ptr_heap_count(intern->heap)==0);
611 }
612 /* }}} */
613 
614 /* {{{ proto bool SplHeap::insert(mixed $value) U
615 	   Push $value on the heap */
SPL_METHOD(SplHeap,insert)616 SPL_METHOD(SplHeap, insert)
617 {
618 	zval *value;
619 	spl_heap_object *intern;
620 
621 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) == FAILURE) {
622 		return;
623 	}
624 
625 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
626 
627 	if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
628 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
629 		return;
630 	}
631 
632 	SEPARATE_ARG_IF_REF(value);
633 
634 	spl_ptr_heap_insert(intern->heap, value, getThis() TSRMLS_CC);
635 
636 	RETURN_TRUE;
637 }
638 /* }}} */
639 
640 /* {{{ proto mixed SplHeap::extract() U
641 	   extract the element out of the top of the heap */
SPL_METHOD(SplHeap,extract)642 SPL_METHOD(SplHeap, extract)
643 {
644 	zval *value;
645 	spl_heap_object *intern;
646 
647 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
648 		return;
649 	}
650 
651 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
652 
653 	if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
654 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
655 		return;
656 	}
657 
658 	value  = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
659 
660 	if (!value) {
661 		zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
662 		return;
663 	}
664 
665 	RETURN_ZVAL(value, 1, 1);
666 }
667 /* }}} */
668 
669 /* {{{ proto bool SplPriorityQueue::insert(mixed $value, mixed $priority) U
670 	   Push $value with the priority $priodiry on the priorityqueue */
SPL_METHOD(SplPriorityQueue,insert)671 SPL_METHOD(SplPriorityQueue, insert)
672 {
673 	zval *data, *priority, *elem;
674 	spl_heap_object *intern;
675 
676 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &data, &priority) == FAILURE) {
677 		return;
678 	}
679 
680 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
681 
682 	if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
683 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
684 		return;
685 	}
686 
687 	SEPARATE_ARG_IF_REF(data);
688 	SEPARATE_ARG_IF_REF(priority);
689 
690 	ALLOC_INIT_ZVAL(elem);
691 
692 	array_init(elem);
693 	add_assoc_zval_ex(elem, "data",     sizeof("data"),     data);
694 	add_assoc_zval_ex(elem, "priority", sizeof("priority"), priority);
695 
696 	spl_ptr_heap_insert(intern->heap, elem, getThis() TSRMLS_CC);
697 
698 	RETURN_TRUE;
699 }
700 /* }}} */
701 
702 /* {{{ proto mixed SplPriorityQueue::extract() U
703 	   extract the element out of the top of the priority queue */
SPL_METHOD(SplPriorityQueue,extract)704 SPL_METHOD(SplPriorityQueue, extract)
705 {
706 	zval *value, *value_out, **value_out_pp;
707 	spl_heap_object *intern;
708 
709 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
710 		return;
711 	}
712 
713 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
714 
715 	if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
716 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
717 		return;
718 	}
719 
720 	value  = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
721 
722 	if (!value) {
723 		zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
724 		return;
725 	}
726 
727 	value_out_pp = spl_pqueue_extract_helper(&value, intern->flags);
728 
729 
730 	if (!value_out_pp) {
731 		zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
732 		zval_ptr_dtor(&value);
733 		return;
734 	}
735 
736 	value_out = *value_out_pp;
737 
738 	Z_ADDREF_P(value_out);
739 	zval_ptr_dtor(&value);
740 
741 	RETURN_ZVAL(value_out, 1, 1);
742 }
743 /* }}} */
744 
745 /* {{{ proto mixed SplPriorityQueue::top() U
746 	   Peek at the top element of the priority queue */
SPL_METHOD(SplPriorityQueue,top)747 SPL_METHOD(SplPriorityQueue, top)
748 {
749 	zval *value, **value_out;
750 	spl_heap_object *intern;
751 
752 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
753 		return;
754 	}
755 
756 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
757 
758 	if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
759 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
760 		return;
761 	}
762 
763 	value  = (zval *)spl_ptr_heap_top(intern->heap);
764 
765 	if (!value) {
766 		zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
767 		return;
768 	}
769 
770 	value_out = spl_pqueue_extract_helper(&value, intern->flags);
771 
772 	if (!value_out) {
773 		zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
774 		return;
775 	}
776 
777 	RETURN_ZVAL(*value_out, 1, 0);
778 }
779 /* }}} */
780 
781 /* {{{ proto int SplPriorityQueue::setIteratorMode($flags) U
782  Set the flags of extraction*/
SPL_METHOD(SplPriorityQueue,setExtractFlags)783 SPL_METHOD(SplPriorityQueue, setExtractFlags)
784 {
785 	long value;
786 	spl_heap_object *intern;
787 
788 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &value) == FAILURE) {
789 		return;
790 	}
791 
792 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
793 
794 	intern->flags = value & SPL_PQUEUE_EXTR_MASK;
795 
796 	RETURN_LONG(intern->flags);
797 }
798 /* }}} */
799 
800 /* {{{ proto int SplHeap::recoverFromCorruption() U
801  Recover from a corrupted state*/
SPL_METHOD(SplHeap,recoverFromCorruption)802 SPL_METHOD(SplHeap, recoverFromCorruption)
803 {
804 	spl_heap_object *intern;
805 
806 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
807 		return;
808 	}
809 
810 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
811 
812 	intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED;
813 
814 	RETURN_TRUE;
815 }
816 /* }}} */
817 
818 /* {{{ proto bool SplPriorityQueue::compare(mixed $a, mixed $b) U
819 	   compare the priorities */
SPL_METHOD(SplPriorityQueue,compare)820 SPL_METHOD(SplPriorityQueue, compare)
821 {
822 	zval *a, *b;
823 
824 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
825 		return;
826 	}
827 
828 	RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
829 }
830 /* }}} */
831 
832 /* {{{ proto mixed SplHeap::top() U
833 	   Peek at the top element of the heap */
SPL_METHOD(SplHeap,top)834 SPL_METHOD(SplHeap, top)
835 {
836 	zval *value;
837 	spl_heap_object *intern;
838 
839 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
840 		return;
841 	}
842 
843 	intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
844 
845 	if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
846 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
847 		return;
848 	}
849 
850 	value  = (zval *)spl_ptr_heap_top(intern->heap);
851 
852 	if (!value) {
853 		zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
854 		return;
855 	}
856 
857 	RETURN_ZVAL(value, 1, 0);
858 }
859 /* }}} */
860 
861 /* {{{ proto bool SplMinHeap::compare(mixed $a, mixed $b) U
862 	   compare the values */
SPL_METHOD(SplMinHeap,compare)863 SPL_METHOD(SplMinHeap, compare)
864 {
865 	zval *a, *b;
866 
867 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
868 		return;
869 	}
870 
871 	RETURN_LONG(spl_ptr_heap_zval_min_cmp(a, b, NULL TSRMLS_CC));
872 }
873 /* }}} */
874 
875 /* {{{ proto bool SplMaxHeap::compare(mixed $a, mixed $b) U
876 	   compare the values */
SPL_METHOD(SplMaxHeap,compare)877 SPL_METHOD(SplMaxHeap, compare)
878 {
879 	zval *a, *b;
880 
881 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
882 		return;
883 	}
884 
885 	RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
886 }
887 /* }}} */
888 
spl_heap_it_dtor(zend_object_iterator * iter TSRMLS_DC)889 static void spl_heap_it_dtor(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
890 {
891 	spl_heap_it *iterator = (spl_heap_it *)iter;
892 
893 	zend_user_it_invalidate_current(iter TSRMLS_CC);
894 	zval_ptr_dtor((zval**)&iterator->intern.it.data);
895 
896 	efree(iterator);
897 }
898 /* }}} */
899 
spl_heap_it_rewind(zend_object_iterator * iter TSRMLS_DC)900 static void spl_heap_it_rewind(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
901 {
902 	/* do nothing, the iterator always points to the top element */
903 }
904 /* }}} */
905 
spl_heap_it_valid(zend_object_iterator * iter TSRMLS_DC)906 static int spl_heap_it_valid(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
907 {
908 	spl_heap_it         *iterator = (spl_heap_it *)iter;
909 
910 	return (iterator->object->heap->count != 0 ? SUCCESS : FAILURE);
911 }
912 /* }}} */
913 
spl_heap_it_get_current_data(zend_object_iterator * iter,zval *** data TSRMLS_DC)914 static void spl_heap_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
915 {
916 	spl_heap_it  *iterator = (spl_heap_it *)iter;
917 	zval        **element  = (zval **)&iterator->object->heap->elements[0];
918 
919 	if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
920 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
921 		return;
922 	}
923 
924 	if (iterator->object->heap->count == 0 || !*element) {
925 		*data = NULL;
926 	} else {
927 		*data = element;
928 	}
929 }
930 /* }}} */
931 
spl_pqueue_it_get_current_data(zend_object_iterator * iter,zval *** data TSRMLS_DC)932 static void spl_pqueue_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
933 {
934 	spl_heap_it  *iterator = (spl_heap_it *)iter;
935 	zval        **element  = (zval **)&iterator->object->heap->elements[0];
936 
937 	if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
938 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
939 		return;
940 	}
941 
942 	if (iterator->object->heap->count == 0 || !*element) {
943 		*data = NULL;
944 	} else {
945 		*data = spl_pqueue_extract_helper(element, iterator->object->flags);
946 		if (!*data) {
947 			zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
948 		}
949 	}
950 }
951 /* }}} */
952 
spl_heap_it_get_current_key(zend_object_iterator * iter,zval * key TSRMLS_DC)953 static void spl_heap_it_get_current_key(zend_object_iterator *iter, zval *key TSRMLS_DC) /* {{{ */
954 {
955 	spl_heap_it *iterator = (spl_heap_it *)iter;
956 
957 	ZVAL_LONG(key, iterator->object->heap->count - 1);
958 }
959 /* }}} */
960 
spl_heap_it_move_forward(zend_object_iterator * iter TSRMLS_DC)961 static void spl_heap_it_move_forward(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
962 {
963 	zval                 *object   = (zval*)((zend_user_iterator *)iter)->it.data;
964 	spl_heap_it          *iterator = (spl_heap_it *)iter;
965 	spl_ptr_heap_element elem;
966 
967 	if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
968 		zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
969 		return;
970 	}
971 
972 	elem = spl_ptr_heap_delete_top(iterator->object->heap, object TSRMLS_CC);
973 
974 	if (elem != NULL) {
975 		zval_ptr_dtor((zval **)&elem);
976 	}
977 
978 	zend_user_it_invalidate_current(iter TSRMLS_CC);
979 }
980 /* }}} */
981 
982 /* {{{  proto int SplHeap::key() U
983    Return current array key */
SPL_METHOD(SplHeap,key)984 SPL_METHOD(SplHeap, key)
985 {
986 	spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
987 
988 	if (zend_parse_parameters_none() == FAILURE) {
989 		return;
990 	}
991 
992 	RETURN_LONG(intern->heap->count - 1);
993 }
994 /* }}} */
995 
996 /* {{{ proto void SplHeap::next() U
997    Move to next entry */
SPL_METHOD(SplHeap,next)998 SPL_METHOD(SplHeap, next)
999 {
1000 	spl_heap_object      *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1001 	spl_ptr_heap_element  elem   = spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
1002 
1003 	if (zend_parse_parameters_none() == FAILURE) {
1004 		return;
1005 	}
1006 
1007 	if (elem != NULL) {
1008 		zval_ptr_dtor((zval **)&elem);
1009 	}
1010 }
1011 /* }}} */
1012 
1013 /* {{{ proto bool SplHeap::valid() U
1014    Check whether the datastructure contains more entries */
SPL_METHOD(SplHeap,valid)1015 SPL_METHOD(SplHeap, valid)
1016 {
1017 	spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1018 
1019 	if (zend_parse_parameters_none() == FAILURE) {
1020 		return;
1021 	}
1022 
1023 	RETURN_BOOL(intern->heap->count != 0);
1024 }
1025 /* }}} */
1026 
1027 /* {{{ proto void SplHeap::rewind() U
1028    Rewind the datastructure back to the start */
SPL_METHOD(SplHeap,rewind)1029 SPL_METHOD(SplHeap, rewind)
1030 {
1031 	if (zend_parse_parameters_none() == FAILURE) {
1032 		return;
1033 	}
1034 	/* do nothing, the iterator always points to the top element */
1035 }
1036 /* }}} */
1037 
1038 /* {{{ proto mixed|NULL SplHeap::current() U
1039    Return current datastructure entry */
SPL_METHOD(SplHeap,current)1040 SPL_METHOD(SplHeap, current)
1041 {
1042 	spl_heap_object *intern  = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1043 	zval            *element = (zval *)intern->heap->elements[0];
1044 
1045 	if (zend_parse_parameters_none() == FAILURE) {
1046 		return;
1047 	}
1048 
1049 	if (!intern->heap->count || !element) {
1050 		RETURN_NULL();
1051 	} else {
1052 		RETURN_ZVAL(element, 1, 0);
1053 	}
1054 }
1055 /* }}} */
1056 
1057 /* {{{ proto mixed|NULL SplPriorityQueue::current() U
1058    Return current datastructure entry */
SPL_METHOD(SplPriorityQueue,current)1059 SPL_METHOD(SplPriorityQueue, current)
1060 {
1061 	spl_heap_object  *intern  = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1062 	zval            **element = (zval **)&intern->heap->elements[0];
1063 
1064 	if (zend_parse_parameters_none() == FAILURE) {
1065 		return;
1066 	}
1067 
1068 	if (!intern->heap->count || !*element) {
1069 		RETURN_NULL();
1070 	} else {
1071 		zval **data = spl_pqueue_extract_helper(element, intern->flags);
1072 
1073 		if (!data) {
1074 			zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
1075 			RETURN_NULL();
1076 		}
1077 
1078 		RETURN_ZVAL(*data, 1, 0);
1079 	}
1080 }
1081 /* }}} */
1082 
1083 /* iterator handler table */
1084 zend_object_iterator_funcs spl_heap_it_funcs = {
1085 	spl_heap_it_dtor,
1086 	spl_heap_it_valid,
1087 	spl_heap_it_get_current_data,
1088 	spl_heap_it_get_current_key,
1089 	spl_heap_it_move_forward,
1090 	spl_heap_it_rewind
1091 };
1092 
1093 zend_object_iterator_funcs spl_pqueue_it_funcs = {
1094 	spl_heap_it_dtor,
1095 	spl_heap_it_valid,
1096 	spl_pqueue_it_get_current_data,
1097 	spl_heap_it_get_current_key,
1098 	spl_heap_it_move_forward,
1099 	spl_heap_it_rewind
1100 };
1101 
spl_heap_get_iterator(zend_class_entry * ce,zval * object,int by_ref TSRMLS_DC)1102 zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
1103 {
1104 	spl_heap_it     *iterator;
1105 	spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
1106 
1107 	if (by_ref) {
1108 		zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1109 		return NULL;
1110 	}
1111 
1112 	Z_ADDREF_P(object);
1113 
1114 	iterator                  = emalloc(sizeof(spl_heap_it));
1115 	iterator->intern.it.data  = (void*)object;
1116 	iterator->intern.it.funcs = &spl_heap_it_funcs;
1117 	iterator->intern.ce       = ce;
1118 	iterator->intern.value    = NULL;
1119 	iterator->flags           = heap_object->flags;
1120 	iterator->object          = heap_object;
1121 
1122 	return (zend_object_iterator*)iterator;
1123 }
1124 /* }}} */
1125 
spl_pqueue_get_iterator(zend_class_entry * ce,zval * object,int by_ref TSRMLS_DC)1126 zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
1127 {
1128 	spl_heap_it     *iterator;
1129 	spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
1130 
1131 	if (by_ref) {
1132 		zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1133 		return NULL;
1134 	}
1135 
1136 	Z_ADDREF_P(object);
1137 
1138 	iterator                  = emalloc(sizeof(spl_heap_it));
1139 	iterator->intern.it.data  = (void*)object;
1140 	iterator->intern.it.funcs = &spl_pqueue_it_funcs;
1141 	iterator->intern.ce       = ce;
1142 	iterator->intern.value    = NULL;
1143 	iterator->flags           = heap_object->flags;
1144 	iterator->object          = heap_object;
1145 
1146 	return (zend_object_iterator*)iterator;
1147 }
1148 /* }}} */
1149 
1150 ZEND_BEGIN_ARG_INFO(arginfo_heap_insert, 0)
1151 	ZEND_ARG_INFO(0, value)
1152 ZEND_END_ARG_INFO()
1153 
1154 ZEND_BEGIN_ARG_INFO(arginfo_heap_compare, 0)
1155 	ZEND_ARG_INFO(0, a)
1156 	ZEND_ARG_INFO(0, b)
1157 ZEND_END_ARG_INFO()
1158 
1159 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_insert, 0)
1160 	ZEND_ARG_INFO(0, value)
1161 	ZEND_ARG_INFO(0, priority)
1162 ZEND_END_ARG_INFO()
1163 
1164 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_setflags, 0)
1165 	ZEND_ARG_INFO(0, flags)
1166 ZEND_END_ARG_INFO()
1167 
1168 ZEND_BEGIN_ARG_INFO(arginfo_splheap_void, 0)
1169 ZEND_END_ARG_INFO()
1170 
1171 static const zend_function_entry spl_funcs_SplMinHeap[] = {
1172 	SPL_ME(SplMinHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1173 	{NULL, NULL, NULL}
1174 };
1175 static const zend_function_entry spl_funcs_SplMaxHeap[] = {
1176 	SPL_ME(SplMaxHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1177 	{NULL, NULL, NULL}
1178 };
1179 
1180 static const zend_function_entry spl_funcs_SplPriorityQueue[] = {
1181 	SPL_ME(SplPriorityQueue, compare,               arginfo_heap_compare,    ZEND_ACC_PUBLIC)
1182 	SPL_ME(SplPriorityQueue, insert,                arginfo_pqueue_insert,   ZEND_ACC_PUBLIC)
1183 	SPL_ME(SplPriorityQueue, setExtractFlags,       arginfo_pqueue_setflags, ZEND_ACC_PUBLIC)
1184 	SPL_ME(SplPriorityQueue, top,                   arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1185 	SPL_ME(SplPriorityQueue, extract,               arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1186 	SPL_ME(SplHeap,          count,                 arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1187 	SPL_ME(SplHeap,          isEmpty,               arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1188 	SPL_ME(SplHeap,          rewind,                arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1189 	SPL_ME(SplPriorityQueue, current,               arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1190 	SPL_ME(SplHeap,          key,                   arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1191 	SPL_ME(SplHeap,          next,                  arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1192 	SPL_ME(SplHeap,          valid,                 arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1193 	SPL_ME(SplHeap,          recoverFromCorruption, arginfo_splheap_void,    ZEND_ACC_PUBLIC)
1194 	{NULL, NULL, NULL}
1195 };
1196 
1197 static const zend_function_entry spl_funcs_SplHeap[] = {
1198 	SPL_ME(SplHeap, extract,               arginfo_splheap_void, ZEND_ACC_PUBLIC)
1199 	SPL_ME(SplHeap, insert,                arginfo_heap_insert, ZEND_ACC_PUBLIC)
1200 	SPL_ME(SplHeap, top,                   arginfo_splheap_void, ZEND_ACC_PUBLIC)
1201 	SPL_ME(SplHeap, count,                 arginfo_splheap_void, ZEND_ACC_PUBLIC)
1202 	SPL_ME(SplHeap, isEmpty,               arginfo_splheap_void, ZEND_ACC_PUBLIC)
1203 	SPL_ME(SplHeap, rewind,                arginfo_splheap_void, ZEND_ACC_PUBLIC)
1204 	SPL_ME(SplHeap, current,               arginfo_splheap_void, ZEND_ACC_PUBLIC)
1205 	SPL_ME(SplHeap, key,                   arginfo_splheap_void, ZEND_ACC_PUBLIC)
1206 	SPL_ME(SplHeap, next,                  arginfo_splheap_void, ZEND_ACC_PUBLIC)
1207 	SPL_ME(SplHeap, valid,                 arginfo_splheap_void, ZEND_ACC_PUBLIC)
1208 	SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1209 	ZEND_FENTRY(compare, NULL, NULL, ZEND_ACC_PROTECTED|ZEND_ACC_ABSTRACT)
1210 	{NULL, NULL, NULL}
1211 };
1212 /* }}} */
1213 
PHP_MINIT_FUNCTION(spl_heap)1214 PHP_MINIT_FUNCTION(spl_heap) /* {{{ */
1215 {
1216 	REGISTER_SPL_STD_CLASS_EX(SplHeap, spl_heap_object_new, spl_funcs_SplHeap);
1217 	memcpy(&spl_handler_SplHeap, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1218 
1219 	spl_handler_SplHeap.clone_obj      = spl_heap_object_clone;
1220 	spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
1221 	spl_handler_SplHeap.get_debug_info = spl_heap_object_get_debug_info;
1222 
1223 	REGISTER_SPL_IMPLEMENTS(SplHeap, Iterator);
1224 	REGISTER_SPL_IMPLEMENTS(SplHeap, Countable);
1225 
1226 	spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
1227 
1228 	REGISTER_SPL_SUB_CLASS_EX(SplMinHeap,           SplHeap,        spl_heap_object_new, spl_funcs_SplMinHeap);
1229 	REGISTER_SPL_SUB_CLASS_EX(SplMaxHeap,           SplHeap,        spl_heap_object_new, spl_funcs_SplMaxHeap);
1230 
1231 	spl_ce_SplMaxHeap->get_iterator = spl_heap_get_iterator;
1232 	spl_ce_SplMinHeap->get_iterator = spl_heap_get_iterator;
1233 
1234 	REGISTER_SPL_STD_CLASS_EX(SplPriorityQueue, spl_heap_object_new, spl_funcs_SplPriorityQueue);
1235 	memcpy(&spl_handler_SplPriorityQueue, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1236 
1237 	spl_handler_SplPriorityQueue.clone_obj      = spl_heap_object_clone;
1238 	spl_handler_SplPriorityQueue.count_elements = spl_heap_object_count_elements;
1239 	spl_handler_SplPriorityQueue.get_debug_info = spl_pqueue_object_get_debug_info;
1240 
1241 	REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Iterator);
1242 	REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Countable);
1243 
1244 	spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
1245 
1246 	REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_BOTH",      SPL_PQUEUE_EXTR_BOTH);
1247 	REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_PRIORITY",  SPL_PQUEUE_EXTR_PRIORITY);
1248 	REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_DATA",      SPL_PQUEUE_EXTR_DATA);
1249 
1250 	return SUCCESS;
1251 }
1252 /* }}} */
1253 
1254 /*
1255  * Local variables:
1256  * tab-width: 4
1257  * c-basic-offset: 4
1258  * End:
1259  * vim600: fdm=marker
1260  * vim: noet sw=4 ts=4
1261  */
1262 
1263