This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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  <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
+
+#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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]