Chinaunix

标题: 有人研究过linux下链表的实现 [打印本页]
作者: 怪怪虎    时间: 2006-06-26 22:57
标题: 有人研究过linux下链表的实现
有兴趣的可以共同研究，
我们作个小程序。
赫赫。
联系
xuejian1982@gmail.com
作者: yg    时间: 2006-06-26 23:48
链表和linux有什么关系?
作者: wolf0403    时间: 2006-06-27 08:21
内核里的链表在 IBM dW 介绍的很详细了。。
作者: seawolf1979    时间: 2006-06-27 10:05
http://www-900.ibm.com/developer ... l-chain/index.shtml
作者: albcamus    时间: 2006-06-27 11:12
这个很简单啊， 我觉得主要是gcc扩展offset_of的利用，不然很难写出可靠的list_entry宏。
作者: flw    时间: 2006-06-27 11:20
原帖由 albcamus 于 2006-6-27 11:12 发表
这个很简单啊， 我觉得主要是gcc扩展offset_of的利用，不然很难写出可靠的list_entry宏。

什么叫 offset_of 啊？
作者: albcamus    时间: 2006-06-27 13:39
原帖由 flw 于 2006-6-27 11:20 发表

什么叫 offset_of 啊？


打错了，没有那个下划线。

linux内核的list_entry及相关宏是这样的：

  2. #define list_entry(ptr, type, member) \
  3.         container_of(ptr, type, member)

  5. #define container_of(ptr, type, member) ({                        \
  6.         const typeof( ((type *)0)->member ) *__mptr = (ptr);        \
  7.         (type *)( (char *)__mptr - offsetof(type,member) );})

  9. #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)

  11. #define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
复制代码


说到底， 最重要的还是gcc允许程序员使用__builtin_offsetof来探测struct中某个域的偏移是多少， 不然这个代码就很难写了。
作者: mingyanguo    时间: 2006-06-27 14:20
可以不用builtin的
这是FreeBSD的

  2. #ifndef __cplusplus
  3. #define __offsetof(type, field) ((size_t)(&((type *)0)->field))
  4. #else
  5. #define __offsetof(type, field)                                 \
  6.   (__offsetof__ (reinterpret_cast <size_t>                      \
  7.                  (&reinterpret_cast <const volatile char &>     \
  8.                   (static_cast<type *> (0)->field))))
  9. #endif
复制代码
作者: albcamus    时间: 2006-06-27 17:23
[quote]原帖由 mingyanguo 于 2006-6-27 14:20 发表
可以不用builtin的
这是FreeBSD的

  2. #ifndef __cplusplus
  3. #define __offsetof(type, field) ((size_t)(&((type *)0)->field))
  4. #else
  5. #define __offsetof(type, field)                     ... [/quote]

  7. 你看早期linux的定义：
  8. [code]
  9. #define list_entry(ptr, type, member) \
  10.         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
复制代码


为什么后来改成了gcc的呢？ 害得我都忘了最初看《情景分析》一开始就是看到的这个定义。……

--知道了，在include/linux/stddef.h中， 编译器提供方法的话就用编译器的，不然就用可移植的。

[ 本帖最后由 albcamus 于 2006-6-27 17:25 编辑 ]
作者: yg    时间: 2006-06-27 19:26
离题不知几里老
作者: mingyanguo    时间: 2006-06-27 19:32
原帖由 albcamus 于 2006-6-27 17:23 发表


你看早期linux的定义：

  2. #define list_entry(ptr, type, member) \
  3.         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
复制代码


为什么后来改成了gcc的呢？ 害得我都忘了 ...

nod.
Linux反正已经依赖gcc了,干脆多依赖一点了.
作者: dos_net    时间: 2006-06-27 21:58
好像有本书专讲这方面的,忘了..
作者: connet    时间: 2006-06-28 08:52
2.4 是从  (type*)0 得到offset的。个人觉得还是老的定义好，
任何平台任何编译器老定义永远不会出错。
应用程序也可以使用这种方法。若你的应用程序是跨平台的， 最好避免gcc 特性。



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2