10  * The Min Heap API provides utilities for managing min-heaps, a binary tree
21  * Data structure to hold a min-heap.
22  * @nr: Number of elements currently in the heap.
24  * @data: Pointer to the start of array holding the heap elements.
25  * @preallocated: Start of the static preallocated array holding the heap elements.
44  * @less: Partial order function for this heap.
195  * @i: the offset of the heap element whose parent is sought.  Non-zero.
219 /* Initialize a min-heap. */
221 void __min_heap_init_inline(min_heap_char *heap, void *data, size_t size)  in __min_heap_init_inline()  argument
223 	heap->nr = 0;  in __min_heap_init_inline()
224 	heap->size = size;  in __min_heap_init_inline()
226 		heap->data = data;  in __min_heap_init_inline()
228 		heap->data = heap->preallocated;  in __min_heap_init_inline()
234 /* Get the minimum element from the heap. */
236 void *__min_heap_peek_inline(struct min_heap_char *heap)  in __min_heap_peek_inline()  argument
238 	return heap->nr ? heap->data : NULL;  in __min_heap_peek_inline()
245 /* Check if the heap is full. */
247 bool __min_heap_full_inline(min_heap_char *heap)  in __min_heap_full_inline()  argument
249 	return heap->nr == heap->size;  in __min_heap_full_inline()
255 /* Sift the element at pos down the heap. */
257 void __min_heap_sift_down_inline(min_heap_char *heap, size_t pos, size_t elem_size,  in __min_heap_sift_down_inline()  argument
261 	void *data = heap->data;  in __min_heap_sift_down_inline()
266 	size_t n = heap->nr * elem_size;  in __min_heap_sift_down_inline()
295 /* Sift up ith element from the heap, O(log2(nr)). */
297 void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size_t idx,  in __min_heap_sift_up_inline()  argument
301 	void *data = heap->data;  in __min_heap_sift_up_inline()
324 void __min_heapify_all_inline(min_heap_char *heap, size_t elem_size,  in __min_heapify_all_inline()  argument
329 	for (i = heap->nr / 2 - 1; i >= 0; i--)  in __min_heapify_all_inline()
330 		__min_heap_sift_down_inline(heap, i, elem_size, func, args);  in __min_heapify_all_inline()
337 /* Remove minimum element from the heap, O(log2(nr)). */
339 bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size,  in __min_heap_pop_inline()  argument
342 	void *data = heap->data;  in __min_heap_pop_inline()
344 	if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap"))  in __min_heap_pop_inline()
348 	heap->nr--;  in __min_heap_pop_inline()
349 	memcpy(data, data + (heap->nr * elem_size), elem_size);  in __min_heap_pop_inline()
350 	__min_heap_sift_down_inline(heap, 0, elem_size, func, args);  in __min_heap_pop_inline()
365 void __min_heap_pop_push_inline(min_heap_char *heap, const void *element, size_t elem_size,  in __min_heap_pop_push_inline()  argument
368 	memcpy(heap->data, element, elem_size);  in __min_heap_pop_push_inline()
369 	__min_heap_sift_down_inline(heap, 0, elem_size, func, args);  in __min_heap_pop_push_inline()
376 /* Push an element on to the heap, O(log2(nr)). */
378 bool __min_heap_push_inline(min_heap_char *heap, const void *element, size_t elem_size,  in __min_heap_push_inline()  argument
381 	void *data = heap->data;  in __min_heap_push_inline()
384 	if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap"))  in __min_heap_push_inline()
388 	pos = heap->nr;  in __min_heap_push_inline()
390 	heap->nr++;  in __min_heap_push_inline()
393 	__min_heap_sift_up_inline(heap, elem_size, pos, func, args);  in __min_heap_push_inline()
402 /* Remove ith element from the heap, O(log2(nr)). */
404 bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t idx,  in __min_heap_del_inline()  argument
407 	void *data = heap->data;  in __min_heap_del_inline()
410 	if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap"))  in __min_heap_del_inline()
417 	heap->nr--;  in __min_heap_del_inline()
418 	if (idx == heap->nr)  in __min_heap_del_inline()
420 	do_swap(data + (idx * elem_size), data + (heap->nr * elem_size), elem_size, swp, args);  in __min_heap_del_inline()
421 	__min_heap_sift_up_inline(heap, elem_size, idx, func, args);  in __min_heap_del_inline()
422 	__min_heap_sift_down_inline(heap, idx, elem_size, func, args);  in __min_heap_del_inline()
431 void __min_heap_init(min_heap_char *heap, void *data, size_t size);
432 void *__min_heap_peek(struct min_heap_char *heap);
433 bool __min_heap_full(min_heap_char *heap);
434 void __min_heap_sift_down(min_heap_char *heap, size_t pos, size_t elem_size,
436 void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
438 void __min_heapify_all(min_heap_char *heap, size_t elem_size,
440 bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
442 void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size,
444 bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
446 bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,