From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libgo/go/container/list/list.go | 211 +++++++++++++++++++++++++++++++++++ libgo/go/container/list/list_test.go | 209 ++++++++++++++++++++++++++++++++++ 2 files changed, 420 insertions(+) create mode 100755 libgo/go/container/list/list.go create mode 100755 libgo/go/container/list/list_test.go (limited to 'libgo/go/container/list') diff --git a/libgo/go/container/list/list.go b/libgo/go/container/list/list.go new file mode 100755 index 000000000..c1ebcddaa --- /dev/null +++ b/libgo/go/container/list/list.go @@ -0,0 +1,211 @@ +// 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. + +// The list package 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 in the linked list. +type Element struct { + // Next and previous pointers in the doubly-linked list of elements. + // The front of the list has prev = nil, and the back has next = nil. + next, prev *Element + + // The list to which this element belongs. + list *List + + // The contents of this list element. + Value interface{} +} + +// Next returns the next list element or nil. +func (e *Element) Next() *Element { return e.next } + +// Prev returns the previous list element or nil. +func (e *Element) Prev() *Element { return e.prev } + +// List represents a doubly linked list. +// The zero value for List is an empty list ready to use. +type List struct { + front, back *Element + len int +} + +// Init initializes or clears a List. +func (l *List) Init() *List { + l.front = nil + l.back = nil + l.len = 0 + return l +} + +// New returns an initialized list. +func New() *List { return new(List) } + +// Front returns the first element in the list. +func (l *List) Front() *Element { return l.front } + +// Back returns the last element in the list. +func (l *List) Back() *Element { return l.back } + +// Remove removes the element from the list +// and returns its Value. +func (l *List) Remove(e *Element) interface{} { + l.remove(e) + e.list = nil // do what remove does not + return e.Value +} + +// remove the element from the list, but do not clear the Element's list field. +// This is so that other List methods may use remove when relocating Elements +// without needing to restore the list field. +func (l *List) remove(e *Element) { + if e.list != l { + return + } + if e.prev == nil { + l.front = e.next + } else { + e.prev.next = e.next + } + if e.next == nil { + l.back = e.prev + } else { + e.next.prev = e.prev + } + + e.prev = nil + e.next = nil + l.len-- +} + +func (l *List) insertBefore(e *Element, mark *Element) { + if mark.prev == nil { + // new front of the list + l.front = e + } else { + mark.prev.next = e + } + e.prev = mark.prev + mark.prev = e + e.next = mark + l.len++ +} + +func (l *List) insertAfter(e *Element, mark *Element) { + if mark.next == nil { + // new back of the list + l.back = e + } else { + mark.next.prev = e + } + e.next = mark.next + mark.next = e + e.prev = mark + l.len++ +} + +func (l *List) insertFront(e *Element) { + if l.front == nil { + // empty list + l.front, l.back = e, e + e.prev, e.next = nil, nil + l.len = 1 + return + } + l.insertBefore(e, l.front) +} + +func (l *List) insertBack(e *Element) { + if l.back == nil { + // empty list + l.front, l.back = e, e + e.prev, e.next = nil, nil + l.len = 1 + return + } + l.insertAfter(e, l.back) +} + +// PushFront inserts the value at the front of the list and returns a new Element containing the value. +func (l *List) PushFront(value interface{}) *Element { + e := &Element{nil, nil, l, value} + l.insertFront(e) + return e +} + +// PushBack inserts the value at the back of the list and returns a new Element containing the value. +func (l *List) PushBack(value interface{}) *Element { + e := &Element{nil, nil, l, value} + l.insertBack(e) + return e +} + +// InsertBefore inserts the value immediately before mark and returns a new Element containing the value. +func (l *List) InsertBefore(value interface{}, mark *Element) *Element { + if mark.list != l { + return nil + } + e := &Element{nil, nil, l, value} + l.insertBefore(e, mark) + return e +} + +// InsertAfter inserts the value immediately after mark and returns a new Element containing the value. +func (l *List) InsertAfter(value interface{}, mark *Element) *Element { + if mark.list != l { + return nil + } + e := &Element{nil, nil, l, value} + l.insertAfter(e, mark) + return e +} + +// MoveToFront moves the element to the front of the list. +func (l *List) MoveToFront(e *Element) { + if e.list != l || l.front == e { + return + } + l.remove(e) + l.insertFront(e) +} + +// MoveToBack moves the element to the back of the list. +func (l *List) MoveToBack(e *Element) { + if e.list != l || l.back == e { + return + } + l.remove(e) + l.insertBack(e) +} + +// Len returns the number of elements in the list. +func (l *List) Len() int { return l.len } + +// PushBackList inserts each element of ol at the back of the list. +func (l *List) PushBackList(ol *List) { + last := ol.Back() + for e := ol.Front(); e != nil; e = e.Next() { + l.PushBack(e.Value) + if e == last { + break + } + } +} + +// PushFrontList inserts each element of ol at the front of the list. The ordering of the passed list is preserved. +func (l *List) PushFrontList(ol *List) { + first := ol.Front() + for e := ol.Back(); e != nil; e = e.Prev() { + l.PushFront(e.Value) + if e == first { + break + } + } +} diff --git a/libgo/go/container/list/list_test.go b/libgo/go/container/list/list_test.go new file mode 100755 index 000000000..1d44ff84e --- /dev/null +++ b/libgo/go/container/list/list_test.go @@ -0,0 +1,209 @@ +// 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 checkListPointers(t *testing.T, l *List, es []*Element) { + if len(es) == 0 { + if l.front != nil || l.back != nil { + t.Errorf("l.front/l.back = %v/%v should be nil/nil", l.front, l.back) + } + return + } + + if l.front != es[0] { + t.Errorf("l.front = %v, want %v", l.front, es[0]) + } + if last := es[len(es)-1]; l.back != last { + t.Errorf("l.back = %v, want %v", l.back, last) + } + + for i, e := range es { + var e_prev, e_next *Element = nil, nil + if i > 0 { + e_prev = es[i-1] + } + if i < len(es)-1 { + e_next = es[i+1] + } + if e.prev != e_prev { + t.Errorf("elt #%d (%v) has prev=%v, want %v", i, e, e.prev, e_prev) + } + if e.next != e_next { + t.Errorf("elt #%d (%v) has next=%v, want %v", i, e, e.next, e_next) + } + } +} + +func checkListLen(t *testing.T, l *List, n int) { + if an := l.Len(); an != n { + t.Errorf("l.Len() = %d, want %d", an, n) + } +} + +func TestList(t *testing.T) { + l := New() + checkListPointers(t, l, []*Element{}) + checkListLen(t, l, 0) + + // Single element list + e := l.PushFront("a") + checkListLen(t, l, 1) + checkListPointers(t, l, []*Element{e}) + l.MoveToFront(e) + checkListPointers(t, l, []*Element{e}) + l.MoveToBack(e) + checkListPointers(t, l, []*Element{e}) + checkListLen(t, l, 1) + l.Remove(e) + checkListPointers(t, l, []*Element{}) + checkListLen(t, l, 0) + + // 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}) + checkListLen(t, l, 4) + + l.Remove(e2) + checkListPointers(t, l, []*Element{e1, e3, e4}) + checkListLen(t, l, 3) + + 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.Iter() = %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{}) + checkListLen(t, l, 0) +} + +func checkList(t *testing.T, l *List, es []interface{}) { + if l.Len() != len(es) { + t.Errorf("list has len=%v, want %v", l.Len(), 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 has 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}) + checkListLen(t, l, 1) + l.Remove(e) + checkListPointers(t, l, []*Element{e2}) + checkListLen(t, l, 1) +} -- cgit v1.2.3