heap.go

     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  
     5  package ld
     6  
     7  import "cmd/link/internal/loader"
     8  
     9  // Min-heap implementation, for the deadcode pass.
    10  // Specialized for loader.Sym elements.
    11  
    12  type heap []loader.Sym
    13  
    14  func (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  
    28  func (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  
    54  func (h *heap) empty() bool { return len(*h) == 0 }
    55
View as plain text