Lines Matching +full:in +full:- +full:functions
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_*()**
21 In addition to the standard version of the functions, the API also includes a
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
26 custom comparison and swap functions to be called directly, rather than through
29 more expensive. As with the non-inline versions, it is important to use the
30 macro wrappers for inline functions instead of directly calling the functions
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
50 int nr; /* Number of elements in the heap */
64 ------------------
67 elements in the heap and swapping them. It contains two function pointers:
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
83 The following macro wrappers are provided for interacting with the heap in a
84 user-friendly manner. Each macro corresponds to a function that operates on the
85 heap, and they abstract away direct calls to internal functions.
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)**.
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
132 `less` and `swp` functions.
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
149 `less` and `swp` functions.
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
170 `less` and `swp` functions.
171 - **args**: Optional arguments passed to the `less` and `swp` functions.
174 index (`pos`) down the heap until it is in the correct position. The operation
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
186 `less` and `swp` functions.
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
200 `less` and `swp` functions.
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
219 `less` and `swp` functions.
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) */