最小堆 API¶

作者:: Kuan-Wei Chiu <visitorckw@gmail.com>

简介¶

最小堆 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 {
    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)

一个典型的堆结构将包括一个元素计数器 (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 内核

目录

本页