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