Red Black Tree in Linux

Question

I am working on a Linux kernel project that involves using the rb_tree defined in rbtree.h. Here is the structure that I am storing in the tree:

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

In order to retrieve objects from the tree, I do the following:

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

However, when compiling, I get this error:

warning: initialization from incompatible pointer type

Also, the number that I store in the source and cache fields are different when I retrieve the struts from the tree. For example, I would store the number 512 in the source field, and when I retrieve the struct later on, it would be some ridiculously large number like 16810075660910329857. From what I understand, sector_t is a long long unsigned integer. Why would the number stored change? Why are the pointer types incompatible?

Answer 1

You should define your struct source_store as:

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

That is because rb_entry is defined as

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

And it is just some simple offset calculation

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

The type of __mptr is struct rb_node** and the type of your ptr is struct rb_node*. So there is a warning of incompatible pointer type.