This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [PATCH 1/4] new gdb_queue.h in common/.
- From: dje at google dot com
- To: Yao Qi <yao at codesourcery dot com>
- Cc: <gdb-patches at sourceware dot org>
- Date: Mon, 10 Sep 2012 13:47:15 -0700
- Subject: Re: [PATCH 1/4] new gdb_queue.h in common/.
- References: <1345775139-13576-1-git-send-email-yao@codesourcery.com> <1345775139-13576-2-git-send-email-yao@codesourcery.com> <20535.52070.49473.442620@ruffy2.mtv.corp.google.com> <503DE3E0.5070803@codesourcery.com> <20550.27760.260327.470212@ruffy2.mtv.corp.google.com> <50495FFA.5080107@codesourcery.com>
Yao Qi writes:
> On 09/05/2012 05:02 AM, dje@google.com wrote:
> > [...]
> > I like thinner APIs than fatter ones, but in this case I'm not sure
> > this is better (or worth it).
> > Thoughts?
> >
>
> Yeah, I agree. However, 'remove/remove_matching/find' are clear, but
> 'iterate' with different callbacks to achieve the same task are hard to
> read. I post an implementation of _iterate method, and either way is OK
> to me.
They're ok for me to read. It might be more a matter of frequency of use.
> 2012-09-06 Yao Qi <yao@codesourcery.com>
>
> * common/queue.h: New.
> ---
> gdb/common/queue.h | 292 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 files changed, 292 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..fff6778
> --- /dev/null
> +++ b/gdb/common/queue.h
> @@ -0,0 +1,292 @@
> +/* 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_TYPE(TYPE)' is to define the new queue type for
> + 'TYPE', and macro 'DECLARE_QUEUE' *is to declare these external
> + APIs. */
> +
> +#ifndef QUEUE_H
> +#define QUEUE_H
> +
> +#include <stdio.h>
> +
> +#include "libiberty.h" /* xmalloc */
> +#include "gdb_assert.h"
> +
> +/* Define a new queue implementation. */
> +
> +#define QUEUE(TYPE) struct queue_ ## TYPE
> +#define QUEUE_ELEM(TYPE) struct queue_ele_ ## TYPE
queue_elem_ ## TYPE
> +/* Return true if queue Q is empty. */ \
> + \
> +int \
> +queue_ ## TYPE ## _is_empty (QUEUE (TYPE) *q) \
> +{ \
> + gdb_assert (q != NULL); \
> + return q->head == NULL; \
> +} \
> + \
> +void \
> +queue_ ## TYPE ## _remove_ele (QUEUE (TYPE) *q, \
_remove_elem
Plus this function needs a comment.
> + QUEUE_ELEM (TYPE) *p, \
> + QUEUE_ELEM (TYPE) *prev) \
> +{ \
> + if (p == q->head || p == q->tail) \
> + { \
> + if (p == q->head) \
> + q->head = p->next; \
> + if (p == q->tail) \
> + q->tail = prev; \
> + } \
> + else \
> + prev->next = p->next; \
> + \
> + xfree (p); \
> +} \
> + \
> +/* Iterate over elements in the queue Q. If function MATCH returns \
> + true, call function OPERATE_ON_MATCH. If function OPERATE_ON_MATCH \
> + returns true, return with true directly, otherwise, continue to \
> + traverse elements in queue. If none of elements matches, return \
> + false. */ \
> + \
> +int \
> +queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + int (*operate_on_match) (QUEUE (TYPE) *, \
> + QUEUE_ELEM (TYPE) *, \
> + QUEUE_ELEM (TYPE) **), \
> + void *data) \
The iterator I had in mind wouldn't pass v, leaving it for the function
that is passed in to record the element found (either in *data directly,
or as part of the struct that data points to).
Also, I had envisioned just passing in one function, say "operate".
Thus:
int
queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q,
int (*operate) (QUEUE (TYPE) *,
QUEUE_ITER (TYPE) *,
QUEUE_ELEM (TYPE) *,
void *),
void *data)
operate would return 0 to terminate the iteration
and 1 to continue the iteration
(akin to hashtab.h:htab_trav - Consistency Is Good!).
QUEUE_ITER abstracts away the implementation details,
and is passed to _remove_elem.
I wasn't thinking of including _find, _remove, _remove_matching
in the API if we have an iterator - let the user write one if
desired for his/her particular type.
I was expecting users to write "operate" and then just call the
_iterate.
If you want _find,_remove,_remove_matching in the API,
it's not that big a deal. You *could* leave _iterate for later then.
I just want to make sure you've thought about it.
> +{ \
> + int matches = 0; \
> + \
> + QUEUE_ELEM (TYPE) *p; \
> + QUEUE_ELEM (TYPE) *prev = NULL, *next = NULL; \
> + \
> + gdb_assert (q != NULL); \
> + \
> + for (p = q->head; p != NULL; p = next) \
> + { \
> + next = p->next; \
> + if (match (p->data, data)) \
> + { \
> + matches = 1; \
> + if (v != NULL) \
> + *v = p->data; \
> + \
> + if (operate_on_match (q, p, &prev)) \
> + return 1; \
> + } \
> + else \
> + prev = p; \
> + } \
> + return matches; \
> +} \
> + \
> +static int \
> +queue_ ## TYPE ##_on_match_once (QUEUE (TYPE) *q, QUEUE_ELEM (TYPE) *p, \
> + QUEUE_ELEM (TYPE) **prev) \
> +{ \
> + return 1; \
> +} \
> + \
> +/* Find the first element in queue Q for which function MATCH returns \
> + true. Return true if found, and store the found element in V. \
> + Otherwise return false.. */ \
> + \
> +int \
> +queue_ ## TYPE ## _find (QUEUE (TYPE) *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + void *data) \
> +{ \
> + return queue_ ## TYPE ## _iterate (q, v, match, \
> + queue_ ## TYPE ##_on_match_once, data); \
> +} \
> + \
> +/* 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; \
> +} \
blank line here
> +/* Free memory for queue Q. */ \
> + \
> +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. */
> +#define DECLARE_QUEUE_P(TYPE) \
> +QUEUE (TYPE); \
> +QUEUE_ELEM (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 int \
> + queue_ ## TYPE ## _find (QUEUE (TYPE) *, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + void *data); \
> +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); \
> +extern int \
> + queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + int (*operate_on_match) (QUEUE (TYPE) *, \
> + QUEUE_ELEM (TYPE) *, \
> + QUEUE_ELEM (TYPE) **), \
> + void *data); \
> +extern void queue_ ## TYPE ## _remove_ele (QUEUE (TYPE) *q, \
> + QUEUE_ELEM (TYPE) *p, \
> + QUEUE_ELEM (TYPE) *prev); \
> +
> +#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_find(TYPE, QUEUE, V, MATCH, DATA) \
> + queue_ ## TYPE ## _find ((QUEUE), (V), (MATCH), (DATA))
> +#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, V, MATCH, OP_ON_MATCH, DATA) \
> + queue_ ## TYPE ## _iterate ((QUEUE), (V), (MATCH), (OP_ON_MATCH), (DATA))
> +#define QUEUE_remove_ele(TYPE, QUEUE, P, PREV) \
> + queue_ ## TYPE ## _remove_ele ((QUEUE), (P), (PREV))
> +
> +#endif /* QUEUE_H */
> --