list_head: получить мусор, если начать разбор со второго элемента

Question

Я использую в своей структуре list_head проекта C, чтобы определить связанный список.В некоторых случаях мне нужно проанализировать список из второго элемента, но в этом случае я получаю дополнительный элемент со значением мусора.Я попытался с помощью небольшой программы на моем компьютере имитировать тот же сценарий.Я получаю ту же проблему:

#include<stdio.h>
#include<stdlib.h>
#include "list.h"

struct struct_report{
        struct list_head list;
        char *report;
};


//Add an element to the linked list
void add_report_to_list(struct list_head *reports, char *report) {
        struct struct_report *report_strct;
        report_strct = calloc(1, sizeof(struct struct_report));
        list_add_tail(&report_strct->list, reports);
        report_strct->report= strdup(report);
}

int main() {
        struct struct_report *retreport;
        LIST_HEAD(reports); //instantiate a struct list_head instance
        add_report_to_list(&reports, "elt1");
        add_report_to_list(&reports, "elt2");
        add_report_to_list(&reports, "elt3");
        add_report_to_list(&reports, "elt4");
        list_for_each_entry(retreport, &reports, list){
                printf("============> no next retreport: %s\n", retreport->report);
        }
        printf("\n");
        list_for_each_entry(retreport, reports.next, list){
                printf("============> Next retreport: %s\n", retreport->report);
        }
        return 1;
} 

list.h - это то же самое, что и linux: https://github.com/torvalds/linux/blob/master/include/linux/list.h

В результате выполнения я получаю следующую трассировку:

============> no next retreport: elt1
============> no next retreport: elt2
============> no next retreport: elt3
============> no next retreport: elt4

============> Next retreport: elt2
============> Next retreport: elt3
============> Next retreport: elt4
============> Next retreport: 

Понятно, что в случае, если я начинаю синтаксический анализ с первого элемента, у меня нет проблем.Но в случае, если я начинаю со второго элемента в списке, я получаю дополнительный элемент со странным значением, например, мусор.

Есть объяснение, почему я получаю дополнительный элемент?И как я могу это исправить до разбора до elt4?

Answer 1

Реализация списка фактически создает кольцо.Заголовок списка - это фиктивный элемент, который указывает next на первый элемент и prev на последний элемент.(Изначально оба указывают на сам заголовок списка.) Добавление элемента в хвосте фактически реализовано как добавление его «перед заголовком списка».При зацикливании этого кольца голова помечается отдельным указателем, указывающим на него.Нет другого способа отличить его от других элементов списка.

Цикл for в list_for_each_entry имеет сравнение с указателем head в качестве условия цикла, поэтому он остановится, когдаон снова достигнет объекта, предоставленного в качестве заголовка списка.

/**
 * 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_head within the struct.
 */
#define list_for_each_entry(pos, head, member)              \
    for (pos = list_first_entry(head, typeof(*pos), member);    \
         &pos->member != (head);                    \
         pos = list_next_entry(pos, member))

Оба макроса list_first_entry и list_next_entry возвращают указатель на пользовательскую структуру, которая должна содержать struct list_head, используяmacro container_of.

Если вы передадите reports.next вместо &reports на list_for_each_entry(), он примет это как элемент заголовка фиктивного списка и рассмотрит все остальные элементы в кольце как реальные записи списка.

Ваш код печатает мусор для элемента позади элемента tail, потому что это чистый struct list_head, который не встроен в struct struct_report, поэтому макрос list_next_entry возвращает указатель на память перед вашим struct list_head reports in main(), что является неопределенным поведением.

Если ваша программа не падает, вы получите такой же мусор после elt4, если передадите, например, reports.next->next.В этом случае я бы ожидал вывод, как это:

============> Next retreport: elt3
============> Next retreport: elt4
============> Next retreport: <garbage>
============> Next retreport: elt1

Answer 2

Если вы начинаете с первого элемента списка (а не с заголовка), то list_for_each_entry() остановится в том же объекте списка, потому что это круговой список.

Таким образом, list_for_each_entry() будетпройти через голову.И голова не привязана к записи.поэтому, когда вы попытаетесь обратиться к записи из списка заголовков, вы получите мусор

Решение: запустите цикл из заголовка списка и пропустите первый элемент

Answer 3

Хотя один и тот же тип - list_head - используется для обоих:

• заголовок списка,
• элементы списка,

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

Макрос list_for_each_entry принимает указатель на заголовок списка в качестве второго аргумента, поэтому вместо него не следует передавать указатель на элемент.

Для пропускапервые элементы при итерации по списку, макросы

• list_for_each_entry_from
• list_for_each_entry_continue или

.

Обаэти макросы принимают те же аргументы, что и list_for_each_entry one, но учитывают начальное значение курсора (первый аргумент):

• list_for_each_entry_from запускает итерацию в элемент, наведенный курсором,
• list_for_each_entry_continue начинает итерацию после элемента, на который указывает курсор.

Таким образом, перебор списка с пропуском первого элемента может бытьследует:

// Set cursor to the first element in the list
retreport = list_first_entry(reports, typeof(*retreport), list);
// Iterate starting after the cursor
list_for_each_entry_continue(retreport, reports, list){
    printf("============> Next retreport: %s\n", retreport->report);
}