# 2019-06-04 劉溢茗

## Q1: 給定兩個整數 x 及 y，用 bitwise operator 做出兩者平均值
`int mean(int x, int y) { ... }`
Hint: 可用 `&`, `^`, `|`, `+`. `>>`, `<<` 等運算子
=>

int mean(int x,int y){
 // int od1 = 1 & x; 
 // int od2 = 1 & y;
 // int z = ( >>1) + (od2 >>1)
// x^=1; 
// y^=1; 

return (((x ^ y)>>1) + (x & y));
// if (od1 && od2){
//         mean++;
//     }
}

---

## Q2: 以 Linux 核心的 [include/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 實作出兩個節點互換 (不得複製節點內全部的資料)
Hint: 考慮到 HEAD 可能跟其他節點互換
=>
swapping node x and node y

static inline void _swap(struct list_head *head,
                         struct list_head *x, 
                         struct list_head *y){
    if (list_empty(head) || x==y) return;
    struct list_head tmp;
    // if(list_is_first(x,head)){
    //     head = y;
    // }else if(list_is_first(y,head)){
    //     head = x;
    // }
    list_replace(y,&tmp);
    list_replace(x,y);
    list_replace(&tmp,x);
}

---

假設上圖 head(x) 和 y 進行交換後


結果如上，會造成 first entry 位置改變

### 版本 2:

#include "list.h"
#include <stdio.h>
#include <stdlib.h>

struct listitem {
  struct list_head list;
  int i;
};

static inline void _swap(struct list_head *list, struct list_head *x,struct list_head *y) {
    if (list_empty(list) || x==y) return;
    list_replace(y,&tmp);
    list_replace(x,y);
    list_replace(&tmp,x);
}

int main() {
    struct list_head *list;
    struct listitem *entry, *next, *item;
    INIT_LIST_HEAD(list);
    
    for (int i = 0; i < 4; i++) {
    item = (struct listitem *)malloc(sizeof(struct listitem));
    item->i = i;
    list_add_tail(&item->list, list);
    }
    
    struct list_head *x
    _swap(list, list, &(list->prev->prev)->list);
    
    list_for_each_entry_safe(entry, next, list, list) {
    list_del(&entry->list);
    free(entry);
    }
}

##### 上述程式碼預期行為


* _swap 後


因為只動指標的關係，不會影響節點內部的資料
但是 swap 後 first entry 由 0 變 3

:::danger
先改善標注方式，原本的 head~1~ 在操作後應改為 head~2~, 由於 linked list 主要用途就是在「非連續的記憶體單元之間連接」，所以這裡的 swap 本該只做前後關聯的調整。

回頭思考 [How does the kernel implements Linked Lists?](https://kernelnewbies.org/FAQ/LinkedLists)，我們應該善用 Linux 核心提供的 macro / inlined functions 來實作。

請愛用 GraphViz。
:notes: jserv
:::

---

## Q3: 在 Linux 核心中，要取得 (acquire) semaphore，該用哪個 API?
* `(a)` `up()`
* `(b)` `up_trylock()`
* `(c)` `up_interruptible()`
* `(d)` `down()`
* `(e)` `down_tryonce()`
* `(f)` `down_trylock()`
* `(g)` `down_interrupt()`

----