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