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