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