Commit | Line | Data |
---|---|---|
dbb0cf06 YQ |
1 | /* General queue data structure for GDB, the GNU debugger. |
2 | ||
42a4f53d | 3 | Copyright (C) 2012-2019 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 | ||
dbb0cf06 YQ |
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, ¶m); | |
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 | { \ | |
8d749320 | 128 | QUEUE_ELEM (TYPE) *p = XNEW (QUEUE_ELEM (TYPE)); \ |
dbb0cf06 YQ |
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 | { \ | |
8d749320 | 231 | QUEUE (TYPE) *q = XNEW (QUEUE (TYPE)); \ |
dbb0cf06 | 232 | \ |
dbb0cf06 YQ |
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 */ |