云风的 BLOG: sequence 的 C 实现

这段时间一直在写代码，大约一周三四千行的样子。所以没有什么闲余时间写 blog 。可能再过段时间可以总结一些想法吧。

我这几年一直用 C 在做设计和编码（当然还写了许多 Lua 程序）。也一直在纠结，到底，我们在系统编程中，最少的需求是什么。C++ 给了我们太多，但是 C 又给的太少。如果常年用 C 写程序，那么必须多一点。

比如基础数据类型，在《C语言接口与实现》中叫作 ADT 的东西。给出了许多。我还是觉得多了点，其实用不了那么些。

其中 atom 是必须的，在我的系统中，给了个不恰当的命名，但是本质是一样的。以前写过一篇 blog 讨论过。

因为 Lua 用的太多，感觉字典是个很有用的东西，所以我实现了一个基本的 hash map 。

然后，用的比较多的是变长数组，以及用于收发消息的队列。这个东西实在是太简单了，我一直没有单独实现成一个独立模块，都是随用随写。也不大容易写错。但是写了这么多年，我还是想把它抽象出来。和同事讨论的时候，Soloist 同学提醒我，其实我想要的 ADT 就是 sequence 。

一个可以方便的从两头插入，从两头删除，可变长，可以高效随机访问的 sequence 。在《C语言接口与实现》里把这个东西简写为 seq ，在 Haskell 里也是。

为什么我一直从心里排斥把 seq 做成独立模块，我想是我的追求高效的坏习惯在作祟。虽然这个习惯很不好，但是我总觉得明明可以用一个原生数组来做这件事情，用个指针就可以遍历了，何必多几次函数调用，和数据访问的间接性呢。

固然，C++ 的 STL 提供了一个折中的方案，把代码都写到 .h 里（使用 template ），利用编译器去优化 inline 代码。但是却在源代码中暴露了数据结构的实现细节。今天的我看来，这是更不可以容忍的事情。（不同意这个观点的同学请原谅我的偏执）

从昨天开始，我又一次仔细考虑了这个问题，并花了今天一天的时间，实现了一个让我还算满意的 seq 模块。

隐藏内部细节，总会有一些性能损失。那么，哪部分我所关注，而哪些是可以容忍的？

IMHO ，我希望让 seq 的遍历可以最到最高效，就同用一个 for 循环以及 int 类型的 i 去迭代它一样高效。读写 seq 里的数据也希望是高效的。而从两头插入和删除数据，则是可以承担性能损失。

seq 的内部数据结构应该隐藏起来。大部分操作也仅以 C API 形式提供。seq 要可以可变长。并在内存上连续（读写性能最好）。

最终的设计，我用一个数组模拟了一个循环队列。并暴露了一个迭代器的数据结构。这个迭代器大多数情况下能够也只允许在栈上构造。这里使用了 C 的一个小技巧，是学习的 jmp_buf 的定义。这样，这个被我称为 seqi 的数据类型，就可以直接在栈上声明，并以指针形式传递了。

struct seq;

struct _seq_iterator {
    struct seq *seq;
    void **begin;
    int offset;
    int length;
};

typedef struct _seq_iterator seqi[1];

由于 seq 是可变长的，迭代的过程又需要足够高效。我选择在 seq 本身变化的时候再去通知迭代器，而不是在迭代的时候去查询。所以迭代都需要向 seq 本身登记。

另外，我在迭代器里记录了一块连续内存空间，迭代器在这个区间内是可以自由前移后移，读写数据的（用 inline 函数或宏来实现）。只有超出这个范围，才需要调用更重量的 api 。

由于 seq 的内部实现中，数据区是由两块连续空间构成（循环利用），这个维护工作稍显重量，幸运的是，大多数情况下，我们不会进到这个分支。

这几个相关函数被我定义成：

void seq_head(struct seq *s , seqi iter);
void seq_tail(struct seq *s , seqi iter);
void seq_close(seqi iter);
void seq_update(seqi iter);

static inline void
seq_inc(seqi iter)
{
    ++iter->offset;
    if (iter->offset >= iter->length) {
        seq_update(iter);
    }
}

static inline void
seq_dec(seqi iter)
{
    --iter->offset;
    if (iter->offset<0) {
        seq_update(iter);
    }
}

static inline bool
seq_isvalid(seqi iter)
{
    return iter->begin != 0;
}

static inline void*
seq_read(seqi iter)
{
    return *(iter->begin + iter->offset);
}

static inline void*
seq_write(seqi iter, void *v)
{
    *(iter->begin + iter->offset) = v;
    return v;
}

使用起来比较方便，看起来就是一个 for 循环，而且在性能上也非常接近原生数组：

seqi iter;
for (seq_head(s,iter);seq_isvalid(iter);seq_inc(iter)) {
    printf("%p\n",seq_read(iter));
}

一个简化设计的约定是，一旦一个 seqi 变得无效（比如迭代到 seq 一端，或是引用的数据被 pop 出去），那么永远就不可能再使它有效。我就可以简单的在 seqi 中标记出这种情况（使用 seq_close 把 begin 字段置空，且在 seq 内部注销）

我们同时保有的 seq 迭代器不会太多，在 seq 结构中开辟有限空间存放引用即可。

剩下的一些 api 列在下面：

struct seq * seq_create(int hint);
void seq_release(struct seq *s);
void seq_pushhead(struct seq *s, void *v);
void seq_pushtail(struct seq *s, void *v);
bool seq_empty(struct seq *s);
void* seq_pophead(struct seq *s);
void* seq_poptail(struct seq *s);
void seq_clear(struct seq *s);
int seq_size(struct seq *s);

主要就是用来从两端压入和弹出数据的，或者清空整个结构（同时注销所有正在使用的 seqi ）。对于 release 方法，除了使用相关内存外，还可以附带检查所有迭代器使用注销。这可以帮助派错。我觉得，约定所有的迭代行为都比较进行完整（从一端都另一端）是比较合理的。实在要破坏这个约定，可以自己调用 seq_close 方法。

seq 的实现要点还在于，在迭代过程中，向两端的任意一边压如数据要保证安全。否则就没什么实用价值了。

还可以考虑的功能是对 seq 进行排序以及二分查找。

嗯，实现代码不难写，就不列出了。不过想实现的高效还是挺麻烦的，也容易写错。优化是万恶之源啊。

这两天，我们办公室里讨论 google 的新语言相当热闹，不过我还没有想好该写点什么。我们创建了一个 wave(不再提供链接，昨天有人放了个 twitter 机器人把帖子弄坏了，投票丢了:( ) 来讨论这它。悲剧的是 Go 的官网 http://golang.org 被墙了 :( 。

暂时看来 Go 还是一个实验性的语言，不过它满足了我对系统编程语言几乎所有的梦想：快速编译，可链接，Coroutine、Closure （这两个东西是用 Goroutine 实现的），静态类型，鸭子类型，原生的 string 、map 类型，完善的包依赖机制，gc …… 并没有特别花哨多余的东西。Ken Thompson 大神和 Rob Pike 大神杵在那里，绝对是品质保证啊。

好吧，还说漏了一个优点：不支持 Windows 。

Comments

struct B {int x;};
struct D {union{B b;struct{int x;};};
int y;
};
这样就可以继承了

Posted by: htzyhtzy | (22) September 26, 2010 03:38 PM

嗯,看来云风还是纠结在语言/数据结构上啊.
对于云风个人这样的做法,我是完全支持赞同的,但是呢,对于其他绝大部分程序员,我建议你们不要学云风.
一,你没有云风这么深厚的底子(我也没有)
二,搞不好你年纪比云风还大(我也是)
三,你精力没有他旺盛(我还是)
四,你可能有生活压力,目前看来,云风是没有的(我有,两孩子...)

那么,你怎么在这个行业里混出点名堂呢?

这是我在2002年离开网易的时候思考的.事隔多年,连当初把我从网易弄走的前前前任老板都说我错过了网易发展最好的时机,少挣了不少钱,心里有愧(有愧也没有多请我搓两顿),但现在看来,也未必是坏事.离开网易后,我认为,想追随云风的脚步,最后的结果就是永远落后于他,想超越他,就不能在他最优秀的地方跟他火拼,最后的下场一定是你死了他还活着.

那么出路在哪里?

我认为,在语言/数据结构/算法合格的基础上,应该追求某个专业领域的精通.后来我选择了往3D方向发展,经过几年沉淀,终算衣食无忧了.

Posted by: tearshark | (21) December 6, 2009 10:56 PM

哦,刚发贴发现一个问题,6 + 1的结果才是7, 而六加一的结果应该是七才对, 云风这个人类验证不太严谨:D

Posted by: JiChong | (20) November 23, 2009 05:22 PM

Posted by: Anonymous | (19) November 23, 2009 05:19 PM

强烈赞成2号Anonymous的观点, "我倾向于把C++当成C语言来用使用C++的函数重载、继承、模板"

Posted by: JiChong | (18) November 23, 2009 05:17 PM

还是放下代码吧，我是初学者，写不出来。谢谢。

Posted by: Anonymous | (17) November 18, 2009 04:22 PM

代表广大用windows环境的表示不爽!云风不要把除已之外的选择说得一无是处

Posted by: lichking | (16) November 18, 2009 03:47 PM