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

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

#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?


person Kallel Omar    schedule 20.09.2019    source источник
comment
Что такое LIST_HEAD(reports);? Поле .next нигде не определено. Что такое list_for_each_entry()? Часть`list_for_each_entry (...) {printf ...} выглядит странно. Пожалуйста, отредактируйте свой вопрос, чтобы добавить эту информацию вместо добавления комментария.   -  person Bodo    schedule 20.09.2019
comment
Пожалуйста, покажите определения для list_for_each_entry функции и struct list_head структуры   -  person Rishikesh Raje    schedule 20.09.2019
comment
@Bodo LIST_HEAD (отчеты); создает переменную rports struct list_head. .next - это атрибут в list_head: struct list_head {struct list_head * next; struct list_head * пред;};   -  person Kallel Omar    schedule 20.09.2019
comment
@RishikeshRaje github.com/torvalds/linux/blob/master/ include / linux / list.h   -  person Kallel Omar    schedule 20.09.2019
comment
@KallelOmar Пожалуйста, отредактируйте свой вопрос и добавьте к нему всю информацию вместо того, чтобы писать комментарии.   -  person Bodo    schedule 20.09.2019
comment
Я только что обновил вопрос со ссылкой на list.h used   -  person Kallel Omar    schedule 20.09.2019
comment
Я не говорю, что это проблема, но это хорошая тактика, чтобы установить значение NULL для каждого указателя, который вы объявляете. Я бы сделал struct struct_report * retreport = NULL   -  person Tsakiroglou Fotis    schedule 20.09.2019
comment
@TsakiroglouFotis: спасибо за ваше предложение. Я создал повторный отчет со значением NULL, но проблема не устранена.   -  person Kallel Omar    schedule 20.09.2019
comment
Интересно, почему проголосовали за этот плохой вопрос ?!   -  person Vlad from Moscow    schedule 20.09.2019
comment
@VladfromMoscow Я не могу, что не так в моем вопросе. Пожалуйста, если есть проблема, пожалуйста, сообщите мне или отредактируйте ее.   -  person Kallel Omar    schedule 20.09.2019
comment
@KallelOmar Вы уже указали, почему ваш вопрос очень плохой.   -  person Vlad from Moscow    schedule 20.09.2019
comment
@KallelOmar Пожалуйста, не помещайте теги в заголовок вопроса - для этого нужны теги.   -  person Konrad Rudolph    schedule 20.09.2019


Ответы (3)


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

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

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

person MOHAMED    schedule 20.09.2019

Реализация списка фактически создает кольцо. Заголовок списка - это фиктивный элемент, который указывает 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, с помощью макроса container_of.

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

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

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

============> Next retreport: elt3
============> Next retreport: elt4
============> Next retreport: <garbage>
============> Next retreport: elt1
person Bodo    schedule 20.09.2019

В то время как один и тот же тип - list_head - используется для обоих:

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

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

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

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

  • list_for_each_entry_from
  • list_for_each_entry_continue or

может быть использован.

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

  • 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);
}
person Tsyvarev    schedule 21.09.2019