110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @file op_list.h 310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Kernel-style lists 410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @remark Copyright 2002 OProfile authors 610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @remark Read the file COPYING 710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @author Linux kernel authors 910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 1010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 1110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#ifndef OP_LIST_H 1210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define OP_LIST_H 1310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 1410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/* 1510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Simple doubly linked list implementation. 1610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 1710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Some of the internal functions ("__xxx") are useful when 1810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * manipulating whole lists rather than single entries, as 1910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * sometimes we already know the next/prev entries and we can 2010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * generate better code by using them directly rather than 2110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * using the generic single-entry routines. 2210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 2310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 2410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstruct list_head { 2510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * next, * prev; 2610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project}; 2710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 2810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 2910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_init - init a new entry 3010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param ptr the list to init 3110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 3210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Init a list head to create an empty list from it 3310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 3410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void list_init(struct list_head * ptr) 3510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 3610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project ptr->next = ptr; 3710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project ptr->prev = ptr; 3810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 3910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 4010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/* 4110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Insert a new entry between two known consecutive entries. 4210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 4310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * This is only for internal list manipulation where we know 4410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * the prev/next entries already! 4510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 4610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void __list_add(struct list_head * new_entry, 4710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * prev, 4810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * next) 4910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 5010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project next->prev = new_entry; 5110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project new_entry->next = next; 5210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project new_entry->prev = prev; 5310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project prev->next = new_entry; 5410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 5510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 5610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 5710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_add - add a new entry 5810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param new new entry to be added 5910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param head list head to add it after 6010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 6110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Insert a new entry after the specified head. 6210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * This is good for implementing stacks. 6310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 6410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void list_add(struct list_head * new_entry, struct list_head * head) 6510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 6610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project __list_add(new_entry, head, head->next); 6710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 6810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 6910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 7010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_add_tail - add a new entry 7110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param new new entry to be added 7210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param head list head to add it before 7310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 7410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Insert a new entry before the specified head. 7510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * This is useful for implementing queues. 7610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 7710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void list_add_tail(struct list_head * new_entry, struct list_head * head) 7810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 7910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project __list_add(new_entry, head->prev, head); 8010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 8110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 8210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/* 8310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Delete a list entry by making the prev/next entries 8410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * point to each other. 8510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * 8610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * This is only for internal list manipulation where we know 8710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * the prev/next entries already! 8810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 8910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void __list_del(struct list_head * prev, 9010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * next) 9110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 9210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project next->prev = prev; 9310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project prev->next = next; 9410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 9510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 9610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 9710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_del - deletes entry from list. 9810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param entry the element to delete from the list. 9910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * Note: list_empty on entry does not return true after this, the entry is in an undefined state. 10010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 10110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void list_del(struct list_head * entry) 10210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 10310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project __list_del(entry->prev, entry->next); 10410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 10510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 10610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 10710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_del_init - deletes entry from list and reinitialize it. 10810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param entry the element to delete from the list. 10910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 11010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void list_del_init(struct list_head * entry) 11110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 11210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project __list_del(entry->prev, entry->next); 11310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project list_init(entry); 11410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 11510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 11610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 11710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_empty - tests whether a list is empty 11810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param head the list to test. 11910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 12010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ int list_empty(struct list_head const * head) 12110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 12210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project return head->next == head; 12310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 12410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 12510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 12610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_splice - join two lists 12710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param list the new list to add. 12810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param head the place to add it in the first list. 12910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 13010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic __inline__ void list_splice(struct list_head * list, struct list_head * head) 13110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project{ 13210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * first = list->next; 13310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 13410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project if (first != list) { 13510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * last = list->prev; 13610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct list_head * at = head->next; 13710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 13810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project first->prev = head; 13910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project head->next = first; 14010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 14110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project last->next = at; 14210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project at->prev = last; 14310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project } 14410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 14510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 14610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 14710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_entry - get the struct for this entry 14810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param ptr the &struct list_head pointer. 14910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param type the type of the struct this is embedded in. 15010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param member the name of the list_struct within the struct. 15110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 15210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define list_entry(ptr, type, member) \ 15310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) 15410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 15510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 15610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_for_each - iterate over a list 15710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param pos the &struct list_head to use as a loop counter. 15810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param head the head for your list. 15910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 16010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define list_for_each(pos, head) \ 16110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project for (pos = (head)->next; pos != (head); pos = pos->next) 16210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 16310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project/** 16410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * list_for_each_safe - iterate over a list safe against removal of list entry 16510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param pos the &struct list_head to use as a loop counter. 16610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param n another &struct list_head to use as temporary storage 16710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project * @param head the head for your list. 16810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project */ 16910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define list_for_each_safe(pos, n, head) \ 17010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project for (pos = (head)->next, n = pos->next; pos != (head); \ 17110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project pos = n, n = pos->next) 17210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 17310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define LIST_HEAD_INIT(name) { &(name), &(name) } 17410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 17510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 17610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 17710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#endif /* OP_LIST_H */ 178