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
