# 2023q1 Homework1 (lab0)
contributed by < `ItisCaleb` >
## 開發環境
6.1.12-arch1-1
```shell
$ gcc --version
gcc (GCC) 12.2.1 20230201
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12400
CPU family: 6
Model: 151
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
CPU(s) scaling MHz: 19%
CPU max MHz: 5600.0000
CPU min MHz: 800.0000
BogoMIPS: 4993.00
```
## 開發過程
目前在修正 dudect 後，自動測試程式可以得到 100 分
但程式碼還需要去進行改進
### `q_new`
:::danger
依循作業書寫規範，中英文間用一個半形空白字元區隔。
:notes: jserv
:::
呼叫 `malloc` 來配置 `list_head` 的記憶體空間
並且使用 `list.h` 裡的 `INIT_LIST_HEAD` 初始化新的 list
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
### `q_free`
使用 `list_for_each_entry_safe` 來走訪 list 裡的每個元素
並且一一釋放記憶體空間
最後將l ist 的 head 所佔用的空間釋放
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *ele, *safe;
list_for_each_entry_safe (ele, safe, l, list)
q_release_element(ele);
free(l);
}
```
### `q_insert_head`/`q_insert_tail`
兩個函式的實作幾乎相同，所以 `q_insert_tail` 直接呼叫 `q_insert_head`
先用 `malloc` 分配一個 `element_t` 的記憶體空間
並且使用 `strdup` 來複製字串 `s` 到 `ele->value` 裡
最後使用 `list_add` 來將 `ele` 加入到 list 的頭部/尾端
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add(&ele->list, head);
return true;
}
```
```c
bool q_insert_tail(struct list_head *head, char *s)
{
return q_insert_head(head->prev, s);
}
```
[commit 2a2a0fa](https://github.com/ItisCaleb/lab0-c/commit/2a2a0fac9fc88a7eb55788c17020971e9274780b)
### `q_remove_head`/`q_remove_tail`
兩個函式的實作幾乎相同，所以 `q_remove_tail` 直接呼叫 `q_remove_head`
首先使用 `list_entry` / `list_last_entry` 來獲得list頭部
接著使用 `list_del` 來使 `ele->value` 從list中移除
然後先比較 `ele->value` 及 `bufsize` 的大小，將較小的作為字串複製的長度
並透過 `strncpy` 將 `ele->value` 複製到 `sp` 上
最後將字串結尾改成`\0`
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_entry(head->next, element_t, list);
list_del(&ele->list);
if (sp) {
size_t len = strlen(ele->value);
len = len < bufsize - 1 ? len : bufsize - 1;
strncpy(sp, ele->value, len);
*(sp + len) = '\0';
}
return ele;
}
```
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove_head(head->prev->prev, sp, bufsize);
}
```
[commit 2a2a0fa](https://github.com/ItisCaleb/lab0-c/commit/2a2a0fac9fc88a7eb55788c17020971e9274780b)
### `q_size`
使用 `list_for_each` 走訪 list 的每個節點
並將次數累加到 `len` 上後回傳
```c
int q_size(struct list_head *head)
{
if (head == NULL)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head) {
len++;
}
return len;
}
```
### `q_delete_mid`
先透過 `q_size` 取得 list 的長度，除 2 後獲得中間的位置
之後走訪 list 的節點直到到達中間的位置
接著把中間的節點從 list 中移除
最後透過 `list_entry` 取得節點的元素並且釋放元素所佔的記憶體空間
本來是走訪 list 的元素
後來想了一下發現只要走訪到中間後再取得元素就好
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
int m_pos = q_size(head) / 2, pos = 0;
struct list_head *li, *safe;
list_for_each_safe (li, safe, head)
if (m_pos == pos++) {
list_del(li);
q_release_element(list_entry(li, element_t, list));
return true;
}
return false;
}
```
用快慢指標去重新實作
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *slow = head->next, *fast;
for (fast = head->next; fast != head && fast->next != head;
fast = fast->next->next) {
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### `q_delete_dup`
走訪 list 的每個節點
並且如果下一個節點的內容跟現在的重複便持續刪除，接著將 `flag` 設成 `true`
如果 `flag` 為 `true` 則把現在的節點刪除
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
struct list_head *li, *safe;
list_for_each_safe (li, safe, head) {
element_t *ele = list_entry(li, element_t, list);
struct list_head *ptr = li->next;
bool flag = false;
while (ptr != head &&
strcmp(ele->value, list_entry(ptr, element_t, list)->value) ==
0) {
list_del(ptr);
q_release_element(list_entry(ptr, element_t, list));
ptr = li->next;
flag = true;
}
safe = li->next;
if (flag) {
list_del(li);
q_release_element(list_entry(li, element_t, list));
}
}
return true;
}
```
### `q_swap`
走訪每一個節點並計數
如果 `i` 為奇數則把現在的節點移除
並以往前兩個的節點作為 head 重新加入 list
以此來達成交換
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *li, *safe;
int i = 0;
list_for_each_safe (li, safe, head) {
if (i & 1) {
list_del(li);
list_add(li, li->prev->prev);
}
i++;
}
}
```
### `q_reverse`
走訪每一個節點直到 list 的尾端的節點
並且把現在的節點從 list 移除後以原本尾端的節點作為 head 重新加入 list
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *li, *safe, *last = head->prev;
list_for_each_safe (li, safe, head) {
if (li == last)
return;
list_del(li);
list_add(li, last);
}
}
```
### `q_reverseK`
走訪 list 的每個節點並計數
每 `k` 個為一個 sublist
並使 `khead` 作為這個 sublist 的頭部
使用 `q_reverse` 把這個 sublist 反向排列
最後當走訪到下一個 sublist 時要把 `khead->next`連接上去
因為在 `q_reverse` 之後 `khead->next` 是連接到 `khead->prev` 的
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head)
return;
LIST_HEAD(khead);
khead.next = head;
struct list_head *li, *safe;
int i = k;
list_for_each_safe (li, safe, head) {
if (i == k) {
khead.next->next = li;
khead.next = li;
} else if (i == 1) {
khead.prev = li;
q_reverse(&khead);
i = k;
continue;
}
i--;
}
}
```
### `q_sort`
Merge Sort
先用快慢指標把 list 分成兩半
並且用 `first` 跟 `second` 分別做為這兩半的 head
接著便遞迴下去直到分割成只有一個節點的 list
最後兩兩合併
```c
void l_merge_two(struct list_head *first,
struct list_head *second,
struct list_head *head)
{
while (!list_empty(first) && !list_empty(second)) {
element_t *ele1 = list_entry(first->next, element_t, list);
element_t *ele2 = list_entry(second->next, element_t, list);
if (strcmp(ele1->value, ele2->value) <= 0)
list_move_tail(first->next, head);
else
list_move_tail(second->next, head);
}
if (!list_empty(first))
list_splice_tail_init(first, head);
else
list_splice_tail_init(second, head);
}
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *slow = head, *fast = head;
do {
slow = slow->next;
fast = fast->next->next;
} while (fast != head && fast->next != head);
LIST_HEAD(first);
LIST_HEAD(second);
list_splice_tail_init(head, &second);
list_cut_position(&first, &second, slow);
q_sort(&first);
q_sort(&second);
l_merge_two(&first, &second, head);
}
```
### `q_descend`
從 list 的尾端反向走訪
並不斷紀錄最大的元素
如果有元素比紀錄到的小便從 list 中移除並且釋放記憶體
最後回傳沒有被刪除的元素的數量
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head) || list_is_singular(head))
return 0;
struct list_head *cur = head, *safe;
element_t *max = NULL;
int sum = 0;
do {
cur = cur->prev;
safe = cur->prev;
element_t *ele = list_entry(cur, element_t, list);
if (!max || strcmp(ele->value, max->value) >= 0) {
max = ele;
sum++;
} else {
list_del(cur);
q_release_element(ele);
cur = safe->next;
}
} while (safe != head);
return sum;
}
```
### `q_merge`
把每個 list 都接到第一個 list 後面並且累加在內的元素數量
然後使用 Merge Sort 去排序
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain),
*ctx = NULL;
int sum = first->size;
list_for_each_entry (ctx, head, chain) {
if (ctx == first)
continue;
sum += ctx->size;
list_splice_tail_init(ctx->q, first->q);
}
q_sort(first->q);
return sum;
}
```
## qtest
使用`make valgrind` 發現 `qtest` 有 Memory Leak 的情況
觀察了一下 `qtest.c`
發現在函式 `q_quit` 中第一行為 `return true`
把這行刪掉即可使 `qtest` 在退出時正確釋放記憶體
```c
static bool q_quit(int argc, char *argv[])
{
return true;
report(3, "Freeing queue");
if (current && current->size > BIG_LIST_SIZE)
set_cautious_mode(false);
...
}
```
如果在 queue 為 NULL 的情況下使用一些如 `reverseK`, `descend` 等指令
會出現 NULL pointer dereference 的情況
已進行修改為 `qtest.c` 加上 NULL check
並提交 pull request
[Fix some NULL pointer dereference in qtest when the queue is NULL](https://github.com/sysprog21/lab0-c/pull/126/commits/b492a77d82721071bd24ccfe7bf30d31f7835a19)
## dudect
實驗的原理為測量兩組資料執行的時間並且透過 t-test 去分析
如果兩組資料平均執行時間的統計差異超過一定閥值的話
則程式的複雜度便不為常數時間
> **How does this work?** In a nutshell, this code takes two different inputs, runs the piece of code many times for each input and measures how much time it takes. If there is a statistical difference on the (average) time it takes to run with different inputs, the implementation is deemed not time constant.
Reference: [dudect(Questions)](https://github.com/oreparaz/dudect/blob/master/README.md#questions)
要注意的是 dudect 並不保證通過實驗的程式絕對為常數時間
如果需要更嚴謹的結果也需要去透過其他的測試去測量
> **My code passes this tests. Does it mean it is really time constant?** Absolutely not. The test implemented is perhaps the simplest form of leakage detection. For serious assessment, you should also run many other tests, with specially crafted input vectors. The test harness implemented here is not yet that comprehensive. You're encourage to submit an implementation that is not constant time yet passes the test--in that way we can improve the test suite. The more you know about the implementation, the better you can design input vectors. For inspiration, see these RSA test vectors.
Reference: [dudect(Questions)](https://github.com/oreparaz/dudect/blob/master/README.md#questions)
### Student's t-test
Student's t-test 是一種用於比較兩個樣本均值是否有顯著差異的統計檢驗方法，可以用於解決實驗數據中小樣本數量的問題。
在進行 t-test 時，我們通常有兩個樣本，每個樣本都有一組觀察值。我們希望知道這兩個樣本是否來自同一總體分佈。為此，我們首先計算每個樣本的平均值和標準差，然後使用這些統計量計算t值，這是兩個樣本均值之間的標準化差異。 t值的大小取決於樣本的大小、差異的大小以及每個樣本的標準差。如果t值很大，這意味著兩個樣本的均值之間的差異很顯著，而如果t值很小，則這兩個樣本的均值之間可能沒有顯著差異。
在計算t值後，我們可以將它與臨界值進行比較，以確定差異是否顯著。臨界值取決於樣本大小和所選的顯著性水平（通常為0.05）。如果 t 值超過了臨界值，我們可以拒絕假設，即這兩個樣本來自不同的總體分佈。
> ChatGPT
### dudect 的細節
在論文中總共分為三個部份
- Measure execution time
首先需要去測量程式的執行時間(CPU Cycles)
所以我們便使用兩組測資
一組為固定測資 (fix class)，另一組則為隨機測資(random class)
而固定測資可以選擇邊緣測資去觸發程式的特例處理
最後為了降低環境對測量的影響（如 OS、外部程式），每次測試的測資是隨機選擇的
> In the original leakage detection paper [CKN00] the authors propose
to interleave the sequence of classes during the evaluation. We extend this
suggestion and randomize this sequence to prevent interference due to any
concurrent process that may be executing in parallel.
Reference: [Dude, is my code constant time? page 2](https://eprint.iacr.org/2016/1123.pdf)
- Apply post-processing
當進行測量後，可以在統計分析之前先預處理得到的數據(CPU Cycles)
我們可以去除掉明顯超過一定閥值的數據，因為這些數據可能是由於外部環境的干擾而形成的誤差
或是使用其他更高階的 pre-processing
- Apply statistical test
最後一步便是對先前測量得到的數據(CPU Cycles)做 t-test
若是進行分析後得到的結果 t 超過某個閥值
我們便能斷定測試的程式執行時間不為常數時間
### lab-0 的 dudect
在把 `queue.c` 實作完之後
會發現經由測試 dudect 測試的 `q_insert_head` 及 `q_insert_tail` 並不為常數時間
在本課程的教材中有提到 lab-0 的 dudect 缺少對 `percentiles` 的處理
透過觀察原本的程式碼會發現 `percentiles` 原本是作為對測量後得到的數據作預處理的閾值
我們把 `percentiles` 引進 lab-0 之後 dudect 便能正確分析 `q_insert_head` 及 `q_insert_tail` 的執行時間
```c
static int64_t percentile(int64_t *a, double which, size_t size)
{
qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp);
size_t array_position = (size_t) ((double) size * (double) which);
assert(array_position >= 0);
assert(array_position < size);
return a[array_position];
}
/*
set different thresholds for cropping measurements.
the exponential tendency is meant to approximately match
the measurements distribution, but there's not more science
than that.
*/
static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times)
{
for (size_t i = 0; i < NUMBER_PERCENTILES; i++) {
percentiles[i] = percentile(
exec_times,
1 - (pow(0.5, 10 * (double) (i + 1) / NUMBER_PERCENTILES)),
N_MEASURES);
}
}
static void update_statistics(const int64_t *exec_times,
uint8_t *classes,
int64_t *percentiles,
t_context_t *ttest_ctxs[])
{
for (size_t i = 0; i < N_MEASURES; i++) {
int64_t difference = exec_times[i];
/* CPU cycle counter overflowed or dropped measurement */
if (difference <= 0)
continue;
/* do a t-test on the execution time */
t_push(ttest_ctxs[0], difference, classes[i]);
// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < NUMBER_PERCENTILES;
crop_index++) {
if (difference < percentiles[crop_index]) {
t_push(ttest_ctxs[crop_index + 1], difference, classes[i]);
}
}
}
}
```
## shuffle
用 Fisher-Yates Shuffle 去實作 shuffle 指令
把隨機選到的節點直接接到 list 的尾端
因為選擇的範圍是 `len` 所以不會選到重複的節點
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
int len = q_size(head);
struct list_head *ptr;
while (len) {
ptr = head->next;
for (int i = rand() % len; i > 0; i--)
ptr = ptr->next;
list_move_tail(ptr, head);
len--;
}
}
```
這是用[1,2,3]去執行 shuffle 一萬次的結果
自由度為5
並且設顯著水準 $α$ 為 0.05
```
Expectation: 166666
Observation: {'123': 166339, '132': 167262, '213': 166269, '231': 166302, '312': 167085, '321': 166743}
chi square sum: 5.60246240984964
```
可以看到 chi-squared sum 約為5.6
查卡方分佈表表後的 p value 介於0.3~0.5
明顯大於我們設的顯著水準 0.05
因此我們不拒絕虛無假設 $H_0$
而同時圖表也顯示結果大致符合 Uniform distribution
## Linux 的 list_sort.c
先從 `list_sort` 的參數開始
- priv -> 要塞進cmp裡的物件
- head -> 要排序 list 的 head
- cmp -> 自訂的比較函式
```
/**
* list_sort - sort a list
* @priv: private data, opaque to list_sort(), passed to @cmp
* @head: the list to sort
* @cmp: the elements comparison function
*
```
### cmp
接收三個參數
- priv
- a -> list_head
- b -> list_head
如果是要讓 `a` 排在 `b`
則必須回傳 >0 (回傳a>b可以讓他變成遞增排列)
而如果是 `a` 排在 `b`之前
則是回傳 <=0
這樣子做可以支援兩種形式的 cmp
像是 `strcmp` 的 <0 =0 >0
或是回傳 0/1 的 `boolean` 形式
### merge_sort
[lib/list_sort: Optimize number of calls to comparison function](https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1957556.html)
演算法會去保證 merge 時的 list 至少長度為2:1
當有兩個長度為 $2^k$ 的 sublist 的時候，只有等到出現下一個 $2^k$ 的 sublist 才會把前者合併
因為如果用一般的 fully-eager bottom-up mergesort
也就是每遇到兩個 list 就 merge
當整體的長度略大於2的冪(n=1028)
那最後一次 merge 的兩個 list 就會極為不平衡 (1024:4)
使得浪費很多不必要的時間在比較上
同時只要這2:1的 list 都能放進 cache 就能去避免 cache thrashing 的發生
```
* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
*
* Thus, it will avoid cache thrashing as long as 3*2^k elements can
* fit into the cache. Not quite as good as a fully-eager bottom-up
* mergesort, but it does use 0.2*n fewer comparisons, so is faster in
* the common case that everything fits into L1.
```
在實作上何時決定merge是用變數 `count` (`pending` 裡的節點數量) 去決定的
而每當 `count` 增加的時候，我們就把一個節點放進 `pending` 裡
同時 `count` 增加代表著我們會把第k個 bit 設成 1 並把 k-1 ~ 0 的bit清除
```
0 -> 1 -> 2 -> 3 -> 4 -> 5
000 001 010 011 100 101
```
而在增加的過程中
我們會把兩個 $2^k$ 的 sublist 合併成一個 $2^{k+1}$ 的list
只有當 `count` 增加到2的冪我們才不會合併
```
0 -> 1 | 000 -> 001 no merge
1 -> 2 | 001 -> 010 no merge
2 -> 3 | 010 -> 011 merge k=0
3 -> 4 | 011 -> 100 no merge
4 -> 5 | 100 -> 101 merge k=0
5 -> 6 | 101 -> 110 merge k=1
6 -> 7 | 110 -> 111 merge k=0
7 -> 8 | 111 -> 1000 no merge
```
在實作上也有說明函式是怎麼去處理資料的
- list 跟 sublist 都會變成 null-terminated，且不再去維護 list 的 `prev`
- `pending` 是一個反向的 list ，每一個節點都是準備去被 merge 的 sublist
- 每個 sublist 長度都是 2 的冪
- 在 `pending` 中的 sublist 順序是依照長度跟時間，越小且越新的 sublist 會排在最前面
- 每種大小的 sublist 只會有 0~2 個
- 一對 sublist 在總長度跟在 `pending` 中的節點數量一樣時就會被合併(每當 `count` 增加到 sublist 長度的奇數倍)，這樣可以確保每次 merge 的長度都是 2:1 (ex: 兩個長度為 2 的 sublist 會在 `count` 增加到6的時候合併成長度為 4 的 sublist)
- 每一輪都會做以下的事情
-- 合併兩個長度由 `count` 去決定的 sublist ，並重新加入到 `pending` 裡
-- 然後把一個節點放進 `pending` 裡
```
* Data structure invariants:
* - All lists are singly linked and null-terminated; prev
* pointers are not maintained.
* - pending is a prev-linked "list of lists" of sorted
* sublists awaiting further merging.
* - Each of the sorted sublists is power-of-two in size.
* - Sublists are sorted by size and age, smallest & newest at front.
* - There are zero to two sublists of each size.
* - A pair of pending sublists are merged as soon as the number
* of following pending elements equals their size (i.e.
* each time count reaches an odd multiple of that size).
* That ensures each later final merge will be at worst 2:1.
* - Each round consists of:
* - Merging the two sublists selected by the highest bit
* which flips when count is incremented, and
* - Adding an element from the input as a size-1 sublist.
```
接著我們來看實際的程式碼
初始化
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
```
把 list 變成 null-terminated
```c
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
當 `list` 不為 `NULL` 的時候會不斷執行下面的程式
```c
do {
...
} while (list);
```
先去找 `count` 裡為 0 的 LSB
因為那個 bit 在 `count` 增加後便是我們要的 bit k
```c
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
接著我們便進行 merge(`count` 不為$2^n-1$的時候，因為增加後會變成$2^n$)
當 merge 完後我們便把新的 sublist 加回到在 `pending` 中原來的位置
```c
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
```
每一輪的最後我們便把 `list` 中的一個節點放進 `pending`中
並且 `count` 加一
```c
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
當 `list` 裡面都沒東西後
我們在 `pending` 中有可能還會有 sublist 沒有被 merge
於是我們就把剩下的東西 merge 掉
```c
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
最後我們會使用 `merge_final` 把 merge 好的東西放回 `list`
以及把 list 每個節點的 `prev` 都重新接上
並且變回 circular doubly-linked list
```c
merge_final(priv, cmp, head, pending, list);
```
```c
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
```
Sign in with Wallet
Connect another wallet