Lines Matching refs:heap
64 spl_ptr_heap *heap; member
83 static zend_always_inline void *spl_heap_elem(spl_ptr_heap *heap, size_t i) { in spl_heap_elem() argument
84 return (void *) ((char *) heap->elements + heap->elem_size * i); in spl_heap_elem()
87 static zend_always_inline void spl_heap_elem_copy(spl_ptr_heap *heap, void *to, void *from) { in spl_heap_elem_copy() argument
92 if (heap->elem_size == sizeof(spl_pqueue_elem)) { in spl_heap_elem_copy()
95 ZEND_ASSERT(heap->elem_size == sizeof(zval)); in spl_heap_elem_copy()
255 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_init() local
257 heap->dtor = dtor; in spl_ptr_heap_init()
258 heap->ctor = ctor; in spl_ptr_heap_init()
259 heap->cmp = cmp; in spl_ptr_heap_init()
260 heap->elements = ecalloc(PTR_HEAP_BLOCK_SIZE, elem_size); in spl_ptr_heap_init()
261 heap->max_size = PTR_HEAP_BLOCK_SIZE; in spl_ptr_heap_init()
262 heap->count = 0; in spl_ptr_heap_init()
263 heap->flags = 0; in spl_ptr_heap_init()
264 heap->elem_size = elem_size; in spl_ptr_heap_init()
266 return heap; in spl_ptr_heap_init()
270 static void spl_ptr_heap_insert(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_insert() argument
273 if (heap->count+1 > heap->max_size) { in spl_ptr_heap_insert()
274 size_t alloc_size = heap->max_size * heap->elem_size; in spl_ptr_heap_insert()
276 heap->elements = safe_erealloc(heap->elements, 2, alloc_size, 0); in spl_ptr_heap_insert()
277 memset((char *) heap->elements + alloc_size, 0, alloc_size); in spl_ptr_heap_insert()
278 heap->max_size *= 2; in spl_ptr_heap_insert()
282 …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()
283 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, (i-1)/2)); in spl_ptr_heap_insert()
285 heap->count++; in spl_ptr_heap_insert()
289 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_insert()
292 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), elem); in spl_ptr_heap_insert()
296 static void *spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_top() argument
297 if (heap->count == 0) { in spl_ptr_heap_top()
301 return heap->elements; in spl_ptr_heap_top()
305 static int spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_delete_top() argument
307 const int limit = (heap->count-1)/2; in spl_ptr_heap_delete_top()
310 if (heap->count == 0) { in spl_ptr_heap_delete_top()
315 spl_heap_elem_copy(heap, elem, spl_heap_elem(heap, 0)); in spl_ptr_heap_delete_top()
317 heap->dtor(spl_heap_elem(heap, 0)); in spl_ptr_heap_delete_top()
320 bottom = spl_heap_elem(heap, --heap->count); in spl_ptr_heap_delete_top()
325 …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()
330 if(heap->cmp(bottom, spl_heap_elem(heap, j), cmp_userdata) < 0) { in spl_ptr_heap_delete_top()
331 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, j)); in spl_ptr_heap_delete_top()
339 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_delete_top()
342 void *to = spl_heap_elem(heap, i); in spl_ptr_heap_delete_top()
344 spl_heap_elem_copy(heap, to, bottom); in spl_ptr_heap_delete_top()
353 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_clone() local
355 heap->dtor = from->dtor; in spl_ptr_heap_clone()
356 heap->ctor = from->ctor; in spl_ptr_heap_clone()
357 heap->cmp = from->cmp; in spl_ptr_heap_clone()
358 heap->max_size = from->max_size; in spl_ptr_heap_clone()
359 heap->count = from->count; in spl_ptr_heap_clone()
360 heap->flags = from->flags; in spl_ptr_heap_clone()
361 heap->elem_size = from->elem_size; in spl_ptr_heap_clone()
363 heap->elements = safe_emalloc(from->elem_size, from->max_size, 0); in spl_ptr_heap_clone()
364 memcpy(heap->elements, from->elements, from->elem_size * from->max_size); in spl_ptr_heap_clone()
366 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_clone()
367 heap->ctor(spl_heap_elem(heap, i)); in spl_ptr_heap_clone()
370 return heap; in spl_ptr_heap_clone()
374 static void spl_ptr_heap_destroy(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_destroy() argument
377 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_destroy()
378 heap->dtor(spl_heap_elem(heap, i)); in spl_ptr_heap_destroy()
381 efree(heap->elements); in spl_ptr_heap_destroy()
382 efree(heap); in spl_ptr_heap_destroy()
386 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_count() argument
387 return heap->count; in spl_ptr_heap_count()
397 spl_ptr_heap_destroy(intern->heap); in spl_heap_object_free_storage()
417 intern->heap = spl_ptr_heap_clone(other->heap); in spl_heap_object_new_ex()
419 intern->heap = other->heap; in spl_heap_object_new_ex()
430 …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()
438 intern->heap = spl_ptr_heap_init( in spl_heap_object_new_ex()
498 *count = spl_ptr_heap_count(intern->heap); in spl_heap_object_count_elements()
524 ZVAL_BOOL(&tmp, intern->heap->flags&SPL_HEAP_CORRUPTED); in spl_heap_object_get_debug_info()
530 for (i = 0; i < intern->heap->count; ++i) { in spl_heap_object_get_debug_info()
532 spl_pqueue_elem *pq_elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
537 zval *elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
554 *gc_data = (zval *) intern->heap->elements; in spl_heap_object_get_gc()
555 *gc_data_count = intern->heap->count; in spl_heap_object_get_gc()
564 *gc_data = (zval *) intern->heap->elements; in spl_pqueue_object_get_gc()
566 *gc_data_count = 2 * intern->heap->count; in spl_pqueue_object_get_gc()
582 count = spl_ptr_heap_count(intern->heap); in PHP_METHOD()
596 RETURN_BOOL(spl_ptr_heap_count(intern->heap) == 0); in PHP_METHOD()
612 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
618 spl_ptr_heap_insert(intern->heap, value, ZEND_THIS); in PHP_METHOD()
635 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
640 if (spl_ptr_heap_delete_top(intern->heap, return_value, ZEND_THIS) == FAILURE) { in PHP_METHOD()
661 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
677 if (intern->heap->count == 0) { /* Specialize empty queue */ in PHP_METHOD()
678 intern->heap->cmp = new_cmp; in PHP_METHOD()
679 } else if (new_cmp != intern->heap->cmp) { /* Despecialize on type conflict. */ in PHP_METHOD()
680 intern->heap->cmp = spl_ptr_pqueue_elem_cmp; in PHP_METHOD()
684 spl_ptr_heap_insert(intern->heap, &elem, ZEND_THIS); in PHP_METHOD()
702 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
707 if (spl_ptr_heap_delete_top(intern->heap, &elem, ZEND_THIS) == FAILURE) { in PHP_METHOD()
729 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
734 elem = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
794 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED; in PHP_METHOD()
811 RETURN_BOOL(intern->heap->flags & SPL_HEAP_CORRUPTED); in PHP_METHOD()
840 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
845 value = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
897 return ((Z_SPLHEAP_P(&iter->data))->heap->count != 0 ? SUCCESS : FAILURE); in spl_heap_it_valid()
905 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_get_current_data()
910 if (object->heap->count == 0) { in spl_heap_it_get_current_data()
913 return spl_heap_elem(object->heap, 0); in spl_heap_it_get_current_data()
923 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_pqueue_it_get_current_data()
928 if (object->heap->count == 0) { in spl_pqueue_it_get_current_data()
933 spl_pqueue_elem *elem = spl_heap_elem(object->heap, 0); in spl_pqueue_it_get_current_data()
944 ZVAL_LONG(key, object->heap->count - 1); in spl_heap_it_get_current_key()
952 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_move_forward()
957 spl_ptr_heap_delete_top(object->heap, NULL, &iter->data); in spl_heap_it_move_forward()
971 RETURN_LONG(intern->heap->count - 1); in PHP_METHOD()
984 spl_ptr_heap_delete_top(intern->heap, NULL, ZEND_THIS); in PHP_METHOD()
997 RETURN_BOOL(intern->heap->count != 0); in PHP_METHOD()
1020 if (!intern->heap->count) { in PHP_METHOD()
1023 zval *element = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
1038 if (!intern->heap->count) { in PHP_METHOD()
1041 spl_pqueue_elem *elem = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
