1 /* General queue data structure for GDB, the GNU debugger.
3 Copyright (C) 2012-2015 Free Software Foundation, Inc.
5 This file is part of GDB.
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.
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.
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/>. */
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.
29 An example of their use would be,
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);
40 // Enqueue and Dequeue
41 QUEUE_enque (foo_p, foo_queue, foo_var_p);
42 foo_var_p = QUEUE_deque (foo_p, foo_queue);
44 static int visit_foo (QUEUE (foo_p) *q, QUEUE_ITER (foo_p) *iter,
49 // Iterate over queue.
50 QUEUE_iterate (foo_p, foo_queue, visit_foo, ¶m);
52 QUEUE_free (foo_p, foo_queue); // Free queue. */
54 /* Typical enqueue operation. Put V into queue Q. */
55 #define QUEUE_enque(TYPE, Q, V) queue_ ## TYPE ## _enque ((Q), (V))
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)
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)
65 /* Return true if queue Q is empty. */
66 #define QUEUE_is_empty(TYPE, Q) queue_ ## TYPE ## _is_empty (Q)
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)
72 /* Length of queue Q. */
73 #define QUEUE_length(TYPE, Q) queue_ ## TYPE ## _length (Q)
75 /* Free queue Q. Q's free_func is called once for each element. */
76 #define QUEUE_free(TYPE, Q) queue_ ## TYPE ## _free (Q)
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))
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))
91 /* Define a new queue implementation. */
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
98 #define DEFINE_QUEUE_P(TYPE) \
101 QUEUE_ELEM (TYPE) *next; \
106 /* Queue iterator. */ \
109 /* The current element during traverse. */ \
110 QUEUE_ELEM (TYPE) *p; \
111 /* The previous element of P. */ \
112 QUEUE_ELEM (TYPE) *prev; \
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 \
122 void (*free_func) (TYPE); \
126 queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v) \
128 QUEUE_ELEM (TYPE) *p \
129 = xmalloc (sizeof (QUEUE_ELEM (TYPE))); \
131 gdb_assert (q != NULL); \
134 if (q->tail == NULL) \
147 queue_ ## TYPE ## _deque (QUEUE (TYPE) *q) \
149 QUEUE_ELEM (TYPE) *p; \
152 gdb_assert (q != NULL); \
154 gdb_assert (p != NULL); \
156 if (q->head == q->tail) \
162 q->head = q->head->next; \
171 queue_ ## TYPE ## _peek (QUEUE (TYPE) *q) \
173 gdb_assert (q != NULL); \
174 gdb_assert (q->head != NULL); \
175 return q->head->data; \
179 queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q) \
181 gdb_assert (q != NULL); \
182 return q->head == NULL; \
186 queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \
187 QUEUE_ITER (TYPE) *iter) \
189 gdb_assert (q != NULL); \
190 gdb_assert (iter != NULL && iter->p != NULL); \
192 if (iter->p == q->head || iter->p == q->tail) \
194 if (iter->p == q->head) \
195 q->head = iter->p->next; \
196 if (iter->p == q->tail) \
197 q->tail = iter->prev; \
200 iter->prev->next = iter->p->next; \
203 /* Indicate that ITER->p has been deleted from QUEUE q. */ \
208 queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \
209 QUEUE_ITER_FUNC (TYPE) operate, \
212 QUEUE_ELEM (TYPE) *next = NULL; \
213 QUEUE_ITER (TYPE) iter = { NULL, NULL }; \
215 gdb_assert (q != NULL); \
217 for (iter.p = q->head; iter.p != NULL; iter.p = next) \
219 next = iter.p->next; \
220 if (!operate (q, &iter, iter.p->data, data)) \
222 /* ITER.P was not deleted by function OPERATE. */ \
223 if (iter.p != NULL) \
224 iter.prev = iter.p; \
230 queue_ ## TYPE ## _alloc (void (*free_func) (TYPE)) \
234 q = (QUEUE (TYPE) *) xmalloc (sizeof (QUEUE (TYPE))); \
237 q->free_func = free_func; \
242 queue_ ## TYPE ## _length (QUEUE (TYPE) *q) \
244 QUEUE_ELEM (TYPE) *p; \
247 gdb_assert (q != NULL); \
249 for (p = q->head; p != NULL; p = p->next) \
256 queue_ ## TYPE ## _free (QUEUE (TYPE) *q) \
258 QUEUE_ELEM (TYPE) *p, *next; \
260 gdb_assert (q != NULL); \
262 for (p = q->head; p != NULL; p = next) \
266 q->free_func (p->data); \
272 /* External declarations for queue functions. */
273 #define DECLARE_QUEUE_P(TYPE) \
278 queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v); \
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); \
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) *, \
293 queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \
294 QUEUE_ITER_FUNC (TYPE) operate, \
297 queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \
298 QUEUE_ITER (TYPE) *iter); \
This page took 0.034792 seconds and 4 git commands to generate.