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