go中的ring實(shí)現(xiàn)了環(huán)形雙向鏈表

源碼解析

// 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.
// 鏈表節(jié)點(diǎn)結(jié)構(gòu)至会，包括前后項(xiàng)指針和節(jié)點(diǎn)值
type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

// 初始化
// 注意這里沒有初始化Value，此時(shí)Value == nil
func (r *Ring) init() *Ring {
    r.next = r
    r.prev = r
    return r
}

// Next returns the next ring element. r must not be empty.
// 獲取后項(xiàng)節(jié)點(diǎn)
// 這里會(huì)判斷r是否初始化過，始終會(huì)保證返回的*Ring不為nil
func (r *Ring) Next() *Ring {
    if r.next == nil {
        return r.init()
    }
    return r.next
}

// Prev returns the previous ring element. r must not be empty.
// 獲取前項(xiàng)節(jié)點(diǎn)
// 這里會(huì)判斷r是否初始化過扼脐，始終會(huì)保證返回的*Ring不為nil
func (r *Ring) Prev() *Ring {
    if r.next == nil {
        return r.init()
    }
    return r.prev
}

// 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.
// 獲取向前/向后的第x個(gè)節(jié)點(diǎn)肠仪，其中x = n % r.Len()
func (r *Ring) Move(n int) *Ring {
    // 如果r沒有初始化則初始化肖抱，且對(duì)于只有一個(gè)節(jié)點(diǎn)的環(huán)鏈表，前后第x個(gè)節(jié)點(diǎn)都是自己
    if r.next == nil {
        return r.init()
    }
    switch {
    // n < 0 表示向前
    case n < 0:
        for ; n < 0; n++ {
            r = r.prev
        }
    // n > 0 表示向后
    case n > 0:
        for ; n > 0; n-- {
            r = r.next
        }
    }
    return r
}

// New creates a ring of n elements.
// 構(gòu)建包含n個(gè)節(jié)點(diǎn)的環(huán)鏈表
// 注意新建后的所有節(jié)點(diǎn)的Value == nil
func New(n int) *Ring {
    if n <= 0 {
        return nil
    }
    r := new(Ring)
    p := r
    for i := 1; i < n; i++ {
        p.next = &Ring{prev: p}
        p = p.next
    }
    p.next = r
    r.prev = p
    return r
}

// Link connects ring r with ring s such that r.Next()
// becomes s and returns the original value for r.Next().
// r must not be empty.
//
// If r and s point to the same ring, linking
// them removes the elements between r and s from the ring.
// The removed elements form a subring and the result is a
// reference to that subring (if no elements were removed,
// the result is still the original value for r.Next(),
// and not nil).
//
// If r and s point to different rings, linking
// them creates a single ring with the elements of s inserted
// after r. The result points to the element following the
// last element of s after insertion.
// 連接兩個(gè)環(huán)
// 如果是同一個(gè)環(huán)异旧，則可能會(huì)刪除部分節(jié)點(diǎn)
func (r *Ring) Link(s *Ring) *Ring {
    // 獲取r的后項(xiàng)節(jié)點(diǎn)意述，這里會(huì)檢查是否初始化
    n := r.Next()
    if s != nil {
        // 獲得s的前項(xiàng)節(jié)點(diǎn)，這里會(huì)檢查是否初始化
        p := s.Prev()
        // Note: Cannot use multiple assignment because
        // evaluation order of LHS is not specified.
        // 切掉r和r.next的連接吮蛹，讓r和s連接上
        r.next = s
        // 切掉s和s.prev的連接荤崇，讓s和r連接上
        s.prev = r
        // 讓r的后項(xiàng)節(jié)點(diǎn)和s的前項(xiàng)節(jié)點(diǎn)連接上
        // 這里如果r和s是同一個(gè)環(huán)鏈接的話，r和s中間的所有節(jié)點(diǎn)都會(huì)被切掉
        // 如果r和s是同一節(jié)點(diǎn)潮针，那么最后就只剩r一個(gè)節(jié)點(diǎn)了
        n.prev = p
        p.next = n
    }
    return 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.
// 刪除自r為起點(diǎn)后的x個(gè)節(jié)點(diǎn)术荤，其中x = n % r.Len()
func (r *Ring) Unlink(n int) *Ring {
    if n <= 0 {
        return nil
    }
    // 注意這里需要n+1，因?yàn)長ink刪除的是節(jié)點(diǎn)r 和 節(jié)點(diǎn)r+n+1之間的所有節(jié)點(diǎn)每篷，也就是 r+n+1 - r - 1 = n 個(gè)節(jié)點(diǎn)
    return r.Link(r.Move(n + 1))
}

// Len computes the number of elements in ring r.
// It executes in time proportional to the number of elements.
// 獲取環(huán)鏈表的長度
func (r *Ring) Len() int {
    n := 0
    if r != nil {
        n = 1
        // 注意這里只能通過p != r來判斷是否遍歷結(jié)束瓣戚，因?yàn)槭黔h(huán)形的
        for p := r.Next(); p != r; p = p.next {
            n++
        }
    }
    return n
}

// Do calls function f on each element of the ring, in forward order.
// The behavior of Do is undefined if f changes *r.
// 遍歷所有節(jié)點(diǎn)，并使用Value作為參數(shù)執(zhí)行f方法
// 注意該方法中涉及到遍歷環(huán)鏈表焦读，如果f方法對(duì)環(huán)鏈表進(jìn)行了變更子库，后果將是不可預(yù)期的
func (r *Ring) Do(f func(interface{})) {
    if r != nil {
        f(r.Value)
        for p := r.Next(); p != r; p = p.next {
            f(p.Value)
        }
    }
}

舉個(gè)栗子

func p(r *ring.Ring) {
    if r == nil {
        fmt.Println("nil")
        return
    }

    fmt.Printf("%d ->", r.Value.(int))
    p := r.Next()
    for ; p != r; p = p.Next() {
        fmt.Printf("%d ->", p.Value.(int))
    }
    fmt.Println("")
}

func main() {
    r := ring.New(5)
    n := r.Len()

    for i := 0; i < n; i++ {
        r.Value = i
        r = r.Next()
    }
    p(r) // 0 ->1 ->2 ->3 ->4 ->
    r = r.Move(2)
    p(r) // 2 ->3 ->4 ->0 ->1 ->
    r = r.Move(-1)
    p(r) // 1 ->2 ->3 ->4 ->0 ->
    r1 := r.Move(3)
    p(r1) // 4 ->0 ->1 ->2 ->3 ->
    r.Link(r1)
    p(r) // 1 ->4 ->0 ->
    r.Unlink(1)
    p(r) // 1 ->0 ->

    // 因?yàn)檎{(diào)用了r.Unlink(1)，只輸出了1
    // 方法中切記謹(jǐn)慎操作r矗晃，可能導(dǎo)致死循環(huán)等意外的結(jié)果   
    r.Do(func(i interface{}) {
        fmt.Println(i.(int))  // 1
        r.Unlink(1)
    })
}

總結(jié)

別的不說仑嗅，Link方法可謂精妙，包含了向后插入新節(jié)點(diǎn)、合并兩個(gè)環(huán)形鏈表和刪除鏈表部分節(jié)點(diǎn)三個(gè)功能无畔，而且結(jié)合Prev方法也能做到向前插入節(jié)點(diǎn)啊楚，唯一不過癮的地方就是沒法像list那樣，插入節(jié)點(diǎn)的同時(shí)進(jìn)行Value的初始化浑彰，只能自己先初始化Ring節(jié)點(diǎn)恭理，使用場(chǎng)景上，ring可以作為可覆蓋的熱緩存使用郭变，比如存儲(chǔ)最新的N個(gè)訂單颜价，類似innodb的redo log