mware/list.h

   1 /*!
   2  * \file
   3  * <!--
   4  * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
   5  * Copyright 2001 Bernardo Innocenti <bernie@develer.com>
   6  * This file is part of DevLib - See devlib/README for information.
   7  * -->
   8  *
   9  * \version $Id$
  10  *
  11  * \author Bernardo Innocenti <bernie@develer.com>
  12  *
  13  * \brief General pourpose double-linked lists
  14  */
  15
  16 /*#*
  17  *#* $Log$
  18  *#* Revision 1.12  2005/01/22 04:21:32  bernie
  19  *#* Add integrity checks.
  20  *#*
  21  *#* Revision 1.11  2004/12/31 16:44:11  bernie
  22  *#* list_remHead(), list_remTail(): Name like normal functions.
  23  *#*
  24  *#* Revision 1.10  2004/11/28 23:21:05  bernie
  25  *#* Remove obsolete INITLIST macro.
  26  *#*
  27  *#* Revision 1.9  2004/10/21 09:37:55  bernie
  28  *#* Revamp documentation.
  29  *#*
  30  *#* Revision 1.8  2004/10/19 08:46:34  bernie
  31  *#* Fix header.
  32  *#*
  33  *#* Revision 1.7  2004/08/25 14:12:09  rasky
  34  *#* Aggiornato il comment block dei log RCS
  35  *#*
  36  *#* Revision 1.6  2004/07/30 14:34:10  rasky
  37  *#* Vari fix per documentazione e commenti
  38  *#* Aggiunte PP_CATn e STATIC_ASSERT
  39  *#*
  40  *#* Revision 1.5  2004/07/20 23:45:01  bernie
  41  *#* Finally remove redundant protos.
  42  *#*
  43  *#* Revision 1.4  2004/07/18 22:12:53  bernie
  44  *#* Fix warnings with GCC 3.3.2.
  45  *#*
  46  *#* Revision 1.3  2004/07/18 22:01:43  bernie
  47  *#* REMHEAD(), REMTAIL(): Move to list.h as inline functions.
  48  *#*
  49  *#* Revision 1.2  2004/06/03 11:27:09  bernie
  50  *#* Add dual-license information.
  51  *#*
  52  *#* Revision 1.1  2004/05/23 15:43:16  bernie
  53  *#* Import mware modules.
  54  *#*
  55  *#*/
  56 #ifndef MWARE_LIST_H
  57 #define MWARE_LIST_H
  58
  59 #include <compiler.h> // INLINE
  60
  61 /*!
  62  * This structure represents a node for bidirectional lists.
  63  *
  64  * Data is usually appended to nodes by making them the first
  65  * field of another struture, as a poor-man's form of inheritance.
  66  */
  67 typedef struct _Node
  68 {
  69         struct _Node *succ;
  70         struct _Node *pred;
  71 } Node;
  72
  73 /*!
  74  * Head of a doubly-linked list of \c Node structs.
  75  *
  76  * Lists must be initialized with LIST_INIT() prior to use.
  77  *
  78  * Nodes can be added and removed from either end of the list
  79  * with O(1) performance.  Iterating over these lists can be
  80  * tricky: use the FOREACHNODE() macro instead.
  81  */
  82 typedef struct _List
  83 {
  84         Node *head;
  85         Node *null;
  86         Node *tail;
  87 } List;
  88
  89
  90 /*! Template for a list of \a T structures. */
  91 #define DECLARE_LIST(T) \
  92         struct { T *head; T *null; T *tail; }
  93
  94 /*! Template for a node in a list of \a T structures. */
  95 #define DECLARE_NODE(T) \
  96         struct { T *succ; T *pred; }
  97
  98 /*! Template for a node in a list of \a T structures. */
  99 #define DECLARE_NODE_ANON(T) \
 100         T *succ; T *pred;
 101
 102 /*!
 103  * Iterate over all nodes in a list.
 104  *
 105  * This macro generates a "for" statement using the following parameters:
 106  * \param n   Node pointer to be used in each iteration.
 107  * \param l   Pointer to list.
 108  */
 109 #define FOREACHNODE(n,l) \
 110         for( \
 111                 (n) = (typeof(n))((l)->head); \
 112                 ((Node *)(n))->succ; \
 113                 (n) = (typeof(n))(((Node *)(n))->succ) \
 114         )
 115
 116 /*! Initialize a list. */
 117 #define LIST_INIT(l) \
 118         do { \
 119                 (l)->head = (Node *)(&(l)->null); \
 120                 (l)->null = NULL; \
 121                 (l)->tail = (Node *)(&(l)->head); \
 122         } while (0)
 123
 124 /* Make sure that a list is valid (it was initialized and is not corrupted) */
 125 #ifdef _DEBUG
 126         #define LIST_ASSERT_VALID(l) \
 127                 do { \
 128                         Node *n, *pred; \
 129                         ASSERT((l)->head != NULL); \
 130                         ASSERT((l)->null == NULL); \
 131                         ASSERT((l)->tail != NULL); \
 132                         pred = (Node *)(&(l)->head); \
 133                         FOREACHNODE(n, l) \
 134                         { \
 135                                 ASSERT(n->pred == pred); \
 136                                 pred = n; \
 137                         } \
 138                         ASSERT(n == (Node *)(&(l)->null)); \
 139                 } while (0)
 140 #else
 141         #define LIST_ASSERT_VALID(l) do {} while (0)
 142 #endif
 143
 144 /*! Add node to list head. */
 145 #define ADDHEAD(l,n) \
 146         do { \
 147                 (n)->succ = (l)->head; \
 148                 (n)->pred = (Node *)&(l)->head; \
 149                 (n)->succ->pred = (n); \
 150                 (l)->head = (n); \
 151         } while (0)
 152
 153 /*! Add node to list tail. */
 154 #define ADDTAIL(l,n) \
 155         do { \
 156                 (n)->succ = (Node *)(&(l)->null); \
 157                 (n)->pred = (l)->tail; \
 158                 (n)->pred->succ = (n); \
 159                 (l)->tail = (n); \
 160         } while (0)
 161
 162 /*!
 163  * Insert node \a n before node \a ln.
 164  *
 165  * \note You can't pass in a list header as \a ln, but
 166  *       it is safe to pass list-\>head of an empty list.
 167  */
 168 #define INSERTBEFORE(n,ln) \
 169         do { \
 170                 (n)->succ = (ln); \
 171                 (n)->pred = (ln)->pred; \
 172                 (ln)->pred->succ = (n); \
 173                 (ln)->pred = (n); \
 174         } while (0)
 175
 176 /*!
 177  * Remove \a n from whatever list it is in.
 178  *
 179  * \note Removing a node that has not previously been
 180  *       inserted into a list invokes undefined behavior.
 181  */
 182 #define REMOVE(n) \
 183         do { \
 184                 (n)->pred->succ = (n)->succ; \
 185                 (n)->succ->pred = (n)->pred; \
 186         } while (0)
 187
 188 /*! Tell whether a list is empty. */
 189 #define ISLISTEMPTY(l)  ( (l)->head == (Node *)(&(l)->null) )
 190
 191 /*!
 192  * Unlink a node from the head of the list \a l.
 193  *
 194  * \return Pointer to node, or NULL if the list was empty.
 195  */
 196 INLINE Node *list_remHead(List *l)
 197 {
 198         Node *n;
 199
 200         if (ISLISTEMPTY(l))
 201                 return (Node *)0;
 202
 203         n = l->head;
 204         l->head = n->succ;
 205         n->succ->pred = (Node *)l;
 206         return n;
 207 }
 208
 209 /*!
 210  * Unlink a node from the tail of the list \a l.
 211  *
 212  * \return Pointer to node, or NULL if the list was empty.
 213  */
 214 INLINE Node *list_remTail(List *l)
 215 {
 216         Node *n;
 217
 218         if (ISLISTEMPTY(l))
 219                 return (Node *)0;
 220
 221         n = l->tail;
 222         l->tail = n->pred;
 223         n->pred->succ = (Node *)&l->null;
 224         return n;
 225 }
 226
 227 /* OBSOLETE names */
 228 #define REMHEAD list_remHead
 229 #define REMTAIL list_remTail
 230
 231 #endif /* MWARE_LIST_H */