2019q1 第 11 週測驗題 (中)

目的: 檢驗學員對 linked list 實作的技巧

測驗 `1`

給定一個 circular linked list 實作如下: (檔案 list.h)

#ifndef INTERNAL_LIST_H
#define INTERNAL_LIST_H

/* circular doubly-linked list */
typedef struct __list_t {
    struct __list_t *prev, *next;
} list_t;

/*
 * Initialize a list to empty. Because these are circular lists, an "empty"
 * list is an entry where both links point to itself. This makes insertion
 * and removal simpler because they do not need any branches.
 */
static inline void list_init(list_t *list) {
    list->prev = list;
    list->next = list;
}

/*
 * Append the provided entry to the end of the list. This assumes the entry
 * is not in a list already because it overwrites the linked list pointers.
 */
static inline void list_push(list_t *list, list_t *entry) {
    list_t *prev = list->prev;
    entry->prev = prev;
    entry->next = list;
    prev->next = entry;
    list->prev = entry;
}

/*
 * Remove the provided entry from whichever list it is currently in. This
 * assumes that the entry is in a list. You do not need to provide the list
 * because the lists are circular, so the list's pointers will automatically
 * be updated if the first or last entries are removed.
 */
static inline void list_remove(list_t *entry) {
    list_t *prev = entry->prev;
    list_t *next = entry->next;
    prev->next = next;
    next->prev = prev;
}

/*
 * Remove and return the first entry in the list or NULL if the list is empty.
 */
static inline list_t *list_pop(list_t *list) {
    list_t *foo = list->prev;
    if (foo == list)
        return NULL;
    LL1
}
#endif

請參照上方程式註解，補完對應程式碼。

作答區

LL1 = ?

(a) return foo;
(b) return foo->next;
(c) return foo->prev;
(d) list_remove(foo->prev); return foo;
(e) list_remove(foo); return foo;
(f) list_remove(foo->next); return foo->next;
(g) list_remove(foo); return foo->next;

延伸問題:

研讀 2019q3 Week11 的 cache-oblivious data structures 參考資料，記錄所見所聞;
依據之前給定的 Linux 核心 linked list 實作，開發 cache-oblivious 的版本，並證實其效益;
實作 Skip list，並且比照之前的 unit test 提供對應的測試、效能分析，還有改善機制

2019q1 第 11 週測驗題 (中)

測驗 1

測驗 `1`