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