From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29207 invoked by alias); 7 Sep 2012 02:47:31 -0000 Received: (qmail 29195 invoked by uid 22791); 7 Sep 2012 02:47:28 -0000 X-SWARE-Spam-Status: No, hits=-4.4 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,KHOP_THREADED,RCVD_IN_HOSTKARMA_W,RCVD_IN_HOSTKARMA_WL X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 07 Sep 2012 02:47:13 +0000 Received: from svr-orw-exc-10.mgc.mentorg.com ([147.34.98.58]) by relay1.mentorg.com with esmtp id 1T9ob9-00068r-19 from Yao_Qi@mentor.com ; Thu, 06 Sep 2012 19:47:11 -0700 Received: from SVR-ORW-FEM-05.mgc.mentorg.com ([147.34.97.43]) by SVR-ORW-EXC-10.mgc.mentorg.com with Microsoft SMTPSVC(6.0.3790.4675); Thu, 6 Sep 2012 19:47:10 -0700 Received: from qiyao.dyndns.org (147.34.91.1) by svr-orw-fem-05.mgc.mentorg.com (147.34.97.43) with Microsoft SMTP Server id 14.1.289.1; Thu, 6 Sep 2012 19:47:09 -0700 Message-ID: <50495FFA.5080107@codesourcery.com> Date: Fri, 07 Sep 2012 02:47:00 -0000 From: Yao Qi User-Agent: Mozilla/5.0 (X11; Linux i686; rv:14.0) Gecko/20120717 Thunderbird/14.0 MIME-Version: 1.0 To: CC: 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> In-Reply-To: <20550.27760.260327.470212@ruffy2.mtv.corp.google.com> Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2012-09/txt/msg00054.txt.bz2 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 * 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 . */ + +/* 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 + +#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 */ --