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