最近在看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}

给这篇文章的作者打赏

微信扫一扫打赏

支付宝扫一扫打赏

×

打赏 点赞(1)