# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 15 週測驗題
###### tags: `linux2022`

:::info
目的: 檢驗學員對 **[針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model)** 和 **[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)** 的認知
:::

作答表單:
* ==[測驗 `1`](https://docs.google.com/forms/d/e/1FAIpQLSfhuSGXXfC4TcupHhYA6KBv1eNdIMapBkwq4qOk7HyMNG2lxQ/viewform)== (Linux 核心設計)

### 測驗 `1`

在作業 [seHTTPd](https://hackmd.io/@sysprog/linux2022-sehttpd) 和 [高效 Web 伺服器開發](https://hackmd.io/@sysprog/fast-web-server) 論及 HTTP 連線管理時，Web 伺服器和客戶端網頁瀏覽器保持著一個長期連線的狀況下，遇到客戶端網路離線，通訊協定無法立刻知悉，所以僅能透過伺服器引入 timer 逾時事件來克服。timer 可透過 priority queue 實作，後者又常用 binary heap 實作。
> [Priority Queue：Binary Heap](https://alrightchiu.github.io/SecondRound/priority-queuebinary-heap.html)

以下是 [min heap](https://en.wikipedia.org/wiki/Binary_heap) 的一個實作:

#include <assert.h>
#include <inttypes.h>
#include <stdint.h>

struct heap_item {
    uint64_t key;
};

#if __WORDSIZE == 64
#define clz64(x) __builtin_clzl(x)
#define clz32(x) __builtin_clz(x)
#define log2_floor(x) log2_floor64(x)
#elif __WORDSIZE == 32
#define clz64(x) __builtin_clzll(x)
#define clz32(x) __builtin_clzl(x)
#define log2_floor(x) log2_floor32(x)
#else
#error "Bad machine word size"
#endif

static inline unsigned int log2_floor64(uint64_t val)
{
    return 64 - (clz64(val) + 1);
}

static inline unsigned int log2_floor32(uint32_t val)
{
    return 32 - (clz32(val) + 1);
}

static inline unsigned long parent(unsigned long idx)
{
    return idx >> 1;
}

static inline unsigned long left(unsigned long idx)
{
    return idx << 1;
}

static inline unsigned long right(unsigned long idx)
{
    return (idx << 1) + 1;
}

static void do_sift_up(unsigned long idx,
                       unsigned long nr_items,
                       struct heap_item *h)
{
    assert(idx > 0);
    if (idx == 1)
        return;

    uint64_t v = h[idx].key;
    unsigned long pidx = parent(idx);
    uint64_t pv = h[pidx].key;
    if (UUUU)
        return;

    struct heap_item tmp = h[pidx];
    h[pidx] = h[idx];
    h[idx] = tmp;
    do_sift_up(pidx, nr_items, h);
}

static void do_sift_down(unsigned long idx,
                         unsigned long nr_items,
                         struct heap_item *h)
{
    unsigned long l = left(idx);
    if (l > nr_items)
        return;

    unsigned long r = right(idx);
    unsigned long smallest;
    if (r > nr_items) {
        smallest = l;
    } else {
        smallest = h[l].key < h[r].key ? l : r;
    }

    if (DDDD)
        return;

    struct heap_item tmp = h[smallest];
    h[smallest] = h[idx];
    h[idx] = tmp;
    do_sift_down(smallest, nr_items, h);
}

void minheap_init(unsigned long nr_items, struct heap_item *h)
{
    unsigned long lf = log2_floor(nr_items);
    unsigned long f = (1 << lf) - 1, c = (1 << lf);

    for (unsigned long i = f; i < nr_items; i++)
        do_sift_up(i + 1, nr_items, h);

    c = (c - (nr_items - f)) >> 1;
    for (unsigned long i = parent(nr_items); i < parent(nr_items) + c; i++)
        do_sift_up(i + 1, nr_items, h);
}

void minheap_sift_down(unsigned long nr_items, struct heap_item *h)
{
    do_sift_down(1, nr_items, h);
}

void minheap_sift_up(unsigned long nr_items, struct heap_item *h)
{
    do_sift_up(nr_items, nr_items, h);
}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void print_heap(unsigned long nr_items, struct heap_item *h)
{
    for (unsigned long i = 0; i < nr_items; i++)
        printf("%" PRId64 " ", h[i + 1].key);
    printf("\n");
}

static unsigned int xs;
/* 16-Bit Xorshift Pseudorandom Numbers.
 * http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html
 */
static inline unsigned int xorshift()
{
    xs ^= xs << 7;
    xs ^= xs >> 9;
    xs ^= xs << 8;
    return xs;
}

int main(int argc, char **argv)
{
    unsigned long nr = atoi(argv[1]);
    struct heap_item *h = calloc(nr, sizeof(*h));
    h--;

    xs = getpid();
    for (unsigned long i = 0; i < nr; i++)
        h[i + 1].key = xorshift() & 127;
    printf("init: ");
    print_heap(nr, h);

    minheap_init(nr, h);
    printf("heapified: ");
    print_heap(nr, h);

    while (nr) {
        printf("%" PRId64 ": ", h[1].key);
        h[1] = h[nr--];
        minheap_sift_down(nr, h);
        print_heap(nr, h);
    }

    printf("\n");

    h[++nr].key = 100;
    minheap_sift_up(nr, h);

    h[++nr].key = 300;
    minheap_sift_up(nr, h);

    h[++nr].key = 200;
    minheap_sift_up(nr, h);

    while (nr) {
        printf("%" PRId64 ": ", h[1].key);
        h[1] = h[nr--];
        minheap_sift_down(nr, h);
        print_heap(nr, h);
    }
    return EXIT_SUCCESS;
}

參考執行輸出: (前 10 個數值可能會變化)

$ ./minheap 10
init: 95 62 66 71 36 34 67 30 72 82 
heapified: 30 95 34 62 36 66 67 71 72 82 
30: 34 95 66 62 36 82 67 71 72 
34: 66 95 67 62 36 82 72 71 
66: 67 95 71 62 36 82 72 
67: 71 95 72 62 36 82 
71: 72 95 82 62 36 
72: 36 95 82 62 
36: 62 95 82 
62: 82 95 
82: 95 
95: 

100: 200 300 
200: 300 
300: 

請補完程式碼，使其運作符合預期。作答規範:
* `UUUU` 和 `DDDD` 皆為表示式，且有 ==`<`== 運算子，不包含小括號 (即 `(` 和 `)`)
* 以合法且最精簡的 C99 語法撰寫

:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 將上述實作整合進 [seHTTPd](https://github.com/sysprog21/sehttpd)
:::

---

#### 修正
根據 kdnvt 同學的觀察，使用上述程式碼考慮以下情境:

digraph BST {
    node [fontname="Arial" ];
    l1  [ label = "100" ];
    l21 [ label = "2" ];
    l22 [ label = "3" ];
    l31 [ label = "4" ];
    
    l32 [label = "5" ];
    l33 [color=red shape=rect label = "6" ];
    l34 [color=red shape=rect label = "7" ];
    l41 [color=blue shape=rect label = "8" ];
    l42 [color=blue shape=rect label = "9" ];
    l43 [color=blue shape=rect label = "10" ];
    l1  -> { l21 l22 };
    l21 -> { l31 l32 };
    l22 -> { l33 l34 };
    
    l31 -> { l41 l42 };
    l32 -> { l43}
}

原版程式在檢查後發現 8, 9, 10 的 parent 都比較小後就不會繼續遞迴往上 heapify。同理， 6, 7 的 parent 小於兩者，所以不會繼續往更上面的 node 做 heapify。但是除了 3, 4, 5，我們不能保證其他節點的位置是否正確，因此可以透過修改 do_sift_up 來確保正確性:

static void do_sift_up(unsigned long idx,
                       unsigned long nr_items,
                       struct heap_item *h)
{
...
    if (pv < v){
        do_sift_up(pidx, nr_items, h);
        return;
    }
...
}

當 parent 小於 child 時不會中止遞迴，會繼續往 parent 上檢查。