From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 11689 invoked by alias); 13 Sep 2012 15:55:12 -0000 Received: (qmail 11653 invoked by uid 22791); 13 Sep 2012 15:55:07 -0000 X-SWARE-Spam-Status: No, hits=-5.2 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-qc0-f201.google.com (HELO mail-qc0-f201.google.com) (209.85.216.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 13 Sep 2012 15:54:49 +0000 Received: by qcha6 with SMTP id a6so306939qch.0 for ; Thu, 13 Sep 2012 08:54:48 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:content-type:content-transfer-encoding:message-id:date :to:cc:subject:in-reply-to:references:x-mailer:from :x-gm-message-state; bh=4URu1ozRU4JseMLlsFS72xj7odVKahgyLH9L+++DtBk=; b=omdABAAR0GWr07jsMY9123pgKjbeTnxIysjoG1NmAlIq7uv0ZVoYJMzUdRJhK+lG3i /ZPnvwQ1fUrJT05yjFG2y65Bw38MAyQ4Ch6H+o5/UwFTxXGe05sfGI/ZbTW+v9w/AIhv PC1xFk5H97TNhPSWTmnmlXqAtwixDePMjR42rd01IUCdJMfrOuy+I4uyQ2wUKy45mwEi Ss7YRUzAyFCW/yNNHHFeBWtHwbkM1ADXQwstqbIC+d6mHt59PhBFHz8ek+7bbl8BbwsC KVVR8M+zUFvL8oz8VpRN1Rxix1epuUfgRIPyjdtRovJLkrYKgGIWhgK3eVFX9F2bVf5X 9+sA== Received: by 10.236.75.138 with SMTP id z10mr1604252yhd.14.1347551687968; Thu, 13 Sep 2012 08:54:47 -0700 (PDT) Received: by 10.236.75.138 with SMTP id z10mr1604246yhd.14.1347551687905; Thu, 13 Sep 2012 08:54:47 -0700 (PDT) Received: from wpzn4.hot.corp.google.com (216-239-44-65.google.com [216.239.44.65]) by gmr-mx.google.com with ESMTPS id o6si6278595yhn.7.2012.09.13.08.54.47 (version=TLSv1/SSLv3 cipher=AES128-SHA); Thu, 13 Sep 2012 08:54:47 -0700 (PDT) Received: from ruffy2.mtv.corp.google.com (ruffy2.mtv.corp.google.com [172.18.110.129]) by wpzn4.hot.corp.google.com (Postfix) with ESMTP id 60D181E0043; Thu, 13 Sep 2012 08:54:47 -0700 (PDT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <20562.454.680299.970360@ruffy2.mtv.corp.google.com> Date: Thu, 13 Sep 2012 15:55:00 -0000 To: Yao Qi Cc: Subject: Re: [PATCH 1/4] new gdb_queue.h in common/. In-Reply-To: <50509AD9.7010408@codesourcery.com> 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> <50495FFA.5080107@codesourcery.com> <20558.20947.170261.875294@ruffy2.mtv.corp.google.com> <50509AD9.7010408@codesourcery.com> From: dje@google.com X-Gm-Message-State: ALoCoQnMlB2tbKqMvqr7iGRbSv9c26j1OAwuLFcI1Ip1m+2KXVq5zrflUq/K09/M23uf2YLpQvPKZ/7/fqHTJDEnC/iSnnOOtbKgv2TREXXbL0MVLE0nZriNzcxAhyd0I5lCVYHVUVUBFu4aX4KiM7znBghEjckJFPhRA8QsXuk/TrKPCDXBP0AyCFQVjT2p5sWEXagmq4XYE950hkXlKm+eiZNurCbb2A== 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/msg00247.txt.bz2 Yao Qi writes: > On 09/11/2012 04:47 AM, dje@google.com wrote: > > The iterator I had in mind wouldn't pass v, leaving it for the function > > that is passed in to record the element found (either in *data directly, > > or as part of the struct that data points to). > > Also, I had envisioned just passing in one function, say "operate". > > > > Thus: > > > > int > > queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, > > int (*operate) (QUEUE (TYPE) *, > > QUEUE_ITER (TYPE) *, > > QUEUE_ELEM (TYPE) *, > > void *), > > void *data) > > > > Doug, > I almost followed this design in the new patch, except moving parameter > 3 (QUEUE_ELEM (TYPE) *) of '*operate' into QUEUE_ITER (TYPE), so that we > can save one parameter, and don't have to expose details of QUEUE_ELEM. Oops, I didn't intend to expose the details of QUEUE_ELEM. Pretend I wrote TYPE instead. :-) [The intent being to provide operate with the element, but not expose the details of QUEUE_ITER.] > > operate would return 0 to terminate the iteration > > and 1 to continue the iteration > > (akin to hashtab.h:htab_trav - Consistency Is Good!). > > > > QUEUE_ITER abstracts away the implementation details, > > and is passed to _remove_elem. > > > > I wasn't thinking of including _find, _remove, _remove_matching > > in the API if we have an iterator - let the user write one if > > desired for his/her particular type. > > I was expecting users to write "operate" and then just call the > > _iterate. > > Agreed. > > > > > If you want _find,_remove,_remove_matching in the API, > > it's not that big a deal. You*could* leave _iterate for later then. > > I just want to make sure you've thought about it. > > I really like the iterator, and I'd like to try again to implement > _iterate here. :) The queue is tested with the rest of patches ('general > async notification'), and no regressions. > > -- > Yao > > gdb/ > > 2012-09-12 Yao Qi > Doug Evans > > * common/queue.h: New. > --- > gdb/common/queue.h | 267 ++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 files changed, 267 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..47157a3 > --- /dev/null > +++ b/gdb/common/queue.h > @@ -0,0 +1,267 @@ > +/* 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_P(TYPE)' is to define the new queue type for 'TYPE', and > + macro 'DECLARE_QUEUE_P' 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_elem_ ## TYPE > +#define QUEUE_ITER(TYPE) struct queue_iter_ ## TYPE > + > +#define DEFINE_QUEUE_P(TYPE) \ > +QUEUE_ELEM (TYPE) \ > +{ \ > + QUEUE_ELEM (TYPE) *next; \ > + \ > + TYPE data; \ > +}; \ > + \ > +/* Queue iterator. */ \ > +QUEUE_ITER (TYPE) \ > +{ \ > + /* The current element during traverse. */ \ > + QUEUE_ELEM (TYPE) *p; \ > + /* The previous element of P. */ \ > + QUEUE_ELEM (TYPE) *prev; \ > +}; \ > + \ > +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; \ > +} \ > + \ > +/* Remove the element per the state of iterator ITER from queue Q. */ \ > + \ > +void \ > +queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \ > + QUEUE_ITER (TYPE) *iter) \ > +{ \ gdb_assert (q != NULL); gdb_assert (iter != NULL && iter->p != NULL); > + if (iter->p == q->head || iter->p == q->tail) \ > + { \ > + if (iter->p == q->head) \ > + q->head = iter->p->next; \ > + if (iter->p == q->tail) \ > + q->tail = iter->prev; \ > + } \ > + else \ > + iter->prev->next = iter->p->next; \ > + \ Need to check if q->free_func != NULL and call it on p->data. > + xfree (iter->p); \ > +} \ > + \ > +/* Iterate over elements in the queue Q and call function OPERATE on \ > + each element. OPERATE would return false to terminate the \ > + iteration and true to continue the iteration. Return false if \ > + iteration is terminated by function OPERATE, otherwise return \ > + true. */ \ > + \ > +int \ > +queue_ ## TYPE ## _iterate (QUEUE (TYPE) *q, \ > + int (*operate) (QUEUE (TYPE) *, \ > + QUEUE_ITER (TYPE) *, \ > + TYPE, \ > + void *), \ IWBN to have a typedef of operate. typedef int queue_ ## TYPE ## _operate_func (QUEUE (TYPE) *, QUEUE_ITER (TYPE) *, TYPE, void *); or some such. > + void *data) \ > +{ \ > + QUEUE_ELEM (TYPE) *next = NULL; \ > + QUEUE_ITER (TYPE) iter = { NULL, NULL }; \ > + \ > + gdb_assert (q != NULL); \ > + \ > + for (iter.p = q->head; iter.p != NULL; iter.p = next) \ Need to update iter.prev somewhere here (and handle the case that iter.p has been deleted). > + { \ > + next = iter.p->next; \ > + if (!operate (q, &iter, iter.p->data, data)) \ > + return 0; \ > + } \ > + return 1; \ > +} \ > + \ > +/* 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); \ > +QUEUE_ITER (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 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, \ > + int (*operate) (QUEUE (TYPE) *, \ > + QUEUE_ITER (TYPE) *, \ > + TYPE, \ > + void *), \ > + void *); \ > +extern void \ > + queue_ ## TYPE ## _remove_elem (QUEUE (TYPE) *q, \ > + QUEUE_ITER (TYPE) *iter); \ > + > +#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_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, OPERATE, PARAM) \ > + queue_ ## TYPE ## _iterate ((QUEUE), (OPERATE), (PARAM)) > +#define QUEUE_remove_elem(TYPE, QUEUE, ITER) \ > + queue_ ## TYPE ## _remove_elem ((QUEUE), (ITER)) > + > +#endif /* QUEUE_H */ > -- > 1.7.7.6 I'm happy with the above nits fixed. Thanks!