亚洲精品一二区_国产黄色片网站_99久久久成人国产精品_蜜臀网_国产精品一区二区三区免费_成人av中文字幕_91精品国产欧美一区二区成人

    1、ARM Linux內(nèi)核鏈表概述

    在ARM Linux中，鏈表是為基本的數(shù)據(jù)結構，也是為常用的數(shù)據(jù)結構。在本文中盡管使用2.6內(nèi)核作為講解的基礎，但實際上2.4內(nèi)核中的鏈表結構和2.6并沒有太大區(qū)別。二者不同之處在于2.6擴充了兩種鏈表數(shù)據(jù)結構：鏈表的讀拷貝更新（rcu）和HASH鏈表（hlist）。這兩種擴展都是基于基本的list結構。因此，在此處主要介紹基本鏈表結構。

    鏈表數(shù)據(jù)結構的定義很簡單（<include/linux/list.h>，以下所有代碼除非加以說明，其余均取自該文件）：

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

    list_head結構包含兩個指向list_head結構的指針prev和next，由此可見，內(nèi)核的鏈表具備雙鏈表功能，實際上，通常它都組織成雙循環(huán)鏈表。

    和之前介紹的雙鏈表結構模型不同，這里的list_head沒有數(shù)據(jù)域。在Linux內(nèi)核鏈表中，不是在鏈表結構中包含數(shù)據(jù)，而是在數(shù)據(jù)結構中包含鏈表節(jié)點。由于鏈表數(shù)據(jù)類型差別很大，如果對每一種數(shù)據(jù)項類型都需要定義各自的鏈表結構，不利于抽象成為公共的模板。

    在Linux內(nèi)核鏈表中，需要用鏈表組織起來的數(shù)據(jù)通常會包含一個struct list_head成員，例如在<include/linux/netfilter.h>中定義了一個nf_sockopt_ops結構來描述netfilter為某一協(xié)議族準備的getsockopt/setsockopt接口，其中就有一個（struct list_head list）成員，各個協(xié)議族的nf_sockopt_ops結構都通過這個list成員組織在一個鏈表中，表頭是定義在<net/core/netfilter.c>中的nf_sockopts（struct list_head）。讀者可以看到，Linux的簡捷實用、不求完美和標準的風格在這里體現(xiàn)得相當充分。

    2、Linux內(nèi)核鏈表接口

    （1）聲明和初始化

    實際上Linux只定義了鏈表節(jié)點，并沒有專門定義鏈表頭，那么一個鏈表結構是如何建立起來的呢？這里是使用LIST_HEAD()這個宏來構建的。

    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

    這樣，當需要用LIST_HEAD(nf_sockopts)聲明一個名為nf_sockopts的鏈表頭時，它的next、prev指針都初始化為指向自己。這樣就構建了一個空鏈表，因為Linux用頭指針的next是否指向自己來判斷鏈表是否為空。

    static inline int list_empty(const struct list_head *head)
    { return head->next == head; }

    除了用LIST_HEAD()宏在聲明的時候創(chuàng)建一個鏈表以外，Linux還提供了一個INIT_LIST_HEAD宏用于運行時創(chuàng)建鏈表：

    #define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr);
    (ptr)->prev = (ptr); } while (0)

    （2）插入

    對鏈表的插入操作有兩種：在表頭插入和在表尾插入。Linux為此提供了兩個接口：

    static inline void list_add(struct list_head *new, struct list_head *head);
    static inline void list_add_tail(struct list_head *new, struct list_head *head);

    因為Linux鏈表是循環(huán)表，且表頭的next、prev分別指向鏈表中的第一個和末一個節(jié)點，所以，list_add()和list_add_tail()的區(qū)別并不大，實際上，Linux分別用以下兩個函數(shù)來實現(xiàn)接口。

    static inline void __list_add(struct list_head *new,
    struct list_head *prev,
    struct list_head *next)
    {
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
    }
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next);
    }
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head);
    }

    （3）刪除

    Linux中刪除的代碼也是類似的，通過__list_del來實現(xiàn)list_del接口，讀者可以自行分析以下代碼段：

    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
        next->prev = prev;
        prev->next = next;
    }
    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
    }

    從接口函數(shù)中可以看到，被刪除下來的prev、next指針分別被設為LIST_POSITION2和LIST_POSITION1兩個特殊值，這樣設置是為了保證不在鏈表中的節(jié)點項不可訪問，對LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障。與之相對應，list_del_init()函數(shù)將節(jié)點從鏈表中解下來之后，調(diào)用LIST_INIT_HEAD()將節(jié)點置為空鏈狀態(tài)。

   熱點鏈接：

   1、嵌入式linux內(nèi)核數(shù)據(jù)結構之循環(huán)鏈表
   2、嵌入式linux內(nèi)核數(shù)據(jù)結構之雙向鏈表
   3、嵌入式linux內(nèi)核數(shù)據(jù)結構之單向鏈表

更多新聞>>