前言

早期工作时候还是在开发内核驱动，对内核链表的抽象惊为天人，以至于后来多年时不时的还是回顾下，最近几年开始用golang作为工作语言，基本不大用链表这种数据结构，因此一直没有去实现一个类似的，最近go的泛型总算出来了，所以先用反射实现一个版本，以后等泛型稳定在考虑优化。

侵入式链表

侵入式链表指的是链表的结构本身是不包含数据域，比如内核的链表结构为

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

链表需要嵌入到业务结构中使用，比如我们定义一个目录结构体，这个目录通过链表链接了当前目录下所有的文件

struct dir {  struct list_head head;}struct file {  char *name;  struct list_head file;}

这种把链表直接作为数据结构嵌入到业务结构的我们就叫做intrusive list。他的优点是可以把当前的链表元素作为局部元素进行一系列的操作。内核实现侵入式链表的核心主要是两个设计container_of和offsetof

/** * container_of - cast a member of a structure out to the containing structure * @ptr:  the pointer to the member. * @type:  the type of the container struct this is embedded in. * @member:  the name of the member within the struct. * */#define container_of(ptr, type, member) ({        \  void *__mptr = (void *)(ptr);          \  static_assert(__same_type(*(ptr), ((type *)0)->member) ||  \          __same_type(*(ptr), void),      \          "pointer type mismatch in container_of()");  \  ((type *)(__mptr - offsetof(type, member))); })

通过这个container_of可以很轻松的通过宏构建简化遍历等操作

/** * list_for_each_entry  -  iterate over list of given type * @pos:  the type * to use as a loop cursor. * @head:  the head for your list. * @member:  the name of the list_head within the struct. */#define list_for_each_entry(pos, head, member)        \  for (pos = list_first_entry(head, typeof(*pos), member);  \       !list_entry_is_head(pos, head, member);      \       pos = list_next_entry(pos, member))

举一个使用的例子,使用非常简洁

struct dir d;for i = 0; i < 10;i++{  struct file f = &struct file{.name: fsprintf("file %d", i)}  list_add(&f.file,d.head)}struct file f;list_for_each_entry(f, d.head, "file"){  printf("file name %s", f.name)}

golang 实现

我们先定义基础结构

type ListHead struct {  next, prev *ListHead}func NewListHead() *ListHead {  var head ListHead  head.prev = &head  head.next = &head  return &head}func listAdd(new, prev, next *ListHead) {  next.prev = new  new.next = next  new.prev = prev  prev.next = new}func Add(new, head *ListHead) {  listAdd(new, head, head.next)}

这样基本是翻译内核的源码，非常的简单，接下来我们需要实现container_of

内核container_of的原理很简单，就是通过构造一个空结构计算member的offset在减去这个offset就指向结构体指针，go有反射可以部分的替代offset计算。

// #define container_of(ptr, type, member) ({        \//  void *__mptr = (void *)(ptr);          \//  static_assert(__same_type(*(ptr), ((type *)0)->member) ||  \//          __same_type(*(ptr), void),      \//          "pointer type mismatch in container_of()");  \// ((type *)(__mptr - offsetof(type, member))); })func containerOf(ptr *ListHead, v interface{}, member string) unsafe.Pointer {  t := reflect.TypeOf(v)  for t.Kind() == reflect.Ptr {    t = t.Elem()  }  filed, _ := t.FieldByName(member)  return unsafe.Add(unsafe.Pointer(ptr), -filed.Offset)}

实现这个container_of后我们还需要设计辅助遍历函数，c因为有宏只是做简单的文本替换，所以设计遍历宏比较简单，go只能依赖业务进行一次强转，否则接口无法设计

func ForEachEntry(head *ListHead, pos interface{}, member string, fn func(FiledStructPointer)) {  for ptr := head.next; !listEntryIsHead(ptr, head); ptr = ptr.next {    fsp := containerOf(ptr, pos, member)    fn(FiledStructPointer(fsp))  }}

这样就完成了一个侵入式链表的设计。

测试代码如下

type TestList struct {  a  int  ts ListHead}head := NewListHead() for i := 0; i < 10; i++ {    tl := TestList{a: i}    Add(&tl.ts, head) } ForEachEntry(head, TestList{}, "ts", func(pointer FiledStructPointer) {    tl := (*TestList)(pointer)    fmt.Printf("test list %v
", tl.a) })

上面这种实现还是不大优雅，比如需要业务自己强转一次，我们尝试优化下

func ForEachEntry(head *ListHead, pos interface{}, member string, fn func()) {  for ptr := head.next; !listEntryIsHead(ptr, head); ptr = ptr.next {    fsp := containerOf(ptr, pos, member)    reflect.ValueOf(pos).Elem().Set(reflect.NewAt(reflect.TypeOf(pos).Elem().Elem(), fsp))    fn()  }}

测试代码

head = NewListHead() for i := 0; i < 10; i++ {    tl := TestList{a: i}    AddTail(&tl.ts, head) }  var tl *TestList  ForEachEntry(head, &tl, "ts", func() {    fmt.Printf("test list %v
", tl.a)  })