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