gdb/common/queue.h

   1 /* General queue data structure for GDB, the GNU debugger.
   2
   3    Copyright (C) 2012-2013 Free Software Foundation, Inc.
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef QUEUE_H
  21 #define QUEUE_H
  22
  23 #include "libiberty.h" /* xmalloc */
  24 #include "gdb_assert.h"
  25
  26 /* These macros implement functions and structs for a general queue.
  27    Macro 'DEFINE_QUEUE_P(TYPEDEF)' is to define the new queue type for
  28    TYPEDEF', and macro 'DECLARE_QUEUE_P' is to declare external queue
  29    APIs.  The character P indicates TYPEDEF is a pointer (P).  The
  30    counterpart on object (O) and integer (I) are not implemented.
  31
  32    An example of their use would be,
  33
  34    typedef struct foo
  35    {} *foo_p;
  36
  37    DEFINE_QUEUE_P (foo_p);
  38    // A pointer to a queue of foo pointers.  FOO_XFREE is a destructor
  39    // function for foo instances in queue.
  40    QUEUE(foo_p) *foo_queue = QUEUE_alloc (foo_p, foo_xfree);
  41
  42    foo_p foo_var_p;
  43    // Enqueue and Dequeue
  44    QUEUE_enque (foo_p, foo_queue, foo_var_p);
  45    foo_var_p = QUEUE_deque (foo_p, foo_queue);
  46
  47    static int visit_foo (QUEUE (foo_p) *q, QUEUE_ITER (foo_p) *iter,
  48                         foo_p f, void *data)
  49    {
  50      return 1;
  51    }
  52    // Iterate over queue.
  53    QUEUE_iterate (foo_p, foo_queue, visit_foo, &param);
  54
  55    QUEUE_free (foo_p, foo_queue);  // Free queue.  */
  56
  57 /* Typical enqueue operation.  Put V into queue Q.  */
  58 #define QUEUE_enque(TYPE, Q, V) queue_ ## TYPE ## _enque ((Q), (V))
  59
  60 /* Typical dequeue operation.  Return head element of queue Q and
  61    remove it.  Q must not be empty.  */
  62 #define QUEUE_deque(TYPE, Q) queue_ ## TYPE ## _deque (Q)
  63
  64 /* Return the head element, but don't remove it from the queue.
  65    Q must not be empty.  */
  66 #define QUEUE_peek(TYPE, Q) queue_ ## TYPE ## _peek (Q)
  67
  68 /* Return true if queue Q is empty.  */
  69 #define QUEUE_is_empty(TYPE, Q) queue_ ## TYPE ## _is_empty (Q)
  70
  71 /* Allocate memory for queue.  FREE_FUNC is a function to release the
  72    data put in each queue element.  */
  73 #define QUEUE_alloc(TYPE, FREE_FUNC) queue_ ## TYPE ## _alloc (FREE_FUNC)
  74
  75 /* Length of queue Q.  */
  76 #define QUEUE_length(TYPE, Q) queue_ ## TYPE ## _length (Q)
  77
  78 /* Free queue Q.  Q's free_func is called once for each element.  */
  79 #define QUEUE_free(TYPE, Q) queue_ ## TYPE ## _free (Q)
  80
  81 /* Iterate over elements in the queue Q and call function OPERATE on
  82    each element.  It is allowed to remove element by OPERATE.  OPERATE
  83    returns false to terminate the iteration and true to continue the
  84    iteration.  Return false if iteration is terminated by function
  85    OPERATE, otherwise return true.  */
  86 #define QUEUE_iterate(TYPE, Q, OPERATE, PARAM)  \
  87   queue_ ## TYPE ## _iterate ((Q), (OPERATE), (PARAM))
  88
  89 /* Remove the element per the state of iterator ITER from queue Q.
  90    Leave the caller to release the data in the queue element.  */
  91 #define QUEUE_remove_elem(TYPE, Q, ITER) \
  92   queue_ ## TYPE ## _remove_elem ((Q), (ITER))
  93
  94 /* Define a new queue implementation.  */
  95
  96 #define QUEUE(TYPE) struct queue_ ## TYPE
  97 #define QUEUE_ELEM(TYPE) struct queue_elem_ ## TYPE
  98 #define QUEUE_ITER(TYPE) struct queue_iter_ ## TYPE
  99 #define QUEUE_ITER_FUNC(TYPE) queue_ ## TYPE ## _operate_func
 100
 101 #define DEFINE_QUEUE_P(TYPE)                    \
 102 QUEUE_ELEM (TYPE)                               \
 103 {                                               \
 104   QUEUE_ELEM (TYPE) *next;                      \
 105                                                 \
 106   TYPE data;                                    \
 107 };                                              \
 108                                                 \
 109 /* Queue iterator.  */                          \
 110 QUEUE_ITER (TYPE)                               \
 111 {                                               \
 112   /* The current element during traverse.  */   \
 113   QUEUE_ELEM (TYPE) *p;                 \
 114   /* The previous element of P.  */             \
 115   QUEUE_ELEM (TYPE) *prev;                      \
 116 };                                              \
 117                                                 \
 118 QUEUE(TYPE)                                     \
 119 {                                               \
 120   /*  The head and tail of the queue.  */       \
 121   QUEUE_ELEM (TYPE) *head;                      \
 122   QUEUE_ELEM (TYPE) *tail;                      \
 123   /* Function to release the data put in each   \
 124      queue element.  */                 \
 125   void (*free_func) (TYPE);                     \
 126 };                                              \
 127                                                 \
 128 void                                                                    \
 129 queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v)                      \
 130 {                                                                       \
 131   QUEUE_ELEM (TYPE) *p                                                  \
 132     = xmalloc (sizeof (QUEUE_ELEM (TYPE)));                             \
 133                                                                         \
 134   gdb_assert (q != NULL);                                               \
 135   p->data = v;                                                          \
 136   p->next = NULL;                                                       \
 137   if (q->tail == NULL)                                                  \
 138     {                                                                   \
 139       q->tail = p;                                                      \
 140       q->head = p;                                                      \
 141     }                                                                   \
 142   else                                                                  \
 143     {                                                                   \
 144       q->tail->next = p;                                                \
 145       q->tail = p;                                                      \
 146     }                                                                   \
 147 }                                                                       \
 148                                                                         \
 149 TYPE                                                                    \
 150 queue_ ## TYPE ## _deque (QUEUE (TYPE) *q)                              \
 151 {                                                                       \
 152   QUEUE_ELEM (TYPE) *p;                                         \
 153   TYPE v;                                                               \
 154                                                                         \
 155   gdb_assert (q != NULL);                                               \
 156   p = q->head;                                                          \
 157   gdb_assert (p != NULL);                                               \
 158                                                                         \
 159   if (q->head == q->tail)                                               \
 160     {                                                                   \
 161       q->head = NULL;                                                   \
 162       q->tail = NULL;                                                   \
 163     }                                                                   \
 164   else                                                                  \
 165     q->head = q->head->next;                                            \
 166                                                                         \
 167   v = p->data;                                                          \
 168                                                                         \
 169   xfree (p);                                                            \
 170   return v;                                                             \
 171 }                                                                       \
 172                                                                         \
 173 TYPE                                                                    \
 174 queue_ ## TYPE ## _peek (QUEUE (TYPE) *q)                               \
 175 {                                                                       \
 176   gdb_assert (q != NULL);                                               \
 177   gdb_assert (q->head != NULL);                                 \
 178   return q->head->data;                                         \
 179 }                                                                       \
 180                                                                         \
 181 int                                                                     \
 182 queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q)                           \
 183 {                                                                       \
 184   gdb_assert (q != NULL);                                               \
 185   return q->head == NULL;                                               \
 186 }                                                                       \
 187                                                                         \
 188 void                                                                    \
 189 queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q,                        \
 190                                 QUEUE_ITER (TYPE) *iter)                \
 191 {                                                                       \
 192   gdb_assert (q != NULL);                                               \
 193   gdb_assert (iter != NULL && iter->p != NULL);                 \
 194                                                                         \
 195   if (iter->p == q->head || iter->p == q->tail)                 \
 196     {                                                                   \
 197       if (iter->p == q->head)                                           \
 198         q->head = iter->p->next;                                        \
 199       if (iter->p == q->tail)                                           \
 200         q->tail = iter->prev;                                           \
 201     }                                                                   \
 202   else                                                                  \
 203     iter->prev->next = iter->p->next;                                   \
 204                                                                         \
 205   xfree (iter->p);                                                      \
 206   /* Indicate that ITER->p has been deleted from QUEUE q.  */           \
 207   iter->p = NULL;                                                       \
 208 }                                                                       \
 209                                                                         \
 210 int                                                                     \
 211 queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q,                            \
 212                             QUEUE_ITER_FUNC (TYPE) operate,             \
 213                             void *data)                         \
 214 {                                                                       \
 215   QUEUE_ELEM (TYPE) *next = NULL;                                       \
 216   QUEUE_ITER (TYPE) iter = { NULL, NULL };                              \
 217                                                                         \
 218   gdb_assert (q != NULL);                                               \
 219                                                                         \
 220   for (iter.p = q->head; iter.p != NULL; iter.p = next)         \
 221     {                                                                   \
 222       next = iter.p->next;                                              \
 223       if (!operate (q, &iter, iter.p->data, data))                      \
 224         return 0;                                                       \
 225       /* ITER.P was not deleted by function OPERATE.  */                \
 226       if (iter.p != NULL)                                               \
 227         iter.prev = iter.p;                                             \
 228     }                                                                   \
 229   return 1;                                                             \
 230 }                                                                       \
 231                                                                         \
 232 QUEUE (TYPE) *                                                          \
 233 queue_ ## TYPE ## _alloc (void (*free_func) (TYPE))                     \
 234 {                                                                       \
 235   QUEUE (TYPE) *q;                                                      \
 236                                                                         \
 237   q = (QUEUE (TYPE) *) xmalloc (sizeof (QUEUE (TYPE)));         \
 238   q->head = NULL;                                                       \
 239   q->tail = NULL;                                                       \
 240   q->free_func = free_func;                                             \
 241   return q;                                                             \
 242 }                                                                       \
 243                                                                         \
 244 int                                                                     \
 245 queue_ ## TYPE ## _length (QUEUE (TYPE) *q)                             \
 246 {                                                                       \
 247   QUEUE_ELEM (TYPE) *p;                                         \
 248   int len = 0;                                                          \
 249                                                                         \
 250   gdb_assert (q != NULL);                                               \
 251                                                                         \
 252   for (p = q->head; p != NULL; p = p->next)                             \
 253     len++;                                                              \
 254                                                                         \
 255   return len;                                                           \
 256 }                                                                       \
 257                                                                         \
 258 void                                                                    \
 259 queue_ ## TYPE ## _free (QUEUE (TYPE) *q)                               \
 260 {                                                                       \
 261   QUEUE_ELEM (TYPE) *p, *next;                                          \
 262                                                                         \
 263   gdb_assert (q != NULL);                                               \
 264                                                                         \
 265   for (p = q->head; p != NULL; p = next)                                \
 266     {                                                                   \
 267       next = p->next;                                                   \
 268       if (q->free_func)                                         \
 269         q->free_func (p->data);                                 \
 270       xfree (p);                                                        \
 271     }                                                                   \
 272   xfree (q);                                                            \
 273 }                                                                       \
 274
 275 /* External declarations for queue functions.  */
 276 #define DECLARE_QUEUE_P(TYPE)                                   \
 277 QUEUE (TYPE);                                                   \
 278 QUEUE_ELEM (TYPE);                                              \
 279 QUEUE_ITER (TYPE);                                              \
 280 extern void                                                     \
 281   queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v);           \
 282 extern TYPE                                                     \
 283   queue_ ## TYPE ## _deque (QUEUE (TYPE) *q);                   \
 284 extern int queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q);       \
 285 extern QUEUE (TYPE) *                                           \
 286   queue_ ## TYPE ## _alloc (void (*free_func) (TYPE));          \
 287 extern int queue_ ## TYPE ## _length (QUEUE (TYPE) *q); \
 288 extern TYPE                                                     \
 289   queue_ ## TYPE ## _peek (QUEUE (TYPE) *q);                    \
 290 extern void queue_ ## TYPE ## _free (QUEUE (TYPE) *q);          \
 291 typedef int QUEUE_ITER_FUNC(TYPE) (QUEUE (TYPE) *,              \
 292                                    QUEUE_ITER (TYPE) *, \
 293                                    TYPE,                        \
 294                                    void *);                     \
 295 extern int                                                      \
 296   queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q,                  \
 297                               QUEUE_ITER_FUNC (TYPE) operate,   \
 298                               void *);                          \
 299 extern void                                                     \
 300   queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q,              \
 301                                   QUEUE_ITER (TYPE) *iter);     \
 302
 303 #endif /* QUEUE_H */