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