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 README.devlib 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.15  2005/11/04 16:20:02  bernie
  19  *#* Fix reference to README.devlib in header.
  20  *#*
  21  *#* Revision 1.14  2005/07/19 07:25:18  bernie
  22  *#* Refactor to remove type aliasing problems.
  23  *#*
  24  *#* Revision 1.13  2005/04/11 19:10:28  bernie
  25  *#* Include top-level headers from cfg/ subdir.
  26  *#*
  27  *#* Revision 1.12  2005/01/22 04:21:32  bernie
  28  *#* Add integrity checks.
  29  *#*
  30  *#* Revision 1.11  2004/12/31 16:44:11  bernie
  31  *#* list_remHead(), list_remTail(): Name like normal functions.
  32  *#*
  33  *#* Revision 1.10  2004/11/28 23:21:05  bernie
  34  *#* Remove obsolete INITLIST macro.
  35  *#*
  36  *#* Revision 1.9  2004/10/21 09:37:55  bernie
  37  *#* Revamp documentation.
  38  *#*
  39  *#* Revision 1.8  2004/10/19 08:46:34  bernie
  40  *#* Fix header.
  41  *#*
  42  *#* Revision 1.7  2004/08/25 14:12:09  rasky
  43  *#* Aggiornato il comment block dei log RCS
  44  *#*
  45  *#* Revision 1.6  2004/07/30 14:34:10  rasky
  46  *#* Vari fix per documentazione e commenti
  47  *#* Aggiunte PP_CATn e STATIC_ASSERT
  48  *#*
  49  *#* Revision 1.5  2004/07/20 23:45:01  bernie
  50  *#* Finally remove redundant protos.
  51  *#*
  52  *#* Revision 1.4  2004/07/18 22:12:53  bernie
  53  *#* Fix warnings with GCC 3.3.2.
  54  *#*
  55  *#* Revision 1.3  2004/07/18 22:01:43  bernie
  56  *#* REMHEAD(), REMTAIL(): Move to list.h as inline functions.
  57  *#*
  58  *#* Revision 1.2  2004/06/03 11:27:09  bernie
  59  *#* Add dual-license information.
  60  *#*
  61  *#* Revision 1.1  2004/05/23 15:43:16  bernie
  62  *#* Import mware modules.
  63  *#*
  64  *#*/
  65 #ifndef MWARE_LIST_H
  66 #define MWARE_LIST_H
  67
  68 #include <cfg/compiler.h> /* INLINE */
  69 #include <cfg/debug.h> /* ASSERT() */
  70
  71 /*!
  72  * This structure represents a node for bidirectional lists.
  73  *
  74  * Data is usually appended to nodes by making them the first
  75  * field of another struture, as a poor-man's form of inheritance.
  76  */
  77 typedef struct _Node
  78 {
  79         struct _Node *succ;
  80         struct _Node *pred;
  81 } Node;
  82
  83 /*!
  84  * Head of a doubly-linked list of \c Node structs.
  85  *
  86  * Lists must be initialized with LIST_INIT() prior to use.
  87  *
  88  * Nodes can be added and removed from either end of the list
  89  * with O(1) performance.  Iterating over these lists can be
  90  * tricky: use the FOREACHNODE() macro instead.
  91  */
  92 typedef struct _List
  93 {
  94         Node head;
  95         Node tail;
  96 } List;
  97
  98
  99 /*!
 100  * Template for a naked node in a list of \a T structures.
 101  *
 102  * To be used as data member in other structures:
 103  *
 104  * \code
 105  *    struct Foo
 106  *    {
 107  *        DECLARE_NODE_ANON(struct Foo)
 108  *        int a;
 109  *        float b;
 110  *    }
 111  *
 112  *    DECLARE_LIST_TYPE(Foo);
 113  *
 114  *    void foo(void)
 115  *    {
 116  *        static LIST_TYPE(Foo) foo_list;
 117  *        static Foo foo1, foo2;
 118  *        Foo *fp;
 119  *
 120  *        LIST_INIT(&foo_list);
 121  *        LIST_ADDHEAD(&foo_list, &foo1);
 122  *        INSERTBEFORE(&foo_list, &foo2);
 123  *        FOREACHNODE(fp, &foo_list)
 124  *              fp->a = 10;
 125  *    }
 126  *
 127  * \endcode
 128  */
 129 #define DECLARE_NODE_ANON(T) \
 130         T *succ; T *pred;
 131
 132 /*! Declare a typesafe node for structures of type \a T. */
 133 #define DECLARE_NODE_TYPE(T) \
 134         typedef struct T##Node { T *succ; T *pred; } T##Node
 135
 136 /*! Template for a list of \a T structures. */
 137 #define DECLARE_LIST_TYPE(T) \
 138         DECLARE_NODE_TYPE(T); \
 139         typedef struct T##List { \
 140                  T##Node head; \
 141                  T##Node tail; \
 142         } T##List
 143
 144 #define NODE_TYPE(T) T##Node
 145 #define LIST_TYPE(T) T##List
 146
 147 /*!
 148  * Get a pointer to the first node in a list.
 149  *
 150  * If \a l is empty, result points to l->tail.
 151  */
 152 #define LIST_HEAD(l) ((l)->head.succ)
 153
 154 /*!
 155  * Get a pointer to the last node in a list.
 156  *
 157  * If \a l is empty, result points to l->head.
 158  */
 159 #define LIST_TAIL(l) ((l)->tail.pred)
 160
 161 /*!
 162  * Iterate over all nodes in a list.
 163  *
 164  * This macro generates a "for" statement using the following parameters:
 165  * \param n   Node pointer to be used in each iteration.
 166  * \param l   Pointer to list.
 167  */
 168 #define FOREACHNODE(n, l) \
 169         for( \
 170                 (n) = (typeof(n))LIST_HEAD(l); \
 171                 ((Node *)(n))->succ; \
 172                 (n) = (typeof(n))(((Node *)(n))->succ) \
 173         )
 174
 175 /*! Initialize a list. */
 176 #define LIST_INIT(l) \
 177         do { \
 178                 (l)->head.succ = (typeof((l)->head.succ)) &(l)->tail; \
 179                 (l)->head.pred = NULL; \
 180                 (l)->tail.succ = NULL; \
 181                 (l)->tail.pred = (typeof((l)->tail.pred)) &(l)->head; \
 182         } while (0)
 183
 184 #ifdef _DEBUG
 185         /*! Make sure that a list is valid (it was initialized and is not corrupted). */
 186         #define LIST_ASSERT_VALID(l) \
 187                 do { \
 188                         Node *n, *pred; \
 189                         ASSERT((l)->head.succ != NULL); \
 190                         ASSERT((l)->head.pred == NULL); \
 191                         ASSERT((l)->tail.succ == NULL); \
 192                         ASSERT((l)->tail.pred != NULL); \
 193                         pred = &(l)->head; \
 194                         FOREACHNODE(n, l) \
 195                         { \
 196                                 ASSERT(n->pred == pred); \
 197                                 pred = n; \
 198                         } \
 199                         ASSERT(n == &(l)->tail); \
 200                 } while (0)
 201
 202         #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
 203 #else
 204         #define LIST_ASSERT_VALID(l) do {} while (0)
 205         #define INVALIDATE_NODE(n) do {} while (0)
 206 #endif
 207
 208 /*! Add node to list head. */
 209 #define ADDHEAD(l,n) \
 210         do { \
 211                 ASSERT(l); \
 212                 ASSERT(n); \
 213                 (n)->succ = (l)->head.succ; \
 214                 (n)->pred = (l)->head.succ->pred; \
 215                 (n)->succ->pred = (n); \
 216                 (n)->pred->succ = (n); \
 217         } while (0)
 218
 219 /*! Add node to list tail. */
 220 #define ADDTAIL(l,n) \
 221         do { \
 222                 ASSERT(l); \
 223                 ASSERT(n); \
 224                 (n)->succ = &(l)->tail; \
 225                 (n)->pred = (l)->tail.pred; \
 226                 (n)->pred->succ = (n); \
 227                 (l)->tail.pred = (n); \
 228         } while (0)
 229
 230 /*!
 231  * Insert node \a n before node \a ln.
 232  *
 233  * \note You can't pass in a list header as \a ln, but
 234  *       it is safe to pass list-\>head of an empty list.
 235  */
 236 #define INSERT_BEFORE(n,ln) \
 237         do { \
 238                 (n)->succ = (ln); \
 239                 (n)->pred = (ln)->pred; \
 240                 (ln)->pred->succ = (n); \
 241                 (ln)->pred = (n); \
 242         } while (0)
 243
 244 /*!
 245  * Remove \a n from whatever list it is in.
 246  *
 247  * \note Removing a node that has not previously been
 248  *       inserted into a list invokes undefined behavior.
 249  */
 250 #define REMOVE(n) \
 251         do { \
 252                 (n)->pred->succ = (n)->succ; \
 253                 (n)->succ->pred = (n)->pred; \
 254                 INVALIDATE_NODE(n); \
 255         } while (0)
 256
 257 /*! Tell whether a list is empty. */
 258 #define LIST_EMPTY(l)  ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
 259
 260 /*!
 261  * Unlink a node from the head of the list \a l.
 262  *
 263  * \return Pointer to node, or NULL if the list was empty.
 264  */
 265 INLINE Node *list_remHead(List *l)
 266 {
 267         Node *n;
 268
 269         if (LIST_EMPTY(l))
 270                 return (Node *)0;
 271
 272         n = l->head.succ; /* Get first node. */
 273         l->head.succ = n->succ; /* Link list head to second node. */
 274         n->succ->pred = &l->head; /* Link second node to list head. */
 275
 276         INVALIDATE_NODE(n);
 277         return n;
 278 }
 279
 280 /*!
 281  * Unlink a node from the tail of the list \a l.
 282  *
 283  * \return Pointer to node, or NULL if the list was empty.
 284  */
 285 INLINE Node *list_remTail(List *l)
 286 {
 287         Node *n;
 288
 289         if (LIST_EMPTY(l))
 290                 return (Node *)0;
 291
 292         n = l->tail.pred; /* Get last node. */
 293         l->tail.pred = n->pred; /* Link list tail to second last node. */
 294         n->pred->succ = &l->tail; /* Link second last node to list tail. */
 295
 296         INVALIDATE_NODE(n);
 297         return n;
 298 }
 299
 300 /* OBSOLETE names */
 301 #define REMHEAD list_remHead
 302 #define REMTAIL list_remTail
 303 #define INSERTBEFORE INSERT_BEFORE
 304 #define ISLISTEMPTY LIST_EMPTY
 305
 306
 307 #endif /* MWARE_LIST_H */