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