1// Copyright 2020 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package ld
6
7import "cmd/link/internal/loader"
8
9// Min-heap implementation, for the deadcode pass.
10// Specialized for loader.Sym elements.
11
12type heap []loader.Sym
13
14func (h *heap) push(s loader.Sym) {
15	*h = append(*h, s)
16	// sift up
17	n := len(*h) - 1
18	for n > 0 {
19		p := (n - 1) / 2 // parent
20		if (*h)[p] <= (*h)[n] {
21			break
22		}
23		(*h)[n], (*h)[p] = (*h)[p], (*h)[n]
24		n = p
25	}
26}
27
28func (h *heap) pop() loader.Sym {
29	r := (*h)[0]
30	n := len(*h) - 1
31	(*h)[0] = (*h)[n]
32	*h = (*h)[:n]
33
34	// sift down
35	i := 0
36	for {
37		c := 2*i + 1 // left child
38		if c >= n {
39			break
40		}
41		if c1 := c + 1; c1 < n && (*h)[c1] < (*h)[c] {
42			c = c1 // right child
43		}
44		if (*h)[i] <= (*h)[c] {
45			break
46		}
47		(*h)[i], (*h)[c] = (*h)[c], (*h)[i]
48		i = c
49	}
50
51	return r
52}
53
54func (h *heap) empty() bool { return len(*h) == 0 }
55
56// Same as heap, but sorts alphabetically instead of by index.
57// (Note that performance is not so critical here, as it is
58// in the case above. Some simplification might be in order.)
59type lexHeap []loader.Sym
60
61func (h *lexHeap) push(ldr *loader.Loader, s loader.Sym) {
62	*h = append(*h, s)
63	// sift up
64	n := len(*h) - 1
65	for n > 0 {
66		p := (n - 1) / 2 // parent
67		if ldr.SymName((*h)[p]) <= ldr.SymName((*h)[n]) {
68			break
69		}
70		(*h)[n], (*h)[p] = (*h)[p], (*h)[n]
71		n = p
72	}
73}
74
75func (h *lexHeap) pop(ldr *loader.Loader) loader.Sym {
76	r := (*h)[0]
77	n := len(*h) - 1
78	(*h)[0] = (*h)[n]
79	*h = (*h)[:n]
80
81	// sift down
82	i := 0
83	for {
84		c := 2*i + 1 // left child
85		if c >= n {
86			break
87		}
88		if c1 := c + 1; c1 < n && ldr.SymName((*h)[c1]) < ldr.SymName((*h)[c]) {
89			c = c1 // right child
90		}
91		if ldr.SymName((*h)[i]) <= ldr.SymName((*h)[c]) {
92			break
93		}
94		(*h)[i], (*h)[c] = (*h)[c], (*h)[i]
95		i = c
96	}
97
98	return r
99}
100
101func (h *lexHeap) empty() bool { return len(*h) == 0 }
102