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