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:

List Sorting

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

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:

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:

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:

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:

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_k^u|x_{k+1}^l)A,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=\left(\begin{array}{ccccc}& 1& & & \\ & & 1& & \\ & & & \ddots & \\ & & & & 1\\ a_{w-1}& a_{w-2}& \cdots & \cdots & a_0\end{array}\right)$, which makes mutiplication by

$A$ is very fast.

To improve accuracy, the generated number

$x$ should be transformed by following transformation:

$$\begin{gathered} y:=x\oplus (x\gg u) \\ y:=y\oplus ((y\ll s)\mathrm{\&}b) \\ y:=y\oplus ((y\ll t)\mathrm{\&}c) \\ z:=y\oplus (y\gg l) \end{gathered}$$
where

$z$ is the final result of generation.

MT19937

This is a version of Mersenne Twister, with following parameters are given:

$$\begin{gathered} (w,n,m,r)=(32,624,397,31) \\ a=9908b0df \\ (u,s,t,l)=(11,7,15,18) \\ b=9d2c5680 \\ c=efc60000 \end{gathered}$$
where

$a$ is the bottom of matrix

$A$.

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. 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 and Quiz Program

The main difference between these two kinds of lists is that the list implemented in 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

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.

---

1. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator ↩︎