---
# System prepended metadata

title: 2021q1 Homework1 (lab0)
tags: [linux2021]

---

# 2021q1 Homework1 (lab0)
###### tags: `linux2021`
Info: https://hackmd.io/@sysprog/linux2021-lab0
Origin: https://github.com/sysprog21/lab0-c

## Contents

- In-place merge sort implementation

## Merge Sort 1.0

### Concept

The key of merge sort algorithm is by using a **merge** function that turns two **sorted partition**s of size $(0, M]$ into one sorted partition of size $(0, 2M]$, we can produce a $N$ sized sorted list by starting from partition size of $1/N$, and merge it all the way up.

#### Virtual Partition / Counted Iterator

When implementing merge sort for linked list, a **virtual partition** that takes up a very small $O(1)$ memory can be created using **Counted Iterator (CI)**:
```c
struct counted_iterator {
    list_ele_t* next,
    long long remaining
}

inline list_ele_t* ci_next(struct counted_iterator* ci) {
    if (ci->remaining == 0)
        return NULL;
    if (!ci->next) {
        ci->remaining = 0;
        return NULL;
    }
    list_ele_t* ret = ci->next;
    ci->remaining--;
    ci->next = ret->next;
    return ret;
}
```
A CI will return the next element normally unless an initially specified `remaining` count of elements have been returned.  For example, given an initial value of 4, fifth call of `ci_next(A)`  will returns `NULL`.

```graphviz

digraph {
    node [shape=record];
    
    llist [label="<i0>a|b|c|d| <i4>r|x|y|z"];
    "<CI> A"->llist:i0;
    "<CI> B"->llist:i4;
}

```

#### Slot ~~Machine~~

The **merge** function will compare `next(A)` and `next(B)`, and insert the smaller element to a **slot**.  This allows us to handle different target using a same logic.
```graphviz 
digraph {
    node [shape=record];
    rankdir = "LR"
    queue [label="{<head>head|size}|queue_t"];
    lele [label="{value | <next>next}|<elem>list_ele_t"];
    slot -> queue:head;
    slot -> lele:next;
    lele:next -> list_ele_t;
    queue:head -> lele:elem;
}
```
We can then do `*slot = <pointer to list_ele_t>` to update the `head` field of `queue_t` or `next` field of `list_ele_t`.

#### Skip Size / Partition Size

The term **skip size** comes from the number of elements to skip starting from the head of `A` to reach the head of `B`.  This guarantees that virtual partition `A` will have exactly `skip_size` elements.

### Algorithm

#### Description

* Iterate through skip size of $1, 2, 4 ... N$:
    * Initialize `cur = q->head`
    * Initialize `slot = &q->head`
    * When there's more than `skip_size` elements left:
        * Initialize CI `A = {cur, skip_size}`
        * Skip `skip_size` elements to find head of `B`
        * Initialize CI `B {bhead, skip_size}`
        * When `a = ci_next(A)` and `b = ci_next(B)` is not `NULL`:
            * `*slot = min(a, b)`
            * `slot = &(*slot)->next`
        * Put remaining items in A and B into slot and update accordingly
        * `cur` is set to whatever that's after the original tail of partition `B`
    * Put remaining $(0,$ `skip_size` $)$ items into slot
    * *end of iterA*
#### Invariants

1. At the end of *iterA* every `2 * skip_size` elements are sorted within its own virtual partition.