list.h

Go to the documentation of this file.
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 */

Generated on Tue Jun 19 20:38:26 2007 for lucid by  doxygen 1.5.2