Min Heap API

Min Heap API 소개

SPDX license 식별자는 GPL-2.0입니다.

Min Heap API

저자: Kuan-Wei Chiu <visitorckw@gmail.com>

소개 (Introduction)

Min Heap API는 Linux kernel에서 min-heap을 관리하는 function과 macro 집합을 제공합니다. Min-heap은 각 node의 값이 child 값보다 작거나 같은 binary tree structure이므로 가장 작은 element가 항상 root에 있습니다.

이 문서는 min-heap을 정의하고 사용하는 방법을 자세히 설명합니다. 사용자는 `__min_heap_*()` prefix가 붙은 function을 직접 호출하지 말고 제공되는 macro wrapper를 사용해야 합니다.

표준 version 외에도 성능이 중요한 상황을 위한 inline version이 있습니다. Inline function은 non-inline function과 같은 이름에 `_inline` suffix를 붙입니다. 예를 들어 `__min_heap_init_inline`의 macro wrapper는 `min_heap_init_inline`입니다. Inline version은 custom comparison과 swap function을 indirect function call 대신 직접 호출하므로 overhead를 크게 줄일 수 있습니다. 특히 `CONFIG_MITIGATION_RETPOLINE`을 활성화하면 indirect function call 비용이 커지므로 효과가 큽니다. Non-inline version과 마찬가지로 function을 직접 호출하지 말고 macro wrapper를 사용해야 합니다.

Min-heap data structure 정의

Data Structures

Min-Heap Definition

Min-heap의 핵심 data structure는 `MIN_HEAP_PREALLOCATED`와 `DEFINE_MIN_HEAP` macro로 정의합니다. 이 macro를 사용하면 preallocated buffer 또는 동적으로 할당한 memory를 사용하는 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)

일반적인 heap structure에는 element 수를 나타내는 `nr`, heap의 최대 capacity인 `size`, element array pointer인 `data`가 포함됩니다. `MIN_HEAP_PREALLOCATED`를 사용하면 preallocated heap storage를 위한 static array를 선택적으로 지정할 수 있습니다.

Min Heap callback

Min Heap Callbacks

`struct min_heap_callbacks`는 heap element ordering과 swap 동작을 custom하게 지정합니다. 두 function pointer를 포함합니다.

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

• `less`는 element 순서를 정하는 comparison function입니다.
• `swp`는 heap의 element를 교환하는 function입니다. `swp`를 `NULL`로 설정하면 element size를 기준으로 교환하는 기본 swap function을 사용합니다.

Macro wrapper와 heap 초기화

Macro Wrappers

Heap을 사용자 친화적으로 다루기 위해 다음 macro wrapper를 제공합니다. 각 macro는 heap을 조작하는 function에 대응하며 internal function의 직접 호출을 감춥니다. 각 macro의 parameter는 아래에서 설명합니다.

Heap Initialization

min_heap_init(heap, data, size);

• `heap`: 초기화할 min-heap structure pointer입니다.
• `data`: heap element를 저장할 buffer pointer입니다. `NULL`이면 heap structure 안의 preallocated buffer를 사용합니다.
• `size`: heap이 담을 수 있는 최대 element 수입니다.

이 macro는 heap을 초기 상태로 설정합니다. `data`가 `NULL`이면 heap structure 내부의 preallocated memory를 사용하고, 그렇지 않으면 사용자가 제공한 buffer를 사용합니다. 시간 복잡도는 `O(1)`입니다.

Inline version은 `min_heap_init_inline(heap, data, size)`입니다.

최솟값 접근

Top element 접근 (Accessing the Top Element)

element = min_heap_peek(heap);

• `heap`: 가장 작은 element를 가져올 min-heap pointer입니다.

이 macro는 heap의 가장 작은 element, 즉 root의 pointer를 반환합니다. Heap이 비어 있으면 `NULL`을 반환합니다. 시간 복잡도는 `O(1)`입니다.

Inline version은 `min_heap_peek_inline(heap)`입니다.

Heap insertion

Heap Insertion

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

• `heap`: element를 insert할 min-heap pointer입니다.
• `element`: heap에 insert할 element pointer입니다.
• `callbacks`: `less`와 `swp` function을 제공하는 `struct min_heap_callbacks` pointer입니다.
• `args`: `less`와 `swp` function에 전달할 optional argument입니다.

이 macro는 heap에 element를 insert합니다. 성공하면 `true`, heap이 가득 차 있으면 `false`를 반환합니다. 시간 복잡도는 `O(log n)`입니다.

Inline version은 `min_heap_push_inline(heap, element, callbacks, args)`입니다.

Heap removal

Heap Removal

success = min_heap_pop(heap, callbacks, args);

• `heap`: 가장 작은 element를 제거할 min-heap pointer입니다.
• `callbacks`: `less`와 `swp` function을 제공하는 `struct min_heap_callbacks` pointer입니다.
• `args`: `less`와 `swp` function에 전달할 optional argument입니다.

이 macro는 heap의 가장 작은 element, 즉 root를 제거합니다. 성공하면 `true`, heap이 비어 있으면 `false`를 반환합니다. 시간 복잡도는 `O(log n)`입니다.

Inline version은 `min_heap_pop_inline(heap, callbacks, args)`입니다.

Heap property 유지

Heap Maintenance

다음 macro를 사용하여 heap structure를 유지할 수 있습니다.

min_heap_sift_down(heap, pos, callbacks, args);

• `heap`: min-heap pointer입니다.
• `pos`: sift down을 시작할 index입니다.
• `callbacks`: `less`와 `swp` function을 제공하는 `struct min_heap_callbacks` pointer입니다.
• `args`: `less`와 `swp` function에 전달할 optional argument입니다.

`min_heap_sift_down()`은 지정 index `pos`의 element를 올바른 위치에 도달할 때까지 heap 아래쪽으로 이동해 heap property를 복원합니다. 시간 복잡도는 `O(log n)`입니다. Inline version은 `min_heap_sift_down_inline(heap, pos, callbacks, args)`입니다.

min_heap_sift_up(heap, idx, callbacks, args);

• `heap`: min-heap pointer입니다.
• `idx`: 위쪽으로 sift할 element의 index입니다.
• `callbacks`: `less`와 `swp` function을 제공하는 `struct min_heap_callbacks` pointer입니다.
• `args`: `less`와 `swp` function에 전달할 optional argument입니다.

`min_heap_sift_up()`은 지정 index `idx`의 element를 heap 위쪽으로 이동해 heap property를 복원합니다. 시간 복잡도는 `O(log n)`입니다. Inline version은 `min_heap_sift_up_inline(heap, idx, callbacks, args)`입니다.

min_heapify_all(heap, callbacks, args);

• `heap`: min-heap pointer입니다.
• `callbacks`: `less`와 `swp` function을 제공하는 `struct min_heap_callbacks` pointer입니다.
• `args`: `less`와 `swp` function에 전달할 optional argument입니다.

`min_heapify_all()`은 heap 전체가 heap property를 만족하도록 합니다. Heap을 처음부터 만들거나 많은 수정 뒤에 호출합니다. 시간 복잡도는 `O(n)`입니다. Inline version은 `min_heapify_all_inline(heap, callbacks, args)`입니다.

특정 element 제거

Removing Specific Elements

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

• `heap`: min-heap pointer입니다.
• `idx`: 삭제할 element의 index입니다.
• `callbacks`: `less`와 `swp` function을 제공하는 `struct min_heap_callbacks` pointer입니다.
• `args`: `less`와 `swp` function에 전달할 optional argument입니다.

`min_heap_del()`은 지정 index `idx`의 element를 제거하고 heap property를 복원합니다. 시간 복잡도는 `O(log n)`입니다.

Inline version은 `min_heap_del_inline(heap, idx, callbacks, args)`입니다.

Heap 상태 utility

Other Utilities

• `min_heap_full(heap)`은 heap이 가득 찼는지 검사합니다. 시간 복잡도는 `O(1)`입니다.
• `min_heap_empty(heap)`는 heap이 비어 있는지 검사합니다. 시간 복잡도는 `O(1)`입니다.

bool full = min_heap_full(heap);

`heap`은 검사할 min-heap pointer입니다. `min_heap_full()`은 heap이 가득 찼으면 `true`, 아니면 `false`를 반환합니다. Inline version은 `min_heap_full_inline(heap)`입니다.

bool empty = min_heap_empty(heap);

`heap`은 검사할 min-heap pointer입니다. `min_heap_empty()`는 heap이 비어 있으면 `true`, 아니면 `false`를 반환합니다. Inline version은 `min_heap_empty_inline(heap)`입니다.

Min Heap API 사용 예제

Example Usage

Min-heap API의 일반적인 사용은 heap structure를 정의하고 초기화한 뒤 필요에 따라 element를 insert하거나 제거하는 과정으로 구성됩니다.

#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/min_heap.h>`를 include하고 integer 비교 function `my_less_function()`과 기본 swap을 사용하는 `heap_cb`를 정의합니다. `DEFINE_MIN_HEAP(int, my_heap)`으로 heap을 선언하고 다섯 element가 든 buffer로 초기화합니다.

`my_heap.nr`을 5로 설정한 뒤 `min_heapify_all()`로 heap property를 구성합니다. `min_heap_peek()`은 1을 반환하고, `min_heap_pop()`으로 1을 제거한 다음에는 2가 top이 됩니다. 마지막으로 0을 `min_heap_push()`하면 새 top은 0이 됩니다.