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-2018 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 = 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 /* QUEUE_H */
Generated by   doxygen 1.8.14