container/list: combining insert and remove operations while moving elements within a list.

Fixes #27747

Change-Id: I843e9e121d33440648b364650ee8a8a1639a0144
GitHub-Last-Rev: c614e91e23d4d3dea80bc78886a1b7e96456596b
GitHub-Pull-Request: golang/go#28413
Reviewed-on: https://go-review.googlesource.com/c/144998
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 21 insertions, 4 deletions

diff --git a/src/container/list/list.go b/src/container/list/list.go
index dc4260e131..b8b599aabb 100644
--- a/src/container/list/list.go
+++ b/src/container/list/list.go
@@ -116,6 +116,23 @@ func (l *List) remove(e *Element) *Element {
 	return e
 }
 
+// move moves e to next to at and returns e.
+func (l *List) move(e, at *Element) *Element {
+	if e == at {
+		return e
+	}
+	e.prev.next = e.next
+	e.next.prev = e.prev
+
+	n := at.next
+	at.next = e
+	e.prev = at
+	e.next = n
+	n.prev = e
+
+	return e
+}
+
 // Remove removes e from l if e is an element of list l.
 // It returns the element value e.Value.
 // The element must not be nil.
@@ -170,7 +187,7 @@ func (l *List) MoveToFront(e *Element) {
 		return
 	}
 	// see comment in List.Remove about initialization of l
-	l.insert(l.remove(e), &l.root)
+	l.move(e, &l.root)
 }
 
 // MoveToBack moves element e to the back of list l.
@@ -181,7 +198,7 @@ func (l *List) MoveToBack(e *Element) {
 		return
 	}
 	// see comment in List.Remove about initialization of l
-	l.insert(l.remove(e), l.root.prev)
+	l.move(e, l.root.prev)
 }
 
 // MoveBefore moves element e to its new position before mark.
@@ -191,7 +208,7 @@ func (l *List) MoveBefore(e, mark *Element) {
 	if e.list != l || e == mark || mark.list != l {
 		return
 	}
-	l.insert(l.remove(e), mark.prev)
+	l.move(e, mark.prev)
 }
 
 // MoveAfter moves element e to its new position after mark.
@@ -201,7 +218,7 @@ func (l *List) MoveAfter(e, mark *Element) {
 	if e.list != l || e == mark || mark.list != l {
 		return
 	}
-	l.insert(l.remove(e), mark)
+	l.move(e, mark)
 }
 
 // PushBackList inserts a copy of an other list at the back of list l.