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