gdb/common/queue.h

   1 /* General queue data structure for GDB, the GNU debugger.
   2
   3    Copyright (C) 2012-2019 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 COMMON_QUEUE_H
  21 #define COMMON_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 = XNEW (QUEUE_ELEM (TYPE));                      \
 129                                                                         \
 130   gdb_assert (q != NULL);                                               \
 131   p->data = v;                                                          \
 132   p->next = NULL;                                                       \
 133   if (q->tail == NULL)                                                  \
 134     {                                                                   \
 135       q->tail = p;                                                      \
 136       q->head = p;                                                      \
 137     }                                                                   \
 138   else                                                                  \
 139     {                                                                   \
 140       q->tail->next = p;                                                \
 141       q->tail = p;                                                      \
 142     }                                                                   \
 143 }                                                                       \
 144                                                                         \
 145 TYPE                                                                    \
 146 queue_ ## TYPE ## _deque (QUEUE (TYPE) *q)                              \
 147 {                                                                       \
 148   QUEUE_ELEM (TYPE) *p;                                         \
 149   TYPE v;                                                               \
 150                                                                         \
 151   gdb_assert (q != NULL);                                               \
 152   p = q->head;                                                          \
 153   gdb_assert (p != NULL);                                               \
 154                                                                         \
 155   if (q->head == q->tail)                                               \
 156     {                                                                   \
 157       q->head = NULL;                                                   \
 158       q->tail = NULL;                                                   \
 159     }                                                                   \
 160   else                                                                  \
 161     q->head = q->head->next;                                            \
 162                                                                         \
 163   v = p->data;                                                          \
 164                                                                         \
 165   xfree (p);                                                            \
 166   return v;                                                             \
 167 }                                                                       \
 168                                                                         \
 169 TYPE                                                                    \
 170 queue_ ## TYPE ## _peek (QUEUE (TYPE) *q)                               \
 171 {                                                                       \
 172   gdb_assert (q != NULL);                                               \
 173   gdb_assert (q->head != NULL);                                 \
 174   return q->head->data;                                         \
 175 }                                                                       \
 176                                                                         \
 177 int                                                                     \
 178 queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q)                           \
 179 {                                                                       \
 180   gdb_assert (q != NULL);                                               \
 181   return q->head == NULL;                                               \
 182 }                                                                       \
 183                                                                         \
 184 void                                                                    \
 185 queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q,                        \
 186                                 QUEUE_ITER (TYPE) *iter)                \
 187 {                                                                       \
 188   gdb_assert (q != NULL);                                               \
 189   gdb_assert (iter != NULL && iter->p != NULL);                 \
 190                                                                         \
 191   if (iter->p == q->head || iter->p == q->tail)                 \
 192     {                                                                   \
 193       if (iter->p == q->head)                                           \
 194         q->head = iter->p->next;                                        \
 195       if (iter->p == q->tail)                                           \
 196         q->tail = iter->prev;                                           \
 197     }                                                                   \
 198   else                                                                  \
 199     iter->prev->next = iter->p->next;                                   \
 200                                                                         \
 201   xfree (iter->p);                                                      \
 202   /* Indicate that ITER->p has been deleted from QUEUE q.  */           \
 203   iter->p = NULL;                                                       \
 204 }                                                                       \
 205                                                                         \
 206 int                                                                     \
 207 queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q,                            \
 208                             QUEUE_ITER_FUNC (TYPE) operate,             \
 209                             void *data)                         \
 210 {                                                                       \
 211   QUEUE_ELEM (TYPE) *next = NULL;                                       \
 212   QUEUE_ITER (TYPE) iter = { NULL, NULL };                              \
 213                                                                         \
 214   gdb_assert (q != NULL);                                               \
 215                                                                         \
 216   for (iter.p = q->head; iter.p != NULL; iter.p = next)         \
 217     {                                                                   \
 218       next = iter.p->next;                                              \
 219       if (!operate (q, &iter, iter.p->data, data))                      \
 220         return 0;                                                       \
 221       /* ITER.P was not deleted by function OPERATE.  */                \
 222       if (iter.p != NULL)                                               \
 223         iter.prev = iter.p;                                             \
 224     }                                                                   \
 225   return 1;                                                             \
 226 }                                                                       \
 227                                                                         \
 228 QUEUE (TYPE) *                                                          \
 229 queue_ ## TYPE ## _alloc (void (*free_func) (TYPE))                     \
 230 {                                                                       \
 231   QUEUE (TYPE) *q = XNEW (QUEUE (TYPE));                                \
 232                                                                         \
 233   q->head = NULL;                                                       \
 234   q->tail = NULL;                                                       \
 235   q->free_func = free_func;                                             \
 236   return q;                                                             \
 237 }                                                                       \
 238                                                                         \
 239 int                                                                     \
 240 queue_ ## TYPE ## _length (QUEUE (TYPE) *q)                             \
 241 {                                                                       \
 242   QUEUE_ELEM (TYPE) *p;                                         \
 243   int len = 0;                                                          \
 244                                                                         \
 245   gdb_assert (q != NULL);                                               \
 246                                                                         \
 247   for (p = q->head; p != NULL; p = p->next)                             \
 248     len++;                                                              \
 249                                                                         \
 250   return len;                                                           \
 251 }                                                                       \
 252                                                                         \
 253 void                                                                    \
 254 queue_ ## TYPE ## _free (QUEUE (TYPE) *q)                               \
 255 {                                                                       \
 256   QUEUE_ELEM (TYPE) *p, *next;                                          \
 257                                                                         \
 258   gdb_assert (q != NULL);                                               \
 259                                                                         \
 260   for (p = q->head; p != NULL; p = next)                                \
 261     {                                                                   \
 262       next = p->next;                                                   \
 263       if (q->free_func)                                         \
 264         q->free_func (p->data);                                 \
 265       xfree (p);                                                        \
 266     }                                                                   \
 267   xfree (q);                                                            \
 268 }                                                                       \
 269
 270 /* External declarations for queue functions.  */
 271 #define DECLARE_QUEUE_P(TYPE)                                   \
 272 QUEUE (TYPE);                                                   \
 273 QUEUE_ELEM (TYPE);                                              \
 274 QUEUE_ITER (TYPE);                                              \
 275 extern void                                                     \
 276   queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v);           \
 277 extern TYPE                                                     \
 278   queue_ ## TYPE ## _deque (QUEUE (TYPE) *q);                   \
 279 extern int queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q);       \
 280 extern QUEUE (TYPE) *                                           \
 281   queue_ ## TYPE ## _alloc (void (*free_func) (TYPE));          \
 282 extern int queue_ ## TYPE ## _length (QUEUE (TYPE) *q); \
 283 extern TYPE                                                     \
 284   queue_ ## TYPE ## _peek (QUEUE (TYPE) *q);                    \
 285 extern void queue_ ## TYPE ## _free (QUEUE (TYPE) *q);          \
 286 typedef int QUEUE_ITER_FUNC(TYPE) (QUEUE (TYPE) *,              \
 287                                    QUEUE_ITER (TYPE) *, \
 288                                    TYPE,                        \
 289                                    void *);                     \
 290 extern int                                                      \
 291   queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q,                  \
 292                               QUEUE_ITER_FUNC (TYPE) operate,   \
 293                               void *);                          \
 294 extern void                                                     \
 295   queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q,              \
 296                                   QUEUE_ITER (TYPE) *iter);     \
 297
 298 #endif /* COMMON_QUEUE_H */