GoLang完整实现快速列表

目录

快速列表介绍

快速列表（quicklist）是Redis中特有的一种数据结构，主要是为了解决双端链表的弊端：双端链表的附加空间比较高，因为prev和next指针会占掉一部分的空间（64位系统占用8>

Redis中的快速列表实际上是zipList（经过优化过的数组）和linkedList的混合体，它把zipList放在linkedList的每个结点中，实现紧凑存储。如下图所示：

实现快速列表

快速列表的结构

由于Go语言自带slice这种操作方便的“动态数组”结构，所以我给链表的每个节点中都分配一个容量为1024大小的切片，那么一个链表节点就可以看作是一页，页大小就是1024。

页大小

首先定义页大小为1024：

// pageSize 一页的大小
const pageSize = 1024

表头结构

// QuickList 快速列表是在页（切片）之上建立的链表
// QuickList 比普通链表的插入、遍历以及内存有着更好的性能
type QuickList struct {
	data *list.List // 每一页就是interface{}的切片，大小为1024
	size int
}

表头结构中的data字段直接使用了Go语言list包中的List结构：

// 双向链表标头结构
type List struct {
	root Element // 哨兵节点
	len  int     // 链表的节点个数
}

// 双向链表的节点
type Element struct {
	// 前向和后向指针
	next, prev *Element
	// 表头结构
	list *List
	// 值域
	Value interface{}
}

Go语言自带的list包实现了对双向链表的封装，双向链表的节点元素是interface{}类型，利用这种方式实现了泛型。

我们对快速列表的实现，使得上述双向链表节点中存储的实际上是容量为1024的切片，此后对于链表的相关操作，直接调用list包向外暴露的API即可。

快速列表的迭代器

快速列表的迭代器中有三个字段：链表的节点node（可以看成一页），元素在页中的偏移量、表头结构。

这样实现的迭代器，使得迭代器既可以在元素之前迭代，也可以在页之间快速迭代。

// iterator 快速列表的迭代器，在[-1, ql.Len()]之间迭代
type iterator struct {
	// 快速列表的一页
	node *list.Element
	// 元素下标在页中的偏移量
	offset int
	ql     *QuickList
}

使用迭代器返回一个元素

使用迭代器返回一个元素的复杂度为O(1)，一个元素的位置可以通过 页的位置 + 该元素在页中的位置 快速定位。

// 使用迭代器返回一个元素
func (iter *iterator) get() interface{} {
	return iter.page()[iter.offset]
}

返回迭代器对应的那一页

上面我们说过，链表的节点元素其实就是一个容量为1024的slice，通过类型断言直接返回即可。

// 返回迭代器对应的那一页
func (iter *iterator) page() []interface{} {
	return iter.node.Value.([]interface{})
}

根据元素下标返回对应的迭代器

快速列表查找元素效率比双向列表要快，首先利用迭代器一页一页进行迭代，当确定了元素在哪一页后，利用元素的下标直接在页内的slice中直接定位即可。

func (ql *QuickList) find(index int) *iterator {
	if ql == nil {
		panic("list is nil")
	}
	if index < 0 || index >= ql.size {
		panic("index out of bound")
	}
	var n *list.Element
	// 保存当前页的所有元素
	var page []interface{}
	// 累加遍历到当前页为止，前面的所有元素数量
	var pageBeg int
	if index < ql.size/2 {
		// 从表头进行查找
		n = ql.data.Front()
		pageBeg = 0
		for {
			page = n.Value.([]interface{})
			if pageBeg+len(page) > index {
				break
			}
			pageBeg += len(page)
			n = n.Next()
		}
	} else {
		// 从表尾进行查找
		n = ql.data.Back()
		pageBeg = ql.size
		for {
			page = n.Value.([]interface{})
			pageBeg -= len(page)
			if pageBeg <= index {
				break
			}
			n = n.Prev()
		}
	}
	pageOffset := index - pageBeg
	return &iterator{
		node:   n,
		offset: pageOffset,
		ql:     ql,
	}
}

向后迭代一位

// next 页内迭代器，向后迭代一位
// 如果当前元素下标未出界且不在最后一位，就向后移动一位，返回true
// 如果当前元素下标在快速列表的最后一页且是最后一个元素，直接返回false
// 如果当前元素下标不在快速列表的最后一页，但是是当前页的最后一个元素，跳转到下一页，返回true
func (iter *iterator) next() bool {
	// 得到迭代器对应的那一页
	page := iter.page()
	// 当前位置未出界且不在最后一位，就向后移动一位，返回true
	if iter.offset < len(page)-1 {
		iter.offset++
		return true
	}
	// 当前元素在快速列表的最后一页且是最后一个元素，直接返回false
	if iter.node == iter.ql.data.Back() {
		// already at last node
		iter.offset = len(page)
		return false
	}
	// 当前元素不在快速列表的最后一页，但是是当前页的最后一个元素，跳转到下一页，返回true
	iter.offset = 0
	iter.node = iter.node.Next()
	return true
}

往前迭代一位

// prev 页内迭代器，向前迭代一位
func (iter *iterator) prev() bool {
	if iter.offset > 0 {
		iter.offset--
		return true
	}
	if iter.node == iter.ql.data.Front() {
		iter.offset = -1
		return false
	}
	iter.node = iter.node.Prev()
	prevPage := iter.node.Value.([]interface{})
	iter.offset = len(prevPage) - 1
	return true
}

添加和插入元素

向表尾添加一个元素

向表尾添加元素需要考虑三种情况：

列表是空的，创建新的一页，添加到表尾即可。表尾节点那一页是满的，获取表尾节点，创建新的一页，添加到表尾节点的后面即可。表尾节点那一页不是满的，正常添加到表尾即可。

// Add 添加元素到表尾
func (ql *QuickList) Add(val interface{}) {
	ql.size++
	// 列表是空的
	if ql.data.Len() == 0 {
		page := make([]interface{}, 0, pageSize)
		page = append(page, val)
		ql.data.PushBack(page)
		return
	}
	// 获取表尾节点
	backNode := ql.data.Back()
	backPage := backNode.Value.([]interface{})
	// 表尾节点页满了，需要新创建一页
	if len(backPage) == cap(backPage) {
		page := make([]interface{}, 0, pageSize)
		page = append(page, val)
		ql.data.PushBack(page)
		return
	}
	// 默认将节点添加进表尾页中
	backPage = append(backPage, val)
	backNode.Value = backPage
}

根据下标插入一个元素

// Insert 插入元素
// 插入元素的策略分三种情况：
// 1. 向最后一页的最后一个位置插入元素，直接掉用ql.Add()插入即可
// 2. 某一页插入一个元素，且该页未满，直接插入该页即可
// 3. 某一页插入一个元素，该页满了，就新创建一页，然后将前512个元素留在原来那页，将后512个元素移到新的页中，
//    新插入的元素，如果下标在[0,512]之间，就插入到原来页，如果下标在[516, 1024]之间，就插入到新创建的页中
func (ql *QuickList) Insert(index int, val interface{}) {
	// 向表尾插入元素
	if index == ql.size {
		ql.Add(val)
		return
	}
	iter := ql.find(index)
	page := iter.node.Value.([]interface{})
	// 如果待插入页的元素小于1024，直接插入到该页即可
	if len(page) < pageSize {
		// insert into not full page
		page = append(page[:iter.offset+1], page[iter.offset:]...)
		page[iter.offset] = val
		iter.node.Value = page
		ql.size++
		return
	}
	// 待插入页的元素已经满1024，就需要新创建一页
	var nextPage []interface{}
	// 后一半的元素放在新创建的页中，前一半元素放在原来的页中
	nextPage = append(nextPage, page[pageSize/2:]...) // pageSize must be even
	page = page[:pageSize/2]
	// 待插入元素的下标小于512，插到前面那页
	if iter.offset < len(page) {
		page = append(page[:iter.offset+1], page[iter.offset:]...)
		page[iter.offset] = val
	} else {
		// 待插入元素的下标大于512，插到后面那页
		i := iter.offset - pageSize/2
		nextPage = append(nextPage[:i+1], nextPage[i:]...)
		nextPage[i] = val
	}
	// 储存当前页和新创建的下一页
	iter.node.Value = page
	ql.data.InsertAfter(nextPage, iter.node)
	ql.size++
}

删除元素

// 删除元素
// 删除元素分为三种情况：
// 1.删除后的页不为空，且删除的不是该页的最后一个元素，什么都不用管
// 2.删除后的页不为空，且删除的是该页的最后一个元素，需要将迭代器移动到下一页的最后一个元素
// 3.删除的页为空（需要删除该页），且删除的页是最后一页，将迭代器置空
// 4.删除的页为空（需要删除该页），且删除的页不是最后一页，将迭代器指向下一页
func (iter *iterator) remove() interface{} {
	page := iter.page()
	val := page[iter.offset]
	// 先直接在页中删除这个元素
	page = append(page[:iter.offset], page[iter.offset+1:]...)
	// 如果删除后的页不为空，只更新iter.offset即可
	if len(page) > 0 {
		iter.node.Value = page
		// 如果删除的是页中的最后一个元素，那么迭代器需要移动到下一页的第一个元素
		if iter.offset == len(page) {
			if iter.node != iter.ql.data.Back() {
				iter.node = iter.node.Next()
				iter.offset = 0
			}
		}
	} else {
		// 如果删除后的页为空，需要删除该页
		// 如果删除的是最后一页，迭代器需要置空
		if iter.node == iter.ql.data.Back() {
			iter.ql.data.Remove(iter.node)
			iter.node = nil
			iter.offset = 0
		} else {
			// 如果删除的不是最后一页，迭代器需要指向下一页
			nextNode := iter.node.Next()
			iter.ql.data.Remove(iter.node)
			iter.node = nextNode
			iter.offset = 0
		}
	}
	iter.ql.size--
	return val
}

遍历快速列表

// Consumer 用于遍历中断的函数，返回true表示继续遍历，可以在Consumer中调用自定义函数
type Consumer func(i int, v interface{}) bool

// ForEach 遍历快速列表中的元素
// 如果consumer返回false，结束遍历
func (ql *QuickList) ForEach(consumer Consumer) {
	if ql == nil {
		panic("list is nil")
	}
	if ql.Len() == 0 {
		return
	}
	iter := ql.find(0)
	i := 0
	for {
		goNext := consumer(i, iter.get())
		if !goNext {
			break
		}
		i++
		// 遍历到表尾，结束
		if !iter.next() {
			break
		}
	}
}

完整实现

https://github.com/omlight95/GoRedis/blob/master/datastruct/list/quicklist.go

到此这篇关于GoLang完整实现快速列表的文章就介绍到这了,更多相关Go快速列表内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站！