云风的 BLOG

迁移到自己的分支上后，我们陆续对 RmlUI 的代码进行了不少重构。

最近，发现了 RmlUI 原有的一个 Bug ，有时修改了一个 css 节点属性后，会影响另一个不相干的节点的属性。仔细研究后，判断这是它固有的设计失误造成的。

我们知道，css 非常灵活，每个节点的属性都可以被很多数据源影响。如果我们不做任何优化，推导一个节点上的属性会是一个相当昂贵的操作。所以，必须对其做一些缓存。

而 RmlUI 的属性缓存算法有一些设计问题，它是根据节点的 C++ 对象指针做缓存索引的。这势必会因为对象的删除重建所影响。（因为内存指针的值有可能重复）且这部分代码实现的非常繁杂，我思考后觉得重新设计和实现会更好。

首先定义问题：

每个节点的属性表其实是一个 kv 对的数组。其中 k 是一个 enum ，范围不大（小于 100 种）且不会重复；v 是一个对象。而这个对象一定可以从文本序列化而来（因为源头的数据都是用文本书写的）。

这些属性表是由若干属性表合成的。合成方式有两种，从预定义的类型中继承以及从 DOM 的父节点继承。后者会受属性是否可以继承所影响，哪些属性可以从父节点继承是一开始就确定好不会改变的。

每个节点最终的属性表会以一种特定的次序从若干属性表合成而来。

如果我们把属性表看作一个对象，那么合成表 A 和 表 B 就能视为 A * B ，其中 * 是合成操作。每个节点上的表都可以看作是一串数据表连续合成操作的结果 A * B * C ....

如果我们要做缓存，就应该缓存任意两个表 A * B 的结果，即可提高性能。

我们可以把属性表分成两类，一类是元素数据表，一类是两张表的合成结果。对于前一类表，由使用者来维护其生命期，而后者可以完全由缓存模块管理。因为一旦缓存失效，使用者都可以想办法重建它们。

我用 64bit ID 来指代属性表（其中奇数用来指代数据表，偶数用来指代合成表），如果数据表被释放，或合成表从缓存中消失，ID 不会回收，这样，我们很容易知道哪些 ID 还是有效的，哪些已经无效。

至于属性表的内容，可以额外再做一层 Cache ，对它们 Interning 。相同内容的属性表内部其实指向同一份数据。

对于合成表，一开始只用记住引用的是哪两张表，合成操作可以推迟到最后的求值之前。如果有源头表改变，那么需要清理之前的合成结果。

我在实现以上想法的时候，专门思考了内部的数据结构该如何设计更好。其中有点意思的是关于合成表的 Cache 的结构。

所有的合成表都是由 Cache 管理的，用户不复杂它们的生命期。即，如果你计算 A * B = C ，那么 C 的生命期是不用自己管理，但做（弱）引用。既然是 Cache 管理，就有失效的时候。因为每个节点上的表都是一系列表联合作用的结果，所以当结果失效后，用户直接把合成过程重新做一遍即可。这个过程可能很长，我们需要尽量 Cache 中间变量。

合成表首先应由一个 LRU 队列所管理。我直接使用了一个固定大小（4095）的数组，内部用双向链表串起来。这样，对任何一张表求职，都可以方便的把它调整到队列的最前面。

然后，我们需要两种途径快速索引 LRU 队列中的对象。从 ID 索引，以及从两个 ID 的组合索引。即，如果 A * B = C 计算过，那么从 (A, B) 可以快速索引到已经创建过的对象 C 。

每张索引表我采用一个 8191 大小的数组作 hash 表。它的大小比 Cache 大一倍，所以几乎不应该碰撞。但碰撞从理论上无法避免，在解决碰撞冲突上，我的设计比较特殊，既不是开散列表，也不算闭散列表。

我用 64bit 为一个 slot 的大小。因为原始数据是 4095 ，也就是 12 bits ，这个 slot 可以放下 5 个索引值，也就是说，理论上，最多可以碰撞 5 次。如果某个 hash 值真的碰撞了 5 次（非常罕见），那么就需要遍历整个 LRU 队列查找是否有第 6 个值。

附代码：https://github.com/cloudwu/stylecache