# 2019q3 Homework3 (list)
contributed by < `kksweet8845` >
## Implementation of `Merge Sort`
After I finish the implementation of merge sort,it make me understand `Sort algorithm` more further and more clear.
Here, is my analysis of average time of Insertion, Quick and Merge sort.
And, I compare the time of three algorithm with differen length of array
Here,The length of array is more large a bit
I analysis the method of partition of merge sort.
- Fisrt partition - always separate to (1, n-1)
- Mean partition - always separate to ( n/2, n/2 )
- Rand partition - randmoly separate to any combination.
We can see that the method of first method is the worst, while the other two method have similiar preformance.
## Acquirement
- [x] Why linux implement linked list by using `macro` instead of `function call`
- [x] Under what circumstance, where does linux applies linked list? Please take three real examples, with descriptions, and think about the motivation of applying linked list
- [x] What is the usage of `typeof` of GNU extension ?
- [ ] What is the meaning of designing `LIST_POSIONING` ? hint: linux memory management
- [x] Describe the principle of the macro shown following
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- [x] Except the operation `add` and `delete` you familiar with, `list.h` are also define a series of operations, why ? and think about the benefits ?
- [x] What is the purpose of implementing the linked list with circularity?
- [x] Under what occasion will need to sort the linked list ? Take a example implementing in OS
- [x] Under what circumstance will need to find the kth big/small element in a array? How to implement it?
- [x] What is the difference of `list_of_each_safe` and `list_for_each` ? What is the influence of `safe` in execution environment ?
- [ ] What is the influence of `for_each` style for developer?
* hint : Perl and Python
- [ ] What is the meaning of `@` in the comment ? Can you apply it in the follow-up development?
- [ ] What does it do in the directory,`tests/` ? What is the spirit of this for software engineer ?
- [ ] How can `tests/` be refined and defined ?
## Why linux implement linked list by using `macro` instead of `function call`
Typically, the major difference of function call and macro is about the `preprocessing` and `compiled`.
- `Macro` is been ==replaced== when executing preprocessing stage.
- While, `function call` is been compiled and needs to be invoked in execution environment. It will produce the ==overhead== in each invocation. The execution environment will need to push the address of function to the stack then pop up finished afterward.
Although, `macro` is looks like more convenient than `function call`, the macro also need to sacrifice its safty and unexpected-prone behavior when defined imprecisely.
Instead of conclusion with words, I experiment the method of macro and functions to see what happened when using macro and functions, respectively.
### Difference between `Macro` & `function`
I wrote the following code to see what happened during `preprocessing`.
```cpp
#include<stdio.h>
// with the constant
#define NUMBER 10
// function-like
#define triple(b) (typeof(b))b*b*b
int num(){
return 10;
}
int f_triple(int b){
return b*b*b;
}
int main() {
printf("%d\n", NUMBER);
printf("%d\n", triple((int)10));
printf("%d\n", f_triple(int(10)));
}
```
Execute with
```shell
>> gcc -E func_ma.c -o func_ma
```
Then, it produce the following code
```cpp
stdlib replacement...
...
# 8 "func_ma.c"
int num(){
return 10;
}
int f_triple(int b){
return b*b*b;
}
int main() {
printf("%d\n", 10);
printf("%d\n", (typeof((int)10))(int)10*(int)10*(int)10);
printf("%d\n", f_triple(int(10)));
}
```
We can see that the constant `NUMBER` is replace with the defined string. And, the function-like macro `triple()` is literally replaced with the defined string.
However, what if I pass a expression into the function-like macro ? That is,
```cpp
#define triple(b) (typeof(b)) b*b*b
printf("%d", triple(1+2));
```
Which will produce the unexpected result.
```cpp
... stdlib
printf("%d", (typeof(1+2)) 1+2*1+2*1+2);
```
Finally, I test the performance of `macro` and `function call`, each with 50 iteration.
- Conclusion
Although `Macro` is more efficient than function call, it also increase its vulnerability. The main purpose of defining with macro is that linked list is too common in linux kernel. Linux kernel used linked list a lot in kernel to implement some operation liked ==Task(Process)==, ==net(Socket)==,etc.
## Under what circumstance, where does linux applies linked list?
1. `struct task_structure`
The `struct task_structure` uses the circular doubly linked list to implement the process management.
```cpp
struct task_struct {
...
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_info sched_info;
struct list_head tasks;
...
}
```
- `struct task_struct` uses doubly linked list to handle the operation of process management.
- The `task_struct` implemented the doubly linked list with a struct named `sturct list_head`, which can perform a series of operation of linked list, such as `list_add`, `list_add_tail` and `list_del`,etc.
- It is useful when the scheduler operate these task to different queue, such like `waiting`, `ready`,etc.
2. `struct clk`
```cpp
struct clk {
struct list_head node; //Also implemented with doubly linked list
const struct clkops *ops;
const char *name;
struct clk *parent;
struct list_head children;
struct list_head sibling; /* node for children */
...
};
```
- `struct clk` is implemented by using doubly linked list.
- In a typical ARM system-on-chip (SoC), there can be dozens of different clocks for use by various I/O and other devices in the SoC. Typically those clocks are hooked together into elaborate tree-like structures.
- In those trees, child clocks can sometimes only change their frequency if the parent (and any other children) are correspondingly changed; disabling certain clocks will affect other clocks in the system and so on.
- Each of the entries in the clk_hw_ops structure correspond to a function in the driver-facing API for the clock framework. That API does some sanity checking before calling the corresponding operation from clk_hw_ops:
```cpp
struct clk_hw_ops {
int (*prepare)(struct clk *clk);
void (*unprepare)(struct clk *clk);
int (*enable)(struct clk *clk);
void (*disable)(struct clk *clk);
unsigned long (*recalc_rate)(struct clk *clk);
long (*round_rate)(struct clk *clk, unsigned long,
unsigned long *);
int (*set_parent)(struct clk *clk, struct clk *);
struct clk * (*get_parent)(struct clk *clk);
int (*set_rate)(struct clk *clk, unsigned long);
};
```
Resource : [struct clk](https://lwn.net/Articles/472998/)
>> There is funny thing happened when the author explain the `clk_ops`. The author used the word ==unprepare== to represent the state which is not prepared, however, the native English speaker disagreed with that definition of function. Then, This issue caused a lot of comments.
3. `command.c`
It is a definition of IBM ASm Service Processor Device Driver, which use the `struct list_head` to operate the command list.
#### `enqueue_command`
This method just invoked the method of list_head, `list_add_tail`.
```cpp
static void enqueue_command(struct service_processor *sp, struct command *cmd)
{
list_add_tail(&cmd->queue_node, &sp->command_queue);
}
```
#### `dequeue_command`
This method to pop out the entry in the front of queue. And, it invoked the method in `list.h`.
- `list_empty()` : Check whether list is empty.
- `list_del_init()` : Delete the given entry.
- `list_entry()` : Get the address of object which contains the `list_head`
```cpp
static struct command *dequeue_command(struct service_processor *sp)
{
struct command *cmd;
struct list_head *next;
if (list_empty(&sp->command_queue))
return NULL;
next = sp->command_queue.next;
list_del_init(next);
cmd = list_entry(next, struct command, queue_node);
return cmd;
}
```
Extension :
- [<include/linux/sched.h>](https://github.com/torvalds/linux/blob/master/include/linux/sched.h)
- [linux process management](http://140.120.7.21/LinuxRef/ProcMana/ProcessManaging.html#TaskS)
## What is the usage of `typeof` in GNU extension ?
- A method to reger to the type of an expression is with typeof.
- It can be dynamically declared the variable corresponding to the given argument. Such like,
```cpp
# define add(a,b) ({ \
typeof(a) _a = a; \
typeof(b) _b = b; \
_a+_b; \
})
# define autoCast(x,y) typeof(x)y;
# define pointer(T,y) typeof(T *)y;
# define sum(start, end, interval) ({\
typeof(start) _sum = 0;\
for(typeof(start) i=start;i<end;i=i+interval) _sum+=i;\
_sum;})
```
Then, we can use the following declaration method
```cpp
int main(){
int a;
autoCast(a, b);
pointer(int, c);
b = 15;
a = 10;
c = &b;
printf("%d\n", add(a,b)); //25
printf("%d\n", add(a, *c)); //25
printf("%.2f\n", sum(0.0f, 101.0f, 1.0f)); //5050.00
printf("%d\n", sum(0u,101u,2u)); //2550
}
```
- The role of `typeof` play an important role to implement a flexible operation in order to shorten the code and make the code more elegant.
- It is also make the C program have the power to check the type of variable for fear of occurring undefined computation.
- It extends the usage of `macro` with dynamic type operation.
Resource :
- [Referring to a Type with typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)
- [Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords)
- [Statements and Declarartions in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html#Statement-Exprs)
## Describe the principle of the macro shown as following
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- `__extension__` which is just an empty literally.
```cpp
#if !__GNUC_PREREQ (2,8)
# define __extension__ /* Ignore */
#endif
```
- `__typeof__` is the version of `typeof` in ansi C and ISO C, which have no extension `typeof`.
Right now, we can regard the code above as following.
```cpp
#define container_of(ptr, type, member) \
({ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- And the statement are enclosed with a pair of {},which is called compound statement. It may appear as an expression in GNU C. This allows you to use loops, switches, and local variables within an expression.
Let take a look at `&(((type *) 0)->member)`, according to the c standard, it said
- `(type*)0` : represent a null pointer constant of that type
- And the `NULL` expands to an implementation-defined null pointer constant
- >> It specifically defined that `&((type*0)->member)` is the offset in bytes, to the structure member(designated by member-designator), from the beginning of its structure(designed by type).
- That is, `((type *) 0)->member` means the member which derivated by member-designator.
- `__typeof__(((type *) 0)->member)` define the type of that struct member, which is used to declared a pointer to that sturct,`__typeof__(((type *) 0)->member) *`,named `__pmember`. Finally, let `__pmember` points to the given address of the specific structure address.
Now, it's time to consider the expression,`(type *) ((char *) __pmember - offsetof(type, member))`
- It converses `__pmember` to the type of pointer of char,which make the `__pmember` shifts according to its type, that is, one byte per shift.
- Then, The macro `offsetof(type,member)` is defined by c standard
>> `offsetof(type, member-designator)`, which expands to an integer constant expression that has type `size_t`, the value of which is the offset in bytes, to the structure member(designated by member-designator), from the beginning of its tructure(designated by type).
- That is, `(type *) ((char *) __pmember - offsetof(type, member))` will return the address of the structure containing the given object of member structure.
## Except the operations `add` and `delete` you familiar with, list.h are also define a series of operations, why ? and think about the benefits ?
Except the operation `add` and `del`, there are many other operations such like
- `list_add_tail`
- Add the node to the end of list.
- `list_cut_position(head_to, head_from, node)`
- Replaced the `head_to` from `head_from` until the `node` in list of `head_from`.
- `list_del_init(node)`
- Delete the `node` and initialize it with `INIT_LIST_HEAD`.
- `list_empty(head)`
- Check the `head` is empty or not
- `list_is_sigular`.
- Check the `head` is sigular or not.
- `list_move_tail(node, head)`
- Move the `node` to the end of `head`
- `list_move(node, head)`
- Move the `node` to the beginning of `head`
- `list_splice_init`
- Add list nodes from a list to the beginning of another list.
- `list_splice_tail_init`
- The tail version of `list_splice_init`, which will add nodes to the end of another list.
- `list_splice_tail`
- The version of `list_splice_init` without `init`.
- `list_splice`
- The fundemental operation of adding nodes to another list.
- `list_entry(node, type, member)`
- The alias of `container_of(node, type, member)`
- `list_first_entry`
- Get the first entry of the list
- `list_for_each_entry`
- Iterate over list entries.
- `list_for_each_entry_safe`
- Iterate over list entries and allow deletes.
- `list_for_each_safe`
- Iterate over list nodes and allow deletes.
- `list_for_each`
- Iterate over list nodes.
- `list_last_entry`
- Get the last entry of the list.
### Why?
- Defining a series of operations of linked list will short the length of code and make the code more elegant.
- Espeically for the series of opeartions with prefix `list_for-` are defined by `macro` which make the code more readble and more convenient.
- Defining a series of similiar operations with stages, which reduce the length of code and make the maintenance easier.
```cpp
#define list_entry(node, type, member) container_of(node, type, member)
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
```
The code above are all relative but slightly different between each other.
### Benefits?
- Defining plenty of operations can streamline the complication of code which make the logic of program more clear and simple.
- Eliminating the stereotype of low-level programing language, which make the C more readable and easy to maintain.
## What is the purpose of implementing the linked list with circularity?
- Eliminate the vulnerability of `segementation fault`
- More flexible more the definition of head and tail. Because of circularity, each node can be the head and tail.
- Useful for implementation of queue. Because of the characteristic of FIFO, this feature demand the changable head and tail.
- Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
- Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap, which can has better compliexity.
Resource: [Circular Linked list](https://www.geeksforgeeks.org/circular-linked-list/)
## Under what circumstance will need to sort the linked list ?
- When query to a database, it's usually needed to be sort by its `id` in each table. Then search it by using Binary search tree.
- In data mining, there is a algorithm called Apriori Algorithm, which can find some assocaition rule in a dataset. When using this algorithm, it need to sort the frequent rule.
## Under what circumstance will need to find the kth big/small element in a array? How to implement it?
- $O(nlgn)$
- Using the qsort or merge sort to sort the array, then access the kth element of array.
- It only need $O(nlgn)$ to sort the array. $O(1)$ to find out the kth big or kth(n-k) small element of array.
- $O(n + klgn)$
- Using the max-heap to build a max-heap in a array then extract the max-heap k times will obtain the kth big or kth(n-k) small element in array.
- Because building max-heap only needs $O(n)$ with tighter bound, and extract a max-heap then rebuild the max-heap need $O(lgn)$.
Here is my experiment of max-heap.
```cpp
void max_heapify(uint16_t **arr, uint16_t ri, uint16_t arr_len){
uint16_t left = (ri)*2+1, largest;
uint16_t right = (ri+1)*2;
if( left <= arr_len && (*arr)[left] > (*arr)[ri] ){
largest = left;
}else {
largest = ri;
}
if( right <= arr_len && (*arr)[right] > (*arr)[largest])
largest = right;
if(largest != ri){
(*arr)[ri] = (*arr)[largest] ^ (*arr)[ri];
(*arr)[largest] = (*arr)[ri] ^ (*arr)[largest];
(*arr)[ri] = (*arr)[ri] ^ (*arr)[largest];
max_heapify(arr, largest, arr_len);
}
}
void build_max_heap(uint16_t** arr, uint16_t arr_len){
for(int i= (arr_len-2)/2;i>=0;i--){
max_heapify(arr, i, arr_len);
}
}
void heap_sort(uint16_t** arr, uint16_t arr_len){
for(int i=arr_len-1;i>=1;i--){
(*arr)[0] = (*arr)[i] ^ (*arr)[0];
(*arr)[i] = (*arr)[0] ^ (*arr)[i];
(*arr)[0] = (*arr)[0] ^ (*arr)[i];
max_heapify(arr, 0, i-1);
}
}
```
```cpp
int main(void){
random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
uint16_t *max_h = malloc(sizeof(uint16_t)*(256));
for(int i=0;i<256;i++){
max_h[i] = values[i];
}
build_max_heap(&max_h, 256);
heap_sort(&max_h, 256);
qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
for(size_t i=0;i<ARRAY_SIZE(values);i++){
assert(max_h[i] == values[i]);
}
return 0;
}
```
- $O(n)$ in expected linear time
- The method in here is to use randomized quick sort. Instead of finishing the whole process of quick sort, we apply the concept in quick sort. For every iteration of quick sort, it will partition out two parts, one is the part is smaller than the pivot, while the other part is all greater than the pivot. In here, we just randomly choose the element as pivot then swap it with first element in array. After finishing the rerange process, we see is the key of pivot equal to the wanted key value or not. If it is equal, we just return the pivot. If key value of pivot is greater than wanted key value, recursive it- self but with the array of left side. Otherwise, recursive itself but with the array of right side. Here is my implementation..
I modified the `list_qsort()` to a selection problem.
```cpp
static int list_random_qsort(struct list_head *head, uint16_t k){
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return -1 ;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
uint16_t less_num = 0;
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0){
list_move_tail(&item->list, &list_less);
less_num++;
}
else
list_move(&item->list, &list_greater);
}
if(less_num+1 == k)
return pivot->i;
else if(less_num+1 > k)
return list_random_qsort(&list_less, k);
else
return list_random_qsort(&list_greater, k-less_num-1);
}
```
## What is the difference of list_of_each_safe and list_for_each ? What is the influence of safe in execution environment ?
- It can avoid the situation of deleting the node of list for fear of occurring memory leackaged.
- It create two pointer, one is `entry`, another is `safe`. The former pointer is for your manipulation. While the latter is a precaution if you delete the node, that is which `next` points to `NULL`, so that the next node will be missed. Thus, the `safe` pointer can rescue this situation, because it save the address of `next` pointer in each iteration.
## What is the influence of for_each style for developer?
## What is the meaning of @ in the comment ? Can you apply it in the follow-up development?
Sign in with Wallet
Connect another wallet