Linux kernel doubly linked-list implementation

• list.h

/* A simple doubly linked list implementation in C.
 *  Copyright (C) 2015  Yang Zhang <yzfedora@gmail.com>
 *
 * Internals:
 *  for eaxmple, we want to declare a doubly linked list called
 *  "struct job" which used to store the basic informations of the job.
 *  like: name, place, salary..., etc.
 *
 *  struct job {
 *      char *name;
 *      char *place;
 *      unsigned salary;
 *      ....            // other members you wants
 *
 *      struct list list;
 *  };
 *  -------------------------------------------------
 *  ... list <----> list <----> list <----> ...
 *  -----|-----------|-----------|-------------------
 *           |           |           |
 *           ^           ^           ^
 *      ... struct job; struct job; struct job; ...
 *
 *      we use a list structure to administrate and links every node in the
 *      doubly linked list. you just need embeded a "struct list" and use it
 *      to manipulate your real doubly linked list("struct job"), it somewhat
 *      likes the "basic class" in Object Oriented Programming.
 *
 *      when you are defined a structure and embeded a "struct list", you can
 *      using the following API to manipulate you doubly linked list. without
 *      need to process the basic node operation.
 */
#ifndef _LIST_H
#define _LIST_H

#ifndef container_of
#define container_of(ptr, type, member) \
    ({ (type *)((char *)ptr - (char *)&((type *)0)->member)})
#endif
#ifndef __container_of
#define __container_of(ptr, type, member) \
    ({ (typeof(type))((char *)ptr - (char *)&((typeof(type))0)->member); })
#endif

struct list {
    struct list* prev;
    struct list* next;
};

/*
 * Used to define a list by use given name, and initialize it. or you can
 * use list_init to initialize a list also.
 */
#define LIST_HEAD(name) struct list name = { &(name), &(name) }


/*
 * Initialize the list head, and the head node will not including any real
 * data. it's a "sentry".
 */
static inline void list_init(struct list* head)
{
    head->prev = head->next = head;
}

static inline void _list_add(struct list* new,
                             struct list* prev,
                             struct list* next)
{
    prev->next = new;
    new->prev = prev;
    new->next = next;
    next->prev = new;
}

/*
 * Insert the new node into list, it will be placed after head.
 */
static inline void list_add(struct list* new, struct list* head)
{
    _list_add(new, head, head->next);
}

/*
 * Insert new node to the tail of list(head->prev will be the last node).
 */
static inline void list_add_tail(struct list* new, struct list* head)
{
    _list_add(new, head->prev, head);
}

/*
 * Remove the current node from the list.
 */
static inline void list_del(struct list* node)
{
    struct list* prev = node->prev, *next = node->next;

    prev->next = next;
    next->prev = prev;
}

/*
 * If list is empty, true will be returned, else false will be returned.
 */
static inline int list_empty(struct list* head)
{
    return (head->next == head);
}


/*
 * Move the list node to the head of list.
 */
static inline void list_move(struct list* list, struct list* head)
{
    list_del(list);
    list_add(list, head);
}

/*
 * Move the list node to the tail of the list.
 */
static inline void list_move_tail(struct list* list, struct list* head)
{
    list_del(list);
    list_add_tail(list, head);
}

/*
 * Get the container structure.
 * ptr    pointer to the member in the type.
 * type   the container structure.
 * member the name of ptr in the container structure.
 */
#define list_entry(ptr, type, member) container_of(ptr, type, member)

/*
 * traval all entrys in the list.
 * pos    a pointer to entry(pointer to the container structure).
 * head   head pointer of list.
 * member the list name in the container structure("struct list" will be
 *        embeded into container structure).
 *
 * Note: head just is a sentry, actually pos is not a valid pointer when
 * &pos->member is equal to head. but there is safe since we are not
 * reference or access it.
 */
#define list_for_each(pos, head, member) \
    for (pos = __container_of((head)->next, pos, member); \
         &pos->member != head; \
         pos = __container_of(pos->member.next, pos, member))

#define list_for_each_reverse(pos, head, member) \
    for (pos = __container_of((head)->prev, pos, member); \
         &pos->member != head; \
         pos = __container_of(pos->member.prev, pos, member))


#endif

• list_test.c

/* A doubly linked list test program.
 *  Copyright (C) 2015  Yang Zhang <yzfedora@gmail.com>
 */
#define EMPLOYE_ADD_TAIL
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* strcmp() */
#include "list.h"

struct employee {
    char*    name;
    char*    city;
    char*    country;
    unsigned age;

    struct list list;
};


static int employee_add(char* name, char* city, char* country, unsigned age,
                        struct list* head)
{
    struct employee* employee;

    if (!(employee = calloc(1, sizeof(*employee)))) {
        return -1;
    }

    employee->name = name;
    employee->city = city;
    employee->country = country;
    employee->age = age;

    list_add(&employee->list, head);
    return 0;
}

static int employee_add_tail(char* name, char* city, char* country,
                             unsigned age,
                             struct list* head)
{
    struct employee* employee;

    if (!(employee = calloc(1, sizeof(*employee)))) {
        return -1;
    }

    employee->name = name;
    employee->city = city;
    employee->country = country;
    employee->age = age;

    list_add_tail(&employee->list, head);
    return 0;
}

static void employee_travel(struct list* head)
{
    struct employee* pos;

    list_for_each(pos, head, list) {
        printf("Name: %s\n"
               "Age : %d\n"
               "From: %s, %s\n\n",
               pos->name, pos->age, pos->city, pos->country);
    }
}

static void employee_travel_reverse(struct list* head)
{
    struct employee* pos;

    list_for_each_reverse(pos, head, list) {
        printf("Name: %s\n"
               "Age : %d\n"
               "From: %s, %s\n\n",
               pos->name, pos->age, pos->city, pos->country);
    }
}

static void employee_move_by_name(char* name, struct list* head)
{
    struct employee* pos;

    list_for_each(pos, head, list) {
        if (!strcmp(pos->name, name)) {
            list_move(&pos->list, head);
        }
    }
}

static void employee_move_tail_by_name(char* name, struct list* head)
{
    struct employee* pos;

    list_for_each(pos, head, list) {
        if (!strcmp(pos->name, name)) {
            list_move_tail(&pos->list, head);
        }
    }
}

static void employee_del_all(struct list* head)
{
    struct employee* pos;

    list_for_each(pos, head, list) {
        list_del(&pos->list);
        free(pos);
    }
}

int main(int argc, char* argv[])
{
    LIST_HEAD(employee_head);   /* define a doubly linked list */

#ifndef EMPLOYE_ADD_TAIL
    /*
     * add some test samples. the last added entry will in the head of
     * list, like a stack
     */
    employee_add("Linus Torvalds", "Helsinki", "Finland", 46, &employee_head);
    employee_add("Hiroyuki Sawano", "Tokyo", "Japan", 35, &employee_head);
    employee_add("Yang Zhang", "Sichuan", "China", 22, &employee_head);
#else

    /* add the test sample in a normally order, the first added entry will
     * in the head of list. (FIFO) */
    employee_add_tail("Linus Torvalds", "Helsinki", "Finland", 46,
                      &employee_head);
    employee_add_tail("Hiroyuki Sawano", "Tokyo", "Japan", 35,
                      &employee_head);
    employee_add_tail("Yang Zhang", "Sichuan", "China", 22, &employee_head);
#endif


    /* travel the list, and print it to stdout. */
    printf("--------- travel the list ---------\n");
    employee_travel(&employee_head);

    printf("--------- travel the list in reverse order ---------\n");
    employee_travel_reverse(&employee_head);


    /* move last entry which name is "Yang Zhang" to the head of list */
    printf("--------- move Yang Zhang to the head ---------\n");

    employee_move_by_name("Yang Zhang", &employee_head);
    employee_travel(&employee_head);


    printf("--------- move Hiroyuki Sawano to the tail ---------\n");
    employee_move_tail_by_name("Hiroyuki Sawano", &employee_head);
    employee_travel(&employee_head);


    printf("--------- empty the list -------------\n");
    employee_del_all(&employee_head);   /* remove all entrys in the list. */
    printf("list is empty: %s\n",
           list_empty(&employee_head) ? "true" : "false");
    return 0;
}

• Makefile

CC    = gcc
CFLAGS    = -Wall
PROGS    = list_test

all: $(PROGS)

%: %.c list.h
    $(CC) -o $@ $^ $(CFLAGS)

clean:
    $(RM) $(PROGS) $(wildcard *.h.gch)