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  
    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.)
    59  type lexHeap []loader.Sym
    60  
    61  func (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  
    75  func (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  
   101  func (h *lexHeap) empty() bool { return len(*h) == 0 }
   102
View as plain text