Documentation/core-api/min_heap.rst

Source file repositories/reference/linux-study-clean/Documentation/core-api/min_heap.rst

File Facts

System
Linux kernel
Corpus path
Documentation/core-api/min_heap.rst
Extension
.rst
Size
10402 bytes
Lines
303
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

struct _name {
        size_t nr;         /* Number of elements in the heap */
        size_t size;       /* Maximum number of elements that can be held */
        _type *data;    /* Pointer to the heap data */
        _type preallocated[_nr];  /* Static preallocated array */
    }

    #define DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0)

A typical heap structure will include a counter for the number of elements
(`nr`), the maximum capacity of the heap (`size`), and a pointer to an array of
elements (`data`). Optionally, you can specify a static array for preallocated
heap storage using **MIN_HEAP_PREALLOCATED**.

Min Heap Callbacks
------------------

The **struct min_heap_callbacks** provides customization options for ordering
elements in the heap and swapping them. It contains two function pointers:

.. code-block:: c

    struct min_heap_callbacks {
        bool (*less)(const void *lhs, const void *rhs, void *args);
        void (*swp)(void *lhs, void *rhs, void *args);
    };

- **less** is the comparison function used to establish the order of elements.
- **swp** is a function for swapping elements in the heap. If swp is set to
  NULL, the default swap function will be used, which swaps the elements based on their size

Macro Wrappers
==============

The following macro wrappers are provided for interacting with the heap in a
user-friendly manner. Each macro corresponds to a function that operates on the
heap, and they abstract away direct calls to internal functions.

Each macro accepts various parameters that are detailed below.

Heap Initialization
--------------------

.. code-block:: c

    min_heap_init(heap, data, size);

- **heap**: A pointer to the min-heap structure to be initialized.
- **data**: A pointer to the buffer where the heap elements will be stored. If
  `NULL`, the preallocated buffer within the heap structure will be used.
- **size**: The maximum number of elements the heap can hold.

This macro initializes the heap, setting its initial state. If `data` is
`NULL`, the preallocated memory inside the heap structure will be used for
storage. Otherwise, the user-provided buffer is used. The operation is **O(1)**.

**Inline Version:** min_heap_init_inline(heap, data, size)

Accessing the Top Element
-------------------------

.. code-block:: c

    element = min_heap_peek(heap);

- **heap**: A pointer to the min-heap from which to retrieve the smallest
  element.

This macro returns a pointer to the smallest element (the root) of the heap, or
`NULL` if the heap is empty. The operation is **O(1)**.

Annotation

Implementation Notes