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