赌球触犯了什么法律,富贵乐园棋牌中心,美股金沙集团股票代码查询(中国)·官方网站

Linux內(nèi)核代碼中廣泛使用了數(shù)據(jù)結(jié)構(gòu)和算法，其中最常用的兩個是鏈表和紅黑樹。

鏈表

Linux內(nèi)核代碼大量使用了鏈表這種數(shù)據(jù)結(jié)構(gòu)。鏈表是在解決數(shù)組不能動態(tài)擴(kuò)展這個缺陷而產(chǎn)生的一種數(shù)據(jù)結(jié)構(gòu)。鏈表所包含的元素可以動態(tài)創(chuàng)建并插入和刪除。鏈表的每個元素都是離散存放的，因此不需要占用連續(xù)的內(nèi)存。鏈表通常由若干節(jié)點組成，每個節(jié)點的結(jié)構(gòu)都是一樣的，由有效數(shù)據(jù)區(qū)和指針區(qū)兩部分組成。有效數(shù)據(jù)區(qū)用來存儲有效數(shù)據(jù)信息，而指針區(qū)用來指向鏈表的前繼節(jié)點或者后繼節(jié)點。因此，鏈表就是利用指針將各個節(jié)點串聯(lián)起來的一種存儲結(jié)構(gòu)。

（1）單向鏈表

單向鏈表的指針區(qū)只包含一個指向下一個節(jié)點的指針，因此會形成一個單一方向的鏈表，如下代碼所示。

struct list {
int data; /*有效數(shù)據(jù)*/
struct list *next; /*指向下一個元素的指針*/
};

如圖所示，單向鏈表具有單向移動性，也就是只能訪問當(dāng)前的節(jié)點的后繼節(jié)點，而無法訪問當(dāng)前節(jié)點的前繼節(jié)點，因此在實際項目中運用得比較少。

單向鏈表示意圖

（2）雙向鏈表

如圖所示，雙向鏈表和單向鏈表的區(qū)別是指針區(qū)包含了兩個指針，一個指向前繼節(jié)點，另一個指向后繼節(jié)點，如下代碼所示。

struct list {
int data; /*有效數(shù)據(jù)*/
struct list *next; /*指向下一個元素的指針*/
struct list *prev; /*指向上一個元素的指針*/
};

雙向鏈表示意圖

（3）Linux內(nèi)核鏈表實現(xiàn)

單向鏈表和雙向鏈表在實際使用中有一些局限性，如數(shù)據(jù)區(qū)必須是固定數(shù)據(jù)，而實際需求是多種多樣的。這種方法無法構(gòu)建一套通用的鏈表，因為每個不同的數(shù)據(jù)區(qū)需要一套鏈表。為此，Linux內(nèi)核把所有鏈表操作方法的共同部分提取出來，把不同的部分留給代碼編程者自己去處理。Linux內(nèi)核實現(xiàn)了一套純鏈表的封裝，鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu)只有指針區(qū)而沒有數(shù)據(jù)區(qū)，另外還封裝了各種操作函數(shù)，如創(chuàng)建節(jié)點函數(shù)、插入節(jié)點函數(shù)、刪除節(jié)點函數(shù)、遍歷節(jié)點函數(shù)等。

Linux內(nèi)核鏈表使用struct list_head數(shù)據(jù)結(jié)構(gòu)來描述。

struct list_head {
struct list_head *next, *prev;
};

struct list_head數(shù)據(jù)結(jié)構(gòu)不包含鏈表節(jié)點的數(shù)據(jù)區(qū)，通常是嵌入其他數(shù)據(jù)結(jié)構(gòu)，如struct page數(shù)據(jù)結(jié)構(gòu)中嵌入了一個lru鏈表節(jié)點，通常是把page數(shù)據(jù)結(jié)構(gòu)掛入LRU鏈表。

struct page {
...
struct list_head lru;
...
}

鏈表頭的初始化有兩種方法，一種是靜態(tài)初始化，另一種動態(tài)初始化。

把next和prev指針都初始化并指向自己，這樣便初始化了一個帶頭節(jié)點的空鏈表。

/*靜態(tài)初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name)
struct list_head name = LIST_HEAD_INIT(name)

/*動態(tài)初始化*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

添加節(jié)點到一個鏈表中，內(nèi)核提供了幾個接口函數(shù)，如list_add()是把一個節(jié)點添加到表頭，list_add_tail()是插入表尾。

void list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

遍歷節(jié)點的接口函數(shù)。

#define list_for_each(pos, head)
for (pos = (head)->next; pos != (head); pos = pos->next)

這個宏只是遍歷一個一個節(jié)點的當(dāng)前位置，那么如何獲取節(jié)點本身的數(shù)據(jù)結(jié)構(gòu)呢？這里還需要使用list_entry()宏。

#define list_entry(ptr, type, member)
container_of(ptr, type, member)
container_of()宏的定義在kernel.h頭文件中。
#define container_of(ptr, type, member) ({
const typeof( ((type *)0)->member ) *__mptr = (ptr);
(type *)( (char *)__mptr - offsetof(type,member) );})

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

其中offsetof()宏是通過把0地址轉(zhuǎn)換為type類型的指針，然后去獲取該結(jié)構(gòu)體中member成員的指針，也就是獲取了member在type結(jié)構(gòu)體中的偏移量。最后用指針ptr減去offset，就得到type結(jié)構(gòu)體的真實地址了。

下面是遍歷鏈表的一個例子。

static ssize_t class_osdblk_list(struct class *c,
struct class_attribute *attr,
char *data)
{
int n = 0;
struct list_head *tmp;

list_for_each(tmp, &osdblkdev_list) {
struct osdblk_device *osdev;

osdev = list_entry(tmp, struct osdblk_device, node);

n += sprintf(data+n, "%d %d %llu %llu %sn",
osdev->id,
osdev->major,
osdev->obj.partition,
osdev->obj.id,
osdev->osd_path);
}
return n;
}

紅黑樹

紅黑樹（Red Black Tree）被廣泛應(yīng)用在內(nèi)核的內(nèi)存管理和進(jìn)程調(diào)度中，用于將排序的元素組織到樹中。紅黑樹被廣泛應(yīng)用在計算機科學(xué)的各個領(lǐng)域中，它在速度和實現(xiàn)復(fù)雜度之間提供一個很好的平衡。

紅黑樹是具有以下特征的二叉樹。

每個節(jié)點或紅或黑。

每個葉節(jié)點是黑色的。
如果結(jié)點都是紅色，那么兩個子結(jié)點都是黑色。
從一個內(nèi)部結(jié)點到葉結(jié)點的簡單路徑上，對所有葉節(jié)點來說，黑色結(jié)點的數(shù)目都是相同的。

紅黑樹的一個優(yōu)點是，所有重要的操作（例如插入、刪除、搜索）都可以在O(log n)時間內(nèi)完成，n為樹中元素的數(shù)目。經(jīng)典的算法教科書都會講解紅黑樹的實現(xiàn)，這里只是列出一個內(nèi)核中使用紅黑樹的例子，供讀者在實際的驅(qū)動和內(nèi)核編程中參考。這個例子可以在內(nèi)核代碼的documentation/Rbtree.txt文件中找到。

#include
#include
#include
#include
#include
#include
#include

MODULE_AUTHOR("figo.zhang");
MODULE_DESCRIPTION(" ");
MODULE_LICENSE("GPL");

struct mytype {
struct rb_node node;
int key;
};

/*紅黑樹根節(jié)點*/
struct rb_root mytree = RB_ROOT;
/*根據(jù)key來查找節(jié)點*/
struct mytype *my_search(struct rb_root *root, int new)
{
struct rb_node *node = root->rb_node;

while (node) {
struct mytype *data = container_of(node, struct mytype, node);

if (data->key > new)
node = node->rb_left;
else if (data->key < new)
node = node->rb_right;
else
return data;
}
return NULL;
}

/*插入一個元素到紅黑樹中*/
int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent=NULL;

/* 尋找可以添加新節(jié)點的地方 */
while (*new) {
struct mytype *this = container_of(*new, struct mytype, node);

parent = *new;
if (this->key > data->key)
new = &((*new)->rb_left);
else if (this->key < data->key) {
new = &((*new)->rb_right);
} else
return -1;
}

/* 添加一個新節(jié)點 */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);

return 0;
}

static int __init my_init(void)
{
int i;
struct mytype *data;
struct rb_node *node;

/*插入元素*/
for (i =0; i < 20; i+=2) {
data = kmalloc(sizeof(struct mytype), GFP_KERNEL);
data->key = i;
my_insert(&mytree, data);
}

/*遍歷紅黑樹，打印所有節(jié)點的key值*/
for (node = rb_first(&mytree); node; node = rb_next(node))
printk("key=%dn", rb_entry(node, struct mytype, node)->key);

return 0;
}

static void __exit my_exit(void)
{
struct mytype *data;
struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node)) {
data = rb_entry(node, struct mytype, node);
if (data) {
rb_erase(&data->node, &mytree);
kfree(data);
}
}
}
module_init(my_init);
module_exit(my_exit);

mytree是紅黑樹的根節(jié)點，my_insert()實現(xiàn)插入一個元素到紅黑樹中，my_search()根據(jù)key來查找節(jié)點。內(nèi)核大量使用紅黑樹，如虛擬地址空間VMA的管理。

無鎖環(huán)形緩沖區(qū)

生產(chǎn)者和消費者模型是計算機編程中最常見的一種模型。生產(chǎn)者產(chǎn)生數(shù)據(jù)，而消費者消耗數(shù)據(jù)，如一個網(wǎng)絡(luò)設(shè)備，硬件設(shè)備接收網(wǎng)絡(luò)包，然后應(yīng)用程序讀取網(wǎng)絡(luò)包。環(huán)形緩沖區(qū)是實現(xiàn)生產(chǎn)者和消費者模型的經(jīng)典算法。環(huán)形緩沖區(qū)通常有一個讀指針和一個寫指針。讀指針指向環(huán)形緩沖區(qū)中可讀的數(shù)據(jù)，寫指針指向環(huán)形緩沖區(qū)可寫的數(shù)據(jù)。通過移動讀指針和寫指針實現(xiàn)緩沖區(qū)數(shù)據(jù)的讀取和寫入。

在Linux內(nèi)核中，KFIFO是采用無鎖環(huán)形緩沖區(qū)的實現(xiàn)。FIFO的全稱是“First In First Out”，即先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，它采用環(huán)形緩沖區(qū)的方法來實現(xiàn)，并提供一個無邊界的字節(jié)流服務(wù)。采用環(huán)形緩沖區(qū)的好處是，當(dāng)一個數(shù)據(jù)元素被消耗之后，其余數(shù)據(jù)元素不需要移動其存儲位置，從而減少復(fù)制，提高效率。

（1）創(chuàng)建KFIFO

在使用KFIFO之前需要進(jìn)行初始化，這里有靜態(tài)初始化和動態(tài)初始化兩種方式。

int kfifo_alloc(fifo, size, gfp_mask)

該函數(shù)創(chuàng)建并分配一個大小為size的KFIFO環(huán)形緩沖區(qū)。第一個參數(shù)fifo是指向該環(huán)形緩沖區(qū)的struct kfifo數(shù)據(jù)結(jié)構(gòu)；第二個參數(shù)size是指定緩沖區(qū)元素的數(shù)量；第三個參數(shù)gfp_mask表示分配KFIFO元素使用的分配掩碼。

靜態(tài)分配可以使用如下的宏。

#define DEFINE_KFIFO(fifo, type, size)
#define INIT_KFIFO(fifo)

（2）入列

把數(shù)據(jù)寫入KFIFO環(huán)形緩沖區(qū)可以使用kfifo_in()函數(shù)接口。

int kfifo_in(fifo, buf, n)

該函數(shù)把buf指針指向的n個數(shù)據(jù)復(fù)制到KFIFO環(huán)形緩沖區(qū)中。第一個參數(shù)fifo指的是KFIFO環(huán)形緩沖區(qū)；第二個參數(shù)buf指向要復(fù)制的數(shù)據(jù)的buffer；第三個數(shù)據(jù)是要復(fù)制數(shù)據(jù)元素的數(shù)量。

（3）出列

從KFIFO環(huán)形緩沖區(qū)中列出或者摘取數(shù)據(jù)可以使用kfifo_out()函數(shù)接口。

#define kfifo_out(fifo, buf, n)

該函數(shù)是從fifo指向的環(huán)形緩沖區(qū)中復(fù)制n個數(shù)據(jù)元素到buf指向的緩沖區(qū)中。如果KFIFO環(huán)形緩沖區(qū)的數(shù)據(jù)元素小于n個，那么復(fù)制出去的數(shù)據(jù)元素小于n個。

（4）獲取緩沖區(qū)大小

KFIFO提供了幾個接口函數(shù)來查詢環(huán)形緩沖區(qū)的狀態(tài)。

#define kfifo_size(fifo)
#define kfifo_len(fifo)
#define kfifo_is_empty(fifo)
#define kfifo_is_full(fifo)

kfifo_size()用來獲取環(huán)形緩沖區(qū)的大小，也就是最大可以容納多少個數(shù)據(jù)元素。kfifo_len()用來獲取當(dāng)前環(huán)形緩沖區(qū)中有多少個有效數(shù)據(jù)元素。kfifo_is_empty()判斷環(huán)形緩沖區(qū)是否為空。kfifo_is_full()判斷環(huán)形緩沖區(qū)是否為滿。

（5）與用戶空間數(shù)據(jù)交互

KFIFO還封裝了兩個函數(shù)與用戶空間數(shù)據(jù)交互。

#define kfifo_from_user(fifo, from, len, copied)
#define kfifo_to_user(fifo, to, len, copied)

kfifo_from_user()是把from指向的用戶空間的len個數(shù)據(jù)元素復(fù)制到KFIFO中，最后一個參數(shù)copied表示成功復(fù)制了幾個數(shù)據(jù)元素。

kfifo_to_user()則相反，把KFIFO的數(shù)據(jù)元素復(fù)制到用戶空間。這兩個宏結(jié)合了copy_to_user()、copy_from_user()以及KFIFO的機制，給驅(qū)動開發(fā)者提供了方便。

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。舉報投訴

存儲

存儲

+關(guān)注

關(guān)注
13

文章
4353

瀏覽量
86169
內(nèi)存

內(nèi)存

+關(guān)注

關(guān)注
8

文章
3055

瀏覽量
74327
數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)

+關(guān)注

關(guān)注
3

文章
573

瀏覽量
40230
LINUX內(nèi)核

LINUX內(nèi)核

+關(guān)注

關(guān)注
1

文章
316

瀏覽量
21742

Linux內(nèi)核結(jié)構(gòu)詳解

，打印警告或錯誤信息的過程，還有系統(tǒng)的調(diào)試?yán)痰鹊取Ｏ到y(tǒng)數(shù)據(jù)結(jié)構(gòu)在linux的內(nèi)核的實現(xiàn)中，有一些數(shù)據(jù)結(jié)構(gòu)使用頻度較高，他們是：task_struct.

發(fā)表于 07-11 16:59

Linux內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)的一點認(rèn)識

大家都知道linux內(nèi)核是世界上優(yōu)秀的軟件之一，作為一款優(yōu)秀的軟件，其中的許多的設(shè)計都精妙之處，十分值得學(xué)習(xí)和借鑒。今天我們就帶大家看一下內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)中一點設(shè)計。打開

發(fā)表于 04-20 16:42

OpenHarmony——內(nèi)核IPC機制數(shù)據(jù)結(jié)構(gòu)解析

制涉及到哪些關(guān)鍵數(shù)據(jù)結(jié)構(gòu)？這些數(shù)據(jù)結(jié)構(gòu)又是如何工作的？接下來我將從隊列、事件、互斥鎖、信號量幾個內(nèi)核對象出發(fā)，為大家講解內(nèi)核IPC機制的數(shù)據(jù)結(jié)構(gòu)

發(fā)表于 09-05 11:02

OpenHarmony——內(nèi)核IPC機制數(shù)據(jù)結(jié)構(gòu)解析

制涉及到哪些關(guān)鍵數(shù)據(jù)結(jié)構(gòu)？這些數(shù)據(jù)結(jié)構(gòu)又是如何工作的？接下來我將從隊列、事件、互斥鎖、信號量幾個內(nèi)核對象出發(fā)，為大家講解內(nèi)核IPC機制的數(shù)據(jù)結(jié)構(gòu)

發(fā)表于 09-08 11:44

Linux的內(nèi)核教程

本章學(xué)習(xí)目標(biāo)掌握LINUX內(nèi)核版本的含義理解并掌握進(jìn)程的概念掌握管道的概念及實現(xiàn)了解內(nèi)核的數(shù)據(jù)結(jié)構(gòu)了解LINUX

發(fā)表于 04-10 16:59 ?0次下載

《深入Linux內(nèi)核架構(gòu)》莫爾勒著

電子發(fā)燒友為您提供了免費下載，《深入Linux內(nèi)核架構(gòu)》一書討論了Linux內(nèi)核的概念、結(jié)構(gòu)和實現(xiàn)。內(nèi)核

發(fā)表于 07-10 11:24 ?0次下載

數(shù)據(jù)結(jié)構(gòu)是什么_數(shù)據(jù)結(jié)構(gòu)有什么用

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高

發(fā)表于 11-17 14:45 ?1.6w次閱讀

什么是數(shù)據(jù)結(jié)構(gòu)?為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)的應(yīng)用實例分析

本文檔的主要內(nèi)容詳細(xì)介紹的是什么是數(shù)據(jù)結(jié)構(gòu)?為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)的應(yīng)用實例分析包括了：數(shù)據(jù)結(jié)構(gòu)在串口通信當(dāng)中的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)在按鍵

發(fā)表于 09-26 15:45 ?14次下載

Linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)：Radix 樹

首先說明一下什么是 radix tree ，Radix tree 是一個壓縮 trie， trie 是一種通過保存關(guān)聯(lián)數(shù)組（associative array）來提供關(guān)鍵字-值（key-value）存儲與查找的數(shù)據(jù)結(jié)構(gòu)。通常關(guān)鍵字是字符串，不過也可以是其他數(shù)據(jù)類型。

發(fā)表于 05-14 17:22 ?2121次閱讀

Linux 內(nèi)核數(shù)據(jù)結(jié)構(gòu)：位圖（Bitmap）

除了各種鏈?zhǔn)胶蜆湫?b class='flag-5'>數(shù)據(jù)結(jié)構(gòu)，Linux內(nèi)核還提供了位圖接口。位圖在Linux內(nèi)核中大量使用。下面的源代碼文件包含這些

發(fā)表于 05-14 17:24 ?3506次閱讀

你知道Linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)中雙向鏈表的作用？

Linux 內(nèi)核提供一套雙向鏈表的實現(xiàn)，你可以在 include/linux/list.h 中找到。我們以雙向鏈表著手開始介紹 Linux 內(nèi)核

發(fā)表于 05-14 17:27 ?1894次閱讀

Linux0.11-進(jìn)程控制塊數(shù)據(jù)結(jié)構(gòu)

嵌入式Linux中文站收集整理Linux0.11版本內(nèi)核學(xué)習(xí)筆記，本文分析了Linux進(jìn)程控制模塊的數(shù)據(jù)結(jié)構(gòu)。

發(fā)表于 05-15 15:22 ?995次閱讀

Linux內(nèi)核的鏈表數(shù)據(jù)結(jié)構(gòu)

Linux內(nèi)核實現(xiàn)了自己的鏈表數(shù)據(jù)結(jié)構(gòu)，它的設(shè)計與傳統(tǒng)的方式不同，非常巧妙也很通用。

發(fā)表于 03-24 11:34 ?881次閱讀

Linux內(nèi)核代碼中常用的數(shù)據(jù)結(jié)構(gòu)有哪些？

Linux內(nèi)核代碼中廣泛使用了數(shù)據(jù)結(jié)構(gòu)和算法，其中最常用的兩個是鏈表和紅黑樹。

發(fā)表于 07-20 09:39 ?541次閱讀

epoll的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

一、epoll的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) 在開始研究源代碼之前，我們先看一下 epoll 中使用的數(shù)據(jù)結(jié)構(gòu)，分別是 eventpoll、epitem 和 eppoll_entry。 1、eventpoll 我們

發(fā)表于 11-10 10:20 ?845次閱讀