From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15809 invoked by alias); 10 Sep 2012 20:47:37 -0000 Received: (qmail 15798 invoked by uid 22791); 10 Sep 2012 20:47:36 -0000 X-SWARE-Spam-Status: No, hits=-5.1 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-qa0-f73.google.com (HELO mail-qa0-f73.google.com) (209.85.216.73) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 10 Sep 2012 20:47:17 +0000 Received: by qats34 with SMTP id s34so221754qat.0 for ; Mon, 10 Sep 2012 13:47:16 -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=2fLj4oserfTYUQH6cbpZDX+3FLBOd0FxIO/rKMR1JeQ=; b=MlSb233dptXtQrDEhGiZjM1JpJr03fmZ/l0gE5HjkHyigxvXlAD5s+WBX3XZDkVyDq ae+SHlAJUlkU9gJMj6DjVJjAUdt8gZm8pJLDEHYKC8l3/RTlbgx8njGAA9D2KUW/pQ+F K8nStLQABOOUGoofZ3PrxybzNarVycDKxLxKJ/66Ctap/tquGTkF2n053YSKNpPZJ93f JAvyePIOfKYRsMxwVKh8jLetTdqxMJiRUe9eAE2kjIkKhp3c72NulDm23awsHQBnuwWb PYImeInjQDXRw4dAFKzMsnAmgTFNP3F3GEQynWrYp0KCqpvBS5r1OW81QA/9nAim/ERz mc0Q== Received: by 10.236.83.39 with SMTP id p27mr8992312yhe.27.1347310036303; Mon, 10 Sep 2012 13:47:16 -0700 (PDT) Received: by 10.236.83.39 with SMTP id p27mr8992307yhe.27.1347310036255; Mon, 10 Sep 2012 13:47:16 -0700 (PDT) Received: from wpzn3.hot.corp.google.com (216-239-44-65.google.com [216.239.44.65]) by gmr-mx.google.com with ESMTPS id o6si4098484yhn.7.2012.09.10.13.47.16 (version=TLSv1/SSLv3 cipher=AES128-SHA); Mon, 10 Sep 2012 13:47:16 -0700 (PDT) Received: from ruffy2.mtv.corp.google.com (ruffy2.mtv.corp.google.com [172.18.110.129]) by wpzn3.hot.corp.google.com (Postfix) with ESMTP id C09A7100047; Mon, 10 Sep 2012 13:47:15 -0700 (PDT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <20558.20947.170261.875294@ruffy2.mtv.corp.google.com> Date: Mon, 10 Sep 2012 20:47:00 -0000 To: Yao Qi Cc: Subject: Re: [PATCH 1/4] new gdb_queue.h in common/. In-Reply-To: <50495FFA.5080107@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> From: dje@google.com X-Gm-Message-State: ALoCoQkhgOsnMlCfwV7IEL36mvCxFCUhL4MPqm2XtOk8JX15LdJo3aXwvrn7tK9H4beKgqpA1urLlefxv7BZkkZSiLmAGvPudqA1/ynwmcghdGNkvqrTLTEd8x1lxzA9QZnsRHa8gmqTOOMjG9MsZu3JAmHEsQ1oOo5r4OwyKGggdE+6KvqFyslo5cEZpc4tZaBIZVkoGExg5oeMMYT6eDgh1nike5w8hQ== 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/msg00142.txt.bz2 Yao Qi writes: > On 09/05/2012 05:02 AM, dje@google.com wrote: > > [...] > > 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. They're ok for me to read. It might be more a matter of frequency of use. > 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 queue_elem_ ## TYPE > +/* 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, \ _remove_elem Plus this function needs a comment. > + 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) \ 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) 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. 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. > +{ \ > + 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; \ > +} \ blank line here > +/* 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 */ > --