最近在看gokit的熔斷器源碼的時候看到了內(nèi)部有使用到 container/ring 的這個數(shù)據(jù)結(jié)構(gòu)；雖然大體知道這個數(shù)據(jù)結(jié)構(gòu)提供的一個常用API，也知道該怎么用；但是不知道內(nèi)部具體是怎么實現(xiàn)的。所以就看了內(nèi)部的源碼實現(xiàn)；在這里分享出來，有不對的地方歡迎大家指正。

在正式開始講解源碼之前先鋪墊幾個基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)知識
1、單鏈表

節(jié)點內(nèi)部會存儲當(dāng)前節(jié)點的值跟下一個節(jié)點的指針，單鏈表的訪問只能向前推進(jìn)訪問不能后退

單鏈表

2、單向循環(huán)鏈表

單向循環(huán)鏈表的尾節(jié)點的后繼節(jié)點指向了鏈表的頭結(jié)點；其他跟單鏈表完全相同

單向循環(huán)鏈表

3、雙向鏈表

雙向鏈表每個節(jié)點內(nèi)部存儲了當(dāng)前節(jié)點的值，后繼節(jié)點的指針，前驅(qū)節(jié)點的指針

雙向鏈表

4、雙向循環(huán)鏈表

雙向循環(huán)鏈表的頭結(jié)點的前驅(qū)節(jié)點為鏈表的尾節(jié)點指針，而尾結(jié)點的后繼節(jié)點為頭結(jié)點的指針，其他跟雙向鏈表完全相同

雙向循環(huán)鏈表

而我們今天的主角也是 雙向循環(huán)鏈表

• 首先看下暴露出來的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、現(xiàn)在讓我們從 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是一個由多個元素節(jié)點組成的環(huán)形的鏈表，或者是一個環(huán)；組成這樣一個環(huán)的每個元素都由三個字段組成

• next：后繼節(jié)點指針
• prev：前驅(qū)節(jié)點指針
• Value：存節(jié)點元素的值

2、創(chuàng)建有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
    }
   // 創(chuàng)建環(huán)的頭結(jié)點
    r := new(Ring)
   // 哨兵暫存環(huán)的頭結(jié)點用于鏈接它的下一個節(jié)點
    p := r
   // 創(chuàng)建剩下的 n-1個結(jié)點（頭結(jié)點也是其中一個）
    for i := 1; i < n; i++ {
   // 創(chuàng)建p的下一個節(jié)點同時將p節(jié)點的指針存入它的下一個節(jié)點的前驅(qū)節(jié)點
        p.next = &Ring{prev: p}
   // 繼續(xù)創(chuàng)建p.next的下一個節(jié)點
        p = p.next
    }
    // 到這里 p 是環(huán)的最后一個節(jié)點了
    // 所以這里將環(huán)的最后一個節(jié)點跟環(huán)的頭結(jié)點串了起來，然后返回了環(huán)的頭結(jié)點
    p.next = r
    r.prev = p
    // 其實這里已經(jīng)完全是一個環(huán)了根本就沒有頭結(jié)點之說,因為可以通
    // 過環(huán)中的任何一個節(jié)點都可以訪問整個環(huán)的所有節(jié)點
    // 不過我這里將第一創(chuàng)建的結(jié)點稱為頭結(jié)點
    return r
}

3、Do函數(shù)(func (r *Ring) Do(f func(interface{})))：從r元素開始對環(huán)上的每個元素的值執(zhí)行f函數(shù)

// 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結(jié)點開始對整個環(huán)的所有元素執(zhí)行f函數(shù)操作 
    if r != nil {
        f(r.Value)
        for p := r.Next(); p != r; p = p.next {
            f(p.Value)
        }
    }
}

4、Len函數(shù)(func (r *Ring) Len() int)：獲取環(huán)的元素個數(shù)

// 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統(tǒng)計所有元素個數(shù)
    if r != nil {
        n = 1
        for p := r.Next(); p != r; p = p.next {
            n++
        }
    }
    return n
}

5、Link函數(shù)(func (r *Ring) Link(s *Ring) *Ring)：鏈接兩個環(huán)為一個環(huán)

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的過程如下圖所示：假設(shè)有兩個Ring(頭尾也是相連的我這里沒有表示出來)

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

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

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

Link過程

6、Move函數(shù)(func (r *Ring) Move(n int) *Ring)：r指針從環(huán)的r元素位置向前或向后移動n個位置，整個環(huá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
}

注意這里的移動并不是將節(jié)點元素移動，而是當(dāng)前指針指向環(huán)元素的指針的移動

假設(shè)有一個環(huán)： 1 <--> 2 <--> 3 <--> 4
當(dāng)前r指向想1這個結(jié)點：此時使用Do函數(shù)打印元素值的話是這樣的
1 -> 2 -> 3 -> 4
現(xiàn)在Move 2 個位置則r會處于r'的位置,再用Do函數(shù)打印環(huán)的元素：
3 -> 4 -> 1 -> 2

Move示意圖

7、UnLink函數(shù)(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))
}

這個函數(shù)內(nèi)部代碼很簡潔，用了Link跟Move方式實現(xiàn)了刪除操作；這里的實現(xiàn)方式有一定的技巧
假設(shè)有r的環(huán)為：1 <--> 2 <--> 3 <--> 4
假設(shè)這里需要Unlink2個節(jié)點
內(nèi)部Move(2+1)之后的環(huán)為：4 <--> 1 <--> 2 <--> 3
再次Link之后只剩下： 1 <--> 4
通過下圖解釋下過程

Unlink過程

其實合并之后按理來說應(yīng)該是這樣子的：
1 <--> 4 <--> 1 <--> 2 <--> 3 <--> 2 <--> 3 <--> 4
從上面這個鏈可以看出來
1 <--> 4 <--> 1形成了一個環(huán)
2 <--> 3 <--> 2形成了一個環(huán)
因為r指向的是節(jié)點1所以最后只保存下來了1 <--> 4這個環(huán)，如果在Unlink前保存了2或者3節(jié)點則另外一個環(huán)也能夠訪問

8、Next函數(shù)(func (r *Ring) init() *Ring)：獲取r元素的一個元素（比較簡單）

// 如果r為空的話初始化函數(shù)，會初始化一個只有一個元素的環(huán)，它的前驅(qū)節(jié)點跟后繼節(jié)點都是指向了自己
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函數(shù)(func (r *Ring) Prev() *Ring)：獲取r節(jié)點的前驅(qū)節(jié)點元素

// 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
}