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 */