Как пример макроса foreach

/**
 * __list_for_each	-	iterate over a list
 * @pos:	the &struct list_head to use as a loop cursor.
 * @head:	the head for your list.
 *
 * This variant differs from list_for_each() in that it's the
 * simplest possible list iteration code, no prefetching is done.
 * Use this for code that knows the list to be very short (empty
 * or 1 entry) most of the time.
 */
#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)


/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     prefetch(pos->member.next), &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

> Начал глубоко изучать list_head

«Читал list.h. Много думал» почти (с)

Что хотел сказать?

1й вариант, только не нужен целый «мусорный» объект, нужна лишь структура list_head - указатель на список.

> Что хотел сказать?

Поиздеваться над нубом.

P.S. в качестве головы списка используй, ВНЕЗАПНО, struct list_head.

Нда... И эти люди ковыряются в ядре. Ты действительно не знаешь как устроен список, или просто прикалываешься?

Вот, я тоже так думал, но тогда задался таким вопросом:

у меня есть

struct main_obj {
struct list_head child_objects;
};

struct child_obj {
struct list_head list;
};

struct main_obj m;

Допустим, у меня есть уже несколько child_obj в main_obj.child_objects списке. Я хочу проитерировать по всем child_objects и делаю list_for_each_entry.

#define list_for_each_entry(pos, head, member)            \
   for (pos = list_entry((head)->next, typeof(*pos), member);   \
        prefetch(pos->member.next), &pos->member != (head);    \
        pos = list_entry(pos->member.next, typeof(*pos), member))

НО ТОГДА на последней итерации я сделаю list_entry для main_object->child_objects, и только потом проверю на pos->member != (head)

Это ведь может привести к ошибке?

Пока нубом выглядишь здесь только ты. Если тямы не хватает нормально ответить, зачем тогда вообще писать?

Давай, крутой, объясни, как он работает.

>однако, смущает наличие мусорного объекта.

Он не нужен. См. например http://lxr.linux.no/#linux+v2.6.39/include/linux/sched.h#L1294

children — точка входа в список.

siblings — сами head'ы списка (В boost они логично названы «hooks»).

Кстати с прошлого раза когда я смотрел исходники ядра наконец-то добавили документацию о том, какой list_info — точка входа, а какой — сам список. Хорошо бы так было по всему ядру.

> Пока нубом выглядишь здесь только ты

...и только в твоих глазах %)

Если тямы не хватает нормально ответить

Я и нормально ответил.

intrusive списки могут показаться странными когда видишь их впервые. Даже если до этого работал с обычными списками.

Давай, умный, ответь на [c][linux][kernel] Не могу понять list_head (комментарий) вопрос 2 постами выше

Харе тут ЧСВ демонстрировать :)
Интересно же :) Давайте по теме :)

>НО ТОГДА на последней итерации я сделаю list_entry для main_object->child_objects

Не сделаешь. list_for_each пропускает первый элемент.

> Давай, умный, ответь на

Утипути. Родной, ты правда думаешь, что после просьбы в таком тоне я пойду по некликабельной ссылке и начну тебе что-то объяснять?

> Утипути. Родной, ты правда думаешь, что после просьбы в таком тоне я пойду по некликабельной ссылке и начну тебе что-то объяснять?

а что ты планируешь делать? дальше поднимать ЧСВ за счет новичка?

Тогда какого хера ты тут вообще пишешь? Это не толксы, утипути.

На _последней_ итерации, не на первой! Я понимаю, что последняя итерация приведет к list_entry с указанием в качестве type main_struct, хотя на самом деле должен быть child_obj.

Если так, что, скорее всего, это может с какой-то вероятностью привести к ошибке обращения к памяти по левому адресу.

Последний элемент снова указывает на голову списка. Как только pos на нее попадет, ты вылетишь из цикла по «&pos->member != (head)».

Или я тебя не понял?

Скорее всего обращения к памяти просто не происходит.

Хоть ты и получаешь указатель на мусор, но обращения к этой памяти не происходит. Единственное что известно про этот указатель, что если привести его к типу typeof(*pos) и взять поле member, то там будет корректный list_head.

Посмотри как реализован list_entry, там вообще используется нулевой указатель для получения смещения поля структуры (насколько я помню)

Вероятно, я не ясно обрисовал ситуацию.

Итак, есть две структуры: главная и дочерняя. Есть список дочерних структур. Доступ к этому списку дочерних структур должен быть у главной структуры

Этот доступ делается через фиктивный list_head, который хранится в главной структуре. Он же представляет собой голову списка, но _никаких данным за ним не хранится_, ибо он лежит в главной структуре.

Итак, я добавил в этот список несколько дочерних структур (понятно, у них есть свой list_head). Теперь я хочу пройтись по этому списку макросом foreach_entry.

Вот здесь для меня возникла загвоздка.

У меня ВСЕ list_head-ы, кроме ПЕРВОГО, лежат в дочерних структурах. Это значит, что в макросе

#define list_for_each_entry(pos, member, head) \
	for (pos = list_entry((head)->next, typeof(*pos), member); \
		&pos->member != (head); \
		pos = list_entry(pos->member.next, typeof(*pos), member))

когда я дойду до реально последнего элемента - последней дочерней структуры (выполнится 3-й блок цикла for), проверка &pos->member != (head) даст TRUE, поскольку это так.

Далее я обработаю своим кодом эту структуру и снова выполнится код 3-го блока цикла for

pos = list_entry(pos->member.next, typeof(*pos), member)

ВОТ ЗДЕСЬ структура по адресу pos->member.next хранится уже в ГЛАВНОЙ структуре, а не в дочерней.

Вот проблема, которую я вижу. Может,я ошибаюсь?

Да,я знаю как он реализуется, но сам факт получения невалидного адреса смущает

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

ВОТ ЗДЕСЬ структура по адресу pos->member.next хранится уже в ГЛАВНОЙ структуре, а не в дочерней.

Вот проблема, которую я вижу. Может,я ошибаюсь?

И еще - после получения указателя на struct child_obj в переменную pos - это реально будет strut main_obj *. И тогда проверка во 2ом блоке for даст хрен знает что.

Здесь я запутался.

Что за дочерние структуры? И какое она имеет отношение к списку?

list_head такой?

struct list_head {
	struct list_head *next, *prev;
};

это реально будет strut main_obj *

Это не обязательно будет struct main_obj, но вот такой код:

&((struct child_obj*)pos)->list

Да.

Мне кажется, ты ошибаешься.

pos->list ==> struct list_head

& pos->list ==> struct list_head *

Вот как они задумали:

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
        return head->next == head;
}

Да, именно поэтому я заключил, что должен быть «фиктивный» list_head внутри структуры, которая контолирует списо.

См. в файле kernel/time/clocksource.c как объявляется и используется переменная watchdog_list

Мог бы ты, пожалуйста, объяснить, как использовать list_head в такой ситуации:

Есть связный список структур struct child_obj. Ясное дело, в ней есть list_head, которым они «соединены.»

Этот linked list должен как-то хранится в структурe struct main_obj и обрабатываться функциями, работающими с этой структурой.

Как лучше всего хранить информацию об этом списке в struct main_obj?

Так как ты написал выше.

>Вот проблема, которую я вижу. Может,я ошибаюсь?

pos = list_entry(pos->member.next, typeof(*pos), member)

pos будет указывать на некоторое отвлеченное место, отступ до которого от головы списка будет такое же, как соответствующее в дочерней структуре. Вычисление pos перед последней проверкой нужно только для арифметики.

Да, это верно, я уже поговорил с rostedt на irc://kernelnewbees.

Бл__ь, как я сразу не понял про одинаковые сдвиги...

Однако остается открытым вопрос - этот «неизвестный» сдвиг от &main_obj.child_list - SMTH не вызовет ошибок обращения к памяти, например, при отсутствии доступа?

Вопрос закрыт - мы никогда не обращаеися к «некорректной» памяти.

klkl

чудесные творения эти списки подкупают своей простотой и мощью но всеже для обычных дел я бы взял std::list или GList

Почему же?

ну во первых не надо юзерские структуры портачить витыкая в них list_head ы линее телодвижение лень плюс std::list сам память выделяет к тому же тупо писанины меньше ну а GList хотя бы не требует специальных структур со связями внутри опять же телодвижений меньше

Зато самый главный недостаток - неЪ.