云风的 BLOG

和 zip 格式一样，我的包格式内部是平坦结构的，没有分目录。所有文件都是保存的完整的路径名聚合在一起。比如包里可能有如下文件：

bar.txt
bar/bar.txt
bar/foo.txt
foo/bar.txt
foo/foo.txt
foobar.txt

这个列表我经过了排序，是想在检索的时候可以快一点。有序的文件名可以二分检索。

我的虚拟文件系统的框架要求每个 fs 需要提供虚拟目录遍历的能力，比如在这个包内，如果需要遍历 bar 目录，就需要依次返回 bar.txt foo.txt 。如果需要遍历 / ，则返回 bar.txt bar foo foobar.txt 。

遍历的 api 形式上我用的一个 C 函数，叫做 enum_next 传入空指针的时候，返回第一项。传入非空指针的时候，返回下一项。若传入的是最后一项，则返回空。

这个 api 对实现上性能的要求并不算太高。因为在框架内，对遍历结果 cache 到了一张 hash 表内，下次查询的时候，是不用再次调用的。

我多年来养成的坏习惯，让我直觉上排斥愚笨的挨个比较的方法，（如果是这样，也不用排序了），而是采用了二分查找（这可以明显的提高检索性能一个数量级）。

由于有时候需要处理中间的子目录里的文件，在 enum_next 的时候就需要跳过。这就在跳过的时候再次使用一次二分查找。而且，这个跳过操作是需要二分查找返回一段数据，而不是一个的。

二分查找这件事，在 C++ 的 algorithm 模版中，是有 binary_search 来干这件事的。但是如果需要找到一个区间，则需要用 lower_bound 和 upper_bound ；而在 C 语言里，则有 bsearch 来做，我暂时不太清楚有没有对应的 lower_bound 等函数来获得区间的功能。

还是我的坏习惯，导致我第一反应就是自己来写这段查找代码。我对自己的编码能力非常自信，觉得完全不会出错。这样，我就不需要去编写那个比较用的回调函数了。甚至可以把整个复杂操作放在一个大循环里高效的完成。

可惜最终还是出了 bug ，倒不是出在二分查找的循环上，而是我想当然的认为，一个目录下的文件名，经过排序后，子目录里的文件名一定排在前面。然后在默认这个前提下，写了一大坨代码。最后出错了，回头又怀疑自己算法实现有误，前后查了一个多小时 :( 。比如在这个例子中，bar.txt 就排在了 bar/bar.txt 的前面。

其实这个 bug 是完全可以在编写的时候避免的。我犯了许多经典错误：

1. 过早优化（这个可以商榷，虽然不是热点，这种明显的优化我认为还是可以顺手做的。不然永远都不会有人做。即使在某种特定环境下，它变成了热点）

2. 没有尽可能的分解算法。（觉得这个问题足够简单，不需要分的太细。性能方面的思考作祟，想尽量减少不必要的层次）

3. 没有使用现成的算法库。这一点跟 C 库在这方面略显单薄有关。不过如果用 C++ ，估计我也会比较反感那些需要自定义比较函数的算法模板。