gdb/common/queue.h

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