Lines Matching refs:heap
71 spl_ptr_heap *heap; member
225 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_init() local
227 heap->dtor = dtor; in spl_ptr_heap_init()
228 heap->ctor = ctor; in spl_ptr_heap_init()
229 heap->cmp = cmp; in spl_ptr_heap_init()
230 heap->elements = ecalloc(PTR_HEAP_BLOCK_SIZE, sizeof(zval)); in spl_ptr_heap_init()
231 heap->max_size = PTR_HEAP_BLOCK_SIZE; in spl_ptr_heap_init()
232 heap->count = 0; in spl_ptr_heap_init()
233 heap->flags = 0; in spl_ptr_heap_init()
235 return heap; in spl_ptr_heap_init()
239 static void spl_ptr_heap_insert(spl_ptr_heap *heap, zval *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_insert() argument
242 if (heap->count+1 > heap->max_size) { in spl_ptr_heap_insert()
244 heap->elements = erealloc(heap->elements, heap->max_size * 2 * sizeof(zval)); in spl_ptr_heap_insert()
245 memset(heap->elements + heap->max_size, 0, heap->max_size * sizeof(zval)); in spl_ptr_heap_insert()
246 heap->max_size *= 2; in spl_ptr_heap_insert()
250 …for (i = heap->count; i > 0 && heap->cmp(&heap->elements[(i-1)/2], elem, cmp_userdata) < 0; i = (i… in spl_ptr_heap_insert()
251 heap->elements[i] = heap->elements[(i-1)/2]; in spl_ptr_heap_insert()
253 heap->count++; in spl_ptr_heap_insert()
257 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_insert()
260 ZVAL_COPY_VALUE(&heap->elements[i], elem); in spl_ptr_heap_insert()
264 static zval *spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_top() argument
265 if (heap->count == 0) { in spl_ptr_heap_top()
269 return Z_ISUNDEF(heap->elements[0])? NULL : &heap->elements[0]; in spl_ptr_heap_top()
273 static void spl_ptr_heap_delete_top(spl_ptr_heap *heap, zval *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_delete_top() argument
275 const int limit = (heap->count-1)/2; in spl_ptr_heap_delete_top()
278 if (heap->count == 0) { in spl_ptr_heap_delete_top()
283 ZVAL_COPY_VALUE(elem, &heap->elements[0]); in spl_ptr_heap_delete_top()
284 bottom = &heap->elements[--heap->count]; in spl_ptr_heap_delete_top()
289 if(j != heap->count && heap->cmp(&heap->elements[j+1], &heap->elements[j], cmp_userdata) > 0) { in spl_ptr_heap_delete_top()
294 if(heap->cmp(bottom, &heap->elements[j], cmp_userdata) < 0) { in spl_ptr_heap_delete_top()
295 heap->elements[i] = heap->elements[j]; in spl_ptr_heap_delete_top()
303 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_delete_top()
306 ZVAL_COPY_VALUE(&heap->elements[i], bottom); in spl_ptr_heap_delete_top()
313 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_clone() local
315 heap->dtor = from->dtor; in spl_ptr_heap_clone()
316 heap->ctor = from->ctor; in spl_ptr_heap_clone()
317 heap->cmp = from->cmp; in spl_ptr_heap_clone()
318 heap->max_size = from->max_size; in spl_ptr_heap_clone()
319 heap->count = from->count; in spl_ptr_heap_clone()
320 heap->flags = from->flags; in spl_ptr_heap_clone()
322 heap->elements = safe_emalloc(sizeof(zval), from->max_size, 0); in spl_ptr_heap_clone()
323 memcpy(heap->elements, from->elements, sizeof(zval)*from->max_size); in spl_ptr_heap_clone()
325 for (i=0; i < heap->count; ++i) { in spl_ptr_heap_clone()
326 heap->ctor(&heap->elements[i]); in spl_ptr_heap_clone()
329 return heap; in spl_ptr_heap_clone()
333 static void spl_ptr_heap_destroy(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_destroy() argument
336 for (i=0; i < heap->count; ++i) { in spl_ptr_heap_destroy()
337 heap->dtor(&heap->elements[i]); in spl_ptr_heap_destroy()
340 efree(heap->elements); in spl_ptr_heap_destroy()
341 efree(heap); in spl_ptr_heap_destroy()
345 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_count() argument
346 return heap->count; in spl_ptr_heap_count()
358 spl_ptr_heap_destroy(intern->heap); in spl_heap_object_free_storage()
381 intern->heap = spl_ptr_heap_clone(other->heap); in spl_heap_object_new_ex()
383 intern->heap = other->heap; in spl_heap_object_new_ex()
388 …intern->heap = spl_ptr_heap_init(spl_ptr_heap_zval_max_cmp, spl_ptr_heap_zval_ctor, spl_ptr_heap_z… in spl_heap_object_new_ex()
395 intern->heap->cmp = spl_ptr_pqueue_zval_cmp; in spl_heap_object_new_ex()
402 intern->heap->cmp = spl_ptr_heap_zval_min_cmp; in spl_heap_object_new_ex()
407 intern->heap->cmp = spl_ptr_heap_zval_max_cmp; in spl_heap_object_new_ex()
474 *count = spl_ptr_heap_count(intern->heap); in spl_heap_object_count_elements()
503 ZVAL_BOOL(&tmp, intern->heap->flags&SPL_HEAP_CORRUPTED); in spl_heap_object_get_debug_info_helper()
509 for (i = 0; i < intern->heap->count; ++i) { in spl_heap_object_get_debug_info_helper()
510 add_index_zval(&heap_array, i, &intern->heap->elements[i]); in spl_heap_object_get_debug_info_helper()
511 if (Z_REFCOUNTED(intern->heap->elements[i])) { in spl_heap_object_get_debug_info_helper()
512 Z_ADDREF(intern->heap->elements[i]); in spl_heap_object_get_debug_info_helper()
527 *gc_data = intern->heap->elements; in spl_heap_object_get_gc()
528 *gc_data_count = intern->heap->count; in spl_heap_object_get_gc()
557 count = spl_ptr_heap_count(intern->heap); in SPL_METHOD()
572 RETURN_BOOL(spl_ptr_heap_count(intern->heap) == 0); in SPL_METHOD()
589 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in SPL_METHOD()
595 spl_ptr_heap_insert(intern->heap, value, getThis()); in SPL_METHOD()
613 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in SPL_METHOD()
618 spl_ptr_heap_delete_top(intern->heap, return_value, getThis()); in SPL_METHOD()
640 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in SPL_METHOD()
652 spl_ptr_heap_insert(intern->heap, &elem, getThis()); in SPL_METHOD()
671 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in SPL_METHOD()
676 spl_ptr_heap_delete_top(intern->heap, &value, getThis()); in SPL_METHOD()
710 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in SPL_METHOD()
715 value = spl_ptr_heap_top(intern->heap); in SPL_METHOD()
782 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED; in SPL_METHOD()
800 RETURN_BOOL(intern->heap->flags & SPL_HEAP_CORRUPTED); in SPL_METHOD()
831 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in SPL_METHOD()
836 value = spl_ptr_heap_top(intern->heap); in SPL_METHOD()
893 return ((Z_SPLHEAP_P(&iter->data))->heap->count != 0 ? SUCCESS : FAILURE); in spl_heap_it_valid()
900 zval *element = &object->heap->elements[0]; in spl_heap_it_get_current_data()
902 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_get_current_data()
907 if (object->heap->count == 0 || Z_ISUNDEF_P(element)) { in spl_heap_it_get_current_data()
918 zval *element = &object->heap->elements[0]; in spl_pqueue_it_get_current_data()
920 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_pqueue_it_get_current_data()
925 if (object->heap->count == 0 || Z_ISUNDEF_P(element)) { in spl_pqueue_it_get_current_data()
941 ZVAL_LONG(key, object->heap->count - 1); in spl_heap_it_get_current_key()
950 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_move_forward()
955 spl_ptr_heap_delete_top(object->heap, &elem, &iter->data); in spl_heap_it_move_forward()
973 RETURN_LONG(intern->heap->count - 1); in SPL_METHOD()
983 spl_ptr_heap_delete_top(intern->heap, &elem, getThis()); in SPL_METHOD()
1003 RETURN_BOOL(intern->heap->count != 0); in SPL_METHOD()
1023 zval *element = &intern->heap->elements[0]; in SPL_METHOD()
1029 if (!intern->heap->count || Z_ISUNDEF_P(element)) { in SPL_METHOD()
1043 zval *element = &intern->heap->elements[0]; in SPL_METHOD()
1049 if (!intern->heap->count || Z_ISUNDEF_P(element)) { in SPL_METHOD()