1 /* SPDX-License-Identifier: GPL-2.0 */
10  * The Min Heap API provides utilities for managing min-heaps, a binary tree
17  * For further details and examples, refer to Documentation/core-api/min_heap.rst.
21  * Data structure to hold a min-heap.
39 #define __minheap_cast(_heap)		(typeof((_heap)->data[0]) *)
40 #define __minheap_obj_size(_heap)	sizeof((_heap)->data[0])
43  * struct min_heap_callbacks - Data/functions to customise the min_heap.
45  * @swp: Swap elements function.
53  * is_aligned - is this pointer & size okay for word-wide copying?
58  * Returns true if elements can be copied using word loads and stores.
59  * The size must be a multiple of the alignment, and the base address must
74 	return (lsbits & (align - 1)) == 0;  in is_aligned()
78  * swap_words_32 - swap two elements in 32-bit chunks
79  * @a: pointer to the first element to swap
80  * @b: pointer to the second element to swap
95 		u32 t = *(u32 *)(a + (n -= 4));  in swap_words_32()
102  * swap_words_64 - swap two elements in 64-bit chunks
103  * @a: pointer to the first element to swap
104  * @b: pointer to the second element to swap
111  * We'd like to use 64-bit loads if possible.  If they're not, emulating
113  * processors do not.  If CONFIG_64BIT, we definitely have 64-bit loads,
114  * but it's possible to have 64-bit loads without 64-bit pointers (e.g.
122 		u64 t = *(u64 *)(a + (n -= 8));  in swap_words_64()
126 		/* Use two 32-bit transfers to avoid base+index+4 addressing */  in swap_words_64()
127 		u32 t = *(u32 *)(a + (n -= 4));  in swap_words_64()
131 		t = *(u32 *)(a + (n -= 4));  in swap_words_64()
139  * swap_bytes - swap two elements a byte at a time
140  * @a: pointer to the first element to swap
141  * @b: pointer to the second element to swap
150 		char t = ((char *)a)[--n];  in swap_bytes()
158  * a pointer, but small integers make for the smallest compare
166  * Selects the appropriate swap function based on the element size.
194  * parent - given the offset of the child, find the offset of the parent.
195  * @i: the offset of the heap element whose parent is sought.  Non-zero.
196  * @lsbit: a precomputed 1-bit mask, equal to "size & -size"
200  * (j-1)/2.  But when working in byte offsets, we can't use implicit
205  * an even multiple of @size, and set if it's an odd multiple.
207  * Logically, we're doing "if (i & lsbit) i -= size;", but since the
208  * branch is unpredictable, it's done with a bit of clever branch-free
214 	i -= size;  in parent()
215 	i -= size & -(i & lsbit);  in parent()
219 /* Initialize a min-heap. */
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()
232 	__min_heap_init_inline(container_of(&(_heap)->nr, min_heap_char, nr), _data, _size)
238 	return heap->nr ? heap->data : NULL;  in __min_heap_peek_inline()
243 	 __min_heap_peek_inline(container_of(&(_heap)->nr, min_heap_char, nr)))
249 	return heap->nr == heap->size;  in __min_heap_full_inline()
253 	__min_heap_full_inline(container_of(&(_heap)->nr, min_heap_char, nr))
260 	const unsigned long lsbit = elem_size & -elem_size;  in __min_heap_sift_down_inline()
261 	void *data = heap->data;  in __min_heap_sift_down_inline()
262 	void (*swp)(void *lhs, void *rhs, void *args) = func->swp;  in __min_heap_sift_down_inline()
263 	/* pre-scale counters for performance */  in __min_heap_sift_down_inline()
266 	size_t n = heap->nr * elem_size;  in __min_heap_sift_down_inline()
271 	/* Find the sift-down path all the way to the leaves. */  in __min_heap_sift_down_inline()
273 		b = func->less(data + c, data + d, args) ? c : d;  in __min_heap_sift_down_inline()
280 	while (b != a && func->less(data + a, data + b, args))  in __min_heap_sift_down_inline()
292 	__min_heap_sift_down_inline(container_of(&(_heap)->nr, min_heap_char, nr), _pos,	\
300 	const unsigned long lsbit = elem_size & -elem_size;  in __min_heap_sift_up_inline()
301 	void *data = heap->data;  in __min_heap_sift_up_inline()
302 	void (*swp)(void *lhs, void *rhs, void *args) = func->swp;  in __min_heap_sift_up_inline()
303 	/* pre-scale counters for performance */  in __min_heap_sift_up_inline()
311 		if (func->less(data + b, data + a, args))  in __min_heap_sift_up_inline()
319 	__min_heap_sift_up_inline(container_of(&(_heap)->nr, min_heap_char, nr),	\
329 	for (i = heap->nr / 2 - 1; i >= 0; i--)  in __min_heapify_all_inline()
334 	__min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr),	\
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()
347 	/* Place last element at the root (position 0) and then sift down. */  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()
356 	__min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr),	\
360  * Remove the minimum element and then push the given element. The
361  * implementation performs 1 sift (O(log2(nr))) and is therefore more
368 	memcpy(heap->data, element, elem_size);  in __min_heap_pop_push_inline()
373 	__min_heap_pop_push_inline(container_of(&(_heap)->nr, min_heap_char, nr), _element,	\
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()
399 	__min_heap_push_inline(container_of(&(_heap)->nr, min_heap_char, nr), _element,	\
407 	void *data = heap->data;  in __min_heap_del_inline()
408 	void (*swp)(void *lhs, void *rhs, void *args) = func->swp;  in __min_heap_del_inline()
410 	if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap"))  in __min_heap_del_inline()
416 	/* Place last element at the root (position 0) and then sift down. */  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()
428 	__min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr),	\
450 	__min_heap_init(container_of(&(_heap)->nr, min_heap_char, nr), _data, _size)
452 	(__minheap_cast(_heap) __min_heap_peek(container_of(&(_heap)->nr, min_heap_char, nr)))
454 	__min_heap_full(container_of(&(_heap)->nr, min_heap_char, nr))
456 	__min_heap_sift_down(container_of(&(_heap)->nr, min_heap_char, nr), _pos,	\
459 	__min_heap_sift_up(container_of(&(_heap)->nr, min_heap_char, nr),	\
462 	__min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr),	\
465 	__min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr),	\
468 	__min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _element,	\
471 	__min_heap_push(container_of(&(_heap)->nr, min_heap_char, nr), _element,	\
474 	__min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr),	\