119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#ifndef _LINUX_LIST_H 219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define _LINUX_LIST_H 319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Simple doubly linked list implementation. 619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Some of the internal functions ("__xxx") are useful when 819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * manipulating whole lists rather than single entries, as 919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * sometimes we already know the next/prev entries and we can 1019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * generate better code by using them directly rather than 1119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * using the generic single-entry routines. 1219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 1319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstruct list_head { 1519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head *next, *prev; 1619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project}; 1719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define LIST_HEAD_INIT(name) { &(name), &(name) } 1919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 2019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define LIST_HEAD(name) \ 2119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head name = { &name, &name } 2219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 2319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define INIT_LIST_HEAD(ptr) do { \ 2419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 2519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} while (0) 2619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 2719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#if (!defined(__GNUC__) && !defined(__WATCOMC__)) 2819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define __inline__ 2919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#endif 3019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 3119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 323984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt * Insert a new entry between two known consecutive entries. 3319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 3419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * This is only for internal list manipulation where we know 3519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * the prev/next entries already! 3619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 3719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ void __list_add(struct list_head * new, 3819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head * prev, 3919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head * next) 4019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 4119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project next->prev = new; 4219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project new->next = next; 4319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project new->prev = prev; 4419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project prev->next = new; 4519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 4619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 4819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Insert a new entry after the specified head.. 4919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 5019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ void list_add(struct list_head *new, struct list_head *head) 5119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 5219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project __list_add(new, head, head->next); 5319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 5419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 5519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 5619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Insert a new entry at the tail 5719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 5819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ void list_add_tail(struct list_head *new, struct list_head *head) 5919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 6019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project __list_add(new, head->prev, head); 6119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 6219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 6319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 6419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Delete a list entry by making the prev/next entries 6519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * point to each other. 6619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * 6719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * This is only for internal list manipulation where we know 6819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * the prev/next entries already! 6919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 7019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ void __list_del(struct list_head * prev, 7119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head * next) 7219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 7319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project next->prev = prev; 7419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project prev->next = next; 7519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 7619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 7719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ void list_del(struct list_head *entry) 7819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 7919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project __list_del(entry->prev, entry->next); 8019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 8119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 8219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ int list_empty(struct list_head *head) 8319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 8419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return head->next == head; 8519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 8619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 8719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project/* 8819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project * Splice in "list" into "head" 8919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project */ 9019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectstatic __inline__ void list_splice(struct list_head *list, struct list_head *head) 9119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project{ 9219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head *first = list->next; 9319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 9419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project if (first != list) { 9519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head *last = list->prev; 9619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project struct list_head *at = head->next; 9719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 9819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project first->prev = head; 9919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project head->next = first; 10019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 10119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project last->next = at; 10219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project at->prev = last; 10319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 10419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project} 10519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 10619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define list_entry(ptr, type, member) \ 10719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) 10819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 10919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define list_for_each(pos, head) \ 11019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project for (pos = (head)->next; pos != (head); pos = pos->next) 11119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 11219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#endif 113