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

dje@google.com dje@google.com
Tue Sep 4 21:03:00 GMT 2012


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  <yao@codesourcery.com>
 > 
 > 	* 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 <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

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



More information about the Gdb-patches mailing list