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