package pprof

import "unsafe"

type profMap struct {
	hash    map[uintptr]*profMapEntry
	all     *profMapEntry
	last    *profMapEntry
	free    []profMapEntry
	freeStk []uintptr
}

type profMapEntry struct {
	nextHash *profMapEntry // next in hash list
	nextAll  *profMapEntry // next in list of all entries
	stk      []uintptr
	tag      unsafe.Pointer
	count    int64
}

	h := uintptr(0)
	for _, x := range stk {
		h = h<<8 | (h >> (8 * (unsafe.Sizeof(h) - 1)))
		h += uintptr(x) * 41
	}
	h = h<<8 | (h >> (8 * (unsafe.Sizeof(h) - 1)))
	h += uintptr(tag) * 41

	var last *profMapEntry
Search:
	for e := m.hash[h]; e != nil; last, e = e, e.nextHash {
		if len(e.stk) != len(stk) || e.tag != tag {
			continue
		}
		for j := range stk {
			if e.stk[j] != uintptr(stk[j]) {
				continue Search
			}

		if last != nil {
			last.nextHash = e.nextHash
			e.nextHash = m.hash[h]
			m.hash[h] = e
		}
		return e
	}

	if len(m.free) < 1 {
		m.free = make([]profMapEntry, 128)
	}
	e := &m.free[0]
	m.free = m.free[1:]
	e.nextHash = m.hash[h]
	e.tag = tag

	if len(m.freeStk) < len(stk) {
		m.freeStk = make([]uintptr, 1024)

	e.stk = m.freeStk[:len(stk):len(stk)]
	m.freeStk = m.freeStk[len(stk):]

	for j := range stk {
		e.stk[j] = uintptr(stk[j])
	}
	if m.hash == nil {
		m.hash = make(map[uintptr]*profMapEntry)
	}
	m.hash[h] = e
	if m.all == nil {
		m.all = e
		m.last = e
	} else {
		m.last.nextAll = e
		m.last = e
	}
	return e