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