goc

我的一些 go 代码 自认为， 我的代码技术上应该不差， 但默默无闻， 大概是没有 readme 的原因 ：）

持续更新吧， 写到哪里算哪里： listhead 其实是 linux 内核里的那个， 挺有名， 弄成 go 以后和原始版本有点区别， 多少累赘一点 waitlist 是一个简单的等待链表的实现， 任意 go routine可以在上面等待被唤醒， 并且不会丢失事件 lkf 是一个我自己发明的无锁链表 trie 是一个 go版本的前缀树， 自己感觉语义灵活性上更好

有个skip list的小主意， 不值得贴完整代码了， 只将自己觉得有提高的地方放在这里： skiplist 有一个选择 level 的逻辑， 算是调用比较频繁的； 我看到的实现基本上都是做一个循环， 无论如何算是 O(N) 的复杂度， 我弄了一个 O(1) 的， c语言版本如下： #define chooseHeight(s)
({
uint64_t level = 0;
if (__builtin_expect(!list_empty(&s->entry[0]), 1)) {
level = ((uint64_t) lrand48()) % level_range(s->maxh) + 1;
level = (uint64_t) (__builtin_clzl(level) + s->maxh) - 64;
if (level > (size_t) s->height) {
level = (size_t) s->height + 1;
}
}
(size_t) level;
}) 这个依赖lrand48本身分布的均匀性， 不过这个如果不满足， 可以换成其他的。