This source file includes following definitions.
- spl_heap_from_obj
- spl_ptr_heap_zval_dtor
- spl_ptr_heap_zval_ctor
- spl_ptr_heap_cmp_cb_helper
- spl_pqueue_extract_helper
- spl_ptr_heap_zval_max_cmp
- spl_ptr_heap_zval_min_cmp
- spl_ptr_pqueue_zval_cmp
- spl_ptr_heap_init
- spl_ptr_heap_insert
- spl_ptr_heap_top
- spl_ptr_heap_delete_top
- spl_ptr_heap_clone
- spl_ptr_heap_destroy
- spl_ptr_heap_count
- spl_heap_object_free_storage
- spl_heap_object_new_ex
- spl_heap_object_new
- spl_heap_object_clone
- spl_heap_object_count_elements
- spl_heap_object_get_debug_info_helper
- spl_heap_object_get_gc
- spl_heap_object_get_debug_info
- spl_pqueue_object_get_debug_info
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- spl_heap_it_dtor
- spl_heap_it_rewind
- spl_heap_it_valid
- spl_heap_it_get_current_data
- spl_pqueue_it_get_current_data
- spl_heap_it_get_current_key
- spl_heap_it_move_forward
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- spl_heap_get_iterator
- spl_pqueue_get_iterator
- PHP_MINIT_FUNCTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
80 struct _spl_heap_it {
81 zend_user_iterator intern;
82 int flags;
83 };
84
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
257 heap->flags |= SPL_HEAP_CORRUPTED;
258 }
259
260 ZVAL_COPY_VALUE(&heap->elements[i], elem);
261 }
262
263
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
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
288 j = i * 2 + 1;
289 if(j != heap->count && heap->cmp(&heap->elements[j+1], &heap->elements[j], cmp_userdata) > 0) {
290 j++;
291 }
292
293
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
303 heap->flags |= SPL_HEAP_CORRUPTED;
304 }
305
306 ZVAL_COPY_VALUE(&heap->elements[i], bottom);
307 }
308
309
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
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
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
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
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) {
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
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
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
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
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
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
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
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
547
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
563
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
577
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
602
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
628
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
659
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
698
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
736
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
755
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
771
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
789
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
805
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
819
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
849
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
863
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
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
885 static void spl_heap_it_rewind(zend_object_iterator *iter)
886 {
887
888 }
889
890
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
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
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
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
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
964
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
978
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
994
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
1008
1009 SPL_METHOD(SplHeap, rewind)
1010 {
1011 if (zend_parse_parameters_none() == FAILURE) {
1012 return;
1013 }
1014
1015 }
1016
1017
1018
1019
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
1039
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
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 };
1074
1075 zend_object_iterator_funcs spl_pqueue_it_funcs = {
1076 spl_heap_it_dtor,
1077 spl_heap_it_valid,
1078 spl_pqueue_it_get_current_data,
1079 spl_heap_it_get_current_key,
1080 spl_heap_it_move_forward,
1081 spl_heap_it_rewind
1082 };
1083
1084 zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref)
1085 {
1086 spl_heap_it *iterator;
1087 spl_heap_object *heap_object = Z_SPLHEAP_P(object);
1088
1089 if (by_ref) {
1090 zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0);
1091 return NULL;
1092 }
1093
1094 iterator = emalloc(sizeof(spl_heap_it));
1095
1096 zend_iterator_init(&iterator->intern.it);
1097
1098 ZVAL_COPY(&iterator->intern.it.data, object);
1099 iterator->intern.it.funcs = &spl_heap_it_funcs;
1100 iterator->intern.ce = ce;
1101 iterator->flags = heap_object->flags;
1102 ZVAL_UNDEF(&iterator->intern.value);
1103
1104 return &iterator->intern.it;
1105 }
1106
1107
1108 zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval *object, int by_ref)
1109 {
1110 spl_heap_it *iterator;
1111 spl_heap_object *heap_object = Z_SPLHEAP_P(object);
1112
1113 if (by_ref) {
1114 zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0);
1115 return NULL;
1116 }
1117
1118 iterator = emalloc(sizeof(spl_heap_it));
1119
1120 zend_iterator_init((zend_object_iterator*)iterator);
1121
1122 ZVAL_COPY(&iterator->intern.it.data, object);
1123 iterator->intern.it.funcs = &spl_pqueue_it_funcs;
1124 iterator->intern.ce = ce;
1125 iterator->flags = heap_object->flags;
1126
1127 ZVAL_UNDEF(&iterator->intern.value);
1128
1129 return &iterator->intern.it;
1130 }
1131
1132
1133 ZEND_BEGIN_ARG_INFO(arginfo_heap_insert, 0)
1134 ZEND_ARG_INFO(0, value)
1135 ZEND_END_ARG_INFO()
1136
1137 ZEND_BEGIN_ARG_INFO(arginfo_heap_compare, 0)
1138 ZEND_ARG_INFO(0, a)
1139 ZEND_ARG_INFO(0, b)
1140 ZEND_END_ARG_INFO()
1141
1142 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_insert, 0)
1143 ZEND_ARG_INFO(0, value)
1144 ZEND_ARG_INFO(0, priority)
1145 ZEND_END_ARG_INFO()
1146
1147 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_setflags, 0)
1148 ZEND_ARG_INFO(0, flags)
1149 ZEND_END_ARG_INFO()
1150
1151 ZEND_BEGIN_ARG_INFO(arginfo_splheap_void, 0)
1152 ZEND_END_ARG_INFO()
1153
1154 static const zend_function_entry spl_funcs_SplMinHeap[] = {
1155 SPL_ME(SplMinHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1156 {NULL, NULL, NULL}
1157 };
1158 static const zend_function_entry spl_funcs_SplMaxHeap[] = {
1159 SPL_ME(SplMaxHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1160 {NULL, NULL, NULL}
1161 };
1162
1163 static const zend_function_entry spl_funcs_SplPriorityQueue[] = {
1164 SPL_ME(SplPriorityQueue, compare, arginfo_heap_compare, ZEND_ACC_PUBLIC)
1165 SPL_ME(SplPriorityQueue, insert, arginfo_pqueue_insert, ZEND_ACC_PUBLIC)
1166 SPL_ME(SplPriorityQueue, setExtractFlags, arginfo_pqueue_setflags, ZEND_ACC_PUBLIC)
1167 SPL_ME(SplPriorityQueue, getExtractFlags, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1168 SPL_ME(SplPriorityQueue, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1169 SPL_ME(SplPriorityQueue, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1170 SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1171 SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1172 SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1173 SPL_ME(SplPriorityQueue, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1174 SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1175 SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1176 SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1177 SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1178 SPL_ME(SplHeap, isCorrupted, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1179 {NULL, NULL, NULL}
1180 };
1181
1182 static const zend_function_entry spl_funcs_SplHeap[] = {
1183 SPL_ME(SplHeap, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1184 SPL_ME(SplHeap, insert, arginfo_heap_insert, ZEND_ACC_PUBLIC)
1185 SPL_ME(SplHeap, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1186 SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1187 SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1188 SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1189 SPL_ME(SplHeap, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1190 SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1191 SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1192 SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1193 SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1194 SPL_ME(SplHeap, isCorrupted, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1195 ZEND_FENTRY(compare, NULL, NULL, ZEND_ACC_PROTECTED|ZEND_ACC_ABSTRACT)
1196 {NULL, NULL, NULL}
1197 };
1198
1199
1200 PHP_MINIT_FUNCTION(spl_heap)
1201 {
1202 REGISTER_SPL_STD_CLASS_EX(SplHeap, spl_heap_object_new, spl_funcs_SplHeap);
1203 memcpy(&spl_handler_SplHeap, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1204
1205 spl_handler_SplHeap.offset = XtOffsetOf(spl_heap_object, std);
1206 spl_handler_SplHeap.clone_obj = spl_heap_object_clone;
1207 spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
1208 spl_handler_SplHeap.get_debug_info = spl_heap_object_get_debug_info;
1209 spl_handler_SplHeap.get_gc = spl_heap_object_get_gc;
1210 spl_handler_SplHeap.dtor_obj = zend_objects_destroy_object;
1211 spl_handler_SplHeap.free_obj = spl_heap_object_free_storage;
1212
1213 REGISTER_SPL_IMPLEMENTS(SplHeap, Iterator);
1214 REGISTER_SPL_IMPLEMENTS(SplHeap, Countable);
1215
1216 spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
1217
1218 REGISTER_SPL_SUB_CLASS_EX(SplMinHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMinHeap);
1219 REGISTER_SPL_SUB_CLASS_EX(SplMaxHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMaxHeap);
1220
1221 spl_ce_SplMaxHeap->get_iterator = spl_heap_get_iterator;
1222 spl_ce_SplMinHeap->get_iterator = spl_heap_get_iterator;
1223
1224 REGISTER_SPL_STD_CLASS_EX(SplPriorityQueue, spl_heap_object_new, spl_funcs_SplPriorityQueue);
1225 memcpy(&spl_handler_SplPriorityQueue, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1226
1227 spl_handler_SplPriorityQueue.offset = XtOffsetOf(spl_heap_object, std);
1228 spl_handler_SplPriorityQueue.clone_obj = spl_heap_object_clone;
1229 spl_handler_SplPriorityQueue.count_elements = spl_heap_object_count_elements;
1230 spl_handler_SplPriorityQueue.get_debug_info = spl_pqueue_object_get_debug_info;
1231 spl_handler_SplPriorityQueue.get_gc = spl_heap_object_get_gc;
1232 spl_handler_SplPriorityQueue.dtor_obj = zend_objects_destroy_object;
1233 spl_handler_SplPriorityQueue.free_obj = spl_heap_object_free_storage;
1234
1235 REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Iterator);
1236 REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Countable);
1237
1238 spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
1239
1240 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_BOTH", SPL_PQUEUE_EXTR_BOTH);
1241 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_PRIORITY", SPL_PQUEUE_EXTR_PRIORITY);
1242 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_DATA", SPL_PQUEUE_EXTR_DATA);
1243
1244 return SUCCESS;
1245 }
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256