From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15667 invoked by alias); 24 Aug 2012 02:26:19 -0000 Received: (qmail 15624 invoked by uid 22791); 24 Aug 2012 02:26:15 -0000 X-SWARE-Spam-Status: No, hits=-4.4 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,KHOP_THREADED,RCVD_IN_HOSTKARMA_W,RCVD_IN_HOSTKARMA_WL X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 24 Aug 2012 02:25:56 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1T4jau-0003vz-4u from Yao_Qi@mentor.com for gdb-patches@sourceware.org; Thu, 23 Aug 2012 19:25:56 -0700 Received: from SVR-ORW-FEM-04.mgc.mentorg.com ([147.34.97.41]) by svr-orw-fem-01.mgc.mentorg.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Thu, 23 Aug 2012 19:25:56 -0700 Received: from qiyao.dyndns.org.dyndns.org (147.34.91.1) by svr-orw-fem-04.mgc.mentorg.com (147.34.97.41) with Microsoft SMTP Server id 14.1.289.1; Thu, 23 Aug 2012 19:25:54 -0700 From: Yao Qi To: Subject: [PATCH 1/4] new gdb_queue.h in common/. Date: Fri, 24 Aug 2012 02:26:00 -0000 Message-ID: <1345775139-13576-2-git-send-email-yao@codesourcery.com> In-Reply-To: <1345775139-13576-1-git-send-email-yao@codesourcery.com> References: <1345775139-13576-1-git-send-email-yao@codesourcery.com> MIME-Version: 1.0 Content-Type: text/plain X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2012-08/txt/msg00704.txt.bz2 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 * 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 . */ + +/* 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 + +#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