Documentation/core-api/min_heap.rst

   1 .. SPDX-License-Identifier: GPL-2.0
   2
   3 ============
   4 Min Heap API
   5 ============
   6
   7 Introduction
   8 ============
   9
  10 The Min Heap API provides a set of functions and macros for managing min-heaps
  11 in the Linux kernel. A min-heap is a binary tree structure where the value of
  12 each node is less than or equal to the values of its children, ensuring that
  13 the smallest element is always at the root.
  14
  15 This document provides a guide to the Min Heap API, detailing how to define and
  16 use min-heaps. Users should not directly call functions with **__min_heap_*()**
  17 prefixes, but should instead use the provided macro wrappers.
  18
  19 In addition to the standard version of the functions, the API also includes a
  20 set of inline versions for performance-critical scenarios. These inline
  21 functions have the same names as their non-inline counterparts but include an
  22 **_inline** suffix. For example, **__min_heap_init_inline** and its
  23 corresponding macro wrapper **min_heap_init_inline**. The inline versions allow
  24 custom comparison and swap functions to be called directly, rather than through
  25 indirect function calls. This can significantly reduce overhead, especially
  26 when CONFIG_MITIGATION_RETPOLINE is enabled, as indirect function calls become
  27 more expensive. As with the non-inline versions, it is important to use the
  28 macro wrappers for inline functions instead of directly calling the functions
  29 themselves.
  30
  31 Data Structures
  32 ===============
  33
  34 Min-Heap Definition
  35 -------------------
  36
  37 The core data structure for representing a min-heap is defined using the
  38 **MIN_HEAP_PREALLOCATED** and **DEFINE_MIN_HEAP** macros. These macros allow
  39 you to define a min-heap with a preallocated buffer or dynamically allocated
  40 memory.
  41
  42 Example:
  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
  56 A 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
  58 elements (`data`). Optionally, you can specify a static array for preallocated
  59 heap storage using **MIN_HEAP_PREALLOCATED**.
  60
  61 Min Heap Callbacks
  62 ------------------
  63
  64 The **struct min_heap_callbacks** provides customization options for ordering
  65 elements 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
  78 Macro Wrappers
  79 ==============
  80
  81 The following macro wrappers are provided for interacting with the heap in a
  82 user-friendly manner. Each macro corresponds to a function that operates on the
  83 heap, and they abstract away direct calls to internal functions.
  84
  85 Each macro accepts various parameters that are detailed below.
  86
  87 Heap 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
  99 This macro initializes the heap, setting its initial state. If `data` is
 100 `NULL`, the preallocated memory inside the heap structure will be used for
 101 storage. Otherwise, the user-provided buffer is used. The operation is **O(1)**.
 102
 103 **Inline Version:** min_heap_init_inline(heap, data, size)
 104
 105 Accessing 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
 115 This 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
 120 Heap 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
 133 This macro inserts an element into the heap. It returns `true` if the insertion
 134 was 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
 138 Heap 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
 150 This 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
 152 empty. The operation is **O(log n)**.
 153
 154 **Inline Version:** min_heap_pop_inline(heap, callbacks, args)
 155
 156 Heap Maintenance
 157 ----------------
 158
 159 You 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
 171 This macro restores the heap property by moving the element at the specified
 172 index (`pos`) down the heap until it is in the correct position. The operation
 173 is **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
 187 This macro restores the heap property by moving the element at the specified
 188 index (`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
 201 This macro ensures that the entire heap satisfies the heap property. It is
 202 called when the heap is built from scratch or after many modifications. The
 203 operation is **O(n)**.
 204
 205 **Inline Version:** min_heapify_all_inline(heap, callbacks, args)
 206
 207 Removing 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
 220 This macro removes an element at the specified index (`idx`) from the heap and
 221 restores the heap property. The operation is **O(log n)**.
 222
 223 **Inline Version:** min_heap_del_inline(heap, idx, callbacks, args)
 224
 225 Other 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
 237 This 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
 250 This macro returns `true` if the heap is empty, otherwise `false`.
 251
 252 **Inline Version:** min_heap_empty_inline(heap)
 253
 254 Example Usage
 255 =============
 256
 257 An example usage of the min-heap API would involve defining a heap structure,
 258 initializing 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     }