1 #ifndef _GPXE_LIST_H 2 #define _GPXE_LIST_H 3 4 /** @file 5 * 6 * Linked lists 7 * 8 * This linked list handling code is based on the Linux kernel's 9 * list.h. 10 */ 11 12 FILE_LICENCE ( GPL2_ONLY ); 13 14 #include <stddef.h> 15 #include <assert.h> 16 17 /* 18 * Simple doubly linked list implementation. 19 * 20 * Some of the internal functions ("__xxx") are useful when 21 * manipulating whole lists rather than single entries, as 22 * sometimes we already know the next/prev entries and we can 23 * generate better code by using them directly rather than 24 * using the generic single-entry routines. 25 */ 26 27 struct list_head { 28 struct list_head *next; 29 struct list_head *prev; 30 }; 31 32 #define LIST_HEAD_INIT( name ) { &(name), &(name) } 33 34 #define LIST_HEAD( name ) \ 35 struct list_head name = LIST_HEAD_INIT ( name ) 36 37 #define INIT_LIST_HEAD( ptr ) do { \ 38 (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 39 } while ( 0 ) 40 41 /* 42 * Insert a new entry between two known consecutive entries. 43 * 44 * This is only for internal list manipulation where we know 45 * the prev/next entries already! 46 */ 47 static inline void __list_add ( struct list_head *new, 48 struct list_head *prev, 49 struct list_head *next ) { 50 next->prev = new; 51 new->next = next; 52 new->prev = prev; 53 prev->next = new; 54 } 55 56 /** 57 * Add a new entry to the head of a list 58 * 59 * @v new New entry to be added 60 * @v head List head to add it after 61 * 62 * Insert a new entry after the specified head. This is good for 63 * implementing stacks. 64 */ 65 static inline void list_add ( struct list_head *new, struct list_head *head ) { 66 __list_add ( new, head, head->next ); 67 } 68 #define list_add( new, head ) do { \ 69 assert ( (head)->next->prev == (head) ); \ 70 assert ( (head)->prev->next == (head) ); \ 71 list_add ( (new), (head) ); \ 72 } while ( 0 ) 73 74 /** 75 * Add a new entry to the tail of a list 76 * 77 * @v new New entry to be added 78 * @v head List head to add it before 79 * 80 * Insert a new entry before the specified head. This is useful for 81 * implementing queues. 82 */ 83 static inline void list_add_tail ( struct list_head *new, 84 struct list_head *head ) { 85 __list_add ( new, head->prev, head ); 86 } 87 #define list_add_tail( new, head ) do { \ 88 assert ( (head)->next->prev == (head) ); \ 89 assert ( (head)->prev->next == (head) ); \ 90 list_add_tail ( (new), (head) ); \ 91 } while ( 0 ) 92 93 /* 94 * Delete a list entry by making the prev/next entries 95 * point to each other. 96 * 97 * This is only for internal list manipulation where we know 98 * the prev/next entries already! 99 */ 100 static inline void __list_del ( struct list_head * prev, 101 struct list_head * next ) { 102 next->prev = prev; 103 prev->next = next; 104 } 105 106 /** 107 * Delete an entry from a list 108 * 109 * @v entry Element to delete from the list 110 * 111 * Note that list_empty() on entry does not return true after this; 112 * the entry is in an undefined state. 113 */ 114 static inline void list_del ( struct list_head *entry ) { 115 __list_del ( entry->prev, entry->next ); 116 } 117 #define list_del( entry ) do { \ 118 assert ( (entry)->prev != NULL ); \ 119 assert ( (entry)->next != NULL ); \ 120 assert ( (entry)->next->prev == (entry) ); \ 121 assert ( (entry)->prev->next == (entry) ); \ 122 list_del ( (entry) ); \ 123 } while ( 0 ) 124 125 /** 126 * Test whether a list is empty 127 * 128 * @v head List to test. 129 */ 130 static inline int list_empty ( const struct list_head *head ) { 131 return head->next == head; 132 } 133 134 /** 135 * Get the containing struct for this entry 136 * 137 * @v ptr The struct list_head pointer 138 * @v type The type of the struct this is embedded in 139 * @v member The name of the list_struct within the struct 140 */ 141 #define list_entry( ptr, type, member ) \ 142 container_of ( ptr, type, member ) 143 144 /** 145 * Iterate over a list 146 * 147 * @v pos The &struct list_head to use as a loop counter 148 * @v head The head for your list 149 */ 150 #define list_for_each( pos, head ) \ 151 for ( pos = (head)->next; pos != (head); pos = pos->next ) 152 153 /** 154 * Iterate over entries in a list 155 * 156 * @v pos The type * to use as a loop counter 157 * @v head The head for your list 158 * @v member The name of the list_struct within the struct 159 */ 160 #define list_for_each_entry( pos, head, member ) \ 161 for ( pos = list_entry ( (head)->next, typeof ( *pos ), member ); \ 162 &pos->member != (head); \ 163 pos = list_entry ( pos->member.next, typeof ( *pos ), member ) ) 164 165 /** 166 * Iterate over entries in a list, safe against deletion of entries 167 * 168 * @v pos The type * to use as a loop counter 169 * @v tmp Another type * to use for temporary storage 170 * @v head The head for your list 171 * @v member The name of the list_struct within the struct 172 */ 173 #define list_for_each_entry_safe( pos, tmp, head, member ) \ 174 for ( pos = list_entry ( (head)->next, typeof ( *pos ), member ), \ 175 tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \ 176 &pos->member != (head); \ 177 pos = tmp, \ 178 tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) ) 179 180 #endif /* _GPXE_LIST_H */ 181
