四叉堆在GO中的应用-定时任务timer

// 新建一个ticker，定设置周期为1秒
ticker := time.NewTicker(time.Second * 3)
// 在一个协程接收ticker的channel回调
go func() {
	for {
		", time.Now().String())
	}
}()
time.Sleep(time.Hour)

……
tick--> 2023-10-08 21:01:30.1830277 +0800 CST m=+3.009288301
tick--> 2023-10-08 21:01:33.1811243 +0800 CST m=+6.007384901
tick--> 2023-10-08 21:01:36.179331 +0800 CST m=+9.005591601
……

type Ticker struct {
	C 

func NewTicker(d Duration) *Ticker {
	if d 

// startTimer adds t to the timer heap.
//
//go:linkname startTimer time.startTimer
func startTimer(t *timer) {
	if raceenabled {
		racerelease(unsafe.Pointer(t))
	}
	addtimer(t)
}

// Note: this changes some unsynchronized operations to synchronized operations
// addtimer adds a timer to the current P.
// This should only be called with a newly created timer.
// That avoids the risk of changing the when field of a timer in some P's heap,
// which could cause the heap to become unsorted.
func addtimer(t *timer) {
	// when must be positive. A negative value will cause runtimer to
	// overflow during its delta calculation and never expire other runtime
	// timers. Zero will cause checkTimers to fail to notice the timer.
	if t.when 

// doaddtimer adds t to the current P's heap.
// The caller must have locked the timers for pp.
func doaddtimer(pp *p, t *timer) {
	// Timers rely on the network poller, so make sure the poller
	// has started.
	if netpollInited.Load() == 0 {
	    // netpool如未初始化则进行初始化
		netpollGenericInit()
	}

	if t.pp != 0 {
		throw("doaddtimer: P already set in timer")
	}
	// 给timer绑定p
	t.pp.set(pp)
	i := len(pp.timers)
	// 将此timer添加到p的timer集合中，放到堆的末尾
	pp.timers = append(pp.timers, t)
	// 堆内新增了元素，进行上推操作在保持堆的特性
	siftupTimer(pp.timers, i)
	if t == pp.timers[0] {
		pp.timer0When.Store(t.when)
	}
	// p的timer计数器加1
	pp.numTimers.Add(1)
}

func siftupTimer(t []*timer, i int) int {
	// 判断新增元素的正确性
	if i >= len(t) {
		badTimer()
	}
	// 获取出新增元素的具体运行时间
	when := t[i].when
	if when  0 {
	    // 获取出新增元素的父节点索引，四叉堆时父节点索引为(i-1)/4
		p := (i - 1) / 4 // parent
		if when >= t[p].when {
		    // 新增元素的运行时间晚于父节点，则无需继续siftup
			break
		}
		// 将原父节点位置往下降一级
		t[i] = t[p]
		// 新增元素的位置往上提升一级
		i = p
	}
	if tmp != t[i] {
	    // 新增元素的值在最后确定了位置后才赋值，而不是每次都进行交换
		t[i] = tmp
	}
	return i
}

func runtimer(pp *p, now int64) int64 {
	for {
	    // 获取出当前p的堆顶timer
		t := pp.timers[0]
		if t.pp.ptr() != pp {
			throw("runtimer: bad p")
		}
		// 对堆顶timer的状态进行判断
		switch s := t.status.Load(); s {
		case timerWaiting:
			if t.when > now {
				// Not ready to run.
				return t.wh服务器托管网en
			}

			if !t.status.CompareAndSwap(s, timerRunning) {
			    // 已在运行，不重复运行
				continue
			}
			// Note that runOneTimer may temporarily unlock
			// pp.timersLock.
			runOneTimer(pp, t, now)
			return 0

		case timerDeleted:
			if !t.status.CompareAndSwap(s, timerRemoving) {
				continue
			}
			dodeltimer0(pp)
			if !t.status.CompareAndSwap(timerRemoving, timerRemoved) {
				badTimer()
			}
			pp.deletedTimers.Add(-1)
			if len(pp.timers) == 0 {
				return -1
			}

		case timerModifiedEarlier, timerModifiedLater:
			if !t.status.CompareAndSwap(s, timerMoving) {
				continue
			}
			t.when = t.nextwhen
			dodeltimer0(pp)
			doaddtimer(pp, t)
			if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
				badTimer()
			}

		case timerModifying:
			// Wait for modification to complete.
			osyield()

		case timerNoStatus, timerRemoved:
			// Should not see a new or inactive timer on the heap.
			badTimer()
		case timerRunning, timerRemoving, timerMoving:
			// These should only be set when timers are locked,
			// and we didn't do it.
			badTimer()
		default:
			badTimer()
		}
	}
}

// runOneTimer runs a single timer.
// The caller must have locked the timers for pp.
// This will temporarily unlock the timers while running the timer function.
//
//go:systemstack
func runOneTimer(pp *p, t *timer, now int64) {
	if raceenabled {
		ppcur := getg().m.p.ptr()
		if ppcur.timerRaceCtx == 0 {
			ppcur.timerRaceCtx = racegostart(abi.FuncPCABIInternal(runtimer) + sys.PCQuantum)
		}
		raceacquirectx(ppcur.timerRaceCtx, unsafe.Po服务器托管网inter(t))
	}
    
    // 取出timer中的function和参数
	f := t.f
	arg := t.arg
	seq := t.seq

	if t.period > 0 {
	    // tick类型的timer，以实际运行时间和固定周期计算出下次运行时间
		// Leave in heap but adjust next time to fire.
		delta := t.when - now
		t.when += t.period * (1 + -delta/t.period)
		if t.when 

// siftdownTimer puts the timer at position i in the right place
// in the heap by moving it down toward the bottom of the heap.
func siftdownTimer(t []*timer, i int) {
	n := len(t)
	if i >= n {
		badTimer()
	}
	// 获取出要调整节点的执行时间
	when := t[i].when
	if when = n {
			break
		}
		// 最左子节点的下次执行时间
		w := t[c].when
		// 左边第2个节点的执行时间比最左子节点执行时间更先执行
		if c+1 = when {
		    // 堆已调整完毕
			break
		}
		// 将最左的子节点向上升一级
		t[i] = t[c]
		// 原i向下降一级
		i = c
	}
	if tmp != t[i] {
	    // 将siftdown节点调整到最终确定的位置
		t[i] = tmp
	}
}

// dodeltimer0 removes timer 0 from the current P's heap.
// We are locked on the P when this is called.
// It reports whether it saw no problems due to races.
// The caller must have locked the timers for pp.
func dodeltimer0(pp *p) {
	if t := pp.timers[0]; t.pp.ptr() != pp {
		throw("dodeltimer0: wrong P")
	} else {
		t.pp = 0
	}
	// 获取到堆中的最后一个节点
	last := len(pp.timers) - 1
	if last > 0 {
	    // 最后一个节点放到堆顶
		pp.timers[0] = pp.timers[last]
	}
	// 删除堆中的原末尾节点
	pp.timers[last] = nil
	pp.timers = pp.timers[:last]
	if last > 0 {
	    // 对放到堆顶的原末尾节点进行siftdown操作
		siftdownTimer(pp.timers, 0)
	}
	// 更新timer集合
	updateTimer0When(pp)
	n := pp.numTimers.Add(-1)
	if n == 0 {
		// If there are no timers, then clearly none are modified.
		pp.timerModifiedEarliest.Store(0)
	}
}