list_empty связанный список ядра функции

Функция list_empty() определена в ./include/linux/list.h, и ее определение

static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}

list_head структура данных определяется как

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

Чего я не понимаю, так это почему эта реализация в ядре проверяет head->next == head, а не head->next == NULL && head->prev == NULL.


c linux-kernel kernel linked-list
person Aman Deep Gautam    schedule 25.10.2012    source источник

Ответы (2)


arrow_upward
9
arrow_downward

Список круговой, а сам заголовок служит фиктивным узлом. Циклические списки имеют небольшое преимущество в количестве сравнений, необходимых при вставке и удалении. Поскольку нет нулевых указателей, не так много особых случаев нужно искать. У меня нет здесь исходного кода, но если вы его проверите, то обнаружите, что инициализация списка выполняется примерно так:

head->next = head->prev = head;

Вставка будет:

void insert_after(struct list_head *node, struct list_head *after)
{
  node->next = after->next;
  node->prev = after;
  after->next->prev = node;
  after->next = node; 
}

Смотреть! Никаких операторов if вообще!

person Gene    schedule 25.10.2012

arrow_upward
0
arrow_downward

поскольку head->next не является NULL, когда список пуст, вместо этого он указывает на head.

person iabdalkader    schedule 25.10.2012