Интересуют преимущества и недостатки этих двух подходов к реализации связных списков.
glib:
struct GList {
gpointer data;
GList *next;
GList *prev;
};
next и prev указывают на такой же GList
linux:
struct list_head{
struct list_head *next;
struct list_head *prev;
};
struct my_cool_list{
struct list_head list; /* kernel's list structure */
int my_cool_data;
void* my_cool_void;
};
То, что вижу я:
1. Реализация в linux требует на sizeof(void *)*N байт меньше, чем реализация в glib, где N - количество элементов в списке.
Why so?
glib = N * { sizeof(next_ptr) + sizeof(prev_ptr) + sizeof(data_ptr) + sizeof(data_struct) }
linux = N * { sizeof(data_struct) + sizeof(next_ptr) + sizeof(prev_ptr) }
То есть, нет N штук data_ptr.
2. Мне кажется, модель списков в glib более интуитивно понятная.
Плюс, в linux list_head структура сама определяет, в каких списках она может хранится. Если я захочу добавить возможность вносить структуру в список, у меня есть 2 варианта:
а) изменить код структуры и добавить туда еще один list_head;
б) написать структуру-обертку и использовать уже ее.
То есть, код получается зависимым от того, что сделал разработчик. В linux такое можно легко использовать, поскольку сорцы открыты, либо закрыты полностью (есть только unmodifiable headers).
Опять же, неудобно каждый раз писать структуру обертку
struct my_struct {
int a;
struct list_head list1;
};
struct my_struct_add {
struct my_struct datal
struct list_head list2;
};
для добавления возможности вставлять структуру в списки.
Гораздо проще в данном плане использовать модель GLib, где _любой_ объект может быть добавлен в список.
3. Реализация list_head оперирует сдвигом для определения указателя на структуру по указателю на list_head.
void *mystruct_ptr = mylist_ptr - &(((struct mystruct *)0)->mylist_head);
Насколько это портабельно между различными компиляторами?
Тема интересная, посему - lets discuss begin!
