[PATCH 1/4] new gdb_queue.h in common/.
Yao Qi
yao@codesourcery.com
Wed Aug 29 09:42:00 GMT 2012
On 08/25/2012 02:43 AM, dje@google.com wrote:
> > +
> > +/* Define a new queue implementation. */
> > +
> > +#define QUEUE_DEFINE_TYPE(TYPE) \
>
> DEFINE_QUEUE_TYPE
>
Personally, I prefer operation prefixed with data type, such
as queue_define_type or queue_enque, etc. However, I am OK
with your suggestion.
> 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.
>
OK.
> 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]
Sure, fixed.
>
> > +{ \
> > + 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]
>
In version 1, I focused on Pointer. Considering Object and Int, deque should
return TYPE here, and give an assert fail if something is unexpected.
> > + \
> > +/* 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==]
Add an assertion here.
>
> 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. :-)
>
Oh, right. Get comment fixed.
> > +} \
> > + \
> > +/* 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.
>
Agreed. gdb_assert is added here.
> > +} \
> > + \
> > +/* 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".
>
That sounds good.
> > + 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).
>
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.
> > + 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.
>
Fixed it by returning boolean indicating success and pass a pointer
of TYPE to the value 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]
... likewise here.
>
> > + \
> > +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.
>
destructor is added.
> > + \
> > +/* 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.
>
This macro is removed.
> > +
> > +/* External declarations for these functions. */
> > +#define QUEUE_DECLARE(TYPE) \
>
> DECLARE_QUEUE_TYPE (akin to DEFINE_QUEUE_TYPE).
Fixed.
gdb_queue.h is renamed to queue.h, and all symbols gdb_queue_XXX
are renamed to queue_XXX.
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.
--
Yao
gdb/
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
+
+#define DEFINE_QUEUE_TYPE(TYPE) \
+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 *); \
+}; \
+ \
+/* 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); \
+ 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); \
+} \
+ \
+/* 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; \
+ \
+ 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; \
+ \
+ 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. */ \
+ \
+int \
+queue_ ## TYPE ## _remove (struct queue_ ## TYPE *q, TYPE *v, \
+ int (*match) (TYPE, void *), \
+ void *data) \
+{ \
+ struct queue_ele_ ## TYPE *p = NULL; \
+ struct queue_ele_ ## TYPE *prev = NULL; \
+ \
+ if (q == NULL) \
+ return 0; \
+ \
+ 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.. */ \
+ \
+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; \
+ \
+ 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; \
+ \
+ for (p = q->head; p != NULL; p = p->next) \
+ len++; \
+ return len; \
+} \
+/* Free memory for queue Q. */ \
+ \
+void \
+queue_ ## TYPE ## _free (struct queue_ ## TYPE *q) \
+{ \
+ struct queue_ele_ ## TYPE *p, *next; \
+ \
+ if (q == NULL) \
+ return; \
+ \
+ for (p = q->head; p != NULL; p = next) \
+ { \
+ next = p->next; \
+ if (q->free_func) \
+ q->free_func (p->data); \
+ xfree (p); \
+ } \
+} \
+
+/* External declarations for these functions. */
+#define DECLARE_QUEUE_TYPE(TYPE) \
+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); \
+
+
+#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)
+#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
More information about the Gdb-patches
mailing list