From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16894 invoked by alias); 12 Sep 2012 14:24:23 -0000 Received: (qmail 16864 invoked by uid 22791); 12 Sep 2012 14:24:17 -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; Wed, 12 Sep 2012 14:24:03 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1TBnrG-00079v-I0 from Yao_Qi@mentor.com ; Wed, 12 Sep 2012 07:24:02 -0700 Received: from SVR-ORW-FEM-02.mgc.mentorg.com ([147.34.96.206]) by svr-orw-fem-01.mgc.mentorg.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Wed, 12 Sep 2012 07:24:02 -0700 Received: from qiyao.dyndns.org (147.34.91.1) by svr-orw-fem-02.mgc.mentorg.com (147.34.96.168) with Microsoft SMTP Server id 14.1.289.1; Wed, 12 Sep 2012 07:24:00 -0700 Message-ID: <50509AD9.7010408@codesourcery.com> Date: Wed, 12 Sep 2012 14:24: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> <50495FFA.5080107@codesourcery.com> <20558.20947.170261.875294@ruffy2.mtv.corp.google.com> In-Reply-To: <20558.20947.170261.875294@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/msg00199.txt.bz2 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. > 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) \ +{ \ + 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; \ + \ + 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 *), \ + 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) \ + { \ + 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