go源码解读-ring

发表于 | 分类于 ，

ring

  • ring为环结构，没有开始和结束
  • 本质是双向链表
  • 空ring的next和prev都指向自己

ring结构体

  • Ring结构体包含三个参数
    • next 指向当前节点的下一个节点
    • prev 指向当前节点的上一个节点
    • Value 当前节点的值
  • New方法为创建一个包含n个元素的ring的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type Ring struct {
	next, prev *Ring
	Value      interface{} // for use by client; untouched by this library
}
// New creates a ring of n elements.
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
}

Ring结构体的方法

  • init为初始一个0个节点的Ring结构体的方法
  • Next返回当前节点的下一个节点
  • Prev返回当前节点的上一个节点
  • Move将当前节点移动n个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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
}
// 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
}
// 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()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

链接操作

  • Link 将s和r链接到一起，返回r.next
    • s和r在一个圆环里，操作会将r和s之间的元素移除到圆环
    • s和r不在一个圆环里，操作会将r和s合并成一个圆环
  • Unlink移除n%r.len个元素，本质上是对Link方法的封装
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
}
// 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))
}

Len和Do方法

  • Len方法返回圆环的长度
  • Do方法的参数为一个函数f，对于圆环上的每个元素的值，执行该函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		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.
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)
		}
	}
}
Donate comment here