GDB (xrefs)
queue.h
Go to the documentation of this file.
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 */