有没有c语言版的tuple, list, vector, hash等通用数据结构的实现？

prolj

glib就是从gtk分离出来那个所谓的贡献，很大很全相当复杂

cugb_cat

原帖由 drunkedcat 于 2008-6-5 16:51 发表


不好意思，误会了，我是说关于从一个结构中找到一个成员地址的方法，不是指 list 这个结构。

当时看了这段代码后，我就再也不敢在人前说我“熟悉” C 语言了。所以才说它“令人发指”。

内核中红黑树的代码更能提现什么叫做精致。
红黑树节点结构是这样的：

1. 
   
2. struct rb_node
   
3. {
   
4.         unsigned long  rb_parent_color;
   
5. #define        RB_RED                0
   
6. #define        RB_BLACK        1
   
7.         struct rb_node *rb_right;
   
8.         struct rb_node *rb_left;
   
9. } __attribute__((aligned(sizeof(long))));
   

复制代码

__attribute__((aligned(sizeof(long))))的意思是使这个结构体以sizeof(long)对齐，也就是以4字节或8字节对齐，这样对齐的地址有什么特点呢？就是地址的最后2位或3位为0,而这2位或3位就可以用来表示节点的颜色了。
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
这个宏的意思是得到该节点的父节点。

5毛党党员

struct rb_node
{
        unsigned long  rb_parent_color;
#define        RB_RED                0
#define        RB_BLACK        1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

果然令人发指。。。

guotie

虽然节省了空间，但增加了执行时间。

空间换时间，不值得。

dicky3651

kernel 中的这个实现真是……
不知道怎么来形容了，奇特得令人发指。
drunkedcat 发表于 2008-06-05 08:35

      与其说内核的List结构奇特得令人发指，倒不如承认对C不熟悉吧！正常链表是一个数据域一个指针域，但这样的可复用性低，所以Linux的List为每个项建立统一的结构，而每个这样的结构就由struct list_head 这个连接起来（相当于正常的指针域），但带来的问题是当做链表遍历只，我们遍历的只是list_head带来的指针域，要转化成实际数据就要转换，具体转换就是靠当中的一个求结构当中成员偏移量的宏定义，该宏很复杂，具体就不写出来，需要的可以找Linux内核当中的：\linux-2.6.32.8\include\linux\kernel.h（因为我家里那份代码是2.6.32）
      但操作可以介绍，先是以被遍历元素所在结构的结构作为类型，并将结构的起始地址强制转换成0，再指向要成员起始位置，就得到偏移量，现用结构中指针域所在的位置减偏移量，就可以得出指针域相对于成员的偏移量（我自己都说得口打结了，只有自己去看才真正明白）！

    操作要说复杂是很复杂，要说简单其实也挺简单，其并非为了让人看不懂，而是为了让该结构有高度可重用性并有一定效率！具体的参考一下C语言ANSI C 99 标准库的offset宏！

unistd

Kernel中的List的实现并不见得适合应用层使用，List的实现有好多方法，要看具体怎么用才能选择一个效率最好的方法。
另外宏中的

1. # #define container_of(ptr, type, member) ({ \
   
2. #         const typeof( ((type *)0)->member) *__mptr = (ptr); \
   
3. #         (type *)( (char *)__mptr - offsetof(type, member) );})

复制代码

typeof 哪里来的？ C 中没有typeof这个关键词吧。

bittertea

bsd下的sys queue.h这里实现了链表 队列 栈
sys tree.h这里实现了rbtree ,splay tree
后来又根据这种实现方式封装个堆的了minheap.h

freeradius里的hash tab不错
现在项目基本用这些

yulihua49

不好意思，误会了，我是说关于从一个结构中找到一个成员地址的方法，不是指 list 这个结构。

当时看 ...
drunkedcat 发表于 2008-06-05 16:51

    对于编译时可定义的结构，前边各位的意见不错。
如果编译时不知道，运行时才知道的结构（未知类，在JAVA里统称Object），怎么处理呢？

比如写一个 Tree，或list，数据域你只好给一个 void * data;或 char data[0];
暂且把这个东西叫‘框架’，框架不知道数据结构，也不会处理。
空间的分配和数据的处理都要通过参数和回调函数。应用提供的回调函数知道怎么处理数据。
使用回调函数会使人非常不舒服。

这是一个自上世纪70年代提出，至今未能圆满解决的问题，叫做“程序与数据分离”，现在有个词叫“程序与数据松耦合”。
与面向对象相反的。但是面向对象也提供一些松耦合方法，如泛型、抽象类，模板，反射等等。

jmy2446267

建议楼主看看 libcstl这个开源项目

liexusong

Kernel中的List的实现并不见得适合应用层使用，List的实现有好多方法，要看具体怎么用才能选择一个效率最好 ...
unistd 发表于 2011-06-04 07:16

    typeof是gcc扩展功能～