From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12776 invoked by alias); 4 Sep 2012 21:03:00 -0000 Received: (qmail 12670 invoked by uid 22791); 4 Sep 2012 21:02:57 -0000 X-SWARE-Spam-Status: No, hits=-5.0 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,TW_CP X-Spam-Check-By: sourceware.org Received: from mail-yx0-f201.google.com (HELO mail-yx0-f201.google.com) (209.85.213.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 04 Sep 2012 21:02:42 +0000 Received: by yenr11 with SMTP id r11so726072yen.0 for ; Tue, 04 Sep 2012 14:02:41 -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=PhdJnPW+rJvD0tiSarjUcCEQymjLctAX/ytskbZQTak=; b=cHJm/EEGytZIENb9B+/6fPHcOwi3di+xaAlLpdmYY3/6KnhoQqmOiXmtJT/uh5750y BDbxLxntuOpYnlILan7vTKBs3JYmGfhgLqHf+j6V+2CLLD//g6KnLxBwKXZDVUZyLbGV UIFW15QvMeVzN+Jg5Jbp8qWHVzSy0A5+qP+mboEdyZKkOfi767zQECP9nwZXST+YxXvd fcMy+OoAmlVSYDG3F1ymZTcMujIRaNVoWwH9TGiQz7hn5/DjDlhROGn96aasY+rnwvrU pUfBvwRHYym0I4QJh+n9PqzcrstU2nhOLSDunM2F+f8vgrP4UIbsllmVk1Ieqym2CCdi BvVQ== Received: by 10.236.115.130 with SMTP id e2mr13295339yhh.25.1346792561572; Tue, 04 Sep 2012 14:02:41 -0700 (PDT) Received: by 10.236.115.130 with SMTP id e2mr13295327yhh.25.1346792561390; Tue, 04 Sep 2012 14:02:41 -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 q2si4870904yhi.5.2012.09.04.14.02.41 (version=TLSv1/SSLv3 cipher=AES128-SHA); Tue, 04 Sep 2012 14:02:41 -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 D903A100052; Tue, 4 Sep 2012 14:02:40 -0700 (PDT) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <20550.27760.260327.470212@ruffy2.mtv.corp.google.com> Date: Tue, 04 Sep 2012 21:03:00 -0000 To: Yao Qi Cc: Subject: Re: [PATCH 1/4] new gdb_queue.h in common/. In-Reply-To: <503DE3E0.5070803@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> From: dje@google.com X-Gm-Message-State: ALoCoQlQ0/Ec4VA+zT26etcy1Wn/YeTg+9BVs6VfIcaBNA98A1NVRJyzlS1qIVbXQjiF7mwaIAITBZMECG4pDZZT/JDffh4VFla4y3u/tzSM/KYV+rqMI5fBdihyXev1g74ealDY4S0wmgVFlcHNMlrIVOQ3DMrvrPsCOPkAgwMr5mc1hJKZbklIfPHSmHXxp8RhXoMhY3ZjvRObaN4/DURG+uRELndBZQ== 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/msg00034.txt.bz2 Yao Qi writes: > On 08/25/2012 02:43 AM, dje@google.com wrote: > [...] > > 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. Yeah, OTOH this is how "extended" versions of API functions come into being. They're a wart in the API so I like to avoid them. E.g. consider htab_create_alloc vs htab_create_alloc_ex in the hashtab API. Some might not think this is a wart, alas I do, so this is one situation where I don't like to lazily add stuff (when I'm aware of it at the time ... :-)). OTOOH, since we're lazily adding the object version of the API anyway, I don't feel too strongly about it here. > 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. Thanks btw! Note that part of the support for pointers, ints, and objects in vec.h involves naming. That's missing here. So while we don't need to implement the _I (integral) and _O (object) versions of this, we still need the _P (pointer) naming (IMO). [Also, we don't have to implement deques and stacks here. I just wanted thought put into what it might look like, and see if that would influence the design here. I think(!) the API won't change, so I'm happy to leave it at that for now.] > 2012-08-29 Yao Qi > > * 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 . */ > + > +/* 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 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. 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). > +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 *? > +}; \ > + \ > +/* 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); \ It'd be better to move this assert above to right after assigning to p. > + 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); \ No need to put q->head == NULL in parens. > +} \ > + \ > +/* 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. > + \ > + if (q == NULL) \ > + return; \ assert q != NULL. > + \ > + 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. */ \ "and set data to V" is a bit confusing (since "data" is also a parameter). How about "and store the queue element in V" ? > + \ > +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. > + struct queue_ele_ ## TYPE *prev = NULL; \ > + \ > + if (q == NULL) \ > + return 0; \ assert q != 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; \ > + \ > + *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.. */ \ Apologies for not bringing this up earlier. _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 like thinner APIs than fatter ones, but in this case I'm not sure this is better (or worth it). Thoughts? > + \ > +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. > + \ > + 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; \ assert q != NULL. > + \ > + for (p = q->head; p != NULL; p = p->next) \ > + len++; \ > + return len; \ > +} \ blank line needed here > +/* 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. > +} \ > + > +/* External declarations for these functions. */ > +#define DECLARE_QUEUE_TYPE(TYPE) \ DECLARE_QUEUE_P > +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); \ > + > + In the following, where the macro takes multiple parameters, put each parameter in parens. > +#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) I'd rename FUNC to FREE_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