# Linux2025q1: Quiz 1 Write-Up

## Content Reference

- [2025q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)

## 測驗 1

該題要求實現鏈結串列的插入功能，其中關鍵函式 `list_insert_before` 原型如下:

/**
 * 
 * ...
 * 
 * @before  : Pointer to the item before which the new item
 *            should be inserted.
 * ...
 * 
 * 
 */
static inline void list_insert_before(list_t *l,
                                      list_item_t *before, 
                                      list_item_t *item
)

其中 `list_t`, `list_item_t` 定義如下:

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

`before` 是該函式的關鍵參數，指向欲插入的串列單元 `item` 的 `next` 應指向的 `item`，結果示意如下圖:

## 測驗 2

## 測驗 3

本題結合 linux 的封裝過鏈結串列結構 `list_head` 來實現非遞迴的鏈結串列的快速排序。

首先觀察 `linux/include/linux/types.h` 中 [`list_head`](https://github.com/torvalds/linux/blob/27eddbf3449026a73d6ed52d55b192bfcf526a03/include/linux/types.h#L194) 定義:

struct list_head {
	struct list_head *next, *prev;
};

搭配下方圖片 (根據 [1] 重繪) 可知 `list_head` 運作的原理:


圖中的 `custom_node_t` 定義如下:

typedef struct __custom_node 
{
    /* data */
    int a;
    int b;
    int c;
    /* ... */
    
    /* list head */
    struct list_head list;
} custom_node_t;

另外，因為 `list` 和 `list.next` 的地址是一樣的，以下程式說明了 `next` 可以透過將指向 `list` 的指標轉型成指向一個指向 `list` 的指標 (`struct list_head**`) 來取得 `list.next` 儲存的地址。

#include <stdio.h>

struct list_head {
  struct list_head *next, *prev;
};

int main() {
  struct list_head v1, v2;

  // assign pointers for demonstration
  v1.next = &v2;
  v2.prev = &v1;

  // By casting &v1 to a pointer to pointer of list_head, we obtain the value of v1.next.
  struct list_head *p_next = *( (struct list_head **)&v1 );
  printf("Value of v1.next (obtained by casting): %p\n", (void *)p_next);
  printf("Address of v2 (should be equal to v1.next): %p\n", (void *)&v2);

  return 0;
}

$ gcc test.c -o test

$ ./test 
Value of v1.next (obtained by casting): 0x7fff2fa260f0
Address of v2 (should be equal to v1.next): 0x7fff2fa260f0

## Reference