Linux操作系统课程指导：Ch6KernelDataStructures

KernelDataStructuresKernelDataStructures

Codereuse

Donotrollyourown

Linkedlists(链表操作)

Queues(队列操作)

Maps(映射操作)

BinaryTrees(树的操作)2022/4/21LiangShi：LinuxOperatingSystems2Outline

LinkedLists

Queues

Maps

BinaryTrees

Conclusions2022/4/21LiangShi：LinuxOperatingSystems3LinkedLists(链表)

SingleandDoublyLinkedLists,CircularList2022/4/21LiangShi：LinuxOperatingSystems4LinkedLists(链表)

TheLinuxImplementation

Linuxistoembedalinkedlistnodeinthestructure!!!!1声明一个与member同一个类型的指针常量*__mptr,并初始化为ptr.2__mptr的地址减去member在该struct中的偏移量得到的地址,再转换成type型指针.该指针就是member的入口地址2022/4/21LiangShi：LinuxOperatingSystems5LinkedLists(链表)

TheLinuxImplementation

DefineaLinkedList(LIST_HEAD_INIT(list))

ListHeads:staticLIST_HEAD(fox_list)

ManipulatingLinkedLists

Addinganode:list_add(…),list_add_tail(…).

Deletinganode:list_del(…),list_del_init().

MovingandSplicing:list_move(…),list_move_tail(…).List_empty(…),list_splice(…),list_splice_init(…);

Traversing:2022/4/21LiangShi：LinuxOperatingSystems6LinkedLists(链表)

Traversing

Basicapproach:list_for_each(p,fox_list)2022/4/21LiangShi：LinuxOperatingSystems7LinkedLists(链表)

Traversing

Usableapproach:list_for_each_entry(pos,head,member)2022/4/21LiangShi：LinuxOperatingSystems8LinkedLists(链表)

Traversing

Usableapproach:遍历list_for_each_entry_reverse(pos,head,member)反向遍历list_for_each_entry_safe(pos,next,head,member)<linux/list.h>2022/4/21LiangShi：LinuxOperatingSystems9Queues(队列)

First-InFirst-Out:FIFO,kfifo<linux/kfifo.c*h>2022/4/21LiangShi：LinuxOperatingSystems10Queues(队列)

Kfifo:

CreatingaQueue:intkfifo_alloc(structkfifo*fifo,unsignedintsize,gfp_tgfp_mask);voidkfifo_init(structkfifo*fifo,void*buffer,unsignedintsize);

EnqueuingData:unsignedintkfifo_in(structkfifo*fifo,constvoid*from,unsignedintlen);

DequeuingData:unsignedintkfifo_out(structkfifo*fifo,void*to,unsignedintlen);unsignedintkfifo_out_peek(structkfifo*fifo,void*to,unsignedintlen,unsignedoffset);

kfifo_size(),kfifo_len(),kfifo_avail(),kfifo_reset(),kfifo_free(),kfifo_is_empty(),kfifo_is_full().2022/4/21LiangShi：LinuxOperatingSystems11Maps(映射)

Key<->value

Add(key,value)

Remove(key)

Value=Lookup(key)

Nothash,itisbinarytree

init_idr()

idr_pre_get()

idr_get_new(),idr_get_new_above()

idr_find()

idr_remove()

idr_destroy(),idr_remove_all()2022/4/21LiangShi：LinuxOperatingSystems12BinaryTrees(二叉树)

binarytreeBinarySearchTrees2022/4/21LiangShi：LinuxOperatingSystems13BinaryTrees(二叉树)

Self-BalanceBinaryTrees2022/4/21LiangShi：LinuxOperatingSystems14BinaryTrees(二叉树)

Red_blackTrees1.Allnodesareeitherredorblack2.Leafnodesareblack3.Leafnodesdonotcontaindata4.Allnon-leafnodeshavetwochildren5.Ifanodeisred,bothofitschildrenareblack6.Thepathfromanodetooneofitsleavescontainsthesamenumberofblacknodesastheshortestpathtoanyofitsotherleaves.

Rbtree:

structrb_rootroot=RB_ROOT;

rb_node2022/4/21LiangShi：LinuxOperatingSystems15WhatDataStructuretoUse,When

Ifyourprimaryaccessmethodisiteratingoverallyourdata,usealinkedlist.

Iducer/consumerpattern,useaqueue,particularlyifyouwant(orcancopewith)afixed-sizebuffer.

IfyouneedtomapaUIDtoanobject,useamap.

Ifyouneedtostorealargeamountofdataandlookitupefficiently,considerared-blacktree.2022/4/21LiangShi：LinuxOperatingSystems16AlgorithmicComplexity

Big-ONotation–upperbound

O(1),O(n),O(n2),O(logn),O(nlogn)

BigThetaNotation–leastupperbound

Tplexity2022/4/21LiangShi：LinuxOperatingSystems17Conclusion

LinkedLists

Queues

Maps

BinaryTrees

AlgorithmComplexity2022/4/21LiangShi：LinuxOperatingSystems18其他几件事情

关于4月9日课程的调课（校运动会）

关于课后作业的提交：请大家在每周布置作业开始的下一周上课前将作业发送给助教邮箱1449848370@

必做作业会算入期末考核，选做不算入但会酌情加分（总分不超过100）

本周开始，请大家务必出勤，学校严查。2022/4/21LiangShi：LinuxOperatingSystems19作业

自选一个数据结构，编写程序实现其所有基本功能（必做）

阅读内核源码，找出相应数据结构实现的实例，并进行分析（选做）2022/4/21LiangShi：LinuxOperatingSystems20第一次源码阅读报告发布

请根据