Red Black Tree в Linux

Я работаю над проектом ядра Linux, который включает в себя использование rb_tree, определенного в rbtree.h. Вот структура, что я храню в дереве:Red Black 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

Кроме того, число, которое я храню в полях источника и кеша, отличается, когда я извлекаю стойки из дерева. Например, я бы сохранил число 512 в исходном поле, и когда я получаю структуру позже, это будет какое-то смехотворно большое число, например 16810075660910329857. Из того, что я понимаю, sector_t является длинным длинным целым без знака. Зачем менять число? Почему типы указателей несовместимы?

источник

2013-06-09 Gregory-Turtle

Как вы можете передать struct source_store в качестве второго параметра - это тип данных, а не переменная. Кроме того, что такое прототип 'rb_entry'? – user93353

В соответствии с этим руководством: http://lwn.net/Articles/184495/, тип должен быть передан. Прототип: rb_entry (указатель, тип, член); где member - это имя узла в содержащей структуре. rb_entry - это просто оболочка для container_of(). –

Это потому, что 'rb_entry' является макросом, а не функцией. Вот почему вам нужно было предоставить эту информацию в вопросе - определение rb_entry. – user93353

Вы должны определить ваш 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*. Поэтому есть предупреждение о несовместимом типе указателя.

источник

2013-06-09 05:43:40 Naruil

Red Black Tree в Linux

ответ

Смежные вопросы