Go语言移植Linux内核数据结构hlist

hlist(哈希链表)可以通过相应的Hash算法，迅速找到相关的链表Head及节点.在有些应用场景，比Go标准库提供的list(一种常见的双向链表)更合适。 依照list.h中的源码，我实现了一个Go语言版本的hlist例子。首先说下hlist的构成: 在hlist(哈希链表)中， 头结点使用struct hlist_head来表示,hlist_head仅一个first指针. 普通节点使用struct hlist_node来表示。源码中有几个特别的地方:1. 在struct hlist_node中有一个**pprev中的二级指针, pprev指向的是当前hlist_node变量中的前一个变量的next的地址， 如果是第一个元素的话，这个值指向的是first的地址， 如果是最后一个节点的话，指向的是NULL。2.container_of 源码里面有个宏定义: #define hlist_entry(ptr, type, member) container_of(ptr,type,member) 利用一些技巧，可通过结构体内部成员member(即链表node)得到所在结构体的首地址所以C/C++应用中调用时，常用如下定义方式：struct MYST { int data; struct list_head head; struct hlist_node node;} *myst;在Go中，我将其变更为:type HLElement struct { Next *HLElement PPrev **HLElement Value interface{}}利用interface{}的特性，可将自定义struct之类对应设置给Value.在使用时，，通过interface{}转换回原本对象即可3.在hlist_del()中使用LIST_POISON而不是(== NULL)的形式 n->next = LIST_POISON1; n->pprev = LIST_POISON2; 原因可能是，通过这个标记删除node,如果在其它地方用到这种node, 可以用来区分是否引用了已被删除的node。在Go版中，我直接去掉了LIST_POISON,直接将其设为nil。4.在遍历链表时，提供了safe版本，防止因为节点被删除而引起的中断 在Go版中我也提供了相关实现。具体的实现及测试代码:

package main//hlist (仿Linux内核数据结构hlist, 可参考内核源码list.h)//author: Xiong Chuan Liang//date: 2015-2-12import ("fmt")func main() {/////////////////////////////////////*Hash桶HLHead[0]HLHead[1]-> HLElement[0] ->HLElement[1]HLHead[2]-> HLElement[0]HLHead[3]-> HLElement[0] ->HLElement[1]-> HLElement[2] ->HLElement[3]HLHead[4]-> HLElement[0]*/fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" hlist用法演示 : ")lst := [20]HLHead{}for i := 0; i < 20; i++ {hash := getHash(i)elem1 := &HLElement{Value: i}AddHead(elem1, &lst[hash])fmt.Println("i:", i, " Hash:", hash)}fmt.Println(" \n 遍历其中一个Head(lst[1])所对应的链表: ")f := func(e *HLElement) bool {fmt.Println("HLElement.Value =", e.Value)return true}For_each_safe(&lst[1], f)fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" 演示InsertAfter/InsertBefore : ")hHead := &HLHead{}elem1 := &HLElement{Value: 1}elem2 := &HLElement{Value: 2}elem3 := &HLElement{Value: 300}elem4 := &HLElement{Value: 400}AddHead(elem1, hHead)InsertAfter(elem1, elem2)InsertAfter(elem2, elem3)InsertBefore(elem4, elem3)fmt.Println(" \n 遍历链表看效果: ")For_each(hHead, f)fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" \n 测试MoveList: lst[1] => MoveList(0->1) ")MoveList(&lst[0], &lst[1])For_each_safe(&lst[1], f)fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" 从指定element开始遍历链表: ")For_each_safe_from(elem2, f)fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" 将自定义结构体放入链表: ")elemA := &HLElement{Value: &Demo{"a"}}elemB := &HLElement{Value: &Demo{"b"}}elemC := &HLElement{Value: &Demo{"c"}}AddHead(elemA, hHead)AddHead(elemB, hHead)AddHead(elemC, hHead)fs := func(e *HLElement) bool {m, ok := e.Value.(*Demo)if ok {fmt.Println("struct =", m.Data)} else {fmt.Println("int =", e.Value)}return true}For_each_safe(hHead, fs)fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" Remove(elemB): ")Remove(elemB)For_each_safe(hHead, fs)fmt.Println(" \n //////////////////////////////////// ")fmt.Println(" Empty()/Unhashed(): ")if Empty(hHead) {fmt.Println(" Empty(hHead) = true: hHead对应的链表为空! ")} else {fmt.Println(" Empty(hHead) = false: hHead对应的链表不为空! ")}hHeadEmpty := &HLHead{}if Empty(hHeadEmpty) {fmt.Println(" Empty(hHeadEmpty) = true: hHeadEmpty对应的链表为空! ")} else {fmt.Println(" Empty(hHeadEmpty) = false : hHeadEmpty对应的链表不为空! ")}if Unhashed(elem1) {fmt.Println(" Unhashed(elem1) = true: elem1不在链表中! ")} else {fmt.Println(" Unhashed(elem1) = false: elem1在链表中! ")}}//演示用的Structtype Demo struct {Data string}//演示用的Hash算法func getHash(c int) int {return (c % 16)}///////////////////////////////////////////////////////////////////type HLHead struct {First *HLElement}type HLElement struct {Next *HLElementPPrev **HLElementValue interface{}}type ElemFunc func(e *HLElement) boolfunc For_each(h *HLHead, f ElemFunc) {pos := h.Firstfor pos != nil {if !f(pos) {break}pos = pos.Next}}func For_each_safe(h *HLHead, f ElemFunc) {pos := h.Firstfor pos != nil {n := pos.Nextif !f(pos) {break}pos = n}}func For_each_safe_from(h *HLElement, f ElemFunc) {pos := h.Nextfor pos != nil {n := pos.Nextif !f(pos) {break}pos = n}}//将普通结点n插入到头结点h对应的hash桶的第一个结点的位置func AddHead(n *HLElement, h *HLHead) {first := h.Firstn.Next = firstif first != nil {first.PPrev = &n.Next}h.First = nn.PPrev = &h.First}//n: 新节点, next:链表func InsertBefore(n *HLElement, next *HLElement) {pprev := next.PPrevn.PPrev = pprevn.Next = nextnext.PPrev = &n.Nextif pprev != nil {//将原来上一个结点的next的值,指向新节点n*pprev = n}}//n: 链表, next:新节点func InsertAfter(n *HLElement, next *HLElement) {next.Next = n.Nextn.Next = nextnext.PPrev = &n.Nextif next.Next != nil {next.Next.PPrev = &next.Next}}//移动listfunc MoveList(old, new *HLHead) {new.First = old.Firstif new.First != nil {//链表所指定向的第一个元素不为空，更改其pprev指向到Newnew.First.PPrev = &new.First}old.First = nil}//判断结点是否已经在链表中,如返回true,表示不在其中func Unhashed(h *HLElement) bool {return (h.PPrev == nil)}//判断链表是否为空func Empty(h *HLHead) bool {return (h.First == nil)}//删除节点func Remove(n *HLElement) {next := n.Nextpprev := n.PPrevif pprev != nil {*pprev = next}if next != nil {next.PPrev = pprev}n.Next = niln.PPrev = nil}////////////////////////////////////////////////////////////////////* //////////////////////////////////// hlist用法演示 :i: 0 Hash: 0i: 1 Hash: 1i: 2 Hash: 2i: 3 Hash: 3i: 4 Hash: 4i: 5 Hash: 5i: 6 Hash: 6i: 7 Hash: 7i: 8 Hash: 8i: 9 Hash: 9i: 10 Hash: 10i: 11 Hash: 11i: 12 Hash: 12i: 13 Hash: 13i: 14 Hash: 14i: 15 Hash: 15i: 16 Hash: 0i: 17 Hash: 1i: 18 Hash: 2i: 19 Hash: 3 遍历其中一个Head(lst[1])所对应的链表:HLElement.Value = 17HLElement.Value = 1 //////////////////////////////////// 演示InsertAfter/InsertBefore : 遍历链表看效果:HLElement.Value = 1HLElement.Value = 2HLElement.Value = 400HLElement.Value = 300 //////////////////////////////////// 测试MoveList: lst[1] => MoveList(0->1)HLElement.Value = 16HLElement.Value = 0 //////////////////////////////////// 从指定element开始遍历链表:HLElement.Value = 400HLElement.Value = 300 //////////////////////////////////// 将自定义结构体放入链表:struct = cstruct = bstruct = aint = 1int = 2int = 400int = 300 //////////////////////////////////// Remove(elemB):struct = cstruct = aint = 1int = 2int = 400int = 300 //////////////////////////////////// Empty()/Unhashed(): Empty(hHead) = false: hHead对应的链表不为空! Empty(hHeadEmpty) = true: hHeadEmpty对应的链表为空! Unhashed(elem1) = false: elem1在链表中!*/

例子基本实现了常用的东西。

在实现InsertBefore()的过程中，发现指针的使用与C实现有些许差别，原因不甚了了，有空再测测。

部份参考资料:

一份list.h的源码:一篇很细的hlist的说明:

MAIL: xcl_168@aliyun.com

BLOG:

人言未必皆真，听言只听三分。