实现 List 结构

本文进度对应的代码仓库：List

在前面的章节中，我们从 0 开始，实现了一个具备集群功能、可以持久化的 Redis 服务器。但是之前我们只实现了字符串类型，并没有实现其他的数据类型。

从这一章节开始，我们将逐步实现其他的数据类型。

我们先删除 redis.conf 文件中的集群相关配置，然后重新启动服务器，以单例模式启动服务器。

介绍

List 是 Redis 中最基础的数据结构之一，它是一个有序的字符串集合。

它支持的操作有：

LPUSH：将一个或多个值插入到列表的头部
RPUSH：将一个或多个值插入到列表的尾部
LPOP：移除并返回列表的第一个元素
RPOP：移除并返回列表的最后一个元素
LRANGE：返回列表中指定区间内的元素
LLEN：返回列表的长度
LINDEX：返回列表中指定索引的元素
LSET：设置列表中指定索引的元素的值

实现

我们对 List 结构的实现，我们使用 Go 语言的标准库中的 container/list 包。这个包提供了一个双向链表，我们可以使用它来实现 List 结构。我们在 database/list.go 文件中实现了 List 结构的相关操作。

database/list.go


package database
 
import (
	// Use the go standard library's list package
	"container/list"
	"redigo/interface/database"
	"redigo/interface/resp"
	"redigo/lib/utils"
	"redigo/resp/reply"
	"strconv"
)
 
// getAsList retrieves the list stored at the given key, or creates a new one if it doesn't exist.
// It returns the list and a boolean indicating if the key existed.
func getAsList(db *DB, key string) (*list.List, bool) {
	entity, ok := db.GetEntity(key)
	if !ok {
		// Key doesn't exist, create a new list
		return list.New(), false
	}
	// Key exists, check if it's a list
	lst, ok := entity.Data.(*list.List)
	if !ok {
		// Key exists but is not a list type
		return nil, true // Indicate key exists but is wrong type
	}
	return lst, true
}
 
// execLPush implements the LPUSH command: Prepends one or multiple values to a list
// LPUSH key value [value ...]
func execLPush(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
	values := args[1:]
 
	// Get or create list
	lst, exists := getAsList(db, key)
	if lst == nil && exists { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	// Prepend values
	for _, value := range values {
		lst.PushFront(value) // Add to the front (left)
	}
 
	// Store the updated list
	db.PutEntity(key, &database.DataEntity{Data: lst})
	db.addAof(utils.ToCmdLineWithName("LPUSH", args...))
 
	// Return the new length of the list
	return reply.MakeIntReply(int64(lst.Len()))
}
 
// execRPush implements the RPUSH command: Appends one or multiple values to a list
// RPUSH key value [value ...]
func execRPush(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
	values := args[1:]
 
	// Get or create list
	lst, exists := getAsList(db, key)
	if lst == nil && exists { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	// Append values
	for _, value := range values {
		lst.PushBack(value) // Add to the back (right)
	}
 
	// Store the updated list
	db.PutEntity(key, &database.DataEntity{Data: lst})
	db.addAof(utils.ToCmdLineWithName("RPUSH", args...))
 
	// Return the new length of the list
	return reply.MakeIntReply(int64(lst.Len()))
}
 
// execLPop implements the LPOP command: Removes and returns the first element of the list stored at key
// LPOP key
func execLPop(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
 
	// Get list
	lst, exists := getAsList(db, key)
	if !exists {
		return reply.MakeNullBulkReply()
	}
	if lst == nil { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	// Check if list is empty
	if lst.Len() == 0 {
		return reply.MakeNullBulkReply()
	}
 
	// Remove and get the first element
	element := lst.Front()
	lst.Remove(element)
	value := element.Value.([]byte)
 
	// If list becomes empty after pop, remove the key
	if lst.Len() == 0 {
		db.Remove(key)
	} else {
		// Otherwise update the list in database
		db.PutEntity(key, &database.DataEntity{Data: lst})
	}
 
	db.addAof(utils.ToCmdLineWithName("LPOP", args...))
	return reply.MakeBulkReply(value)
}
 
// execRPop implements the RPOP command: Removes and returns the last element of the list stored at key
// RPOP key
func execRPop(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
 
	// Get list
	lst, exists := getAsList(db, key)
	if !exists {
		return reply.MakeNullBulkReply()
	}
	if lst == nil { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	// Check if list is empty
	if lst.Len() == 0 {
		return reply.MakeNullBulkReply()
	}
 
	// Remove and get the last element
	element := lst.Back()
	lst.Remove(element)
	value := element.Value.([]byte)
 
	// If list becomes empty after pop, remove the key
	if lst.Len() == 0 {
		db.Remove(key)
	} else {
		// Otherwise update the list in database
		db.PutEntity(key, &database.DataEntity{Data: lst})
	}
 
	db.addAof(utils.ToCmdLineWithName("RPOP", args...))
	return reply.MakeBulkReply(value)
}
 
// execLRange implements the LRANGE command: Returns the specified elements of the list stored at key
// LRANGE key start stop
func execLRange(db *DB, args [][]byte) resp.Reply {
	// Parse arguments
	key := string(args[0])
	start, err := strconv.ParseInt(string(args[1]), 10, 64)
	if err != nil {
		return reply.MakeStandardErrorReply("value is not an integer or out of range")
	}
	stop, err := strconv.ParseInt(string(args[2]), 10, 64)
	if err != nil {
		return reply.MakeStandardErrorReply("value is not an integer or out of range")
	}
 
	// Get list
	lst, exists := getAsList(db, key)
	if !exists {
		return reply.MakeEmptyMultiBulkReply()
	}
	if lst == nil { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	// Convert negative indices
	size := int64(lst.Len())
	if start < 0 {
		start = size + start
	}
	if stop < 0 {
		stop = size + stop
	}
	if start < 0 {
		start = 0
	}
	if stop >= size {
		stop = size - 1
	}
	if start > stop {
		return reply.MakeEmptyMultiBulkReply()
	}
 
	// Collect elements
	elements := make([][]byte, 0, stop-start+1)
	index := int64(0)
	for e := lst.Front(); e != nil; e = e.Next() {
		if index >= start && index <= stop {
			elements = append(elements, e.Value.([]byte))
		} else if index > stop {
			break
		}
		index++
	}
 
	return reply.MakeMultiBulkReply(elements)
}
 
// execLLen implements the LLEN command: Returns the length of the list stored at key
// LLEN key
func execLLen(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
 
	// Get list
	lst, exists := getAsList(db, key)
	if !exists {
		return reply.MakeIntReply(0)
	}
	if lst == nil { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	return reply.MakeIntReply(int64(lst.Len()))
}
 
// execLIndex implements the LINDEX command: Returns the element at index in the list stored at key
// LINDEX key index
func execLIndex(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
	index, err := strconv.ParseInt(string(args[1]), 10, 64)
	if err != nil {
		return reply.MakeStandardErrorReply("value is not an integer or out of range")
	}
 
	// Get list
	lst, exists := getAsList(db, key)
	if !exists {
		return reply.MakeNullBulkReply()
	}
	if lst == nil { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	size := int64(lst.Len())
	if index < 0 {
		index = size + index
	}
	if index < 0 || index >= size {
		return reply.MakeNullBulkReply()
	}
 
	// Find the element at the specified index
	var element *list.Element
	if index < size/2 {
		// If index is in the first half, iterate from front
		element = lst.Front()
		for i := int64(0); i < index; i++ {
			element = element.Next()
		}
	} else {
		// If index is in the second half, iterate from back
		element = lst.Back()
		for i := size - 1; i > index; i-- {
			element = element.Prev()
		}
	}
 
	return reply.MakeBulkReply(element.Value.([]byte))
}
 
// execLSet implements the LSET command: Sets the list element at index to value
// LSET key index value
func execLSet(db *DB, args [][]byte) resp.Reply {
	key := string(args[0])
	index, err := strconv.ParseInt(string(args[1]), 10, 64)
	if err != nil {
		return reply.MakeStandardErrorReply("value is not an integer or out of range")
	}
	value := args[2]
 
	// Get list
	lst, exists := getAsList(db, key)
	if !exists {
		return reply.MakeStandardErrorReply("no such key")
	}
	if lst == nil { // Key exists but is not a list
		return reply.MakeWrongTypeErrReply()
	}
 
	size := int64(lst.Len())
	if index < 0 {
		index = size + index
	}
	if index < 0 || index >= size {
		return reply.MakeStandardErrorReply("index out of range")
	}
 
	// Find and update the element at the specified index
	var element *list.Element
	if index < size/2 {
		element = lst.Front()
		for i := int64(0); i < index; i++ {
			element = element.Next()
		}
	} else {
		element = lst.Back()
		for i := size - 1; i > index; i-- {
			element = element.Prev()
		}
	}
	element.Value = value
 
	db.PutEntity(key, &database.DataEntity{Data: lst})
	db.addAof(utils.ToCmdLineWithName("LSET", args...))
	return reply.MakeOKReply()
}
 
func init() {
	// Register list commands
	// Arity is negative because the command takes a variable number of arguments (key + at least one value)
	RegisterCommand("LPUSH", execLPush, -3)  // key value [value ...] -> at least 3 args
	RegisterCommand("RPUSH", execRPush, -3)  // key value [value ...] -> at least 3 args
	RegisterCommand("LPOP", execLPop, 2)     // key
	RegisterCommand("RPOP", execRPop, 2)     // key
	RegisterCommand("LRANGE", execLRange, 4) // key start stop
	RegisterCommand("LLEN", execLLen, 2)     // LLEN key -> exactly 2 args
	RegisterCommand("LINDEX", execLIndex, 3) // LINDEX key index -> exactly 3 args
	RegisterCommand("LSET", execLSet, 4)     // LSET key index value -> exactly 4 args
}

但是这里我们还有一点没做，就是在 Cluster 模式下，我们的 List 结构还不能正常工作。因为我们还没注册 List 结构的相关命令。

我们只需要在 cluster/router.go 文件中注册 List 结构的相关命令即可，使用 defaultFunc 函数作为默认处理函数。因为每个指令都是对单独的单个 key 进行操作的。

cluster/router.go


func makeRouter() map[string]CmdFunc {
	routerMap := make(map[string]CmdFunc)
	routerMap["exists"] = defaultFunc // exists key
	routerMap["type"] = defaultFunc   // type key
	routerMap["set"] = defaultFunc    // set key
	routerMap["get"] = defaultFunc    // get key
	routerMap["setnx"] = defaultFunc  // setnx key
	routerMap["getset"] = defaultFunc // getset key
 
	routerMap["ping"] = pingFunc     // ping command
	routerMap["rename"] = renameFunc // rename key
	routerMap["renamex"] = renameFunc
	routerMap["flushdb"] = flushDBFunc // flushdb command
	routerMap["del"] = delFunc         // del key
	routerMap["select"] = selectFunc   // select database
 
	routerMap["lpush"] = defaultFunc
	routerMap["rpush"] = defaultFunc
	routerMap["lpop"] = defaultFunc
	routerMap["rpop"] = defaultFunc
	routerMap["lrange"] = defaultFunc
	routerMap["llen"] = defaultFunc
	routerMap["lindex"] = defaultFunc
	routerMap["lset"] = defaultFunc
 
	return routerMap
}

测试


redis-cli -p 6380
127.0.0.1:6380> LPUSH mylist "first"
(integer) 1
127.0.0.1:6380> LPUSH mylist "second" "third"
(integer) 3
127.0.0.1:6380> RPUSH mylist "last"
(integer) 4
127.0.0.1:6380> LPOP mylist
"third"
127.0.0.1:6380> RPOP mylist
"last"
127.0.0.1:6380> LRANGE mylist 0 -1
1) "second"
2) "first"
127.0.0.1:6380> LRANGE mylist 0 0
1) "second"
127.0.0.1:6380> LRANGE mylist -2 -1
1) "second"
2) "first"
127.0.0.1:6380> DEL mylist
(integer) 1
127.0.0.1:6380> RPUSH mylist "one" "two" "three"
(integer) 3
127.0.0.1:6380> LLEN mylist
(integer) 3
127.0.0.1:6380> LINDEX mylist 0
"one"
127.0.0.1:6380> LINDEX mylist -1
"three"
127.0.0.1:6380> LINDEX mylist 5
(nil)
127.0.0.1:6380> LSET mylist 1 "new-two"
OK
127.0.0.1:6380> LRANGE mylist 0 -1
1) "one"
2) "new-two"
3) "three"

在这里我们测试了 List 结构的基本操作。如结果所示，这些操作都可以正常执行。