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

[Yao Qi <yao@codesourcery.com>]

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  <yao@codesourcery.com>
	    Doug Evans  <dje@google.com>

	* 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 <http://www.gnu.org/licenses/>.  */
+
+/* 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 <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_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