/* SPDX-License-Identifier: GPL-2.0 */ #ifndef _LINUX_MIN_HEAP_H #define _LINUX_MIN_HEAP_H #include <linux/bug.h> #include <linux/string.h> #include <linux/types.h> /** * Data structure to hold a min-heap. * @nr: Number of elements currently in the heap. * @size: Maximum number of elements that can be held in current storage. * @data: Pointer to the start of array holding the heap elements. * @preallocated: Start of the static preallocated array holding the heap elements. */ #define MIN_HEAP_PREALLOCATED(_type, _name, _nr) … #define DEFINE_MIN_HEAP(_type, _name) … min_heap_char; #define __minheap_cast(_heap) … #define __minheap_obj_size(_heap) … /** * struct min_heap_callbacks - Data/functions to customise the min_heap. * @less: Partial order function for this heap. * @swp: Swap elements function. */ struct min_heap_callbacks { … }; /* Initialize a min-heap. */ static __always_inline void __min_heap_init(min_heap_char *heap, void *data, int size) { … } #define min_heap_init(_heap, _data, _size) … /* Get the minimum element from the heap. */ static __always_inline void *__min_heap_peek(struct min_heap_char *heap) { … } #define min_heap_peek(_heap) … /* Check if the heap is full. */ static __always_inline bool __min_heap_full(min_heap_char *heap) { … } #define min_heap_full(_heap) … /* Sift the element at pos down the heap. */ static __always_inline void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func, void *args) { … } #define min_heap_sift_down(_heap, _pos, _func, _args) … /* Sift up ith element from the heap, O(log2(nr)). */ static __always_inline void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, const struct min_heap_callbacks *func, void *args) { … } #define min_heap_sift_up(_heap, _idx, _func, _args) … /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { … } #define min_heapify_all(_heap, _func, _args) … /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline bool __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { … } #define min_heap_pop(_heap, _func, _args) … /* * Remove the minimum element and then push the given element. The * implementation performs 1 sift (O(log2(nr))) and is therefore more * efficient than a pop followed by a push that does 2. */ static __always_inline void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size, const struct min_heap_callbacks *func, void *args) { … } #define min_heap_pop_push(_heap, _element, _func, _args) … /* Push an element on to the heap, O(log2(nr)). */ static __always_inline bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, const struct min_heap_callbacks *func, void *args) { … } #define min_heap_push(_heap, _element, _func, _args) … /* Remove ith element from the heap, O(log2(nr)). */ static __always_inline bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, const struct min_heap_callbacks *func, void *args) { … } #define min_heap_del(_heap, _idx, _func, _args) … #endif /* _LINUX_MIN_HEAP_H */
Codebase Browser
linux