| /* General queue data structure for GDB, the GNU debugger. |
| |
| Copyright (C) 2012-2017 Free Software Foundation, Inc. |
| |
| This file is part of GDB. |
| |
| This program is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| |
| #ifndef QUEUE_H |
| #define QUEUE_H |
| |
| /* These macros implement functions and structs for a general queue. |
| Macro 'DEFINE_QUEUE_P(TYPEDEF)' is to define the new queue type for |
| TYPEDEF', and macro 'DECLARE_QUEUE_P' is to declare external queue |
| APIs. The character P indicates TYPEDEF is a pointer (P). The |
| counterpart on object (O) and integer (I) are not implemented. |
| |
| An example of their use would be, |
| |
| typedef struct foo |
| {} *foo_p; |
| |
| DEFINE_QUEUE_P (foo_p); |
| // A pointer to a queue of foo pointers. FOO_XFREE is a destructor |
| // function for foo instances in queue. |
| QUEUE(foo_p) *foo_queue = QUEUE_alloc (foo_p, foo_xfree); |
| |
| foo_p foo_var_p; |
| // Enqueue and Dequeue |
| QUEUE_enque (foo_p, foo_queue, foo_var_p); |
| foo_var_p = QUEUE_deque (foo_p, foo_queue); |
| |
| static int visit_foo (QUEUE (foo_p) *q, QUEUE_ITER (foo_p) *iter, |
| foo_p f, void *data) |
| { |
| return 1; |
| } |
| // Iterate over queue. |
| QUEUE_iterate (foo_p, foo_queue, visit_foo, ¶m); |
| |
| QUEUE_free (foo_p, foo_queue); // Free queue. */ |
| |
| /* Typical enqueue operation. Put V into queue Q. */ |
| #define QUEUE_enque(TYPE, Q, V) queue_ ## TYPE ## _enque ((Q), (V)) |
| |
| /* Typical dequeue operation. Return head element of queue Q and |
| remove it. Q must not be empty. */ |
| #define QUEUE_deque(TYPE, Q) queue_ ## TYPE ## _deque (Q) |
| |
| /* Return the head element, but don't remove it from the queue. |
| Q must not be empty. */ |
| #define QUEUE_peek(TYPE, Q) queue_ ## TYPE ## _peek (Q) |
| |
| /* Return true if queue Q is empty. */ |
| #define QUEUE_is_empty(TYPE, Q) queue_ ## TYPE ## _is_empty (Q) |
| |
| /* Allocate memory for queue. FREE_FUNC is a function to release the |
| data put in each queue element. */ |
| #define QUEUE_alloc(TYPE, FREE_FUNC) queue_ ## TYPE ## _alloc (FREE_FUNC) |
| |
| /* Length of queue Q. */ |
| #define QUEUE_length(TYPE, Q) queue_ ## TYPE ## _length (Q) |
| |
| /* Free queue Q. Q's free_func is called once for each element. */ |
| #define QUEUE_free(TYPE, Q) queue_ ## TYPE ## _free (Q) |
| |
| /* Iterate over elements in the queue Q and call function OPERATE on |
| each element. It is allowed to remove element by OPERATE. OPERATE |
| returns false to terminate the iteration and true to continue the |
| iteration. Return false if iteration is terminated by function |
| OPERATE, otherwise return true. */ |
| #define QUEUE_iterate(TYPE, Q, OPERATE, PARAM) \ |
| queue_ ## TYPE ## _iterate ((Q), (OPERATE), (PARAM)) |
| |
| /* Remove the element per the state of iterator ITER from queue Q. |
| Leave the caller to release the data in the queue element. */ |
| #define QUEUE_remove_elem(TYPE, Q, ITER) \ |
| queue_ ## TYPE ## _remove_elem ((Q), (ITER)) |
| |
| /* Define a new queue implementation. */ |
| |
| #define QUEUE(TYPE) struct queue_ ## TYPE |
| #define QUEUE_ELEM(TYPE) struct queue_elem_ ## TYPE |
| #define QUEUE_ITER(TYPE) struct queue_iter_ ## TYPE |
| #define QUEUE_ITER_FUNC(TYPE) queue_ ## TYPE ## _operate_func |
| |
| #define DEFINE_QUEUE_P(TYPE) \ |
| QUEUE_ELEM (TYPE) \ |
| { \ |
| QUEUE_ELEM (TYPE) *next; \ |
| \ |
| TYPE data; \ |
| }; \ |
| \ |
| /* Queue iterator. */ \ |
| QUEUE_ITER (TYPE) \ |
| { \ |
| /* The current element during traverse. */ \ |
| QUEUE_ELEM (TYPE) *p; \ |
| /* The previous element of P. */ \ |
| QUEUE_ELEM (TYPE) *prev; \ |
| }; \ |
| \ |
| QUEUE(TYPE) \ |
| { \ |
| /* The head and tail of the queue. */ \ |
| QUEUE_ELEM (TYPE) *head; \ |
| QUEUE_ELEM (TYPE) *tail; \ |
| /* Function to release the data put in each \ |
| queue element. */ \ |
| void (*free_func) (TYPE); \ |
| }; \ |
| \ |
| void \ |
| queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v) \ |
| { \ |
| QUEUE_ELEM (TYPE) *p = XNEW (QUEUE_ELEM (TYPE)); \ |
| \ |
| gdb_assert (q != NULL); \ |
| p->data = v; \ |
| p->next = NULL; \ |
| if (q->tail == NULL) \ |
| { \ |
| q->tail = p; \ |
| q->head = p; \ |
| } \ |
| else \ |
| { \ |
| q->tail->next = p; \ |
| q->tail = p; \ |
| } \ |
| } \ |
| \ |
| TYPE \ |
| queue_ ## TYPE ## _deque (QUEUE (TYPE) *q) \ |
| { \ |
| QUEUE_ELEM (TYPE) *p; \ |
| TYPE v; \ |
| \ |
| gdb_assert (q != NULL); \ |
| p = q->head; \ |
| gdb_assert (p != NULL); \ |
| \ |
| if (q->head == q->tail) \ |
| { \ |
| q->head = NULL; \ |
| q->tail = NULL; \ |
| } \ |
| else \ |
| q->head = q->head->next; \ |
| \ |
| v = p->data; \ |
| \ |
| xfree (p); \ |
| return v; \ |
| } \ |
| \ |
| TYPE \ |
| queue_ ## TYPE ## _peek (QUEUE (TYPE) *q) \ |
| { \ |
| gdb_assert (q != NULL); \ |
| gdb_assert (q->head != NULL); \ |
| return q->head->data; \ |
| } \ |
| \ |
| int \ |
| queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q) \ |
| { \ |
| gdb_assert (q != NULL); \ |
| return q->head == NULL; \ |
| } \ |
| \ |
| void \ |
| queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \ |
| QUEUE_ITER (TYPE) *iter) \ |
| { \ |
| gdb_assert (q != NULL); \ |
| gdb_assert (iter != NULL && iter->p != NULL); \ |
| \ |
| if (iter->p == q->head || iter->p == q->tail) \ |
| { \ |
| if (iter->p == q->head) \ |
| q->head = iter->p->next; \ |
| if (iter->p == q->tail) \ |
| q->tail = iter->prev; \ |
| } \ |
| else \ |
| iter->prev->next = iter->p->next; \ |
| \ |
| xfree (iter->p); \ |
| /* Indicate that ITER->p has been deleted from QUEUE q. */ \ |
| iter->p = NULL; \ |
| } \ |
| \ |
| int \ |
| queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \ |
| QUEUE_ITER_FUNC (TYPE) operate, \ |
| void *data) \ |
| { \ |
| QUEUE_ELEM (TYPE) *next = NULL; \ |
| QUEUE_ITER (TYPE) iter = { NULL, NULL }; \ |
| \ |
| gdb_assert (q != NULL); \ |
| \ |
| for (iter.p = q->head; iter.p != NULL; iter.p = next) \ |
| { \ |
| next = iter.p->next; \ |
| if (!operate (q, &iter, iter.p->data, data)) \ |
| return 0; \ |
| /* ITER.P was not deleted by function OPERATE. */ \ |
| if (iter.p != NULL) \ |
| iter.prev = iter.p; \ |
| } \ |
| return 1; \ |
| } \ |
| \ |
| QUEUE (TYPE) * \ |
| queue_ ## TYPE ## _alloc (void (*free_func) (TYPE)) \ |
| { \ |
| QUEUE (TYPE) *q = XNEW (QUEUE (TYPE)); \ |
| \ |
| q->head = NULL; \ |
| q->tail = NULL; \ |
| q->free_func = free_func; \ |
| return q; \ |
| } \ |
| \ |
| int \ |
| queue_ ## TYPE ## _length (QUEUE (TYPE) *q) \ |
| { \ |
| QUEUE_ELEM (TYPE) *p; \ |
| int len = 0; \ |
| \ |
| gdb_assert (q != NULL); \ |
| \ |
| for (p = q->head; p != NULL; p = p->next) \ |
| len++; \ |
| \ |
| return len; \ |
| } \ |
| \ |
| void \ |
| queue_ ## TYPE ## _free (QUEUE (TYPE) *q) \ |
| { \ |
| QUEUE_ELEM (TYPE) *p, *next; \ |
| \ |
| gdb_assert (q != NULL); \ |
| \ |
| for (p = q->head; p != NULL; p = next) \ |
| { \ |
| next = p->next; \ |
| if (q->free_func) \ |
| q->free_func (p->data); \ |
| xfree (p); \ |
| } \ |
| xfree (q); \ |
| } \ |
| |
| /* External declarations for queue functions. */ |
| #define DECLARE_QUEUE_P(TYPE) \ |
| QUEUE (TYPE); \ |
| QUEUE_ELEM (TYPE); \ |
| QUEUE_ITER (TYPE); \ |
| extern void \ |
| queue_ ## TYPE ## _enque (QUEUE (TYPE) *q, TYPE v); \ |
| extern TYPE \ |
| queue_ ## TYPE ## _deque (QUEUE (TYPE) *q); \ |
| extern int queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q); \ |
| extern QUEUE (TYPE) * \ |
| queue_ ## TYPE ## _alloc (void (*free_func) (TYPE)); \ |
| extern int queue_ ## TYPE ## _length (QUEUE (TYPE) *q); \ |
| extern TYPE \ |
| queue_ ## TYPE ## _peek (QUEUE (TYPE) *q); \ |
| extern void queue_ ## TYPE ## _free (QUEUE (TYPE) *q); \ |
| typedef int QUEUE_ITER_FUNC(TYPE) (QUEUE (TYPE) *, \ |
| QUEUE_ITER (TYPE) *, \ |
| TYPE, \ |
| void *); \ |
| extern int \ |
| queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \ |
| QUEUE_ITER_FUNC (TYPE) operate, \ |
| void *); \ |
| extern void \ |
| queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \ |
| QUEUE_ITER (TYPE) *iter); \ |
| |
| #endif /* QUEUE_H */ |