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: Yao Qi <yao at codesourcery dot com>
- To: <dje at google dot com>
- Cc: <gdb-patches at sourceware dot org>
- Date: Fri, 7 Sep 2012 10:46:18 +0800
- 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>
On 09/05/2012 05:02 AM, dje@google.com wrote:
> 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.
>
I am using QUEUE_ELEM in this new version.
> 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).
>
OK, let us use 'DEFINE_QUEUE_P' and '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 *?
>
Sure. Fixed.
> > + \
> > +/* 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.
OK, done.
> > + \
> > +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.
Removed.
>
> > +} \
> > + \
> > +/* 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.
OK.
>
> > + \
> > + if (q == NULL) \
> > + return; \
>
> assert q != NULL.
>
I replaced all null pointer checking with assert.
> > + \
> > +/* 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" ?
>
OK.
> > + \
> > +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.
Fixed.
> > + \
> > +/* 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.
Never mind :)
> _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 tried to write an iterator, and build _remove_matching, _remove and _find
on top of it. However, it doesn't allow finding multiple matching results.
>
> 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.
/* 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 driectly, 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) \
{ \
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; \
} \
You can see the implementation of _find on top of it in this patch.
We can implement '_remove_matching' like this,
static int
always_remove_ele_on_match (QUEUE (notif_reply_p) *q,
QUEUE_ELEM (notif_reply_p) *p,
QUEUE_ELEM (notif_reply_p) ** prev)
{
if (q->free_func != NULL)
q->free_func (p->data);
QUEUE_remove_ele (notif_reply_p, q, p, *prev);
return 0;
}
QUEUE_iterate (notif_reply_p, notif->queue, NULL, notif_reply_match_pid,
always_remove_ele_on_match, &pid);
We can implement '_remove' like this:
static int
remote_notif_remove_once_on_match (QUEUE (notif_reply_p) *q,
QUEUE_ELEM (notif_reply_p) *p,
QUEUE_ELEM (notif_reply_p) **prev)
{
QUEUE_remove_ele (notif_reply_p, q, p, *prev);
return 1;
}
QUEUE_iterate (notif_reply_p, np->ack_queue, &reply, match,
remote_notif_remove_once_on_match, data);
> > + \
> > +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.
OK, fixed.
> > + \
> > + for (p = q->head; p != NULL; p = p->next) \
> > + len++; \
> > + return len; \
> > +} \
>
> blank line needed here
Done.
>
> > +/* 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.
>
Add xfree here.
> > +} \
> > +
> > +/* External declarations for these functions. */
> > +#define DECLARE_QUEUE_TYPE(TYPE) \
>
> DECLARE_QUEUE_P
>
Fixed.
--
Yao
gdb/
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
+
+#define DEFINE_QUEUE_P(TYPE) \
+QUEUE_ELEM (TYPE) \
+{ \
+ QUEUE_ELEM (TYPE) *next; \
+ \
+ TYPE data; \
+}; \
+ \
+QUEUE(TYPE) \
+{ \
+ QUEUE_ELEM (TYPE) *head; \
+ QUEUE_ELEM (TYPE) *tail; \
+ void (*free_func) (TYPE); \
+}; \
+ \
+/* 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. Assert \
+ fail if Q is NULL or Q is 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. */ \
+ \
+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; \
+} \
+ \
+void \
+queue_ ## TYPE ## _remove_ele (QUEUE (TYPE) *q, \
+ 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) \
+{ \
+ 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; \
+} \
+/* 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 */
--