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/.
Yao Qi writes:
> 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-08-24 Yao Qi <yao@codesourcery.com>
>
> * common/gdb_queue.h: New.
> ---
> gdb/common/gdb_queue.h | 283 ++++++++++++++++++++++++++++++++++++++++++++++++
> 1 files changed, 283 insertions(+), 0 deletions(-)
> create mode 100644 gdb/common/gdb_queue.h
>
> diff --git a/gdb/common/gdb_queue.h b/gdb/common/gdb_queue.h
> new file mode 100644
> index 0000000..fa582c1
> --- /dev/null
> +++ b/gdb/common/gdb_queue.h
> @@ -0,0 +1,283 @@
> +/* 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
> + 'QUEUE_DEFINE_TYPE(TYPE)' is to define the new queue type for
> + 'struct TYPE', and macro 'QUEUE_DECLARE' *is to declare these external
> + APIs. When define a queue type for 'struct FOO', an extra helper function
> + 'gdb_queue_ele_FOO_xfree (struct FOO *foo)' has to be defined to release
> + the contents in foo, but not foo itself. */
> +
> +#ifndef GDB_QUEUE_H
> +#define GDB_QUEUE_H
> +
> +#include <stdio.h>
> +
> +#include "libiberty.h" /* xmalloc */
> +#include "gdb_assert.h"
> +
> +/* Define a new queue implementation. */
> +
> +#define QUEUE_DEFINE_TYPE(TYPE) \
DEFINE_QUEUE_TYPE
Plus, seems like we should go all the way and provide I(integer),P(pointer),O(object_) support that vec.h does.
I'm ok with, e.g., just support pointers for now, leaving integers and objects for later.
Also, one can imagine wanting stacks and deques too.
[I only mention it so that we think about it. It would be unfortunate if this proliferated and only later, when it's much harder, do we decide we want some unification.]
> +struct gdb_queue_ele_ ## TYPE \
> +{ \
> + struct gdb_queue_ele_ ## TYPE *next; \
> + \
> + struct TYPE *data; \
> +}; \
> + \
> +struct gdb_queue_ ## TYPE \
> +{ \
> + struct gdb_queue_ele_ ## TYPE *head; \
> + struct gdb_queue_ele_ ## TYPE *tail; \
> +}; \
> + \
> +/* Typical enqueue operation. Put V into queue Q. */ \
> + \
> +void \
> +gdb_queue_ ## TYPE ## _enque (struct TYPE *v, \
> + struct gdb_queue_ ## TYPE *q) \
I think it'd be better to keep the queue argument as the first parameter.
[general rule for every such function]
> +{ \
> + struct gdb_queue_ele_ ## TYPE *p \
> + = xmalloc (sizeof (struct gdb_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. Return NULL \
> + if queue Q is empty. */ \
Returning NULL means one can't queue it as a value.
[mixed feelings on whether that's important enough]
assert fail if queue is empty?
Plus if one went with vec's IPO support, should this return the int-like type?
[in which case deciding whether to return NULL becomes moot]
> + \
> +struct TYPE * \
> +gdb_queue_ ## TYPE ## _deque (struct gdb_queue_ ## TYPE *q) \
> +{ \
> + struct gdb_queue_ele_ ## TYPE *p = NULL; \
> + struct TYPE *v = NULL; \
> + \
> + if (q == NULL) \
> + return NULL; \
> + p = q->head; \
> + \
> + if (q->head == q->tail) \
> + { \
> + q->head = NULL; \
> + q->tail = NULL; \
> + } \
> + else \
> + q->head = q->head->next; \
> + \
> + if (p != NULL) \
> + v = p->data; \
> + \
> + xfree (p); \
> + return v; \
> +} \
> + \
> +/* Return the element on tail, but don't remove it from queue. Return \
> + NULL if queue is empty. */ \
> + \
> +struct TYPE * \
> +gdb_queue_ ## TYPE ## _peek (struct gdb_queue_ ## TYPE *q) \
> +{ \
> + if (q== NULL || q->head == NULL) \
> + return NULL; \
assert fail if q == NULL?
[missing space in q==]
I wouldn't use "peek" to name a function that returns the tail.
"peek" should return the head.
> + return q->head->data; \
Oh, heh, the function comment is wrong, it returns head. :-)
> +} \
> + \
> +/* Return true if queue Q is empty. */ \
> + \
> +int \
> +gdb_queue_ ## TYPE ## _is_empty (struct gdb_queue_ ## TYPE *q) \
> +{ \
> + return (q == NULL || q->head == NULL); \
assert q != NULL ?
The vec functions handle vec == NULL because it's actually a pointer to the vector (so it can be resized which involves an xrealloc).
We don't need that here, so I'm thinking it'd be better to not be lax, and require q != NULL.
> +} \
> + \
> +/* Iterate over elements in the queue Q, and remove all of them for \
> + which function MATCH returns true. */ \
> + \
> +void \
> +gdb_queue_ ## TYPE ## _remove_all (struct gdb_queue_ ## TYPE *q, \
> + int (*match) (struct TYPE *, void *), \
> + void *data) \
> +{ \
The "all" in "remove_all" is confusing (I'd expected it to empty the queue completely).
How about "remove_matching".
> + struct gdb_queue_ele_ ## TYPE *p = NULL; \
> + struct gdb_queue_ele_ ## TYPE *prev = NULL, *next = NULL; \
> + \
> + if (q == NULL) \
> + return; \
> + \
> + 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; \
> + \
> + gdb_queue_ele_ ## TYPE ## _xfree (p->data); \
> + xfree (p->data); \
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).
> + xfree (p); \
> + } \
> + else \
> + prev = p; \
> + } \
> +} \
> + \
> +/* Iterate over queue Q and remove one element for which function \
> + MATCH returns true. */ \
I'd rather this be clearer and specify that the *first* matching element is returned.
Here things get muddy as it's normal to return NULL if the value wasn't found, but that conflicts with the discussion above. I'm not sure what to do except return a bool indicating success, and pass in a pointer to the value to be returned.
> + \
> +struct TYPE * \
> +gdb_queue_ ## TYPE ## _remove (struct gdb_queue_ ## TYPE *q, \
> + int (*match) (struct TYPE *, void *), \
> + void *data) \
> +{ \
> + struct gdb_queue_ele_ ## TYPE *p = NULL; \
> + struct gdb_queue_ele_ ## TYPE *prev = NULL; \
> + struct TYPE *t = NULL; \
> + \
> + if (q == NULL) \
> + return 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; \
> + \
> + t = p->data; \
> + xfree (p); \
> + return t; \
> + } \
> + else \
> + prev = p; \
> + } \
> + return NULL; \
> +} \
> + \
> +/* Find an element in queue Q for which function MATCH returns true. \
> + Return NULL if not found. */ \
"Find the first element in queue ..."
Return bool, and pass in a pointer into which to store the found value?
[these notes are just for discussion btw]
> + \
> +struct TYPE * \
> +gdb_queue_ ## TYPE ## _find (struct gdb_queue_ ## TYPE *q, \
> + int (*match) (struct TYPE *, void *), \
> + void *data) \
> +{ \
> + struct gdb_queue_ele_ ## TYPE *p = NULL; \
> + \
> + if (q == NULL) \
> + return NULL; \
> + \
> + for (p = q->head; p != NULL; p = p->next) \
> + { \
> + if (match (p->data, data)) \
> + return p->data; \
> + } \
> + return NULL; \
> +} \
> + \
> +/* Allocate memory for queue. */ \
> + \
> +struct gdb_queue_ ## TYPE * \
> +gdb_queue_ ## TYPE ## _alloc (void) \
> +{ \
> + struct gdb_queue_ ## TYPE *p; \
> + \
> + p = (struct gdb_queue_ ## TYPE *) xmalloc (sizeof (struct gdb_queue_ ## TYPE));\
> + p->head = NULL; \
> + p->tail = NULL; \
> + return p; \
> +} \
The queue destructor is missing.
> + \
> +/* Length of queue Q. */ \
> + \
> +int \
> +gdb_queue_ ## TYPE ## _length (struct gdb_queue_ ## TYPE *q) \
> +{ \
> + struct gdb_queue_ele_ ## TYPE *p = NULL; \
> + int len = 0; \
> + \
> + if (q == NULL) \
> + return 0; \
> + \
> + for (p = q->head; p != NULL; p = p->next) \
> + len++; \
> + return len; \
> +} \
> +
> +
> +/* Define a variable of type gdb_queue_ ## TYPE. */
> +
> +#define QUEUE_DEFINE_VAR(TYPE, VAR) \
> + struct gdb_queue_ ## TYPE VAR = { NULL, NULL }
DEFINE_QUEUE_VAR
OTOH, I think I would delete this, and require the user to use gdb_queue_##TYPE##_alloc.
> +
> +/* External declarations for these functions. */
> +#define QUEUE_DECLARE(TYPE) \
DECLARE_QUEUE_TYPE (akin to DEFINE_QUEUE_TYPE).
> +struct gdb_queue_ ## TYPE; \
> +extern void gdb_queue_ ## TYPE ## _enque (struct TYPE *v, \
> + struct gdb_queue_ ## TYPE *q); \
> +extern struct TYPE * \
> + gdb_queue_ ## TYPE ## _deque (struct gdb_queue_ ## TYPE *q); \
> +extern int \
> + gdb_queue_ ## TYPE ## _is_empty (struct gdb_queue_ ## TYPE *q); \
> +extern void \
> + gdb_queue_ ## TYPE ## _remove_all (struct gdb_queue_ ## TYPE *q, \
> + int (*match) (struct TYPE *, void *), \
> + void *data); \
> +extern struct TYPE * \
> + gdb_queue_ ## TYPE ## _remove (struct gdb_queue_ ## TYPE *q, \
> + int (*match) (struct TYPE *, void *), \
> + void *data); \
> +extern struct TYPE * \
> + gdb_queue_ ## TYPE ## _find (struct gdb_queue_ ## TYPE *q, \
> + int (*match) (struct TYPE *, void *), \
> + void *data); \
> +extern struct gdb_queue_ ## TYPE * \
> + gdb_queue_ ## TYPE ## _alloc (void); \
> +extern void gdb_queue_ele_ ## TYPE ## _xfree (struct TYPE *); \
> +extern int gdb_queue_ ## TYPE ## _length (struct gdb_queue_ ## TYPE *q);\
> +extern struct TYPE * \
> + gdb_queue_ ## TYPE ## _peek (struct gdb_queue_ ## TYPE *q); \
> +
> +#endif /* GDB_QUEUE_H */
> --
> 1.7.7.6
>