From 1bc5aee63eb72b341f506ad058502cd0361f0d10 Mon Sep 17 00:00:00 2001 From: Ben Cheng Date: Tue, 25 Mar 2014 22:37:19 -0700 Subject: Initial checkin of GCC 4.9.0 from trunk (r208799). Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba --- gcc-4.9/libgo/go/container/heap/heap.go | 117 +++++++++++ gcc-4.9/libgo/go/container/heap/heap_test.go | 213 ++++++++++++++++++++ gcc-4.9/libgo/go/container/list/list.go | 216 ++++++++++++++++++++ gcc-4.9/libgo/go/container/list/list_test.go | 287 +++++++++++++++++++++++++++ gcc-4.9/libgo/go/container/ring/ring.go | 141 +++++++++++++ gcc-4.9/libgo/go/container/ring/ring_test.go | 220 ++++++++++++++++++++ 6 files changed, 1194 insertions(+) create mode 100644 gcc-4.9/libgo/go/container/heap/heap.go create mode 100644 gcc-4.9/libgo/go/container/heap/heap_test.go create mode 100755 gcc-4.9/libgo/go/container/list/list.go create mode 100755 gcc-4.9/libgo/go/container/list/list_test.go create mode 100644 gcc-4.9/libgo/go/container/ring/ring.go create mode 100644 gcc-4.9/libgo/go/container/ring/ring_test.go (limited to 'gcc-4.9/libgo/go/container') diff --git a/gcc-4.9/libgo/go/container/heap/heap.go b/gcc-4.9/libgo/go/container/heap/heap.go new file mode 100644 index 000000000..52c8507b4 --- /dev/null +++ b/gcc-4.9/libgo/go/container/heap/heap.go @@ -0,0 +1,117 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package heap provides heap operations for any type that implements +// heap.Interface. A heap is a tree with the property that each node is the +// minimum-valued node in its subtree. +// +// The minimum element in the tree is the root, at index 0. +// +// A heap is a common way to implement a priority queue. To build a priority +// queue, implement the Heap interface with the (negative) priority as the +// ordering for the Less method, so Push adds items while Pop removes the +// highest-priority item from the queue. The Examples include such an +// implementation; the file example_pq_test.go has the complete source. +// +package heap + +import "sort" + +// Any type that implements heap.Interface may be used as a +// min-heap with the following invariants (established after +// Init has been called or if the data is empty or sorted): +// +// !h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len() +// +// Note that Push and Pop in this interface are for package heap's +// implementation to call. To add and remove things from the heap, +// use heap.Push and heap.Pop. +type Interface interface { + sort.Interface + Push(x interface{}) // add x as element Len() + Pop() interface{} // remove and return element Len() - 1. +} + +// A heap must be initialized before any of the heap operations +// can be used. Init is idempotent with respect to the heap invariants +// and may be called whenever the heap invariants may have been invalidated. +// Its complexity is O(n) where n = h.Len(). +// +func Init(h Interface) { + // heapify + n := h.Len() + for i := n/2 - 1; i >= 0; i-- { + down(h, i, n) + } +} + +// Push pushes the element x onto the heap. The complexity is +// O(log(n)) where n = h.Len(). +// +func Push(h Interface, x interface{}) { + h.Push(x) + up(h, h.Len()-1) +} + +// Pop removes the minimum element (according to Less) from the heap +// and returns it. The complexity is O(log(n)) where n = h.Len(). +// It is equivalent to Remove(h, 0). +// +func Pop(h Interface) interface{} { + n := h.Len() - 1 + h.Swap(0, n) + down(h, 0, n) + return h.Pop() +} + +// Remove removes the element at index i from the heap. +// The complexity is O(log(n)) where n = h.Len(). +// +func Remove(h Interface, i int) interface{} { + n := h.Len() - 1 + if n != i { + h.Swap(i, n) + down(h, i, n) + up(h, i) + } + return h.Pop() +} + +// Fix reestablishes the heap ordering after the element at index i has changed its value. +// Changing the value of the element at index i and then calling Fix is equivalent to, +// but less expensive than, calling Remove(h, i) followed by a Push of the new value. +// The complexity is O(log(n)) where n = h.Len(). +func Fix(h Interface, i int) { + down(h, i, h.Len()) + up(h, i) +} + +func up(h Interface, j int) { + for { + i := (j - 1) / 2 // parent + if i == j || !h.Less(j, i) { + break + } + h.Swap(i, j) + j = i + } +} + +func down(h Interface, i, n int) { + for { + j1 := 2*i + 1 + if j1 >= n || j1 < 0 { // j1 < 0 after int overflow + break + } + j := j1 // left child + if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) { + j = j2 // = 2*i + 2 // right child + } + if !h.Less(j, i) { + break + } + h.Swap(i, j) + i = j + } +} diff --git a/gcc-4.9/libgo/go/container/heap/heap_test.go b/gcc-4.9/libgo/go/container/heap/heap_test.go new file mode 100644 index 000000000..b3d054c5f --- /dev/null +++ b/gcc-4.9/libgo/go/container/heap/heap_test.go @@ -0,0 +1,213 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package heap + +import ( + "math/rand" + "testing" +) + +type myHeap []int + +func (h *myHeap) Less(i, j int) bool { + return (*h)[i] < (*h)[j] +} + +func (h *myHeap) Swap(i, j int) { + (*h)[i], (*h)[j] = (*h)[j], (*h)[i] +} + +func (h *myHeap) Len() int { + return len(*h) +} + +func (h *myHeap) Pop() (v interface{}) { + *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1] + return +} + +func (h *myHeap) Push(v interface{}) { + *h = append(*h, v.(int)) +} + +func (h myHeap) verify(t *testing.T, i int) { + n := h.Len() + j1 := 2*i + 1 + j2 := 2*i + 2 + if j1 < n { + if h.Less(j1, i) { + t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h[i], j1, h[j1]) + return + } + h.verify(t, j1) + } + if j2 < n { + if h.Less(j2, i) { + t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h[i], j1, h[j2]) + return + } + h.verify(t, j2) + } +} + +func TestInit0(t *testing.T) { + h := new(myHeap) + for i := 20; i > 0; i-- { + h.Push(0) // all elements are the same + } + Init(h) + h.verify(t, 0) + + for i := 1; h.Len() > 0; i++ { + x := Pop(h).(int) + h.verify(t, 0) + if x != 0 { + t.Errorf("%d.th pop got %d; want %d", i, x, 0) + } + } +} + +func TestInit1(t *testing.T) { + h := new(myHeap) + for i := 20; i > 0; i-- { + h.Push(i) // all elements are different + } + Init(h) + h.verify(t, 0) + + for i := 1; h.Len() > 0; i++ { + x := Pop(h).(int) + h.verify(t, 0) + if x != i { + t.Errorf("%d.th pop got %d; want %d", i, x, i) + } + } +} + +func Test(t *testing.T) { + h := new(myHeap) + h.verify(t, 0) + + for i := 20; i > 10; i-- { + h.Push(i) + } + Init(h) + h.verify(t, 0) + + for i := 10; i > 0; i-- { + Push(h, i) + h.verify(t, 0) + } + + for i := 1; h.Len() > 0; i++ { + x := Pop(h).(int) + if i < 20 { + Push(h, 20+i) + } + h.verify(t, 0) + if x != i { + t.Errorf("%d.th pop got %d; want %d", i, x, i) + } + } +} + +func TestRemove0(t *testing.T) { + h := new(myHeap) + for i := 0; i < 10; i++ { + h.Push(i) + } + h.verify(t, 0) + + for h.Len() > 0 { + i := h.Len() - 1 + x := Remove(h, i).(int) + if x != i { + t.Errorf("Remove(%d) got %d; want %d", i, x, i) + } + h.verify(t, 0) + } +} + +func TestRemove1(t *testing.T) { + h := new(myHeap) + for i := 0; i < 10; i++ { + h.Push(i) + } + h.verify(t, 0) + + for i := 0; h.Len() > 0; i++ { + x := Remove(h, 0).(int) + if x != i { + t.Errorf("Remove(0) got %d; want %d", x, i) + } + h.verify(t, 0) + } +} + +func TestRemove2(t *testing.T) { + N := 10 + + h := new(myHeap) + for i := 0; i < N; i++ { + h.Push(i) + } + h.verify(t, 0) + + m := make(map[int]bool) + for h.Len() > 0 { + m[Remove(h, (h.Len()-1)/2).(int)] = true + h.verify(t, 0) + } + + if len(m) != N { + t.Errorf("len(m) = %d; want %d", len(m), N) + } + for i := 0; i < len(m); i++ { + if !m[i] { + t.Errorf("m[%d] doesn't exist", i) + } + } +} + +func BenchmarkDup(b *testing.B) { + const n = 10000 + h := make(myHeap, n) + for i := 0; i < b.N; i++ { + for j := 0; j < n; j++ { + Push(&h, 0) // all elements are the same + } + for h.Len() > 0 { + Pop(&h) + } + } +} + +func TestFix(t *testing.T) { + h := new(myHeap) + h.verify(t, 0) + + for i := 200; i > 0; i -= 10 { + Push(h, i) + } + h.verify(t, 0) + + if (*h)[0] != 10 { + t.Fatalf("Expected head to be 10, was %d", (*h)[0]) + } + (*h)[0] = 210 + Fix(h, 0) + h.verify(t, 0) + + for i := 100; i > 0; i-- { + elem := rand.Intn(h.Len()) + if i&1 == 0 { + (*h)[elem] *= 2 + } else { + (*h)[elem] /= 2 + } + Fix(h, elem) + h.verify(t, 0) + } +} diff --git a/gcc-4.9/libgo/go/container/list/list.go b/gcc-4.9/libgo/go/container/list/list.go new file mode 100755 index 000000000..ed2d15a45 --- /dev/null +++ b/gcc-4.9/libgo/go/container/list/list.go @@ -0,0 +1,216 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package list implements a doubly linked list. +// +// To iterate over a list (where l is a *List): +// for e := l.Front(); e != nil; e = e.Next() { +// // do something with e.Value +// } +// +package list + +// Element is an element of a linked list. +type Element struct { + // Next and previous pointers in the doubly-linked list of elements. + // To simplify the implementation, internally a list l is implemented + // as a ring, such that &l.root is both the next element of the last + // list element (l.Back()) and the previous element of the first list + // element (l.Front()). + next, prev *Element + + // The list to which this element belongs. + list *List + + // The value stored with this element. + Value interface{} +} + +// Next returns the next list element or nil. +func (e *Element) Next() *Element { + if p := e.next; e.list != nil && p != &e.list.root { + return p + } + return nil +} + +// Prev returns the previous list element or nil. +func (e *Element) Prev() *Element { + if p := e.prev; e.list != nil && p != &e.list.root { + return p + } + return nil +} + +// List represents a doubly linked list. +// The zero value for List is an empty list ready to use. +type List struct { + root Element // sentinel list element, only &root, root.prev, and root.next are used + len int // current list length excluding (this) sentinel element +} + +// Init initializes or clears list l. +func (l *List) Init() *List { + l.root.next = &l.root + l.root.prev = &l.root + l.len = 0 + return l +} + +// New returns an initialized list. +func New() *List { return new(List).Init() } + +// Len returns the number of elements of list l. +// The complexity is O(1). +func (l *List) Len() int { return l.len } + +// Front returns the first element of list l or nil +func (l *List) Front() *Element { + if l.len == 0 { + return nil + } + return l.root.next +} + +// Back returns the last element of list l or nil. +func (l *List) Back() *Element { + if l.len == 0 { + return nil + } + return l.root.prev +} + +// lazyInit lazily initializes a zero List value. +func (l *List) lazyInit() { + if l.root.next == nil { + l.Init() + } +} + +// insert inserts e after at, increments l.len, and returns e. +func (l *List) insert(e, at *Element) *Element { + n := at.next + at.next = e + e.prev = at + e.next = n + n.prev = e + e.list = l + l.len++ + return e +} + +// insertValue is a convenience wrapper for insert(&Element{Value: v}, at). +func (l *List) insertValue(v interface{}, at *Element) *Element { + return l.insert(&Element{Value: v}, at) +} + +// remove removes e from its list, decrements l.len, and returns e. +func (l *List) remove(e *Element) *Element { + e.prev.next = e.next + e.next.prev = e.prev + e.next = nil // avoid memory leaks + e.prev = nil // avoid memory leaks + e.list = nil + l.len-- + return e +} + +// Remove removes e from l if e is an element of list l. +// It returns the element value e.Value. +func (l *List) Remove(e *Element) interface{} { + if e.list == l { + // if e.list == l, l must have been initialized when e was inserted + // in l or l == nil (e is a zero Element) and l.remove will crash + l.remove(e) + } + return e.Value +} + +// PushFront inserts a new element e with value v at the front of list l and returns e. +func (l *List) PushFront(v interface{}) *Element { + l.lazyInit() + return l.insertValue(v, &l.root) +} + +// PushBack inserts a new element e with value v at the back of list l and returns e. +func (l *List) PushBack(v interface{}) *Element { + l.lazyInit() + return l.insertValue(v, l.root.prev) +} + +// InsertBefore inserts a new element e with value v immediately before mark and returns e. +// If mark is not an element of l, the list is not modified. +func (l *List) InsertBefore(v interface{}, mark *Element) *Element { + if mark.list != l { + return nil + } + // see comment in List.Remove about initialization of l + return l.insertValue(v, mark.prev) +} + +// InsertAfter inserts a new element e with value v immediately after mark and returns e. +// If mark is not an element of l, the list is not modified. +func (l *List) InsertAfter(v interface{}, mark *Element) *Element { + if mark.list != l { + return nil + } + // see comment in List.Remove about initialization of l + return l.insertValue(v, mark) +} + +// MoveToFront moves element e to the front of list l. +// If e is not an element of l, the list is not modified. +func (l *List) MoveToFront(e *Element) { + if e.list != l || l.root.next == e { + return + } + // see comment in List.Remove about initialization of l + l.insert(l.remove(e), &l.root) +} + +// MoveToBack moves element e to the back of list l. +// If e is not an element of l, the list is not modified. +func (l *List) MoveToBack(e *Element) { + if e.list != l || l.root.prev == e { + return + } + // see comment in List.Remove about initialization of l + l.insert(l.remove(e), l.root.prev) +} + +// MoveBefore moves element e to its new position before mark. +// If e is not an element of l, or e == mark, the list is not modified. +func (l *List) MoveBefore(e, mark *Element) { + if e.list != l || e == mark { + return + } + l.insert(l.remove(e), mark.prev) +} + +// MoveAfter moves element e to its new position after mark. +// If e is not an element of l, or e == mark, the list is not modified. +func (l *List) MoveAfter(e, mark *Element) { + if e.list != l || e == mark { + return + } + l.insert(l.remove(e), mark) +} + +// PushBackList inserts a copy of an other list at the back of list l. +// The lists l and other may be the same. +func (l *List) PushBackList(other *List) { + l.lazyInit() + for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() { + l.insertValue(e.Value, l.root.prev) + } +} + +// PushFrontList inserts a copy of an other list at the front of list l. +// The lists l and other may be the same. +func (l *List) PushFrontList(other *List) { + l.lazyInit() + for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() { + l.insertValue(e.Value, &l.root) + } +} diff --git a/gcc-4.9/libgo/go/container/list/list_test.go b/gcc-4.9/libgo/go/container/list/list_test.go new file mode 100755 index 000000000..ee52afe82 --- /dev/null +++ b/gcc-4.9/libgo/go/container/list/list_test.go @@ -0,0 +1,287 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package list + +import "testing" + +func checkListLen(t *testing.T, l *List, len int) bool { + if n := l.Len(); n != len { + t.Errorf("l.Len() = %d, want %d", n, len) + return false + } + return true +} + +func checkListPointers(t *testing.T, l *List, es []*Element) { + root := &l.root + + if !checkListLen(t, l, len(es)) { + return + } + + // zero length lists must be the zero value or properly initialized (sentinel circle) + if len(es) == 0 { + if l.root.next != nil && l.root.next != root || l.root.prev != nil && l.root.prev != root { + t.Errorf("l.root.next = %p, l.root.prev = %p; both should both be nil or %p", l.root.next, l.root.prev, root) + } + return + } + // len(es) > 0 + + // check internal and external prev/next connections + for i, e := range es { + prev := root + Prev := (*Element)(nil) + if i > 0 { + prev = es[i-1] + Prev = prev + } + if p := e.prev; p != prev { + t.Errorf("elt[%d](%p).prev = %p, want %p", i, e, p, prev) + } + if p := e.Prev(); p != Prev { + t.Errorf("elt[%d](%p).Prev() = %p, want %p", i, e, p, Prev) + } + + next := root + Next := (*Element)(nil) + if i < len(es)-1 { + next = es[i+1] + Next = next + } + if n := e.next; n != next { + t.Errorf("elt[%d](%p).next = %p, want %p", i, e, n, next) + } + if n := e.Next(); n != Next { + t.Errorf("elt[%d](%p).Next() = %p, want %p", i, e, n, Next) + } + } +} + +func TestList(t *testing.T) { + l := New() + checkListPointers(t, l, []*Element{}) + + // Single element list + e := l.PushFront("a") + checkListPointers(t, l, []*Element{e}) + l.MoveToFront(e) + checkListPointers(t, l, []*Element{e}) + l.MoveToBack(e) + checkListPointers(t, l, []*Element{e}) + l.Remove(e) + checkListPointers(t, l, []*Element{}) + + // Bigger list + e2 := l.PushFront(2) + e1 := l.PushFront(1) + e3 := l.PushBack(3) + e4 := l.PushBack("banana") + checkListPointers(t, l, []*Element{e1, e2, e3, e4}) + + l.Remove(e2) + checkListPointers(t, l, []*Element{e1, e3, e4}) + + l.MoveToFront(e3) // move from middle + checkListPointers(t, l, []*Element{e3, e1, e4}) + + l.MoveToFront(e1) + l.MoveToBack(e3) // move from middle + checkListPointers(t, l, []*Element{e1, e4, e3}) + + l.MoveToFront(e3) // move from back + checkListPointers(t, l, []*Element{e3, e1, e4}) + l.MoveToFront(e3) // should be no-op + checkListPointers(t, l, []*Element{e3, e1, e4}) + + l.MoveToBack(e3) // move from front + checkListPointers(t, l, []*Element{e1, e4, e3}) + l.MoveToBack(e3) // should be no-op + checkListPointers(t, l, []*Element{e1, e4, e3}) + + e2 = l.InsertBefore(2, e1) // insert before front + checkListPointers(t, l, []*Element{e2, e1, e4, e3}) + l.Remove(e2) + e2 = l.InsertBefore(2, e4) // insert before middle + checkListPointers(t, l, []*Element{e1, e2, e4, e3}) + l.Remove(e2) + e2 = l.InsertBefore(2, e3) // insert before back + checkListPointers(t, l, []*Element{e1, e4, e2, e3}) + l.Remove(e2) + + e2 = l.InsertAfter(2, e1) // insert after front + checkListPointers(t, l, []*Element{e1, e2, e4, e3}) + l.Remove(e2) + e2 = l.InsertAfter(2, e4) // insert after middle + checkListPointers(t, l, []*Element{e1, e4, e2, e3}) + l.Remove(e2) + e2 = l.InsertAfter(2, e3) // insert after back + checkListPointers(t, l, []*Element{e1, e4, e3, e2}) + l.Remove(e2) + + // Check standard iteration. + sum := 0 + for e := l.Front(); e != nil; e = e.Next() { + if i, ok := e.Value.(int); ok { + sum += i + } + } + if sum != 4 { + t.Errorf("sum over l = %d, want 4", sum) + } + + // Clear all elements by iterating + var next *Element + for e := l.Front(); e != nil; e = next { + next = e.Next() + l.Remove(e) + } + checkListPointers(t, l, []*Element{}) +} + +func checkList(t *testing.T, l *List, es []interface{}) { + if !checkListLen(t, l, len(es)) { + return + } + + i := 0 + for e := l.Front(); e != nil; e = e.Next() { + le := e.Value.(int) + if le != es[i] { + t.Errorf("elt[%d].Value = %v, want %v", i, le, es[i]) + } + i++ + } +} + +func TestExtending(t *testing.T) { + l1 := New() + l2 := New() + + l1.PushBack(1) + l1.PushBack(2) + l1.PushBack(3) + + l2.PushBack(4) + l2.PushBack(5) + + l3 := New() + l3.PushBackList(l1) + checkList(t, l3, []interface{}{1, 2, 3}) + l3.PushBackList(l2) + checkList(t, l3, []interface{}{1, 2, 3, 4, 5}) + + l3 = New() + l3.PushFrontList(l2) + checkList(t, l3, []interface{}{4, 5}) + l3.PushFrontList(l1) + checkList(t, l3, []interface{}{1, 2, 3, 4, 5}) + + checkList(t, l1, []interface{}{1, 2, 3}) + checkList(t, l2, []interface{}{4, 5}) + + l3 = New() + l3.PushBackList(l1) + checkList(t, l3, []interface{}{1, 2, 3}) + l3.PushBackList(l3) + checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3}) + + l3 = New() + l3.PushFrontList(l1) + checkList(t, l3, []interface{}{1, 2, 3}) + l3.PushFrontList(l3) + checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3}) + + l3 = New() + l1.PushBackList(l3) + checkList(t, l1, []interface{}{1, 2, 3}) + l1.PushFrontList(l3) + checkList(t, l1, []interface{}{1, 2, 3}) +} + +func TestRemove(t *testing.T) { + l := New() + e1 := l.PushBack(1) + e2 := l.PushBack(2) + checkListPointers(t, l, []*Element{e1, e2}) + e := l.Front() + l.Remove(e) + checkListPointers(t, l, []*Element{e2}) + l.Remove(e) + checkListPointers(t, l, []*Element{e2}) +} + +func TestIssue4103(t *testing.T) { + l1 := New() + l1.PushBack(1) + l1.PushBack(2) + + l2 := New() + l2.PushBack(3) + l2.PushBack(4) + + e := l1.Front() + l2.Remove(e) // l2 should not change because e is not an element of l2 + if n := l2.Len(); n != 2 { + t.Errorf("l2.Len() = %d, want 2", n) + } + + l1.InsertBefore(8, e) + if n := l1.Len(); n != 3 { + t.Errorf("l1.Len() = %d, want 3", n) + } +} + +func TestIssue6349(t *testing.T) { + l := New() + l.PushBack(1) + l.PushBack(2) + + e := l.Front() + l.Remove(e) + if e.Value != 1 { + t.Errorf("e.value = %d, want 1", e.Value) + } + if e.Next() != nil { + t.Errorf("e.Next() != nil") + } + if e.Prev() != nil { + t.Errorf("e.Prev() != nil") + } +} + +func TestMove(t *testing.T) { + l := New() + e1 := l.PushBack(1) + e2 := l.PushBack(2) + e3 := l.PushBack(3) + e4 := l.PushBack(4) + + l.MoveAfter(e3, e3) + checkListPointers(t, l, []*Element{e1, e2, e3, e4}) + l.MoveBefore(e2, e2) + checkListPointers(t, l, []*Element{e1, e2, e3, e4}) + + l.MoveAfter(e3, e2) + checkListPointers(t, l, []*Element{e1, e2, e3, e4}) + l.MoveBefore(e2, e3) + checkListPointers(t, l, []*Element{e1, e2, e3, e4}) + + l.MoveBefore(e2, e4) + checkListPointers(t, l, []*Element{e1, e3, e2, e4}) + e1, e2, e3, e4 = e1, e3, e2, e4 + + l.MoveBefore(e4, e1) + checkListPointers(t, l, []*Element{e4, e1, e2, e3}) + e1, e2, e3, e4 = e4, e1, e2, e3 + + l.MoveAfter(e4, e1) + checkListPointers(t, l, []*Element{e1, e4, e2, e3}) + e1, e2, e3, e4 = e1, e4, e2, e3 + + l.MoveAfter(e2, e3) + checkListPointers(t, l, []*Element{e1, e3, e2, e4}) + e1, e2, e3, e4 = e1, e3, e2, e4 +} diff --git a/gcc-4.9/libgo/go/container/ring/ring.go b/gcc-4.9/libgo/go/container/ring/ring.go new file mode 100644 index 000000000..6d3b3e5b3 --- /dev/null +++ b/gcc-4.9/libgo/go/container/ring/ring.go @@ -0,0 +1,141 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package ring implements operations on circular lists. +package ring + +// A Ring is an element of a circular list, or ring. +// Rings do not have a beginning or end; a pointer to any ring element +// serves as reference to the entire ring. Empty rings are represented +// as nil Ring pointers. The zero value for a Ring is a one-element +// ring with a nil Value. +// +type Ring struct { + next, prev *Ring + Value interface{} // for use by client; untouched by this library +} + +func (r *Ring) init() *Ring { + r.next = r + r.prev = r + return r +} + +// Next returns the next ring element. r must not be empty. +func (r *Ring) Next() *Ring { + if r.next == nil { + return r.init() + } + return r.next +} + +// Prev returns the previous ring element. r must not be empty. +func (r *Ring) Prev() *Ring { + if r.next == nil { + return r.init() + } + return r.prev +} + +// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0) +// in the ring and returns that ring element. r must not be empty. +// +func (r *Ring) Move(n int) *Ring { + if r.next == nil { + return r.init() + } + switch { + case n < 0: + for ; n < 0; n++ { + r = r.prev + } + case n > 0: + for ; n > 0; n-- { + r = r.next + } + } + return r +} + +// New creates a ring of n elements. +func New(n int) *Ring { + if n <= 0 { + return nil + } + r := new(Ring) + p := r + for i := 1; i < n; i++ { + p.next = &Ring{prev: p} + p = p.next + } + p.next = r + r.prev = p + return r +} + +// Link connects ring r with ring s such that r.Next() +// becomes s and returns the original value for r.Next(). +// r must not be empty. +// +// If r and s point to the same ring, linking +// them removes the elements between r and s from the ring. +// The removed elements form a subring and the result is a +// reference to that subring (if no elements were removed, +// the result is still the original value for r.Next(), +// and not nil). +// +// If r and s point to different rings, linking +// them creates a single ring with the elements of s inserted +// after r. The result points to the element following the +// last element of s after insertion. +// +func (r *Ring) Link(s *Ring) *Ring { + n := r.Next() + if s != nil { + p := s.Prev() + // Note: Cannot use multiple assignment because + // evaluation order of LHS is not specified. + r.next = s + s.prev = r + n.prev = p + p.next = n + } + return n +} + +// Unlink removes n % r.Len() elements from the ring r, starting +// at r.Next(). If n % r.Len() == 0, r remains unchanged. +// The result is the removed subring. r must not be empty. +// +func (r *Ring) Unlink(n int) *Ring { + if n <= 0 { + return nil + } + return r.Link(r.Move(n + 1)) +} + +// Len computes the number of elements in ring r. +// It executes in time proportional to the number of elements. +// +func (r *Ring) Len() int { + n := 0 + if r != nil { + n = 1 + for p := r.Next(); p != r; p = p.next { + n++ + } + } + return n +} + +// Do calls function f on each element of the ring, in forward order. +// The behavior of Do is undefined if f changes *r. +func (r *Ring) Do(f func(interface{})) { + if r != nil { + f(r.Value) + for p := r.Next(); p != r; p = p.next { + f(p.Value) + } + } +} diff --git a/gcc-4.9/libgo/go/container/ring/ring_test.go b/gcc-4.9/libgo/go/container/ring/ring_test.go new file mode 100644 index 000000000..099d92b25 --- /dev/null +++ b/gcc-4.9/libgo/go/container/ring/ring_test.go @@ -0,0 +1,220 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package ring + +import ( + "fmt" + "testing" +) + +// For debugging - keep around. +func dump(r *Ring) { + if r == nil { + fmt.Println("empty") + return + } + i, n := 0, r.Len() + for p := r; i < n; p = p.next { + fmt.Printf("%4d: %p = {<- %p | %p ->}\n", i, p, p.prev, p.next) + i++ + } + fmt.Println() +} + +func verify(t *testing.T, r *Ring, N int, sum int) { + // Len + n := r.Len() + if n != N { + t.Errorf("r.Len() == %d; expected %d", n, N) + } + + // iteration + n = 0 + s := 0 + r.Do(func(p interface{}) { + n++ + if p != nil { + s += p.(int) + } + }) + if n != N { + t.Errorf("number of forward iterations == %d; expected %d", n, N) + } + if sum >= 0 && s != sum { + t.Errorf("forward ring sum = %d; expected %d", s, sum) + } + + if r == nil { + return + } + + // connections + if r.next != nil { + var p *Ring // previous element + for q := r; p == nil || q != r; q = q.next { + if p != nil && p != q.prev { + t.Errorf("prev = %p, expected q.prev = %p\n", p, q.prev) + } + p = q + } + if p != r.prev { + t.Errorf("prev = %p, expected r.prev = %p\n", p, r.prev) + } + } + + // Next, Prev + if r.Next() != r.next { + t.Errorf("r.Next() != r.next") + } + if r.Prev() != r.prev { + t.Errorf("r.Prev() != r.prev") + } + + // Move + if r.Move(0) != r { + t.Errorf("r.Move(0) != r") + } + if r.Move(N) != r { + t.Errorf("r.Move(%d) != r", N) + } + if r.Move(-N) != r { + t.Errorf("r.Move(%d) != r", -N) + } + for i := 0; i < 10; i++ { + ni := N + i + mi := ni % N + if r.Move(ni) != r.Move(mi) { + t.Errorf("r.Move(%d) != r.Move(%d)", ni, mi) + } + if r.Move(-ni) != r.Move(-mi) { + t.Errorf("r.Move(%d) != r.Move(%d)", -ni, -mi) + } + } +} + +func TestCornerCases(t *testing.T) { + var ( + r0 *Ring + r1 Ring + ) + // Basics + verify(t, r0, 0, 0) + verify(t, &r1, 1, 0) + // Insert + r1.Link(r0) + verify(t, r0, 0, 0) + verify(t, &r1, 1, 0) + // Insert + r1.Link(r0) + verify(t, r0, 0, 0) + verify(t, &r1, 1, 0) + // Unlink + r1.Unlink(0) + verify(t, &r1, 1, 0) +} + +func makeN(n int) *Ring { + r := New(n) + for i := 1; i <= n; i++ { + r.Value = i + r = r.Next() + } + return r +} + +func sumN(n int) int { return (n*n + n) / 2 } + +func TestNew(t *testing.T) { + for i := 0; i < 10; i++ { + r := New(i) + verify(t, r, i, -1) + } + for i := 0; i < 10; i++ { + r := makeN(i) + verify(t, r, i, sumN(i)) + } +} + +func TestLink1(t *testing.T) { + r1a := makeN(1) + var r1b Ring + r2a := r1a.Link(&r1b) + verify(t, r2a, 2, 1) + if r2a != r1a { + t.Errorf("a) 2-element link failed") + } + + r2b := r2a.Link(r2a.Next()) + verify(t, r2b, 2, 1) + if r2b != r2a.Next() { + t.Errorf("b) 2-element link failed") + } + + r1c := r2b.Link(r2b) + verify(t, r1c, 1, 1) + verify(t, r2b, 1, 0) +} + +func TestLink2(t *testing.T) { + var r0 *Ring + r1a := &Ring{Value: 42} + r1b := &Ring{Value: 77} + r10 := makeN(10) + + r1a.Link(r0) + verify(t, r1a, 1, 42) + + r1a.Link(r1b) + verify(t, r1a, 2, 42+77) + + r10.Link(r0) + verify(t, r10, 10, sumN(10)) + + r10.Link(r1a) + verify(t, r10, 12, sumN(10)+42+77) +} + +func TestLink3(t *testing.T) { + var r Ring + n := 1 + for i := 1; i < 100; i++ { + n += i + verify(t, r.Link(New(i)), n, -1) + } +} + +func TestUnlink(t *testing.T) { + r10 := makeN(10) + s10 := r10.Move(6) + + sum10 := sumN(10) + + verify(t, r10, 10, sum10) + verify(t, s10, 10, sum10) + + r0 := r10.Unlink(0) + verify(t, r0, 0, 0) + + r1 := r10.Unlink(1) + verify(t, r1, 1, 2) + verify(t, r10, 9, sum10-2) + + r9 := r10.Unlink(9) + verify(t, r9, 9, sum10-2) + verify(t, r10, 9, sum10-2) +} + +func TestLinkUnlink(t *testing.T) { + for i := 1; i < 4; i++ { + ri := New(i) + for j := 0; j < i; j++ { + rj := ri.Unlink(j) + verify(t, rj, j, -1) + verify(t, ri, i-j, -1) + ri.Link(rj) + verify(t, ri, i, -1) + } + } +} -- cgit v1.2.3