# 2021q1 Homework1 (quiz1)
contributed by < `RZHunagJeff` >
###### tags: `linux2021`

## Question
With a singly linked list defined as follows:

typedef struct __node {
    int value;
    struct __node *next;
} node_t;

Given following program:

static inline void list_add_node_t(node_t **list, node_t *node_t) {
    node_t->next = *list;
    *list = node_t;
}

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

void quicksort(node_t **list)
{
    if (!*list)
        return;

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    CCC;
    *list = result;
}

And the corresponding test bench:

static bool list_is_ordered(node_t *list) {
    bool first = true;
    int value;
    while (list) {
        if (first) {
            value = list->value;
            first = false;
        } else {
            if (list->value < value)
                return false;
            value = list->value;
        }
        list = list->next;
    }
    return true;
}

static void list_display(node_t *list) {
    printf("%s IN ORDER : ", list_is_ordered(list) ? "   " : "NOT");
    while (list) {
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}

int main(int argc, char **argv) {
    size_t count = 20;

    node_t *list = NULL;
    while (count--)
        list = list_make_node_t(list, random() % 1024);

    list_display(list);
    quicksort(&list);
    list_display(list);

    if (!list_is_ordered(list))
        return EXIT_FAILURE;

    list_free(&list);
    return EXIT_SUCCESS;
}

Complete the program, which makes the program work properly.

## Analysis
In order to answer the question, the program should be analyzed. Following is my analysis flow.

### Test Bench
First, I started with the test bench, in the `main` function of test bench, it shows that the list is generated by 20 random number. After display the original list, the list will be sorted, by calling function `quicksort`, and display it again after sorting. After all, the order of the list will be checked whether it is in acensing order by function `list_is_ordered`. The flow of test bench is shown below:

st=>start: Start

init=>operation: Init list
show_b=>operation: Show list
(before sort)
sort=>operation: Sort list
show_a=>operation: Show list
(after sort)
check=>condition: Is list ordered?

ed_succ=>end: EXIT_SUCCESS
ed_fail=>end: EXIT_FAILURE

st->init(right)->show_b(right)->sort(right)->show_a->check
check(yes)->ed_succ
check(no)->ed_fail

### List Sorting
Then, I start to analyze function `quicksort`. To demonstrate, the list shown below is used:

digraph{
    rankdir=LR
    node [shape="box"]

    list [label="*list"]
    a [label="10"]
    b [label="2"]
    c [label="24"]
    d [label="7"]
    e [label="13"]
    other [label="..." shape="none"]
        
    list -> a -> b -> c -> d -> e -> other
}

Following are the steps in `quicksort`:
1. **Check the list**: check if given list is empty. Function will continue only when the list is not empty.

    if (!*list)
        return;

2. **Pick a pivot**: the first element in the list will be choosen as pivot of this round.

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

After these lines are evaluated:

    digraph{
        rankdir=LR
        node [shape="box"]

        pivot [label="pivot"]
        list [label="*list"]
        a [label="10"]
        b [label="2"]
        c [label="24"]
        d [label="7"]
        e [label="13"]
        other [label="..." shape="none"]
        
        pivot -> a
        list -> b -> c -> d -> e -> other
    }

3. **Spilt the list**: go through remaining elements of the list, reattach them to other two lists named `left` and `right`, depends on the value of the element. An element will be attached to `right` if it holds a greater value than pivot does, to `left`, otherwise.

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? &right /*AAA*/ : &left /*BBB*/, n);
    }

As we can see later(step 5), `left` will be concatenated to `result` first, which means that `left` should contain elements less than pivot and others will be attached to `right`. And with the definition of `list_add_node_t`, the type of first argument passed to `list_add_node_t` is `node_t**`, so we can conclude that `AAA` is `&right` and `BBB` is `&left`.

After spliting:

    digraph{
        rankdir=LR
        node [shape="box"]

        pivot
        left
        right
        
        a [label="10"]
        b [label="2"]
        c [label="24"]
        d [label="7"]
        e [label="13"]
        otherl [label="...\n(other elements\nless than 10)" shape="none"]
        otherr [label="...\n(other elements\ngreater than 10)" shape="none"]
        
        left -> b -> d -> otherl
        right -> c -> e -> otherr
        pivot -> a
    }

4. **Recursive operation**: call `quicksort` recursively with `left` and `right` as arguments. After this step, elements in `left` and `right` will be ranked in acensing order.

    quicksort(&left);
    quicksort(&right);

After return from recursive calls:

    digraph{
        rankdir=LR
        node [shape="box"]

        pivot
        left
        right
        
        a [label="10"]
        b [label="2"]
        c [label="24"]
        d [label="7"]
        e [label="13"]
        
        lh [label="...\n(elements\nless than 2)" shape="none"]
        lm [label="...\n(elements\nbetween 2 - 7)" shape="none"]
        lt [label="...\n(elements\ngreater than 7)" shape="none"]
        
        rh [label="...\n(elements\nless than 13)" shape="none"]
        rm [label="...\n(elements\nbetween 13 - 24)" shape="none"]
        rt [label="...\n(elements\ngreater than 24)" shape="none"]
        
        pivot -> a
        left -> lh -> b -> lm -> d -> lt
        right -> rh -> e -> rm -> c -> rt
    }

5. **Rebuild the list**: define an empty list named `result`, concatenate `left`, `pivot` and `right` with it one after another. At this moment, we can find that `CCC` would be `list_concat(&result, pivot); list_concat(&result, right);`, which attaches `pivot` to `result` before `right`. Finally, `result` holds the result of sorting and will be set back to `list`.

    node_t *result = NULL;
    list_concat(&result, left);
    list_concat(&result, pivot); list_concat(&result, right); /*CCC*/
    *list = result;

After all:

    digraph{
        rankdir=LR
        node [shape="box"]

        list [label="*list"]
        res [label="result"]
        a [label="10"]
        b [label="2"]
        c [label="24"]
        d [label="7"]
        e [label="13"]
        
        lh [label="...\n(elements\nless than 2)" shape="none"]
        lm [label="...\n(elements\nbetween 2 - 7)" shape="none"]
        lt [label="...\n(elements\ngreater than 7)" shape="none"]
        
        rh [label="...\n(elements\nless than 13)" shape="none"]
        rm [label="...\n(elements\nbetween 13 - 24)" shape="none"]
        rt [label="...\n(elements\ngreater than 24)" shape="none"]
        
        
        res, list -> lh -> b -> lm -> d -> lt
         -> a -> rh -> e -> rm -> c -> rt
    }

With steps mentioned above, the list will be sorted in acensing order.

### List Concatenation
There is another function that aims to concatenate lists, that is `list_concat`.

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next); /*LLL*/
    *left = right;
}

In order to attach `right` to the tail of `left`, the tail of `left` should be found first, that is what the while loop around line 11 - 12 does. We can find that `LLL` should be `left = &((*left)->next)`, which moves `left` to the tail of first list.

## Pseudorandom Number Generator
The generator that being choosen here is **Mersenne Twister**[^1].
There are several reasons of why choosing this algorithm:
1. **Fast**: it takes 10.18 seconds of cpu time in average to generate $10^7$ numbers.
2. **Large prime period**: this generator has prime period with in $2^{19937} - 1$, while consuming only 624 words as working area.
3. **Highly randomness**: the sequence it generate is 623-distributed to 32-bit accuracy.

### MT Algorithm
The MT number generator is based on following algorithm:
$$
x_{k+n} := x_{k+m} \oplus (x^u_k|x^l_{k+1})A,\quad k \in N
$$

Notation:
$w$: the size in bits of generated number
$n$: an integer, which is the degree of recurrence
$m$: an integer with in range $1 \le m \le n$
$r$: the cut point of combination of two numbers (mention below) where $0 \le r \le w-1$
$x_i$: the $i^{th}$ number generated by MT algorithm
$x^u$: the upper $w-r$ bits of $x$
$x^l$: the lower $r$ bits of $x$
$A$: a $w \times w$ matrix with entries in $F_2$, this matrix is in form of $A = \begin{pmatrix} & 1 & & & \\ & & 1 & & \\ & & & \ddots & \\ & & & & 1 \\ a_{w-1} & a_{w-2} & \cdots & \cdots & a_0 \end{pmatrix}$, which makes mutiplication by $A$ is very fast.

To improve accuracy, the generated number $x$ should be transformed by following transformation:
$$
y := x \oplus (x \gg u) \\
y := y \oplus ((y \ll s) \& b) \\
y := y \oplus ((y \ll t) \& c) \\
z := y \oplus (y \gg l)
$$
where $z$ is the final result of generation.

### MT19937
This is a version of Mersenne Twister, with following parameters are given:
$$
(w, n, m, r) = (32, 624, 397, 31) \\
a = 9908b0df \\
(u, s, t, l) = (11, 7, 15, 18) \\
b = 9d2c5680 \\
c = efc60000
$$
where $a$ is the bottom of matrix $A$.

[^1]: [Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator](https://dl.acm.org/doi/pdf/10.1145/272991.272995)

### Implementation

uint32_t prng_gen_number() {
  if (!been_set)
    prng_set_seed(1);

  uint32_t y;
  int k;
  
  if (xi == N) {
    for (k = 0; k < N - M; k++) {
      y = (x[k] & U_MASK) | (x[k + 1] & L_MASK);
      x[k] = x[k + M] ^ (y >> 1) ^ ((y & 0x1) ? _a : 0);
    }

    for (; k < N - 1; k++) {
      y = (x[k] & U_MASK) | (x[k + 1] & L_MASK);
      x[k] = x[k - N + M] ^ (y >> 1) ^ ((y & 0x1) ? _a : 0);
    }

    y = (x[N - 1] & U_MASK) | (x[0] & L_MASK);
    x[N - 1] = x[M - 1] ^ (y >> 1) ^ ((y & 0x1) ? _a : 0);

    xi = 0;
  }

  y = x[xi++];
  y ^= (y >> U);
  y ^= (y << S) & _b;
  y ^= (y << T) & _c;
  y ^= (y >> L);

  return y;
}

The program shown above is my implementation of MT19937. For this implementation, there are several things require detail explanation.
First one is the if statement at line 8, the design of this part of program is to generate `N` random numbers at a time, that is, replace the content of buffer with a bunch of new numbers at a time.
Second is the body of if statement around line 9 - 22, as we can see in the recursive algorithm shown above, the $i^{th}$ number requires $(i-n+m)^{th}$, $(i - n)^{th}$ and $(i - n + 1)^{th}$ number, in order to simplify the program, the loop to fill buffer with new numbers was divided into three parts, with in each part, the loop does no need to concern about possibility of out of range.
Last one is codes around line 24 - 29, which does the final transformation that mentioned about.

## None Recursive `quicksort`
The basic concept of my implementation of non-recursive quicksort is base on the content of this [website](https://alienryderflex.com/quicksort/). And the following is my program to perform non-recursive quicksort.

void nr_quicksort(node_t **list) {
    node_t **begin[MAX_COUNT], **end[MAX_COUNT], **swap;
    node_t *pivot, *ptr, **rt, **lt;
    int value, i = 0, lcnt, rcnt;

    begin[0] = list;
    end[0] = &list_find_tail(*list)->next;

    while (i >= 0) {
      if (*end[i] != *begin[i] && *end[i] != (*begin[i])->next) {
        pivot = *begin[i];
        value = pivot->value;

        ptr = (*begin[i])->next;
        rt = &pivot->next;
        lt = begin[i];

        lcnt = rcnt = 0;
        while (ptr != *end[i]) {
          if (ptr->value > value) {
            *rt = ptr;
            rt = &ptr->next;
            rcnt++;
          } else {
            *lt = ptr;
            lt = &ptr->next;
            lcnt++;
          }

          ptr = ptr->next;
        }

        *rt = *end[i];
        *lt = pivot;

        end[i + 1] = rt;
        end[i] = lt;
        begin[i + 1] = &pivot->next;
        i++;
      
        if (lcnt < rcnt) {
          swap = begin[i]; begin[i] = begin[i - 1]; begin[i - 1] = swap;
          swap = end[i]; end[i] = end[i - 1]; end[i - 1] = swap;
        }
      } else {
        i--;
      }
    }
}

To perform quicksort without recursive function calls, it is important to record the head and tail of each partition manually, which will be maintained in array `begin` and `end`, and the variable `i` acts as stack pointer that shows the partition should be done with for each loop iteration.
There is a huge different between sorting elements in array and elements maintained with linked-list. The order between each element will be maintained automatically while reordering some elements in array, while the order between each node in a linked-list is represented by "link" from one node points to another, which means that "link" should be re-linked while the order is changed, that is why `begin` and `end` are in type of `node_t **`. Since that the content of `begin` are addresses of pointer that points to the head of coresponding partition, the partition is able to be linked back into the list by just modifying the pointer that points to it, which is record in content of `begin`.

## Differences between [linux-list](https://github.com/sysprog21/linux-list) and Quiz Program
The main difference between these two kinds of lists is that the list implemented in [linux-list](https://github.com/sysprog21/linux-list) has only pointers to other nodes in `list_head` structure, which means that for any program requires feature of linked list, they do not need to re-implement their own version of linked list, all they have to do is containing `list_head` in their own structure, and hand off the work of maintaining list to the functions that are already written. Another advantage of abstracting a linked list in this way is that many different structures can be contained in a single list, as long as `list_head` is contained in these structures.

## None Recursive Quick Sort of [linux-list](https://github.com/sysprog21/linux-list)

static void list_nr_qsort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;
    
    struct list_head *beg[MAX_LEVEL], *end[MAX_LEVEL], *item, *safe, *swap;
    struct listitem *pivot, *it;
    int i = 0, lcnt, rcnt;

    beg[0] = head;
    end[0] = head;
    while (i >= 0) {
        if (beg[i]->next != end[i] && beg[i]->next->next != end[i]) {
            pivot = list_entry(beg[i]->next, struct listitem, list);

            lcnt = rcnt = 0;
            for (item = pivot->list.next, safe = item->next;
                 item != end[i];
                 item = safe, safe = item->next) {
                if (cmpint(&list_entry(item, struct listitem, list)->i, &pivot->i) < 0) {
                    list_move_tail(item, &pivot->list);
                    lcnt++;
                } else {
                    list_move(item, &pivot->list);
                    rcnt++;
                }
            }

            end[i + 1] = end[i];
            beg[i + 1] = end[i] = &pivot->list;
            i++;

            if (lcnt < rcnt) {
                swap = beg[i]; beg[i] = beg[i - 1]; beg[i - 1] = swap;
                swap = end[i]; end[i] = end[i - 1]; end[i - 1] = swap;
            }
        } else {
            i--;
        }
    }
}

This function looks similar as non-recursive version that performs on singly-linked list. In this function, a partition is marked by recording the previous node of its first node in `beg`, and the next one of its last node in `end`, base on these records, we can perform in place sorting. With two built in functions `list_move_tail` and `list_move`, which will attach `item` as previous node or next node of `pivot` respectively, the rank of nodes in given partition can be easily reordered with nodes less than `pivot` in front of it and greater ones at its back.