linux2021
>1
考慮以下仿效 Linux 核心 include/linux/list.h 的精簡實作:
#include <stddef.h>
/**
* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
#ifndef container_of
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#endif
/**
* struct list_head - Head and node of a doubly-linked list
* @prev: pointer to the previous node in the list
* @next: pointer to the next node in the list
*/
struct list_head {
struct list_head *prev, *next;
};
/**
* LIST_HEAD - Declare list head and initialize it
* @head: name of the new object
*/
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
/**
* INIT_LIST_HEAD() - Initialize empty list head
* @head: pointer to list head
*/
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
/**
* list_add_tail() - Add a list node to the end of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
/**
* list_empty() - Check if list head has no nodes attached
* @head: pointer to the head of the list
*/
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
/**
* list_is_singular() - Check if list head has exactly one node attached
* @head: pointer to the head of the list
*/
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
/**
* list_splice_tail() - Add list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next, *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
/**
* list_entry() - Calculate address of entry that contains list node
* @node: pointer to list node
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_entry(node, type, member) container_of(node, type, member)
/**
* list_first_entry() - get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
/**
* list_for_each - iterate over list nodes
* @node: list_head pointer used as iterator
* @head: pointer to the head of the list
*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
接著延伸上述程式碼時做 doubly-linked list 的 merge sort:
#include <string.h>
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
struct list_head list;
} queue_t;
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (COND1 || COND2)
break;
fast = fast->next->next;
}
return list_entry(TTT, list_ele_t, list);
}
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
if (list_empty(lhs)) {
list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
list_splice_tail(rhs, head);
return;
}
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = list_entry(lhs->next, list_ele_t, list)->value;
char *rv = list_entry(rhs->next, list_ele_t, list)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
void list_merge_sort(queue_t *q)
{
if (list_is_singular(&q->list))
return;
queue_t left;
struct list_head sorted;
INIT_LIST_HEAD(&left.list);
list_cut_position(&left.list, &q->list, MMM);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
}
fast -> next == list
fasr->next->next == list
&get_middle(&q->list)->list
slow
測試程式碼 main.c 如下:
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
static bool validate(queue_t *q)
{
struct list_head *node;
list_for_each (node, &q->list) {
if (node->next == &q->list)
break;
if (strcmp(list_entry(node, list_ele_t, list)->value,
list_entry(node->next, list_ele_t, list)->value) > 0)
return false;
}
return true;
}
static queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) return NULL;
q->head = q->tail = NULL;
q->size = 0;
INIT_LIST_HEAD(&q->list);
return q;
}
static void q_free(queue_t *q)
{
if (!q) return;
list_ele_t *current = q->head;
while (current) {
list_ele_t *tmp = current;
current = current->next;
free(tmp->value);
free(tmp);
}
free(q);
}
bool q_insert_head(queue_t *q, char *s)
{
if (!q) return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *new_value = strdup(s);
if (!new_value) {
free(newh);
return false;
}
newh->value = new_value;
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = newh;
q->size++;
list_add_tail(&newh->list, &q->list);
return true;
}
int main(void)
{
FILE *fp = fopen("cities.txt", "r");
if (!fp) {
perror("failed to open cities.txt");
exit(EXIT_FAILURE);
}
queue_t *q = q_new();
char buf[256];
while (fgets(buf, 256, fp))
q_insert_head(q, buf);
fclose(fp);
list_merge_sort(q);
assert(validate(q));
q_free(q);
return 0;
}
根據 merge-sort 的實作方法,第一步先將整個序列對半分割:
分別將左右兩個序列依照一樣的步驟分割直到不能再分割(size is 1)後倆倆合併 :
對於 Linked List 裡面該如何將其分成兩段?在程式碼中的 get_middle
使用的方法是利用 fast
、 slow
指標,fast
指標走訪 linked list 的速度是 slow
的兩倍,因為是 doubly linked list 所以當 fast
走到開頭的時候代表整個串列已經走訪完,所以 slow
指標會指在串列的中間位置,對應的程式碼為:
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (fast->next == list || fast->next->next == list)
break;
fast = fast->next->next;
}
return list_entry(slow, list_ele_t, list);
}
上述程式碼在最後的回傳值是 list_ele_t*
(pointer to list_ele_t) ,但是 slow
是 struct list_head*
(pointer to struct list_head) ,所以在回傳時使用 list_entry
巨集算出包含 slow
指標的 list_ele_t
記憶體位置。
接著看程式碼中在哪裡呼叫 get_middle
:
...
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
...
由此可知是在 list_cut_position
中呼叫的,接下來看看 list_cut_position
的實作:
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
對應的操作如圖:
e1
為 list 的開頭 e3
為中間的節點e1
(head_from 所指的記憶體位址) 的 next 指向 e4
(node->next 所指的記憶體位址),e4
(head_from->next 所指的記憶體位址) 的 pre 指向 e1
(head_from 所指的記憶體位址)接下來針對分出的兩段 linked list 個別去做 merge sort 依序遞迴下去,
(Keep going)
2
考慮函式 func 接受一個 16 位元無號整數 N,並回傳小於或等於 N 的 power-of-2 (漢字可寫作為 2 的冪)
假定 N = 101012 = 2110,那麼 func(21) 要得到 16,請補完程式碼,使其運作符合預期。
實作程式碼如下:
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> X;
N |= N >> Y;
N |= N >> Z;
return (N + 1) >> 1;
}
or(|)
運算後得到的結果可見最高位元的右邊一格變成 1or
運算才能把前面 4 位元都變為 1 ,結果如圖or
便可以把它填滿並變成 1is_power_of_2
在 arch/microblaze/mm/pgtable.c 中將其定為 macro:
#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
若該數為 2 的冪次方則該數的最高非 0 位元右側必定全都為 0 ,將該數對該數扣 1 做 and
運算若為 0 則該數為 2 的冪次方
contributed by < hankchang805 > quiz4 題目 測驗 1 考慮到以下 bitcpy 實作,允許開發者對指定的記憶體區域,逐 bit 進行資料複製: #include <stdint.h> #include <stdio.h> #include <string.h>
Mar 30, 2020contributed by < hankchang805 > 開發紀錄 queue.h queue_t 為了讓 q_insert_tail 以及 q_size 可以在 $O(1)$ 的時間複雜度內完成,所以增加 tail (指向 queue 中最後一個元素)以及 size (紀錄目前 queue 有幾個元素) typedef struct { list_ele_t *head; list_ele_t *tail;
Mar 28, 2020or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up