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

xcltapestry · · 3733 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

   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-12

import (
	"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在链表中!  ")
	}

}

//演示用的Struct
type Demo struct {
	Data string
}

//演示用的Hash算法
func getHash(c int) int {
	return (c % 16)
}

///////////////////////////////////////////////////////////////////
type HLHead struct {
	First *HLElement
}

type HLElement struct {
	Next  *HLElement
	PPrev **HLElement
	Value interface{}
}

type ElemFunc func(e *HLElement) bool

func For_each(h *HLHead, f ElemFunc) {
	pos := h.First
	for pos != nil {
		if !f(pos) {
			break
		}
		pos = pos.Next
	}
}

func For_each_safe(h *HLHead, f ElemFunc) {
	pos := h.First
	for pos != nil {
		n := pos.Next
		if !f(pos) {
			break
		}
		pos = n
	}
}

func For_each_safe_from(h *HLElement, f ElemFunc) {
	pos := h.Next
	for pos != nil {
		n := pos.Next
		if !f(pos) {
			break
		}
		pos = n
	}
}

//将普通结点n插入到头结点h对应的hash桶的第一个结点的位置
func AddHead(n *HLElement, h *HLHead) {
	first := h.First
	n.Next = first
	if first != nil {
		first.PPrev = &n.Next
	}

	h.First = n
	n.PPrev = &h.First
}

//n: 新节点,  next:链表
func InsertBefore(n *HLElement, next *HLElement) {
	pprev := next.PPrev
	n.PPrev = pprev
	n.Next = next
	next.PPrev = &n.Next
	if pprev != nil {
		//将原来上一个结点的next的值,指向新节点n
		*pprev = n
	}
}

//n: 链表, next:新节点
func InsertAfter(n *HLElement, next *HLElement) {
	next.Next = n.Next
	n.Next = next
	next.PPrev = &n.Next

	if next.Next != nil {
		next.Next.PPrev = &next.Next
	}
}

//移动list
func MoveList(old, new *HLHead) {
	new.First = old.First
	if new.First != nil {
		//链表所指定向的第一个元素不为空，更改其pprev指向到New
		new.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.Next
	pprev := n.PPrev
	if pprev != nil {
		*pprev = next
	}
	if next != nil {
		next.PPrev = pprev
	}
	n.Next = nil
	n.PPrev = nil
}

///////////////////////////////////////////////////////////////////

/*

 ////////////////////////////////////
 hlist用法演示 :
i: 0   Hash: 0
i: 1   Hash: 1
i: 2   Hash: 2
i: 3   Hash: 3
i: 4   Hash: 4
i: 5   Hash: 5
i: 6   Hash: 6
i: 7   Hash: 7
i: 8   Hash: 8
i: 9   Hash: 9
i: 10   Hash: 10
i: 11   Hash: 11
i: 12   Hash: 12
i: 13   Hash: 13
i: 14   Hash: 14
i: 15   Hash: 15
i: 16   Hash: 0
i: 17   Hash: 1
i: 18   Hash: 2
i: 19   Hash: 3

 遍历其中一个Head(lst[1])所对应的链表:
HLElement.Value = 17
HLElement.Value = 1

 ////////////////////////////////////
 演示InsertAfter/InsertBefore :

 遍历链表看效果:
HLElement.Value = 1
HLElement.Value = 2
HLElement.Value = 400
HLElement.Value = 300

 ////////////////////////////////////

 测试MoveList: lst[1] => MoveList(0->1)
HLElement.Value = 16
HLElement.Value = 0

 ////////////////////////////////////
  从指定element开始遍历链表:
HLElement.Value = 400
HLElement.Value = 300

 ////////////////////////////////////
  将自定义结构体放入链表:
struct = c
struct = b
struct = a
int  = 1
int  = 2
int  = 400
int  = 300

 ////////////////////////////////////
  Remove(elemB):
struct = c
struct = a
int  = 1
int  = 2
int  = 400
int  = 300

 ////////////////////////////////////
  Empty()/Unhashed():
  Empty(hHead) = false: hHead对应的链表不为空!
  Empty(hHeadEmpty) = true: hHeadEmpty对应的链表为空!
  Unhashed(elem1) = false: elem1在链表中!


*/

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

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

部份参考资料:

一份list.h的源码:
http://lxr.free-electrons.com/source/include/linux/list.h
一篇很细的hlist的说明:
http://blog.chinaunix.net/uid-22566367-id-2192969.html

MAIL: xcl_168@aliyun.com

BLOG: http://blog.csdn.net/xcl168

有疑问加站长微信联系（非本文作者）