Lines Matching refs:heap
65 spl_ptr_heap *heap; member
84 static zend_always_inline void *spl_heap_elem(spl_ptr_heap *heap, size_t i) { in spl_heap_elem() argument
85 return (void *) ((char *) heap->elements + heap->elem_size * i); in spl_heap_elem()
88 static zend_always_inline void spl_heap_elem_copy(spl_ptr_heap *heap, void *to, void *from) { in spl_heap_elem_copy() argument
93 if (heap->elem_size == sizeof(spl_pqueue_elem)) { in spl_heap_elem_copy()
96 ZEND_ASSERT(heap->elem_size == sizeof(zval)); in spl_heap_elem_copy()
256 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_init() local
258 heap->dtor = dtor; in spl_ptr_heap_init()
259 heap->ctor = ctor; in spl_ptr_heap_init()
260 heap->cmp = cmp; in spl_ptr_heap_init()
261 heap->elements = ecalloc(PTR_HEAP_BLOCK_SIZE, elem_size); in spl_ptr_heap_init()
262 heap->max_size = PTR_HEAP_BLOCK_SIZE; in spl_ptr_heap_init()
263 heap->count = 0; in spl_ptr_heap_init()
264 heap->flags = 0; in spl_ptr_heap_init()
265 heap->elem_size = elem_size; in spl_ptr_heap_init()
267 return heap; in spl_ptr_heap_init()
271 static void spl_ptr_heap_insert(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_insert() argument
274 if (heap->count+1 > heap->max_size) { in spl_ptr_heap_insert()
275 size_t alloc_size = heap->max_size * heap->elem_size; in spl_ptr_heap_insert()
277 heap->elements = safe_erealloc(heap->elements, 2, alloc_size, 0); in spl_ptr_heap_insert()
278 memset((char *) heap->elements + alloc_size, 0, alloc_size); in spl_ptr_heap_insert()
279 heap->max_size *= 2; in spl_ptr_heap_insert()
282 heap->flags |= SPL_HEAP_WRITE_LOCKED; in spl_ptr_heap_insert()
285 …for (i = heap->count; i > 0 && heap->cmp(spl_heap_elem(heap, (i-1)/2), elem, cmp_userdata) < 0; i … in spl_ptr_heap_insert()
286 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, (i-1)/2)); in spl_ptr_heap_insert()
288 heap->count++; in spl_ptr_heap_insert()
290 heap->flags &= ~SPL_HEAP_WRITE_LOCKED; in spl_ptr_heap_insert()
294 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_insert()
297 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), elem); in spl_ptr_heap_insert()
301 static void *spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_top() argument
302 if (heap->count == 0) { in spl_ptr_heap_top()
306 return heap->elements; in spl_ptr_heap_top()
310 static zend_result spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /*… in spl_ptr_heap_delete_top() argument
312 const int limit = (heap->count-1)/2; in spl_ptr_heap_delete_top()
315 if (heap->count == 0) { in spl_ptr_heap_delete_top()
319 heap->flags |= SPL_HEAP_WRITE_LOCKED; in spl_ptr_heap_delete_top()
322 spl_heap_elem_copy(heap, elem, spl_heap_elem(heap, 0)); in spl_ptr_heap_delete_top()
324 heap->dtor(spl_heap_elem(heap, 0)); in spl_ptr_heap_delete_top()
327 bottom = spl_heap_elem(heap, --heap->count); in spl_ptr_heap_delete_top()
332 …if (j != heap->count && heap->cmp(spl_heap_elem(heap, j+1), spl_heap_elem(heap, j), cmp_userdata) … in spl_ptr_heap_delete_top()
337 if(heap->cmp(bottom, spl_heap_elem(heap, j), cmp_userdata) < 0) { in spl_ptr_heap_delete_top()
338 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, j)); in spl_ptr_heap_delete_top()
344 heap->flags &= ~SPL_HEAP_WRITE_LOCKED; in spl_ptr_heap_delete_top()
348 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_delete_top()
351 void *to = spl_heap_elem(heap, i); in spl_ptr_heap_delete_top()
353 spl_heap_elem_copy(heap, to, bottom); in spl_ptr_heap_delete_top()
362 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_clone() local
364 heap->dtor = from->dtor; in spl_ptr_heap_clone()
365 heap->ctor = from->ctor; in spl_ptr_heap_clone()
366 heap->cmp = from->cmp; in spl_ptr_heap_clone()
367 heap->max_size = from->max_size; in spl_ptr_heap_clone()
368 heap->count = from->count; in spl_ptr_heap_clone()
369 heap->flags = from->flags; in spl_ptr_heap_clone()
370 heap->elem_size = from->elem_size; in spl_ptr_heap_clone()
372 heap->elements = safe_emalloc(from->elem_size, from->max_size, 0); in spl_ptr_heap_clone()
373 memcpy(heap->elements, from->elements, from->elem_size * from->max_size); in spl_ptr_heap_clone()
375 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_clone()
376 heap->ctor(spl_heap_elem(heap, i)); in spl_ptr_heap_clone()
379 return heap; in spl_ptr_heap_clone()
383 static void spl_ptr_heap_destroy(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_destroy() argument
385 if (!heap) { in spl_ptr_heap_destroy()
391 heap->flags |= SPL_HEAP_WRITE_LOCKED; in spl_ptr_heap_destroy()
393 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_destroy()
394 heap->dtor(spl_heap_elem(heap, i)); in spl_ptr_heap_destroy()
397 heap->flags &= ~SPL_HEAP_WRITE_LOCKED; in spl_ptr_heap_destroy()
399 efree(heap->elements); in spl_ptr_heap_destroy()
400 efree(heap); in spl_ptr_heap_destroy()
404 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_count() argument
405 return heap->count; in spl_ptr_heap_count()
415 spl_ptr_heap_destroy(intern->heap); in spl_heap_object_free_storage()
435 intern->heap = spl_ptr_heap_clone(other->heap); in spl_heap_object_new_ex()
437 intern->heap = other->heap; in spl_heap_object_new_ex()
448 …intern->heap = spl_ptr_heap_init(spl_ptr_pqueue_elem_cmp, spl_ptr_heap_pqueue_elem_ctor, spl_ptr_h… in spl_heap_object_new_ex()
455 intern->heap = spl_ptr_heap_init( in spl_heap_object_new_ex()
515 *count = spl_ptr_heap_count(intern->heap); in spl_heap_object_count_elements()
541 ZVAL_BOOL(&tmp, intern->heap->flags&SPL_HEAP_CORRUPTED); in spl_heap_object_get_debug_info()
547 for (i = 0; i < intern->heap->count; ++i) { in spl_heap_object_get_debug_info()
549 spl_pqueue_elem *pq_elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
554 zval *elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
571 *gc_data = (zval *) intern->heap->elements; in spl_heap_object_get_gc()
572 *gc_data_count = intern->heap->count; in spl_heap_object_get_gc()
581 *gc_data = (zval *) intern->heap->elements; in spl_pqueue_object_get_gc()
583 *gc_data_count = 2 * intern->heap->count; in spl_pqueue_object_get_gc()
599 count = spl_ptr_heap_count(intern->heap); in PHP_METHOD()
613 RETURN_BOOL(spl_ptr_heap_count(intern->heap) == 0); in PHP_METHOD()
619 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_consistency_validations()
624 if (write && (intern->heap->flags & SPL_HEAP_WRITE_LOCKED)) { in spl_heap_consistency_validations()
649 spl_ptr_heap_insert(intern->heap, value, ZEND_THIS); in PHP_METHOD()
670 if (spl_ptr_heap_delete_top(intern->heap, return_value, ZEND_THIS) == FAILURE) { in PHP_METHOD()
706 if (intern->heap->count == 0) { /* Specialize empty queue */ in PHP_METHOD()
707 intern->heap->cmp = new_cmp; in PHP_METHOD()
708 } else if (new_cmp != intern->heap->cmp) { /* Despecialize on type conflict. */ in PHP_METHOD()
709 intern->heap->cmp = spl_ptr_pqueue_elem_cmp; in PHP_METHOD()
713 spl_ptr_heap_insert(intern->heap, &elem, ZEND_THIS); in PHP_METHOD()
735 if (spl_ptr_heap_delete_top(intern->heap, &elem, ZEND_THIS) == FAILURE) { in PHP_METHOD()
761 elem = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
821 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED; in PHP_METHOD()
838 RETURN_BOOL(intern->heap->flags & SPL_HEAP_CORRUPTED); in PHP_METHOD()
871 value = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
923 return ((Z_SPLHEAP_P(&iter->data))->heap->count != 0 ? SUCCESS : FAILURE); in spl_heap_it_valid()
935 if (object->heap->count == 0) { in spl_heap_it_get_current_data()
938 return spl_heap_elem(object->heap, 0); in spl_heap_it_get_current_data()
952 if (object->heap->count == 0) { in spl_pqueue_it_get_current_data()
957 spl_pqueue_elem *elem = spl_heap_elem(object->heap, 0); in spl_pqueue_it_get_current_data()
968 ZVAL_LONG(key, object->heap->count - 1); in spl_heap_it_get_current_key()
980 spl_ptr_heap_delete_top(object->heap, NULL, &iter->data); in spl_heap_it_move_forward()
994 RETURN_LONG(intern->heap->count - 1); in PHP_METHOD()
1007 spl_ptr_heap_delete_top(intern->heap, NULL, ZEND_THIS); in PHP_METHOD()
1020 RETURN_BOOL(intern->heap->count != 0); in PHP_METHOD()
1043 if (!intern->heap->count) { in PHP_METHOD()
1046 zval *element = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
1061 if (!intern->heap->count) { in PHP_METHOD()
1064 spl_pqueue_elem *elem = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
