176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman// This list structure implementation is adapted from the list implementation 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman// on the Linux kernel. 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman// Original source: 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman// http://git.kernel.org/?p=linux/kernel/git/stable/linux-2.6.25.y.git;a=blob_plain;f=include/linux/list.h;hb=HEAD 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifndef _LINUX_LIST_H 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define _LINUX_LIST_H 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Simple doubly linked list implementation. 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Some of the internal functions ("__xxx") are useful when 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * manipulating whole lists rather than single entries, as 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * sometimes we already know the next/prev entries and we can 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * generate better code by using them directly rather than 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * using the generic single-entry routines. 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdlib.h> 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stddef.h> 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstruct list_head { 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *next, *prev; 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}; 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define LIST_HEAD_INIT(name) { &(name), &(name) } 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define LIST_HEAD(name) \ 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head name = LIST_HEAD_INIT(name) 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void INIT_LIST_HEAD(struct list_head *list) 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list->next = list; 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list->prev = list; 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Insert a new entry between two known consecutive entries. 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This is only for internal list manipulation where we know 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the prev/next entries already! 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void __list_add(struct list_head *new, 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *prev, 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *next) 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman next->prev = new; 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new->next = next; 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new->prev = prev; 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman prev->next = new; 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_add - add a new entry 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @new: new entry to be added 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: list head to add it after 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Insert a new entry after the specified head. 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This is good for implementing stacks. 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_add(struct list_head *new, struct list_head *head) 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_add(new, head, head->next); 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_add_tail - add a new entry 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @new: new entry to be added 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: list head to add it before 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Insert a new entry before the specified head. 7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This is useful for implementing queues. 7676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 7776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_add_tail(struct list_head *new, struct list_head *head) 7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_add(new, head->prev, head); 8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Delete a list entry by making the prev/next entries 8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * point to each other. 8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This is only for internal list manipulation where we know 8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the prev/next entries already! 8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void __list_del(struct list_head * prev, struct list_head * next) 9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman next->prev = prev; 9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman prev->next = next; 9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_del - deletes entry from list. 9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @entry: the element to delete from the list. 9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Note: list_empty() on entry does not return true after this, the entry is 10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * in an undefined state. 10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_del(struct list_head *entry) 10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_del(entry->prev, entry->next); 10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman entry->next = NULL; 10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman entry->prev = NULL; 10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_replace - replace old entry by new one 11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @old : the element to be replaced 11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @new : the new element to insert 11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * If @old was empty, it will be overwritten. 11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_replace(struct list_head *old, 11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *new) 11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new->next = old->next; 12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new->next->prev = new; 12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new->prev = old->prev; 12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman new->prev->next = new; 12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_replace_init(struct list_head *old, 12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *new) 12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list_replace(old, new); 12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman INIT_LIST_HEAD(old); 13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_del_init - deletes entry from list and reinitialize it. 13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @entry: the element to delete from the list. 13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_del_init(struct list_head *entry) 13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_del(entry->prev, entry->next); 13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman INIT_LIST_HEAD(entry); 14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_move - delete from one list and add as another's head 14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @list: the entry to move 14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head that will precede our entry 14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_move(struct list_head *list, struct list_head *head) 14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_del(list->prev, list->next); 15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list_add(list, head); 15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_move_tail - delete from one list and add as another's tail 15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @list: the entry to move 15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head that will follow our entry 15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_move_tail(struct list_head *list, 15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *head) 16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_del(list->prev, list->next); 16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list_add_tail(list, head); 16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_is_last - tests whether @list is the last entry in list @head 16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @list: the entry to test 16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head of the list 16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline int list_is_last(const struct list_head *list, 17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const struct list_head *head) 17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return list->next == head; 17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_empty - tests whether a list is empty 17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the list to test. 17976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 18076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline int list_empty(const struct list_head *head) 18176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 18276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return head->next == head; 18376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 18476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 18576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 18676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_empty_careful - tests whether a list is empty and not being modified 18776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the list to test 18876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 18976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Description: 19076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * tests whether a list is empty _and_ checks that no other CPU might be 19176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * in the process of modifying either member (next or prev) 19276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 19376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * NOTE: using list_empty_careful() without synchronization 19476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * can only be safe if the only activity that can happen 19576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * to the list entry is list_del_init(). Eg. it cannot be used 19676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * if another CPU could re-list_add() it. 19776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 19876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline int list_empty_careful(const struct list_head *head) 19976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 20076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *next = head->next; 20176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return (next == head) && (next == head->prev); 20276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 20376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 20476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void __list_splice(struct list_head *list, 20576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *head) 20676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 20776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *first = list->next; 20876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *last = list->prev; 20976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *at = head->next; 21076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 21176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman first->prev = head; 21276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman head->next = first; 21376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 21476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman last->next = at; 21576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman at->prev = last; 21676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 21776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 21876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 21976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_splice - join two lists 22076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @list: the new list to add. 22176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the place to add it in the first list. 22276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 22376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_splice(struct list_head *list, struct list_head *head) 22476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 22576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!list_empty(list)) 22676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_splice(list, head); 22776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 22876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 22976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 23076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_splice_init - join two lists and reinitialise the emptied list. 23176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @list: the new list to add. 23276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the place to add it in the first list. 23376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 23476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * The list at @list is reinitialised 23576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 23676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic inline void list_splice_init(struct list_head *list, 23776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct list_head *head) 23876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 23976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!list_empty(list)) { 24076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman __list_splice(list, head); 24176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman INIT_LIST_HEAD(list); 24276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 24376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 24476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 24576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 24676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_entry - get the struct for this entry 24776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @ptr: the &struct list_head pointer. 24876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @type: the type of the struct this is embedded in. 24976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 25076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 25176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_entry(ptr, type, member) \ 25276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman container_of(ptr, type, member) 25376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 25476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 25576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_first_entry - get the first element from a list 25676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @ptr: the list head to take the element from. 25776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @type: the type of the struct this is embedded in. 25876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 25976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 26076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Note, that list is expected to be not empty. 26176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 26276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_first_entry(ptr, type, member) \ 26376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list_entry((ptr)->next, type, member) 26476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 26576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 26676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each - iterate over a list 26776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the &struct list_head to use as a loop cursor. 26876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 26976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 27076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each(pos, head) \ 27176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = (head)->next; pos != (head); \ 27276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = pos->next) 27376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 27476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 27576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * __list_for_each - iterate over a list 27676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the &struct list_head to use as a loop cursor. 27776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 27876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 27976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This variant differs from list_for_each() in that it's the 28076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * simplest possible list iteration code, no prefetching is done. 28176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Use this for code that knows the list to be very short (empty 28276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * or 1 entry) most of the time. 28376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 28476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define __list_for_each(pos, head) \ 28576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = (head)->next; pos != (head); pos = pos->next) 28676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 28776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 28876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_prev - iterate over a list backwards 28976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the &struct list_head to use as a loop cursor. 29076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 29176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 29276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_prev(pos, head) \ 29376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = (head)->prev; pos != (head); \ 29476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = pos->prev) 29576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 29676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 29776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_safe - iterate over a list safe against removal of list entry 29876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the &struct list_head to use as a loop cursor. 29976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @n: another &struct list_head to use as temporary storage 30076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 30176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 30276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_safe(pos, n, head) \ 30376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = (head)->next, n = pos->next; pos != (head); \ 30476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = pos->next) 30576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 30676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 30776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry 30876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the &struct list_head to use as a loop cursor. 30976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @n: another &struct list_head to use as temporary storage 31076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 31176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 31276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_prev_safe(pos, n, head) \ 31376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = (head)->prev, n = pos->prev; \ 31476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos != (head); \ 31576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = pos->prev) 31676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 31776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 31876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry - iterate over list of given type 31976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 32076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 32176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 32276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 32376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry(pos, head, member) \ 32476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry((head)->next, typeof(*pos), member); \ 32576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 32676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = list_entry(pos->member.next, typeof(*pos), member)) 32776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 32876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 32976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry 33076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman* @pos: the type * to use as a loop cursor. 33176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman* @n: another type * to use as temporary storage 33276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman* @head: the head for your list. 33376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman* @member: the name of the list_struct within the struct. 33476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman*/ 33576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_safe(pos, n, head, member) \ 33676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry((head)->next, typeof(*pos), member), \ 33776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman n = list_entry(pos->member.next, typeof(*pos), member); \ 33876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 33976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = list_entry(n->member.next, typeof(*n), member)) 34076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 34176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 34276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_reverse - iterate backwards over list of given type. 34376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 34476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 34576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 34676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 34776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_reverse(pos, head, member) \ 34876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry((head)->prev, typeof(*pos), member); \ 34976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 35076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = list_entry(pos->member.prev, typeof(*pos), member)) 35176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 35276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 35376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() 35476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a start point 35576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head of the list 35676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 35776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 35876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). 35976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 36076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_prepare_entry(pos, head, member) \ 36176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ((pos) ? : list_entry(head, typeof(*pos), member)) 36276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 36376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 36476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_continue - continue iteration over list of given type 36576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 36676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 36776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 36876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 36976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Continue to iterate over list of given type, continuing after 37076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the current position. 37176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 37276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_continue(pos, head, member) \ 37376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry(pos->member.next, typeof(*pos), member); \ 37476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 37576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = list_entry(pos->member.next, typeof(*pos), member)) 37676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 37776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 37876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_continue_reverse - iterate backwards from the given point 37976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 38076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 38176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 38276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 38376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Start to iterate over list of given type backwards, continuing after 38476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the current position. 38576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 38676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_continue_reverse(pos, head, member) \ 38776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ 38876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 38976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = list_entry(pos->member.prev, typeof(*pos), member)) 39076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 39176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 39276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_from - iterate over list of given type from the current point 39376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 39476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 39576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 39676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 39776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Iterate over list of given type, continuing from current position. 39876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 39976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_from(pos, head, member) \ 40076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (; &pos->member != (head); \ 40176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = list_entry(pos->member.next, typeof(*pos), member)) 40276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 40376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 40476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry 40576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 40676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @n: another type * to use as temporary storage 40776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 40876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 40976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 41076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_safe(pos, n, head, member) \ 41176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry((head)->next, typeof(*pos), member), \ 41276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman n = list_entry(pos->member.next, typeof(*pos), member); \ 41376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 41476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = list_entry(n->member.next, typeof(*n), member)) 41576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 41676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 41776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_safe_continue 41876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 41976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @n: another type * to use as temporary storage 42076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 42176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 42276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 42376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Iterate over list of given type, continuing after current point, 42476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * safe against removal of list entry. 42576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 42676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_safe_continue(pos, n, head, member) \ 42776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry(pos->member.next, typeof(*pos), member), \ 42876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman n = list_entry(pos->member.next, typeof(*pos), member); \ 42976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 43076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = list_entry(n->member.next, typeof(*n), member)) 43176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 43276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 43376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_safe_from 43476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 43576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @n: another type * to use as temporary storage 43676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 43776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 43876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 43976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Iterate over list of given type from current point, safe against 44076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * removal of list entry. 44176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 44276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_safe_from(pos, n, head, member) \ 44376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = list_entry(pos->member.next, typeof(*pos), member); \ 44476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 44576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = list_entry(n->member.next, typeof(*n), member)) 44676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 44776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/** 44876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * list_for_each_entry_safe_reverse 44976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @pos: the type * to use as a loop cursor. 45076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @n: another type * to use as temporary storage 45176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @head: the head for your list. 45276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * @member: the name of the list_struct within the struct. 45376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 45476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Iterate backwards over list of given type, safe against removal 45576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * of list entry. 45676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 45776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define list_for_each_entry_safe_reverse(pos, n, head, member) \ 45876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (pos = list_entry((head)->prev, typeof(*pos), member), \ 45976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman n = list_entry(pos->member.prev, typeof(*pos), member); \ 46076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman &pos->member != (head); \ 46176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pos = n, n = list_entry(n->member.prev, typeof(*n), member)) 46276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 46376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 46476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 465