1 | /* |
2 | +----------------------------------------------------------------------+ |
3 | | PHP Version 5 | |
4 | +----------------------------------------------------------------------+ |
5 | | Copyright (c) 1997-2015 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$ */ |
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 | 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 **(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 | /* exception or call failure */ |
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 | /* exception or call failure */ |
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 | /* exception or call failure */ |
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 | /* we need to allocate more memory */ |
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 | /* sifting up */ |
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 | /* exception thrown during comparison */ |
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 | /* Find smaller child */ |
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++; /* next child is bigger */ |
295 | } |
296 | |
297 | /* swap elements between two levels */ |
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 | /* exception thrown during comparison */ |
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) { /* this must never happen */ |
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 | /* {{{ proto int SplHeap::count() U |
585 | Return the number of elements in the heap. */ |
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 | /* {{{ proto int SplHeap::isEmpty() U |
601 | Return true if the heap is empty. */ |
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 | /* {{{ proto bool SplHeap::insert(mixed $value) U |
615 | Push $value on the heap */ |
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 | /* {{{ proto mixed SplHeap::extract() U |
641 | extract the element out of the top of the heap */ |
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 | /* {{{ proto bool SplPriorityQueue::insert(mixed $value, mixed $priority) U |
670 | Push $value with the priority $priodiry on the priorityqueue */ |
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 | /* {{{ proto mixed SplPriorityQueue::extract() U |
703 | extract the element out of the top of the priority queue */ |
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 | /* {{{ proto mixed SplPriorityQueue::top() U |
746 | Peek at the top element of the priority queue */ |
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 | /* {{{ proto int SplPriorityQueue::setIteratorMode($flags) U |
782 | Set the flags of extraction*/ |
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 | /* {{{ proto int SplHeap::recoverFromCorruption() U |
801 | Recover from a corrupted state*/ |
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 | /* {{{ proto bool SplPriorityQueue::compare(mixed $a, mixed $b) U |
819 | compare the priorities */ |
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 | /* {{{ proto mixed SplHeap::top() U |
833 | Peek at the top element of the heap */ |
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 | /* {{{ proto bool SplMinHeap::compare(mixed $a, mixed $b) U |
862 | compare the values */ |
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 | /* {{{ proto bool SplMaxHeap::compare(mixed $a, mixed $b) U |
876 | compare the values */ |
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 | /* do nothing, the iterator always points to the top element */ |
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 | /* {{{ proto int SplHeap::key() U |
983 | Return current array key */ |
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 | /* {{{ proto void SplHeap::next() U |
997 | Move to next entry */ |
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 | /* {{{ proto bool SplHeap::valid() U |
1014 | Check whether the datastructure contains more entries */ |
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 | /* {{{ proto void SplHeap::rewind() U |
1028 | Rewind the datastructure back to the start */ |
1029 | SPL_METHOD(SplHeap, rewind) |
1030 | { |
1031 | if (zend_parse_parameters_none() == FAILURE) { |
1032 | return; |
1033 | } |
1034 | /* do nothing, the iterator always points to the top element */ |
1035 | } |
1036 | /* }}} */ |
1037 | |
1038 | /* {{{ proto mixed|NULL SplHeap::current() U |
1039 | Return current datastructure entry */ |
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 | /* {{{ proto mixed|NULL SplPriorityQueue::current() U |
1058 | Return current datastructure entry */ |
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 | /* iterator handler table */ |
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 | * Local variables: |
1256 | * tab-width: 4 |
1257 | * c-basic-offset: 4 |
1258 | * End: |
1259 | * vim600: fdm=marker |
1260 | * vim: noet sw=4 ts=4 |
1261 | */ |
1262 | |
1263 | |