From e38294a62d7f37c0661273a9a26fda16d557423f Mon Sep 17 00:00:00 2001 From: Jon Skeet Date: Tue, 9 Jun 2015 19:30:44 +0100 Subject: First pass at the mutable API. Quite a bit more to do - in particular, it's pretty slow right now. --- .../ProtocolBuffers/Collections/RepeatedField.cs | 168 +++++++++++++++++++++ 1 file changed, 168 insertions(+) create mode 100644 csharp/src/ProtocolBuffers/Collections/RepeatedField.cs (limited to 'csharp/src/ProtocolBuffers/Collections/RepeatedField.cs') diff --git a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs new file mode 100644 index 00000000..7dcd060e --- /dev/null +++ b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs @@ -0,0 +1,168 @@ +using System; +using System.Collections; +using System.Collections.Generic; + +namespace Google.Protobuf.Collections +{ + public sealed class RepeatedField : IList, IEquatable> + { + private readonly List list = new List(); + + public void Add(T item) + { + if (item == null) + { + throw new ArgumentNullException("item"); + } + list.Add(item); + } + + public void Clear() + { + list.Clear(); + } + + public bool Contains(T item) + { + if (item == null) + { + throw new ArgumentNullException("item"); + } + return list.Contains(item); + } + + public void CopyTo(T[] array, int arrayIndex) + { + list.CopyTo(array); + } + + public bool Remove(T item) + { + if (item == null) + { + throw new ArgumentNullException("item"); + } + return list.Remove(item); + } + + public int Count { get { return list.Count; } } + + // TODO(jonskeet): If we implement freezing, make this reflect it. + public bool IsReadOnly { get { return false; } } + + public void Add(RepeatedField values) + { + if (values == null) + { + throw new ArgumentNullException("values"); + } + // We know that all the values will be valid, because it's a RepeatedField. + list.AddRange(values); + } + + public void Add(IEnumerable values) + { + if (values == null) + { + throw new ArgumentNullException("values"); + } + foreach (T item in values) + { + Add(item); + } + } + + // TODO(jonskeet): Create our own mutable struct for this, rather than relying on List. + public List.Enumerator GetEnumerator() + { + return list.GetEnumerator(); + } + + IEnumerator IEnumerable.GetEnumerator() + { + return list.GetEnumerator(); + } + + public override bool Equals(object obj) + { + return Equals(obj as RepeatedField); + } + + public override int GetHashCode() + { + int hash = 23; + foreach (T item in this) + { + hash = hash * 31 + item.GetHashCode(); + } + return hash; + } + + IEnumerator IEnumerable.GetEnumerator() + { + return GetEnumerator(); + } + + public bool Equals(RepeatedField other) + { + if (ReferenceEquals(other, null)) + { + return false; + } + if (ReferenceEquals(other, this)) + { + return true; + } + if (other.Count != this.Count) + { + return false; + } + // TODO(jonskeet): Does this box for enums? + EqualityComparer comparer = EqualityComparer.Default; + for (int i = 0; i < Count; i++) + { + if (!comparer.Equals(this[i], other[i])) + { + return false; + } + } + return true; + } + + public int IndexOf(T item) + { + if (item == null) + { + throw new ArgumentNullException("item"); + } + return list.IndexOf(item); + } + + public void Insert(int index, T item) + { + if (item == null) + { + throw new ArgumentNullException("item"); + } + list.Insert(index, item); + } + + public void RemoveAt(int index) + { + list.RemoveAt(index); + } + + public T this[int index] + { + get { return list[index]; } + set + { + if (value == null) + { + throw new ArgumentNullException("value"); + } + list[index] = value; + } + } + } +} -- cgit v1.2.3 From 7532f0256f58e0d11711da4e159534bccbf266f0 Mon Sep 17 00:00:00 2001 From: Jon Skeet Date: Fri, 12 Jun 2015 13:07:51 +0100 Subject: Reimplement RepeatedField using an array as the backing store. This is effectively reimplementing List, but with a few advantages: - We know that an empty repeated field is common, so don't allocate an array until we need to - With direct access to the array, we can easily convert enum values to int without boxing - We can relax the restrictions over what happens if the repeated field is modified while iterating, avoiding so much checking This is somewhat risky, in that reimplementing a building block like this is *always* risky, but hey... (The performance benefits are significant...) --- .../ProtocolBuffers.Test/CodedInputStreamTest.cs | 4 +- .../src/ProtocolBuffers.Test/RepeatedFieldTest.cs | 9 +- csharp/src/ProtocolBuffers/CodedInputStream.cs | 7 +- csharp/src/ProtocolBuffers/CodedOutputStream.cs | 23 +- .../ProtocolBuffers/Collections/RepeatedField.cs | 239 ++++++++++++++++++--- 5 files changed, 231 insertions(+), 51 deletions(-) (limited to 'csharp/src/ProtocolBuffers/Collections/RepeatedField.cs') diff --git a/csharp/src/ProtocolBuffers.Test/CodedInputStreamTest.cs b/csharp/src/ProtocolBuffers.Test/CodedInputStreamTest.cs index 450662a6..07f54e94 100644 --- a/csharp/src/ProtocolBuffers.Test/CodedInputStreamTest.cs +++ b/csharp/src/ProtocolBuffers.Test/CodedInputStreamTest.cs @@ -487,7 +487,7 @@ namespace Google.Protobuf uint tag; Assert.IsTrue(input.ReadTag(out tag)); - List values = new List(); + RepeatedField values = new RepeatedField(); input.ReadEnumArray(tag, values); Assert.AreEqual(6, values.Count); @@ -511,7 +511,7 @@ namespace Google.Protobuf uint tag; Assert.IsTrue(input.ReadTag(out tag)); - List values = new List(); + RepeatedField values = new RepeatedField(); input.ReadEnumArray(tag, values); Assert.AreEqual(6, values.Count); diff --git a/csharp/src/ProtocolBuffers.Test/RepeatedFieldTest.cs b/csharp/src/ProtocolBuffers.Test/RepeatedFieldTest.cs index 94e30189..cbe79294 100644 --- a/csharp/src/ProtocolBuffers.Test/RepeatedFieldTest.cs +++ b/csharp/src/ProtocolBuffers.Test/RepeatedFieldTest.cs @@ -40,11 +40,12 @@ namespace Google.Protobuf [Test] public void Add_RepeatedField() { - var list = new RepeatedField(); + var list = new RepeatedField { "original" }; list.Add(new RepeatedField { "foo", "bar" }); - Assert.AreEqual(2, list.Count); - Assert.AreEqual("foo", list[0]); - Assert.AreEqual("bar", list[1]); + Assert.AreEqual(3, list.Count); + Assert.AreEqual("original", list[0]); + Assert.AreEqual("foo", list[1]); + Assert.AreEqual("bar", list[2]); } } } diff --git a/csharp/src/ProtocolBuffers/CodedInputStream.cs b/csharp/src/ProtocolBuffers/CodedInputStream.cs index 17fcc64b..447adbb1 100644 --- a/csharp/src/ProtocolBuffers/CodedInputStream.cs +++ b/csharp/src/ProtocolBuffers/CodedInputStream.cs @@ -38,6 +38,7 @@ using System; using System.Collections.Generic; using System.IO; using System.Text; +using Google.Protobuf.Collections; using Google.Protobuf.Descriptors; namespace Google.Protobuf @@ -700,7 +701,7 @@ namespace Google.Protobuf } } - public void ReadEnumArray(uint fieldTag, ICollection list) + public void ReadEnumArray(uint fieldTag, RepeatedField list) where T : struct, IComparable, IFormattable { WireFormat.WireType wformat = WireFormat.GetTagWireType(fieldTag); @@ -712,8 +713,8 @@ namespace Google.Protobuf int limit = PushLimit(length); while (!ReachedLimit) { - // TODO(jonskeet): Avoid this horrible boxing! - list.Add((T)(object) ReadEnum()); + // Ghastly hack, but it works... + list.AddInt32(ReadEnum()); } PopLimit(limit); } diff --git a/csharp/src/ProtocolBuffers/CodedOutputStream.cs b/csharp/src/ProtocolBuffers/CodedOutputStream.cs index dfcaf8a2..bc3ed7d7 100644 --- a/csharp/src/ProtocolBuffers/CodedOutputStream.cs +++ b/csharp/src/ProtocolBuffers/CodedOutputStream.cs @@ -743,10 +743,11 @@ namespace Google.Protobuf { return; } - // TODO(jonskeet): Avoid the Cast call here. Work out a better mass "T to int" conversion. - foreach (int value in list.Cast()) + // Bit of a hack, to access the values as ints + var iterator = list.GetInt32Enumerator(); + while (iterator.MoveNext()) { - WriteEnum(fieldNumber, value); + WriteEnum(fieldNumber, iterator.Current); } } @@ -956,15 +957,19 @@ namespace Google.Protobuf { return; } - // Obviously, we'll want to get rid of this hack... - var temporaryHack = new RepeatedField(); - temporaryHack.Add(list.Cast()); - uint size = temporaryHack.CalculateSize(ComputeEnumSizeNoTag); + // Bit of a hack, to access the values as ints + var iterator = list.GetInt32Enumerator(); + uint size = 0; + while (iterator.MoveNext()) + { + size += (uint) ComputeEnumSizeNoTag(iterator.Current); + } + iterator.Reset(); WriteTag(fieldNumber, WireFormat.WireType.LengthDelimited); WriteRawVarint32(size); - foreach (int value in temporaryHack) + while (iterator.MoveNext()) { - WriteEnumNoTag(value); + WriteEnumNoTag(iterator.Current); } } diff --git a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs index 7dcd060e..0cd5cf80 100644 --- a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs +++ b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs @@ -6,7 +6,27 @@ namespace Google.Protobuf.Collections { public sealed class RepeatedField : IList, IEquatable> { - private readonly List list = new List(); + private const int MinArraySize = 8; + private T[] array = null; + private int count = 0; + + private void EnsureSize(int size) + { + if (array == null) + { + array = new T[Math.Max(size, MinArraySize)]; + } + else + { + if (array.Length < size) + { + int newSize = Math.Max(array.Length * 2, size); + var tmp = new T[newSize]; + Array.Copy(array, 0, tmp, 0, array.Length); + array = tmp; + } + } + } public void Add(T item) { @@ -14,38 +34,55 @@ namespace Google.Protobuf.Collections { throw new ArgumentNullException("item"); } - list.Add(item); + EnsureSize(count + 1); + array[count++] = item; + } + + /// + /// Hack to allow us to add enums easily... will only work with int-based types. + /// + /// + internal void AddInt32(int item) + { + EnsureSize(count + 1); + int[] castArray = (int[]) (object) array; + castArray[count++] = item; } public void Clear() { - list.Clear(); + array = null; + count = 0; } public bool Contains(T item) { - if (item == null) - { - throw new ArgumentNullException("item"); - } - return list.Contains(item); + return IndexOf(item) != -1; } public void CopyTo(T[] array, int arrayIndex) { - list.CopyTo(array); + if (this.array == null) + { + return; + } + Array.Copy(this.array, 0, array, arrayIndex, count); } public bool Remove(T item) { - if (item == null) + int index = IndexOf(item); + if (index == -1) { - throw new ArgumentNullException("item"); - } - return list.Remove(item); + return false; + } + Array.Copy(array, index + 1, array, index, count - index - 1); + count--; + array[count] = default(T); + return true; } - public int Count { get { return list.Count; } } + public int Count { get { return count; } } // TODO(jonskeet): If we implement freezing, make this reflect it. public bool IsReadOnly { get { return false; } } @@ -56,8 +93,10 @@ namespace Google.Protobuf.Collections { throw new ArgumentNullException("values"); } + EnsureSize(count + values.count); // We know that all the values will be valid, because it's a RepeatedField. - list.AddRange(values); + Array.Copy(values.array, 0, array, count, values.count); + count += values.count; } public void Add(IEnumerable values) @@ -66,21 +105,21 @@ namespace Google.Protobuf.Collections { throw new ArgumentNullException("values"); } + // TODO: Check for ICollection and get the Count? foreach (T item in values) { Add(item); } } - // TODO(jonskeet): Create our own mutable struct for this, rather than relying on List. - public List.Enumerator GetEnumerator() + public RepeatedField.Enumerator GetEnumerator() { - return list.GetEnumerator(); + return new Enumerator(this); } IEnumerator IEnumerable.GetEnumerator() { - return list.GetEnumerator(); + return GetEnumerator(); } public override bool Equals(object obj) @@ -88,21 +127,30 @@ namespace Google.Protobuf.Collections return Equals(obj as RepeatedField); } + IEnumerator IEnumerable.GetEnumerator() + { + return GetEnumerator(); + } + + /// + /// Returns an enumerator of the values in this list as integers. + /// Used for enum types. + /// + internal Int32Enumerator GetInt32Enumerator() + { + return new Int32Enumerator((int[])(object)array, count); + } + public override int GetHashCode() { int hash = 23; - foreach (T item in this) + for (int i = 0; i < count; i++) { - hash = hash * 31 + item.GetHashCode(); + hash = hash * 31 + array[i].GetHashCode(); } return hash; } - IEnumerator IEnumerable.GetEnumerator() - { - return GetEnumerator(); - } - public bool Equals(RepeatedField other) { if (ReferenceEquals(other, null)) @@ -119,9 +167,9 @@ namespace Google.Protobuf.Collections } // TODO(jonskeet): Does this box for enums? EqualityComparer comparer = EqualityComparer.Default; - for (int i = 0; i < Count; i++) + for (int i = 0; i < count; i++) { - if (!comparer.Equals(this[i], other[i])) + if (!comparer.Equals(array[i], other.array[i])) { return false; } @@ -135,7 +183,20 @@ namespace Google.Protobuf.Collections { throw new ArgumentNullException("item"); } - return list.IndexOf(item); + if (array == null) + { + return -1; + } + // TODO(jonskeet): Does this box for enums? + EqualityComparer comparer = EqualityComparer.Default; + for (int i = 0; i < count; i++) + { + if (comparer.Equals(array[i], item)) + { + return i; + } + } + return -1; } public void Insert(int index, T item) @@ -144,24 +205,136 @@ namespace Google.Protobuf.Collections { throw new ArgumentNullException("item"); } - list.Insert(index, item); + if (index < 0 || index > count) + { + throw new ArgumentOutOfRangeException("index"); + } + EnsureSize(count + 1); + Array.Copy(array, index, array, index + 1, count - index); + count++; } public void RemoveAt(int index) { - list.RemoveAt(index); + if (index < 0 || index >= count) + { + throw new ArgumentOutOfRangeException("index"); + } + Array.Copy(array, index + 1, array, index, count - index - 1); + count--; + array[count] = default(T); } public T this[int index] { - get { return list[index]; } + get + { + if (index < 0 || index >= count) + { + throw new ArgumentOutOfRangeException("index"); + } + return array[index]; + } set { + if (index < 0 || index >= count) + { + throw new ArgumentOutOfRangeException("index"); + } if (value == null) { throw new ArgumentNullException("value"); } - list[index] = value; + array[index] = value; + } + } + + public struct Enumerator : IEnumerator + { + private int index; + private readonly RepeatedField field; + + public Enumerator(RepeatedField field) + { + this.field = field; + this.index = -1; + } + + public bool MoveNext() + { + if (index + 1 >= field.Count) + { + return false; + } + index++; + return true; + } + + public void Reset() + { + index = -1; + } + + public T Current + { + get + { + if (index == -1 || index >= field.count) + { + throw new InvalidOperationException(); + } + return field.array[index]; + } + } + + object IEnumerator.Current + { + get { return Current; } + } + + public void Dispose() + { + } + } + + internal struct Int32Enumerator : IEnumerator + { + private int index; + private readonly int[] array; + private readonly int count; + + public Int32Enumerator(int[] array, int count) + { + this.array = array; + this.index = -1; + this.count = count; + } + + public bool MoveNext() + { + if (index + 1 >= count) + { + return false; + } + index++; + return true; + } + + public void Reset() + { + index = -1; + } + + // No guard here, as we're only going to use this internally... + public int Current { get { return array[index]; } } + + object IEnumerator.Current + { + get { return Current; } + } + + public void Dispose() + { } } } -- cgit v1.2.3 From d7dda2fed8c37a83e2d4cd7ecc4201b628588c4c Mon Sep 17 00:00:00 2001 From: Jon Skeet Date: Fri, 19 Jun 2015 08:38:21 +0100 Subject: Use an empty array instead of a null reference for an empty repeated field. --- .../ProtocolBuffers/Collections/RepeatedField.cs | 32 +++++++--------------- 1 file changed, 10 insertions(+), 22 deletions(-) (limited to 'csharp/src/ProtocolBuffers/Collections/RepeatedField.cs') diff --git a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs index 0cd5cf80..25651784 100644 --- a/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs +++ b/csharp/src/ProtocolBuffers/Collections/RepeatedField.cs @@ -6,25 +6,21 @@ namespace Google.Protobuf.Collections { public sealed class RepeatedField : IList, IEquatable> { + private static readonly T[] EmptyArray = new T[0]; + private const int MinArraySize = 8; - private T[] array = null; + private T[] array = EmptyArray; private int count = 0; private void EnsureSize(int size) { - if (array == null) - { - array = new T[Math.Max(size, MinArraySize)]; - } - else + size = Math.Max(size, MinArraySize); + if (array.Length < size) { - if (array.Length < size) - { - int newSize = Math.Max(array.Length * 2, size); - var tmp = new T[newSize]; - Array.Copy(array, 0, tmp, 0, array.Length); - array = tmp; - } + int newSize = Math.Max(array.Length * 2, size); + var tmp = new T[newSize]; + Array.Copy(array, 0, tmp, 0, array.Length); + array = tmp; } } @@ -51,7 +47,7 @@ namespace Google.Protobuf.Collections public void Clear() { - array = null; + array = EmptyArray; count = 0; } @@ -62,10 +58,6 @@ namespace Google.Protobuf.Collections public void CopyTo(T[] array, int arrayIndex) { - if (this.array == null) - { - return; - } Array.Copy(this.array, 0, array, arrayIndex, count); } @@ -183,10 +175,6 @@ namespace Google.Protobuf.Collections { throw new ArgumentNullException("item"); } - if (array == null) - { - return -1; - } // TODO(jonskeet): Does this box for enums? EqualityComparer comparer = EqualityComparer.Default; for (int i = 0; i < count; i++) -- cgit v1.2.3