搜索

[24990] 2016-05-15_Linux内核里的数据结构——双向链表

文档创建者：s7ckTeam
浏览次数：0
最后更新：2025-01-18
2016-05-15_Linux内核里的数据结构——双向链表 L i n u x   内 核 里 的 数 据 结 构 — — 双 向 链 表 译 者 ： o s k a 8 7 4   L i n u x 中 国   2 0 1 6 - 0 5 - 1 5 L i n u x   内 核 中 自 己 实 现 了 双 向 链 表 ， 可 以 在   i n c l u d e / l i n u x / l i s t . h [ 1 ]   找 到 定 义 。 我 们 将 会 首 先 从 双 向 链 表 数 据 结 构 开 始 介 绍 内 核 里 的 数 据 结 构 内 核 里 的 数 据 结 构 。 为 什 么 ？ 因 为 它 在 内 核 里 使 用 的 很 广 泛 ， 你 只 需 要 在   f r e e - e l e c t r o n s . c o m [ 2 ]   检 索 一 下 就 知 道 了 。 首 先 让 我 们 看 一 下 在   i n c l u d e / l i n u x / t y p e s . h [ 3 ]   里 的 主 结 构 体 ： 你 可 能 注 意 到 这 和 你 以 前 见 过 的 双 向 链 表 的 实 现 方 法 是 不 同 的 。 举 个 例 子 来 说 ， 在   g l i b [ 4 ]   库 里 是 这 样 实 现 的 ： 通 常 来 说 一 个 链 表 结 构 会 包 含 一 个 指 向 某 个 项 目 的 指 针 。 但 是   L i n u x   内 核 中 的 链 表 实 现 并 没 有 这 样 做 。 所 以 问 题 来 了 ： 链 表 在 哪 里 保 存 数 链 表 在 哪 里 保 存 数 据 呢 ？ 据 呢 ？ 。 实 际 上 ， 内 核 里 实 现 的 链 表 是 侵 入 式 链 表 （ 侵 入 式 链 表 （ I n t r u s i v e   l i s t ） ） 。 侵 入 式 链 表 并 不 在 节 点 内 保 存 数 据 - 它 的 节 点 仅 仅 包 含 指 向 前 后 节 点 1 .   s t r u c t   l i s t _ h e a d   { 2 .           s t r u c t   l i s t _ h e a d   * n e x t ,   * p r e v ; 3 .   } ; 1 .   s t r u c t   G L i s t   { 2 .       g p o i n t e r   d a t a ; 3 .       G L i s t   * n e x t ; 4 .       G L i s t   * p r e v ; 5 .   } ;
的 指 针 ， 以 及 指 向 链 表 节 点 数 据 部 分 的 指 针 — — 数 据 就 是 这 样 附 加 在 链 表 上 的 。 这 就 使 得 这 个 数 据 结 构 是 通 用 的 ， 使 用 起 来 就 不 需 要 考 虑 节 点 数 据 的 类 型 了 。 比 如 ： 让 我 们 看 几 个 例 子 来 理 解 一 下 在 内 核 里 是 如 何 使 用     的 。 如 上 所 述 ， 在 内 核 里 有 很 多 很 多 不 同 的 地 方 都 用 到 了 链 表 。 我 们 来 看 一 个 在 杂 项 字 符 驱 动 里 面 的 使 用 的 例 子 。 在   d r i v e r s / c h a r / m i s c . c [ 5 ]   的 杂 项 字 符 驱 动   A P I   被 用 来 编 写 处 理 小 型 硬 件 或 虚 拟 设 备 的 小 驱 动 。 这 些 驱 动 共 享 相 同 的 主 设 备 号 ： 但 是 都 有 各 自 不 同 的 次 设 备 号 。 比 如 ： 1 .   s t r u c t   n m i _ d e s c   { 2 .           s p i n l o c k _ t   l o c k ; 3 .           s t r u c t   l i s t _ h e a d   h e a d ; 4 .   } ; l i s t _ h e a d 1 .   # d e f i n e   M I S C _ M A J O R                             1 0 1 .   l s   - l   / d e v   |     g r e p   1 0 2 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,   2 3 5   M a r   2 1   1 2 : 0 1   a u t o f s 3 .   d r w x r - x r - x     1 0   r o o t   r o o t                   2 0 0   M a r   2 1   1 2 : 0 1   c p u 4 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,     6 2   M a r   2 1   1 2 : 0 1   c p u _ d m a _ l a t e n c y 5 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,   2 0 3   M a r   2 1   1 2 : 0 1   c u s e 6 .   d r w x r - x r - x       2   r o o t   r o o t                   1 0 0   M a r   2 1   1 2 : 0 1   d r i 7 .   c r w - r w - r w -       1   r o o t   r o o t           1 0 ,   2 2 9   M a r   2 1   1 2 : 0 1   f u s e 8 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,   2 2 8   M a r   2 1   1 2 : 0 1   h p e t 9 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,   1 8 3   M a r   2 1   1 2 : 0 1   h w r n g 1 0 .   c r w - r w - - - - +     1   r o o t   k v m             1 0 ,   2 3 2   M a r   2 1   1 2 : 0 1   k v m 1 1 .   c r w - r w - - - -       1   r o o t   d i s k           1 0 ,   2 3 7   M a r   2 1   1 2 : 0 1   l o o p - c o n t r o l 1 2 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,   2 2 7   M a r   2 1   1 2 : 0 1   m c e l o g 1 3 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,     5 9   M a r   2 1   1 2 : 0 1   m e m o r y _ b a n d w i d t h 1 4 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,     6 1   M a r   2 1   1 2 : 0 1   n e t w o r k _ l a t e n c y 1 5 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,     6 0   M a r   2 1   1 2 : 0 1   n e t w o r k _ t h r o u g h p u t 1 6 .   c r w - r - - - - -       1   r o o t   k m e m           1 0 ,   1 4 4   M a r   2 1   1 2 : 0 1   n v r a m
现 在 让 我 们 看 看 它 是 如 何 使 用 链 表 的 。 首 先 看 一 下 结 构 体   ： 可 以 看 到 结 构 体 的 第 四 个 变 量   是 所 有 注 册 过 的 设 备 的 链 表 。 在 源 代 码 文 件 的 开 始 可 以 看 到 这 个 链 表 的 定 义 ： 它 实 际 上 是 对 用   类 型 定 义 的 变 量 的 扩 展 。 1 6 .   c r w - r - - - - -       1   r o o t   k m e m           1 0 ,   1 4 4   M a r   2 1   1 2 : 0 1   n v r a m 1 7 .   b r w - r w - - - -       1   r o o t   d i s k             1 ,     1 0   M a r   2 1   1 2 : 0 1   r a m 1 0 1 8 .   c r w - - w - - - -       1   r o o t   t t y               4 ,     1 0   M a r   2 1   1 2 : 0 1   t t y 1 0 1 9 .   c r w - r w - - - -       1   r o o t   d i a l o u t       4 ,     7 4   M a r   2 1   1 2 : 0 1   t t y S 1 0 2 0 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,     6 3   M a r   2 1   1 2 : 0 1   v g a _ a r b i t e r 2 1 .   c r w - - - - - - -       1   r o o t   r o o t           1 0 ,   1 3 7   M a r   2 1   1 2 : 0 1   v h c i m i s c d e v i c e 1 .   s t r u c t   m i s c d e v i c e 2 .   { 3 .               i n t   m i n o r ; 4 .               c o n s t   c h a r   * n a m e ; 5 .               c o n s t   s t r u c t   f i l e _ o p e r a t i o n s   * f o p s ; 6 .               s t r u c t   l i s t _ h e a d   l i s t ; 7 .               s t r u c t   d e v i c e   * p a r e n t ; 8 .               s t r u c t   d e v i c e   * t h i s _ d e v i c e ; 9 .               c o n s t   c h a r   * n o d e n a m e ; 1 0 .               m o d e _ t   m o d e ; 1 1 .   } ; m i s c d e v i c e l i s t 1 .   s t a t i c   L I S T _ H E A D ( m i s c _ l i s t ) ; l i s t _ h e a d
然 后 使 用 宏     进 行 初 始 化 ， 这 会 使 用 变 量   的 地 址 来 填 充 和   结 构 体 的 两 个 变 量 。 现 在 来 看 看 注 册 杂 项 设 备 的 函 数 。 它 在 一 开 始 就 用 函 数     初 始 化 了 。 作 用 和 宏 一 样 。 1 .   # d e f i n e   L I S T _ H E A D ( n a m e )   2 .           s t r u c t   l i s t _ h e a d   n a m e   =   L I S T _ H E A D _ I N I T ( n a m e ) L I S T _ H E A D _ I N I T n a m e p r e v n e x t 1 .   # d e f i n e   L I S T _ H E A D _ I N I T ( n a m e )   {   & ( n a m e ) ,   & ( n a m e )   } m i s c _ r e g i s t e r I N I T _ L I S T _ H E A D m i s c d e v i c e - > l i s t 1 .   I N I T _ L I S T _ H E A D ( & m i s c - > l i s t ) ; L I S T _ H E A D _ I N I T 1 .   s t a t i c   i n l i n e   v o i d   I N I T _ L I S T _ H E A D ( s t r u c t   l i s t _ h e a d   * l i s t ) 2 .   { 3 .           l i s t - > n e x t   =   l i s t ; 4 .           l i s t - > p r e v   =   l i s t ;
接 下 来 ， 在 函 数   创 建 了 设 备 后 ， 我 们 就 用 下 面 的 语 句 将 设 备 添 加 到 设 备 链 表 ： 内 核 文 件   提 供 了 向 链 表 添 加 新 项 的   A P I   接 口 。 我 们 来 看 看 它 的 实 现 ： 实 际 上 就 是 使 用 3 个 指 定 的 参 数 来 调 用 了 内 部 函 数 ： n e w   -   新 项 。 h e a d   -   新 项 将 会 插 在 的 后 面 h e a d - > n e x t   -   插 入 前 ，   后 面 的 项 。 的 实 现 非 常 简 单 ： 4 .           l i s t - > p r e v   =   l i s t ; 5 .   } d e v i c e _ c r e a t e 1 .   l i s t _ a d d ( & m i s c - > l i s t ,   & m i s c _ l i s t ) ; l i s t . h 1 .   s t a t i c   i n l i n e   v o i d   l i s t _ a d d ( s t r u c t   l i s t _ h e a d   * n e w ,   s t r u c t   l i s t _ h e a d   * h e a d ) 2 .   { 3 .           _ _ l i s t _ a d d ( n e w ,   h e a d ,   h e a d - > n e x t ) ; 4 .   } _ _ l i s t _ a d d h e a d h e a d _ _ l i s t _ a d d 1 .   s t a t i c   i n l i n e   v o i d   _ _ l i s t _ a d d ( s t r u c t   l i s t _ h e a d   * n e w , 2 .                                       s t r u c t   l i s t _ h e a d   * p r e v , 3 .                                       s t r u c t   l i s t _ h e a d   * n e x t ) 4 .   { 5 .           n e x t - > p r e v   =   n e w ;
这 里 ， 我 们 在 和   之 间 添 加 了 一 个 新 项 。 所 以 我 们 开 始 时 用 宏 定 义 的   链 表 会 包 含 指 向   的 向 前 指 针 和 向 后 指 针 。 这 儿 还 有 一 个 问 题 ： 如 何 得 到 列 表 的 内 容 呢 ？ 这 里 有 一 个 特 殊 的 宏 ： 使 用 了 三 个 参 数 ： p t r   -   指 向 结 构     的 指 针 ； t y p e   -   结 构 体 类 型 ; m e m b e r   -   在 结 构 体 内 类 型 为   的 变 量 的 名 字 ； 比 如 说 ： 然 后 我 们 就 可 以 使 用 5 .           n e x t - > p r e v   =   n e w ; 6 .           n e w - > n e x t   =   n e x t ; 7 .           n e w - > p r e v   =   p r e v ; 8 .           p r e v - > n e x t   =   n e w ; 9 .   } p r e v n e x t L I S T _ H E A D _ I N I T m i s c m i s c d e v i c e - > l i s t 1 .   # d e f i n e   l i s t _ e n t r y ( p t r ,   t y p e ,   m e m b e r )   2 .           c o n t a i n e r _ o f ( p t r ,   t y p e ,   m e m b e r ) l i s t _ h e a d l i s t _ h e a d 1 .   c o n s t   s t r u c t   m i s c d e v i c e   * p   =   l i s t _ e n t r y ( v ,   s t r u c t   m i s c d e v i c e ,   l i s t ) p - > m i n o r
  或 者   来 访 问 。 让 我 们 来 看 看   的 实 现 ： 如 我 们 所 见 ， 它 仅 仅 使 用 相 同 的 参 数 调 用 了 宏 。 初 看 这 个 宏 挺 奇 怪 的 ： 首 先 你 可 以 注 意 到 花 括 号 内 包 含 两 个 表 达 式 。 编 译 器 会 执 行 花 括 号 内 的 全 部 语 句 ， 然 后 返 回 最 后 的 表 达 式 的 值 。 举 个 例 子 来 说 ： 2 .   最 终 会 打 印 出 。 p - > n a m e m i s c d e v i c e l i s t _ e n t r y 1 .   # d e f i n e   l i s t _ e n t r y ( p t r ,   t y p e ,   m e m b e r )   2 .           c o n t a i n e r _ o f ( p t r ,   t y p e ,   m e m b e r ) c o n t a i n e r _ o f 1 .   # d e f i n e   c o n t a i n e r _ o f ( p t r ,   t y p e ,   m e m b e r )   ( {                                             2 .           c o n s t   t y p e o f (   ( ( t y p e   * ) 0 ) - > m e m b e r   )   * _ _ m p t r   =   ( p t r ) ;         3 .           ( t y p e   * ) (   ( c h a r   * ) _ _ m p t r   -   o f f s e t o f ( t y p e , m e m b e r )   ) ; } ) 1 .   # i n c l u d e   < s t d i o . h > 3 .   i n t   m a i n ( )   { 4 .           i n t   i   =   0 ; 5 .           p r i n t f ( " i   =   % d n " ,   ( { + + i ;   + + i ; } ) ) ; 6 .           r e t u r n   0 ; 7 .   } 2
下 一 点 就 是 , 它 也 很 简 单 。 就 如 你 从 名 字 所 理 解 的 ， 它 仅 仅 返 回 了 给 定 变 量 的 类 型 。 当 我 第 一 次 看 到 宏 的 实 现 时 ， 让 我 觉 得 最 奇 怪 的 就 是 表 达 式 中 的 0 。 实 际 上 这 个 指 针 巧 妙 的 计 算 了 从 结 构 体 特 定 变 量 的 偏 移 ， 这 里 的 刚 好 就 是 位 宽 里 的 零 偏 移 。 让 我 们 看 一 个 简 单 的 例 子 ： 2 .   8 .   结 果 显 示 。 下 一 个 宏 会 计 算 从 结 构 体 起 始 地 址 到 某 个 给 定 结 构 字 段 的 偏 移 。 它 的 实 现 和 上 面 类 似 ： 现 在 我 们 来 总 结 一 下 宏 t y p e o f c o n t a i n e r _ o f ( ( t y p e   * ) 0 ) 0 1 .   # i n c l u d e   < s t d i o . h > 3 .   s t r u c t   s   { 4 .                   i n t   f i e l d 1 ; 5 .                   c h a r   f i e l d 2 ; 6 .             c h a r   f i e l d 3 ; 7 .   } ; 9 .   i n t   m a i n ( )   { 1 0 .           p r i n t f ( " % p n " ,   & ( ( s t r u c t   s * ) 0 ) - > f i e l d 3 ) ; 1 1 .           r e t u r n   0 ; 1 2 .   } 0 x 5 o f f s e t o f 1 .   # d e f i n e   o f f s e t o f ( T Y P E ,   M E M B E R )   ( ( s i z e _ t )   & ( ( T Y P E   * ) 0 ) - > M E M B E R ) c o n t a i n e r _ o f
。 只 需 给 定 结 构 体 中 类 型   字 段 的 地 址 、 名 字 和 结 构 体 容 器 的 类 型 ， 它 就 可 以 返 回 结 构 体 的 起 始 地 址 。 在 宏 定 义 的 第 一 行 ， 声 明 了 一 个 指 向 结 构 体 成 员 变 量 的 指 针 ， 并 且 把   的 地 址 赋 给 它 。 现 在   和   指 向 了 同 一 个 地 址 。 从 技 术 上 讲 我 们 并 不 需 要 这 一 行 ， 但 是 它 可 以 方 便 地 进 行 类 型 检 查 。 第 一 行 保 证 了 特 定 的 结 构 体 （ 参 数 ） 包 含 成 员 变 量 。 第 二 行 代 码 会 用 宏 计 算 成 员 变 量 相 对 于 结 构 体 起 始 地 址 的 偏 移 ， 然 后 从 结 构 体 的 地 址 减 去 这 个 偏 移 ， 最 后 就 得 到 了 结 构 体 。 当 然 了   和   不 是 提 供 的 唯 一 功 能 。 双 向 链 表 的 实 现 还 提 供 了 如 下 A P I ： l i s t _ a d d l i s t _ a d d _ t a i l l i s t _ d e l l i s t _ r e p l a c e l i s t _ m o v e l i s t _ i s _ l a s t l i s t _ e m p t y l i s t _ c u t _ p o s i t i o n l i s t _ s p l i c e l i s t _ f o r _ e a c h l i s t _ f o r _ e a c h _ e n t r y 等 等 很 多 其 它 A P I 。 l i s t _ h e a d p t r _ _ m p t r p t r p t r _ _ m p t r t y p e m e m b e r o f f s e t o f l i s t _ a d d l i s t _ e n t r y < l i n u x / l i s t . h >
v i a :   h t t p s : / / g i t h u b . c o m / 0 x A X / l i n u x - i n s i d e s / b l o b / m a s t e r / D a t a S t r u c t u r e s / d l i s t . m d 译 者 ： E z i o [ 6 ]   校 对 ： M r 小 眼 儿 [ 7 ] 本 文 由   L C T T [ 8 ]   原 创 编 译 ， L i n u x 中 国 [ 9 ]   荣 誉 推 出 [ 1 ] :   h t t p s : / / g i t h u b . c o m / t o r v a l d s / l i n u x / b l o b / m a s t e r / i n c l u d e / l i n u x / l i s t . h [ 2 ] :   h t t p : / / l x r . f r e e - e l e c t r o n s . c o m / i d e n t ? i = l i s t _ h e a d [ 3 ] :   h t t p s : / / g i t h u b . c o m / t o r v a l d s / l i n u x / b l o b / m a s t e r / i n c l u d e / l i n u x / t y p e s . h [ 4 ] :   h t t p : / / w w w . g n u . o r g / s o f t w a r e / l i b c / [ 5 ] :   h t t p s : / / g i t h u b . c o m / t o r v a l d s / l i n u x / b l o b / m a s t e r / d r i v e r s / c h a r / m i s c . c [ 6 ] :   h t t p s : / / g i t h u b . c o m / o s k a 8 7 4 [ 7 ] :   h t t p s : / / g i t h u b . c o m / t i n y e y e s e r [ 8 ] :   h t t p s : / / g i t h u b . c o m / L C T T / T r a n s l a t e P r o j e c t [ 9 ] :   h t t p s : / / l i n u x . c n / a r t i c l e - 7 3 2 1 - 1 . h t m l ? w x 推 荐 文 章 推 荐 文 章 点 击 标 题 或 输 入 文 章   I D   直 达 该 文 章
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理