This source file includes following definitions.
- spl_ptr_heap_zval_dtor
- spl_ptr_heap_zval_ctor
- spl_ptr_heap_cmp_cb_helper
- spl_pqueue_extract_helper
- spl_ptr_heap_zval_max_cmp
- spl_ptr_heap_zval_min_cmp
- spl_ptr_pqueue_zval_cmp
- spl_ptr_heap_init
- spl_ptr_heap_insert
- spl_ptr_heap_top
- spl_ptr_heap_delete_top
- spl_ptr_heap_clone
- spl_ptr_heap_destroy
- spl_ptr_heap_count
- spl_heap_object_free_storage
- spl_heap_object_new_ex
- spl_heap_object_new
- spl_heap_object_clone
- spl_heap_object_count_elements
- spl_heap_object_get_debug_info_helper
- spl_heap_object_get_debug_info
- spl_pqueue_object_get_debug_info
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- spl_heap_it_dtor
- spl_heap_it_rewind
- spl_heap_it_valid
- spl_heap_it_get_current_data
- spl_pqueue_it_get_current_data
- spl_heap_it_get_current_key
- spl_heap_it_move_forward
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- SPL_METHOD
- spl_heap_get_iterator
- spl_pqueue_get_iterator
- PHP_MINIT_FUNCTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 #ifdef HAVE_CONFIG_H
22 # include "config.h"
23 #endif
24
25 #include "php.h"
26 #include "zend_exceptions.h"
27
28 #include "php_spl.h"
29 #include "spl_functions.h"
30 #include "spl_engine.h"
31 #include "spl_iterators.h"
32 #include "spl_heap.h"
33 #include "spl_exceptions.h"
34
35 #define PTR_HEAP_BLOCK_SIZE 64
36
37 #define SPL_HEAP_CORRUPTED 0x00000001
38
39 #define SPL_PQUEUE_EXTR_MASK 0x00000003
40 #define SPL_PQUEUE_EXTR_BOTH 0x00000003
41 #define SPL_PQUEUE_EXTR_DATA 0x00000001
42 #define SPL_PQUEUE_EXTR_PRIORITY 0x00000002
43
44 zend_object_handlers spl_handler_SplHeap;
45 zend_object_handlers spl_handler_SplPriorityQueue;
46
47 PHPAPI zend_class_entry *spl_ce_SplHeap;
48 PHPAPI zend_class_entry *spl_ce_SplMaxHeap;
49 PHPAPI zend_class_entry *spl_ce_SplMinHeap;
50 PHPAPI zend_class_entry *spl_ce_SplPriorityQueue;
51
52 typedef void *spl_ptr_heap_element;
53
54 typedef void (*spl_ptr_heap_dtor_func)(spl_ptr_heap_element TSRMLS_DC);
55 typedef void (*spl_ptr_heap_ctor_func)(spl_ptr_heap_element TSRMLS_DC);
56 typedef int (*spl_ptr_heap_cmp_func)(spl_ptr_heap_element, spl_ptr_heap_element, void* TSRMLS_DC);
57
58 typedef struct _spl_ptr_heap {
59 spl_ptr_heap_element *elements;
60 spl_ptr_heap_ctor_func ctor;
61 spl_ptr_heap_dtor_func dtor;
62 spl_ptr_heap_cmp_func cmp;
63 int count;
64 int max_size;
65 int flags;
66 } spl_ptr_heap;
67
68 typedef struct _spl_heap_object spl_heap_object;
69 typedef struct _spl_heap_it spl_heap_it;
70
71 struct _spl_heap_object {
72 zend_object std;
73 spl_ptr_heap *heap;
74 zval *retval;
75 int flags;
76 zend_class_entry *ce_get_iterator;
77 zend_function *fptr_cmp;
78 zend_function *fptr_count;
79 HashTable *debug_info;
80 };
81
82
83 struct _spl_heap_it {
84 zend_user_iterator intern;
85 int flags;
86 spl_heap_object *object;
87 };
88
89
90 static void spl_ptr_heap_zval_dtor(spl_ptr_heap_element elem TSRMLS_DC) {
91 if (elem) {
92 zval_ptr_dtor((zval **)&elem);
93 }
94 }
95
96
97 static void spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC) {
98 Z_ADDREF_P((zval *)elem);
99 }
100
101
102 static int spl_ptr_heap_cmp_cb_helper(zval *object, spl_heap_object *heap_object, zval *a, zval *b, long *result TSRMLS_DC) {
103 zval *result_p = NULL;
104
105 zend_call_method_with_2_params(&object, heap_object->std.ce, &heap_object->fptr_cmp, "compare", &result_p, a, b);
106
107 if (EG(exception)) {
108 return FAILURE;
109 }
110
111 convert_to_long(result_p);
112 *result = Z_LVAL_P(result_p);
113
114 zval_ptr_dtor(&result_p);
115
116 return SUCCESS;
117 }
118
119
120 static zval **spl_pqueue_extract_helper(zval **value, int flags)
121 {
122 if ((flags & SPL_PQUEUE_EXTR_BOTH) == SPL_PQUEUE_EXTR_BOTH) {
123 return value;
124 } else if ((flags & SPL_PQUEUE_EXTR_BOTH) > 0) {
125
126 if ((flags & SPL_PQUEUE_EXTR_DATA) == SPL_PQUEUE_EXTR_DATA) {
127 zval **data;
128 if (zend_hash_find(Z_ARRVAL_PP(value), "data", sizeof("data"), (void **) &data) == SUCCESS) {
129 return data;
130 }
131 } else {
132 zval **priority;
133 if (zend_hash_find(Z_ARRVAL_PP(value), "priority", sizeof("priority"), (void **) &priority) == SUCCESS) {
134 return priority;
135 }
136 }
137 }
138
139 return NULL;
140 }
141
142
143 static int spl_ptr_heap_zval_max_cmp(spl_ptr_heap_element a, spl_ptr_heap_element b, void* object TSRMLS_DC) {
144 zval result;
145
146 if (EG(exception)) {
147 return 0;
148 }
149
150 if (object) {
151 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object((zval *)object TSRMLS_CC);
152 if (heap_object->fptr_cmp) {
153 long lval = 0;
154 if (spl_ptr_heap_cmp_cb_helper((zval *)object, heap_object, (zval *)a, (zval *)b, &lval TSRMLS_CC) == FAILURE) {
155
156 return 0;
157 }
158 return lval;
159 }
160 }
161
162 INIT_ZVAL(result);
163 compare_function(&result, (zval *)a, (zval *)b TSRMLS_CC);
164 return Z_LVAL(result);
165 }
166
167
168 static int spl_ptr_heap_zval_min_cmp(spl_ptr_heap_element a, spl_ptr_heap_element b, void* object TSRMLS_DC) {
169 zval result;
170
171 if (EG(exception)) {
172 return 0;
173 }
174
175 if (object) {
176 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object((zval *)object TSRMLS_CC);
177 if (heap_object->fptr_cmp) {
178 long lval = 0;
179 if (spl_ptr_heap_cmp_cb_helper((zval *)object, heap_object, (zval *)a, (zval *)b, &lval TSRMLS_CC) == FAILURE) {
180
181 return 0;
182 }
183 return lval;
184 }
185 }
186
187 INIT_ZVAL(result);
188 compare_function(&result, (zval *)b, (zval *)a TSRMLS_CC);
189 return Z_LVAL(result);
190 }
191
192
193 static int spl_ptr_pqueue_zval_cmp(spl_ptr_heap_element a, spl_ptr_heap_element b, void* object TSRMLS_DC) {
194 zval result;
195 zval **a_priority_pp = spl_pqueue_extract_helper((zval **)&a, SPL_PQUEUE_EXTR_PRIORITY);
196 zval **b_priority_pp = spl_pqueue_extract_helper((zval **)&b, SPL_PQUEUE_EXTR_PRIORITY);
197
198 if ((!a_priority_pp) || (!b_priority_pp)) {
199 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
200 return 0;
201 }
202 if (EG(exception)) {
203 return 0;
204 }
205
206 if (object) {
207 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
208 if (heap_object->fptr_cmp) {
209 long lval = 0;
210 if (spl_ptr_heap_cmp_cb_helper((zval *)object, heap_object, *a_priority_pp, *b_priority_pp, &lval TSRMLS_CC) == FAILURE) {
211
212 return 0;
213 }
214 return lval;
215 }
216 }
217
218 INIT_ZVAL(result);
219 compare_function(&result, *a_priority_pp, *b_priority_pp TSRMLS_CC);
220 return Z_LVAL(result);
221 }
222
223
224 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)
225 {
226 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
227
228 heap->dtor = dtor;
229 heap->ctor = ctor;
230 heap->cmp = cmp;
231 heap->elements = safe_emalloc(sizeof(spl_ptr_heap_element), PTR_HEAP_BLOCK_SIZE, 0);
232 heap->max_size = PTR_HEAP_BLOCK_SIZE;
233 heap->count = 0;
234 heap->flags = 0;
235
236 return heap;
237 }
238
239
240 static void spl_ptr_heap_insert(spl_ptr_heap *heap, spl_ptr_heap_element elem, void *cmp_userdata TSRMLS_DC) {
241 int i;
242
243 if (heap->count+1 > heap->max_size) {
244
245 heap->elements = (void **) safe_erealloc(heap->elements, sizeof(spl_ptr_heap_element), (heap->max_size), (sizeof(spl_ptr_heap_element) * (heap->max_size)));
246 heap->max_size *= 2;
247 }
248
249 heap->ctor(elem TSRMLS_CC);
250
251
252 for(i = heap->count; i > 0 && heap->cmp(heap->elements[(i-1)/2], elem, cmp_userdata TSRMLS_CC) < 0; i = (i-1)/2) {
253 heap->elements[i] = heap->elements[(i-1)/2];
254 }
255 heap->count++;
256
257 if (EG(exception)) {
258
259 heap->flags |= SPL_HEAP_CORRUPTED;
260 }
261
262 heap->elements[i] = elem;
263
264 }
265
266
267 static spl_ptr_heap_element spl_ptr_heap_top(spl_ptr_heap *heap) {
268 if (heap->count == 0) {
269 return NULL;
270 }
271
272 return heap->elements[0];
273 }
274
275
276 static spl_ptr_heap_element spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *cmp_userdata TSRMLS_DC) {
277 int i, j;
278 const int limit = (heap->count-1)/2;
279 spl_ptr_heap_element top;
280 spl_ptr_heap_element bottom;
281
282 if (heap->count == 0) {
283 return NULL;
284 }
285
286 top = heap->elements[0];
287 bottom = heap->elements[--heap->count];
288
289 for( i = 0; i < limit; i = j)
290 {
291
292 j = i*2+1;
293 if(j != heap->count && heap->cmp(heap->elements[j+1], heap->elements[j], cmp_userdata TSRMLS_CC) > 0) {
294 j++;
295 }
296
297
298 if(heap->cmp(bottom, heap->elements[j], cmp_userdata TSRMLS_CC) < 0) {
299 heap->elements[i] = heap->elements[j];
300 } else {
301 break;
302 }
303 }
304
305 if (EG(exception)) {
306
307 heap->flags |= SPL_HEAP_CORRUPTED;
308 }
309
310 heap->elements[i] = bottom;
311 heap->dtor(top TSRMLS_CC);
312 return top;
313 }
314
315
316 static spl_ptr_heap *spl_ptr_heap_clone(spl_ptr_heap *from TSRMLS_DC) {
317 int i;
318
319 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
320
321 heap->dtor = from->dtor;
322 heap->ctor = from->ctor;
323 heap->cmp = from->cmp;
324 heap->max_size = from->max_size;
325 heap->count = from->count;
326 heap->flags = from->flags;
327
328 heap->elements = safe_emalloc(sizeof(spl_ptr_heap_element),from->max_size,0);
329 memcpy(heap->elements, from->elements, sizeof(spl_ptr_heap_element)*from->max_size);
330
331 for (i=0; i < heap->count; ++i) {
332 heap->ctor(heap->elements[i] TSRMLS_CC);
333 }
334
335 return heap;
336 }
337
338
339 static void spl_ptr_heap_destroy(spl_ptr_heap *heap TSRMLS_DC) {
340 int i;
341
342 for (i=0; i < heap->count; ++i) {
343 heap->dtor(heap->elements[i] TSRMLS_CC);
344 }
345
346 efree(heap->elements);
347 efree(heap);
348 }
349
350
351 static int spl_ptr_heap_count(spl_ptr_heap *heap) {
352 return heap->count;
353 }
354
355
356
357 zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC);
358
359 static void spl_heap_object_free_storage(void *object TSRMLS_DC)
360 {
361 int i;
362 spl_heap_object *intern = (spl_heap_object *)object;
363
364 zend_object_std_dtor(&intern->std TSRMLS_CC);
365
366 for (i = 0; i < intern->heap->count; ++i) {
367 if (intern->heap->elements[i]) {
368 zval_ptr_dtor((zval **)&intern->heap->elements[i]);
369 }
370 }
371
372 spl_ptr_heap_destroy(intern->heap TSRMLS_CC);
373
374 zval_ptr_dtor(&intern->retval);
375
376 if (intern->debug_info != NULL) {
377 zend_hash_destroy(intern->debug_info);
378 efree(intern->debug_info);
379 }
380
381 efree(object);
382 }
383
384
385 static zend_object_value spl_heap_object_new_ex(zend_class_entry *class_type, spl_heap_object **obj, zval *orig, int clone_orig TSRMLS_DC)
386 {
387 zend_object_value retval;
388 spl_heap_object *intern;
389 zend_class_entry *parent = class_type;
390 int inherited = 0;
391
392 intern = ecalloc(1, sizeof(spl_heap_object));
393 *obj = intern;
394 ALLOC_INIT_ZVAL(intern->retval);
395
396 zend_object_std_init(&intern->std, class_type TSRMLS_CC);
397 object_properties_init(&intern->std, class_type);
398
399 intern->flags = 0;
400 intern->fptr_cmp = NULL;
401 intern->debug_info = NULL;
402
403 if (orig) {
404 spl_heap_object *other = (spl_heap_object*)zend_object_store_get_object(orig TSRMLS_CC);
405 intern->ce_get_iterator = other->ce_get_iterator;
406
407 if (clone_orig) {
408 int i;
409 intern->heap = spl_ptr_heap_clone(other->heap TSRMLS_CC);
410 for (i = 0; i < intern->heap->count; ++i) {
411 if (intern->heap->elements[i]) {
412 Z_ADDREF_P((zval *)intern->heap->elements[i]);
413 }
414 }
415 } else {
416 intern->heap = other->heap;
417 }
418
419 intern->flags = other->flags;
420 } else {
421 intern->heap = spl_ptr_heap_init(spl_ptr_heap_zval_max_cmp, spl_ptr_heap_zval_ctor, spl_ptr_heap_zval_dtor);
422 }
423
424 retval.handlers = &spl_handler_SplHeap;
425
426 while (parent) {
427 if (parent == spl_ce_SplPriorityQueue) {
428 intern->heap->cmp = spl_ptr_pqueue_zval_cmp;
429 intern->flags = SPL_PQUEUE_EXTR_DATA;
430 retval.handlers = &spl_handler_SplPriorityQueue;
431 break;
432 }
433
434 if (parent == spl_ce_SplMinHeap) {
435 intern->heap->cmp = spl_ptr_heap_zval_min_cmp;
436 break;
437 }
438
439 if (parent == spl_ce_SplMaxHeap) {
440 intern->heap->cmp = spl_ptr_heap_zval_max_cmp;
441 break;
442 }
443
444 if (parent == spl_ce_SplHeap) {
445 break;
446 }
447
448 parent = parent->parent;
449 inherited = 1;
450 }
451
452 retval.handle = zend_objects_store_put(intern, (zend_objects_store_dtor_t)zend_objects_destroy_object, spl_heap_object_free_storage, NULL TSRMLS_CC);
453
454 if (!parent) {
455 php_error_docref(NULL TSRMLS_CC, E_COMPILE_ERROR, "Internal compiler error, Class is not child of SplHeap");
456 }
457
458 if (inherited) {
459 zend_hash_find(&class_type->function_table, "compare", sizeof("compare"), (void **) &intern->fptr_cmp);
460 if (intern->fptr_cmp->common.scope == parent) {
461 intern->fptr_cmp = NULL;
462 }
463 zend_hash_find(&class_type->function_table, "count", sizeof("count"), (void **) &intern->fptr_count);
464 if (intern->fptr_count->common.scope == parent) {
465 intern->fptr_count = NULL;
466 }
467 }
468
469 return retval;
470 }
471
472
473 static zend_object_value spl_heap_object_new(zend_class_entry *class_type TSRMLS_DC)
474 {
475 spl_heap_object *tmp;
476 return spl_heap_object_new_ex(class_type, &tmp, NULL, 0 TSRMLS_CC);
477 }
478
479
480 static zend_object_value spl_heap_object_clone(zval *zobject TSRMLS_DC)
481 {
482 zend_object_value new_obj_val;
483 zend_object *old_object;
484 zend_object *new_object;
485 zend_object_handle handle = Z_OBJ_HANDLE_P(zobject);
486 spl_heap_object *intern;
487
488 old_object = zend_objects_get_address(zobject TSRMLS_CC);
489 new_obj_val = spl_heap_object_new_ex(old_object->ce, &intern, zobject, 1 TSRMLS_CC);
490 new_object = &intern->std;
491
492 zend_objects_clone_members(new_object, new_obj_val, old_object, handle TSRMLS_CC);
493
494 return new_obj_val;
495 }
496
497
498 static int spl_heap_object_count_elements(zval *object, long *count TSRMLS_DC)
499 {
500 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
501
502 if (intern->fptr_count) {
503 zval *rv;
504 zend_call_method_with_0_params(&object, intern->std.ce, &intern->fptr_count, "count", &rv);
505 if (rv) {
506 zval_ptr_dtor(&intern->retval);
507 MAKE_STD_ZVAL(intern->retval);
508 ZVAL_ZVAL(intern->retval, rv, 1, 1);
509 convert_to_long(intern->retval);
510 *count = (long) Z_LVAL_P(intern->retval);
511 return SUCCESS;
512 }
513 *count = 0;
514 return FAILURE;
515 }
516
517 *count = spl_ptr_heap_count(intern->heap);
518
519 return SUCCESS;
520 }
521
522
523 static HashTable* spl_heap_object_get_debug_info_helper(zend_class_entry *ce, zval *obj, int *is_temp TSRMLS_DC) {
524 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(obj TSRMLS_CC);
525 zval *tmp, zrv, *heap_array;
526 char *pnstr;
527 int pnlen;
528 int i;
529
530 *is_temp = 0;
531
532 if (!intern->std.properties) {
533 rebuild_object_properties(&intern->std);
534 }
535
536 if (intern->debug_info == NULL) {
537 ALLOC_HASHTABLE(intern->debug_info);
538 ZEND_INIT_SYMTABLE_EX(intern->debug_info, zend_hash_num_elements(intern->std.properties) + 1, 0);
539 }
540
541 if (intern->debug_info->nApplyCount == 0) {
542 INIT_PZVAL(&zrv);
543 Z_ARRVAL(zrv) = intern->debug_info;
544
545 zend_hash_copy(intern->debug_info, intern->std.properties, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
546
547 pnstr = spl_gen_private_prop_name(ce, "flags", sizeof("flags")-1, &pnlen TSRMLS_CC);
548 add_assoc_long_ex(&zrv, pnstr, pnlen+1, intern->flags);
549 efree(pnstr);
550
551 pnstr = spl_gen_private_prop_name(ce, "isCorrupted", sizeof("isCorrupted")-1, &pnlen TSRMLS_CC);
552 add_assoc_bool_ex(&zrv, pnstr, pnlen+1, intern->heap->flags&SPL_HEAP_CORRUPTED);
553 efree(pnstr);
554
555 ALLOC_INIT_ZVAL(heap_array);
556 array_init(heap_array);
557
558 for (i = 0; i < intern->heap->count; ++i) {
559 add_index_zval(heap_array, i, (zval *)intern->heap->elements[i]);
560 Z_ADDREF_P(intern->heap->elements[i]);
561 }
562
563 pnstr = spl_gen_private_prop_name(ce, "heap", sizeof("heap")-1, &pnlen TSRMLS_CC);
564 add_assoc_zval_ex(&zrv, pnstr, pnlen+1, heap_array);
565 efree(pnstr);
566 }
567
568 return intern->debug_info;
569 }
570
571
572 static HashTable* spl_heap_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC)
573 {
574 return spl_heap_object_get_debug_info_helper(spl_ce_SplHeap, obj, is_temp TSRMLS_CC);
575 }
576
577
578 static HashTable* spl_pqueue_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC)
579 {
580 return spl_heap_object_get_debug_info_helper(spl_ce_SplPriorityQueue, obj, is_temp TSRMLS_CC);
581 }
582
583
584
585
586 SPL_METHOD(SplHeap, count)
587 {
588 long count;
589 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
590
591 if (zend_parse_parameters_none() == FAILURE) {
592 return;
593 }
594
595 count = spl_ptr_heap_count(intern->heap);
596 RETURN_LONG(count);
597 }
598
599
600
601
602 SPL_METHOD(SplHeap, isEmpty)
603 {
604 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
605
606 if (zend_parse_parameters_none() == FAILURE) {
607 return;
608 }
609
610 RETURN_BOOL(spl_ptr_heap_count(intern->heap)==0);
611 }
612
613
614
615
616 SPL_METHOD(SplHeap, insert)
617 {
618 zval *value;
619 spl_heap_object *intern;
620
621 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) == FAILURE) {
622 return;
623 }
624
625 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
626
627 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
628 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
629 return;
630 }
631
632 SEPARATE_ARG_IF_REF(value);
633
634 spl_ptr_heap_insert(intern->heap, value, getThis() TSRMLS_CC);
635
636 RETURN_TRUE;
637 }
638
639
640
641
642 SPL_METHOD(SplHeap, extract)
643 {
644 zval *value;
645 spl_heap_object *intern;
646
647 if (zend_parse_parameters_none() == FAILURE) {
648 return;
649 }
650
651 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
652
653 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
654 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
655 return;
656 }
657
658 value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
659
660 if (!value) {
661 zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
662 return;
663 }
664
665 RETURN_ZVAL(value, 1, 1);
666 }
667
668
669
670
671 SPL_METHOD(SplPriorityQueue, insert)
672 {
673 zval *data, *priority, *elem;
674 spl_heap_object *intern;
675
676 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &data, &priority) == FAILURE) {
677 return;
678 }
679
680 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
681
682 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
683 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
684 return;
685 }
686
687 SEPARATE_ARG_IF_REF(data);
688 SEPARATE_ARG_IF_REF(priority);
689
690 ALLOC_INIT_ZVAL(elem);
691
692 array_init(elem);
693 add_assoc_zval_ex(elem, "data", sizeof("data"), data);
694 add_assoc_zval_ex(elem, "priority", sizeof("priority"), priority);
695
696 spl_ptr_heap_insert(intern->heap, elem, getThis() TSRMLS_CC);
697
698 RETURN_TRUE;
699 }
700
701
702
703
704 SPL_METHOD(SplPriorityQueue, extract)
705 {
706 zval *value, *value_out, **value_out_pp;
707 spl_heap_object *intern;
708
709 if (zend_parse_parameters_none() == FAILURE) {
710 return;
711 }
712
713 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
714
715 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
716 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
717 return;
718 }
719
720 value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
721
722 if (!value) {
723 zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
724 return;
725 }
726
727 value_out_pp = spl_pqueue_extract_helper(&value, intern->flags);
728
729
730 if (!value_out_pp) {
731 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
732 zval_ptr_dtor(&value);
733 return;
734 }
735
736 value_out = *value_out_pp;
737
738 Z_ADDREF_P(value_out);
739 zval_ptr_dtor(&value);
740
741 RETURN_ZVAL(value_out, 1, 1);
742 }
743
744
745
746
747 SPL_METHOD(SplPriorityQueue, top)
748 {
749 zval *value, **value_out;
750 spl_heap_object *intern;
751
752 if (zend_parse_parameters_none() == FAILURE) {
753 return;
754 }
755
756 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
757
758 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
759 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
760 return;
761 }
762
763 value = (zval *)spl_ptr_heap_top(intern->heap);
764
765 if (!value) {
766 zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
767 return;
768 }
769
770 value_out = spl_pqueue_extract_helper(&value, intern->flags);
771
772 if (!value_out) {
773 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
774 return;
775 }
776
777 RETURN_ZVAL(*value_out, 1, 0);
778 }
779
780
781
782
783 SPL_METHOD(SplPriorityQueue, setExtractFlags)
784 {
785 long value;
786 spl_heap_object *intern;
787
788 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &value) == FAILURE) {
789 return;
790 }
791
792 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
793
794 intern->flags = value & SPL_PQUEUE_EXTR_MASK;
795
796 RETURN_LONG(intern->flags);
797 }
798
799
800
801
802 SPL_METHOD(SplHeap, recoverFromCorruption)
803 {
804 spl_heap_object *intern;
805
806 if (zend_parse_parameters_none() == FAILURE) {
807 return;
808 }
809
810 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
811
812 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED;
813
814 RETURN_TRUE;
815 }
816
817
818
819
820 SPL_METHOD(SplPriorityQueue, compare)
821 {
822 zval *a, *b;
823
824 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
825 return;
826 }
827
828 RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
829 }
830
831
832
833
834 SPL_METHOD(SplHeap, top)
835 {
836 zval *value;
837 spl_heap_object *intern;
838
839 if (zend_parse_parameters_none() == FAILURE) {
840 return;
841 }
842
843 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
844
845 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
846 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
847 return;
848 }
849
850 value = (zval *)spl_ptr_heap_top(intern->heap);
851
852 if (!value) {
853 zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
854 return;
855 }
856
857 RETURN_ZVAL(value, 1, 0);
858 }
859
860
861
862
863 SPL_METHOD(SplMinHeap, compare)
864 {
865 zval *a, *b;
866
867 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
868 return;
869 }
870
871 RETURN_LONG(spl_ptr_heap_zval_min_cmp(a, b, NULL TSRMLS_CC));
872 }
873
874
875
876
877 SPL_METHOD(SplMaxHeap, compare)
878 {
879 zval *a, *b;
880
881 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
882 return;
883 }
884
885 RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
886 }
887
888
889 static void spl_heap_it_dtor(zend_object_iterator *iter TSRMLS_DC)
890 {
891 spl_heap_it *iterator = (spl_heap_it *)iter;
892
893 zend_user_it_invalidate_current(iter TSRMLS_CC);
894 zval_ptr_dtor((zval**)&iterator->intern.it.data);
895
896 efree(iterator);
897 }
898
899
900 static void spl_heap_it_rewind(zend_object_iterator *iter TSRMLS_DC)
901 {
902
903 }
904
905
906 static int spl_heap_it_valid(zend_object_iterator *iter TSRMLS_DC)
907 {
908 spl_heap_it *iterator = (spl_heap_it *)iter;
909
910 return (iterator->object->heap->count != 0 ? SUCCESS : FAILURE);
911 }
912
913
914 static void spl_heap_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC)
915 {
916 spl_heap_it *iterator = (spl_heap_it *)iter;
917 zval **element = (zval **)&iterator->object->heap->elements[0];
918
919 if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
920 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
921 return;
922 }
923
924 if (iterator->object->heap->count == 0 || !*element) {
925 *data = NULL;
926 } else {
927 *data = element;
928 }
929 }
930
931
932 static void spl_pqueue_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC)
933 {
934 spl_heap_it *iterator = (spl_heap_it *)iter;
935 zval **element = (zval **)&iterator->object->heap->elements[0];
936
937 if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
938 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
939 return;
940 }
941
942 if (iterator->object->heap->count == 0 || !*element) {
943 *data = NULL;
944 } else {
945 *data = spl_pqueue_extract_helper(element, iterator->object->flags);
946 if (!*data) {
947 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
948 }
949 }
950 }
951
952
953 static void spl_heap_it_get_current_key(zend_object_iterator *iter, zval *key TSRMLS_DC)
954 {
955 spl_heap_it *iterator = (spl_heap_it *)iter;
956
957 ZVAL_LONG(key, iterator->object->heap->count - 1);
958 }
959
960
961 static void spl_heap_it_move_forward(zend_object_iterator *iter TSRMLS_DC)
962 {
963 zval *object = (zval*)((zend_user_iterator *)iter)->it.data;
964 spl_heap_it *iterator = (spl_heap_it *)iter;
965 spl_ptr_heap_element elem;
966
967 if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
968 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
969 return;
970 }
971
972 elem = spl_ptr_heap_delete_top(iterator->object->heap, object TSRMLS_CC);
973
974 if (elem != NULL) {
975 zval_ptr_dtor((zval **)&elem);
976 }
977
978 zend_user_it_invalidate_current(iter TSRMLS_CC);
979 }
980
981
982
983
984 SPL_METHOD(SplHeap, key)
985 {
986 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
987
988 if (zend_parse_parameters_none() == FAILURE) {
989 return;
990 }
991
992 RETURN_LONG(intern->heap->count - 1);
993 }
994
995
996
997
998 SPL_METHOD(SplHeap, next)
999 {
1000 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1001 spl_ptr_heap_element elem = spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
1002
1003 if (zend_parse_parameters_none() == FAILURE) {
1004 return;
1005 }
1006
1007 if (elem != NULL) {
1008 zval_ptr_dtor((zval **)&elem);
1009 }
1010 }
1011
1012
1013
1014
1015 SPL_METHOD(SplHeap, valid)
1016 {
1017 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1018
1019 if (zend_parse_parameters_none() == FAILURE) {
1020 return;
1021 }
1022
1023 RETURN_BOOL(intern->heap->count != 0);
1024 }
1025
1026
1027
1028
1029 SPL_METHOD(SplHeap, rewind)
1030 {
1031 if (zend_parse_parameters_none() == FAILURE) {
1032 return;
1033 }
1034
1035 }
1036
1037
1038
1039
1040 SPL_METHOD(SplHeap, current)
1041 {
1042 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1043 zval *element = (zval *)intern->heap->elements[0];
1044
1045 if (zend_parse_parameters_none() == FAILURE) {
1046 return;
1047 }
1048
1049 if (!intern->heap->count || !element) {
1050 RETURN_NULL();
1051 } else {
1052 RETURN_ZVAL(element, 1, 0);
1053 }
1054 }
1055
1056
1057
1058
1059 SPL_METHOD(SplPriorityQueue, current)
1060 {
1061 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1062 zval **element = (zval **)&intern->heap->elements[0];
1063
1064 if (zend_parse_parameters_none() == FAILURE) {
1065 return;
1066 }
1067
1068 if (!intern->heap->count || !*element) {
1069 RETURN_NULL();
1070 } else {
1071 zval **data = spl_pqueue_extract_helper(element, intern->flags);
1072
1073 if (!data) {
1074 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
1075 RETURN_NULL();
1076 }
1077
1078 RETURN_ZVAL(*data, 1, 0);
1079 }
1080 }
1081
1082
1083
1084 zend_object_iterator_funcs spl_heap_it_funcs = {
1085 spl_heap_it_dtor,
1086 spl_heap_it_valid,
1087 spl_heap_it_get_current_data,
1088 spl_heap_it_get_current_key,
1089 spl_heap_it_move_forward,
1090 spl_heap_it_rewind
1091 };
1092
1093 zend_object_iterator_funcs spl_pqueue_it_funcs = {
1094 spl_heap_it_dtor,
1095 spl_heap_it_valid,
1096 spl_pqueue_it_get_current_data,
1097 spl_heap_it_get_current_key,
1098 spl_heap_it_move_forward,
1099 spl_heap_it_rewind
1100 };
1101
1102 zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC)
1103 {
1104 spl_heap_it *iterator;
1105 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
1106
1107 if (by_ref) {
1108 zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1109 return NULL;
1110 }
1111
1112 Z_ADDREF_P(object);
1113
1114 iterator = emalloc(sizeof(spl_heap_it));
1115 iterator->intern.it.data = (void*)object;
1116 iterator->intern.it.funcs = &spl_heap_it_funcs;
1117 iterator->intern.ce = ce;
1118 iterator->intern.value = NULL;
1119 iterator->flags = heap_object->flags;
1120 iterator->object = heap_object;
1121
1122 return (zend_object_iterator*)iterator;
1123 }
1124
1125
1126 zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC)
1127 {
1128 spl_heap_it *iterator;
1129 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
1130
1131 if (by_ref) {
1132 zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1133 return NULL;
1134 }
1135
1136 Z_ADDREF_P(object);
1137
1138 iterator = emalloc(sizeof(spl_heap_it));
1139 iterator->intern.it.data = (void*)object;
1140 iterator->intern.it.funcs = &spl_pqueue_it_funcs;
1141 iterator->intern.ce = ce;
1142 iterator->intern.value = NULL;
1143 iterator->flags = heap_object->flags;
1144 iterator->object = heap_object;
1145
1146 return (zend_object_iterator*)iterator;
1147 }
1148
1149
1150 ZEND_BEGIN_ARG_INFO(arginfo_heap_insert, 0)
1151 ZEND_ARG_INFO(0, value)
1152 ZEND_END_ARG_INFO()
1153
1154 ZEND_BEGIN_ARG_INFO(arginfo_heap_compare, 0)
1155 ZEND_ARG_INFO(0, a)
1156 ZEND_ARG_INFO(0, b)
1157 ZEND_END_ARG_INFO()
1158
1159 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_insert, 0)
1160 ZEND_ARG_INFO(0, value)
1161 ZEND_ARG_INFO(0, priority)
1162 ZEND_END_ARG_INFO()
1163
1164 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_setflags, 0)
1165 ZEND_ARG_INFO(0, flags)
1166 ZEND_END_ARG_INFO()
1167
1168 ZEND_BEGIN_ARG_INFO(arginfo_splheap_void, 0)
1169 ZEND_END_ARG_INFO()
1170
1171 static const zend_function_entry spl_funcs_SplMinHeap[] = {
1172 SPL_ME(SplMinHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1173 {NULL, NULL, NULL}
1174 };
1175 static const zend_function_entry spl_funcs_SplMaxHeap[] = {
1176 SPL_ME(SplMaxHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1177 {NULL, NULL, NULL}
1178 };
1179
1180 static const zend_function_entry spl_funcs_SplPriorityQueue[] = {
1181 SPL_ME(SplPriorityQueue, compare, arginfo_heap_compare, ZEND_ACC_PUBLIC)
1182 SPL_ME(SplPriorityQueue, insert, arginfo_pqueue_insert, ZEND_ACC_PUBLIC)
1183 SPL_ME(SplPriorityQueue, setExtractFlags, arginfo_pqueue_setflags, ZEND_ACC_PUBLIC)
1184 SPL_ME(SplPriorityQueue, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1185 SPL_ME(SplPriorityQueue, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1186 SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1187 SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1188 SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1189 SPL_ME(SplPriorityQueue, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1190 SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1191 SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1192 SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1193 SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1194 {NULL, NULL, NULL}
1195 };
1196
1197 static const zend_function_entry spl_funcs_SplHeap[] = {
1198 SPL_ME(SplHeap, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1199 SPL_ME(SplHeap, insert, arginfo_heap_insert, ZEND_ACC_PUBLIC)
1200 SPL_ME(SplHeap, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1201 SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1202 SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1203 SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1204 SPL_ME(SplHeap, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1205 SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1206 SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1207 SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1208 SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1209 ZEND_FENTRY(compare, NULL, NULL, ZEND_ACC_PROTECTED|ZEND_ACC_ABSTRACT)
1210 {NULL, NULL, NULL}
1211 };
1212
1213
1214 PHP_MINIT_FUNCTION(spl_heap)
1215 {
1216 REGISTER_SPL_STD_CLASS_EX(SplHeap, spl_heap_object_new, spl_funcs_SplHeap);
1217 memcpy(&spl_handler_SplHeap, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1218
1219 spl_handler_SplHeap.clone_obj = spl_heap_object_clone;
1220 spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
1221 spl_handler_SplHeap.get_debug_info = spl_heap_object_get_debug_info;
1222
1223 REGISTER_SPL_IMPLEMENTS(SplHeap, Iterator);
1224 REGISTER_SPL_IMPLEMENTS(SplHeap, Countable);
1225
1226 spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
1227
1228 REGISTER_SPL_SUB_CLASS_EX(SplMinHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMinHeap);
1229 REGISTER_SPL_SUB_CLASS_EX(SplMaxHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMaxHeap);
1230
1231 spl_ce_SplMaxHeap->get_iterator = spl_heap_get_iterator;
1232 spl_ce_SplMinHeap->get_iterator = spl_heap_get_iterator;
1233
1234 REGISTER_SPL_STD_CLASS_EX(SplPriorityQueue, spl_heap_object_new, spl_funcs_SplPriorityQueue);
1235 memcpy(&spl_handler_SplPriorityQueue, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1236
1237 spl_handler_SplPriorityQueue.clone_obj = spl_heap_object_clone;
1238 spl_handler_SplPriorityQueue.count_elements = spl_heap_object_count_elements;
1239 spl_handler_SplPriorityQueue.get_debug_info = spl_pqueue_object_get_debug_info;
1240
1241 REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Iterator);
1242 REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Countable);
1243
1244 spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
1245
1246 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_BOTH", SPL_PQUEUE_EXTR_BOTH);
1247 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_PRIORITY", SPL_PQUEUE_EXTR_PRIORITY);
1248 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_DATA", SPL_PQUEUE_EXTR_DATA);
1249
1250 return SUCCESS;
1251 }
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262