Lines Matching +full:set +full:- +full:top
1 .. SPDX-License-Identifier: GPL-2.0
7 :Author: Kuan-Wei Chiu <[email protected]>
12 The Min Heap API provides a set of functions and macros for managing min-heaps
13 in the Linux kernel. A min-heap is a binary tree structure where the value of
18 use min-heaps. Users should not directly call functions with **__min_heap_*()**
22 set of inline versions for performance-critical scenarios. These inline
23 functions have the same names as their non-inline counterparts but include an
29 more expensive. As with the non-inline versions, it is important to use the
36 Min-Heap Definition
37 -------------------
39 The core data structure for representing a min-heap is defined using the
41 you to define a min-heap with a preallocated buffer or dynamically allocated
46 .. code-block:: c
64 ------------------
69 .. code-block:: c
76 - **less** is the comparison function used to establish the order of elements.
77 - **swp** is a function for swapping elements in the heap. If swp is set to
84 user-friendly manner. Each macro corresponds to a function that operates on the
90 --------------------
92 .. code-block:: c
96 - **heap**: A pointer to the min-heap structure to be initialized.
97 - **data**: A pointer to the buffer where the heap elements will be stored. If
99 - **size**: The maximum number of elements the heap can hold.
103 storage. Otherwise, the user-provided buffer is used. The operation is **O(1)**.
107 Accessing the Top Element
108 -------------------------
110 .. code-block:: c
114 - **heap**: A pointer to the min-heap from which to retrieve the smallest
123 --------------
125 .. code-block:: c
129 - **heap**: A pointer to the min-heap into which the element should be inserted.
130 - **element**: A pointer to the element to be inserted into the heap.
131 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
133 - **args**: Optional arguments passed to the `less` and `swp` functions.
141 ------------
143 .. code-block:: c
147 - **heap**: A pointer to the min-heap from which to remove the smallest element.
148 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
150 - **args**: Optional arguments passed to the `less` and `swp` functions.
159 ----------------
163 .. code-block:: c
167 - **heap**: A pointer to the min-heap.
168 - **pos**: The index from which to start sifting down.
169 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
171 - **args**: Optional arguments passed to the `less` and `swp` functions.
179 .. code-block:: c
183 - **heap**: A pointer to the min-heap.
184 - **idx**: The index of the element to sift up.
185 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
187 - **args**: Optional arguments passed to the `less` and `swp` functions.
194 .. code-block:: c
198 - **heap**: A pointer to the min-heap.
199 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
201 - **args**: Optional arguments passed to the `less` and `swp` functions.
210 --------------------------
212 .. code-block:: c
216 - **heap**: A pointer to the min-heap.
217 - **idx**: The index of the element to delete.
218 - **callbacks**: A pointer to a `struct min_heap_callbacks` providing the
220 - **args**: Optional arguments passed to the `less` and `swp` functions.
230 - **min_heap_full(heap)**: Checks whether the heap is full.
233 .. code-block:: c
237 - `heap`: A pointer to the min-heap to check.
243 - **min_heap_empty(heap)**: Checks whether the heap is empty.
246 .. code-block:: c
250 - `heap`: A pointer to the min-heap to check.
259 An example usage of the min-heap API would involve defining a heap structure,
262 .. code-block:: c
276 /* Pre-populate the buffer with elements */
278 /* Declare a min-heap */
285 my_heap.nr = 5; /* Set the number of elements in the heap */
288 /* Peek at the top element (should be 1 in this case) */
289 int *top = min_heap_peek(&my_heap);
290 pr_info("Top element: %d\n", *top);
292 /* Pop the top element (1) and get the new top (2) */
294 top = min_heap_peek(&my_heap);
295 pr_info("New top element: %d\n", *top);
297 /* Insert a new element (0) and recheck the top */
300 top = min_heap_peek(&my_heap);
301 pr_info("Top element after insertion: %d\n", *top);