1 /*
2 +----------------------------------------------------------------------+
3 | PHP Version 5 |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1997-2013 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 */
spl_ptr_heap_zval_dtor(spl_ptr_heap_element elem TSRMLS_DC)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
spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC)97 static void spl_ptr_heap_zval_ctor(spl_ptr_heap_element elem TSRMLS_DC) { /* {{{ */
98 Z_ADDREF_P((zval *)elem);
99 }
100 /* }}} */
101
spl_ptr_heap_cmp_cb_helper(zval * object,spl_heap_object * heap_object,zval * a,zval * b,long * result TSRMLS_DC)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
spl_pqueue_extract_helper(zval ** value,int flags)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
spl_ptr_heap_zval_max_cmp(spl_ptr_heap_element a,spl_ptr_heap_element b,void * object TSRMLS_DC)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
spl_ptr_heap_zval_min_cmp(spl_ptr_heap_element a,spl_ptr_heap_element b,void * object TSRMLS_DC)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
spl_ptr_pqueue_zval_cmp(spl_ptr_heap_element a,spl_ptr_heap_element b,void * object TSRMLS_DC)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
spl_ptr_heap_init(spl_ptr_heap_cmp_func cmp,spl_ptr_heap_ctor_func ctor,spl_ptr_heap_dtor_func dtor)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
spl_ptr_heap_insert(spl_ptr_heap * heap,spl_ptr_heap_element elem,void * cmp_userdata TSRMLS_DC)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
256 if (EG(exception)) {
257 /* exception thrown during comparison */
258 heap->flags |= SPL_HEAP_CORRUPTED;
259 }
260
261 heap->elements[i] = elem;
262
263 }
264 /* }}} */
265
spl_ptr_heap_top(spl_ptr_heap * heap)266 static spl_ptr_heap_element spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */
267 if (heap->count == 0) {
268 return NULL;
269 }
270
271 return heap->elements[0];
272 }
273 /* }}} */
274
spl_ptr_heap_delete_top(spl_ptr_heap * heap,void * cmp_userdata TSRMLS_DC)275 static spl_ptr_heap_element spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *cmp_userdata TSRMLS_DC) { /* {{{ */
276 int i, j;
277 const int limit = (heap->count-1)/2;
278 spl_ptr_heap_element top;
279 spl_ptr_heap_element bottom;
280
281 if (heap->count == 0) {
282 return NULL;
283 }
284
285 top = heap->elements[0];
286 bottom = heap->elements[--heap->count];
287
288 for( i = 0; i < limit; i = j)
289 {
290 /* Find smaller child */
291 j = i*2+1;
292 if(j != heap->count && heap->cmp(heap->elements[j+1], heap->elements[j], cmp_userdata TSRMLS_CC) > 0) {
293 j++; /* next child is bigger */
294 }
295
296 /* swap elements between two levels */
297 if(heap->cmp(bottom, heap->elements[j], cmp_userdata TSRMLS_CC) < 0) {
298 heap->elements[i] = heap->elements[j];
299 } else {
300 break;
301 }
302 }
303
304 if (EG(exception)) {
305 /* exception thrown during comparison */
306 heap->flags |= SPL_HEAP_CORRUPTED;
307 }
308
309 heap->elements[i] = bottom;
310 heap->dtor(top TSRMLS_CC);
311 return top;
312 }
313 /* }}} */
314
spl_ptr_heap_clone(spl_ptr_heap * from TSRMLS_DC)315 static spl_ptr_heap *spl_ptr_heap_clone(spl_ptr_heap *from TSRMLS_DC) { /* {{{ */
316 int i;
317
318 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
319
320 heap->dtor = from->dtor;
321 heap->ctor = from->ctor;
322 heap->cmp = from->cmp;
323 heap->max_size = from->max_size;
324 heap->count = from->count;
325 heap->flags = from->flags;
326
327 heap->elements = safe_emalloc(sizeof(spl_ptr_heap_element),from->max_size,0);
328 memcpy(heap->elements, from->elements, sizeof(spl_ptr_heap_element)*from->max_size);
329
330 for (i=0; i < heap->count; ++i) {
331 heap->ctor(heap->elements[i] TSRMLS_CC);
332 }
333
334 return heap;
335 }
336 /* }}} */
337
spl_ptr_heap_destroy(spl_ptr_heap * heap TSRMLS_DC)338 static void spl_ptr_heap_destroy(spl_ptr_heap *heap TSRMLS_DC) { /* {{{ */
339 int i;
340
341 for (i=0; i < heap->count; ++i) {
342 heap->dtor(heap->elements[i] TSRMLS_CC);
343 }
344
345 efree(heap->elements);
346 efree(heap);
347 }
348 /* }}} */
349
spl_ptr_heap_count(spl_ptr_heap * heap)350 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */
351 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
spl_heap_object_free_storage(void * object TSRMLS_DC)358 static void spl_heap_object_free_storage(void *object TSRMLS_DC) /* {{{ */
359 {
360 int i;
361 spl_heap_object *intern = (spl_heap_object *)object;
362
363 zend_object_std_dtor(&intern->std TSRMLS_CC);
364
365 for (i = 0; i < intern->heap->count; ++i) {
366 if (intern->heap->elements[i]) {
367 zval_ptr_dtor((zval **)&intern->heap->elements[i]);
368 }
369 }
370
371 spl_ptr_heap_destroy(intern->heap TSRMLS_CC);
372
373 zval_ptr_dtor(&intern->retval);
374
375 if (intern->debug_info != NULL) {
376 zend_hash_destroy(intern->debug_info);
377 efree(intern->debug_info);
378 }
379
380 efree(object);
381 }
382 /* }}} */
383
spl_heap_object_new_ex(zend_class_entry * class_type,spl_heap_object ** obj,zval * orig,int clone_orig TSRMLS_DC)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 {
386 zend_object_value retval;
387 spl_heap_object *intern;
388 zval *tmp;
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 zend_hash_copy(intern->std.properties, &class_type->default_properties, (copy_ctor_func_t) zval_property_ctor, (void *) &tmp, sizeof(zval *));
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
spl_heap_object_new(zend_class_entry * class_type TSRMLS_DC)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
spl_heap_object_clone(zval * zobject TSRMLS_DC)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
spl_heap_object_count_elements(zval * object,long * count TSRMLS_DC)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
spl_heap_object_get_debug_info_helper(zend_class_entry * ce,zval * obj,int * is_temp TSRMLS_DC)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->debug_info == NULL) {
533 ALLOC_HASHTABLE(intern->debug_info);
534 ZEND_INIT_SYMTABLE_EX(intern->debug_info, zend_hash_num_elements(intern->std.properties) + 1, 0);
535 }
536
537 if (intern->debug_info->nApplyCount == 0) {
538 INIT_PZVAL(&zrv);
539 Z_ARRVAL(zrv) = intern->debug_info;
540
541 zend_hash_copy(intern->debug_info, intern->std.properties, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
542
543 pnstr = spl_gen_private_prop_name(ce, "flags", sizeof("flags")-1, &pnlen TSRMLS_CC);
544 add_assoc_long_ex(&zrv, pnstr, pnlen+1, intern->flags);
545 efree(pnstr);
546
547 pnstr = spl_gen_private_prop_name(ce, "isCorrupted", sizeof("isCorrupted")-1, &pnlen TSRMLS_CC);
548 add_assoc_bool_ex(&zrv, pnstr, pnlen+1, intern->heap->flags&SPL_HEAP_CORRUPTED);
549 efree(pnstr);
550
551 ALLOC_INIT_ZVAL(heap_array);
552 array_init(heap_array);
553
554 for (i = 0; i < intern->heap->count; ++i) {
555 add_index_zval(heap_array, i, (zval *)intern->heap->elements[i]);
556 Z_ADDREF_P(intern->heap->elements[i]);
557 }
558
559 pnstr = spl_gen_private_prop_name(ce, "heap", sizeof("heap")-1, &pnlen TSRMLS_CC);
560 add_assoc_zval_ex(&zrv, pnstr, pnlen+1, heap_array);
561 efree(pnstr);
562 }
563
564 return intern->debug_info;
565 }
566 /* }}} */
567
spl_heap_object_get_debug_info(zval * obj,int * is_temp TSRMLS_DC)568 static HashTable* spl_heap_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{ */
569 {
570 return spl_heap_object_get_debug_info_helper(spl_ce_SplHeap, obj, is_temp TSRMLS_CC);
571 }
572 /* }}} */
573
spl_pqueue_object_get_debug_info(zval * obj,int * is_temp TSRMLS_DC)574 static HashTable* spl_pqueue_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{ */
575 {
576 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. */
SPL_METHOD(SplHeap,count)582 SPL_METHOD(SplHeap, count)
583 {
584 long count;
585 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
586
587 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
588 return;
589 }
590
591 count = spl_ptr_heap_count(intern->heap);
592 RETURN_LONG(count);
593 }
594 /* }}} */
595
596 /* {{{ proto int SplHeap::isEmpty() U
597 Return true if the heap is empty. */
SPL_METHOD(SplHeap,isEmpty)598 SPL_METHOD(SplHeap, isEmpty)
599 {
600 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
601
602 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
603 return;
604 }
605
606 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 */
SPL_METHOD(SplHeap,insert)612 SPL_METHOD(SplHeap, insert)
613 {
614 zval *value;
615 spl_heap_object *intern;
616
617 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) == FAILURE) {
618 return;
619 }
620
621 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
622
623 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
624 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
625 return;
626 }
627
628 SEPARATE_ARG_IF_REF(value);
629
630 spl_ptr_heap_insert(intern->heap, value, getThis() TSRMLS_CC);
631
632 RETURN_TRUE;
633 }
634 /* }}} */
635
636 /* {{{ proto mixed SplHeap::extract() U
637 extract the element out of the top of the heap */
SPL_METHOD(SplHeap,extract)638 SPL_METHOD(SplHeap, extract)
639 {
640 zval *value;
641 spl_heap_object *intern;
642
643 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
644 return;
645 }
646
647 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
648
649 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
650 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
651 return;
652 }
653
654 value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
655
656 if (!value) {
657 zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
658 return;
659 }
660
661 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 */
SPL_METHOD(SplPriorityQueue,insert)667 SPL_METHOD(SplPriorityQueue, insert)
668 {
669 zval *data, *priority, *elem;
670 spl_heap_object *intern;
671
672 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &data, &priority) == FAILURE) {
673 return;
674 }
675
676 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
677
678 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
679 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
680 return;
681 }
682
683 SEPARATE_ARG_IF_REF(data);
684 SEPARATE_ARG_IF_REF(priority);
685
686 ALLOC_INIT_ZVAL(elem);
687
688 array_init(elem);
689 add_assoc_zval_ex(elem, "data", sizeof("data"), data);
690 add_assoc_zval_ex(elem, "priority", sizeof("priority"), priority);
691
692 spl_ptr_heap_insert(intern->heap, elem, getThis() TSRMLS_CC);
693
694 RETURN_TRUE;
695 }
696 /* }}} */
697
698 /* {{{ proto mixed SplPriorityQueue::extract() U
699 extract the element out of the top of the priority queue */
SPL_METHOD(SplPriorityQueue,extract)700 SPL_METHOD(SplPriorityQueue, extract)
701 {
702 zval *value, *value_out, **value_out_pp;
703 spl_heap_object *intern;
704
705 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
706 return;
707 }
708
709 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
710
711 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
712 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
713 return;
714 }
715
716 value = (zval *)spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
717
718 if (!value) {
719 zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0 TSRMLS_CC);
720 return;
721 }
722
723 value_out_pp = spl_pqueue_extract_helper(&value, intern->flags);
724
725
726 if (!value_out_pp) {
727 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
728 zval_ptr_dtor(&value);
729 return;
730 }
731
732 value_out = *value_out_pp;
733
734 Z_ADDREF_P(value_out);
735 zval_ptr_dtor(&value);
736
737 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 */
SPL_METHOD(SplPriorityQueue,top)743 SPL_METHOD(SplPriorityQueue, top)
744 {
745 zval *value, **value_out;
746 spl_heap_object *intern;
747
748 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
749 return;
750 }
751
752 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
753
754 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
755 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
756 return;
757 }
758
759 value = (zval *)spl_ptr_heap_top(intern->heap);
760
761 if (!value) {
762 zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
763 return;
764 }
765
766 value_out = spl_pqueue_extract_helper(&value, intern->flags);
767
768 if (!value_out) {
769 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
770 return;
771 }
772
773 RETURN_ZVAL(*value_out, 1, 0);
774 }
775 /* }}} */
776
777 /* {{{ proto int SplPriorityQueue::setIteratorMode($flags) U
778 Set the flags of extraction*/
SPL_METHOD(SplPriorityQueue,setExtractFlags)779 SPL_METHOD(SplPriorityQueue, setExtractFlags)
780 {
781 long value;
782 spl_heap_object *intern;
783
784 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &value) == FAILURE) {
785 return;
786 }
787
788 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
789
790 intern->flags = value & SPL_PQUEUE_EXTR_MASK;
791
792 RETURN_LONG(intern->flags);
793 }
794 /* }}} */
795
796 /* {{{ proto int SplHeap::recoverFromCorruption() U
797 Recover from a corrupted state*/
SPL_METHOD(SplHeap,recoverFromCorruption)798 SPL_METHOD(SplHeap, recoverFromCorruption)
799 {
800 spl_heap_object *intern;
801
802 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
803 return;
804 }
805
806 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
807
808 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED;
809
810 RETURN_TRUE;
811 }
812 /* }}} */
813
814 /* {{{ proto bool SplPriorityQueue::compare(mixed $a, mixed $b) U
815 compare the priorities */
SPL_METHOD(SplPriorityQueue,compare)816 SPL_METHOD(SplPriorityQueue, compare)
817 {
818 zval *a, *b;
819
820 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
821 return;
822 }
823
824 RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
825 }
826 /* }}} */
827
828 /* {{{ proto mixed SplHeap::top() U
829 Peek at the top element of the heap */
SPL_METHOD(SplHeap,top)830 SPL_METHOD(SplHeap, top)
831 {
832 zval *value;
833 spl_heap_object *intern;
834
835 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "") == FAILURE) {
836 return;
837 }
838
839 intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
840
841 if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
842 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
843 return;
844 }
845
846 value = (zval *)spl_ptr_heap_top(intern->heap);
847
848 if (!value) {
849 zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0 TSRMLS_CC);
850 return;
851 }
852
853 RETURN_ZVAL(value, 1, 0);
854 }
855 /* }}} */
856
857 /* {{{ proto bool SplMinHeap::compare(mixed $a, mixed $b) U
858 compare the values */
SPL_METHOD(SplMinHeap,compare)859 SPL_METHOD(SplMinHeap, compare)
860 {
861 zval *a, *b;
862
863 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
864 return;
865 }
866
867 RETURN_LONG(spl_ptr_heap_zval_min_cmp(a, b, NULL TSRMLS_CC));
868 }
869 /* }}} */
870
871 /* {{{ proto bool SplMaxHeap::compare(mixed $a, mixed $b) U
872 compare the values */
SPL_METHOD(SplMaxHeap,compare)873 SPL_METHOD(SplMaxHeap, compare)
874 {
875 zval *a, *b;
876
877 if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &a, &b) == FAILURE) {
878 return;
879 }
880
881 RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL TSRMLS_CC));
882 }
883 /* }}} */
884
spl_heap_it_dtor(zend_object_iterator * iter TSRMLS_DC)885 static void spl_heap_it_dtor(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
886 {
887 spl_heap_it *iterator = (spl_heap_it *)iter;
888
889 zend_user_it_invalidate_current(iter TSRMLS_CC);
890 zval_ptr_dtor((zval**)&iterator->intern.it.data);
891
892 efree(iterator);
893 }
894 /* }}} */
895
spl_heap_it_rewind(zend_object_iterator * iter TSRMLS_DC)896 static void spl_heap_it_rewind(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
897 {
898 /* do nothing, the iterator always points to the top element */
899 }
900 /* }}} */
901
spl_heap_it_valid(zend_object_iterator * iter TSRMLS_DC)902 static int spl_heap_it_valid(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
903 {
904 spl_heap_it *iterator = (spl_heap_it *)iter;
905
906 return (iterator->object->heap->count != 0 ? SUCCESS : FAILURE);
907 }
908 /* }}} */
909
spl_heap_it_get_current_data(zend_object_iterator * iter,zval *** data TSRMLS_DC)910 static void spl_heap_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
911 {
912 spl_heap_it *iterator = (spl_heap_it *)iter;
913 zval **element = (zval **)&iterator->object->heap->elements[0];
914
915 if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
916 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
917 return;
918 }
919
920 if (iterator->object->heap->count == 0 || !*element) {
921 *data = NULL;
922 } else {
923 *data = element;
924 }
925 }
926 /* }}} */
927
spl_pqueue_it_get_current_data(zend_object_iterator * iter,zval *** data TSRMLS_DC)928 static void spl_pqueue_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
929 {
930 spl_heap_it *iterator = (spl_heap_it *)iter;
931 zval **element = (zval **)&iterator->object->heap->elements[0];
932
933 if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
934 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
935 return;
936 }
937
938 if (iterator->object->heap->count == 0 || !*element) {
939 *data = NULL;
940 } else {
941 *data = spl_pqueue_extract_helper(element, iterator->object->flags);
942 if (!*data) {
943 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
944 }
945 }
946 }
947 /* }}} */
948
spl_heap_it_get_current_key(zend_object_iterator * iter,char ** str_key,uint * str_key_len,ulong * int_key TSRMLS_DC)949 static int spl_heap_it_get_current_key(zend_object_iterator *iter, char **str_key, uint *str_key_len, ulong *int_key TSRMLS_DC) /* {{{ */
950 {
951 spl_heap_it *iterator = (spl_heap_it *)iter;
952
953 *int_key = (ulong) iterator->object->heap->count - 1;
954 return HASH_KEY_IS_LONG;
955 }
956 /* }}} */
957
spl_heap_it_move_forward(zend_object_iterator * iter TSRMLS_DC)958 static void spl_heap_it_move_forward(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
959 {
960 zval *object = (zval*)((zend_user_iterator *)iter)->it.data;
961 spl_heap_it *iterator = (spl_heap_it *)iter;
962 spl_ptr_heap_element elem;
963
964 if (iterator->object->heap->flags & SPL_HEAP_CORRUPTED) {
965 zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0 TSRMLS_CC);
966 return;
967 }
968
969 elem = spl_ptr_heap_delete_top(iterator->object->heap, object TSRMLS_CC);
970
971 if (elem != NULL) {
972 zval_ptr_dtor((zval **)&elem);
973 }
974
975 zend_user_it_invalidate_current(iter TSRMLS_CC);
976 }
977 /* }}} */
978
979 /* {{{ proto int SplHeap::key() U
980 Return current array key */
SPL_METHOD(SplHeap,key)981 SPL_METHOD(SplHeap, key)
982 {
983 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
984
985 if (zend_parse_parameters_none() == FAILURE) {
986 return;
987 }
988
989 RETURN_LONG(intern->heap->count - 1);
990 }
991 /* }}} */
992
993 /* {{{ proto void SplHeap::next() U
994 Move to next entry */
SPL_METHOD(SplHeap,next)995 SPL_METHOD(SplHeap, next)
996 {
997 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
998 spl_ptr_heap_element elem = spl_ptr_heap_delete_top(intern->heap, getThis() TSRMLS_CC);
999
1000 if (zend_parse_parameters_none() == FAILURE) {
1001 return;
1002 }
1003
1004 if (elem != NULL) {
1005 zval_ptr_dtor((zval **)&elem);
1006 }
1007 }
1008 /* }}} */
1009
1010 /* {{{ proto bool SplHeap::valid() U
1011 Check whether the datastructure contains more entries */
SPL_METHOD(SplHeap,valid)1012 SPL_METHOD(SplHeap, valid)
1013 {
1014 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1015
1016 if (zend_parse_parameters_none() == FAILURE) {
1017 return;
1018 }
1019
1020 RETURN_BOOL(intern->heap->count != 0);
1021 }
1022 /* }}} */
1023
1024 /* {{{ proto void SplHeap::rewind() U
1025 Rewind the datastructure back to the start */
SPL_METHOD(SplHeap,rewind)1026 SPL_METHOD(SplHeap, rewind)
1027 {
1028 if (zend_parse_parameters_none() == FAILURE) {
1029 return;
1030 }
1031 /* do nothing, the iterator always points to the top element */
1032 }
1033 /* }}} */
1034
1035 /* {{{ proto mixed|NULL SplHeap::current() U
1036 Return current datastructure entry */
SPL_METHOD(SplHeap,current)1037 SPL_METHOD(SplHeap, current)
1038 {
1039 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1040 zval *element = (zval *)intern->heap->elements[0];
1041
1042 if (zend_parse_parameters_none() == FAILURE) {
1043 return;
1044 }
1045
1046 if (!intern->heap->count || !element) {
1047 RETURN_NULL();
1048 } else {
1049 RETURN_ZVAL(element, 1, 0);
1050 }
1051 }
1052 /* }}} */
1053
1054 /* {{{ proto mixed|NULL SplPriorityQueue::current() U
1055 Return current datastructure entry */
SPL_METHOD(SplPriorityQueue,current)1056 SPL_METHOD(SplPriorityQueue, current)
1057 {
1058 spl_heap_object *intern = (spl_heap_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1059 zval **element = (zval **)&intern->heap->elements[0];
1060
1061 if (zend_parse_parameters_none() == FAILURE) {
1062 return;
1063 }
1064
1065 if (!intern->heap->count || !*element) {
1066 RETURN_NULL();
1067 } else {
1068 zval **data = spl_pqueue_extract_helper(element, intern->flags);
1069
1070 if (!data) {
1071 zend_error(E_RECOVERABLE_ERROR, "Unable to extract from the PriorityQueue node");
1072 RETURN_NULL();
1073 }
1074
1075 RETURN_ZVAL(*data, 1, 0);
1076 }
1077 }
1078 /* }}} */
1079
1080 /* iterator handler table */
1081 zend_object_iterator_funcs spl_heap_it_funcs = {
1082 spl_heap_it_dtor,
1083 spl_heap_it_valid,
1084 spl_heap_it_get_current_data,
1085 spl_heap_it_get_current_key,
1086 spl_heap_it_move_forward,
1087 spl_heap_it_rewind
1088 };
1089
1090 zend_object_iterator_funcs spl_pqueue_it_funcs = {
1091 spl_heap_it_dtor,
1092 spl_heap_it_valid,
1093 spl_pqueue_it_get_current_data,
1094 spl_heap_it_get_current_key,
1095 spl_heap_it_move_forward,
1096 spl_heap_it_rewind
1097 };
1098
spl_heap_get_iterator(zend_class_entry * ce,zval * object,int by_ref TSRMLS_DC)1099 zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
1100 {
1101 spl_heap_it *iterator;
1102 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
1103
1104 if (by_ref) {
1105 zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1106 return NULL;
1107 }
1108
1109 Z_ADDREF_P(object);
1110
1111 iterator = emalloc(sizeof(spl_heap_it));
1112 iterator->intern.it.data = (void*)object;
1113 iterator->intern.it.funcs = &spl_heap_it_funcs;
1114 iterator->intern.ce = ce;
1115 iterator->intern.value = NULL;
1116 iterator->flags = heap_object->flags;
1117 iterator->object = heap_object;
1118
1119 return (zend_object_iterator*)iterator;
1120 }
1121 /* }}} */
1122
spl_pqueue_get_iterator(zend_class_entry * ce,zval * object,int by_ref TSRMLS_DC)1123 zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
1124 {
1125 spl_heap_it *iterator;
1126 spl_heap_object *heap_object = (spl_heap_object*)zend_object_store_get_object(object TSRMLS_CC);
1127
1128 if (by_ref) {
1129 zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1130 return NULL;
1131 }
1132
1133 Z_ADDREF_P(object);
1134
1135 iterator = emalloc(sizeof(spl_heap_it));
1136 iterator->intern.it.data = (void*)object;
1137 iterator->intern.it.funcs = &spl_pqueue_it_funcs;
1138 iterator->intern.ce = ce;
1139 iterator->intern.value = NULL;
1140 iterator->flags = heap_object->flags;
1141 iterator->object = heap_object;
1142
1143 return (zend_object_iterator*)iterator;
1144 }
1145 /* }}} */
1146
1147 ZEND_BEGIN_ARG_INFO(arginfo_heap_insert, 0)
1148 ZEND_ARG_INFO(0, value)
1149 ZEND_END_ARG_INFO()
1150
1151 ZEND_BEGIN_ARG_INFO(arginfo_heap_compare, 0)
1152 ZEND_ARG_INFO(0, a)
1153 ZEND_ARG_INFO(0, b)
1154 ZEND_END_ARG_INFO()
1155
1156 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_insert, 0)
1157 ZEND_ARG_INFO(0, value)
1158 ZEND_ARG_INFO(0, priority)
1159 ZEND_END_ARG_INFO()
1160
1161 ZEND_BEGIN_ARG_INFO(arginfo_pqueue_setflags, 0)
1162 ZEND_ARG_INFO(0, flags)
1163 ZEND_END_ARG_INFO()
1164
1165 ZEND_BEGIN_ARG_INFO(arginfo_splheap_void, 0)
1166 ZEND_END_ARG_INFO()
1167
1168 static const zend_function_entry spl_funcs_SplMinHeap[] = {
1169 SPL_ME(SplMinHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1170 {NULL, NULL, NULL}
1171 };
1172 static const zend_function_entry spl_funcs_SplMaxHeap[] = {
1173 SPL_ME(SplMaxHeap, compare, arginfo_heap_compare, ZEND_ACC_PROTECTED)
1174 {NULL, NULL, NULL}
1175 };
1176
1177 static const zend_function_entry spl_funcs_SplPriorityQueue[] = {
1178 SPL_ME(SplPriorityQueue, compare, arginfo_heap_compare, ZEND_ACC_PUBLIC)
1179 SPL_ME(SplPriorityQueue, insert, arginfo_pqueue_insert, ZEND_ACC_PUBLIC)
1180 SPL_ME(SplPriorityQueue, setExtractFlags, arginfo_pqueue_setflags, ZEND_ACC_PUBLIC)
1181 SPL_ME(SplPriorityQueue, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1182 SPL_ME(SplPriorityQueue, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1183 SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1184 SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1185 SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1186 SPL_ME(SplPriorityQueue, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1187 SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1188 SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1189 SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1190 SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1191 {NULL, NULL, NULL}
1192 };
1193
1194 static const zend_function_entry spl_funcs_SplHeap[] = {
1195 SPL_ME(SplHeap, extract, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1196 SPL_ME(SplHeap, insert, arginfo_heap_insert, ZEND_ACC_PUBLIC)
1197 SPL_ME(SplHeap, top, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1198 SPL_ME(SplHeap, count, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1199 SPL_ME(SplHeap, isEmpty, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1200 SPL_ME(SplHeap, rewind, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1201 SPL_ME(SplHeap, current, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1202 SPL_ME(SplHeap, key, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1203 SPL_ME(SplHeap, next, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1204 SPL_ME(SplHeap, valid, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1205 SPL_ME(SplHeap, recoverFromCorruption, arginfo_splheap_void, ZEND_ACC_PUBLIC)
1206 ZEND_FENTRY(compare, NULL, NULL, ZEND_ACC_PROTECTED|ZEND_ACC_ABSTRACT)
1207 {NULL, NULL, NULL}
1208 };
1209 /* }}} */
1210
PHP_MINIT_FUNCTION(spl_heap)1211 PHP_MINIT_FUNCTION(spl_heap) /* {{{ */
1212 {
1213 REGISTER_SPL_STD_CLASS_EX(SplHeap, spl_heap_object_new, spl_funcs_SplHeap);
1214 memcpy(&spl_handler_SplHeap, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1215
1216 spl_handler_SplHeap.clone_obj = spl_heap_object_clone;
1217 spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
1218 spl_handler_SplHeap.get_debug_info = spl_heap_object_get_debug_info;
1219
1220 REGISTER_SPL_IMPLEMENTS(SplHeap, Iterator);
1221 REGISTER_SPL_IMPLEMENTS(SplHeap, Countable);
1222
1223 spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
1224
1225 REGISTER_SPL_SUB_CLASS_EX(SplMinHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMinHeap);
1226 REGISTER_SPL_SUB_CLASS_EX(SplMaxHeap, SplHeap, spl_heap_object_new, spl_funcs_SplMaxHeap);
1227
1228 spl_ce_SplMaxHeap->get_iterator = spl_heap_get_iterator;
1229 spl_ce_SplMinHeap->get_iterator = spl_heap_get_iterator;
1230
1231 REGISTER_SPL_STD_CLASS_EX(SplPriorityQueue, spl_heap_object_new, spl_funcs_SplPriorityQueue);
1232 memcpy(&spl_handler_SplPriorityQueue, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1233
1234 spl_handler_SplPriorityQueue.clone_obj = spl_heap_object_clone;
1235 spl_handler_SplPriorityQueue.count_elements = spl_heap_object_count_elements;
1236 spl_handler_SplPriorityQueue.get_debug_info = spl_pqueue_object_get_debug_info;
1237
1238 REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Iterator);
1239 REGISTER_SPL_IMPLEMENTS(SplPriorityQueue, Countable);
1240
1241 spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
1242
1243 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_BOTH", SPL_PQUEUE_EXTR_BOTH);
1244 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_PRIORITY", SPL_PQUEUE_EXTR_PRIORITY);
1245 REGISTER_SPL_CLASS_CONST_LONG(SplPriorityQueue, "EXTR_DATA", SPL_PQUEUE_EXTR_DATA);
1246
1247 return SUCCESS;
1248 }
1249 /* }}} */
1250
1251 /*
1252 * Local variables:
1253 * tab-width: 4
1254 * c-basic-offset: 4
1255 * End:
1256 * vim600: fdm=marker
1257 * vim: noet sw=4 ts=4
1258 */
1259
1260
