c - Linux 中的红黑树

Question

我正在从事一个涉及使用 rbtree.h 中定义的 rb_tree 的 Linux 内核项目。这是我存储在树中的结构:

struct source_store{
    sector_t source;
    sector_t cache;
    struct rb_node * node;
}

为了从树中检索对象，我执行以下操作:

struct rb_node * parent = root->rb_node;
struct source_store * store = rb_entry(parent, struct source_store, node);

但是，在编译时，我得到了这个错误:

warning: initialization from incompatible pointer type

此外，当我从树中检索 strut 时，我存储在源字段和缓存字段中的数字是不同的。例如，我会将数字 512 存储在源字段中，当我稍后检索结构时，它会是一些大得离谱的数字，如 16810075660910329857。据我了解，sector_t 是一个 long long unsigned integer。为什么存储的数字会改变？为什么指针类型不兼容？

Answer 1

你应该将你的struct source_store定义为:

struct source_store{
    sector_t source;
    sector_t cache;
    struct rb_node node; // not a pointer to node
}

那是因为rb_entry定义为

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

这只是一些简单的偏移量计算

#define container_of(ptr, type, member) ({             /
         const typeof( ((type *)0)->member ) *__mptr = (ptr);  /   <--error happens here
         (type *)( (char *)__mptr - offsetof(type,member) );})

__mptr 的类型是struct rb_node** 而你的ptr 的类型是struct rb_node* .所以有不兼容指针类型的警告。