内核链表list.hstddef.hkernel.hlist.h

#define

offsetof(type, member) ((size_t) &((type *)0)->member)

/**

*

container_of - cast a member of a structure out to the containing

structure

* @ptr:    the pointer to the

member.

* @type:    the type of the

container struct this is embedded in.

@member:    the name of the member within the struct.

*/

#define container_of(ptr, type, member)

({           

\

    const typeof( ((type

*)0)->member ) *__mptr = (ptr);    \

    (type *)( (char *)__mptr -

offsetof(type,member) );})

#ifndef _linux_list_h

#define _linux_list_h

#include

<linux/stddef.h>

#include <linux/poison.h>

#include <linux/prefetch.h>

<asm/system.h>

/*

* simple

doubly linked list implementation.

* some

of the internal functions ("__xxx") are useful when

manipulating whole lists rather than single entries, as

* sometimes we already know the next/prev entries and we can

* generate better code by using them directly rather than

* using the generic single-entry routines.

struct

list_head {

    struct list_head *next,

*prev;

};

list_head_init(name) { &(name), &(name)

}

list_head(name) \

    struct list_head name

= list_head_init(name)

static

inline void init_list_head(struct list_head *list)

{

    list->next = list;

    list->prev = list;

* insert

a new entry between two known consecutive entries.

* this is only for internal list manipulation where we know

* the prev/next entries already!

#ifndef

config_debug_list

将new查到prev和next中间

static inline void __list_add(struct list_head *new,

struct list_head *prev,

struct list_head *next)

    next->prev = new;

    new->next = next;

    new->prev = prev;

    prev->next = new;

#else

extern void __list_add(struct list_head *new,

struct list_head *next);

#endif

list_add - add a new entry

* @new: new entry to be added

* @head: list head to add it after

* insert a new entry after the specified head.

this is good for implementing stacks.

将new插入的head后面。

static inline

void list_add(struct list_head *new, struct list_head *head)

    __list_add(new, head,

head->next);

list_add_tail - add a new entry

* @new: new entry to be

added

* @head: list head to add it before

* insert a new entry before the specified head.

* this is useful for implementing queues.

将new插入到head前面

static inline void list_add_tail(struct list_head

*new, struct list_head *head)

    __list_add(new, head->prev, head);

* delete

a list entry by making the prev/next entries

* point to

each other.

* this is only for internal

list manipulation where we know

* the prev/next entries

already!

删除prev和next中间的结点

inline void __list_del(struct list_head * prev, struct list_head *

next)

    next->prev =

prev;

    prev->next = next;

list_del - deletes entry from list.

* @entry: the

element to delete from the list.

* note: list_empty() on

entry does not return true after this, the entry is

* in

an undefined state.

从链表中删除entry所在的结点，不释放entry的空间

list_poison1  ((void *) 0x00100100)

  #define

list_poison2  ((void *) 0x00200200)

static inline void list_del(struct

list_head *entry)

__list_del(entry->prev, entry->next);

    entry->next = list_poison1;

    entry->prev = list_poison2;

extern void list_del(struct

list_head *entry);

list_replace - replace old entry by new one

* @old : the

element to be replaced

* @new : the new element to

insert

* if @old was empty, it will be

overwritten.

将old替换为new

static inline void list_replace(struct list_head

*old,

struct list_head *new)

    new->next = old->next;

    new->next->prev = new;

    new->prev = old->prev;

    new->prev->next = new;

将old替换为new，并且将old重新初始化

inline void list_replace_init(struct list_head *old,

list_replace(old, new);

init_list_head(old);

list_del_init - deletes entry from list and reinitialize it.

* @entry: the element to delete from the list.

从链表中删除entry，并且将entry重新初始化

static inline void list_del_init(struct list_head

*entry)

    init_list_head(entry);

list_move - delete from one list and add as another‘s head

* @list: the entry to move

* @head: the head that

will precede our entry

将list从原来的链表移动到head链表中

static inline void

list_move(struct list_head *list, struct list_head *head)

    __list_del(list->prev,

list->next);

    list_add(list,

head);

list_move_tail - delete from one list and add as another‘s tail

will follow our entry

将list从原先的链表中删除，添加到head链表中（并且查到head的前边）

list_move_tail(struct list_head *list,

struct list_head *head)

    __list_del(list->prev, list->next);

    list_add_tail(list, head);

list_is_last - tests whether @list is the last entry in list @head

* @list: the entry to test

* @head: the head

of the list

判断list是不是链表head的尾结点

static inline int list_is_last(const

struct list_head *list,

const struct list_head *head)

    return list->next == head;

list_empty - tests whether a list is empty

* @head: the

list to test.

int list_empty(const struct list_head *head)

    return head->next == head;

list_empty_careful - tests whether a list is empty and not being

modified

* @head: the list to test

* description:

* tests whether a list is empty

_and_ checks that no other cpu might be

* in the process

of modifying either member (next or prev)

* note: using list_empty_careful() without synchronization

* can only be safe if the only activity that can happen

* to the list entry is list_del_init(). eg. it cannot be used

* if another cpu could re-list_add() it.

int list_empty_careful(const struct list_head *head)

    struct list_head *next =

head->next;

    return (next == head)

&& (next == head->prev);

list_is_singular - tests whether a list has just one entry.

* @head: the list to test.

int list_is_singular(const struct list_head *head)

    return !list_empty(head) &&

(head->next == head->prev);

inline void __list_cut_position(struct list_head *list,

        struct list_head

*head, struct list_head *entry)

    struct list_head *new_first = entry->next;

    list->next = head->next;

    list->next->prev = list;

    list->prev = entry;

    entry->next = list;

    head->next = new_first;

    new_first->prev = head;

list_cut_position - cut a list into two

* @list: a new

list to add all removed entries

* @head: a list with

entries

* @entry: an entry within head, could be the

head itself

*    and if so we won‘t cut

the list

* this helper moves the initial

part of @head, up to and

* including @entry, from @head

to @list. you should

* pass on @entry an element you

know is on @head. @list

* should be an empty list or a

list you do not care about

* losing its data.

list_cut_position(struct list_head *list,

    if (list_empty(head))

        return;

    if (list_is_singular(head) &&

        (head->next !=

entry && head != entry))

    if (entry == head)

        init_list_head(list);

    else

__list_cut_position(list, head, entry);

__list_splice(const struct list_head *list,

struct list_head *first = list->next;

    struct list_head *last =

list->prev;

first->prev = prev;

    prev->next =

first;

last->next = next;

last;

list_splice - join two lists, this is designed for stacks

* @list: the new list to add.

* @head: the place to

add it in the first list.

void list_splice(const struct list_head *list,

if (!list_empty(list))

        __list_splice(list,

head, head->next);

list_splice_tail - join two lists, each list being a queue

void list_splice_tail(struct list_head *list,

head->prev, head);

list_splice_init - join two lists and reinitialise the emptied list.

place to add it in the first list.

* the

list at @list is reinitialised

inline void list_splice_init(struct list_head *list,

if (!list_empty(list)) {

    }

list_splice_tail_init - join two lists and reinitialise the emptied

list

* @head:

the place to add it in the first list.

each of the lists is a queue.

* the list at @list is

reinitialised

list_splice_tail_init(struct list_head *list,

list_entry - get the struct for this entry

@ptr:    the &struct list_head pointer.

* @type:    the type of the struct this is

embedded in.

* @member:    the name of

the list_struct within the struct.

list_entry(ptr, type, member) \

container_of(ptr, type, member)

list_first_entry - get the first element from a list

@ptr:    the list head to take the element from.

* note,

that list is expected to be not empty.

#define list_first_entry(ptr, type, member) \

    list_entry((ptr)->next, type,

member)

list_for_each    -    iterate over a

* @pos:    the &struct list_head

to use as a loop cursor.

* @head:    the

head for your list.

list_for_each(pos, head) \

    for (pos =

(head)->next; prefetch(pos->next), pos != (head); \

pos = pos->next)

__list_for_each    -    iterate over a

* this variant differs

from list_for_each() in that it‘s the

* simplest

possible list iteration code, no prefetching is done.

use this for code that knows the list to be very short (empty

* or 1 entry) most of the time.

#define __list_for_each(pos, head) \

    for (pos = (head)->next; pos != (head);

list_for_each_prev    -    iterate

over a list backwards

* @pos:    the

&struct list_head to use as a loop cursor.

@head:    the head for your list.

#define list_for_each_prev(pos, head) \

    for (pos = (head)->prev;

prefetch(pos->prev), pos != (head); \

pos = pos->prev)

list_for_each_safe - iterate over a list safe against removal of

list entry

* @pos:    the &struct

list_head to use as a loop cursor.

@n:        another &struct

list_head to use as temporary storage

#define list_for_each_safe(pos, n, head) \

    for (pos = (head)->next, n = pos->next;

pos != (head); \

        pos = n, n =

pos->next)

list_for_each_prev_safe - iterate over a list backwards safe against

removal of list entry

#define list_for_each_prev_safe(pos, n, head) \

    for (pos = (head)->prev, n = pos->prev;

         pos = n, n =

pos->prev)

list_for_each_entry    -    iterate

over list of given type

type * to use as a loop cursor.

@member:    the name of the list_struct within the

struct.

#define list_for_each_entry(pos,

head,

member)               

list_entry((head)->next, typeof(*pos), member);   

prefetch(pos->member.next), &pos->member !=

(head);     \

         pos =

list_entry(pos->member.next, typeof(*pos),

member))

list_for_each_entry_reverse - iterate backwards 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_struct within the struct.

list_for_each_entry_reverse(pos, head,

member)           

list_entry((head)->prev, typeof(*pos), member);   

prefetch(pos->member.prev), &pos->member !=

list_entry(pos->member.prev, typeof(*pos),

list_prepare_entry - prepare a pos entry for use in

list_for_each_entry_continue()

* @pos:   

the type * to use as a start point

@head:    the head of the list

* prepares a pos entry for use as

a start point in list_for_each_entry_continue().

#define list_prepare_entry(pos, head, member) \

    ((pos) ? : list_entry(head, typeof(*pos),

list_for_each_entry_continue - continue iteration over list of given

type

* continue

to iterate over list of given type, continuing after

the current position.

list_for_each_entry_continue(pos, head,

member)         \

    for (pos = list_entry(pos->member.next,

typeof(*pos), member);    \

(head);    \

list_for_each_entry_continue_reverse - iterate backwards from the

given point

* @pos:    the type * to use

as a loop cursor.

* @head:    the head

for your list.

* start

to iterate over list of given type backwards, continuing after

* the current position.

list_for_each_entry_continue_reverse(pos, head,

member)        \

    for (pos = list_entry(pos->member.prev,

list_for_each_entry_from - iterate over list of given type from the

current point

* @pos:    the type * to

use as a loop cursor.

* @member:    the

name of the list_struct within the struct.

* iterate over list of given type, continuing from current position.

#define list_for_each_entry_from(pos,

member)            

    for (;

list_for_each_entry_safe - iterate over list of given type safe

against removal of list entry

the type * to use as a loop cursor.

@n:        another type * to use

as temporary storage

list_for_each_entry_safe(pos, n, head,

list_entry((head)->next, typeof(*pos), member),   

        n =

member);    \

&pos->member !=

(head);                    

n, n = list_entry(n->member.next, typeof(*n),

list_for_each_entry_safe_continue

@pos:    the type * to use as a loop cursor.

* @n:        another type *

to use as temporary storage

* @head:   

the head for your list.

* iterate over list of given type, continuing after current point,

* safe against removal of list entry.

#define list_for_each_entry_safe_continue(pos, n, head,

typeof(*pos),

member),         \

member);        \

(head);                       

list_for_each_entry_safe_from

iterate over list of given type from current point, safe against

* removal of list entry.

list_for_each_entry_safe_from(pos, n, head,

    for (n =

list_for_each_entry_safe_reverse

* iterate backwards over list of given type, safe against removal

* of list entry.

list_for_each_entry_safe_reverse(pos, n, head,

    for (pos = list_entry((head)->prev,

typeof(*pos), member),    \

n, n = list_entry(n->member.prev, typeof(*n),

* double

linked lists with a single pointer list head.

* mostly

useful for hash tables where the two pointer list head is

* too wasteful.

* you lose the ability to access

the tail in o(1).

struct hlist_head {

    struct hlist_node *first;

struct hlist_node {

    struct hlist_node *next, **pprev;

#define hlist_head_init

{ .first = null }

#define hlist_head(name) struct

hlist_head name = {  .first = null }

init_hlist_head(ptr) ((ptr)->first = null)

inline void init_hlist_node(struct hlist_node *h)

    h->next = null;

    h->pprev = null;

static inline int

hlist_unhashed(const struct hlist_node *h)

    return !h->pprev;

hlist_empty(const struct hlist_head *h)

    return !h->first;

__hlist_del(struct hlist_node *n)

    struct hlist_node *next = n->next;

    struct hlist_node **pprev = n->pprev;

    *pprev = next;

    if (next)

        next->pprev =

pprev;

hlist_del(struct hlist_node *n)

    __hlist_del(n);

n->next = list_poison1;

    n->pprev

= list_poison2;

hlist_del_init(struct hlist_node *n)

    if (!hlist_unhashed(n)) {

        __hlist_del(n);

        init_hlist_node(n);

hlist_add_head(struct hlist_node *n, struct hlist_head *h)

    struct hlist_node *first =

h->first;

    n->next = first;

    if (first)

        first->pprev =

&n->next;

    h->first = n;

    n->pprev = &h->first;

/* next must be != null

static inline void hlist_add_before(struct hlist_node

*n,

struct hlist_node *next)

n->pprev = next->pprev;

n->next = next;

    next->pprev =

    *(n->pprev) = n;

hlist_add_after(struct hlist_node *n,

next->next = n->next;

    n->next

= next;

if(next->next)

next->next->pprev  = &next->next;

* move a

list from one list head to another. fixup the pprev

reference of the first entry if it exists.

static inline void hlist_move_list(struct hlist_head *old,

struct hlist_head *new)

new->first = old->first;

    if

(new->first)

new->first->pprev = &new->first;

    old->first = null;

hlist_entry(ptr, type, member)

container_of(ptr,type,member)

hlist_for_each(pos, head) \

(head)->first; pos && ({ prefetch(pos->next); 1; }); \

hlist_for_each_safe(pos, n, head) \

    for

(pos = (head)->first; pos && ({ n = pos->next; 1; });

n)

hlist_for_each_entry    - iterate over list of given

* @tpos:    the type * to use as a

hlist_node to use as a loop cursor.

@member:    the name of the hlist_node within the

#define hlist_for_each_entry(tpos,

pos, head,

(head)->first;                    

         pos

&& ({ prefetch(pos->next); 1;})

&&            

        ({ tpos =

hlist_entry(pos, typeof(*tpos), member); 1;}); \

hlist_for_each_entry_continue - iterate over a hlist continuing

after current point

* @tpos:    the type

* to use as a loop cursor.

&struct hlist_node to use as a loop cursor.

hlist_for_each_entry_continue(tpos, pos,

(pos)->next;                        

hlist_for_each_entry_from - iterate over a hlist continuing from

* @tpos:    the type * to

hlist_for_each_entry_from(tpos, pos,

    for (; pos && ({

prefetch(pos->next); 1;})

hlist_for_each_entry_safe - iterate over list of given type safe

* @tpos:   

@pos:    the &struct hlist_node to use as a loop

cursor.

* @n:       

another &struct hlist_node to use as temporary storage

* @head:    the head for your list.

* @member:    the name of the hlist_node within the

hlist_for_each_entry_safe(tpos, pos, n, head,

member)          \

&& ({ n = pos->next; 1; })

&&