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