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 zend_result 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
376 if (!heap) { in spl_ptr_heap_destroy()
382 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_destroy()
383 heap->dtor(spl_heap_elem(heap, i)); in spl_ptr_heap_destroy()
386 efree(heap->elements); in spl_ptr_heap_destroy()
387 efree(heap); in spl_ptr_heap_destroy()
391 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_count() argument
392 return heap->count; in spl_ptr_heap_count()
402 spl_ptr_heap_destroy(intern->heap); in spl_heap_object_free_storage()
422 intern->heap = spl_ptr_heap_clone(other->heap); in spl_heap_object_new_ex()
424 intern->heap = other->heap; in spl_heap_object_new_ex()
435 …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()
442 intern->heap = spl_ptr_heap_init( in spl_heap_object_new_ex()
502 *count = spl_ptr_heap_count(intern->heap); in spl_heap_object_count_elements()
528 ZVAL_BOOL(&tmp, intern->heap->flags&SPL_HEAP_CORRUPTED); in spl_heap_object_get_debug_info()
534 for (i = 0; i < intern->heap->count; ++i) { in spl_heap_object_get_debug_info()
536 spl_pqueue_elem *pq_elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
541 zval *elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
558 *gc_data = (zval *) intern->heap->elements; in spl_heap_object_get_gc()
559 *gc_data_count = intern->heap->count; in spl_heap_object_get_gc()
568 *gc_data = (zval *) intern->heap->elements; in spl_pqueue_object_get_gc()
570 *gc_data_count = 2 * intern->heap->count; in spl_pqueue_object_get_gc()
586 count = spl_ptr_heap_count(intern->heap); in PHP_METHOD()
600 RETURN_BOOL(spl_ptr_heap_count(intern->heap) == 0); in PHP_METHOD()
616 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
622 spl_ptr_heap_insert(intern->heap, value, ZEND_THIS); in PHP_METHOD()
639 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
644 if (spl_ptr_heap_delete_top(intern->heap, return_value, ZEND_THIS) == FAILURE) { in PHP_METHOD()
665 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
681 if (intern->heap->count == 0) { /* Specialize empty queue */ in PHP_METHOD()
682 intern->heap->cmp = new_cmp; in PHP_METHOD()
683 } else if (new_cmp != intern->heap->cmp) { /* Despecialize on type conflict. */ in PHP_METHOD()
684 intern->heap->cmp = spl_ptr_pqueue_elem_cmp; in PHP_METHOD()
688 spl_ptr_heap_insert(intern->heap, &elem, ZEND_THIS); in PHP_METHOD()
706 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
711 if (spl_ptr_heap_delete_top(intern->heap, &elem, ZEND_THIS) == FAILURE) { in PHP_METHOD()
733 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
738 elem = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
798 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED; in PHP_METHOD()
815 RETURN_BOOL(intern->heap->flags & SPL_HEAP_CORRUPTED); in PHP_METHOD()
844 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
849 value = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
901 return ((Z_SPLHEAP_P(&iter->data))->heap->count != 0 ? SUCCESS : FAILURE); in spl_heap_it_valid()
909 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_get_current_data()
914 if (object->heap->count == 0) { in spl_heap_it_get_current_data()
917 return spl_heap_elem(object->heap, 0); in spl_heap_it_get_current_data()
927 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_pqueue_it_get_current_data()
932 if (object->heap->count == 0) { in spl_pqueue_it_get_current_data()
937 spl_pqueue_elem *elem = spl_heap_elem(object->heap, 0); in spl_pqueue_it_get_current_data()
948 ZVAL_LONG(key, object->heap->count - 1); in spl_heap_it_get_current_key()
956 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_move_forward()
961 spl_ptr_heap_delete_top(object->heap, NULL, &iter->data); in spl_heap_it_move_forward()
975 RETURN_LONG(intern->heap->count - 1); in PHP_METHOD()
988 spl_ptr_heap_delete_top(intern->heap, NULL, ZEND_THIS); in PHP_METHOD()
1001 RETURN_BOOL(intern->heap->count != 0); in PHP_METHOD()
1024 if (!intern->heap->count) { in PHP_METHOD()
1027 zval *element = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
1042 if (!intern->heap->count) { in PHP_METHOD()
1045 spl_pqueue_elem *elem = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
