heap_test.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 (
     8  	"cmd/link/internal/loader"
     9  	"testing"
    10  )
    11  
    12  func TestHeap(t *testing.T) {
    13  	tests := [][]loader.Sym{
    14  		{10, 20, 30, 40, 50, 60, 70, 80, 90, 100},
    15  		{100, 90, 80, 70, 60, 50, 40, 30, 20, 10},
    16  		{30, 50, 80, 20, 60, 70, 10, 100, 90, 40},
    17  	}
    18  	for _, s := range tests {
    19  		h := heap{}
    20  		for _, i := range s {
    21  			h.push(i)
    22  			if !verify(&h, 0) {
    23  				t.Errorf("heap invariant violated: %v", h)
    24  			}
    25  		}
    26  		for j := 0; j < len(s); j++ {
    27  			x := h.pop()
    28  			if !verify(&h, 0) {
    29  				t.Errorf("heap invariant violated: %v", h)
    30  			}
    31  			// pop should return elements in ascending order.
    32  			if want := loader.Sym((j + 1) * 10); x != want {
    33  				t.Errorf("pop returns wrong element: want %d, got %d", want, x)
    34  			}
    35  		}
    36  		if !h.empty() {
    37  			t.Errorf("heap is not empty after all pops")
    38  		}
    39  	}
    40  
    41  	// Also check that mixed pushes and pops work correctly.
    42  	for _, s := range tests {
    43  		h := heap{}
    44  		for i := 0; i < len(s)/2; i++ {
    45  			// two pushes, one pop
    46  			h.push(s[2*i])
    47  			if !verify(&h, 0) {
    48  				t.Errorf("heap invariant violated: %v", h)
    49  			}
    50  			h.push(s[2*i+1])
    51  			if !verify(&h, 0) {
    52  				t.Errorf("heap invariant violated: %v", h)
    53  			}
    54  			h.pop()
    55  			if !verify(&h, 0) {
    56  				t.Errorf("heap invariant violated: %v", h)
    57  			}
    58  		}
    59  		for !h.empty() { // pop remaining elements
    60  			h.pop()
    61  			if !verify(&h, 0) {
    62  				t.Errorf("heap invariant violated: %v", h)
    63  			}
    64  		}
    65  	}
    66  }
    67  
    68  // recursively verify heap-ness, starting at element i.
    69  func verify(h *heap, i int) bool {
    70  	n := len(*h)
    71  	c1 := 2*i + 1 // left child
    72  	c2 := 2*i + 2 // right child
    73  	if c1 < n {
    74  		if (*h)[c1] < (*h)[i] {
    75  			return false
    76  		}
    77  		if !verify(h, c1) {
    78  			return false
    79  		}
    80  	}
    81  	if c2 < n {
    82  		if (*h)[c2] < (*h)[i] {
    83  			return false
    84  		}
    85  		if !verify(h, c2) {
    86  			return false
    87  		}
    88  	}
    89  	return true
    90  }
    91
View as plain text