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