golang container/ring源码解读

最近在看gokit的熔断器源码的时候看到了内部有使用到 container/ring 的这个数据结构；虽然大体知道这个数据结构提供的一个常用API，也知道该怎么用；但是不知道内部具体是怎么实现的。所以就看了内部的源码实现；在这里分享出来，有不对的地方欢迎大家指正。

在正式开始讲解源码之前先铺垫几个基础的数据结构知识
1、单链表

节点内部会存储当前节点的值跟下一个节点的指针，单链表的访问只能向前推进访问不能后退

单链表

2、单向循环链表

单向循环链表的尾节点的后继节点指向了链表的头结点；其他跟单链表完全相同

单向循环链表

3、双向链表

双向链表每个节点内部存储了当前节点的值，后继节点的指针，前驱节点的指针

双向链表

4、双向循环链表

双向循环链表的头结点的前驱节点为链表的尾节点指针，而尾结点的后继节点为头结点的指针，其他跟双向链表完全相同

双向循环链表

而我们今天的主角也是双向循环链表

首先看下暴露出来的API；我们能直接使用的也就是下面这些接口

 type Ring
    func New(n int) *Ring
    func (r *Ring) Do(f func(interface{}))
    func (r *Ring) Len() int
    func (r *Ring) Link(s *Ring) *Ring
    func (r *Ring) Move(n int) *Ring
    func (r *Ring) Next() *Ring
    func (r *Ring) Prev() *Ring
    func (r *Ring) Unlink(n int) *Ring

1、现在让我们从 `type Ring` 这个定义看起

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

文档注释也说的很清楚了 Ring是一个由多个元素节点组成的环形的链表，或者是一个环；组成这样一个环的每个元素都由三个字段组成

next：后继节点指针
prev：前驱节点指针
Value：存节点元素的值

2、创建有n个元素的`Ring`对象(`New(n int) *Ring`)

// New creates a ring of n elements.
func New(n int) *Ring {
    // 条件判断，n 小于0是没有意义的
    if n <= 0 {
        return nil
    }
   // 创建环的头结点
    r := new(Ring)
   // 哨兵暂存环的头结点用于链接它的下一个节点
    p := r
   // 创建剩下的 n-1个结点（头结点也是其中一个）
    for i := 1; i < n; i++ {
   // 创建p的下一个节点同时将p节点的指针存入它的下一个节点的前驱节点
        p.next = &Ring{prev: p}
   // 继续创建p.next的下一个节点
        p = p.next
    }
    // 到这里 p 是环的最后一个节点了
    // 所以这里将环的最后一个节点跟环的头结点串了起来，然后返回了环的头结点
    p.next = r
    r.prev = p
    // 其实这里已经完全是一个环了根本就没有头结点之说,因为可以通
    // 过环中的任何一个节点都可以访问整个环的所有节点
    // 不过我这里将第一创建的结点称为头结点
    return r
}

3、Do函数(`func (r *Ring) Do(f func(interface{}))`)：从r元素开始对环上的每个元素的值执行`f`函数

// Do calls function f on each element of the ring, in forward order.
// The behavior of Do is undefined if f changes *r.
func (r *Ring) Do(f func(interface{})) {
    // 从r结点开始对整个环的所有元素执行f函数操作 
    if r != nil {
        f(r.Value)
        for p := r.Next(); p != r; p = p.next {
            f(p.Value)
        }
    }
}

4、Len函数(`func (r *Ring) Len() int`)：获取环的元素个数

// Len computes the number of elements in ring r.
// It executes in time proportional to the number of elements.
//
func (r *Ring) Len() int {
    n := 0
    // 跟Do操作相同，不过这里是通过n统计所有元素个数
    if r != nil {
        n = 1
        for p := r.Next(); p != r; p = p.next {
            n++
        }
    }
    return n
}

5、Link函数(`func (r Ring) Link(s Ring) *Ring`)：链接两个环为一个环

func (r *Ring) Link(s *Ring) *Ring {
    n := r.Next()
    if s != nil {
        p := s.Prev()
        // Note: Cannot use multiple assignment because
        // evaluation order of LHS is not specified.
        r.next = s
        s.prev = r
        n.prev = p
        p.next = n
    }
    return n
}

Link的过程如下图所示：假设有两个Ring(头尾也是相连的我这里没有表示出来)

r：1 <--> 2 <--> 3 <--> 4

s：5 <--> 6 <--> 7 <--> 8

Link之后：1 <--> 5 <--> 6 <--> 7 <--> 8 <--> 2 <--> 3 <--> 4

Link过程

6、Move函数(`func (r Ring) Move(n int) Ring`)：r指针从环的r元素位置向前或向后移动n个位置，整个环保持不变

// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
// in the ring and returns that ring element. r must not be empty.
//
func (r *Ring) Move(n int) *Ring {
    if r.next == nil {
        return r.init()
    }
    // 如果小于0向前移动
    // 如果大于0向后移动 
    switch {
    case n < 0:
        for ; n < 0; n++ {
            r = r.prev
        }
    case n > 0:
        for ; n > 0; n-- {
            r = r.next
        }
    }
    return r
}

注意这里的移动并不是将节点元素移动，而是当前指针指向环元素的指针的移动

假设有一个环： 1 <--> 2 <--> 3 <--> 4
当前r指向想1这个结点：此时使用Do函数打印元素值的话是这样的
1 -> 2 -> 3 -> 4
现在Move 2 个位置则r会处于r'的位置,再用Do函数打印环的元素：
3 -> 4 -> 1 -> 2

Move示意图

7、UnLink函数(`func (r Ring) Unlink(n int) Ring`)：Link的逆过程，更确切的说是删除从r开始的n个元素

// Unlink removes n % r.Len() elements from the ring r, starting
// at r.Next(). If n % r.Len() == 0, r remains unchanged.
// The result is the removed subring. r must not be empty.
//
func (r *Ring) Unlink(n int) *Ring {
    if n <= 0 {
        return nil
    }
    return r.Link(r.Move(n + 1))
}

这个函数内部代码很简洁，用了Link跟Move方式实现了删除操作；这里的实现方式有一定的技巧
假设有r的环为：1 <--> 2 <--> 3 <--> 4
假设这里需要Unlink2个节点
内部Move(2+1)之后的环为：4 <--> 1 <--> 2 <--> 3
再次Link之后只剩下： 1 <--> 4
通过下图解释下过程

Unlink过程

其实合并之后按理来说应该是这样子的：
1 <--> 4 <--> 1 <--> 2 <--> 3 <--> 2 <--> 3 <--> 4
从上面这个链可以看出来
1 <--> 4 <--> 1形成了一个环
2 <--> 3 <--> 2形成了一个环
因为r指向的是节点1所以最后只保存下来了1 <--> 4这个环，如果在Unlink前保存了2或者3节点则另外一个环也能够访问

8、Next函数(`func (r Ring) init() Ring`)：获取r元素的一个元素（比较简单）

// 如果r为空的话初始化函数，会初始化一个只有一个元素的环，它的前驱节点跟后继节点都是指向了自己
func (r *Ring) init() *Ring {
    r.next = r
    r.prev = r
    return r
}

// Next returns the next ring element. r must not be empty.
func (r *Ring) Next() *Ring {
    if r.next == nil {
        return r.init()
    }
    return r.next

9、Prev函数(`func (r Ring) Prev() Ring`)：获取r节点的前驱节点元素

// Prev returns the previous ring element. r must not be empty.
func (r *Ring) Prev() *Ring {
    if r.next == nil {
        return r.init()
    }
    return r.prev
}

golang container/ring源码解读

而我们今天的主角也是 双向循环链表

1、现在让我们从 type Ring 这个定义看起

2、创建有n个元素的Ring对象(New(n int) *Ring)

3、Do函数(func (r *Ring) Do(f func(interface{})))：从r元素开始对环上的每个元素的值执行f函数

4、Len函数(func (r *Ring) Len() int)：获取环的元素个数

5、Link函数(func (r *Ring) Link(s *Ring) *Ring)：链接两个环为一个环