diff options
Diffstat (limited to 'gdb/common/queue.h')
| -rw-r--r-- | gdb/common/queue.h | 303 |
1 files changed, 303 insertions, 0 deletions
diff --git a/gdb/common/queue.h b/gdb/common/queue.h new file mode 100644 index 0000000..bf48cdf --- /dev/null +++ b/gdb/common/queue.h @@ -0,0 +1,303 @@ +/* General queue data structure for GDB, the GNU debugger. + + Copyright (C) 2012 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 + +#include "libiberty.h" /* xmalloc */ +#include "gdb_assert.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 \ + = xmalloc (sizeof (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; \ + \ + q = (QUEUE (TYPE) *) xmalloc (sizeof (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 */ |