# 2023q1 Homework3 (quiz3)
contributed by < `davidlai1999` >

### 測驗 `1`
**運作原理**
* Linux 在紅黑樹的實作上利用位址的最後 3 位來儲存顏色，這是因為不管是 32 位元還是 64 位元，最後幾個位元必定為零的性質，再加上辨別節點為紅色或是黑色只需要 1 個位元即可，所以在實作上將親節點的位址與代表顏色以 `or` 的形式合併並儲存在型別為 `uintptr_t` 的變數中。
* `left` 與 `right` 分別用於指向該節點的左子節點與右子節點，而 `next` 光看這個結構並沒有辦法直接明白其用意，直到讀到 `cmap_next` 這個函式才明白其指向比該節點大的所有節點中最小的那一個節點。 `value` 用於儲存代表該節點的值。

  typedef struct __node {
      uintptr_t color;
      struct __node *left, *right;
      struct __node *next;
      long value;
  } node_t   __attribute__((aligned(sizeof(long))));

* 此結構用於儲存紅黑樹中一些關鍵的資訊。其中比較重要的像是 `head` 指向紅黑樹的第一個節點，`it_most` 紀錄紅黑樹中最大的節點，`it_least` 紀錄紅黑樹中最小的節點。

  struct cmap_internal {
      node_t *head;

      /* Properties */
      size_t key_size, element_size, size;

      cmap_iter_t it_end, it_most, it_least;

      int (*comparator)(void *, void *);
  };

* 當需要使用到親節點的位址時，將其與 ~7 做 `and` 運算，因為 ~7 的後 3 個位元皆為 0 ，其餘為 1 ，這樣操作相當於只取除了後 3 個位元之外的值，也就是親節點的位址。

  #define rb_parent(r) ((node_t *) (r->color & ~7))

* 設定顏色可以透過 `bitwise` 的方式對變數 `color` 進行操作。當節點要設定為紅色時，最右邊的位元理應設定為 0 ，由於 ~1 等同 0xFFFFFFFE，與其進行 `and` 運算等同於只更動最後 1 個位元並設定為 0 。設定為黑色也是相同道理。

  #define rb_set_red(r) \
      do {              \
          rb_color(r) &= ~1;         \
      } while (0)
  #define rb_set_black(r) \
      do {                \
          rb_color(r) |= 1;           \
      } while (0)

* `cmap_insert` 執行節點的插入，首先呼叫 `cmap_create_node` 像記憶體要求空間並初始化該節點中的變數。接著用 `obj->head` 判斷這個節點會不會是整個紅黑樹的第一個節點，是則將此節點設為黑色並讓 `obj` 的 head 指向它，呼叫 `cmap_calibrate` 更新 `obj` 中的 `it_most` 與 `it_least` 。
* 若該節點並非根節點就必須走訪紅黑樹並找到正確的位置放置，過程為利用 `obj` 中的 `comparator` 比較插入節點與走訪到的當前節點兩者的值， `comparator` 為函式指標，在初始化時被設定為 `cmp` ，回傳值若小於 0 表插入節點小，如果左節點存在則往左節點繼續走訪，否則用 `rb_set_parent` 將當前節點設定為插入節點的親節點並使用 `cmap_fix_colors` 重新審視插入節點以上的顏色是否如何紅黑樹的定義。回傳值若大於 0 有相同的操作邏輯，只是更改為對右節點。最後做 `cmap_calibrate` 更新 `obj` 中的 `it_most` 與 `it_least` 。

  static bool cmap_insert(cmap_t obj, node_t   *node, void *value)
  {
      cmap_create_node(node);

      obj->size++;

      if (!obj->head) {
          /* Just insert the node in as the new head. */
          obj->head = node;
          rb_set_black(obj->head);

          /* Calibrate the tree to properly assign pointers. */
          cmap_calibrate(obj);
          return true;
      }

      /* Traverse the tree until we hit the end or find a side that is NULL */
      for (node_t *cur = obj->head;;) {
          int res = obj->comparator(&node->value, &cur->value);
          if (!res) /* If the key matches something else, don't insert */
              assert(0 && "not support repetitive value");

          if (res < 0) {
              if (!cur->left) {
                  cur->left = node;
                  rb_set_parent(node, cur);
                  cmap_fix_colors(obj, node);
                  break;
              }
              cur = cur->left;
          } else {
              if (!cur->right) {
                  cur->right = node;
                  rb_set_parent(node, cur);
                  cmap_fix_colors(obj, node);
                  break;
              }
              cur = cur->right;
          }
      }

      cmap_calibrate(obj);
      return true;
  }

* tree_sort 先將傳入的 `list` 利用 `cmap_insert` 建立出紅黑樹，建完後從紅黑樹最左邊的節點開始走訪，用 `cmap_next` 找到比當前節點大的節點中最小者，將 `list` 以排序好的順序重新串連起來，最後將 `list` 最後一個節點指向 `NULL` 完成新的 `list` 。

  void tree_sort(node_t **list)
  {
      node_t **record = list;
      cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
      while (*list) {
          cmap_insert(map, *list, NULL);
          list = &(*List)->next;
      }
      node_t *node = cmap_first(map), *first = node;
      for (; node; node = cmap_next(node)) {
          *list = node;
          list = &(*List)->next;
      }
      *List = NULL;
      *record = first;
      free(map);
  }

### 測驗 `2`
**運作原理**
* AVL tree 中節點的結構， `parent_balance` 用於儲存 親代節點的位址，並利用位址最後兩位必為零的特性，將子樹的平衡儲存於此。

enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
struct avl_node {
    unsigned long parent_balance;
    struct avl_node *left, *right;
} AVL_NODE_ALIGNED;

* 假設優先佇列中元素的結構如下，節點所涵蓋的值儲存於 i 中。

struct avlitem {
    uint16_t i;
    struct avl_node *avl;
};

* 用這個結構來儲存佇列開頭，並額外設置指標指向 AVL tree 中值最小的節點，可用於判斷該佇列是否為空。

struct avl_prio_queue {
    struct avl_root root;
    struct avl_node *min_node;
}; 

* 優先佇列要能運作需要實作插入與移除，而又可以分為平衡與非平衡兩種。

**實作插入**
* 重點參數
* `cur_nodep` ：用於走訪 AVL tree 的指標，當其值為 NULL 時，代表已經走訪到 AVL tree 的最底層。
* `cur_entry` ：用於指向當前節點所在的物件起始位置，利用巨集 `container_of` 來實現。
* `isminimal` ：用於判斷是否需要更新優先佇列中的最小值。
* 實作步驟
* `cur_nodep` 首先會指向 AVL tree 的根節點，若其不為空代表還沒走訪到最底層，繼續走訪。

 while (*cur_nodep)

* 每經過一個節點就利用 `avl_entry` 得到該節點所在的物件起始位置並給予 `cur_entry` ， `cmpint` 判斷`cur_entry` 所擁有的值與插入值的大小，小則往左，大則往右並將 `isminimal` 設為零，因為插入值不可能是最小。

if (cmpint(&new_entry->i, &cur_entry->i) <= 0) {
    cur_nodep = &((*cur_nodep)->left);
} else {
    cur_nodep = &((*cur_nodep)->right);
    isminimal = 0;
}

* 到最底時利用 `isminimal` 判斷是否為最小值，如果為真則將 `min_node` 更新。

if (isminimal)
    queue->min_node = &new_entry->avl;

* 最後依照插入為平衡或非平衡分別實行 `avl_insert` 或 `avl_link_node` ，差別在於節點中的 `parent_balance` 有無更新。

avl_link_node(&new_entry->avl, parent, cur_nodep);

avl_insert(&new_entry->avl, parent, cur_nodep, &queue->root);

**實作移除**
* 重點參數
* `queue->min_node` 指向 AVL tree 中最小值的節點。
* `item` ：指向 `queue->min_node` 所在物件的起始位置，為要從 AVL tree 中移除的對象。
* 實作步驟
* 先判斷 `queue->min_node` 是否為空來確認 AVL tree 中是否存在節點可以執行移除。

if (!queue->min_node)
    return NULL;

* 利用 `avl_entry` 得到 `queue->min_node` 所在物件的起始位置並給予 `item` 。利用 `avl_next` 從 `min_node` 的右節點開始尋找次小的節點並將其認定為 `min_node` 。

item = avl_entry(queue->min_node, struct avlitem, avl);
queue->min_node = avl_next(queue->min_node);

* 最後利用 `avl_erase_node` 將 `item` 從 AVL tree 中移除，並回傳 `item` 。

avl_erase_node(&item->avl, &queue->root, &removed_right);

return item;

* avltree.h 中遮蔽程式碼
>IIII ：((node)->parent_balance & ~7)
JJJJ ：((node)->parent_balance & 1)
KKKK ：((node)->parent_balance & 1)
LLLL ：((node)->parent_balance & ~7)
MMMM ：avl_rotate_right
NNNN ：avl_rotate_leftright

### 測驗 `3`
**運作原理**
* 定義參數 `num_of_buckets` 與 `num_of_iterations` 前者代表 bucket 的大小，也就是會產生多少隨機數，後者為 `fill_buckets` 內的迴圈需執行次數，與隨機數的生成有關。

int num_of_buckets = 120;
int num_of_iterations = (1 << 20);

* `log2_64` 用於產生 64 位元輸入值對 2 取對數後的值，實作概念類似二元搜尋，第一個判別式檢查 64 位元的前 32 位元是否存在非零位元，若存在就繼續檢查這 32 位元的前 16 位元是否存在非零位元，以此類推。
* 假如最後我們得知這 64 位元中的前 8 個位元存在值，那輸入值取 2 的對數至少有 56 ，剩下的 8 位元用帶入 `log_table_256` 的方式直接獲得值，兩者相加即為答案。
>AAAA : 56
BBBB : 48
CCCC : 40
DDDD : 32
EEEE : 24
FFFF : 16
GGGG : 8
HHHH : 0
* `bucket_number` 用於確保 LFSR 產生的隨機數值為 `uniformity distribution` ，先用 leq 判斷是否大於 `N_BUCKETS` ，若 leq = 1 ， x & mask111 可以直接回傳，因為後式會因為 1 - leq 而為 0 。若 leq 為 0 ，則需處理該值令其小於 `N_BUCKETS` 才可回傳。
>mask111 = 0b01111111
>mask011 = 0b00111111

unsigned int bucket_number(uint64_t x)
{
    uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
    uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */

    unsigned char leq = ((x & mask111) < N_BUCKETS);
    /* leq (less or equal) is 0 or 1. */

    return (leq * (x & mask111)) +
           ((1 - leq) * ((x >> (N_BITS + 1)) & mask011));
    /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
     * '... & mask011' guarantees that the result is less or equal N_BUCKETS.
     */
}

### 測驗 `4`

**實作原理**
* 利用二元搜尋的概念判斷輸入值左起第 1 個位元位於 32 個位元中的哪個位置，因為左起第 1 個位元是取對數值的關鍵。
* 第一個判別式用於判斷輸入值左邊 16 位元是否存在非零位元，若存在則 r = 16 ，表示對輸入值取對數至少比 16 大，接著將 x 平移 r 個位元，若 r = 16 ，代表我們在意的是左邊 16 個位元，若 r = 0 ，代表我們在意的是右邊 16 個位元，接著將判斷式縮短到 8 位元。
* 只要判斷式為真， r 值就會更新，且 x 就會位移， KKKK = r | shift | x>>1 是因為判斷式只做到 x > 0x3 ，後面的 x>>1 其實就是做 x > 0x1的判斷。最後因為開頭對 x 減一，要將回傳值加 1 。

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                 
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x>>1) + 1;       
}