【BNode】工具篇3：Basic容器-水波萌

前提

这一部分的参考内容在Blender文档的Core/BLI处，包括数组、列表等一些基础容器，在BNode项目中则位于Basic的命名空间下。

因为C++和C#语法不同，在读这些源代码的时候很难复制一些实现细节。一开始我想尽可能多地保留原来的特性，为此反复修改设计了很长一段时间却始终没有什么效果。后来，只能捉摸一下源代码的设计意图：避免拷贝，然后用一种具有C#特色的方式去尽量简化实现。就像List那样，值类型拷贝值，引用类型拷贝引用。

（在开发数个月后）为了保持一致性，在一些命名和使用方式上，我还是选用了更具有C#风格的方案。例如Blender里面喜欢默认某些容器是只读的，然后其可变的类型名字要加个Mutable前缀；C#则喜欢默认为可变类型，在只读类型名字前加上ReadOnly前缀。Blender中喜欢以“G”前缀表示通用的类型，它们用CPPType而非模板存储类型信息；C#中的“G”却经常表示泛型，因此这些部分被我起名为“M”前缀，表示使用了MetaType存储类型信息的容器。

除此之外，还有一些我个人偏好的命名规则，例如说AsArray和ToArray，我规定以As开头的方法，表示它们原本就属于（或者包裹了）Array类型，对其转换不会产生拷贝。

我自知不太会管理内存，所以所有代码都不开启unsafe。以上种种因素导致容器在行为上势必与C++中的有很大不同，但尽量做到简洁和优雅。

Bit

位相关的操作工具。Bit相关的工具把位存储在ulong中（通过下文中的容器），可以节省一些内存。

BitRef是对单个bit的引用（类似指针），通过位运算直接操作ulong数组中的特定位。BitSpan是对连续bit范围的引用（类似Span<bool>），支持切片、批量操作（如SetAll），用于批量处理一个范围内的位。BitVector是动态的bit数组容器（类似List<bool>），能够动态扩容。

值得一提的是，在C#中有个容器叫做BitArray，不过我没有怎么仔细了解过。位部分的工具基本都是小AI辅助完成，对此项目似乎用处不大，不多介绍。

IList扩展

在各种方法中，经常涉及到“多个数据”的操作。一般情况下要么使用数组，要么使用List<T>去作为参数类型。更好的情况是两种参数类型都支持，但这会造成大量的重复代码。一个有趣的特征是，Array和List<T>都实现了IList接口，那么只需要为IList接口编写方法就好了。

然后围绕IList做一些基础的事情，这样创建一个新的容器时，只需要实现很少的基础功能就能作为IList去兼容已有的方法了。

为需要实现IList/IList<T>但不支持扩容或删除的的容器提供默认空实现
为实现IList<T>的容器提供IList的默认实现
为实现索引器的容器提供IList的查找、拷贝等默认实现
为以数组为基础的容器提供IList/IList<T>等多种默认实现
为IList/IList<T>提供默认迭代器
允许通过一个现有的IList<T>实例去实现IList<T>接口，这在做装饰器时很有用
编写IList/IList<T>的多种扩展方法，涉及类型转换、填充、拷贝、搜索等

BArray和BVector

舍弃现成的C#同类容器去重复造轮子，或许对于调试、开发和扩展来说很有用，因为它们可以为此项目提供某些定制服务（包括隐式转换等）。

对于Blender中的多种容器，都用到了一个可内联的Buffer。C#中没有这种功能，我尝试写了个“具有内联风味”的容器，其本质就是一个可扩容的数组。以下介绍一些实现细节：

模板参数：C++中可以创建模板参数，C#虽然有泛型但却没有那么自由。例如C++在创建容器时可以用Array<int,16>这样指定内联容量，而C#却不行。如果作为构造函数的参数，又很繁琐。而这个内联容量（虽然C#中并没有真正的内联）又必须在初始化前赋值，因此也不能用new(…){InlineCapacity=…;}这样赋予。我的解决方式很简单粗暴，就是直接为不同内联容量分别写一个代表其具体数值的结构体，作为泛型类型传入即可。
size和capacity：size代表可用的数据长度，capacity代表容器的容量。有时候C#传递数组时比C++少一个size参数，使用数组的Length替代。虽然我实现的容器本质还是个数组，但是从ArrayPool中借来的，长度可能比需要的更长。另外，写一个size还可以实现假的扩容/清除，有时候很有用。
扩容：把数组返还给ArrayPool，然后再借个新的。如果需要保留数据，就再copy一下。

主要代码片段如下

    public interface IInlineCapacityValue { public int InlineCapacity { get; } }
    //分别代表内联容量为0、4的两种结构体
    public struct Inline0 : IInlineCapacityValue { public int InlineCapacity => 0; }
    public struct Inline4 : IInlineCapacityValue { public int InlineCapacity => 4; }

    //IArrayContainer接口将以数组为基础的容器自动实现IList相关功能
    //IFixedContainer接口表示不可进行添加和删除操作的容器
    public class ContainerBuffer<T, C> : IArrayContainer<T>, IFixedContainer<T>, IDisposable where C : IInlineCapacityValue, new()
    {
        private int _inlineCapacity;
        private T[] _dynamicBuffer;
        private T[] _inlineBuffer;
        private int _size;
        private int _capacity;
        private object _syncRoot = new object();
        bool IList.IsFixedSize => false;
        public int InlineCapacity => _inlineCapacity;
        // Data在get时始终对应当前数据所在数组
        public T[] Data => _dynamicBuffer ?? _inlineBuffer;
        public int Size { get => _size; set => _size = value; }
        public int Capacity => _capacity;
        public bool IsInline => Data == _inlineBuffer;
        object ICollection.SyncRoot => _syncRoot;
        // 创建一个容器，有效范围为(0,size)，容量为Max(size,InlineCapacity)
        public ContainerBuffer(int size)
        {
            ReallocBufferForSize(size);
        }
        public ContainerBuffer(IList<T> list)
        {
            var size = span.Count;
            ReallocBufferForSize(size);
            span.CopyTo(Data, 0);
        }
        // 用于初始化/重分配，不会保留数据
        public void ReallocBufferForSize(int size)
        {
            TryClearAndShrink();
            _inlineCapacity = new C().InlineCapacity;
            _size = size;
            if (size <= _inlineCapacity)
            {
                //我实现的“内联风味”其实就是提前租来足够长的数组
                _inlineBuffer = ArrayPool<T>.Shared.Rent(_inlineCapacity);
                _capacity = _inlineCapacity;
                return;
            }
            _dynamicBuffer = ArrayPool<T>.Shared.Rent(size);
            _capacity = size;
            return;
        }
        // 用于扩容，会保留数据
        public void EnsureCapacity(int requiredCapacity)
        {
            if (requiredCapacity <= _capacity) return;
            //双倍扩容
            int newCapacity = Math.Max(requiredCapacity, _capacity * 2);
            var newArray = ArrayPool<T>.Shared.Rent(newCapacity);
            Data.AsSpan().CopyTo(newArray);
            ReturnArray();
            _dynamicBuffer = newArray;
            _capacity = newCapacity;
        }
        private void ReturnArray()
        {
            if (_inlineBuffer != null) ArrayPool<T>.Shared.Return(_inlineBuffer);
            if (_dynamicBuffer != null) ArrayPool<T>.Shared.Return(_dynamicBuffer);
            _inlineBuffer = null;
            _dynamicBuffer = null;
        }
        public void TryClearAndShrink()
        {
            ReturnArray();
            _inlineCapacity = 0;
            _size = 0;
            _capacity = 0;
        }
    }

在此基础上去做Array或Vector这种容器就很容易了，为防止混淆命名为BArray和BVector。BArray不需要内联，所以始终传入Inline0。

我没有尝试去做一个类似于Blender中Span的工具。随着深入了解，我发现它在C#中使用Memory代替更为简便，因为经常需要获取原来的数组。但仍然编写了一个非泛型的MSpan，它的作用类似于C#中的ArraySegment但使用MetaType存储类型信息，表示数组的一部份。

IndexMask

索引掩码可以表示一些离散或连续的索引值，适合用来对大量对象的一部分进行批量操作。例如说，可以用一个IndexMask来表示{1,14-514,1919}这样的范围，并允许切片和进行范围间的交并补等操作。

Blender文档直接跳转到签名，一开始我没找到方法实现在哪。借助小AI和自己的理解实现了一个没有严格按照签名来的版本。这里说一下我的实现原理。假设有一个有序数组array{1,4,5,9…}，借助一个Segment结构体，它从array中借用一些连续范围的数字，然后统一加上一个偏移数，就可以表示一些索引。式子是array[start..(start+length)] + offset。例如说它的start==1，length==2，offset=10，就是借用4,5,9三个数然后加上10，最终表示14,15,19。

一个IndexMask里包含若干个Segment，这样就可以很好的表示大量索引值。每个Segment里最多包含16384个索引。这和C#里的ArraySegment有些类似。存在一个全局的有序数组，包含所有从0~16383的数。创建表示连续范围的IndexMask时，会从这个全局数组中借用。

后来在Internal里找到实现，和我的实现不太一样。Blender是把Offset、Length等Segment的数据统一放到IndexMask里，以批量管理内存。有趣的是，在这个过程中有一个巧合的发现：它用到了一个叫ExprBuilder的工具，这和我的表达式树构建工具恰好同名（虽然它们毫无关联）。