1586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#ifndef _LINUX_LIST_H 2586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#define _LINUX_LIST_H 3586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 4586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o/* 5586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * Simple doubly linked list implementation. 6586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * 7586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * Some of the internal functions ("__xxx") are useful when 8586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * manipulating whole lists rather than single entries, as 9586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * sometimes we already know the next/prev entries and we can 10586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * generate better code by using them directly rather than 11586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * using the generic single-entry routines. 12586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o */ 13586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 14586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostruct list_head { 15586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head *next, *prev; 16586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o}; 17586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 18586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#define LIST_HEAD_INIT(name) { &(name), &(name) } 19586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 20586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#define INIT_LIST_HEAD(ptr) do { \ 21586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 22586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} while (0) 23586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 247d4343d0d05ce69e0a72da5ac34eea415d4c789fTheodore Ts'o#if (!defined(__GNUC__) && !defined(__WATCOMC__)) 257d4343d0d05ce69e0a72da5ac34eea415d4c789fTheodore Ts'o#define __inline__ 267d4343d0d05ce69e0a72da5ac34eea415d4c789fTheodore Ts'o#endif 277d4343d0d05ce69e0a72da5ac34eea415d4c789fTheodore Ts'o 28586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o/* 29efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * Insert a new entry between two known consecutive entries. 30586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * 31586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * This is only for internal list manipulation where we know 32586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * the prev/next entries already! 33586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o */ 34586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ void __list_add(struct list_head * new, 35586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head * prev, 36586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head * next) 37586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 38586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o next->prev = new; 39586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o new->next = next; 40586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o new->prev = prev; 41586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o prev->next = new; 42586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 43586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 44586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o/* 45586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * Insert a new entry after the specified head.. 46586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o */ 47586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ void list_add(struct list_head *new, struct list_head *head) 48586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 49586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o __list_add(new, head, head->next); 50586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 51586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 52586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o/* 53586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * Insert a new entry at the tail 54586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o */ 55586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ void list_add_tail(struct list_head *new, struct list_head *head) 56586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 57586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o __list_add(new, head->prev, head); 58586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 59586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 60586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o/* 61586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * Delete a list entry by making the prev/next entries 62586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * point to each other. 63586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * 64586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * This is only for internal list manipulation where we know 65586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * the prev/next entries already! 66586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o */ 67586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ void __list_del(struct list_head * prev, 68586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head * next) 69586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 70586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o next->prev = prev; 71586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o prev->next = next; 72586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 73586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 74586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ void list_del(struct list_head *entry) 75586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 76586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o __list_del(entry->prev, entry->next); 77586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 78586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 79586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ int list_empty(struct list_head *head) 80586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 81586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o return head->next == head; 82586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 83586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 84586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o/* 85586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o * Splice in "list" into "head" 86586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o */ 87586187372afea65ae685687505b49b40fc5f3212Theodore Ts'ostatic __inline__ void list_splice(struct list_head *list, struct list_head *head) 88586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o{ 89586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head *first = list->next; 90586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 91586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o if (first != list) { 92586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head *last = list->prev; 93586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o struct list_head *at = head->next; 94586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 95586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o first->prev = head; 96586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o head->next = first; 97586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 98586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o last->next = at; 99586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o at->prev = last; 100586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o } 101586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o} 102586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 103586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#define list_entry(ptr, type, member) \ 104586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) 105586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 106586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#define list_for_each(pos, head) \ 107586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o for (pos = (head)->next; pos != (head); pos = pos->next) 108586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o 109586187372afea65ae685687505b49b40fc5f3212Theodore Ts'o#endif 110