你会得意的封装么？

passwords

有必要再封装

zx_wing

原帖由 OwnWaterloo 于 2009-12-4 16:07 发表
关于linux/list.h ... 我觉得吧。。。 就想flw说的。。。
C语言要实现链表……  动动脑筋就做成那样子了…… 并不一定就是抄袭linux/list.h

用C语言开发的，写了一个linux/list.h， 不能算抄袭吧……  
毕 ...

当然可以看懂后自己再写一个，这个完全没问题的。这是看懂了后自己做出来的东西。
但如果是直接拷贝，或拷贝过来修修改改则不行，这是抄袭。
当然有人会说我抄袭然后一口咬定就是我写的，这就留给打官司时律师判定了。

OwnWaterloo

那我放心了……

其实…… linux/list.h 真没什么值得炫的…… 所有操作是o(1)那是因为它不提供o(n)的操作而已
当然，这是很合理的做法。
只是别把它想成什么突破了……  人云亦云，听到说o(1)就不得了了，不去看看o(1)是怎么回事……


而关于linux/list.h 的设计……  说实话，我不需要它这种设计的时候，我怎么都没看懂（那时候基本不用C，无法从C的角度去想一些问题）
而我真正实现出这种设计之后，才恍然大悟，哦，这不就是linux/list.h嘛……

我把这种设计称为 intrusive data structure —— 侵入式数据结构。
既然是侵入式的，就代表这其实是一种妥协，以牺牲通用性（节点的通用性、而不是intrusive data structure的通用性）换取空间上的效率。
当然，这种妥协出现在kernel中也是非常合理的。

alexhappy

既然是侵入式的，就代表这其实是一种妥协，以牺牲通用性（节点的通用性、而不是intrusive data structure的通用性）换取空间上的效率。

啥是“节点的通用性、而不是intrusive data structure的通用性”？
我认为list.h的这种方式刚好很通用。。。

OwnWaterloo

list本身是通用的。 但list存放的节点不一定。

比如：
typedef struct {
     /*  ... */
} my_data;
这是我所需要的数据结构，是不能直接插入到list中去的。

如果，我只需要（无顺序的）遍历所有元素，可以放到list中，但要改变节点为：
typedef struct {
        intrusive_list_node_t list_node;
        my_data  data;
} my_data_in_list; // 放入list的，已经不是my_data了

如果，我的需求改变了，需要快速查询某个my_data，所以打算将它放入avltree中。
节点必须被改变：
typedef struct {
        intrusive_avltree_node_t tree_node;
        my_data  data;
} my_data_in_avltree;  // 放入avltree的，依然不是my_data


节点，和节点可以插入的容器，这2者是紧耦合的。

如果是glib那种，以void* 代表任意元素的话，就不存在这种耦合。
无论我是想将数据组织为list或者是avltree，我都不需要改变我的数据的定义、分配、以及使用。
当然，这会造成更多的内存分配、占用、以及碎片；还有对内存池的需求。

[ 本帖最后由 OwnWaterloo 于 2009-12-4 17:57 编辑 ]

peidright

当我想多个分支上的代码格式保持一致的时候，可能会封装一层。

比如sem_wait();我发现如果和别的代码需要组装的时候，会需要屏蔽某个信号，而我们自成一体的代码并不需要屏蔽，
我就不愿意修改我的代码，而是愿意更改封装个 sys_sem_wait();

OwnWaterloo

顺便提一下……  stl……

stl既可以实现为intrusive 也可以实现为 non-instrusive。而且对用户是透明的。
stl可以在实现为intrusive的情况下，也表现得如同non-intrusive一般，这也是我之前一直对linux/list.h不得要领的原因……。
它是依赖如下2个C++特性：
1. 模板
定义出 T_with_list_node
2. 操作符重载
再加上指针算术，使得iterator看上去就是一个T*的样子。

所以嘛，只要C++标准愿意，stl随时可以改为intrusive的。
只要肯把T_with_list_node给暴露出来，而不是将它藏到 operator* 之中。


至于boost.intrusive……  我就不知道……   这是在干嘛了……
不就是intrusive么……  居然会被设计得如此复杂……   不解……

alexhappy

原帖由 OwnWaterloo 于 2009-12-4 17:53 发表
list本身是通用的。 但list存放的节点不一定。

比如：
typedef struct {
     /*  ... */
} my_data;
这是我所需要的数据结构，是不能直接插入到list中去的。

如果，我只需要（无顺序的）遍历所有元素 ...

哦，我明白了，谢谢指点

OwnWaterloo

这……  担当不起……    怪我一开始没说清楚……  只抛出个结论……

cwinux_1

唉，怎么说你们呢！