您的位置 首页 golang

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源码解读

文章地址:https://www.zhihuclub.com/1338.shtml

关于作者: 智云科技

热门文章

发表评论

您的电子邮箱地址不会被公开。

网站地图