This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
[PATCH 1/4] new gdb_queue.h in common/.
Hi,
When writing the patches for 'general notification', I find queue is
used in many places, so I think we may need a general queue. This
queue not only have typical operations enqueue and dequeue, but also
has some have some operations like remove and remove_all.
gdb/
2012-08-24 Yao Qi <yao@codesourcery.com>
* common/gdb_queue.h: New.
---
gdb/common/gdb_queue.h | 283 ++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 283 insertions(+), 0 deletions(-)
create mode 100644 gdb/common/gdb_queue.h
diff --git a/gdb/common/gdb_queue.h b/gdb/common/gdb_queue.h
new file mode 100644
index 0000000..fa582c1
--- /dev/null
+++ b/gdb/common/gdb_queue.h
@@ -0,0 +1,283 @@
+/* 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
+ 'QUEUE_DEFINE_TYPE(TYPE)' is to define the new queue type for
+ 'struct TYPE', and macro 'QUEUE_DECLARE' *is to declare these external
+ APIs. When define a queue type for 'struct FOO', an extra helper function
+ 'gdb_queue_ele_FOO_xfree (struct FOO *foo)' has to be defined to release
+ the contents in foo, but not foo itself. */
+
+#ifndef GDB_QUEUE_H
+#define GDB_QUEUE_H
+
+#include <stdio.h>
+
+#include "libiberty.h" /* xmalloc */
+#include "gdb_assert.h"
+
+/* Define a new queue implementation. */
+
+#define QUEUE_DEFINE_TYPE(TYPE) \
+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) \
+{ \
+ 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. */ \
+ \
+struct TYPE * \
+gdb_queue_ ## TYPE ## _deque (struct gdb_queue_ ## TYPE *q) \
+{ \
+ struct gdb_queue_ele_ ## TYPE *p = NULL; \
+ struct TYPE *v = NULL; \
+ \
+ if (q == NULL) \
+ return NULL; \
+ p = q->head; \
+ \
+ if (q->head == q->tail) \
+ { \
+ q->head = NULL; \
+ q->tail = NULL; \
+ } \
+ else \
+ q->head = q->head->next; \
+ \
+ if (p != NULL) \
+ v = p->data; \
+ \
+ xfree (p); \
+ return v; \
+} \
+ \
+/* 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; \
+ return q->head->data; \
+} \
+ \
+/* Return true if queue Q is empty. */ \
+ \
+int \
+gdb_queue_ ## TYPE ## _is_empty (struct gdb_queue_ ## TYPE *q) \
+{ \
+ return (q == NULL || q->head == NULL); \
+} \
+ \
+/* 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) \
+{ \
+ 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); \
+ xfree (p); \
+ } \
+ else \
+ prev = p; \
+ } \
+} \
+ \
+/* Iterate over queue Q and remove one element for which function \
+ MATCH returns true. */ \
+ \
+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. */ \
+ \
+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; \
+} \
+ \
+/* 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 }
+
+/* External declarations for these functions. */
+#define QUEUE_DECLARE(TYPE) \
+struct gdb_queue_ ## TYPE; \
+extern void gdb_queue_ ## TYPE ## _enque (struct TYPE *v, \
+ struct gdb_queue_ ## TYPE *q); \
+extern struct TYPE * \
+ gdb_queue_ ## TYPE ## _deque (struct gdb_queue_ ## TYPE *q); \
+extern int \
+ gdb_queue_ ## TYPE ## _is_empty (struct gdb_queue_ ## TYPE *q); \
+extern void \
+ gdb_queue_ ## TYPE ## _remove_all (struct gdb_queue_ ## TYPE *q, \
+ int (*match) (struct TYPE *, void *), \
+ void *data); \
+extern struct TYPE * \
+ gdb_queue_ ## TYPE ## _remove (struct gdb_queue_ ## TYPE *q, \
+ int (*match) (struct TYPE *, void *), \
+ void *data); \
+extern struct TYPE * \
+ gdb_queue_ ## TYPE ## _find (struct gdb_queue_ ## TYPE *q, \
+ int (*match) (struct TYPE *, void *), \
+ void *data); \
+extern struct gdb_queue_ ## TYPE * \
+ gdb_queue_ ## TYPE ## _alloc (void); \
+extern void gdb_queue_ele_ ## TYPE ## _xfree (struct TYPE *); \
+extern int gdb_queue_ ## TYPE ## _length (struct gdb_queue_ ## TYPE *q);\
+extern struct TYPE * \
+ gdb_queue_ ## TYPE ## _peek (struct gdb_queue_ ## TYPE *q); \
+
+#endif /* GDB_QUEUE_H */
--
1.7.7.6