【DIY kernel】實作簡單資料結構 - Doubly Linked List (雙向鏈結串列)

借用老師投影片的圖~~

實作 timer 之前必須要有基本的資料結構

這部分跟寫作業一樣

只要有修過資料結構的都有寫過

所以就不贅述細節了

先定義 list 和 node 的結構



struct node
{
struct node *next;
struct node *prev;
};
typedef struct node node_t;

struct list
{
node_t head;
node_t tail;
};
typedef struct list list_t;



接下來就是實作double linked list需要用到的方法：

//判斷是否為第一個node
u8int isHeadnode (node_t *node);
//判斷是否為中間的node

u8int isInternalNode (node_t * node);
//判斷是否為最後一個node
u8int isTailNode (node_t * node);
//初始化List
void init_list (list_t * list);
//取得第一個node
node_t *first_node (list_t * list);
//取得最後一個node
node_t *last_node(list_t * list);
//判斷該list是否為空
u8int is_Empty (list_t * list);
//將node依附在某個node之後
void append_list (node_t * before, node_t * node);
//將node插入最前面
void insert_front (list_t * list, node_t * node);
//將node插入最後面
void insert_rear (list_t * list, node_t * node);
//將node刪除
void remove_node (node_t * node);
//將第一個node刪除
node_t *remove_firstNode (list_t * list);
//將最後一個node移除
node_t *remove_lastNode (list_t * list);

以下附上投影片上的程式碼


u8int isHeadNode (node_t *node){
return (node != NULL) && (node->prev == NULL) && (node->next != NULL);
}

u8int isInternalNode (node_t *node){
return (node != NULL) && (node->prev != NULL) && (node->next != NULL);

}

u8int isTailNode (node_t *node){
return (node != NULL) && (node->prev != NULL) && (node->next == NULL);
}

u8int is_Empty (list_t *list){
return (list->head.next == &list->tail);
}

void init_list (list_t *list){
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}

node_t *first_node (list_t *list){
if (is_Empty (list))
return NULL;
return list->head.next;
}

node_t *last_node (list_t *list){
if (is_Empty (list))
return NULL;
return list->tail.prev;
}

void append_list (node_t *before, node_t *node){
if( before->next != NULL )
before->next->prev = node;
node->prev = before;
node->next = before->next;
before->next = node;
}

void insert_front (list_t *list, node_t *node){
append_list( &list->head, node );
}

void insert_rear (list_t *list, node_t *node){
append_list( list->tail.prev, node );
}

void remove_node (node_t *node){
if (isInternalNode (node)){
node->prev->next = node->next;
node->next->prev = node->prev;
node->next = NULL;
node->prev = NULL;
}
}

node_t *remove_firstNode (list_t *list){
node_t *node = first_node (list);
if (node != NULL)
remove_node (node);

return node;
}

node_t *remove_lastNode (list_t *list){
node_t *node = last_node (list);
if (node != NULL)
remove_node (node);

return node;
}