From 01389b966ed81fad6e5fac3e98fe46e162645659 Mon Sep 17 00:00:00 2001
From: Andrew Gerrand <adg@golang.org>
Date: Mon, 25 Oct 2010 14:37:30 +1100
Subject: [PATCH] container/list: fix Remove bug and use pointer to self as
 identifier

Remove wasn't nil'ing the *Element.id. This property was exploited
by MoveToFront and MoveToBack internally, so I renamed the existing
Remove to "remove", and created an exported wrapper "Remove" that does
the right thing for the user's sake.

Also, saved an allocation by using *List as the id rather than *byte.

Fixes #1224.

R=rsc, dsymonds
CC=golang-dev
https://golang.org/cl/2685042
---
 src/pkg/container/list/list.go      | 40 +++++++++++++++++------------
 src/pkg/container/list/list_test.go | 17 ++++++++++--
 2 files changed, 38 insertions(+), 19 deletions(-)

diff --git a/src/pkg/container/list/list.go b/src/pkg/container/list/list.go
index 55831e8e61..47ceae170c 100644
--- a/src/pkg/container/list/list.go
+++ b/src/pkg/container/list/list.go
@@ -11,8 +11,8 @@ type Element struct {
 	// The front of the list has prev = nil, and the back has next = nil.
 	next, prev *Element
 
-	// A unique ID for the list to which this element belongs.
-	id *byte
+	// Thie list to which this element belongs.
+	list *List
 
 	// The contents of this list element.
 	Value interface{}
@@ -29,7 +29,6 @@ func (e *Element) Prev() *Element { return e.prev }
 type List struct {
 	front, back *Element
 	len         int
-	id          *byte
 }
 
 // Init initializes or clears a List.
@@ -37,7 +36,6 @@ func (l *List) Init() *List {
 	l.front = nil
 	l.back = nil
 	l.len = 0
-	l.id = new(byte)
 	return l
 }
 
@@ -52,7 +50,15 @@ func (l *List) Back() *Element { return l.back }
 
 // Remove removes the element from the list.
 func (l *List) Remove(e *Element) {
-	if e.id != l.id {
+	l.remove(e)
+	e.list = nil // do what remove does not
+}
+
+// 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 {
@@ -121,59 +127,59 @@ func (l *List) insertBack(e *Element) {
 
 // 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 {
-	if l.id == nil {
+	if l == nil {
 		l.Init()
 	}
-	e := &Element{nil, nil, l.id, value}
+	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 {
-	if l.id == nil {
+	if l == nil {
 		l.Init()
 	}
-	e := &Element{nil, nil, l.id, value}
+	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.id != l.id {
+	if mark.list != l {
 		return nil
 	}
-	e := &Element{nil, nil, l.id, value}
+	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.id != l.id {
+	if mark.list != l {
 		return nil
 	}
-	e := &Element{nil, nil, l.id, value}
+	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.id != l.id || l.front == e {
+	if e.list != l || l.front == e {
 		return
 	}
-	l.Remove(e)
+	l.remove(e)
 	l.insertFront(e)
 }
 
 // MoveToBack moves the element to the back of the list.
 func (l *List) MoveToBack(e *Element) {
-	if e.id != l.id || l.back == e {
+	if e.list != l || l.back == e {
 		return
 	}
-	l.Remove(e)
+	l.remove(e)
 	l.insertBack(e)
 }
 
diff --git a/src/pkg/container/list/list_test.go b/src/pkg/container/list/list_test.go
index 4538a0dcfd..1d44ff84e4 100644
--- a/src/pkg/container/list/list_test.go
+++ b/src/pkg/container/list/list_test.go
@@ -23,8 +23,7 @@ func checkListPointers(t *testing.T, l *List, es []*Element) {
 		t.Errorf("l.back = %v, want %v", l.back, last)
 	}
 
-	for i := 0; i < len(es); i++ {
-		e := es[i]
+	for i, e := range es {
 		var e_prev, e_next *Element = nil, nil
 		if i > 0 {
 			e_prev = es[i-1]
@@ -194,3 +193,17 @@ func TestExtending(t *testing.T) {
 	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)
+}
-- 
2.48.1