This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [PATCH 1/7] new queue.h in common/.
- From: Pedro Alves <palves at redhat dot com>
- To: Yao Qi <yao at codesourcery dot com>
- Cc: gdb-patches at sourceware dot org
- Date: Thu, 29 Nov 2012 15:45:37 +0000
- Subject: Re: [PATCH 1/7] new queue.h in common/.
- References: <1350991620-12950-1-git-send-email-yao@codesourcery.com> <1350991620-12950-2-git-send-email-yao@codesourcery.com>
On 10/23/2012 12:26 PM, Yao Qi wrote:
> Hi,
> When writing the patches for 'general notification', I find queue is
> used in many places, so I think we may need a general queue. This
> queue not only have typical operations enqueue and dequeue, but also
> has some have some operations like remove and remove_all.
>
> gdb/
>
> 2012-10-23 Yao Qi <yao@codesourcery.com>
> Doug Evans <dje@google.com>
>
> * common/queue.h: New.
> ---
> gdb/common/queue.h | 274 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 files changed, 274 insertions(+), 0 deletions(-)
> create mode 100644 gdb/common/queue.h
>
> diff --git a/gdb/common/queue.h b/gdb/common/queue.h
> new file mode 100644
> index 0000000..de13879
> --- /dev/null
> +++ b/gdb/common/queue.h
> @@ -0,0 +1,274 @@
> +/* 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/>. */
> +
> +/* These macros implement functions and structs for a general queue. Macro
> + 'DEFINE_QUEUE_P(TYPE)' is to define the new queue type for 'TYPE', and
> + macro 'DECLARE_QUEUE_P' is to declare these external APIs. */
> +
> +#ifndef QUEUE_H
> +#define QUEUE_H
> +
> +#include <stdio.h>
Why's this one necessary?
> +
> +#include "libiberty.h" /* xmalloc */
> +#include "gdb_assert.h"
> +
> +/* Define a new queue implementation. */
> +
It'd be very nice if this included an intro comment block on _usage_,
like vec.h.
> +#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) \
> +{ \
> + QUEUE_ELEM (TYPE) *head; \
> + QUEUE_ELEM (TYPE) *tail; \
> + void (*free_func) (TYPE); \
This is missing documentation. Particularly, what is
free_func responsible for freeing.
> +}; \
> + \
> +/* Typical enqueue operation. Put V into queue Q. */ \
> + \
> +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; \
> + } \
> +} \
> + \
> +/* Typical dequeue operation.
> Return one element queue Q.
Suggest:
"Remove the head element of Q, and return it."
> Assert \
> + fail if Q is NULL or Q is empty. */ \
"Assert" is how a requirement is enforced, not the requirement itself.
Suggest: Q must not be empty".
> + \
> +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; \
> +} \
> + \
> +/* Return the element on head, but don't remove it from queue. Assert \
> + fail is Q is NULL or Q is empty. */ \
Suggest:
"Return the head element of Q, but don't remove it from the queue."
> + \
> +TYPE \
> +queue_ ## TYPE ## _peek (QUEUE (TYPE) *q) \
> +{ \
> + gdb_assert (q != NULL); \
> + gdb_assert (q->head != NULL); \
> + return q->head->data; \
> +} \
> + \
> +/* Return true if queue Q is empty. */ \
> + \
> +int \
> +queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q) \
> +{ \
> + gdb_assert (q != NULL); \
> + return q->head == NULL; \
> +} \
> + \
> +/* Remove the element per the state of iterator ITER from queue Q. */ \
> + \
> +void \
> +queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \
> + QUEUE_ITER (TYPE) *iter) \
> +{ \
> + gdb_assert (q != NULL); \
> + gdb_assert (iter != NULL && iter->p != NULL); \
Wrong indentation.
> + \
> + 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); \
Don't we need to call free_func ?
> + /* Indicate that ITER->p has been deleted from QUEUE q. */ \
> + iter->p = NULL; \
> +} \
> + \
> +/* Iterate over elements in the queue Q and call function OPERATE on \
> + each element. OPERATE would return false to terminate the \
> + iteration and true to continue the iteration. Return false if \
> + iteration is terminated by function OPERATE, otherwise return \
> + true. */ \
s/would return/returns/
The fact that it is valid to for OPERATE to remove the current
element should be documented.
> + \
> +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; \
> +} \
> + \
> +/* Allocate memory for queue. */ \
> + \
> +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; \
> +} \
> + \
> +/* Length of queue 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; \
> +} \
> + \
> +/* Free memory for queue Q. */ \
s/for/of/ Given free_func, it may not just be memory.
I suggest:
/* Free queue Q. Q's free_func is called once for each element. */
> + \
> +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 these functions. */
Which "these"?
> +#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); \
> +
> +#define QUEUE_enque(TYPE, QUEUE, V) queue_ ## TYPE ## _enque ((QUEUE), (V))
> +#define QUEUE_deque(TYPE, QUEUE) queue_ ## TYPE ## _deque (QUEUE)
> +#define QUEUE_peek(TYPE, QUEUE) queue_ ## TYPE ## _peek (QUEUE)
> +#define QUEUE_is_empty(TYPE, QUEUE) queue_ ## TYPE ## _is_empty (QUEUE)
> +#define QUEUE_alloc(TYPE, FREE_FUNC) queue_ ## TYPE ## _alloc (FREE_FUNC)
> +#define QUEUE_length(TYPE, QUEUE) queue_ ## TYPE ## _length (QUEUE)
> +#define QUEUE_free(TYPE, QUEUE) queue_ ## TYPE ## _free (QUEUE)
> +#define QUEUE_iterate(TYPE, QUEUE, OPERATE, PARAM) \
> + queue_ ## TYPE ## _iterate ((QUEUE), (OPERATE), (PARAM))
> +#define QUEUE_remove_elem(TYPE, QUEUE, ITER) \
> + queue_ ## TYPE ## _remove_elem ((QUEUE), (ITER))
> +
> +#endif /* QUEUE_H */
--
Pedro Alves