# 2019-06-03 方鈺學

## Q1: 假設 cacheline 是 16B，且在 x86_64 架構，改寫下方程式以降低記憶體操作的成本

/* zero-v1.c */
#include <stdbool.h>
bool mem_is_zero(const void *data, size_t length) {
    const unsigned char *p = data;
    while (length) {   
        if (*p)
            return false;
        p++;
        length--;
    }   
    return true;
}

Hint: [strlen 的最佳化](https://hackmd.io/s/BkRKhQGae#%E9%81%8B%E7%94%A8-bit-wise-operator)
=>

#include <stdbool.h>
#define detect(X)(((X) - 0x01010101) & ~(X) & 0x80808080)

bool mem_is_zero(const void *data, size_t length) {
    const unsigned char *p = data;
    while(length){
        p += 
        if(!detect)
    
    }
    
}

:notes:
考慮以下:

/* zero-v2.c */
bool mem_is_zero(const void *data, size_t length)
{
    const uint8_t *p = data;
    const uint64_t zero[2] = { 0 };

    size_t pre = (size_t) (p) & (sizeof(zero) − 1);

    if (pre) {
        if (memcmp(p, &zero, length) != 0)
            return false;
        p += length;                                     
    }
    while (length > sizeof(zero)) {
        if ((*(uint64_t *) p ) != zero)
            return false;
        p += (sizeof(zero));
        length -= (sizeof(zero));
    }
    return memcmp(&zero, p, length) == 0;
}

---

## Q2: 透過 Linux 核心的 linked list APIs，給定 head，找出 list 內數值最大的節點。假設節點內的數值都是正整數
=>

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

int find_largest(struct list_head *head){
    int n = 0;
    struct list_head* pos = NULL;
    pos = head->next;
    list_for_each(pos ,head){
        if(n < list_entry(pos,struct listitem, list)->i)
            n = list_entry(pos,struct listitem, list)->i;
    }
    return n;
}

---

## Q3: 承 Q2，將給定的 list 中數值最大的節點移除
Hint: 要考慮到 head 本身就是最大數值的狀況

void cut_largest(struct list_head *head)
{

    struct list_head* pos = head -> next;
    struct list_head* target = head ->next;
    list_for_each(pos,head){
        if(list_entry(target, struct listitem, list)-> i < list_entry(pos, struct listitem, list)->i )
            target = pos;
    }
    struct list_head** node = &head -> next;
    
    while(*node != target)
        node = &(*node)->next;
    *node = target -> next;
}

---