From: Yao Qi <yao@codesourcery.com>
To: <gdb-patches@sourceware.org>
Subject: [PATCH 1/4] new gdb_queue.h in common/.
Date: Fri, 24 Aug 2012 02:26:00 -0000 [thread overview]
Message-ID: <1345775139-13576-2-git-send-email-yao@codesourcery.com> (raw)
In-Reply-To: <1345775139-13576-1-git-send-email-yao@codesourcery.com>
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
next prev parent reply other threads:[~2012-08-24 2:26 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-08-24 2:26 [RCF 0/4] A general notification in GDB RSP Yao Qi
2012-08-24 2:26 ` [PATCH 3/4] de-couple %Stop from notification: gdbserver Yao Qi
2012-08-24 2:26 ` [PATCH 2/4] de-couple %Stop from notification: gdb Yao Qi
2012-08-24 16:52 ` Yao Qi
2012-08-24 19:00 ` dje
2012-08-30 6:40 ` Yao Qi
2012-08-24 2:26 ` Yao Qi [this message]
2012-08-24 18:44 ` [PATCH 1/4] new gdb_queue.h in common/ dje
2012-08-24 18:49 ` Doug Evans
2012-08-29 9:42 ` Yao Qi
2012-09-04 21:03 ` dje
2012-09-07 2:47 ` Yao Qi
2012-09-10 20:47 ` dje
2012-09-12 14:24 ` Yao Qi
2012-09-13 15:55 ` dje
2012-09-14 2:38 ` Yao Qi
2012-09-11 16:50 ` Tom Tromey
2012-08-24 2:26 ` [PATCH 4/4] new notification "TEST" Yao Qi
2012-08-24 17:53 ` [RCF 0/4] A general notification in GDB RSP Pedro Alves
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1345775139-13576-2-git-send-email-yao@codesourcery.com \
--to=yao@codesourcery.com \
--cc=gdb-patches@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox