linux内核数据结构

《linux内核数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter6KernelDataStructuresWhat’sdiscussed•Linkedlists•Queues•Maps•BinarytreesAsinglylinkedlistAdoublylinkedlistCircularLinkedListsTheLinuxKernel’sImplementation•AllmethodsaredefinedinTheLinkedListStructureNode•thelist_add()methodaddsanewnodetoanexistinglinkedlist•Thesem

2、ethods,however,aregeneric:Theyacceptonlylist_headstructures•Usingthemacrocontainer_of(),wecaneasilyfindtheparentstructurecontaininganygivenmembervariableDefiningaLinkedList•initializingthelinkedlistatruntime•oratcompiletimeListHeads•youwillgenerallywantaspecialpointerthatreferstoyourli

3、nkedlist,withoutbeingalistnodeitself•thisspecialnodeisinfactanormallist_head:ManipulatingLinkedLists•AddingaNodetoaLinkedList•DeletingaNodefromaLinkedListManipulatingLinkedLists•MovingandSplicingLinkedListNodesTraversingLinkedLists•TheBasicApproach•TheUsableApproach•Realexample:Queues•

4、FIFOs(Firstin,FirstOut)•genericqueueimplementationiscalledkfifo•implementedinkernel/kfifo.canddeclaredin.kfifo•Linux’skfifoworkslikemostotherqueueabstractions•providingtwoprimaryoperations:–enqueue(namedin)–dequeue(namedout)CreatingaQueueEnqueuing&DequeuingDataObtainingt

5、heSizeofaQueue•totalsizeinbytes•currentsizeusedinbytes•availablesizeinbytesResettingandDestroyingtheQueueQueueUsageExampleMaps•knownasanassociativearray•acollectionofuniquekeys•eachkeyisassociatedwithaspecificvalue•designedforonespecificusecase:mappingauniqueidentificationnumber(UID)to

6、apointer•thismapinlinuxiscalledidr.•Theidrdatastructureisusedformappinguser-spaceUIDstotheirassociatedkerneldatastructureMapoperations•Add(key,value)•Remove(key)•value=Lookup(key)AllocatingaNewUID•FirstyoutelltheidrthatyouwanttoallocateanewUID,allowingittoresizethebackingtreeasnecessar

7、y•youactuallyrequestthenewUIDLookingUpaUID•function:•Usage:RemovingaUIDDestroyinganidr•deallocatesonlyunusedmemoryassociatedwiththeidrpointedatbyidp.•ItdoesnotfreeanymemorycurrentlyinusebyallocatedUIDs.•toforcetheremovalofallUIDsInitializinganidrBinaryTrees•isatreeinwhichnodeshaveatm