目的: 檢驗學員對 C 語言程式設計, alignment, bitwise, preprocessor 的認知
作答表單: 測驗 1 (針對 Linux 核心「設計」課程)
作答表單: 測驗 2-3 (針對 Linux 核心「實作」課程)
測驗 1
延續第 3 週測驗題，我們想改寫 Linux 核心的紅黑樹 的實作，進一步精簡紅黑樹節點佔用的空間，如下:
注意親代節點不保存於 rb_node 中，right_red 運用 C 語言：記憶體管理、對齊及硬體特性 和 C 語言: bitwise 操作 提及的指標地址對齊特性。以下是 C++ 測試程式碼:
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <random>
#include "rb.h"
using std::cout;
using std::endl;
struct node_;
typedef struct node_ node_t;
struct node_ {
rb_node(node_t) link;
int key;
};
static int node_cmp(const node_t *a, const node_t *b)
{
int ret = (a->key > b->key) - (a->key < b->key);
if (ret == 0 && a != b)
assert(0 && "Duplicates are not allowed in the tree");
return (ret);
}
typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);
typedef int value_t;
enum {
LEFT = 0,
RIGHT = 1,
NEITHER = 3,
};
typedef int direction;
struct node_s;
class node
{
public:
node() : m_node(NULL) {}
explicit node(node_s *n) : m_node(n) {}
node_s *operator->() const { return as_node(); }
explicit operator bool() const { return m_node != NULL; }
int longer() const { return uintptr_t(m_node) & 3; }
void set_longer(int longer)
{
assert(m_node);
m_node = (node_s *) ((intptr_t(m_node) & ssize_t(-4)) | longer);
}
bool balanced() const { return (uintptr_t(m_node) & 2) != 0; }
bool operator==(const node &other) const
{
return as_node() == other.as_node();
}
bool operator!=(const node &other) const
{
return as_node() != other.as_node();
}
private:
node_s *as_node() const
{
return (node_s *) (intptr_t(m_node) & ssize_t(-4));
}
node_s *m_node;
};
struct node_s {
value_t value;
node next[2];
};
int dir_check_depth(node tree)
{
if (!tree)
return 0;
int err = 0;
int rv;
int b = dir_check_depth(tree->next[LEFT]);
int f = dir_check_depth(tree->next[RIGHT]);
if (b == f) {
if (!tree.balanced())
err = 1;
rv = b + 1;
} else if (b == f - 1) {
if (tree.longer() != RIGHT)
err = 1;
rv = f + 1;
} else if (b - 1 == f) {
if (tree.longer() != LEFT)
err = 1;
rv = b + 1;
} else {
err = 1;
rv = 0;
}
if (err)
printf("err at %d: b=%d f=%d longer=%d\n", tree->value, b, f,
tree.longer());
return rv;
}
std::pair<unsigned int, unsigned long long> doGetGepth(node_t *tree,
node_t *null,
unsigned int level)
{
if (tree == null)
return std::make_pair(0U, 0ULL);
auto left(doGetGepth(rbtn_left_get(node_t, link, tree), null, level + 1)),
right(doGetGepth(rbtn_right_get(node_t, link, tree), null, level + 1));
return {1U + left.first + right.first, left.second + right.second + level};
}
std::pair<unsigned int, unsigned long long> doGetGepth(node tree,
node null,
unsigned int level)
{
if (tree == null)
return std::make_pair(0U, 0ULL);
auto left(doGetGepth(tree->next[0], null, level + 1)),
right(doGetGepth(tree->next[1], null, level + 1));
return {1U + left.first + right.first, left.second + right.second + level};
}
template <typename T>
double getDepth(T tree, T null = static_cast<T>(0))
{
auto depth(doGetGepth(tree, null, 0U));
return depth.first ? double(depth.second) / depth.first : 0;
}
enum { NNODES = 1000 * 1000 };
int main(int argc, char *argv[])
{
node_t *nodes = new node_t[NNODES];
std::default_random_engine dre;
for (int i = 0; i < NNODES; ++i) {
std::uniform_int_distribution<int> di(0, i);
const int j = di(dre);
if (i != j)
nodes[i].key = nodes[j].key;
nodes[j].key = i;
}
tree_t tree;
tree_new(&tree);
clock_t start = clock();
for (int i = 0; i < NNODES; ++i)
tree_insert(&tree, nodes + i);
cout << " tree_insert time: "
<< (double) (clock() - start) / CLOCKS_PER_SEC << " seconds" << endl;
cout << " RB depth: " << getDepth(tree.root) << endl;
start = clock();
for (int i = 0; i < NNODES; ++i) {
if (!tree_search(&tree, nodes + i))
cout << "Strange failure to tree_search " << nodes[i].key << '\n';
}
cout << " tree_search time: "
<< (double) (clock() - start) / CLOCKS_PER_SEC << " seconds" << endl;
start = clock();
for (int i = 0; i < NNODES; ++i) {
if (!tree_search(&tree, nodes + nodes[i].key))
cout << "Strange failure to tree_search " << nodes[i].key << '\n';
}
cout << " alternative tree_search time: "
<< (double) (clock() - start) / CLOCKS_PER_SEC << " seconds" << endl;
start = clock();
for (int i = 0; i < NNODES; ++i) {
tree_remove(&tree, nodes + i);
}
cout << " tree_remove time: "
<< (double) (clock() - start) / CLOCKS_PER_SEC << " seconds" << endl;
delete[] nodes;
tree_destroy(&tree, NULL, NULL);
cout << endl;
return 0;
}
在 Ampere eMAG 8180 的參考執行輸出:
其中 rb.h 的原始程式碼可見 rb.h (部分遮蔽)
你需要對照看 C 語言：前置處理器應用篇 以理解裡頭巨集的使用
請補完程式碼，使其運作符合預期。作答規範:
DDDD 是 0 或 1 的數值AAAA, CCCC, FFFF, GGGG 是巨集名稱BBBB 是變數名稱EEEE 是表示式
測驗 2
第 1 週測驗題 提及 Timsort，這裡我們想實作簡化的 Timsort，在 Ampere eMAG 8180 的參考執行輸出:
其中 qsort 來自 glibc 的 qsort(3p)，儘管 glibc 的 stdlib/qsort.c 已採取非遞迴的快速排序法並包含若干調整，上述的 Timsort 仍可優於快速排序法，並滿足 stable sort。
原始程式碼可見 sort.c (部分遮蔽)
假設 timsort 函式第二個參數 (即 void *f) 轉型為 offset_t 後，必定大於第一個參數 (即 void *l) 轉型為 offset_t 的值。請補完程式碼，使其運作符合預期。作答規範: (以最精簡的形式撰寫，且依循 lab0-c 一致程式碼風格，皆不得包含 ; 字元)
AAAA 是合法 C 語言敘述BBBB 和 CCCC 為表示式，不得出現 ++ 和 -- 運算子DDDD 為表示式，必須包含 MIN_RUN，且 + 運算子必須先於 * 或 / 運算子出現 (由左到右)，不得出現小括號 (即 ( 或 ))EEEE, FFFF, GGGG 是表示式，不得出現小括號 (即 ( 或 ))
測驗 3
延伸測驗 1，考慮 rbi.c 是不依賴遞迴呼叫的紅黑樹實作，原始程式碼可見 rbi.c (部分遮蔽)，編譯後得到檔名為 rbi 的執行檔，執行方式:
參考執行輸出:
234 是所有子樹節點的內含值總和。請補完程式碼，使其運作符合預期，作答規範: (以最精簡的方式撰寫，不包含小括號)
HHHH 和 IIII 是正整數JJJJ, KKKK, LLLL 皆為巨集名稱
HackMD
