From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 24529 invoked by alias); 29 Aug 2012 09:42:07 -0000 Received: (qmail 24516 invoked by uid 22791); 29 Aug 2012 09:42:05 -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,TW_CP 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; Wed, 29 Aug 2012 09:41:51 +0000 Received: from svr-orw-exc-10.mgc.mentorg.com ([147.34.98.58]) by relay1.mentorg.com with esmtp id 1T6emU-0004yH-A7 from Yao_Qi@mentor.com ; Wed, 29 Aug 2012 02:41:50 -0700 Received: from SVR-ORW-FEM-04.mgc.mentorg.com ([147.34.97.41]) by SVR-ORW-EXC-10.mgc.mentorg.com with Microsoft SMTPSVC(6.0.3790.4675); Wed, 29 Aug 2012 02:41:50 -0700 Received: from qiyao.dyndns.org (147.34.91.1) by svr-orw-fem-04.mgc.mentorg.com (147.34.97.41) with Microsoft SMTP Server id 14.1.289.1; Wed, 29 Aug 2012 02:41:48 -0700 Message-ID: <503DE3E0.5070803@codesourcery.com> Date: Wed, 29 Aug 2012 09:42: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> In-Reply-To: <20535.52070.49473.442620@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-08/txt/msg00845.txt.bz2 On 08/25/2012 02:43 AM, dje@google.com wrote: > > + > > +/* Define a new queue implementation. */ > > + > > +#define QUEUE_DEFINE_TYPE(TYPE) \ > > DEFINE_QUEUE_TYPE > Personally, I prefer operation prefixed with data type, such as queue_define_type or queue_enque, etc. However, I am OK with your suggestion. > Plus, seems like we should go all the way and provide I(integer),P(pointer),O(object_) support that vec.h does. > I'm ok with, e.g., just support pointers for now, leaving integers and objects for later. > OK. > Also, one can imagine wanting stacks and deques too. > [I only mention it so that we think about it. It would be unfortunate if this proliferated and only later, when it's much harder, do we decide we want some unification.] > > > +struct gdb_queue_ele_ ## TYPE \ > > +{ \ > > + struct gdb_queue_ele_ ## TYPE *next; \ > > + \ > > + struct TYPE *data; \ > > +}; \ > > + \ > > +struct gdb_queue_ ## TYPE \ > > +{ \ > > + struct gdb_queue_ele_ ## TYPE *head; \ > > + struct gdb_queue_ele_ ## TYPE *tail; \ > > +}; \ > > + \ > > +/* Typical enqueue operation. Put V into queue Q. */ \ > > + \ > > +void \ > > +gdb_queue_ ## TYPE ## _enque (struct TYPE *v, \ > > + struct gdb_queue_ ## TYPE *q) \ > > I think it'd be better to keep the queue argument as the first parameter. > [general rule for every such function] Sure, fixed. > > > +{ \ > > + struct gdb_queue_ele_ ## TYPE *p \ > > + = xmalloc (sizeof (struct gdb_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. Return NULL \ > > + if queue Q is empty. */ \ > > Returning NULL means one can't queue it as a value. > [mixed feelings on whether that's important enough] > assert fail if queue is empty? > > Plus if one went with vec's IPO support, should this return the int-like type? > [in which case deciding whether to return NULL becomes moot] > In version 1, I focused on Pointer. Considering Object and Int, deque should return TYPE here, and give an assert fail if something is unexpected. > > + \ > > +/* Return the element on tail, but don't remove it from queue. Return \ > > + NULL if queue is empty. */ \ > > + \ > > +struct TYPE * \ > > +gdb_queue_ ## TYPE ## _peek (struct gdb_queue_ ## TYPE *q) \ > > +{ \ > > + if (q== NULL || q->head == NULL) \ > > + return NULL; \ > > assert fail if q == NULL? > [missing space in q==] Add an assertion here. > > I wouldn't use "peek" to name a function that returns the tail. > "peek" should return the head. > > > + return q->head->data; \ > > Oh, heh, the function comment is wrong, it returns head. :-) > Oh, right. Get comment fixed. > > +} \ > > + \ > > +/* Return true if queue Q is empty. */ \ > > + \ > > +int \ > > +gdb_queue_ ## TYPE ## _is_empty (struct gdb_queue_ ## TYPE *q) \ > > +{ \ > > + return (q == NULL || q->head == NULL); \ > > assert q != NULL ? > > The vec functions handle vec == NULL because it's actually a pointer to the vector (so it can be resized which involves an xrealloc). > We don't need that here, so I'm thinking it'd be better to not be lax, and require q != NULL. > Agreed. gdb_assert is added here. > > +} \ > > + \ > > +/* Iterate over elements in the queue Q, and remove all of them for \ > > + which function MATCH returns true. */ \ > > + \ > > +void \ > > +gdb_queue_ ## TYPE ## _remove_all (struct gdb_queue_ ## TYPE *q, \ > > + int (*match) (struct TYPE *, void *), \ > > + void *data) \ > > +{ \ > > The "all" in "remove_all" is confusing (I'd expected it to empty the queue completely). > How about "remove_matching". > That sounds good. > > + struct gdb_queue_ele_ ## TYPE *p = NULL; \ > > + struct gdb_queue_ele_ ## TYPE *prev = NULL, *next = NULL; \ > > + \ > > + if (q == NULL) \ > > + return; \ > > + \ > > + 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; \ > > + \ > > + gdb_queue_ele_ ## TYPE ## _xfree (p->data); \ > > + xfree (p->data); \ > > 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. > > + xfree (p); \ > > + } \ > > + else \ > > + prev = p; \ > > + } \ > > +} \ > > + \ > > +/* Iterate over queue Q and remove one element for which function \ > > + MATCH returns true. */ \ > > I'd rather this be clearer and specify that the *first* matching element is returned. > > Here things get muddy as it's normal to return NULL if the value wasn't found, but that conflicts with the discussion above. I'm not sure what to do except return a bool indicating success, and pass in a pointer to the value to be returned. > Fixed it by returning boolean indicating success and pass a pointer of TYPE to the value returned. > > + \ > > +struct TYPE * \ > > +gdb_queue_ ## TYPE ## _remove (struct gdb_queue_ ## TYPE *q, \ > > + int (*match) (struct TYPE *, void *), \ > > + void *data) \ > > +{ \ > > + struct gdb_queue_ele_ ## TYPE *p = NULL; \ > > + struct gdb_queue_ele_ ## TYPE *prev = NULL; \ > > + struct TYPE *t = NULL; \ > > + \ > > + if (q == NULL) \ > > + return 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; \ > > + \ > > + t = p->data; \ > > + xfree (p); \ > > + return t; \ > > + } \ > > + else \ > > + prev = p; \ > > + } \ > > + return NULL; \ > > +} \ > > + \ > > +/* Find an element in queue Q for which function MATCH returns true. \ > > + Return NULL if not found. */ \ > > "Find the first element in queue ..." > > Return bool, and pass in a pointer into which to store the found value? > [these notes are just for discussion btw] ... likewise here. > > > + \ > > +struct TYPE * \ > > +gdb_queue_ ## TYPE ## _find (struct gdb_queue_ ## TYPE *q, \ > > + int (*match) (struct TYPE *, void *), \ > > + void *data) \ > > +{ \ > > + struct gdb_queue_ele_ ## TYPE *p = NULL; \ > > + \ > > + if (q == NULL) \ > > + return NULL; \ > > + \ > > + for (p = q->head; p != NULL; p = p->next) \ > > + { \ > > + if (match (p->data, data)) \ > > + return p->data; \ > > + } \ > > + return NULL; \ > > +} \ > > + \ > > +/* Allocate memory for queue. */ \ > > + \ > > +struct gdb_queue_ ## TYPE * \ > > +gdb_queue_ ## TYPE ## _alloc (void) \ > > +{ \ > > + struct gdb_queue_ ## TYPE *p; \ > > + \ > > + p = (struct gdb_queue_ ## TYPE *) xmalloc (sizeof (struct gdb_queue_ ## TYPE));\ > > + p->head = NULL; \ > > + p->tail = NULL; \ > > + return p; \ > > +} \ > > The queue destructor is missing. > destructor is added. > > + \ > > +/* Length of queue Q. */ \ > > + \ > > +int \ > > +gdb_queue_ ## TYPE ## _length (struct gdb_queue_ ## TYPE *q) \ > > +{ \ > > + struct gdb_queue_ele_ ## TYPE *p = NULL; \ > > + int len = 0; \ > > + \ > > + if (q == NULL) \ > > + return 0; \ > > + \ > > + for (p = q->head; p != NULL; p = p->next) \ > > + len++; \ > > + return len; \ > > +} \ > > + > > + > > +/* Define a variable of type gdb_queue_ ## TYPE. */ > > + > > +#define QUEUE_DEFINE_VAR(TYPE, VAR) \ > > + struct gdb_queue_ ## TYPE VAR = { NULL, NULL } > > DEFINE_QUEUE_VAR > > OTOH, I think I would delete this, and require the user to use gdb_queue_##TYPE##_alloc. > This macro is removed. > > + > > +/* External declarations for these functions. */ > > +#define QUEUE_DECLARE(TYPE) \ > > DECLARE_QUEUE_TYPE (akin to DEFINE_QUEUE_TYPE). Fixed. gdb_queue.h is renamed to queue.h, and all symbols gdb_queue_XXX are renamed to queue_XXX. 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. -- Yao gdb/ 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 + +#define DEFINE_QUEUE_TYPE(TYPE) \ +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 *); \ +}; \ + \ +/* 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); \ + 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); \ +} \ + \ +/* 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; \ + \ + if (q == NULL) \ + return; \ + \ + 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. */ \ + \ +int \ +queue_ ## TYPE ## _remove (struct queue_ ## TYPE *q, TYPE *v, \ + int (*match) (TYPE, void *), \ + void *data) \ +{ \ + struct queue_ele_ ## TYPE *p = NULL; \ + struct queue_ele_ ## TYPE *prev = NULL; \ + \ + if (q == NULL) \ + return 0; \ + \ + 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.. */ \ + \ +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; \ + \ + 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; \ + \ + for (p = q->head; p != NULL; p = p->next) \ + len++; \ + return len; \ +} \ +/* Free memory for queue Q. */ \ + \ +void \ +queue_ ## TYPE ## _free (struct queue_ ## TYPE *q) \ +{ \ + struct queue_ele_ ## TYPE *p, *next; \ + \ + if (q == NULL) \ + return; \ + \ + for (p = q->head; p != NULL; p = next) \ + { \ + next = p->next; \ + if (q->free_func) \ + q->free_func (p->data); \ + xfree (p); \ + } \ +} \ + +/* External declarations for these functions. */ +#define DECLARE_QUEUE_TYPE(TYPE) \ +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); \ + + +#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) +#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