Lines Matching +full:in +full:- +full:functions
1 .. SPDX-License-Identifier: GPL-2.0
10 The Min Heap API provides a set of functions and macros for managing min-heaps
11 in the Linux kernel. A min-heap is a binary tree structure where the value of
16 use min-heaps. Users should not directly call functions with **__min_heap_*()**
19 In addition to the standard version of the functions, the API also includes a
20 set of inline versions for performance-critical scenarios. These inline
21 functions have the same names as their non-inline counterparts but include an
24 custom comparison and swap functions to be called directly, rather than through
27 more expensive. As with the non-inline versions, it is important to use the
28 macro wrappers for inline functions instead of directly calling the functions
34 Min-Heap Definition
35 -------------------
37 The core data structure for representing a min-heap is defined using the
39 you to define a min-heap with a preallocated buffer or dynamically allocated
44 .. code-block:: c
48 int nr; /* Number of elements in the heap */
62 ------------------
65 elements in the heap and swapping them. It contains two function pointers:
67 .. code-block:: c
74 - **less** is the comparison function used to establish the order of elements.
75 - **swp** is a function for swapping elements in the heap. If swp is set to
81 The following macro wrappers are provided for interacting with the heap in a
82 user-friendly manner. Each macro corresponds to a function that operates on the
83 heap, and they abstract away direct calls to internal functions.
88 --------------------
90 .. code-block:: c
94 - **heap**: A pointer to the min-heap structure to be initialized.
95 - **data**: A pointer to the buffer where the heap elements will be stored. If
97 - **size**: The maximum number of elements the heap can hold.
101 storage. Otherwise, the user-provided buffer is used. The operation is **O(1)**.
106 -------------------------
108 .. code-block:: c
112 - **heap**: A pointer to the min-heap from which to retrieve the smallest
121 --------------
123 .. code-block:: c
127 - **heap**: A pointer to the min-heap into which the element should be inserted.
128 - **element**: A pointer to the element to be inserted into the heap.
129 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
130 `less` and `swp` functions.
131 - **args**: Optional arguments passed to the `less` and `swp` functions.
139 ------------
141 .. code-block:: c
145 - **heap**: A pointer to the min-heap from which to remove the smallest element.
146 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
147 `less` and `swp` functions.
148 - **args**: Optional arguments passed to the `less` and `swp` functions.
157 ----------------
161 .. code-block:: c
165 - **heap**: A pointer to the min-heap.
166 - **pos**: The index from which to start sifting down.
167 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
168 `less` and `swp` functions.
169 - **args**: Optional arguments passed to the `less` and `swp` functions.
172 index (`pos`) down the heap until it is in the correct position. The operation
177 .. code-block:: c
181 - **heap**: A pointer to the min-heap.
182 - **idx**: The index of the element to sift up.
183 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
184 `less` and `swp` functions.
185 - **args**: Optional arguments passed to the `less` and `swp` functions.
192 .. code-block:: c
196 - **heap**: A pointer to the min-heap.
197 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
198 `less` and `swp` functions.
199 - **args**: Optional arguments passed to the `less` and `swp` functions.
208 --------------------------
210 .. code-block:: c
214 - **heap**: A pointer to the min-heap.
215 - **idx**: The index of the element to delete.
216 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
217 `less` and `swp` functions.
218 - **args**: Optional arguments passed to the `less` and `swp` functions.
228 - **min_heap_full(heap)**: Checks whether the heap is full.
231 .. code-block:: c
235 - `heap`: A pointer to the min-heap to check.
241 - **min_heap_empty(heap)**: Checks whether the heap is empty.
244 .. code-block:: c
248 - `heap`: A pointer to the min-heap to check.
257 An example usage of the min-heap API would involve defining a heap structure,
260 .. code-block:: c
274 /* Pre-populate the buffer with elements */
276 /* Declare a min-heap */
283 my_heap.nr = 5; /* Set the number of elements in the heap */
286 /* Peek at the top element (should be 1 in this case) */