最小堆 API¶

简介¶

最小堆 API 提供了一组用于在 Linux 内核中管理最小堆的函数和宏。最小堆是一种二叉树结构，其中每个节点的值小于或等于其子节点的值，确保最小的元素始终位于根节点。

本文档提供了最小堆 API 的指南，详细介绍了如何定义和使用最小堆。用户不应直接调用带有 __min_heap_*() 前缀的函数，而应使用提供的宏包装器。

除了标准版本的函数之外，该 API 还包括一组用于性能关键场景的内联版本。这些内联函数与其非内联版本具有相同的名称，但包含 _inline 后缀。例如，__min_heap_init_inline 及其对应的宏包装器 min_heap_init_inline。内联版本允许直接调用自定义比较和交换函数，而不是通过间接函数调用。这可以显著减少开销，尤其是在启用 CONFIG_MITIGATION_RETPOLINE 时，因为间接函数调用的成本会更高。与非内联版本一样，重要的是使用内联函数的宏包装器，而不是直接调用函数本身。

数据结构¶

最小堆定义¶

用于表示最小堆的核心数据结构使用 MIN_HEAP_PREALLOCATED 和 DEFINE_MIN_HEAP 宏定义。这些宏允许您定义具有预分配缓冲区或动态分配内存的最小堆。

示例

#define MIN_HEAP_PREALLOCATED(_type, _name, _nr)
struct _name {
    int nr;         /* Number of elements in the heap */
    int 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)

典型的堆结构将包括元素数量的计数器 (nr)、堆的最大容量 (size) 和指向元素数组的指针 (data)。可选地，您可以使用 MIN_HEAP_PREALLOCATED 为预分配的堆存储指定一个静态数组。

最小堆回调¶

struct min_heap_callbacks 提供了用于对堆中的元素进行排序和交换的自定义选项。它包含两个函数指针：

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

less 是用于建立元素顺序的比较函数。
swp 是用于交换堆中元素的函数。如果 swp 设置为 NULL，则将使用默认的交换函数，该函数根据元素的大小交换元素。

宏包装器¶

提供了以下宏包装器，以便以用户友好的方式与堆进行交互。每个宏都对应于一个对堆进行操作的函数，它们抽象了对内部函数的直接调用。

每个宏都接受下面详细说明的各种参数。

堆初始化¶

min_heap_init(heap, data, size);

heap：指向要初始化的最小堆结构的指针。
data：指向将存储堆元素的缓冲区的指针。如果 NULL，则将使用堆结构中的预分配缓冲区。
size：堆可以容纳的最大元素数。

此宏初始化堆，设置其初始状态。如果 data 为 NULL，则将使用堆结构内部的预分配内存进行存储。否则，将使用用户提供的缓冲区。该操作为 O(1)。

内联版本： min_heap_init_inline(heap, data, size)

访问顶部元素¶

element = min_heap_peek(heap);

heap：指向要从中检索最小元素的最小堆的指针。

此宏返回指向堆的最小元素（根）的指针，如果堆为空，则返回 NULL。该操作为 O(1)。

内联版本： min_heap_peek_inline(heap)

堆插入¶

success = min_heap_push(heap, element, callbacks, args);

heap：指向应插入元素的最小堆的指针。
element：指向要插入到堆中的元素的指针。
callbacks：指向提供 less 和 swp 函数的 struct min_heap_callbacks 的指针。
args：传递给 less 和 swp 函数的可选参数。

此宏将元素插入到堆中。如果插入成功，则返回 true，如果堆已满，则返回 false。该操作为 O(log n)。

内联版本： min_heap_push_inline(heap, element, callbacks, args)

堆删除¶

success = min_heap_pop(heap, callbacks, args);

heap：指向要从中删除最小元素的最小堆的指针。
callbacks：指向提供 less 和 swp 函数的 struct min_heap_callbacks 的指针。
args：传递给 less 和 swp 函数的可选参数。

此宏从堆中删除最小元素（根）。如果元素已成功删除，则返回 true，如果堆为空，则返回 false。该操作为 O(log n)。

内联版本： min_heap_pop_inline(heap, callbacks, args)

堆维护¶

您可以使用以下宏来维护堆的结构：

min_heap_sift_down(heap, pos, callbacks, args);

heap：指向最小堆的指针。
pos：开始向下筛选的索引。
callbacks：指向提供 less 和 swp 函数的 struct min_heap_callbacks 的指针。
args：传递给 less 和 swp 函数的可选参数。

此宏通过将指定索引 (pos) 处的元素向下移动到堆中，直到其处于正确位置，从而恢复堆属性。该操作为 O(log n)。

内联版本： min_heap_sift_down_inline(heap, pos, callbacks, args)

min_heap_sift_up(heap, idx, callbacks, args);

heap：指向最小堆的指针。
idx：要向上筛选的元素的索引。
callbacks：指向提供 less 和 swp 函数的 struct min_heap_callbacks 的指针。
args：传递给 less 和 swp 函数的可选参数。

此宏通过将指定索引 (idx) 处的元素向上移动到堆中，从而恢复堆属性。该操作为 O(log n)。

内联版本： min_heap_sift_up_inline(heap, idx, callbacks, args)

min_heapify_all(heap, callbacks, args);

heap：指向最小堆的指针。
callbacks：指向提供 less 和 swp 函数的 struct min_heap_callbacks 的指针。
args：传递给 less 和 swp 函数的可选参数。

此宏确保整个堆都满足堆属性。当从头构建堆或经过多次修改后调用它。该操作为 O(n)。

内联版本： min_heapify_all_inline(heap, callbacks, args)

删除特定元素¶

success = min_heap_del(heap, idx, callbacks, args);

heap：指向最小堆的指针。
idx：要删除的元素的索引。
callbacks：指向提供 less 和 swp 函数的 struct min_heap_callbacks 的指针。
args：传递给 less 和 swp 函数的可选参数。

此宏从堆中删除指定索引 (idx) 处的元素并恢复堆属性。该操作为 O(log n)。

内联版本： min_heap_del_inline(heap, idx, callbacks, args)

其他实用工具¶

min_heap_full(heap)：检查堆是否已满。复杂度：O(1)。

bool full = min_heap_full(heap);

heap：指向要检查的最小堆的指针。

如果堆已满，则此宏返回 true，否则返回 false。

内联版本： min_heap_full_inline(heap)

min_heap_empty(heap)：检查堆是否为空。复杂度：O(1)。

bool empty = min_heap_empty(heap);

heap：指向要检查的最小堆的指针。

如果堆为空，则此宏返回 true，否则返回 false。

内联版本： min_heap_empty_inline(heap)

使用示例¶

最小堆 API 的一个使用示例将涉及定义一个堆结构、对其进行初始化，以及根据需要插入和删除元素。

#include <linux/min_heap.h>

int my_less_function(const void *lhs, const void *rhs, void *args) {
    return (*(int *)lhs < *(int *)rhs);
}

struct min_heap_callbacks heap_cb = {
    .less = my_less_function,    /* Comparison function for heap order */
    .swp  = NULL,                /* Use default swap function */
};

void example_usage(void) {
    /* Pre-populate the buffer with elements */
    int buffer[5] = {5, 2, 8, 1, 3};
    /* Declare a min-heap */
    DEFINE_MIN_HEAP(int, my_heap);

    /* Initialize the heap with preallocated buffer and size */
    min_heap_init(&my_heap, buffer, 5);

    /* Build the heap using min_heapify_all */
    my_heap.nr = 5;  /* Set the number of elements in the heap */
    min_heapify_all(&my_heap, &heap_cb, NULL);

    /* Peek at the top element (should be 1 in this case) */
    int *top = min_heap_peek(&my_heap);
    pr_info("Top element: %d\n", *top);

    /* Pop the top element (1) and get the new top (2) */
    min_heap_pop(&my_heap, &heap_cb, NULL);
    top = min_heap_peek(&my_heap);
    pr_info("New top element: %d\n", *top);

    /* Insert a new element (0) and recheck the top */
    int new_element = 0;
    min_heap_push(&my_heap, &new_element, &heap_cb, NULL);
    top = min_heap_peek(&my_heap);
    pr_info("Top element after insertion: %d\n", *top);
}

Linux 内核

目录

本页