Aman Deep Gautam
Aman Deep Gautam

Reputation: 8747

list_empty function kernel linked list

list_empty() function is defined in ./include/linux/list.h and its definition is

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

list_head data structure is defined as

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

What I do not understand is why this implementation in kernel checks for head->next == head and not for head->next == NULL && head->prev == NULL.

Upvotes: 2

Views: 6481

Answers (2)

Gene
Gene

Reputation: 46990

The list is circular, with the head itself serving as a dummy node. Circular lists have a slight advantage in the number of comparisons needed during insertion and deletion. Since there are no null pointers, there are not as many special cases to look for. I don't have the source code here, but if you check it, you'll find that initializing a list is done with something like:

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

Insertion will be:

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; 
}

Look! No if statements at all!

Upvotes: 9

iabdalkader
iabdalkader

Reputation: 17312

because head->next is not NULL when the list is empty, it points to head instead.

Upvotes: 0

Related Questions