// Acyclic tells if g has no cycles.
10454
func Acyclic(g Iterator) bool {
	_, acyclic := topsort(g, false)
	return acyclic
}
837886
func (p Properties) CCC() uint8 {
	if p.index >= firstCCCZeroExcept {
		return 0
	}
	return ccc[p.ccc]
}
577599
func Cycle(n int) *Virtual {
	switch {
	case n < 0:
		return nil
	case n == 0:
		return null
	case n == 1:
		return singleton()
	case n == 2:
		return edge()
	}

	g := generic0(n, func(v, w int) (edge bool) {
		switch v - w {
		case 1 - n, -1, 1, n - 1:
			edge = true
		}
		return
	})

	// Precondition : n ≥ 3.
	g.degree = func(v int) int { return 2 }

	// Precondition : n ≥ 3.
	g.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
		var w [2]int
		switch v {
		case 0:
			w = [2]int{1, n - 1}
		case n - 1:
			w = [2]int{0, n - 2}
		default:
			w = [2]int{v - 1, v + 1}
		}
		for _, w := range w {
			if w >= a && do(w, 0) {
				return true
			}
		}
		return
	}
	return g
}
173486
func (pder *MemProvider) SessionGC() {
	pder.lock.RLock()
	for {
		element := pder.list.Back()
		if element == nil {
			break
		}
		if (element.Value.(*MemSessionStore).timeAccessed.Unix() + pder.maxlifetime) < time.Now().Unix() {
			pder.lock.RUnlock()
			pder.lock.Lock()
			pder.list.Remove(element)
			delete(pder.sessions, element.Value.(*MemSessionStore).sid)
			pder.lock.Unlock()
			pder.lock.RLock()
		} else {
			break
		}
	}
	pder.lock.RUnlock()
}
456686
func (vm *Engine) curPC() (script int, off int, err error) {
	err = vm.validPC()
	if err != nil {
		return 0, 0, err
	}
	return vm.scriptIdx, vm.scriptOff, nil
}
602921
func (cfg *Config) WithoutWheels() *Config {
	if !cfg.HasWheels() {
		return cfg
	}

	clone := *cfg
	clone.OverrideName = ""
	clone.Spec = clone.Spec.Clone()
	clone.Spec.Wheel = nil
	return &clone
}
21889
func (c C) GCD(val Input) Input {
	if v, ok := val.(C); ok {
		return C(gcd(float32(c), float32(v)))
	}
	return val.GCD(c)
}
229654
func LifecycleCtx(mctx MetricsCtx, lc fx.Lifecycle) context.Context {
	ctx, cancel := context.WithCancel(mctx)
	lc.Append(fx.Hook{
		OnStop: func(_ context.Context) error {
			cancel()
			return nil
		},
	})
	return ctx
}
685561
func (s *fsCacheStore) GC() error {
	s.mu.Lock()
	defer s.mu.Unlock()
	var size uint64

	ctx := context.Background()
	cutoff := time.Now().Add(-s.gcPolicy.MaxKeepDuration)
	var blacklist []*cachedSource

	for id, snap := range s.sources {
		if len(snap.refs) == 0 {
			if cutoff.After(snap.CachePolicy.LastUsed) {
				if err := s.delete(id); err != nil {
					return errors.Wrapf(err, "failed to delete %s", id)
				}
			} else {
				ss, err := snap.getSize(ctx)
				if err != nil {
					return err
				}
				size += uint64(ss)
				blacklist = append(blacklist, snap)
			}
		}
	}

	sort.Sort(sortableCacheSources(blacklist))
	for _, snap := range blacklist {
		if size <= s.gcPolicy.MaxSize {
			break
		}
		ss, err := snap.getSize(ctx)
		if err != nil {
			return err
		}
		if err := s.delete(snap.id); err != nil {
			return errors.Wrapf(err, "failed to delete %s", snap.id)
		}
		size -= uint64(ss)
	}
	return nil
}
1326401
func (w *GCWorker) prepare() (bool, uint64, error) {
	// Add a transaction here is to prevent following situations:
	// 1. GC check gcEnable is true, continue to do GC
	// 2. The user sets gcEnable to false
	// 3. The user gets `tikv_gc_safe_point` value is t1, then the user thinks the data after time t1 won't be clean by GC.
	// 4. GC update `tikv_gc_safe_point` value to t2, continue do GC in this round.
	// Then the data record that has been dropped between time t1 and t2, will be cleaned by GC, but the user thinks the data after t1 won't be clean by GC.
	ctx := context.Background()
	_, err := w.session.Execute(ctx, "BEGIN")
	if err != nil {
		return false, 0, errors.Trace(err)
	}
	doGC, safePoint, err := w.checkPrepare(ctx)
	if doGC {
		_, err = w.session.Execute(ctx, "COMMIT")
		if err != nil {
			return false, 0, errors.Trace(err)
		}
	} else {
		_, err1 := w.session.Execute(ctx, "ROLLBACK")
		terror.Log(errors.Trace(err1))
	}
	return doGC, safePoint, errors.Trace(err)
}
641753
func (mab *memoryAddrBook) gc() {
	mab.addrmu.Lock()
	defer mab.addrmu.Unlock()

	now := time.Now()
	for p, amap := range mab.addrs {
		for k, addr := range amap {
			if addr.ExpiredBy(now) {
				delete(amap, k)
			}
		}
		if len(amap) == 0 {
			delete(mab.addrs, p)
		}
	}
}
642682
func (s *Simple) GC() {
	// Bail if another GC thread is already running. This may happen
	// automatically when GCPeriodicity is shorter than GCTimeout, or when user
	// manually invokes GC method.
	if !atomic.CompareAndSwapInt32(&s.gcFlag, 0, 1) {
		return
	}
	defer atomic.StoreInt32(&s.gcFlag, 0)

	// MARK PHASE
	s.lock.RLock()

	// Create asynchronous goroutines to collect each key-value pair
	// individually, so overall mark phase task does not block waiting for any
	// of the key locks.  We use a channel to collect key-value pair results in
	// order to serialize the parallel collection of pairs.

	// Ultimately, however, we do not desire to spend more than a specified
	// duration of time collecting key-value pairs during the mark phase, so a
	// context is created with a deadline to allow for early termination of the
	// mark phase. This logic does allow some key-value pairs to remain expired
	// after their eviction time, but with a long enough GCTimeout it is likely
	// that those evicted key-value pairs will be eventually collected during a
	// future GC run.

	// Although context.WithTimeout or context.WithDeadline _could_ be used
	// below, we do not desire to require Go 1.7 or above when a simple
	// time.Timer channel will do the job.
	now := time.Now()
	timeoutC := time.After(s.config.GCTimeout)

	// Create a buffered channel large enough to receive all key-value pairs so
	// that in the event of early mark phase termination due to timeout, the
	// goroutines created below will not block on sending to a full channel that
	// is no longer consumed after mark phase has ended.
	totalCount := len(s.data)
	allPairs := make(chan gcPair, totalCount)

	// Loop through all existing key-value pairs in the cache, creating
	// goroutines for each pair to individually wait for the respective key
	// lock, test the eviction logic, and send the result to the results
	// channel.
	for key, atv := range s.data {
		go func(key string, atv *atomicTimedValue, allPairs chan<- gcPair) {
			if av := atv.av.Load(); av != nil {
				allPairs <- gcPair{
					key:    key,
					doomed: av.(*TimedValue).IsExpiredAt(now),
				}
			}
		}(key, atv, allPairs)
	}

	// After looping through all key-value pairs, we no longer need to hold the
	// read lock for the cache while waiting for the results to arrive.
	s.lock.RUnlock()

	// COLLECT PHASE: Spawn goroutine to collect locked key-value pairs.
	var doomed []string
	var receivedCount int
loop:
	for {
		select {
		case <-timeoutC:
			// The above channel is closed when either the timeout has expired
			// or when the number of received pairs equals the number of
			// key-value pairs in the cache, done manually below by calling
			// `cancel()`.
			break loop
		case pair := <-allPairs:
			if pair.doomed {
				doomed = append(doomed, pair.key)
			}
			// Once all key-value pairs have been received we can terminate the
			// collection phase.
			if receivedCount++; receivedCount == totalCount {
				break loop
			}
		}
	}

	// SWEEP PHASE: Grab the write lock and delete all doomed key-value pairs
	// from the cache.
	s.lock.Lock()
	for _, key := range doomed {
		delete(s.data, key)
	}
	atomic.AddInt64(&s.stats.Evictions, int64(len(doomed)))
	s.lock.Unlock()
}
1204770
func RunGCSCLI(gcsCLIPath, configPath, subcommand string,
	args ...string) (*gexec.Session, error) {

	cmdArgs := []string{
		"-c",
		configPath,
		subcommand,
	}
	cmdArgs = append(cmdArgs, args...)

	command := exec.Command(gcsCLIPath, cmdArgs...)
	gexecSession, err := gexec.Start(command,
		ginkgo.GinkgoWriter, ginkgo.GinkgoWriter)
	if err != nil {
		return nil, err
	}
	gexecSession.Wait(1 * time.Minute)

	return gexecSession, nil
}
242149
func (c KBFSGitClient) Gc(ctx context.Context, __arg GcArg) (err error) {
	err = c.Cli.Call(ctx, "keybase.1.KBFSGit.gc", []interface{}{__arg}, nil)
	return
}
568503
func TraceCubic(t Liner, cubic []float64, flatteningThreshold float64) {
	// Allocation curves
	var curves [CurveRecursionLimit * 8]float64
	copy(curves[0:8], cubic[0:8])
	i := 0

	// current curve
	var c []float64

	var dx, dy, d2, d3 float64

	for i >= 0 {
		c = curves[i*8:]
		dx = c[6] - c[0]
		dy = c[7] - c[1]

		d2 = math.Abs((c[2]-c[6])*dy - (c[3]-c[7])*dx)
		d3 = math.Abs((c[4]-c[6])*dy - (c[5]-c[7])*dx)

		// if it's flat then trace a line
		if (d2+d3)*(d2+d3) < flatteningThreshold*(dx*dx+dy*dy) || i == len(curves)-1 {
			t.LineTo(c[6], c[7])
			i--
		} else {
			// second half of bezier go lower onto the stack
			SubdivideCubic(c, curves[(i+1)*8:], curves[i*8:])
			i++
		}
	}
}
1015750
func ManualGC() {
	go gcOnce.Do(func() {
		tick := time.Tick(2 * time.Minute)
		for {
			<-tick
			var mem runtime.MemStats
			runtime.ReadMemStats(&mem)
			if mem.HeapReleased >= GC_SIZE {
				debug.FreeOSMemory()
				// runtime.GC()
			}
		}
	})
}
1062928
func CheckGCEnable(ctx sessionctx.Context) (enable bool, err error) {
	sql := fmt.Sprintf(selectVariableValueSQL, "tikv_gc_enable")
	rows, _, err := ctx.(sqlexec.RestrictedSQLExecutor).ExecRestrictedSQL(ctx, sql)
	if err != nil {
		return false, errors.Trace(err)
	}
	if len(rows) != 1 {
		return false, errors.New("can not get 'tikv_gc_enable'")
	}
	return rows[0].GetString(0) == "true", nil
}