最小堆 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 核心

目錄

本頁