Lines Matching refs:heap
69 spl_ptr_heap *heap; member
94 static zend_always_inline void *spl_heap_elem(spl_ptr_heap *heap, size_t i) { in spl_heap_elem() argument
95 return (void *) ((char *) heap->elements + heap->elem_size * i); in spl_heap_elem()
98 static zend_always_inline void spl_heap_elem_copy(spl_ptr_heap *heap, void *to, void *from) { in spl_heap_elem_copy() argument
100 memcpy(to, from, heap->elem_size); in spl_heap_elem_copy()
242 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_init() local
244 heap->dtor = dtor; in spl_ptr_heap_init()
245 heap->ctor = ctor; in spl_ptr_heap_init()
246 heap->cmp = cmp; in spl_ptr_heap_init()
247 heap->elements = ecalloc(PTR_HEAP_BLOCK_SIZE, elem_size); in spl_ptr_heap_init()
248 heap->max_size = PTR_HEAP_BLOCK_SIZE; in spl_ptr_heap_init()
249 heap->count = 0; in spl_ptr_heap_init()
250 heap->flags = 0; in spl_ptr_heap_init()
251 heap->elem_size = elem_size; in spl_ptr_heap_init()
253 return heap; in spl_ptr_heap_init()
257 static void spl_ptr_heap_insert(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_insert() argument
260 if (heap->count+1 > heap->max_size) { in spl_ptr_heap_insert()
261 size_t alloc_size = heap->max_size * heap->elem_size; in spl_ptr_heap_insert()
263 heap->elements = erealloc(heap->elements, 2 * alloc_size); in spl_ptr_heap_insert()
264 memset((char *) heap->elements + alloc_size, 0, alloc_size); in spl_ptr_heap_insert()
265 heap->max_size *= 2; in spl_ptr_heap_insert()
269 …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()
270 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, (i-1)/2)); in spl_ptr_heap_insert()
272 heap->count++; in spl_ptr_heap_insert()
276 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_insert()
279 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), elem); in spl_ptr_heap_insert()
283 static void *spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_top() argument
284 if (heap->count == 0) { in spl_ptr_heap_top()
288 return heap->elements; in spl_ptr_heap_top()
292 static int spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */ in spl_ptr_heap_delete_top() argument
294 const int limit = (heap->count-1)/2; in spl_ptr_heap_delete_top()
297 if (heap->count == 0) { in spl_ptr_heap_delete_top()
302 spl_heap_elem_copy(heap, elem, spl_heap_elem(heap, 0)); in spl_ptr_heap_delete_top()
304 heap->dtor(spl_heap_elem(heap, 0)); in spl_ptr_heap_delete_top()
307 bottom = spl_heap_elem(heap, --heap->count); in spl_ptr_heap_delete_top()
312 …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()
317 if(heap->cmp(bottom, spl_heap_elem(heap, j), cmp_userdata) < 0) { in spl_ptr_heap_delete_top()
318 spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, j)); in spl_ptr_heap_delete_top()
326 heap->flags |= SPL_HEAP_CORRUPTED; in spl_ptr_heap_delete_top()
329 void *to = spl_heap_elem(heap, i); in spl_ptr_heap_delete_top()
331 spl_heap_elem_copy(heap, to, bottom); in spl_ptr_heap_delete_top()
340 spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap)); in spl_ptr_heap_clone() local
342 heap->dtor = from->dtor; in spl_ptr_heap_clone()
343 heap->ctor = from->ctor; in spl_ptr_heap_clone()
344 heap->cmp = from->cmp; in spl_ptr_heap_clone()
345 heap->max_size = from->max_size; in spl_ptr_heap_clone()
346 heap->count = from->count; in spl_ptr_heap_clone()
347 heap->flags = from->flags; in spl_ptr_heap_clone()
348 heap->elem_size = from->elem_size; in spl_ptr_heap_clone()
350 heap->elements = safe_emalloc(from->elem_size, from->max_size, 0); in spl_ptr_heap_clone()
351 memcpy(heap->elements, from->elements, from->elem_size * from->max_size); in spl_ptr_heap_clone()
353 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_clone()
354 heap->ctor(spl_heap_elem(heap, i)); in spl_ptr_heap_clone()
357 return heap; in spl_ptr_heap_clone()
361 static void spl_ptr_heap_destroy(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_destroy() argument
364 for (i = 0; i < heap->count; ++i) { in spl_ptr_heap_destroy()
365 heap->dtor(spl_heap_elem(heap, i)); in spl_ptr_heap_destroy()
368 efree(heap->elements); in spl_ptr_heap_destroy()
369 efree(heap); in spl_ptr_heap_destroy()
373 static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */ in spl_ptr_heap_count() argument
374 return heap->count; in spl_ptr_heap_count()
384 spl_ptr_heap_destroy(intern->heap); in spl_heap_object_free_storage()
404 intern->heap = spl_ptr_heap_clone(other->heap); in spl_heap_object_new_ex()
406 intern->heap = other->heap; in spl_heap_object_new_ex()
417 …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()
425 intern->heap = spl_ptr_heap_init( in spl_heap_object_new_ex()
485 *count = spl_ptr_heap_count(intern->heap); in spl_heap_object_count_elements()
511 ZVAL_BOOL(&tmp, intern->heap->flags&SPL_HEAP_CORRUPTED); in spl_heap_object_get_debug_info()
517 for (i = 0; i < intern->heap->count; ++i) { in spl_heap_object_get_debug_info()
519 spl_pqueue_elem *pq_elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
524 zval *elem = spl_heap_elem(intern->heap, i); in spl_heap_object_get_debug_info()
541 *gc_data = (zval *) intern->heap->elements; in spl_heap_object_get_gc()
542 *gc_data_count = intern->heap->count; in spl_heap_object_get_gc()
551 *gc_data = (zval *) intern->heap->elements; in spl_pqueue_object_get_gc()
553 *gc_data_count = 2 * intern->heap->count; in spl_pqueue_object_get_gc()
569 count = spl_ptr_heap_count(intern->heap); in PHP_METHOD()
583 RETURN_BOOL(spl_ptr_heap_count(intern->heap) == 0); in PHP_METHOD()
599 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
605 spl_ptr_heap_insert(intern->heap, value, ZEND_THIS); in PHP_METHOD()
622 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
627 if (spl_ptr_heap_delete_top(intern->heap, return_value, ZEND_THIS) == FAILURE) { in PHP_METHOD()
647 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
655 spl_ptr_heap_insert(intern->heap, &elem, ZEND_THIS); in PHP_METHOD()
673 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
678 if (spl_ptr_heap_delete_top(intern->heap, &elem, ZEND_THIS) == FAILURE) { in PHP_METHOD()
700 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
705 elem = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
765 intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED; in PHP_METHOD()
782 RETURN_BOOL(intern->heap->flags & SPL_HEAP_CORRUPTED); in PHP_METHOD()
811 if (intern->heap->flags & SPL_HEAP_CORRUPTED) { in PHP_METHOD()
816 value = spl_ptr_heap_top(intern->heap); in PHP_METHOD()
870 return ((Z_SPLHEAP_P(&iter->data))->heap->count != 0 ? SUCCESS : FAILURE); in spl_heap_it_valid()
878 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_get_current_data()
883 if (object->heap->count == 0) { in spl_heap_it_get_current_data()
886 return spl_heap_elem(object->heap, 0); in spl_heap_it_get_current_data()
896 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_pqueue_it_get_current_data()
901 if (object->heap->count == 0) { in spl_pqueue_it_get_current_data()
906 spl_pqueue_elem *elem = spl_heap_elem(object->heap, 0); in spl_pqueue_it_get_current_data()
917 ZVAL_LONG(key, object->heap->count - 1); in spl_heap_it_get_current_key()
925 if (object->heap->flags & SPL_HEAP_CORRUPTED) { in spl_heap_it_move_forward()
930 spl_ptr_heap_delete_top(object->heap, NULL, &iter->data); in spl_heap_it_move_forward()
944 RETURN_LONG(intern->heap->count - 1); in PHP_METHOD()
957 spl_ptr_heap_delete_top(intern->heap, NULL, ZEND_THIS); in PHP_METHOD()
970 RETURN_BOOL(intern->heap->count != 0); in PHP_METHOD()
993 if (!intern->heap->count) { in PHP_METHOD()
996 zval *element = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
1011 if (!intern->heap->count) { in PHP_METHOD()
1014 spl_pqueue_elem *elem = spl_heap_elem(intern->heap, 0); in PHP_METHOD()
