Loading...
Note: File does not exist in v4.6.
1.. SPDX-License-Identifier: GPL-2.0
2
3============
4Min Heap API
5============
6
7Introduction
8============
9
10The Min Heap API provides a set of functions and macros for managing min-heaps
11in the Linux kernel. A min-heap is a binary tree structure where the value of
12each node is less than or equal to the values of its children, ensuring that
13the smallest element is always at the root.
14
15This document provides a guide to the Min Heap API, detailing how to define and
16use min-heaps. Users should not directly call functions with **__min_heap_*()**
17prefixes, but should instead use the provided macro wrappers.
18
19In addition to the standard version of the functions, the API also includes a
20set of inline versions for performance-critical scenarios. These inline
21functions have the same names as their non-inline counterparts but include an
22**_inline** suffix. For example, **__min_heap_init_inline** and its
23corresponding macro wrapper **min_heap_init_inline**. The inline versions allow
24custom comparison and swap functions to be called directly, rather than through
25indirect function calls. This can significantly reduce overhead, especially
26when CONFIG_MITIGATION_RETPOLINE is enabled, as indirect function calls become
27more expensive. As with the non-inline versions, it is important to use the
28macro wrappers for inline functions instead of directly calling the functions
29themselves.
30
31Data Structures
32===============
33
34Min-Heap Definition
35-------------------
36
37The core data structure for representing a min-heap is defined using the
38**MIN_HEAP_PREALLOCATED** and **DEFINE_MIN_HEAP** macros. These macros allow
39you to define a min-heap with a preallocated buffer or dynamically allocated
40memory.
41
42Example:
43
44.. code-block:: c
45
46 #define MIN_HEAP_PREALLOCATED(_type, _name, _nr)
47 struct _name {
48 int nr; /* Number of elements in the heap */
49 int size; /* Maximum number of elements that can be held */
50 _type *data; /* Pointer to the heap data */
51 _type preallocated[_nr]; /* Static preallocated array */
52 }
53
54 #define DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0)
55
56A typical heap structure will include a counter for the number of elements
57(`nr`), the maximum capacity of the heap (`size`), and a pointer to an array of
58elements (`data`). Optionally, you can specify a static array for preallocated
59heap storage using **MIN_HEAP_PREALLOCATED**.
60
61Min Heap Callbacks
62------------------
63
64The **struct min_heap_callbacks** provides customization options for ordering
65elements in the heap and swapping them. It contains two function pointers:
66
67.. code-block:: c
68
69 struct min_heap_callbacks {
70 bool (*less)(const void *lhs, const void *rhs, void *args);
71 void (*swp)(void *lhs, void *rhs, void *args);
72 };
73
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
76 NULL, the default swap function will be used, which swaps the elements based on their size
77
78Macro Wrappers
79==============
80
81The following macro wrappers are provided for interacting with the heap in a
82user-friendly manner. Each macro corresponds to a function that operates on the
83heap, and they abstract away direct calls to internal functions.
84
85Each macro accepts various parameters that are detailed below.
86
87Heap Initialization
88--------------------
89
90.. code-block:: c
91
92 min_heap_init(heap, data, size);
93
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
96 `NULL`, the preallocated buffer within the heap structure will be used.
97- **size**: The maximum number of elements the heap can hold.
98
99This macro initializes the heap, setting its initial state. If `data` is
100`NULL`, the preallocated memory inside the heap structure will be used for
101storage. Otherwise, the user-provided buffer is used. The operation is **O(1)**.
102
103**Inline Version:** min_heap_init_inline(heap, data, size)
104
105Accessing the Top Element
106-------------------------
107
108.. code-block:: c
109
110 element = min_heap_peek(heap);
111
112- **heap**: A pointer to the min-heap from which to retrieve the smallest
113 element.
114
115This macro returns a pointer to the smallest element (the root) of the heap, or
116`NULL` if the heap is empty. The operation is **O(1)**.
117
118**Inline Version:** min_heap_peek_inline(heap)
119
120Heap Insertion
121--------------
122
123.. code-block:: c
124
125 success = min_heap_push(heap, element, callbacks, args);
126
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.
132
133This macro inserts an element into the heap. It returns `true` if the insertion
134was successful and `false` if the heap is full. The operation is **O(log n)**.
135
136**Inline Version:** min_heap_push_inline(heap, element, callbacks, args)
137
138Heap Removal
139------------
140
141.. code-block:: c
142
143 success = min_heap_pop(heap, callbacks, args);
144
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.
149
150This macro removes the smallest element (the root) from the heap. It returns
151`true` if the element was successfully removed, or `false` if the heap is
152empty. The operation is **O(log n)**.
153
154**Inline Version:** min_heap_pop_inline(heap, callbacks, args)
155
156Heap Maintenance
157----------------
158
159You can use the following macros to maintain the heap's structure:
160
161.. code-block:: c
162
163 min_heap_sift_down(heap, pos, callbacks, args);
164
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.
170
171This macro restores the heap property by moving the element at the specified
172index (`pos`) down the heap until it is in the correct position. The operation
173is **O(log n)**.
174
175**Inline Version:** min_heap_sift_down_inline(heap, pos, callbacks, args)
176
177.. code-block:: c
178
179 min_heap_sift_up(heap, idx, callbacks, args);
180
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.
186
187This macro restores the heap property by moving the element at the specified
188index (`idx`) up the heap. The operation is **O(log n)**.
189
190**Inline Version:** min_heap_sift_up_inline(heap, idx, callbacks, args)
191
192.. code-block:: c
193
194 min_heapify_all(heap, callbacks, args);
195
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.
200
201This macro ensures that the entire heap satisfies the heap property. It is
202called when the heap is built from scratch or after many modifications. The
203operation is **O(n)**.
204
205**Inline Version:** min_heapify_all_inline(heap, callbacks, args)
206
207Removing Specific Elements
208--------------------------
209
210.. code-block:: c
211
212 success = min_heap_del(heap, idx, callbacks, args);
213
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.
219
220This macro removes an element at the specified index (`idx`) from the heap and
221restores the heap property. The operation is **O(log n)**.
222
223**Inline Version:** min_heap_del_inline(heap, idx, callbacks, args)
224
225Other Utilities
226===============
227
228- **min_heap_full(heap)**: Checks whether the heap is full.
229 Complexity: **O(1)**.
230
231.. code-block:: c
232
233 bool full = min_heap_full(heap);
234
235- `heap`: A pointer to the min-heap to check.
236
237This macro returns `true` if the heap is full, otherwise `false`.
238
239**Inline Version:** min_heap_full_inline(heap)
240
241- **min_heap_empty(heap)**: Checks whether the heap is empty.
242 Complexity: **O(1)**.
243
244.. code-block:: c
245
246 bool empty = min_heap_empty(heap);
247
248- `heap`: A pointer to the min-heap to check.
249
250This macro returns `true` if the heap is empty, otherwise `false`.
251
252**Inline Version:** min_heap_empty_inline(heap)
253
254Example Usage
255=============
256
257An example usage of the min-heap API would involve defining a heap structure,
258initializing it, and inserting and removing elements as needed.
259
260.. code-block:: c
261
262 #include <linux/min_heap.h>
263
264 int my_less_function(const void *lhs, const void *rhs, void *args) {
265 return (*(int *)lhs < *(int *)rhs);
266 }
267
268 struct min_heap_callbacks heap_cb = {
269 .less = my_less_function, /* Comparison function for heap order */
270 .swp = NULL, /* Use default swap function */
271 };
272
273 void example_usage(void) {
274 /* Pre-populate the buffer with elements */
275 int buffer[5] = {5, 2, 8, 1, 3};
276 /* Declare a min-heap */
277 DEFINE_MIN_HEAP(int, my_heap);
278
279 /* Initialize the heap with preallocated buffer and size */
280 min_heap_init(&my_heap, buffer, 5);
281
282 /* Build the heap using min_heapify_all */
283 my_heap.nr = 5; /* Set the number of elements in the heap */
284 min_heapify_all(&my_heap, &heap_cb, NULL);
285
286 /* Peek at the top element (should be 1 in this case) */
287 int *top = min_heap_peek(&my_heap);
288 pr_info("Top element: %d\n", *top);
289
290 /* Pop the top element (1) and get the new top (2) */
291 min_heap_pop(&my_heap, &heap_cb, NULL);
292 top = min_heap_peek(&my_heap);
293 pr_info("New top element: %d\n", *top);
294
295 /* Insert a new element (0) and recheck the top */
296 int new_element = 0;
297 min_heap_push(&my_heap, &new_element, &heap_cb, NULL);
298 top = min_heap_peek(&my_heap);
299 pr_info("Top element after insertion: %d\n", *top);
300 }