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: Tue, 4 Sep 2012 14:02:40 -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>
Yao Qi writes:
> On 08/25/2012 02:43 AM, dje@google.com wrote:
> [...]
> > Why call both ele_TYPE_xfree and xfree?
> > Maybe the API should include the ability to specify an element destructor, passed as an argument to the queue constructor, akin to the htab API (ref: libiberty/hashtab.c). And perhaps also a copy-constructor for the object version of the API (to copy structs as values in the case where a simple memcpy is insufficient).
> >
>
> In V2, I add a function pointer 'free_func' in 'struct queue_ ##type',
> as you suggested. A copy-constructor can be postponed until we need it.
Yeah, OTOH this is how "extended" versions of API functions come into being.
They're a wart in the API so I like to avoid them.
E.g. consider htab_create_alloc vs htab_create_alloc_ex in the hashtab API.
Some might not think this is a wart, alas I do, so this is one situation
where I don't like to lazily add stuff (when I'm aware of it at
the time ... :-)).
OTOOH, since we're lazily adding the object version of the API anyway,
I don't feel too strongly about it here.
> The V2 of this patch obsoletes the rest of patches in this series.
> Once it is OK, I'll post updated patch 2/4 and 3/4.
Thanks btw!
Note that part of the support for pointers, ints, and objects in vec.h
involves naming. That's missing here.
So while we don't need to implement the _I (integral) and _O (object)
versions of this, we still need the _P (pointer) naming (IMO).
[Also, we don't have to implement deques and stacks here.
I just wanted thought put into what it might look like, and see if that
would influence the design here. I think(!) the API won't change,
so I'm happy to leave it at that for now.]
> 2012-08-29 Yao Qi <yao@codesourcery.com>
>
> * common/queue.h: New.
> ---
> gdb/common/queue.h | 312 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 files changed, 312 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..14e260c
> --- /dev/null
> +++ b/gdb/common/queue.h
> @@ -0,0 +1,312 @@
> +/* 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
There should also be a similar macro for queue_ele_. QUEUE_ELE?
[I like ELM instead of ELE, but I don't feel strongly enough. :-)]
And both should be used *throughout* the implementation here.
vec.h also has VEC_OP but I'm not sure it's useful enough yet here
(vec.h API functions can call other API functions so it's more useful there).
> +
> +#define DEFINE_QUEUE_TYPE(TYPE) \
Maybe this should be DEF_QUEUE_P (_P for the pointer version,
akin to DEF_VEC_P), but IIRC vec.h doesn't have a "DECLARE_FOO" macro,
which this has. So I'm happy with DEFINE_QUEUE_P (better matches
DECLARE_QUEUE_P).
> +struct queue_ele_ ## TYPE \
> +{ \
> + struct queue_ele_ ## TYPE *next; \
> + \
> + TYPE data; \
> +}; \
> + \
> +struct queue_ ## TYPE \
> +{ \
> + struct queue_ele_ ## TYPE *head; \
> + struct queue_ele_ ## TYPE *tail; \
> + void (*free_func) (void *); \
Can free_func be passed TYPE instead of void *?
> +}; \
> + \
> +/* Typical enqueue operation. Put V into queue Q. */ \
> + \
> +void \
> +queue_ ## TYPE ## _enque (struct queue_ ## TYPE *q, TYPE v) \
> +{ \
> + struct queue_ele_ ## TYPE *p \
> + = xmalloc (sizeof (struct queue_ele_ ## 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. Assert \
> + fail if Q is NULL or Q is empty. */ \
> + \
> +TYPE \
> +queue_ ## TYPE ## _deque (struct queue_ ## TYPE *q) \
> +{ \
> + struct queue_ele_ ## TYPE *p = NULL; \
> + TYPE v; \
> + \
> + gdb_assert (q != NULL); \
> + p = q->head; \
> + \
> + if (q->head == q->tail) \
> + { \
> + q->head = NULL; \
> + q->tail = NULL; \
> + } \
> + else \
> + q->head = q->head->next; \
> + \
> + gdb_assert (p != NULL); \
It'd be better to move this assert above to right after assigning to p.
> + 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. */ \
> + \
> +TYPE \
> +queue_ ## TYPE ## _peek (struct 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 (struct queue_ ## TYPE *q) \
> +{ \
> + gdb_assert (q != NULL); \
> + return (q->head == NULL); \
No need to put q->head == NULL in parens.
> +} \
> + \
> +/* Iterate over elements in the queue Q, and remove all of them for \
> + which function MATCH returns true. */ \
> + \
> +void \
> +queue_ ## TYPE ## _remove_matching (struct queue_ ## TYPE *q, \
> + int (*match) (TYPE, void *), \
> + void *data) \
> +{ \
> + struct queue_ele_ ## TYPE *p = NULL; \
> + struct queue_ele_ ## TYPE *prev = NULL, *next = NULL; \
I'd remove the initialization of p = NULL.
> + \
> + if (q == NULL) \
> + return; \
assert q != NULL.
> + \
> + for (p = q->head; p != NULL; p = next) \
> + { \
> + next = p->next; \
> + if (match (p->data, data)) \
> + { \
> + 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; \
> + \
> + if (q->free_func != NULL) \
> + q->free_func (p->data); \
> + xfree (p); \
> + } \
> + else \
> + prev = p; \
> + } \
> +} \
> + \
> +/* Iterate over queue Q and remove the first element for which \
> + function MATCH returns true. Return true if element is removed, \
> + and set data to V. Otherwise return false. */ \
"and set data to V" is a bit confusing (since "data" is also a parameter).
How about "and store the queue element in V" ?
> + \
> +int \
> +queue_ ## TYPE ## _remove (struct queue_ ## TYPE *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + void *data) \
> +{ \
> + struct queue_ele_ ## TYPE *p = NULL; \
Remove assignment of p = NULL.
> + struct queue_ele_ ## TYPE *prev = NULL; \
> + \
> + if (q == NULL) \
> + return 0; \
assert q != NULL.
> + \
> + for (p = q->head; p != NULL; p = p->next) \
> + { \
> + if (match (p->data, data)) \
> + { \
> + 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; \
> + \
> + *v = p->data; \
> + xfree (p); \
> + return 1; \
> + } \
> + else \
> + prev = p; \
> + } \
> + return 0; \
> +} \
> + \
> +/* Find the first element in queue Q for which function MATCH returns \
> + true. Return true if found, and set found element to V. Otherwise \
> + return false.. */ \
Apologies for not bringing this up earlier.
_remove_matching, _remove, and _find are quite similar, makes me think
an iterator could replace them.
If the iterator "traverse" function returned a boolean of whether to continue
or not, and there was a new API function that deleted a queue element given
an iterator, both the above _remove_matching and _remove functions could be
subsumed by them, and the result would be more useful.
To implement the _find function, the caller could store the found entry in
space allocated for it in the data parameter.
This would also allow finding multiple matching entries.
I like thinner APIs than fatter ones, but in this case I'm not sure
this is better (or worth it).
Thoughts?
> + \
> +int \
> +queue_ ## TYPE ## _find (struct queue_ ## TYPE *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + void *data) \
> +{ \
> + struct queue_ele_ ## TYPE *p = NULL; \
> + \
> + if (q == NULL) \
> + return 0; \
> + \
> + for (p = q->head; p != NULL; p = p->next) \
> + if (match (p->data, data)) \
> + { \
> + *v = p->data; \
> + return 1; \
> + } \
> + return 0; \
> +} \
> + \
> +/* Allocate memory for queue. */ \
> + \
> +struct queue_ ## TYPE * \
> +queue_ ## TYPE ## _alloc (void (*free_func) (void *)) \
> +{ \
> + struct queue_ ## TYPE *p; \
For consistency's sake, use q instead of p here.
> + \
> + p = (struct queue_ ## TYPE *) xmalloc (sizeof (struct queue_ ## TYPE));\
> + p->head = NULL; \
> + p->tail = NULL; \
> + p->free_func = free_func; \
> + return p; \
> +} \
> + \
> +/* Length of queue Q. */ \
> + \
> +int \
> +queue_ ## TYPE ## _length (struct queue_ ## TYPE *q) \
> +{ \
> + struct queue_ele_ ## TYPE *p = NULL; \
> + int len = 0; \
> + \
> + if (q == NULL) \
> + return 0; \
assert q != NULL.
> + \
> + for (p = q->head; p != NULL; p = p->next) \
> + len++; \
> + return len; \
> +} \
blank line needed here
> +/* Free memory for queue Q. */ \
> + \
> +void \
> +queue_ ## TYPE ## _free (struct queue_ ## TYPE *q) \
> +{ \
> + struct queue_ele_ ## TYPE *p, *next; \
> + \
> + if (q == NULL) \
> + return; \
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) before returning.
> +} \
> +
> +/* External declarations for these functions. */
> +#define DECLARE_QUEUE_TYPE(TYPE) \
DECLARE_QUEUE_P
> +struct queue_ ## TYPE; \
> +extern void \
> + queue_ ## TYPE ## _enque (struct queue_ ## TYPE *q, TYPE v); \
> +extern TYPE \
> + queue_ ## TYPE ## _deque (struct queue_ ## TYPE *q); \
> +extern int queue_ ## TYPE ## _is_empty (struct queue_ ## TYPE *q); \
> +extern void \
> + queue_ ## TYPE ## _remove_matching (struct queue_ ## TYPE *q, \
> + int (*match) (TYPE, void *), \
> + void *data); \
> +extern int \
> + queue_ ## TYPE ## _remove (struct queue_ ## TYPE *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + void *data); \
> +extern int \
> + queue_ ## TYPE ## _find (struct queue_ ## TYPE *q, TYPE *v, \
> + int (*match) (TYPE, void *), \
> + void *data); \
> +extern struct queue_ ## TYPE * \
> + queue_ ## TYPE ## _alloc (void (*free_func) (void *)); \
> +extern int queue_ ## TYPE ## _length (struct queue_ ## TYPE *q); \
> +extern TYPE \
> + queue_ ## TYPE ## _peek (struct queue_ ## TYPE *q); \
> +extern void queue_ ## TYPE ## _free (struct queue_ ## TYPE *q); \
> +
> +
In the following, where the macro takes multiple parameters,
put each parameter in parens.
> +#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_remove(TYPE, QUEUE, V, MATCH, DATA) \
> + queue_ ## TYPE ## _remove (QUEUE, V, MATCH, DATA)
> +#define QUEUE_remove_matching(TYPE, QUEUE, MATCH, DATA) \
> + queue_ ## TYPE ## _remove_matching (QUEUE, MATCH, DATA)
> +#define QUEUE_find(TYPE, QUEUE, V, MATCH, DATA) \
> + queue_ ## TYPE ## _find (QUEUE, V, MATCH, DATA)
> +#define QUEUE_alloc(TYPE, FUNC) queue_ ## TYPE ## _alloc (FUNC)
I'd rename FUNC to FREE_FUNC.
> +#define QUEUE_length(TYPE, QUEUE) queue_ ## TYPE ## _length (QUEUE)
> +#define QUEUE_free(TYPE, QUEUE) queue_ ## TYPE ## _free (QUEUE)
> +
> +#endif /* QUEUE_H */
> --
> 1.7.7.6