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