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 } 301