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