gdb/common/queue.h

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