internal/impl: use linked-list for unknown field ordering
Unknown fields follow a policy where the latest field takes precedence when
it comes to the ordering. However, the current implementation is incorrect
as it uses a slice and simply swaps the current entry with the last entry.
While this ensures that the latest field seen remains last, it does not ensure
that the swapped out entry is second-to-last.
To provide the desired behavior, a linked-list is used.
For simplicity, we use the list package in the standard library even if it
is neither the most performant nor type safe.
Change-Id: I675145c61f6b5b624ed9e94bbe2251b5a71e2c48
Reviewed-on: https://go-review.googlesource.com/c/145241
Reviewed-by: Damien Neil <dneil@google.com>
diff --git a/internal/impl/legacy_test.go b/internal/impl/legacy_test.go
index 32253f3..d2e71d4 100644
--- a/internal/impl/legacy_test.go
+++ b/internal/impl/legacy_test.go
@@ -201,7 +201,7 @@
}
// Simulate manual appending of raw field data.
- fs = append(fs, joinRaw(raw3a, raw1a, raw1b, raw3b, raw2b, raw1c)...)
+ fs = append(fs, joinRaw(raw3a, raw1a, raw1b, raw2b, raw3b, raw1c)...)
if got, want := fs.Len(), 3; got != want {
t.Errorf("Len() = %d, want %d", got, want)
}
@@ -212,8 +212,8 @@
num pref.FieldNumber
raw pref.RawFields
}{
- {3, joinRaw(raw3a, raw3b)},
{2, joinRaw(raw2a, raw2b)},
+ {3, joinRaw(raw3a, raw3b)},
{1, joinRaw(raw1a, raw1b, raw1c)},
}
fs.Range(func(num pref.FieldNumber, raw pref.RawFields) bool {
diff --git a/internal/impl/legacy_unknown.go b/internal/impl/legacy_unknown.go
index c8c3a69..a319f05 100644
--- a/internal/impl/legacy_unknown.go
+++ b/internal/impl/legacy_unknown.go
@@ -5,6 +5,7 @@
package impl
import (
+ "container/list"
"reflect"
protoV1 "github.com/golang/protobuf/proto"
@@ -97,7 +98,6 @@
num pref.FieldNumber
raw pref.RawFields
}
- var xs []entry
// Collect up a list of all the raw fields.
// We preserve the order such that the latest encountered fields
@@ -105,23 +105,19 @@
//
// Runtime complexity: O(n)
b := *fs
- m := map[pref.FieldNumber]int{}
+ l := list.New()
+ m := map[pref.FieldNumber]*list.Element{}
for len(b) > 0 {
num, _, n := wire.ConsumeField(b)
-
- // Ensure the most recently updated entry is always at the end of xs.
- x := entry{num: num}
- if i, ok := m[num]; ok {
- j := len(xs) - 1
- xs[i], xs[j] = xs[j], xs[i] // swap current entry with last entry
- m[xs[i].num] = i // update index of swapped entry
- x = xs[j] // retrieve the last entry
- xs = xs[:j] // truncate off the last entry
+ if e, ok := m[num]; ok {
+ x := e.Value.(*entry)
+ x.raw = append(x.raw, b[:n]...)
+ l.MoveToBack(e)
+ } else {
+ x := &entry{num: num}
+ x.raw = append(x.raw, b[:n]...)
+ m[num] = l.PushBack(x)
}
- m[num] = len(xs)
- x.raw = append(x.raw, b[:n]...)
- xs = append(xs, x)
-
b = b[n:]
}
@@ -130,7 +126,8 @@
// while ranging are not observable.
//
// Runtime complexity: O(n)
- for _, x := range xs {
+ for e := l.Front(); e != nil; e = e.Next() {
+ x := e.Value.(*entry)
if !f(x.num, x.raw) {
return
}
