2019q1 第 3 週測驗題 (下)

目的: 檢驗學員對 C 程式設計的認知

---

測驗 1

以下程式碼是個 XOR linked list 的實作，在這樣的資料結構可表示為:

       1    2    3    4
data  HAT  CAT  EAT  BAT
link   2    2    6    3

要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 HAT (1), 已知前一格是 (0)，那麼下一格就是 link(1) XOR 0 = 2 XOR 0 = 2，也就是 CAT。繼續，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，依此類推。只要當找出來的下一格是 (0) 就結束。

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

typedef struct {
    unsigned long lxr;
    int data1, data2;
} item; 
item *lh = NULL;
        
typedef struct { item *left, *right; } lxr_info; 
        
void print_at(lxr_info *p_lxri, item *pli) {   
    if (pli)
        printf("data1 = %d, data2 = %d\n", pli->data1, pli->data2);
}

static inline item *extract_address(item *lxr, item *other) {
    return (item *) (lxr->lxr ^ (unsigned long) other);
}   

static inline void shift_lxr(item *lxr, item *known, item *update) {
    lxr->lxr = (lxr->lxr ^ (unsigned long) known) ^ (unsigned long) update;
}

/* Walk the list starting at the header */
void list_walk(void) {
    item *pcur = lh;
    lxr_info lxri = {.left = NULL, .right = NULL};
    lxri.right = extract_address(pcur, lxri.left);
    while (pcur) {
        print_at(&lxri, pcur);
        pcur = lxr_move_right(&lxri, pcur);
    }
}

/* Append an item where we are */
item *append_item(lxr_info *p_lxri, item *p_current, int d1, int d2) {
    item *p_this, *p_left, *p_right;
    if ((p_this = calloc(1, sizeof(item)))) {
        p_left = p_lxri->left = p_current;
        p_right = p_lxri->right;
        UCCU;
        VCCV;
        p_this->lxr = (unsigned long) p_current ^ (unsigned long) p_lxri->right;
        p_this->data1 = d1;
        p_this->data2 = d2;
    }
    return p_this;
}

int main(int argc, char **argv) {
    int index = 0;
    int maxrun = 20;
    item *pcur = lh, *pnli;
    lxr_info lxri = {.left = NULL, .right = NULL};

    while (index < maxrun) {
        if ((pnli = append_item(&lxri, pcur, 3 * index, 3 * index + 1)) ==
            NULL) {
            exit(2);
        }
        pcur = pnli;
        if (!lh)
            lh = pcur;
        index++;
    }

    list_walk();
    return 0;
}                          

請補完程式碼。

作答區

UCCU = ?

• (a) shift_lxr(p_left, p_right, p_this);
• (b) shift_lxr(p_right, p_left, p_this);
• (c) if (p_left) shift_lxr(p_left, p_right, p_this);
• (d) shift_lxr(p_this ? p_left: p_right, p_this, p_this)
• (e) shift_lxr(p_this ? p_right: p_left, p_this, p_this)

VCCV = ?

• (a) shift_lxr(p_left, p_right, p_this);
• (b) shift_lxr(p_right, p_left, p_this);
• (c) if (p_right) (p_right, p_left, p_this);
• (d) shift_lxr(p_this ? p_left: p_right, p_this, p_this)
• (e) shift_lxr(p_this ? p_right: p_left, p_this, p_this)

延伸問題:

1. 設計實驗探討 XOR linked list 的記憶體開銷，相較於典型的設計，能省多少呢？
2. 在 Linux 核心原始程式碼找出特製的 linked list，並予以解說

---

測驗 1

考慮以下實作 Reference counting 的程式碼:

#include <stddef.h>                                                                                                                                           
#include <stdio.h>
#include <stdlib.h>
        
struct ref {
    void (*free)(const struct ref *);
    int count;
};  
static inline void ref_inc(const struct ref *ref) {
    ((struct ref *) ref)->count++;
}   
    
static inline void ref_dec(const struct ref *ref) {
    if (--((struct ref *) ref)->count == 0)
        ref->free(ref);
}
    
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))

struct node {
    char id[64];
    float value;
    struct node *next;
    struct ref refcount;
};      
    
static void node_free(const struct ref *ref) {
    struct node *node = container_of(ref, struct node, refcount);
    struct node *child = node->next;
    free(node);
    ABA;
}

struct node *node_create(char *id, float value) {
    struct node *node = malloc(sizeof(*node));
    snprintf(node->id, sizeof(node->id), "%s", id);
    node->value = value;
    node->next = NULL;
    node->refcount = (struct ref){node_free, 1};
    return node;
}

void node_push(struct node **nodes, char *id, float value) {
    struct node *node = node_create(id, value);
    node->next = *nodes;
    *nodes = node;
}

struct node *node_pop(struct node **nodes) {
    struct node *node = *nodes;
    *nodes = (*nodes)->next;
    if (*nodes)
        CDC;
    return node;
}
    
void node_dump(struct node *node) {
    for (; node; node = node->next)
        printf("%s = %f\n", node->id, node->value);
}
    
int main(void) {
    struct node *nodes = NULL;
    char id[64];
    float value;
    node_push(&nodes, "foo", 0.1f);
    node_dump(nodes);
    struct node *old = node_pop(&nodes);
    node_push(&nodes, "bar", 0.2f);
    node_dump(nodes);
    ref_dec(&old->refcount);
    ref_dec(&nodes->refcount);
    return 0;
}

請補完程式碼。

作答區

ABA = ?

• (a) ref_dec(child->ref_dec)
• (b) if (child) ref_dec(child->ref_dec)
• (c) if (child) ref_dec(*child->ref_dec)
• (d) if (child) ref_dec(&child->refcount);

CDC = ?

• (a) ref_inc(*nodes->refcount)
• (b) ref_inc((*node)->refcount)
• (c) ref_inc(&*nodes->refcount)
• (d) ref_inc((*nodes).refcount)
• (e) ref_inc(&(*nodes)->refcount)
• (f) ref_inc(*nodes)

延伸問題:

1. 這個 reference counting 實作沒考慮到 thread safety，請著手改善並設計驗證機制;
2. 在 Linux 核心找出類似的 reference counting 程式碼並解說;