lfstack_test.go

Documentation: runtime

		 1  // Copyright 2012 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 runtime_test
		 6  
		 7  import (
		 8  	"math/rand"
		 9  	. "runtime"
		10  	"testing"
		11  	"unsafe"
		12  )
		13  
		14  type MyNode struct {
		15  	LFNode
		16  	data int
		17  }
		18  
		19  func fromMyNode(node *MyNode) *LFNode {
		20  	return (*LFNode)(unsafe.Pointer(node))
		21  }
		22  
		23  func toMyNode(node *LFNode) *MyNode {
		24  	return (*MyNode)(unsafe.Pointer(node))
		25  }
		26  
		27  var global interface{}
		28  
		29  func TestLFStack(t *testing.T) {
		30  	stack := new(uint64)
		31  	global = stack // force heap allocation
		32  
		33  	// Need to keep additional references to nodes, the stack is not all that type-safe.
		34  	var nodes []*MyNode
		35  
		36  	// Check the stack is initially empty.
		37  	if LFStackPop(stack) != nil {
		38  		t.Fatalf("stack is not empty")
		39  	}
		40  
		41  	// Push one element.
		42  	node := &MyNode{data: 42}
		43  	nodes = append(nodes, node)
		44  	LFStackPush(stack, fromMyNode(node))
		45  
		46  	// Push another.
		47  	node = &MyNode{data: 43}
		48  	nodes = append(nodes, node)
		49  	LFStackPush(stack, fromMyNode(node))
		50  
		51  	// Pop one element.
		52  	node = toMyNode(LFStackPop(stack))
		53  	if node == nil {
		54  		t.Fatalf("stack is empty")
		55  	}
		56  	if node.data != 43 {
		57  		t.Fatalf("no lifo")
		58  	}
		59  
		60  	// Pop another.
		61  	node = toMyNode(LFStackPop(stack))
		62  	if node == nil {
		63  		t.Fatalf("stack is empty")
		64  	}
		65  	if node.data != 42 {
		66  		t.Fatalf("no lifo")
		67  	}
		68  
		69  	// Check the stack is empty again.
		70  	if LFStackPop(stack) != nil {
		71  		t.Fatalf("stack is not empty")
		72  	}
		73  	if *stack != 0 {
		74  		t.Fatalf("stack is not empty")
		75  	}
		76  }
		77  
		78  var stress []*MyNode
		79  
		80  func TestLFStackStress(t *testing.T) {
		81  	const K = 100
		82  	P := 4 * GOMAXPROCS(-1)
		83  	N := 100000
		84  	if testing.Short() {
		85  		N /= 10
		86  	}
		87  	// Create 2 stacks.
		88  	stacks := [2]*uint64{new(uint64), new(uint64)}
		89  	// Need to keep additional references to nodes,
		90  	// the lock-free stack is not type-safe.
		91  	stress = nil
		92  	// Push K elements randomly onto the stacks.
		93  	sum := 0
		94  	for i := 0; i < K; i++ {
		95  		sum += i
		96  		node := &MyNode{data: i}
		97  		stress = append(stress, node)
		98  		LFStackPush(stacks[i%2], fromMyNode(node))
		99  	}
	 100  	c := make(chan bool, P)
	 101  	for p := 0; p < P; p++ {
	 102  		go func() {
	 103  			r := rand.New(rand.NewSource(rand.Int63()))
	 104  			// Pop a node from a random stack, then push it onto a random stack.
	 105  			for i := 0; i < N; i++ {
	 106  				node := toMyNode(LFStackPop(stacks[r.Intn(2)]))
	 107  				if node != nil {
	 108  					LFStackPush(stacks[r.Intn(2)], fromMyNode(node))
	 109  				}
	 110  			}
	 111  			c <- true
	 112  		}()
	 113  	}
	 114  	for i := 0; i < P; i++ {
	 115  		<-c
	 116  	}
	 117  	// Pop all elements from both stacks, and verify that nothing lost.
	 118  	sum2 := 0
	 119  	cnt := 0
	 120  	for i := 0; i < 2; i++ {
	 121  		for {
	 122  			node := toMyNode(LFStackPop(stacks[i]))
	 123  			if node == nil {
	 124  				break
	 125  			}
	 126  			cnt++
	 127  			sum2 += node.data
	 128  			node.Next = 0
	 129  		}
	 130  	}
	 131  	if cnt != K {
	 132  		t.Fatalf("Wrong number of nodes %d/%d", cnt, K)
	 133  	}
	 134  	if sum2 != sum {
	 135  		t.Fatalf("Wrong sum %d/%d", sum2, sum)
	 136  	}
	 137  
	 138  	// Let nodes be collected now.
	 139  	stress = nil
	 140  }
	 141
View as plain text