mware/list.h

   1 /*!
   2  * \file
   3  * Copyright (C) 2003,2004 Develer S.r.l. (http://www.develer.com/)
   4  * Copyright (C) 2001 Bernardo Innocenti <bernie@develer.com>
   5  * This file is part of DevLib - See devlib/README for information.
   6  *
   7  * \version $Id$
   8  *
   9  * \author Bernardo Innocenti <bernie@develer.com>
  10  *
  11  * \brief General pourpose double-linked lists
  12  */
  13
  14 /*#*
  15  *#* $Log$
  16  *#* Revision 1.7  2004/08/25 14:12:09  rasky
  17  *#* Aggiornato il comment block dei log RCS
  18  *#*
  19  *#* Revision 1.6  2004/07/30 14:34:10  rasky
  20  *#* Vari fix per documentazione e commenti
  21  *#* Aggiunte PP_CATn e STATIC_ASSERT
  22  *#*
  23  *#* Revision 1.5  2004/07/20 23:45:01  bernie
  24  *#* Finally remove redundant protos.
  25  *#*
  26  *#* Revision 1.4  2004/07/18 22:12:53  bernie
  27  *#* Fix warnings with GCC 3.3.2.
  28  *#*
  29  *#* Revision 1.3  2004/07/18 22:01:43  bernie
  30  *#* REMHEAD(), REMTAIL(): Move to list.h as inline functions.
  31  *#*
  32  *#* Revision 1.2  2004/06/03 11:27:09  bernie
  33  *#* Add dual-license information.
  34  *#*
  35  *#* Revision 1.1  2004/05/23 15:43:16  bernie
  36  *#* Import mware modules.
  37  *#*
  38  *#*/
  39 #ifndef MWARE_LIST_H
  40 #define MWARE_LIST_H
  41
  42 typedef struct _Node
  43 {
  44         struct _Node *succ;
  45         struct _Node *pred;
  46 } Node;
  47
  48 typedef struct _List
  49 {
  50         Node *head;
  51         Node *null;
  52         Node *tail;
  53 } List;
  54
  55
  56 /*! Template for a list of \a T  structures */
  57 #define DECLARE_LIST(T) \
  58         struct { T *head; T *null; T *tail; }
  59
  60 /*! Template for a node in a list of \a T structures */
  61 #define DECLARE_NODE(T) \
  62         struct { T *succ; T *pred; }
  63
  64 /*! Template for a node in a list of \a T structures */
  65 #define DECLARE_NODE_ANON(T) \
  66         T *succ; T *pred;
  67
  68 /*!
  69  * Iterate over all nodes in a list. This statement defines a for cicle
  70  * accepting the following parameters:
  71  * \param n   node pointer to be used in each iteration
  72  * \param l   pointer to list
  73  */
  74 #define FOREACHNODE(n,l) \
  75         for( \
  76                 (n) = (typeof(n))((l)->head); \
  77                 ((Node *)(n))->succ; \
  78                 (n) = (typeof(n))(((Node *)(n))->succ) \
  79         )
  80
  81 /*! Initialize a list */
  82 #define INITLIST(l) \
  83         do { \
  84                 (l)->head = (Node *)(&(l)->null); \
  85                 (l)->null = NULL; \
  86                 (l)->tail = (Node *)(&(l)->head); \
  87         } while (0)
  88
  89 /*! Add node to list head */
  90 #define ADDHEAD(l,n) \
  91         do { \
  92                 (n)->succ = (l)->head; \
  93                 (n)->pred = (Node *)&(l)->head; \
  94                 (n)->succ->pred = (n); \
  95                 (l)->head = (n); \
  96         } while (0)
  97
  98 /*! Add node to list tail */
  99 #define ADDTAIL(l,n) \
 100         do { \
 101                 (n)->succ = (Node *)(&(l)->null); \
 102                 (n)->pred = (l)->tail; \
 103                 (n)->pred->succ = (n); \
 104                 (l)->tail = (n); \
 105         } while (0)
 106
 107 /*!
 108  * Insert node \a n before node \a ln
 109  * Note: you can't pass in a list header as \a ln, but
 110  * it is safe to pass list-\>head of an empty list.
 111  */
 112 #define INSERTBEFORE(n,ln) \
 113         do { \
 114                 (n)->succ = (ln); \
 115                 (n)->pred = (ln)->pred; \
 116                 (ln)->pred->succ = (n); \
 117                 (ln)->pred = (n); \
 118         } while (0)
 119
 120 /*! Remove \a n from whatever list it is in */
 121 #define REMOVE(n) \
 122         do { \
 123                 (n)->pred->succ = (n)->succ; \
 124                 (n)->succ->pred = (n)->pred; \
 125         } while (0)
 126
 127 /*! Tell whether a list is empty */
 128 #define ISLISTEMPTY(l)  ( (l)->head == (Node *)(&(l)->null) )
 129
 130 /*!
 131  * Unlink a node from the head of the list \a l.
 132  * \return Pointer to node, or NULL if the list was empty.
 133  */
 134 INLINE Node *REMHEAD(List *l)
 135 {
 136         Node *n;
 137
 138         if (ISLISTEMPTY(l))
 139                 return (Node *)0;
 140
 141         n = l->head;
 142         l->head = n->succ;
 143         n->succ->pred = (Node *)l;
 144         return n;
 145 }
 146
 147 /*!
 148  * Unlink a node from the tail of the list \a l.
 149  * \return Pointer to node, or NULL if the list was empty.
 150  */
 151 INLINE Node *REMTAIL(List *l)
 152 {
 153         Node *n;
 154
 155         if (ISLISTEMPTY(l))
 156                 return (Node *)0;
 157
 158         n = l->tail;
 159         l->tail = n->pred;
 160         n->pred->succ = (Node *)&l->null;
 161         return n;
 162 }
 163
 164 #endif /* MWARE_LIST_H */