From 5bc1fd42f6d185b8ff0201db09fb82886978908b Mon Sep 17 00:00:00 2001 From: Raghavendra Nagaraj Date: Fri, 26 Oct 2018 12:18:06 +0000 Subject: [PATCH] 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 Run-TryBot: Robert Griesemer TryBot-Result: Gobot Gobot --- src/container/list/list.go | 25 +++++++++++++++++++++---- 1 file 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. -- 2.50.0