Redis源码学习之链表

  • 链表在Redis中的应用场景

1.列表键的底层实现之一

2.RedisServer中保存的客户端状态信息

3.发布与订阅

4.慢查询

5.监视器

  • 链表节点数据结构

Redis实现的是双端无环链表,pre指针指向其前置节点,next指针指向其后置节点,表头节点的pre属性和表尾节点的next属性为nil,节点值的类型为interface{},从而达到保存不同类型值的目的。

//链表节点
type listNode struct {
	pre   *listNode		//前置节点
	next  *listNode		//后置节点
	value interface{}	//节点值
}
  • 链表结构

通过list结构持有链表,其中head、tail属性分别指向表头和表尾节点,length属性用于记录链表长度,从而可以使获取链表长度的复杂度从O(N)降低为O(1)。此外,还有三个函数类型的属性,分别为节点值复制函数dup,节点值释放函数free,节点值对比函数match。

//持有链表结构
type list struct {
	//指向表头节点
	head   *listNode
	//指向表尾节点
	tail   *listNode
	//记录链表长度
	length int64
	//节点值复制函数
	dup    func(ptr interface{}) interface{}
	//节点值释放函数
	free   func(ptr interface{})
	//节点值对比函数
	match  func(ptr interface{}, key interface{}) bool
}

例如,一个长度为4的节点如下图所示:

1.创建(初始化)链表

//创建链表
func ListCreate() *list {
	list := &list{}
	list.head, list.tail = nil, nil
	list.length = 0
	list.dup = nil
	list.free = nil
	list.match = nil

	return list
}

2.从表头方向插入节点

//从表头方向插入节点
func (l *list) AddNodeHead(v interface{}) {
	//为节点分配内存
	node := &listNode{value: v}
	if l.length == 0 {//插入空链表
		node.pre, node.next = nil, nil
		l.head, l.tail = node, node
	} else {//插入非空链表
		node.pre, node.next = nil, l.head
		//维护表头
		l.head.pre = node
		l.head = node
	}
	//维护链表长度
	l.length++
}

3.从表尾方向插入节点

//从表尾方向插入节点
func (l *list) AddNodeTail(v interface{}) {
	//为节点分配内存
	node := &listNode{value: v}
	if l.length == 0 {//插入空链表
		node.pre, node.next = nil, nil
		l.head, l.tail = node, node
	} else {//插入非空链表
		node.pre, node.next = l.tail, nil
		//维护表尾
		l.tail.next = node
		l.tail = node
	}
	//维护链表长度
	l.length++
}

4.插入节点到链表中某个节点之前或之后

分为两步处理:

第一步:维护插入节点的相关属性,顺带维护链表的head和tail

第二步:维护插入节点影响到的前置节点的next和后置节点的pre属性

//创建一个包含值 value 的新节点,并将它插入到 old_node 的之前或之后
func (l *list) InsertNode(oldNode *listNode, value interface{}, after bool) {
	if nil == oldNode {
		return
	}
	//为节点分配内存
	node := &listNode{value: value}
	//执行插入操作,这里只涉及node节点pre和next属性以及表头、表尾属性的维护
	if after { //插入节点到oldNode节点后,即oldNode.next = node
		node.pre = oldNode
		node.next = oldNode.next
		if l.tail == oldNode { //如果oldNode为原表尾,则需要维护表尾属性
			l.tail = node
		}
	} else { //插入节点到oldNode节点前,即oldNode.pre = node
		node.pre = oldNode.pre
		node.next = oldNode
		if l.head == oldNode { //如果oldNode为原表头,则需要维护表头属性
			l.head = node
		}
	}

	//统一处理插入节点前后节点的属性
	//统一维护插入节点的后置节点next属性
	if nil != node.next {
		node.next.pre = node
	}
	//统一维护插入节点的前置节点pre属性
	if nil != node.pre {
		node.pre.next = node
	}
	//维护链表长度
	l.length++
}

5.删除节点

//删除节点
func (l *list) DeleteNode(node *listNode) {
	if 0 == l.length || nil == node {
		return
	}
	if nil != node.pre {//节点非表头
		node.pre.next = node.next
	} else {//节点是表头
		l.head = node.next
	}
	if nil != node.next {//节点非表尾
		node.next.pre = node.pre
	} else {//节点是表尾
		l.tail = node.pre
	}
	if nil != l.free {
		l.free(node.value)
	}
	node = nil
	//维护链表长度
	l.length--
}

6.通过key值查找节点

如果节点比对函数match为nil则直接判断节点值是否相等。

//通过key查找节点
func (l *list) SearchKey(key interface{}) *listNode {
	if nil == l {
		return nil
	}
	//初始化返回节点
	var node *listNode = nil
	//初始化迭代器
	iter := ListGetIterator(l, AL_START_HEAD)
	//迭代查找
	for current:=iter.Next();nil!=current;current=iter.Next() {
		if nil != l.match {//链表有匹配方法
			if l.match(current.GetValue(), key) {
				node = current
				break
			}
		} else {//链表无匹配方法
			if current.GetValue() == key {
				node = current
				break
			}
		}
	}
	//释放迭代器
	ListReleaseIterator(iter)
	return node
}

7.链表给定索引节点的值

PS:源码中并没有用到迭代器,重写使用了迭代器

//返回链表给定索引上的值
func (l *list) Index(index int64) *listNode {
	var node *listNode = nil
	var n int64
	var iter *listIter
	if index < 0 {//从表尾方向查找
		iter = ListGetIterator(l, AL_START_TAIL)
		n = (-index)-1 //例如:index为-1则n为0
	} else {//从表头方向查找
		iter = ListGetIterator(l, AL_START_HEAD)
		n = index
	}
	//利用迭代器查找
	for current:=iter.Next();nil!=current&&n>=0;current=iter.Next(){
		node = current
		//计数减一,当n为负数时break,则当前node指向头或尾节点
		n--
	}
	if n < 0 { //补偿操作,只要n为负数,则证明out of range,返回nil
		node = nil
	}
	ListReleaseIterator(iter)
	return node
}

8.取出链表的表尾节点,并将它移动到表头,成为新的表头节点

例如:

原表:1->2->3->4

Rotate后:4->1->2->3

func (l *list) Rotate() {
	if nil == l || l.length <= 1 {
		return
	}

	//取出表尾
	tail := l.tail
	l.tail = tail.pre
	l.tail.next = nil

	//将表尾插到表头
	tail.next = l.head
	tail.pre = nil
	l.head.pre = tail
	l.head = tail
}

9.复制链表

如果节点复制函数dup为nil则直接复制节点值

//复制链表
func (l *list)Dup() (*list) {
	//源链表为空直接返回
	if nil == l {
		return nil
	}

	//为链表分配内存
	dest := ListCreate()
	if nil == dest {
		return nil
	}
	//复制三个函数属性
	dest.dup = l.dup
	dest.free = l.free
	dest.match = l.match

	//通过源链表获取迭代器
	iter := ListGetIterator(l, AL_START_HEAD)
	for current:=iter.Next();nil!=current;current=iter.Next() {
		var value interface{}
		if nil != l.dup {//链表存在复制函数
			value = l.dup(current.GetValue())
		} else {
			value = current.GetValue()
		}
		//从表尾插入
		dest.AddNodeTail(value)
	}

	//释放掉迭代器
	ListReleaseIterator(iter)

	return dest
}
  • 链表迭代器

实际上,上文中的代码已经涉及到了迭代器的使用,迭代器有两个属性,next指向迭代节点,direction为迭代方向(表头or表尾)

//迭代器
type listIter struct {
	//指向迭代节点,通过Next方法返回
	next      *listNode
	//迭代方向
	direction int
}

1.为某个链表创建迭代器

//获取迭代器
func ListGetIterator(l *list, direction int) *listIter {
	var listIter = &listIter{direction: direction}
	if direction == AL_START_HEAD {//从表头开始迭代
		listIter.next = l.head
	} else {//从表尾开始迭代
		listIter.next = l.tail
	}
	return listIter
}

2.返回迭代器当前指向节点

//返回迭代器当前所指向的节点
func (iter *listIter) Next() *listNode {
	//获取迭代器下一个节点作为当前节点
	current := iter.next

	if nil != current {
		if iter.direction == AL_START_HEAD { //从头方向迭代
			iter.next = current.next
		} else { //从尾方向迭代
			iter.next = current.pre
		}
	}

	return current
}
  • 综述

adlist体现了Redis精简干练的风格,不到600行的代码读起来让人身心愉悦。尤其是在实现了迭代器之后,可以通过它来实现各种遍历方法,比如:

//打印链表
func (l *list) Print(direction int) {
	//获取迭代器
	iter := ListGetIterator(l, direction)
	for cur:=iter.Next();nil!=cur;cur=iter.Next(){
		fmt.Println(cur.GetValue())
	}
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏每日一篇技术文章

Swift3.0 - 真的很简单

中文翻译文档 https://github.com/numbbbbb/the-swift-programming-language-in-chinese

1571
来自专栏恰童鞋骚年

剑指Offer面试题:12.在O(1)时间删除链表结点

  在单向链表中删除一个结点,最常规的做法无疑是从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点。这种思路由于需要顺序查找,时间复杂度自然就是...

721
来自专栏java初学

hashMap原理(java8)

37517
来自专栏GreenLeaves

C# 通过IEnumberable接口和IEnumerator接口实现自定义集合类型foreach功能

1、IEnumerator和IEnumerable的作用 其实IEnumerator和IEnumerable的作用很简单,就是让除数组和集合之外的类型也能支持f...

20510
来自专栏Java帮帮-微信公众号-技术文章全总结

10(01)总结形式参数,包,修饰符,内部类

类,抽象类,接口的综合小练习 /* 教练和运动员案例(学生分析然后讲解) 乒乓球运动员和篮球运动员。 乒乓球教练和篮球教练。 为了出国交流,跟乒乓球相关...

2765
来自专栏java思维导图

对map集合进行排序

今天做统计时需要对X轴的地区按照地区代码(areaCode)进行排序,由于在构建XMLData使用的map来进行数据统计的,所以在统计过程中就需要对map进行排...

852
来自专栏Java进阶之路

java面试热点:集合框架(二)

1950
来自专栏老马说编程

(35) 泛型 (上) - 基本概念和原理 / 计算机程序的思维逻辑

之前章节中我们多次提到过泛型这个概念,从本节开始,我们就来详细讨论Java中的泛型,虽然泛型的基本思维和概念是比较简单的,但它有一些非常令人费解的语法、细节、以...

2328
来自专栏Java架构

Java 8简明教程

2305
来自专栏kevindroid

leetcode 93. Restore IP Addresses

2034

扫码关注云+社区

领取腾讯云代金券