Re: [PATCH 1/4] new gdb_queue.h in common/.

[dje@google.com]

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  <yao@codesourcery.com>
 > 
 > 	* 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 <http://www.gnu.org/licenses/>.  */
 > +
 > +/* 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 <stdio.h>
 > +
 > +#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 */
 > --