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