1 /* General queue data structure for GDB, the GNU debugger.
3 Copyright (C) 2012-2014 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 #include "libiberty.h" /* xmalloc */
24 #include "gdb_assert.h"
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.
32 An example of their use would be,
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);
43 // Enqueue and Dequeue
44 QUEUE_enque (foo_p, foo_queue, foo_var_p);
45 foo_var_p = QUEUE_deque (foo_p, foo_queue);
47 static int visit_foo (QUEUE (foo_p) *q, QUEUE_ITER (foo_p) *iter,
52 // Iterate over queue.
53 QUEUE_iterate (foo_p, foo_queue, visit_foo, ¶m);
55 QUEUE_free (foo_p, foo_queue); // Free queue. */
57 /* Typical enqueue operation. Put V into queue Q. */
58 #define QUEUE_enque(TYPE, Q, V) queue_ ## TYPE ## _enque ((Q), (V))
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)
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)
68 /* Return true if queue Q is empty. */
69 #define QUEUE_is_empty(TYPE, Q) queue_ ## TYPE ## _is_empty (Q)
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)
75 /* Length of queue Q. */
76 #define QUEUE_length(TYPE, Q) queue_ ## TYPE ## _length (Q)
78 /* Free queue Q. Q's free_func is called once for each element. */
79 #define QUEUE_free(TYPE, Q) queue_ ## TYPE ## _free (Q)
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))
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))
94 /* Define a new queue implementation. */
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
101 #define DEFINE_QUEUE_P(TYPE) \
104 QUEUE_ELEM (TYPE) *next; \
109 /* Queue iterator. */ \
112 /* The current element during traverse. */ \
113 QUEUE_ELEM (TYPE) *p; \
114 /* The previous element of P. */ \
115 QUEUE_ELEM (TYPE) *prev; \
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 \
125 void (*free_func) (TYPE); \
129 queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v) \
131 QUEUE_ELEM (TYPE) *p \
132 = xmalloc (sizeof (QUEUE_ELEM (TYPE))); \
134 gdb_assert (q != NULL); \
137 if (q->tail == NULL) \
150 queue_ ## TYPE ## _deque (QUEUE (TYPE) *q) \
152 QUEUE_ELEM (TYPE) *p; \
155 gdb_assert (q != NULL); \
157 gdb_assert (p != NULL); \
159 if (q->head == q->tail) \
165 q->head = q->head->next; \
174 queue_ ## TYPE ## _peek (QUEUE (TYPE) *q) \
176 gdb_assert (q != NULL); \
177 gdb_assert (q->head != NULL); \
178 return q->head->data; \
182 queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q) \
184 gdb_assert (q != NULL); \
185 return q->head == NULL; \
189 queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \
190 QUEUE_ITER (TYPE) *iter) \
192 gdb_assert (q != NULL); \
193 gdb_assert (iter != NULL && iter->p != NULL); \
195 if (iter->p == q->head || iter->p == q->tail) \
197 if (iter->p == q->head) \
198 q->head = iter->p->next; \
199 if (iter->p == q->tail) \
200 q->tail = iter->prev; \
203 iter->prev->next = iter->p->next; \
206 /* Indicate that ITER->p has been deleted from QUEUE q. */ \
211 queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \
212 QUEUE_ITER_FUNC (TYPE) operate, \
215 QUEUE_ELEM (TYPE) *next = NULL; \
216 QUEUE_ITER (TYPE) iter = { NULL, NULL }; \
218 gdb_assert (q != NULL); \
220 for (iter.p = q->head; iter.p != NULL; iter.p = next) \
222 next = iter.p->next; \
223 if (!operate (q, &iter, iter.p->data, data)) \
225 /* ITER.P was not deleted by function OPERATE. */ \
226 if (iter.p != NULL) \
227 iter.prev = iter.p; \
233 queue_ ## TYPE ## _alloc (void (*free_func) (TYPE)) \
237 q = (QUEUE (TYPE) *) xmalloc (sizeof (QUEUE (TYPE))); \
240 q->free_func = free_func; \
245 queue_ ## TYPE ## _length (QUEUE (TYPE) *q) \
247 QUEUE_ELEM (TYPE) *p; \
250 gdb_assert (q != NULL); \
252 for (p = q->head; p != NULL; p = p->next) \
259 queue_ ## TYPE ## _free (QUEUE (TYPE) *q) \
261 QUEUE_ELEM (TYPE) *p, *next; \
263 gdb_assert (q != NULL); \
265 for (p = q->head; p != NULL; p = next) \
269 q->free_func (p->data); \
275 /* External declarations for queue functions. */
276 #define DECLARE_QUEUE_P(TYPE) \
281 queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v); \
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); \
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) *, \
296 queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \
297 QUEUE_ITER_FUNC (TYPE) operate, \
300 queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \
301 QUEUE_ITER (TYPE) *iter); \
This page took 0.040434 seconds and 4 git commands to generate.