1 /* General queue data structure for GDB, the GNU debugger. 2 3 Copyright (C) 2012-2013 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 #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 */ 304