// Heap maintenance algorithms.
359964
func siftupTimer(i int) {
	t := timers.t
	when := t[i].when
	tmp := t[i]
	for i > 0 {
		p := (i - 1) / 4 // parent
		if when >= t[p].when {
			break
		}
		t[i] = t[p]
		t[i].i = i
		t[p] = tmp
		t[p].i = p
		i = p
	}
}
923562
func (ms *AggMetrics) GC() {
	for {
		unix := time.Duration(time.Now().UnixNano())
		diff := ms.gcInterval - (unix % ms.gcInterval)
		time.Sleep(diff + time.Minute)
		log.Info("checking for stale chunks that need persisting.")
		now := uint32(time.Now().Unix())
		chunkMinTs := now - uint32(ms.chunkMaxStale)
		metricMinTs := now - uint32(ms.metricMaxStale)

		// as this is the only goroutine that can delete from ms.Metrics
		// we only need to lock long enough to get the list of orgs, then for each org
		// get the list of active metrics.
		// It doesn't matter if new orgs or metrics are added while we iterate these lists.
		ms.RLock()
		orgs := make([]uint32, 0, len(ms.Metrics))
		for o := range ms.Metrics {
			orgs = append(orgs, o)
		}
		ms.RUnlock()
		for _, org := range orgs {
			orgActiveMetrics := promActiveMetrics.WithLabelValues(strconv.Itoa(int(org)))
			keys := make([]schema.Key, 0, len(ms.Metrics[org]))
			ms.RLock()
			for k := range ms.Metrics[org] {
				keys = append(keys, k)
			}
			ms.RUnlock()
			for _, key := range keys {
				gcMetric.Inc()
				ms.RLock()
				a := ms.Metrics[org][key]
				ms.RUnlock()
				points, stale := a.GC(now, chunkMinTs, metricMinTs)
				if stale {
					log.Debugf("metric %s is stale. Purging data from memory.", key)
					ms.Lock()
					delete(ms.Metrics[org], key)
					orgActiveMetrics.Set(float64(len(ms.Metrics[org])))
					// note: this is racey. if a metric has just become unstale, it may have created a new chunk,
					// pruning an older one. in which case we double-subtract those points
					// hard to fix and super rare. see https://github.com/grafana/metrictank/pull/1242
					totalPoints.DecUint64(uint64(points))
					ms.Unlock()
				}
			}
			ms.RLock()
			orgActive := len(ms.Metrics[org])
			orgActiveMetrics.Set(float64(orgActive))
			ms.RUnlock()

			// If this org has no keys, then delete the org from the map
			if orgActive == 0 {
				// To prevent races, we need to check that there are still no metrics for the org while holding a write lock
				ms.Lock()
				orgActive = len(ms.Metrics[org])
				if orgActive == 0 {
					delete(ms.Metrics, org)
				}
				ms.Unlock()
			}
		}

		// Get the totalActive across all orgs.
		totalActive := 0
		ms.RLock()
		for o := range ms.Metrics {
			totalActive += len(ms.Metrics[o])
		}
		ms.RUnlock()
		metricsActive.Set(totalActive)
	}
}
770256
func heapSort_func(data lessSwap, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown_func(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown_func(data, lo, i, first)
	}
}
170062
func IndexSort(data sort.Interface) []int {
	indexes := make([]int, data.Len())
	for i := range indexes {
		indexes[i] = i
	}
	sort.Sort(InterfaceStruct{
		LenF: data.Len,
		LessF: func(i, j int) bool {
			return data.Less(indexes[i], indexes[j])
		},
		SwapF: func(i, j int) {
			indexes[i], indexes[j] = indexes[j], indexes[i]
		},
	})
	return indexes
}
760691
func runtime_Semrelease(s *uint32) {
	*s++

	w := semWaiters[s]
	if len(w) == 0 {
		return
	}

	ch := w[0]
	w = w[1:]
	semWaiters[s] = w
	if len(w) == 0 {
		delete(semWaiters, s)
	}

	ch <- true
}
1093640
func (heap *FloatingFibonacciHeap) DequeueMin() (*Entry, error) {
	if heap.IsEmpty() {
		return nil, EmptyHeapError("Cannot dequeue minimum of empty heap")
	}

	heap.size--

	// Copy pointer. Will need it later.
	min := heap.min

	if min.next == min { // This is the only root node
		heap.min = nil
	} else { // There are more root nodes
		heap.min.prev.next = heap.min.next
		heap.min.next.prev = heap.min.prev
		heap.min = heap.min.next // Arbitrary element of the root list
	}

	if min.child != nil {
		// Keep track of the first visited node
		curr := min.child
		for ok := true; ok; ok = (curr != min.child) {
			curr.parent = nil
			curr = curr.next
		}
	}

	heap.min = mergeLists(heap.min, min.child)

	if heap.min == nil {
		// If there are no entries left, we're done.
		return min, nil
	}

	treeSlice := make([]*Entry, 0, heap.size)
	toVisit := make([]*Entry, 0, heap.size)

	for curr := heap.min; len(toVisit) == 0 || toVisit[0] != curr; curr = curr.next {
		toVisit = append(toVisit, curr)
	}

	for _, curr := range toVisit {
		for {
			for curr.degree >= len(treeSlice) {
				treeSlice = append(treeSlice, nil)
			}

			if treeSlice[curr.degree] == nil {
				treeSlice[curr.degree] = curr
				break
			}

			other := treeSlice[curr.degree]
			treeSlice[curr.degree] = nil

			// Determine which of two trees has the smaller root
			var minT, maxT *Entry
			if other.Priority < curr.Priority {
				minT = other
				maxT = curr
			} else {
				minT = curr
				maxT = other
			}

			// Break max out of the root list,
			// then merge it into min's child list
			maxT.next.prev = maxT.prev
			maxT.prev.next = maxT.next

			// Make it a singleton so that we can merge it
			maxT.prev = maxT
			maxT.next = maxT
			minT.child = mergeLists(minT.child, maxT)

			// Reparent max appropriately
			maxT.parent = minT

			// Clear max's mark, since it can now lose another child
			maxT.marked = false

			// Increase min's degree. It has another child.
			minT.degree++

			// Continue merging this tree
			curr = minT
		}

		/* Update the global min based on this node.  Note that we compare
		 * for <= instead of < here.  That's because if we just did a
		 * reparent operation that merged two different trees of equal
		 * priority, we need to make sure that the min pointer points to
		 * the root-level one.
		 */
		if curr.Priority <= heap.min.Priority {
			heap.min = curr
		}
	}

	return min, nil
}
77144
func main() {
	runtime.GOMAXPROCS(8)
	server := redismq.NewServer("localhost", "6379", "", 9, "9999")
	server.Start()
	testQueue := redismq.CreateBufferedQueue("localhost", "6379", "", 9, "example", 200)
	err := testQueue.Start()
	if err != nil {
		panic(err)
	}
	go write(testQueue)

	go read(testQueue, "1")
	go read(testQueue, "2")
	go read(testQueue, "3")
	go read(testQueue, "4")
	go read(testQueue, "5")
	go read(testQueue, "6")
	go read(testQueue, "7")
	go read(testQueue, "8")

	select {}
}
768913
func (d *Debug) Heap() ([]byte, error) {
	r := d.c.newRequest("GET", "/debug/pprof/heap")
	_, resp, err := d.c.doRequest(r)
	if err != nil {
		return nil, fmt.Errorf("error making request: %s", err)
	}
	defer resp.Body.Close()

	// We return a raw response because we're just passing through a response
	// from the pprof handlers
	body, err := ioutil.ReadAll(resp.Body)
	if err != nil {
		return nil, fmt.Errorf("error decoding body: %s", err)
	}

	return body, nil
}
1182624
func (c *cache) cleanup() error {
	unused := []string{}
	now := time.Now()
	// First find old ones.
	for id, bucket := range c.buckets {
		if bucket.status == statusLoading {
			continue
		}
		if bucket.lastUsed.Add(c.ttl).Before(now) {
			unused = append(unused, id)
		}
	}
	// Now delete found ones.
	var errs []error
	for _, id := range unused {
		cacheable := c.buckets[id].cacheable
		delete(c.buckets, id)
		if err := cacheable.Discard(); err != nil {
			errs = append(errs, err)
		}
	}
	if len(errs) > 0 {
		return errors.Collect(errs...)
	}
	return nil
}
1067498
func NewHeap(keyFn KeyFunc, lessFn LessFunc) *Heap {
	h := &Heap{
		data: &heapData{
			items:    map[string]*heapItem{},
			queue:    []string{},
			keyFunc:  keyFn,
			lessFunc: lessFn,
		},
	}
	h.cond.L = &h.lock
	return h
}
611647
func (k *DistKeeper) Keep(c ComparableDist) {
	if c.Dist <= k.Heap[0].Dist {
		heap.Push(k, c)
	}
}
588528
func quickSort_func(data lessSwap, a, b, maxDepth int) {
	for b-a > 12 {
		if maxDepth == 0 {
			heapSort_func(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot_func(data, a, b)
		if mlo-a < b-mhi {
			quickSort_func(data, a, mlo, maxDepth)
			a = mhi
		} else {
			quickSort_func(data, mhi, b, maxDepth)
			b = mlo
		}
	}
	if b-a > 1 {
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort_func(data, a, b)
	}
}
178367
func ElapsedMemory() (ret string) {
	memStat := new(runtime.MemStats)
	runtime.ReadMemStats(memStat)
	ret = FormatByte(memStat.Alloc, 3)
	return
}
824069
func (s *LDBStore) Cleanup(f func(Chunk) bool) {
	var errorsFound, removed, total int

	it := s.db.NewIterator()
	defer it.Release()
	for ok := it.Seek([]byte{keyIndex}); ok; ok = it.Next() {
		key := it.Key()
		if (key == nil) || (key[0] != keyIndex) {
			break
		}
		total++
		var index dpaDBIndex
		err := decodeIndex(it.Value(), &index)
		if err != nil {
			log.Warn("Cannot decode")
			errorsFound++
			continue
		}
		hash := key[1:]
		po := s.po(hash)
		datakey := getDataKey(index.Idx, po)
		data, err := s.db.Get(datakey)
		if err != nil {
			found := false

			// The highest possible proximity is 255, so exit loop upon overflow.
			for po = uint8(1); po != 0; po++ {
				datakey = getDataKey(index.Idx, po)
				data, err = s.db.Get(datakey)
				if err == nil {
					found = true
					break
				}
			}

			if !found {
				log.Warn(fmt.Sprintf("Chunk %x found but count not be accessed with any po", key))
				errorsFound++
				continue
			}
		}

		ck := data[:32]
		c, err := decodeData(ck, data)
		if err != nil {
			log.Error("decodeData error", "err", err)
			continue
		}

		sdata := c.Data()

		cs := int64(binary.LittleEndian.Uint64(sdata[:8]))
		log.Trace("chunk", "key", fmt.Sprintf("%x", key), "ck", fmt.Sprintf("%x", ck), "dkey", fmt.Sprintf("%x", datakey), "dataidx", index.Idx, "po", po, "len data", len(data), "len sdata", len(sdata), "size", cs)

		// if chunk is to be removed
		if f(c) {
			log.Warn("chunk for cleanup", "key", fmt.Sprintf("%x", key), "ck", fmt.Sprintf("%x", ck), "dkey", fmt.Sprintf("%x", datakey), "dataidx", index.Idx, "po", po, "len data", len(data), "len sdata", len(sdata), "size", cs)
			s.deleteNow(&index, getIndexKey(key[1:]), po)
			removed++
			errorsFound++
		}
	}

	log.Warn(fmt.Sprintf("Found %v errors out of %v entries. Removed %v chunks.", errorsFound, total, removed))
}
813966
func getTopK(queue []interface{}, id *bitmap, k int) []interface{} {
	topkHeap := make(topKHeap, 0, k+1)

	for _, value := range queue {
		node := value.(*node)
		distance := id.Xor(node.id)
		if topkHeap.Len() == k {
			var last = topkHeap[topkHeap.Len() - 1]
			if last.distance.Compare(distance, maxPrefixLength) == 1 {
				item := &heapItem{
					distance,
					value,
				}
				heap.Push(&topkHeap, item)
				heap.Pop(&topkHeap)
			}
		} else {
			item := &heapItem{
				distance,
				value,
			}
			heap.Push(&topkHeap, item)
		}
	}

	tops := make([]interface{}, topkHeap.Len())
	for i := len(tops) - 1; i >= 0; i-- {
		tops[i] = heap.Pop(&topkHeap).(*heapItem).value
	}

	return tops
}
399937
func (world *World) Malloc(flags uint, size uint) *Memory {
	return &Memory{world, size}
}
33708
func (h *Heap) Delete(obj interface{}) error {
	key, err := h.data.keyFunc(obj)
	if err != nil {
		return KeyError{obj, err}
	}
	h.lock.Lock()
	defer h.lock.Unlock()
	if item, ok := h.data.items[key]; ok {
		heap.Remove(h.data, item.index)
		return nil
	}
	return fmt.Errorf("object not found")
}