測(cè)試方法準(zhǔn)備
由于需要在內(nèi)核中進(jìn)行代碼測(cè)試驗(yàn)證,完整編譯安裝內(nèi)核比較耗時(shí)耗力。準(zhǔn)備采用module形式來驗(yàn)證。
Makefile
obj-m:=linked-list.o
KERNELBUILD:=/lib/modules/$(shell uname -r)/build
default:
make -C ${KERNELBUILD} M=$(shell pwd) modules
clean:
rm -rf *.o *.cmd *.ko *.mod.c .tmp_versions
linked-list.c
#include
#include
#include
int linked_list_init(void)
{
printk("%s\n", __func__);
return 0;
}
void linked_list_exit(void)
{
printk("%s\n", __func__);
}
module_init(linked_list_init);
module_exit(linked_list_exit);
MODULE_AUTHOR("Arnold Lu");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Linked list test");
安裝module
sudo insmod linked-list.ko
查找安裝情況
lsmod | grep linked-list
執(zhí)行l(wèi)og
<4>[621267.946711] linked_list_init
<4>[621397.154534] linked_list_exit
刪除module
sudo rmmod linked-list
鏈表、雙向鏈表、無鎖鏈表
Linked list, doubly linked list, lock-free linked list.
鏈表是一種常用的組織有序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),它通過指針將一系列數(shù)據(jù)節(jié)點(diǎn)連接成一條數(shù)據(jù)鏈,是線性表的一種重要實(shí)現(xiàn)方式。相對(duì)于數(shù)組,鏈表具有更好的動(dòng)態(tài)性,建立鏈表時(shí)無需預(yù)先知道數(shù)據(jù)總量,可以隨機(jī)分配空間,可以高效地在鏈表中的任意位置實(shí)時(shí)插入或刪除數(shù)據(jù)。鏈表的開銷主要是訪問的順序性和組織鏈的空間損失。
通常鏈表數(shù)據(jù)結(jié)構(gòu)至少應(yīng)包含兩個(gè)域:數(shù)據(jù)域和指針域,數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù),指針域用于建立與下一個(gè)節(jié)點(diǎn)的聯(lián)系。按照指針域的組織以及各個(gè)節(jié)點(diǎn)之間的聯(lián)系形式,鏈表又可以分為單鏈表、雙鏈表、循環(huán)鏈表等多種類型.
?
?
?
通過設(shè)計(jì)前驅(qū)和后繼兩個(gè)指針域,雙鏈表可以從兩個(gè)方向遍歷,這是它區(qū)別于單鏈表的地方。如果打亂前驅(qū)、后繼的依賴關(guān)系,就可以構(gòu)成"二叉樹";如果再讓首節(jié)點(diǎn)的前驅(qū)指向鏈表尾節(jié)點(diǎn)、尾節(jié)點(diǎn)的后繼指向首節(jié)點(diǎn)(如圖2中虛線部分),就構(gòu)成了循環(huán)鏈表;如果設(shè)計(jì)更多的指針域,就可以構(gòu)成各種復(fù)雜的樹狀數(shù)據(jù)結(jié)構(gòu)。
?
?
?
循環(huán)鏈表的特點(diǎn)是尾節(jié)點(diǎn)的后繼指向首節(jié)點(diǎn)。前面已經(jīng)給出了雙循環(huán)鏈表的示意圖,它的特點(diǎn)是從任意一個(gè)節(jié)點(diǎn)出發(fā),沿兩個(gè)方向的任何一個(gè),都能找到鏈表中的任意一個(gè)數(shù)據(jù)。如果去掉前驅(qū)指針,就是單循環(huán)鏈表。
?
Simple doubly linked list
數(shù)據(jù)結(jié)構(gòu):
struct list_head {
struct list_head *next, *prev;
};
聲明和初始化:
static inline void INIT_LIST_HEAD(struct list_head *list)
在表頭插入和在表尾插入:
static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *entry, struct list_head *head)
刪除,被刪除的節(jié)點(diǎn)prev、next分別被設(shè)為L(zhǎng)IST_POISON2、LIST_POISON1,當(dāng)訪問此節(jié)點(diǎn)時(shí)會(huì)引起葉故障。保證不在鏈表中的節(jié)點(diǎn)項(xiàng)不可訪問。
static inline void list_del(struct list_head *entry)
static inline void list_del_init(struct list_head *entry) 將entry從鏈表解下來,重新初始化,就可以訪問節(jié)點(diǎn)。
將節(jié)點(diǎn)從一個(gè)鏈表搬移到另一個(gè)鏈表,根據(jù)插入表頭和表位分兩種:
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list, struct list_head *head)
用新節(jié)點(diǎn)替換糾結(jié)點(diǎn):
static inline void list_replace(struct list_head *old, struct list_head *new)
將list插入到head:
static inline void list_splice(const struct list_head *list, struct list_head *head)
static inline void list_splice_tail(struct list_head *list, struct list_head *head)
static inline void list_splice_init(struct list_head *list, struct list_head *head) 將list設(shè)為空鏈表
static inline void list_splice_tail_init(struct list_head *list, struct list_head *head) 將list設(shè)為空鏈表
?
?
?
static inline void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)
遍歷宏:
list_entry(ptr, type, member)
list_first_entry(ptr, type, member)
list_last_entry(ptr, type, member)
list_next_entry(pos, member)
list_prev_entry(pos, member)
list_for_each(pos, head)
list_for_each_prev(pos, head) 反向操作
list_for_each_safe(pos, n, head) 安全操作
list_for_each_entry(pos, head, member) 遍歷鏈表是獲取鏈表節(jié)點(diǎn)
list_for_each_entry_safe(pos, n, head, member) 安全操作
list_for_each_entry_reverse(pos, head, member) 反向操作
判斷鏈表是否為空:
static inline int list_empty(const struct list_head *head)
Doubly linked list with a single pointer list head
linux內(nèi)核里邊除了著名的list雙向循環(huán)鏈表以外,還有一個(gè)重要的數(shù)據(jù)結(jié)構(gòu),就是哈希鏈表。哈希鏈表也在很多重要的地方有所使用,比如linux內(nèi)核的dentry,進(jìn)程查詢,文件系統(tǒng)等,可以說,弄明白hlist對(duì)于理解linux內(nèi)核具有重要的意義。
struct hlist_head { ? ?struct hlist_node *first; }; struct hlist_node { ? ?struct hlist_node *next, **pprev; };
linux內(nèi)核的hash鏈表有兩個(gè)數(shù)據(jù)結(jié)構(gòu)組成,一個(gè)是hlist_head是hash表的表頭,一個(gè)是hlist_node是hash標(biāo)的后續(xù)節(jié)點(diǎn)。
在使用的時(shí)候,一般定義一個(gè)struct hlist_head xxx[100]數(shù)組(100只是一個(gè)代表的數(shù)字,視具體情況而定),采取哈希函數(shù)來將鍵值與數(shù)組的對(duì)應(yīng)的地址聯(lián)系起來,如果出現(xiàn)沖突的話,就在hlist_head的后邊繼續(xù)添加。 hlist_head的成員first指針指向后續(xù)的第一個(gè)節(jié)點(diǎn),如果哈希鏈表是空的話,就為NULL。
為什么hlist_head不弄成雙向鏈表呢,因?yàn)闉榱斯?jié)約空間,如果一個(gè)指針的話,一個(gè)哈希數(shù)組的空間消耗就會(huì)減半。
hlist_node的成員next指向后續(xù)的節(jié)點(diǎn)的地址,如果為空就是NULL,另一個(gè)成員pprev是二級(jí)指針,指向前一個(gè)節(jié)點(diǎn)的next成員的地址,如果前一個(gè)成員是hlist_head的話,pprev的值就是前一個(gè)的first指針的地址。
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } 定義并且初始化。 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 在定義之后,需要初始化,不然使用會(huì)導(dǎo)致錯(cuò)誤。 static inline void INIT_HLIST_NODE(struct hlist_node *h) 初始化node節(jié)點(diǎn) static inline int hlist_empty(const struct hlist_head *h) 判斷hash鏈表是否為空 static inline void hlist_del(struct hlist_node *n) 刪除節(jié)點(diǎn),并且將節(jié)點(diǎn)next、pprev指針修改為L(zhǎng)IST_POSITION1和LIST_POSITION2。 static inline void hlist_del_init(struct hlist_node *n) 此種方法更安全,刪除然后再初始化節(jié)點(diǎn)。 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 將節(jié)點(diǎn)插入到hash鏈表的頭結(jié)點(diǎn)后邊。 static inline void hlist_add_before(struct hlist_node *n, struct hlist_node *next) 將一個(gè)節(jié)點(diǎn)插入到next前面。 static inline void hlist_add_behind(struct hlist_node *n, struct hlist_node *prev) 將一個(gè)節(jié)點(diǎn)插入到prev后面。 遍歷訪問節(jié)點(diǎn): hlist_for_each(pos, head) hlist_for_each_safe(pos, n, head) #define hlist_entry(ptr, type, member) container_of(ptr,type,member) hlist_entry_safe(ptr, type, member) hlist_for_each_entry(pos, head, member) hlist_for_each_entry_safe(pos, n, head, member)
Lock-less NULL terminated single linked list
數(shù)據(jù)結(jié)構(gòu)如下:
struct llist_head {
struct llist_node *first;
};
struct llist_node {
struct llist_node *next;
};
?
#define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) static inline void init_llist_head(struct llist_head *list) llist_entry(ptr, type, member) llist_for_each(pos, node) static inline bool llist_empty(const struct llist_head *head) static inline struct llist_node *llist_next(struct llist_node *node) static inline bool llist_add(struct llist_node *new, struct llist_head *head) bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, struct llist_head *head) static inline struct llist_node *llist_del_all(struct llist_head *head) struct llist_node *llist_del_first(struct llist_head *head)
llist_add、llist_add_batch、llist_del_first都是基于cmpxchg原子操作來實(shí)現(xiàn),整個(gè)操作是原子的;llist_del_all是基于xchg來實(shí)現(xiàn)的。
?
cmpxchg(void* ptr, int old, int new),如果ptr和old的值一樣,則把new寫到ptr內(nèi)存,否則返回ptr的值,整個(gè)操作是原子的。在Intel平臺(tái)下,會(huì)用lock cmpxchg來實(shí)現(xiàn),這里的lock個(gè)人理解是鎖住內(nèi)存總線,這樣如果有另一個(gè)線程想訪問ptr的內(nèi)存,就會(huì)被block住。
B+樹
A relatively simple B+Tree implementation. I have written it as a learning exercise to understand how B+Trees work. Turned out to be useful as well. ... A tricks was used that is not commonly found in textbooks. The lowest values are to the right, not to the left. All used slots within a node are on the left, all unused slots contain NUL values. Most operations simply loop once over all slots and terminate on the first NUL.
B樹誕生的背景:
在大規(guī)模數(shù)據(jù)存儲(chǔ)中,實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下,樹節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的,這樣就會(huì)導(dǎo)致二叉樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁,進(jìn)而導(dǎo)致查詢效率低下。 那么如何減少樹的深度,一個(gè)基本的想法是采用多叉樹結(jié)構(gòu)。 因?yàn)榇疟P的操作費(fèi)時(shí)費(fèi)資源,那么如何提高效率,即如何避免頻繁的讀取呢?根據(jù)磁盤查找存取的次數(shù)往往由樹的高度決定,所以只要通過較好的結(jié)構(gòu)降低樹的高度。根據(jù)平衡二叉樹的啟發(fā),自然就想到平衡多叉樹結(jié)構(gòu)。
幾個(gè)算法時(shí)間復(fù)雜度度量:
O(n) 表示某函數(shù)值(未列出)是 n 的常數(shù)倍;亦即他們?cè)鲩L(zhǎng)的速度相當(dāng).稱 大O,big O (發(fā)音 "歐" 英文字母 O ) 同理:O(logN):是 logN 的常數(shù)倍;O(nlogn):是 nlogn 的常數(shù)倍
優(yōu)先排序列表
plist有兩個(gè)重要結(jié)構(gòu)體struct plist_head和struct plist_node,分別用來表示plist表頭和plist節(jié)點(diǎn)。
struct plist_head {
struct list_head node_list;
};
struct plist_node {
int prio;
struct list_head prio_list;
struct list_head node_list;
};
相關(guān)函數(shù):
PLIST_HEAD(head) 初始化plist表頭
PLIST_NODE_INIT(node, __prio) 初始化plist節(jié)點(diǎn)
static inline void plist_head_init(struct plist_head *head) 初始化plist表頭
static inline void plist_node_init(struct plist_node *node, int prio) 初始化plist節(jié)點(diǎn)
添加節(jié)點(diǎn)、刪除節(jié)點(diǎn):
extern void plist_add(struct plist_node *node, struct plist_head *head); 通過plist_add添加到head的node是按照prio優(yōu)先級(jí)由高到低順序在node_list上排列。
extern void plist_del(struct plist_node *node, struct plist_head *head);
extern void plist_requeue(struct plist_node *node, struct plist_head *head); 是plist_del的優(yōu)化版本
遍歷plist:
plist_for_each(pos, head)
判斷head是否為空:
static inline int plist_head_empty(const struct plist_head *head)
判斷當(dāng)前node是否在node_list上:
static inline int plist_node_empty(const struct plist_node *node)
獲取前一、后一節(jié)點(diǎn):
plist_next(pos)
plist_prev(pos)
獲取首節(jié)點(diǎn)、尾節(jié)點(diǎn):
static inline struct plist_node *plist_first(const struct plist_head *head)
static inline struct plist_node *plist_last(const struct plist_head *head)
下面是對(duì)plist進(jìn)行的一些驗(yàn)證:
static dump_list(void)
{
struct plist_node *node_pos, *first_node, *last_node;
int i;
printk(KERN_DEBUG "%s start\n", __func__);
printk("node_list: ");
list_for_each_entry(node_pos, &test_head.node_list, node_list) {
printk("%d ", node_pos->prio);
}
printk("\n");
first_node = plist_first(&test_head);
last_node = plist_last(&test_head);
printk("prio_list: %d ", first_node->prio);
list_for_each_entry(node_pos, &first_node->prio_list, prio_list) {
printk("%d ", node_pos->prio);
}
printk("\n");
#if 0
for (i = 0; i < ARRAY_SIZE(test_node); i++) {
if(!plist_node_empty(test_node+i))
printk(KERN_DEBUG "(test_node+%d)->prio=%d\n", i, (test_node+i)->prio);
}
#endif
printk(KERN_DEBUG "MIN(prio)=%d MAX(prio)=%d\n", first_node->prio, last_node->prio);
printk(KERN_DEBUG "%s end\n", __func__);
}
static int __init plist_test(void)
{
int nr_expect = 0, i, loop;
unsigned int r = local_clock();
printk(KERN_DEBUG "start plist test\n");
plist_head_init(&test_head);
for (i = 0; i < ARRAY_SIZE(test_node); i++)
plist_node_init(test_node + i, 0);
for (loop = 0; loop < 10; loop++) {
r = r * 193939 % 47629;
i = r % ARRAY_SIZE(test_node);
if (plist_node_empty(test_node + i)) {
r = r * 193939 % 47629;
test_node[i].prio = r % 10;
plist_add(test_node + i, &test_head);
nr_expect++;
} else {
plist_del(test_node + i, &test_head);
nr_expect--;
}
plist_test_check(nr_expect);
if (!plist_node_empty(test_node + i)) {
plist_test_requeue(test_node + i);
plist_test_check(nr_expect);
}
}
dump_list();
for (i = 0; i < ARRAY_SIZE(test_node); i++) {
if (plist_node_empty(test_node + i))
continue;
plist_del(test_node + i, &test_head);
nr_expect--;
plist_test_check(nr_expect);
}
printk(KERN_DEBUG "end plist test\n");
return 0;
}
通過初始化不超過10個(gè)node節(jié)點(diǎn),優(yōu)先級(jí)為0-9。然后查看node_list和prio_list兩鏈表的節(jié)點(diǎn)情況:
[22050.404475] start plist test [22050.404481] dump_list start [22050.404482] node_list: 0 0 1 1 2 6 8 8 9 9 [22050.404486] prio_list: 0 1 2 6 8 9 [22050.404488] MIN(prio)=0 MAX(prio)=9 [22050.404489] dump_list end [22050.404491] end plist test [22050.947810] start plist test [22050.947816] dump_list start [22050.947817] node_list: 0 1 1 2 2 3 3 3 8 8 [22050.947820] prio_list: 0 1 2 3 8 [22050.947822] MIN(prio)=0 MAX(prio)=8 [22050.947823] dump_list end [22050.947825] end plist test [22051.491245] start plist test [22051.491254] dump_list start [22051.491256] node_list: 0 1 2 3 3 3 6 9 9 9 [22051.491262] prio_list: 0 1 2 3 6 9 [22051.491266] MIN(prio)=0 MAX(prio)=9 [22051.491267] dump_list end [22051.491271] end plist test
可以看出node_list上的節(jié)點(diǎn)按照優(yōu)先級(jí)由高到低排序,優(yōu)先級(jí)可能會(huì)重復(fù);在prio_list上是不同優(yōu)先級(jí)的節(jié)點(diǎn)。如下所示:
* pl:prio_list (only for plist_node) * nl:node_list *HEAD| NODE(S) * | * ||------------------------------------| * ||->|pl|<->|pl|<--------------->|pl|<-| * | |10| |21| |21| |21| |40| (prio) * | | | | | | | | | | | * | | | | | | | | | | | * | ->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-| * |-------------------------------------------------|
紅黑樹
Red-Black treesareusedfor scheduling, virtual memory management, to track file descriptors and directory entries,etc.
審核編輯:湯梓紅
評(píng)論
查看更多