今天周末，桌游店里却没客人，昨天打电话预约的朋友没来，所以我就奔到办公室测试上周写的代码。
上周的工作主要是设计了一个新的包格式，然后整合入前段时间实现的虚拟文件系统中。
这个工作和前段实现的 zipfs 有相似之处，所以做起来也很快。不过前面没仔细测试。今天比较闲，就设计了几组复杂的测试数据，感觉覆盖了各种边界情况。一测试果然发现了 Bug 。
这个 Bug 有点启发意义，所以在解决掉之后，决定记录一下。
和 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 是完全可以在编写的时候避免的。我犯了许多经典错误：
过早优化（这个可以商榷，虽然不是热点，这种明显的优化我认为还是可以顺手做的。不然永远都不会有人做。即使在某种特定环境下，它变成了热点）
没有尽可能的分解算法。（觉得这个问题足够简单，不需要分的太细。性能方面的思考作祟，想尽量减少不必要的层次）
没有使用现成的算法库。这一点跟 C 库在这方面略显单薄有关。不过如果用 C++ ，估计我也会比较反感那些需要自定义比较函数的算法模板。
