From patchwork Thu Nov 26 18:44:02 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pierre Riteau X-Patchwork-Id: 39581 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [199.232.76.165]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 9934F1007D1 for ; Fri, 27 Nov 2009 05:48:36 +1100 (EST) Received: from localhost ([127.0.0.1]:58824 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NDjOL-0007ew-IC for incoming@patchwork.ozlabs.org; Thu, 26 Nov 2009 13:48:33 -0500 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NDjLa-0004ot-0F for qemu-devel@nongnu.org; Thu, 26 Nov 2009 13:45:42 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NDjLR-0004dW-9o for qemu-devel@nongnu.org; Thu, 26 Nov 2009 13:45:37 -0500 Received: from [199.232.76.173] (port=41007 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NDjLQ-0004dN-Ss for qemu-devel@nongnu.org; Thu, 26 Nov 2009 13:45:32 -0500 Received: from mail1-relais-roc.national.inria.fr ([192.134.164.82]:53691) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_ARCFOUR_SHA1:16) (Exim 4.60) (envelope-from ) id 1NDjLQ-0006iJ-AT for qemu-devel@nongnu.org; Thu, 26 Nov 2009 13:45:32 -0500 X-IronPort-AV: E=Sophos;i="4.47,295,1257116400"; d="scan'208";a="40878408" Received: from elfe.irisa.fr (HELO localhost.localdomain) ([131.254.60.12]) by mail1-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 26 Nov 2009 19:45:29 +0100 From: Pierre Riteau To: Liran Schour , qemu-devel@nongnu.org Date: Thu, 26 Nov 2009 19:44:02 +0100 Message-Id: <1259261046-32650-3-git-send-email-Pierre.Riteau@irisa.fr> X-Mailer: git-send-email 1.6.5 In-Reply-To: <1259261046-32650-2-git-send-email-Pierre.Riteau@irisa.fr> References: <1259261046-32650-1-git-send-email-Pierre.Riteau@irisa.fr> <1259261046-32650-2-git-send-email-Pierre.Riteau@irisa.fr> X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. Cc: Pierre Riteau Subject: [Qemu-devel] [PATCH 2/6] Import a simple queue implementation from NetBSD X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Pierre Riteau --- qemu-queue.h | 109 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 105 insertions(+), 4 deletions(-) diff --git a/qemu-queue.h b/qemu-queue.h index 8877efd..1d07745 100644 --- a/qemu-queue.h +++ b/qemu-queue.h @@ -1,8 +1,9 @@ -/* $NetBSD: queue.h,v 1.45.14.1 2007/07/18 20:13:24 liamjfoy Exp $ */ +/* $NetBSD: queue.h,v 1.52 2009/04/20 09:56:08 mschuett Exp $ */ /* * Qemu version: Copy from netbsd, removed debug code, removed some of - * the implementations. Left in lists, tail queues and circular queues. + * the implementations. Left in lists, simple queues, tail queues and + * circular queues. */ /* @@ -40,8 +41,8 @@ #define QEMU_SYS_QUEUE_H_ /* - * This file defines three types of data structures: - * lists, tail queues, and circular queues. + * This file defines four types of data structures: + * lists, simple queues, tail queues, and circular queues. * * A list is headed by a single forward pointer (or an array of forward * pointers for a hash table header). The elements are doubly linked @@ -50,6 +51,13 @@ * or after an existing element or at the head of the list. A list * may only be traversed in the forward direction. * + * A simple queue is headed by a pair of pointers, one the head of the + * list and the other to the tail of the list. The elements are singly + * linked to save space, so elements can only be removed from the + * head of the list. New elements can be added to the list after + * an existing element, at the head of the list, or at the end of the + * list. A simple queue may only be traversed in the forward direction. + * * A tail queue is headed by a pair of pointers, one to the head of the * list and the other to the tail of the list. The elements are doubly * linked so that an arbitrary element can be removed without a need to @@ -140,6 +148,99 @@ struct { \ /* + * Simple queue definitions. + */ +#define QSIMPLEQ_HEAD(name, type) \ +struct name { \ + struct type *sqh_first; /* first element */ \ + struct type **sqh_last; /* addr of last next element */ \ +} + +#define QSIMPLEQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).sqh_first } + +#define QSIMPLEQ_ENTRY(type) \ +struct { \ + struct type *sqe_next; /* next element */ \ +} + +/* + * Simple queue functions. + */ +#define QSIMPLEQ_INIT(head) do { \ + (head)->sqh_first = NULL; \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (head)->sqh_first = (elm); \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.sqe_next = NULL; \ + *(head)->sqh_last = (elm); \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (listelm)->field.sqe_next = (elm); \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_REMOVE_HEAD(head, field) do { \ + if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)\ + (head)->sqh_last = &(head)->sqh_first; \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_REMOVE(head, elm, type, field) do { \ + if ((head)->sqh_first == (elm)) { \ + QSIMPLEQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->sqh_first; \ + while (curelm->field.sqe_next != (elm)) \ + curelm = curelm->field.sqe_next; \ + if ((curelm->field.sqe_next = \ + curelm->field.sqe_next->field.sqe_next) == NULL) \ + (head)->sqh_last = &(curelm)->field.sqe_next; \ + } \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_FOREACH(var, head, field) \ + for ((var) = ((head)->sqh_first); \ + (var); \ + (var) = ((var)->field.sqe_next)) + +#define QSIMPLEQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->sqh_first); \ + (var) && ((next = ((var)->field.sqe_next)), 1); \ + (var) = (next)) + +#define QSIMPLEQ_CONCAT(head1, head2) do { \ + if (!QSIMPLEQ_EMPTY((head2))) { \ + *(head1)->sqh_last = (head2)->sqh_first; \ + (head1)->sqh_last = (head2)->sqh_last; \ + QSIMPLEQ_INIT((head2)); \ + } \ +} while (/*CONSTCOND*/0) + +#define QSIMPLEQ_LAST(head, type, field) \ + (QSIMPLEQ_EMPTY((head)) ? \ + NULL : \ + ((struct type *)(void *) \ + ((char *)((head)->sqh_last) - offsetof(struct type, field)))) + +/* + * Simple queue access methods. + */ +#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) +#define QSIMPLEQ_FIRST(head) ((head)->sqh_first) +#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + + +/* * Tail queue definitions. */ #define Q_TAILQ_HEAD(name, type, qual) \