00001 // Copyright (C) 2006-2007 Benedikt Böhm <hollow@gentoo.org> 00002 // 00003 // This program is free software; you can redistribute it and/or 00004 // modify it under the terms of the GNU General Public License 00005 // as published by the Free Software Foundation; either version 2 00006 // of the License, or (at your option) any later version. 00007 // 00008 // This program is distributed in the hope that it will be useful, 00009 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00010 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00011 // GNU General Public License for more details. 00012 // 00013 // You should have received a copy of the GNU General Public License 00014 // along with this program; if not, write to the Free Software 00015 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 00016 00017 /*! 00018 * @defgroup list Simple doubly linked lists 00019 * 00020 * The simplest kind of linked list is a singly-linked list, which has one link 00021 * per node. This link points to the next node in the list, or to a null value 00022 * or empty list if it is the final node; e.g. 12 -> 99 -> 37 -> NULL. 00023 * 00024 * A more sophisticated kind of linked list is a doubly-linked list. Each node 00025 * has two links: one points to the previous node, or points to a null value or 00026 * empty list if it is the first node; and one points to the next, or points to 00027 * a null value or empty list if it is the final node; e.g. 00028 * NULL <- 26 <-> 56 <-> 46 -> NULL. 00029 * 00030 * The list family of functions and macros provide routines to create a list, 00031 * add, move or remove elements and iterate over the list. 00032 * 00033 * @{ 00034 */ 00035 00036 #ifndef _LUCID_LIST_H 00037 #define _LUCID_LIST_H 00038 00039 #include <stddef.h> 00040 00041 #ifdef _LUCID_BUILD_ 00042 #include "mem.h" 00043 #else 00044 #include <lucid/mem.h> 00045 #endif 00046 00047 /*! @brief get container of list head */ 00048 #define container_of(ptr, type, member) \ 00049 ((type *)((char *)(ptr) - offsetof(type, member))) 00050 00051 /* 00052 * Simple doubly linked list implementation. 00053 * 00054 * Some of the internal functions ("__xxx") are useful when 00055 * manipulating whole lists rather than single entries, as 00056 * sometimes we already know the next/prev entries and we can 00057 * generate better code by using them directly rather than 00058 * using the generic single-entry routines. 00059 */ 00060 00061 /*! @brief list head */ 00062 typedef struct list_head { 00063 struct list_head *next, *prev; 00064 } list_t; 00065 00066 #define LIST_NODE_ALLOC(NAME) \ 00067 NAME = mem_alloc(sizeof(*NAME)) 00068 00069 static inline void INIT_LIST_HEAD(list_t *list) 00070 { 00071 list->next = list; 00072 list->prev = list; 00073 } 00074 00075 /* 00076 * Insert a new entry between two known consecutive entries. 00077 * 00078 * This is only for internal list manipulation where we know 00079 * the prev/next entries already! 00080 */ 00081 static inline 00082 void __list_add(list_t *new, 00083 list_t *prev, 00084 list_t *next) 00085 { 00086 next->prev = new; 00087 new->next = next; 00088 new->prev = prev; 00089 prev->next = new; 00090 } 00091 00092 /*! 00093 * @brief add a new entry 00094 * 00095 * Insert a new entry after the specified head. 00096 * This is good for implementing stacks. 00097 * 00098 * @param new new entry to be added 00099 * @param head list head to add it after 00100 */ 00101 static inline 00102 void list_add(list_t *new, list_t *head) 00103 { 00104 __list_add(new, head, head->next); 00105 } 00106 00107 /*! 00108 * @brief add a new entry 00109 * 00110 * Insert a new entry before the specified head. 00111 * This is useful for implementing queues. 00112 * 00113 * @param new new entry to be added 00114 * @param head list head to add it before 00115 */ 00116 static inline 00117 void list_add_tail(list_t *new, list_t *head) 00118 { 00119 __list_add(new, head->prev, head); 00120 } 00121 00122 /* 00123 * Delete a list entry by making the prev/next entries 00124 * point to each other. 00125 * 00126 * This is only for internal list manipulation where we know 00127 * the prev/next entries already! 00128 */ 00129 static inline 00130 void __list_del(list_t * prev, list_t * next) 00131 { 00132 next->prev = prev; 00133 prev->next = next; 00134 } 00135 00136 /*! 00137 * @brief deletes entry from list 00138 * 00139 * @param entry the element to delete from the list 00140 * 00141 * @note list_empty on entry does not return true after this, the entry is 00142 * in an undefined state 00143 */ 00144 static inline 00145 void list_del(list_t *entry) 00146 { 00147 __list_del(entry->prev, entry->next); 00148 entry->next = (void *) 0; 00149 entry->prev = (void *) 0; 00150 } 00151 00152 /*! 00153 * @brief deletes entry from list and reinitialize it 00154 * 00155 * @param entry the element to delete from the list 00156 */ 00157 static inline 00158 void list_del_init(list_t *entry) 00159 { 00160 __list_del(entry->prev, entry->next); 00161 INIT_LIST_HEAD(entry); 00162 } 00163 00164 /*! 00165 * @brief delete from one list and add as another's head 00166 * 00167 * @param list the entry to move 00168 * @param head the head that will precede our entry 00169 */ 00170 static inline 00171 void list_move(list_t *list, list_t *head) 00172 { 00173 __list_del(list->prev, list->next); 00174 list_add(list, head); 00175 } 00176 00177 /*! 00178 * @brief delete from one list and add as another's tail 00179 * 00180 * @param list the entry to move 00181 * @param head the head that will follow our entry 00182 */ 00183 static inline 00184 void list_move_tail(list_t *list, list_t *head) 00185 { 00186 __list_del(list->prev, list->next); 00187 list_add_tail(list, head); 00188 } 00189 00190 /*! 00191 * @brief tests whether a list is empty 00192 * 00193 * @param head the list to test 00194 */ 00195 static inline 00196 int list_empty(const list_t *head) 00197 { 00198 return head->next == head; 00199 } 00200 00201 static inline 00202 void __list_splice(list_t *list, list_t *head) 00203 { 00204 list_t *first = list->next; 00205 list_t *last = list->prev; 00206 list_t *at = head->next; 00207 00208 first->prev = head; 00209 head->next = first; 00210 00211 last->next = at; 00212 at->prev = last; 00213 } 00214 00215 /*! 00216 * @brief join two lists 00217 * 00218 * @param list the new list to add 00219 * @param head the place to add it in the first list 00220 */ 00221 static inline 00222 void list_splice(list_t *list, list_t *head) 00223 { 00224 if (!list_empty(list)) 00225 __list_splice(list, head); 00226 } 00227 00228 /*! 00229 * @brief join two lists and reinitialise the emptied list 00230 * 00231 * @param list the new list to add 00232 * @param head the place to add it in the first list 00233 */ 00234 static inline 00235 void list_splice_init(list_t *list, list_t *head) 00236 { 00237 if (!list_empty(list)) { 00238 __list_splice(list, head); 00239 INIT_LIST_HEAD(list); 00240 } 00241 } 00242 00243 /*! 00244 * @brief get the struct for this entry 00245 * 00246 * @param ptr the &list_t pointer 00247 * @param type the type of the struct this is embedded in 00248 * @param member the name of the list_struct within the struct 00249 */ 00250 #define list_entry(ptr, type, member) \ 00251 container_of(ptr, type, member) 00252 00253 /*! 00254 * @brief iterate over a list 00255 * 00256 * @param pos the &list_t to use as a loop counter 00257 * @param head the head for your list 00258 */ 00259 #define list_for_each(pos, head) \ 00260 for (pos = (head)->next; pos != (head); pos = pos->next) 00261 00262 /*! 00263 * @brief iterate over a list backwards 00264 * 00265 * @param pos the &list_t to use as a loop counter 00266 * @param head the head for your list 00267 */ 00268 #define list_for_each_prev(pos, head) \ 00269 for (pos = (head)->prev; pos != (head); pos = pos->prev) 00270 00271 /*! 00272 * @brief iterate over a list safe against removal of list entry 00273 * 00274 * @param pos the &list_t to use as a loop counter 00275 * @param n another &list_t to use as temporary storage 00276 * @param head the head for your list 00277 */ 00278 #define list_for_each_safe(pos, n, head) \ 00279 for (pos = (head)->next, n = pos->next; pos != (head); \ 00280 pos = n, n = pos->next) 00281 00282 /*! 00283 * @brief iterate over list of given type 00284 * 00285 * @param pos the type * to use as a loop counter 00286 * @param head: the head for your list 00287 * @param member the name of the list_struct within the struct 00288 */ 00289 #define list_for_each_entry(pos, head, member) \ 00290 for (pos = list_entry((head)->next, typeof(*pos), member); \ 00291 &pos->member != (head); \ 00292 pos = list_entry(pos->member.next, typeof(*pos), member)) 00293 00294 /*! 00295 * @brief iterate backwards over list of given type. 00296 * 00297 * @param pos the type * to use as a loop counter 00298 * @param head the head for your list 00299 * @param member the name of the list_struct within the struct 00300 */ 00301 #define list_for_each_entry_reverse(pos, head, member) \ 00302 for (pos = list_entry((head)->prev, typeof(*pos), member); \ 00303 &pos->member != (head); \ 00304 pos = list_entry(pos->member.prev, typeof(*pos), member)) 00305 00306 /*! 00307 * @brief iterate over list of given type safe against removal of list entry 00308 * 00309 * @param pos the type * to use as a loop counter 00310 * @param n another type * to use as temporary storage 00311 * @param head the head for your list 00312 * @param member the name of the list_struct within the struct 00313 */ 00314 #define list_for_each_entry_safe(pos, n, head, member) \ 00315 for (pos = list_entry((head)->next, typeof(*pos), member), \ 00316 n = list_entry(pos->member.next, typeof(*pos), member); \ 00317 &pos->member != (head); \ 00318 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 00319 00320 /*! 00321 * @brief iterate backwards over list of given type safe against removal of list entry 00322 * 00323 * @param pos the type * to use as a loop counter 00324 * @param n another type * to use as temporary storage 00325 * @param head the head for your list 00326 * @param member the name of the list_struct within the struct 00327 */ 00328 #define list_for_each_entry_safe_reverse(pos, n, head, member) \ 00329 for (pos = list_entry((head)->prev, typeof(*pos), member), \ 00330 n = list_entry(pos->member.prev, typeof(*pos), member); \ 00331 &pos->member != (head); \ 00332 pos = n, n = list_entry(n->member.prev, typeof(*n), member)) 00333 00334 #endif 00335 00336 /*! @} list */