1. StringAtom
设计需求:
1. 集中管理字符串,对于资源标识型字符串一般没有改变内容的需求,所以相同内容的字符串在内存中只存在一份拷贝;
2. 通过比较字符串的首地址,来避免字符串比较中O(n)的时间复杂度;
3. 多线程应用中,为了避免stringatom的数据读写竞争,设计了localstringatomtable和globalstringatomtable;
组织方式:
stringatom是用户唯一需要关注的类;
在后端有localstringatomtable和globalstringatomtable,以及用来存储字符串拷贝的StringBuffer.
只有globalstringatomtable包含StringBuffer,并且globaltable里维护了所有字符串的句柄;
在多线程环境下,在每个线程函数的入口会定义一个localtable(ThreadLocal);
线程访问自身的localtable不用互斥,访问globaltable必须互斥;
各个线程定义新的字符串会走如下步骤:
1. 在localtable中查找string,找到了就将制作记录到stringatom中并返回, 否则2;
2. 在globaltable中查找string,将指针记录到localtable,否则在globaltable的StringBuffer增加字符串,再将指针记录到global/localtable,再返回刚刚更新到localtable中的字符串指针;
为了保证local/globaltable中存储的字符串指针信息一直有效, 对StringBuffer的特性做了如下限制:
1. StringBuffer只可能增长,而绝不会缩小;
2. StringBuffer的数据结构是多个buff的列表,当最后一个buff的空间不足时,就开辟一个新的buff,并且加入到buff列表中;[保证已有字符串的绝对逻辑地址无变化]
3. 只支持新字符串的Append操作,不会改变以前字符串的缓存位置;
Foundation-Util
- BitField. 采用模板类机制将位操作扩展到n个字节, 而不仅限于基本整型数据;
- Variant, 一个'任一类型'的类, 支持了Nebula3中大部分的内建数据类型;
- String, 字符串类型: TODO:
- Array 动态数组类, 同时作为很多其他容器的基础;
- 起初不分配内存, 第一次插入元素会分配16个元素的内存;
- 当超过当前元素上限, 会以当前的两倍大小重新分配内存空间;
- 借用STL的sort来实现排序接口;
- FixedArray 非动态增长的一维数组类:
- 调用SetSize接口设置数组长度的时候, 长度就固定下来, 如果再次调用此接口, 将回收掉之前分配的内存, 再按照新的长度分配内存空间;
- Resize接口会重新调整动态分配内存大小, 并拷贝数据;
- 与Array不同的是: 只有Fill接口去填充元素, 而没有Add接口去追加元素;
- PriorityArray 非动态增长的优先特性数组: 为每个数组元素指定一个优先级值;
- Stack, FILO容器;
- Queue: FIFO容器, 在Array的基础上包装并且抽象了Queue接口; TODO: DeQueue涉及到内存拷贝,性能开销;
- RingBuffer: 在固定大小的数组上环式地存储数据, buffer满的情况下插入数据会替换掉最老的数据;
- FixedTable 非动态增长的二维数组;
- Blob 将一块无规则的内存数据包装成对象, 使其可以拷贝,比较,hash;
- Delegate 代理类; 在一个代理类对象中将被代理的对象和指定方法记录下来, 供之后的某个时间点调用; [revise later]
- 应用: 消息过程绑定和延迟处理, 在前期建立一个消息与代理对象之间的映射, 在后期通过一个消息在不同被代理对象上调用之前注册的方法;
- 参见DelegateTable, Nebula3目前有这个准备, 貌似还没有使用这个机制;
- KeyValuePair 键值对, 被用在Dictionary和HashTable这样的关联性容器中;
- Dictionary:
- 在Array的基础上实现, 在插入过程中保证元素按照Key排序, 通过Key以O(logn)的时间复杂度获取元素;
- 插入为数不多的元素, 直接插入即可, 在内部保证每次插入后都是SortedArray;
- 如果插入较多元素, 使用批量插入接口: BeginBulkAdd + Add + EndBulkAdd, 每次Add将元素追加入到数组后, 在EndBulkAdd时再对数组进行排序;
- 在Begin和End如果调用要求SortedArray的接口, 那么会报错;
- HashTable, 查找的时间复杂度为O(1):
- HashTable采用桶链式数据结构, 桶采用了FixArray类, 链采用了Array类;
- 每个元素以Key-Value的形式存储, 其中Key必须要实现HashCode方法, Value是可以是任意类型的数据;
- HashCode相同的元素在同一个桶中, 并且链中的元素按照Key进行了排序;
- 和Dictionary比较: 虽然查找时间复杂度小一些, 但是内存开销较大;
- 为了在查找和插入过程中产生较少的冲突, 一方面需要选择合适的桶的大小, 另外一方面要选择合适的HashCode算法;
- List, 双向链表:
- 由于List中的每个节点可能存在与内存空间的各个位置, 通常使用动态数组来使得内存可控;
- 但是如果对插入和删除的操作性能要求较高, 那么才会考虑使用List;
- SimpleTree, 将Node简单地存储到Array中来实现;
- QuadTree, 四叉树;
- SparseTable, 稀疏表; TODO;
- RandomNumberTable: 基于表格的随机数生成器:
- 初始化会在表格中填充[0~1]之间的小数, 调用Rand接口会根据需求对小数偏移和缩放, 并返回值;
- 将对最终数值的随机, 转化成对数据偏移量的随机;
- 特性: 给定偏移的情况下得到的随机值是固定的;
- GUID, 全局统一标识符, 在各个平台上有不同的实现;
- Round, 将数值向上取到最近的2^N;
- RunLengthCodec, 游程编码, 在数据较为随机的情况下, 编码结果可能比原数据还要长;